目录
1.代码内容，共有两关
自定义函数部分：
#include <stdio.h>
#include <stdlib.h>
/*此处是顺序线性表数据结构定义*/
typedef int DataType;
struct seqList
{//有3个数据成员
int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM
int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum
DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址
};
typedef struct seqList *PseqList;
/*创建空的顺序线性表，能存放的最大元素个数为 m*/
PseqList createNullList_seq(int m)
{ //若m=0，则返回NULL
PseqList plist = (struct seqList *)malloc(sizeof(struct seqList));
if(plist == NULL) return NULL; //分配空间失败
plist->MAXNUM = m ;
plist->curNum = 0;
plist->element = (DataType *)malloc(sizeof(DataType)*m);
if(plist->element == NULL)
{
free(plist);
return NULL;
}
return plist;
}
/*在线性表表尾插入数据元素,返回值0表示插入失败，返回值1表示在表尾插入成功*/
int insertP_tail(PseqList plist , int x)
{
if(plist->curNum == plist->MAXNUM) //若表满，则无法插入
{
printf("list if full !");
return 0;
}
plist->element[plist->curNum] = x ;
plist->curNum++;
return 1;
}
/*回收线性表占用的空间*/
int destroyList_seq(PseqList plist)
{
//返回值为销毁的线性表中现有数据元素的个数，若待销毁的线性表不存在，则返回0
if(plist == NULL) return 0;
int m = plist->curNum;
free(plist->element);
free(plist);
return m;
}
void printList_seq(PseqList plist)
{//逐个输出线性表的元素，相邻的两个数据元素之间以一个空格为分隔符隔开
for(int i=0;i<plist->curNum;i++)
printf("%d ",plist->element[i]);
}
//第一关:求顺序线性表中连续子表（最少有一个元素）的最大和并输出
int seqMaxSum(PseqList plist)
{
int sum,max,i;
sum = max = plist->element[0];
for (i = 1; i < plist->curNum; i++){
if (sum >= 0)
sum += plist->element[i];
else if (sum < 0)
sum = plist->element[i];
if (max <= sum)
max = sum;
}
return max;
}
//第二关：寻找线性表中没有出现的最小的正整数
int findMinNumber(PseqList plist)
{
//若线性表为空，则返回0
if (!plist->curNum)
return 0;
int a[100],i,j;
for (i = 0; i < 100; i++)
a[i] = 0;
for (i = 0; i < plist->curNum; i++)
if (plist->element[i] > 0)
a[plist->element[i]] = 1;
for (j = 1; j < 60; j++)
if (!a[j])
return j;
}
main函数部分：
int main()
{
int num , data ;
int pos[2];
printf("请输入元素的个数\n");
scanf("%d",&num);
PseqList plist = createNullList_seq(num);
printf("请输入%d个元素\n",num);
for(int i=0;i<num;i++)
{
scanf("%d",&data);
insertP_tail( plist ,data);
}
printf("%d",seqMaxSum(plist));//顺序线性表中连续子表（最少有一个元素）的最大和并输出
printf("%d",findMinNumber(plist));//寻找线性表中没有出现的最小的正整数
printf("请输入待查找的元素：\n");
scanf("%d",&data);
findPos(plist,data,pos);
printf("%d的起始位置和终止位置：\n",data);
printf("%d %d",pos[0],pos[1]);
}
2.代码解析
-
第一关：
利用两个变量sum和max。sum用来储存相加的结果，max则是储存最大的sum。
对于上一轮循环中已经加上上一轮 plist->element[i] 的 sum：
此时若小于0：
说明不如不加，拿下一个 plist->element[i] 的值把此时的 sum 覆盖掉，即舍弃了之前所加的值。如 {5，-9，6}，第二轮中 sum 为 -4，则拿 6 把 -4 覆盖掉。
此时若大于0：
说明可以继续加下去，直接加上下一个值，这个过程中反正最大的 sum 会被储存在 max 里，因此可以冒着 sum 变小的风险继续加下去。
注意：
整个 sum 和 max 的值的变化要一气呵成，先把 sum 和 max 都初始化为 plist->element[0]，之后的 循环从 plist->element[1] 开始。
-
第二关：
利用新建数组，当线性表中元素出现正值，把数组中该下标的元素置1。
如：plist->element = {1，2，-3，4，8，-1，4}
则新建数组中
a[1] = 1;
a[2] = 1;
a[4] = 1;
a[8] = 1;
之后进行数组遍历，从下标为1开始，从小到大看下标为几的元素值为0（即没有被我们置1），则该下标即为我们要找的最小正整数。