《数据结构C语言版陈锐主编第2章 例题 代码资料》由会员分享，可在线阅读，更多相关《数据结构C语言版陈锐主编第2章 例题 代码资料（4页珍藏版）》请在金锄头文库上搜索。
1、【例2.1】 将顺序表(a1, a2, , an)重新排列为以a1为基准的两部分：a1前面的值均比a1小，a1后面的值都比a1大，如图2.5所示。#includetypedef int DataType;#includeSeqList.hvoid Division(SeqList *L) int i,j; DataType x,y; x=L-list0; /*将基准存放在x中*/ for(i=1;ilast;i+) if(L-listilisti;/*将要移动的元素存放到y中*/ for(j=i-1;j=0;j-) /*将前面的元素向后移动一个位置*/ L-listj+1=L-listj; L
2、-list0=y;/*将较小的元素存放在最前面*/ void main() int i; DataType a=30,40,23,60,8,56,9,43; SeqList L; InitList(&L); for(i=0;i8;i+) InsertList(&L,i+1,ai); for(i=0;i=L.last;i+) printf(%4d,L.listi); printf(n); Division(&L); for(i=0;i=L.last;i+) printf(%4d,L.listi); printf(n);【例2.2】 有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们
3、合并成一个顺序表C，要求C的元素也是按从小到大的升序排列。#includetypedef int DataType;#includeSeqList.hvoid Merge(SeqList A,SeqList B,SeqList *C) int i,j,k; i=0;j=0;k=0; while(i=A.last & j=B.last) if(A.listilistk+=A.listi+; else C-listk+=B.listj+; while(ilistk+= A.listi+; while (jlistk+=B.listj+; C-last=k-1;void DispList(SeqLi
4、st L) int i; for(i=0;i=L.last;i+) printf(%4d,L.listi); printf(n);void main() int i; DataType a=5,10,15,20,25; DataType b=4,9,19,23,29; SeqList A,B,C; InitList(&A); InitList(&B); for(i=0;i5;i+) InsertList(&A,i+1,ai); for(i=0;inext; pb=B-next; *C=A;/*将单链表A的头结点作为C的头结点*/ (*C)-next=NULL; pc=*C; /*依次将链表A和
5、B中较小的元素存入链表C中*/ while(pa&pb) if(pa-datadata)/*如果A中的元素小于或等于B中的元素，将A中的元素的结点作为C的结点*/ pc-next=pa; pc=pa; pa=pa-next; else/*如果A中的元素大于B中的元素，将B中的元素的结点作为C的结点*/ pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb;/*将剩余的结点插入C中*/ free(B);/*释放B的头结点*/【例2.4】 有两个循环单链表LA和LB，编写算法，将两个循环单链表合并为一个循环单链表。MergeList (LinkList L
6、A,LinkList LB)/*将链表LA和LB连接在一起形成一个循环链表*/ ListNode *p,*q; p=LA; while(p-next!=LA)/*指针p指向LA的最后一个结点*/ p=p-next; q=LB; while(q-next!=LB)/*指针q指向LB的最后一个结点*/ q=q-next; p-next=LB;/*将LA的尾端连接到LB的第一个结点*/ q-next=LA;/*将LB的尾端连接到LA的第一个结点*/ return LA;2.4.2 一元多项式的相加【算法描述】void AddPolyn(LinkList polya,LinkList polyb)/*
7、多项式相加*/ LinkList ha,pa,pb,temp; float sum; int a,b; pa=polya-next; pb=polyb-next; ha=polya; while(pa&pb) a=pa-data.expn; b=pb-data.expn; if(anext=pb; ha=pb; pb=pb-next; else if(a=b) /*如果A(x)的系数等于B(x)的系数，则将新生产的结点插入链表C*/ sum=pa-data.coef+pb-data.coef; if(sum!=0) pa-data.coef=sum; ha-next=pa; ha=pa; pa=pa-next; temp=pb; pb=pb-next; free(temp); else/*如果系数之和为0，则跳过该结点*/ temp=pa; pa=pa-next; free(temp); temp=pb; pb=pb-next; free(temp); else/*如果A(x)的系数大于B(x)的系数，则将A(x)的结点插入链表C*/ ha-next=pa; ha=pa; pa=pa-next; if(pa!=NULL) /*如果链表A不空，则将剩下的结点插入链表C*/ ha-next=pa; else/*如果链表B不空，则将剩下的结点插入链表C*/ ha-next=pb;
