严蔚敏版数据结构所有算法代码

严蔚敏版数据结构所有算法代码------------------------线性数据结构-----------------------------2013年7月//线性表、链表//栈、队列//数组、广义表//串-------------------------线性表----------------------typedefstruct{charname[20];//注意如果应用指针的形式//在初始化每个结点时一定要先为结点中的每个变量开辟内存空间charsex;charaddr[100];unsignedintage;charphonenum[20];}node;//结点描述typedefstruct{node*p;intlength;//当前顺序表长度intlistsize;//当前分配的线性表长度}list;//线性表描述listL;//定义一个线性表intinitlist(list&l)//构造一个空的线性表{l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node));if(!(l.p))exit(1);l.length=0;l.listsize=LIST_INIT_SIZE;returntrue;}voiddestroylist(list&l)//销毁线性表操作{if(l.p!=NULL){free(l.p);printf(销毁成功!\n);}elseprintf(线性表不存在！\n);}intclearlist(list&l)//将线性表置空操作{if(l.p==NULL){printf(线性表不存在！\n);returnfalse;}else{free(l.p);l.p=(node*)malloc(l.listsize*sizeof(node));l.length=0;}returntrue;}intlistempty(list&l)//判断线性表是否为空表{if(l.p==NULL)returntrue;elsereturnfalse;}intgetelem(list&l,inti,node&e)//用e返回表中第i个数据元素{if(l.p==NULL)returnfalse;elsee=l.p[i-1];returntrue;}intpriorelem(list&l,inti,node&pre_e)//得到第i个元素的前驱元素{if(i==0||l.p==NULL)returnfalse;elsepre_e=l.p[i-1];returntrue;}intnextelem(list&l,inti,node&next_e)//得到表中第i个元素的后继元素{if(i=l.length||l.p==NULL)returnfalse;elsenext_e=l.p[i+1];returntrue;}intinsertlist(list&l,inti,node&e)//将元素e插入到表l中第i个元素的后面{node*q,*k;if(i1||il.length+1)returnfalse;if(l.length=l.listsize){l.p=(node*)realloc(l.p,(l.listsize+LISTINCREMENT)*sizeof(node));if(!l.p)exit(1);l.listsize+=LISTINCREMENT;}k=&l.p[i-1];for(q=&l.p[l.length-1];qk;q--)*(q+1)=*q;*k=e;l.length++;returntrue;}intdeletelist(list&l,inti,node&e)//删除表中第i个元素并用e返回其值{node*q;intj=i-1;if(i1||il.length)returnfalse;e=l.p[i-1];for(q=&l.p[i-1];jl.length-1;j++)*q=*(++q);l.length--;returntrue;}voidmergerlist(listla,listlb,list&lc)//归并两个按非递减排列的线性表{intla_len,lb_len,i=1,j=1,k=0;nodeai,bj;la_len=la.length;lb_len=lb.length;while(i=la_len&&j=lb_len){getelem(la,i,ai);getelem(lb,j,bj);if(ai.a=bj.a){insertlist(lc,++k,ai);i++;}else{insertlist(lc,++k,bj);j++;}}while(i=la_len){getelem(la,i,ai);insertlist(lc,++k,ai);i++;}while(j=lb_len){getelem(lb,j,bj);insertlist(lc,++k,bj);j++;}}intListAscendingOrder(list&l)//按结点中某一元素的比较升序排列线性表中的结点{nodee;inti,j;if(l.p==NULL||l.length==1)returnERROR;for(i=0;il.length-1;i++)for(j=i+1;jl.length;j++)if(l.p[i].num=l.p[j].num){e=l.p[i];l.p[i]=l.p[j];l.p[j]=e;}returnOK;}//省略降序排列voidMergerList(listla,listlb,list&lc)//将两线性表升序排列后再归并{node*q,*k,e1;inti=0,j=0,m=0,n;ListAscendingOrder(la);ListAscendingOrder(lb);printf(表a升序排列后为：\n);for(i=0;ila.length;i++)printf(%d,la.p[i].num);printf(\n);printf(表b升序排列后为：\n);for(i=0;ilb.length;i++)printf(%d,lb.p[i].num);printf(\n);i=0;while(ila.length&&jlb.length){if(la.p[i].num=lb.p[j].num){e1=la.p[i];i++;}else{e1=lb.p[j];j++;}if(e1.num!=lc.p[lc.length-1].num)InsertList(lc,++m,e1);}if(ila.length)while(ila.length){if(la.p[i].num!=lc.p[lc.length-1].num)InsertList(lc,++m,la.p[i]);i++;}if(jlb.length)while(jlb.length){if(lb.p[j].num!=lc.p[lc.length-1].num)InsertList(lc,++m,lb.p[j]);j++;}printf(按升序排列再归并两表为：\n);for(n=0;nlc.length;n++)printf(%d,lc.p[n].num);printf(\n);}----------------------链表-----------------------------typedefstruct{intnum;}node;typedefstructLIST{nodedata;structLIST*next;}list,*slist;intCreatList(slist&head)//此处应为只针对的引用{head=(list*)malloc(sizeof(list));if(!head)returnERROR;head-next=NULL;returnOK;}voidInvertedList(slist&head1,slist&head2){//构造新表逆置单链表函数list*p,*q;p=head1-next;q=p-next;if(p==NULL)printf(链表为空无法实现逆置操作\n);else{while(q!=NULL){p-next=head2-next;head2-next=p;p=q;q=q-next;}p-next=head2-next;head2-next=p;printf(逆置成功！?\n);}}voidInsertList(slist&head,node&e)//此处应为指针的引用{//而不应该是list*headlist*p,*q;p=(list*)malloc(sizeof(list));q=head;while(q-next!=NULL)q=q-next;p-next=q-next;q-next=p;p-data=e;}voidInvertedList(sqlist&head){//-------不构造新表逆置单链表函数---------//list*p,*q,*k;p=head-next;q=p-next;k=q-next;p-next=NULL;while(k!=NULL){q-next=p;p=q;q=k;k=k-next;}q-next=p;head-next=q;}//----交换链表中第i个和第j个结点，函数实现如下——//intSwapListNode(sqlist&head,inti,intj){intm,n,m1,n1,sum=0;list*p,*q,*k,*c,*d,*ba;ba=head-next;while(ba!=NULL){sum++;ba=ba-next;}if(i==j||isum||jsum||i1||j1){printf(所要交换的两个结点有误！\n);returnERROR;}if(ij){m=i;n=j;}else{m=j;n=i;}p=head;q=head;for(m1=1;m1=m;m1++)p=p-next;for(n1=1;n1=n;n1++)q=q-next;if(p-next==q){//如果结点相邻k=head;while(k-next!=p)k=k-next;//相邻两结点的交换p-next=q-next;q-next=p;k-next=q;}else{//如果结点不相邻k=head;c=head;while(k-next!=p)k=k-next;while(c-next!=q)c=c-next;d=p-next;//不相邻两结点之间的交换p-next=q-next;c-next=p;k-next=q;q-next=d;}returnOK;}//-----将链表中结点按结点中某一项大小升序排列，函数实现如下-----//intAscendingList(sqlist&head){intm,n,sum=0,i,j;list*p,*q,*k;k=head-next;while(k!=NULL){sum++;k=k-next;}for(i=1;isum;i++)for(j=i+1;j=sum;j++){p=head-next;m=1;while(m!=i){m++;p=p-next;}q=head-next;n=1;while(n!=j){n++;q=q-next;}if(p-data.expq-data.exp)//如果按exp降序排列，则应将改为；SwapListNode(head,i,j);}returnOK;}//-----将两链表合并为一个链表------//intAddList(sqlist&head1,sqlist&head2,sqlist&head3){//已将表head1和表head2按某一项升序排列过sqlistp,q;nodee;p=head1-next;q=head2-next;while