搜索
//线性表的顺序结构算法实现#includestdio.h#includestdlib.h#defineOVERFLOW-2#defineOK1#defineERROR0//数据类型说明typedefintElemType;typedefintStatus;#defineList_init_size100//线性表存储空间初始分配量#defineListincrement10//线性表存储空间分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量//(以sizeof(ElemType)为单位)}sqlist;//初始化线性表：StatusInitList(sqlist&L){//构造一个空线性表LL.elem=(ElemType*)malloc(List_init_size*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=List_init_size;returnOK;}//在一个空的线性表中输入N个数据：Statussqlistinput(sqlist&L,intn){inti=0;if(nL.listsize)returnERROR;for(;in;i++){scanf(%d,&L.elem[i]);}L.length=n;returnOK;}//判线性表是否为空StatusListEmpty(sqlistL){if(!L.length)returnERROR;elsereturnOK;}//求线性表的长度StatusListLength(sqlistL){returnL.length;}//将线性表L的数据输出：Statussqlistoutput(sqlistL){inti;for(i=0;iListLength(L);i++)printf(%4d,L.elem[i]);printf(\n);returnOK;}//取线性表的第i个元素，其结果保存在e中StatusGetElem(sqlistl,inti,ElemType&e){if(i1||il.length+1)returnERROR;e=l.elem[i-1];returnOK;}//定义两个数据元素相等的比较函数Statusequal(ElemTypee1,ElemTypee2){if(e1==e2)returnOK;elsereturnERROR;}//根据compare()函数在线性表中定位元素e的位置intLocateElem_sq(sqlistL,ElemTypee,Status(*compare)(ElemType,ElemType))//成功返回位序，否则返回0{inti=1;ElemType*p;p=L.elem;while(i=L.length&&!(*compare)(*p++,e))++i;if(i=L.length)returni;elsereturn0;}//locateElem_sq//在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息StatusPriorElem(sqlistL,ElemTypecur_e,ElemType&pre_e){intpos;pos=LocateElem_sq(L,cur_e,equal);if(pos==0)returnERROR;elseif(pos==1)returnOVERFLOW;//overflow表示位于第一个else{GetElem(L,pos-1,pre_e);returnOK;}}//在线性表中求某元素的后继结点StatusNextElem(sqlistL,ElemTypecur_e,ElemType&next_e){intpos;pos=LocateElem_sq(L,cur_e,equal);if(pos==0)returnERROR;elseif(pos==L.length)returnOVERFLOW;//overflow表示最后一个else{GetElem(L,pos+1,next_e);returnOK;}}//在线性表中插入一个元素StatusListinsert_sq(sqlist&L,inti,ElemTypee){ElemType*p,*q,*newbase;if(i1||iL.length+1)returnERROR;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]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//listinsert_sq;//在线性表中删除第i个元素，其结果保留在e中StatusListdelete_sq(sqlist&l,inti,ElemType&e){ElemType*p,*q;if(i1||il.length+1)returnERROR;p=&(l.elem[i-1]);e=*p;q=l.elem+l.length-1;for(++p;p=q;++p)*(p-1)=*p;--l.length;returnOK;}//listdelete_sq;//将la与lb线性表归并到lcvoidmergelist_sq(sqlistla,sqlistlb,sqlist&lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=la.elem;pb=lb.elem;lc.listsize=lc.length=la.length+lb.length;pc=lc.elem=(ElemType*)malloc(lc.listsize*sizeof(ElemType));if(!lc.elem)exit(OVERFLOW);pa_last=la.elem+la.length-1;pb_last=lb.elem+lb.length-1;while((pa=pa_last)&&(pb=pb_last))if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;while(pa=pa_last)*pc++=*pa++;while(pb=pb_last)*pc++=*pb++;}//mergelist_sq;//对线性表的元素进行排序Statussortsqlist(sqlist&L){//冒泡排序inti,j,len;ElemTypet;len=ListLength(L);for(i=len-1;i=1;i--)for(j=0;ji;j++){if(L.elem[j]L.elem[j+1]){t=L.elem[j];L.elem[j]=L.elem[j+1];L.elem[j+1]=t;}}returnOK;}voidmain(){sqlistla,lb,lc;intn,m,i,e,k,cur_e,pre_e,next_e;//建立线性表，并输入输出线性表的数据InitList(la);InitList(lb);printf(pleaseinputla'snumbers:n（请输入线性表la的元素个数n）\n);scanf(%d,&n);printf(pleaseinputlannumbers:(请输入线性表la的n个元素)\n);sqlistinput(la,n);sqlistoutput(la);printf(\n);//调用插入函数，对线性表进行插入操作printf(请输入要插入的元素的位置与插入的值\n);scanf(%d%d,&i,&e);Listinsert_sq(la,i,e);sqlistoutput(la);//调用删除函数，对线性表进除删操作printf(请输入要删除的元素的位置\n);scanf(%d,&i);Listdelete_sq(la,i,e);printf(thedeledatais%d\n,e);sqlistoutput(la);printf(pleaseinputthegetdata'slocate\n);scanf(%d,&i);//调用GetElem()函数，取第I个位置的元素的值。GetElem(la,i,e);printf(thegetdatais%d\n,e);printf(pleaseinputthelocateelem'sdata:cur_e\n);//调用LocateElem_sq()函数，求元素cur_e的位置。scanf(%d,&cur_e);k=LocateElem_sq(la,cur_e,equal);printf(thelocateis%d\n,k);//调用PriorElem()函数，求元素cur_e的前驱。printf(pleaseinputthecur_edata\n);scanf(%d,&cur_e);PriorElem(la,cur_e,pre_e);printf(thepre_eis%d\n,pre_e);//调用NextElem()函数，求元素cur_e的后继。printf(pleaseinputthecur_edata\n);scanf(%d,&cur_e);NextElem(la,cur_e,next_e);printf(thenext_eis%d\n,next_e);//建立两个线性表并排序然后归并printf(pleaseinputlb'snumbers:m\n);scanf(%d,&m);printf(pleaseinputlbmnumbers:\n);sqlistinput(lb,m);printf(\n);sqlistoutput(lb);sortsqlist(la);printf(thesortlistlais:\n);sqlistoutput(la);sortsqlist(lb);printf(thesortlistlbis:\n);sqlistoutput(lb);mergelist_sq(la,lb,lc);printf(laandlb'smergelistis:\n);sqlistoutput(lc);}