数据结构作业1

1、已知顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个元素X后保持该顺序表的有序排列。要求算法的空间复杂度为。#includestdio.h#defineMAXSIZE100#defineOK1#defineERROR0typedefintElemType;//定义线性表typedefstruct{ElemTypeelem[MAXSIZE];intlast;}SeqList;//创建空表voidInitlist(SeqList*L){L-last=-1;}//输入递增有序顺序表voidputseqList(SeqList*L,intn){inti;for(i=0;in;i++)scanf(%d,&(L-elem[i]));L-last=L-last+n;}//求表长intLenList(SeqList*L){intLen;Len=L-last+1;returnLen;}//判断插入位置intPositionList(SeqList*L,intX){intj;for(j=0;j=L-last;j++)if(XL-elem[j])//如果找到位置就返回地址，否则知道循环结束再返回最后一个//地址returnj+1;//注意这里要加1，下标j表示第j+1个元素，所以返回j+1return(L-last+1);//这里不能用else，否则就属于for循环里面的了}//插入元素intInsList(SeqList*L,inti,inte){intk;if((i1)||(iL-last+2)){printf(插入位置不合理);return(ERROR);}if(L-last=MAXSIZE-1){printf(表已满无法插入);return(ERROR);}for(k=L-last;k=i-1;k--)L-elem[k+1]=L-elem[k];L-elem[i-1]=e;L-last++;return(OK);}//输出元素intOutputSeqList(SeqList*L){inti;for(i=0;i=L-last;i++)printf(%d,,L-elem[i]);return(L-elem[i]);}//主程序voidmain(){ints,c;SeqListL;Initlist(&L);printf(请输入顺序表长度:);scanf(%d,&s);printf(请输入递增顺序表:);putseqList(&L,s);LenList(&L);printf(表长为%d\n,LenList(&L));printf(请输入要插入的元素:);scanf(%d,&c);InsList(&L,PositionList(&L,c),c);OutputSeqList(&L);printf(\n);}2、从顺序表L中删除所有值为X的元素。voiddeleteValue（SeqList&L，DataTypevalue）{inti,j;for(i=L.n-1;i=0;i--)if(L.data[i]==value){for(j=i+1;jL.n;j++)L.data[j-1]=L.data[j];L.n--;}}3、从顺序表L中删除重复的元素，并使剩余的元素的相对次序保持不变。Voiddelsame(SqList&L){inti,j,k;if(L.length0){j=0;for(i=1;iL.length;i++){k=0;while(k=j&&L.data[k]!=L.data[i])k++;if(kj){j++;L.data[j]=L.data[i];}}L.length=j+1;}}4、有一个单链表，其结点的元素值以递增有序排列，设计一个算法删除该单链表中多余的元素值相同的结点。Voidf9(LinklistA){p=A-next;While(p&&p-next){if(p-data==p-next-data){q=p-next;p-next=q-next;free(q);}elsep=p-next;}}