线性表顺序结构算法实现.doc

/线性表的顺序结构算法实现 #include stdio.h #include stdlib.h # define OVERFLOW -2 # define OK 1 #define ERROR 0 /数据类型说明 typedef int ElemType; typedef int Status; # define List_init_size 100/线性表存储空间初始分配量# define Listincrement 10/线性表存储空间分配增量typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize;/当前分配的存储容量 / (以sizeof(ElemType)为单位)sqlist;/初始化线性表：Status InitList(sqlist &L) /构造一个空线性表L L.elem=(ElemType *) malloc(List_init_size*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize= List_init_size; return OK;/在一个空的线性表中输入N个数据：Status sqlistinput(sqlist &L,int n)int i=0; if(nL.listsize)return ERROR; for(;in;i+) scanf(%d,&L.elemi); L.length=n; return OK; /判线性表是否为空Status ListEmpty(sqlist L)if (!L.length) return ERROR; else return OK; /求线性表的长度Status ListLength(sqlist L) return L.length; /将线性表L 的数据输出：Status sqlistoutput(sqlist L)int i; for(i=0;iListLength(L);i+) printf(%4d,L.elemi); printf(n); return OK; /取线性表的第i个元素，其结果保存在e中Status GetElem(sqlist l,int i,ElemType &e) if (il.length+1) return ERROR; e=l.elemi-1; return OK; /定义两个数据元素相等的比较函数Status equal(ElemType e1,ElemType e2)if (e1=e2) return OK; else return ERROR; /根据compare()函数在线性表中定位元素e的位置int LocateElem_sq(sqlist L,ElemType e,Status (*compare)(ElemType,ElemType) /成功返回位序，否则返回0 int i=1; ElemType *p; p=L.elem; while(i=L.length &!(*compare)(*p+,e) +i; if (i=L.length) return i; else return 0;/ locateElem_sq/在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息Status PriorElem(sqlist L,ElemType cur_e,ElemType &pre_e) int pos; pos=LocateElem_sq(L,cur_e,equal); if(pos=0) return ERROR; else if(pos=1) return OVERFLOW; /overflow 表示位于第一个 else GetElem(L,pos-1,pre_e); return OK; /在线性表中求某元素的后继结点Status NextElem(sqlist L,ElemType cur_e,ElemType &next_e) int pos; pos=LocateElem_sq(L,cur_e,equal); if(pos=0) return ERROR; else if(pos=L.length) return OVERFLOW; /overflow 表示最后一个 else GetElem(L,pos+1,next_e); return OK; /在线性表中插入一个元素Status Listinsert_sq(sqlist &L,int i,ElemType e) ElemType *p,*q,*newbase; if (iL.length+1) return ERROR; 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.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ listinsert_sq;/在线性表中删除第i个元素，其结果保留在e中Status Listdelete_sq(sqlist &l,int i,ElemType &e) ElemType *p,*q; if (il.length+1) return ERROR; p=&(l.elemi-1); e=*p; q=l.elem+l.length-1; for(+p;p=q;+p) *(p-1)=*p; -l.length; return OK;/ listdelete_sq;/将la与lb线性表归并到lcvoid mergelist_sq(sqlist la,sqlist lb,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=1;i-) for(j=0;jL.elemj+1) t=L.elemj; L.elemj=L.elemj+1 ; L.elemj+1=t; return OK; void main()sqlist la,lb,lc; int n,m,i,e,k,cur_e,pre_e,next_e; /建立线性表，并输入输出线性表的数据 InitList(la);InitList(lb); printf(please input las numbers:n（请输入线性表la的元素个数n）n); scanf(%d,&n); printf(please input la n numbers:( 请输入线性表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(the dele data is %dn,e); sqlistoutput(la); printf(please input the get datas locaten); scanf(%d,&i);/调用GetElem()函数，取第I个位置的元素的值。 GetElem(la,i,e); printf(the get data is %dn,e); printf(please input the locateelems data :cur_en);/调用LocateElem_sq()函数，求元素cur_e的位置。scanf(%d,&cur_e); k=LocateElem_sq(la,cur_e,equal); printf(the locate is %dn,k); /调用PriorElem()函数，求元素cur_e的前驱。 printf(please input the cur_e datan); scanf(%d,&cur_e); PriorElem(la,cur_e,pre_e); printf(the pre_e is %dn,pre_e); /调用NextElem()函数，求元素cur_e的后继。 printf(please input the cur_e datan); scanf(%d,&cur_e); NextElem(la,cur_e,next_e); printf(the next_e is %dn,next_e); /建立两个线性表并排序然后归并 printf(please input lbs numbers:mn); scanf(%d,&m); printf(please input lb m numbers:n); sqlistinput(lb,m); printf(n); s