数据结构-线性表输入-输出-插入-删除-查找

创建一个线性表实现输入，输出，插入，删除，定位。（注意：不论在调用哪个函数前，都要先使L.elem=a，就是使指针elem回到数组a的首地址。）#includestdio.h#includemalloc.h#includestdlib.h#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;//接下来ElemType代表的就是inttypedefintStatus;//Status也代表intinti,*p,*q;//p，q都是指针类型ElemTypee;typedefstruct{ElemType*elem;//定义成指针类型//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//***********************构建空的线性表*************************//StatusInitList_Sq(SqList&L)//构建一个空的线性表L{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//**************************线性表输入函数*********************//voidinput(SqList&L)//输入函数{scanf(%d,L.elem);//要先输入一个，不然一开始就是0，无法进行循环while(*L.elem)//加*是因为elem是指针，加之后才代表值{L.elem++;//输入后指针后移L.length++;//表长加1scanf(%d,L.elem);//循环中也要再输入}}//**************************线性表打印函数********************//voidprint(SqList&L)//输出函数{intn;for(n=0;nL.length;n++){printf(%d\t,*L.elem);L.elem++;//输出后指针后移}}//***********线性表插入函数（在第i个位置插入一个数据e）*************//StatusListInsert_Sq(SqList&L,inti,ElemTypee)//插入函数{//在顺序线性表L中第i个位置之前插入新的元素e//i的合法值为1=i=ListLength.Sq(L)+1Status*newbase;指针类型。因为elem是指针类型if(i1||iL.length+1)returnERROR;//i值不合法if(L.length=L.listsize)//当前存储空间已满，增加分配{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));//分配存储空间if(!newbase)exit(OVERFLOW);//存储分配失败，跳回操作系统L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增加1returnOK;}//*********线性表删除函数（删除第i个位置，并用e返回删除的数据）********//StatusListDelete_Sq(SqList&L,inti,ElemType&e)//删除函数引用调用{//在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1=i=ListLength.Sq(L)if((i1)||(iL.length))returnERROR;//i值不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p=q;++p)*(p-1)=*p;//在被删除元素位置后面的元素左移--L.length;//表长减1returnOK;}//****线性表查找(定位)函数（找到第1个与e相等的值，返回其位置i）********//intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))//定位函数{//在顺序线性表L中查找第1个值与e满足compare()的元素的位序//若找到，则返回其在L中的位序，否则返回0i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while(i=L.length&&!(*compare)(*p++,e))++i;//将表L中的元素依次与e进行比较if(i=L.length)returni;elsereturn0;}//**************************比较函数*******************************//StatusCompare(ElemTypem,ElemTypee)//比较的是实数，不用定义成指针{if(m==e)returnOK;elsereturnERROR;}//*********************主函数**********************//voidmain(){SqListL;inta[100];if(InitList_Sq(L)){L.elem=a;//将数组的首地址赋给指针elemprintf(请输入数据：\n);input(L);//输入线性表L}L.elem=a;//指针elem回到数组首地址，//因为在用的过程中指针已经移动，所以必须归位，才能再从第一个用起。printf(您输入的数据为：\n);print(L);//输出线性表Lprintf(\n);printf(请输入插入元素的位置:);scanf(%d,&i);printf(请输入新元素:);scanf(%d,&e);//指针elem回到数组首地址L.elem=a;if(ListInsert_Sq(L,i,e))//在指定位置插入待插入元素{printf(插入元素后的表含%d个元素:\n,L.length);L.elem=a;print(L);//输出插入元素后的新表L}printf(\n);L.elem=a;//指针elem回到数组首地址printf(请输入删除元素的位置:);scanf(%d,&i);if(ListDelete_Sq(L,i,e))//删除指定元素{printf(您删除的元素为:%d\n,e);printf(删除元素后的表含%d个元素\n,L.length);L.elem=a;//指针elem回到数组首地址print(L);//输出删除元素后的新表L}printf(\n);L.elem=a;//指针elem回到数组首地址printf(请输入您要找的元素的值:);scanf(%d,&e);if(LocateElem_Sq(L,e,Compare))//找出指定元素在表L中的位序printf(元素%d在顺序线性表L的位序为:%d\n,e,i);elseprintf(您输入的元素不在表L中\n);}