数据结构第二章习题

2.5 已知顺序线性表A和B中各存放一个英语单词，字母均为小写。试编写一个判别哪一个单词在字典中排在前面的算法。int compare (Sqlist A,Sqlist B) /返回值为-1，A中的单词在前，返回值为1，B中的单词在前。j=0; while(jA.length & jB.length) if(A.elemjB.elemj) return 1; else j+; if(A.lenghtB.length) return 1; else return -1;2.6 顺序表的就地逆置void Invert_sq(Sqlist &A) for(i=0;iA.lenght/2;i+) K=A.elemi; A.elemi=A.elemA.length-i-1; A.elemA.length-i-1=k; 2.7 ha和hb两个指针，链表长度为m，n。将他们链接到一起。 void Cat_LinkList(LinkList ha,LinkList hb,LinkList &hc) If(mnext) p=p-next; /指针p指向ha的最后一个结点 P-next=hb; /将hb连接在ha后 hc=ha;Else P=hb; While(p-next) p=p-next; /指针p指向hb的最后一个结点 P-next=ha; /将ha连接在hb后 hc=hb; /时间复杂度：O(min(m,n)2.8void Union_Link(LinkList ha,LinkList hb,LinkList & hc) Pa=ha; pb=hb; I f(!pa) hc=hb; /若ha为空链表 else If (!pb) hc=ha; /若hb为空else while(pa-next & pb) hb=hb-next; /删除hb中第一个结点，头指针hb后移 pb-next=pa-next; pa-next=pb; pa=pa-next; pa=pa-next; pb=hb; If (!pa-next) pa-next=pb; /若链表hb长度大于ha，则将hb中剩下的结点直接连接在ha后hc=ha; /新链表头指针2.9一个线表表示的线性表中有3累字符的数据元素。将他分割为3个循环链表void Seg_LinkList(LinkList &L, LinkList &La,LinkList &Lb, LinkList &Lc)/ La=(ElemType*)malloc(sizeof(Lnode);/创建头结点 Lb=(ElemType*)malloc(sizeof(Lnode); Lc=(ElemType*)malloc(sizeof(Lnode);pa=La; pb=Lb; pc=Lc; pa-next=NULL; pb-next=NULL; pc-next =NULL; P=L-next; free(L); L=p; while(p) L=L-next; /从链表中撤离第一个结点，此时头指针后移if(p-data为数字) p-next=pa-next; pa-next=p; pa=pa-next; else if(p-data为字母) p-next=pb-next; pb-next=p; pb=pb-next; else p-next=pc-next; pc-next=p; pc=pc-next; p=L; /指针p指向L的第一个结点 /构建三个循环链表pa-next=La; pb-next=Lb; pc-next=Lc;2.10以待头结点的双向循环链表表示线性表l，时间复杂度nvoid Seg2_Link(LinkList &L)/为了保证算法的时间复杂度为O(n)，可从尾结点开始操作，每隔一个结点，将其前驱删除，并插入到最后。用指针p1从第n个结点开始往前移动，删除其前驱，用p2往后移动，在p2后面插入结点。/若结点为偶数个，删除的第一个结点应为第n-2个，若结点数为奇数个，删除的第一个结点为第n-1个，因此要先求结点数q=L-next; k=0; while(q-next!=L) /循环链表判断尾结点的条件 k+; q=q-next; if(k%2) p1=p2=L-prior; else p1=L-prior-prior; p2=L-prior; while(p1!=L) /p1从后往前移动，直到移动到头结点为止 q=p1-prior; q-prior-next=p1; p1-prior=q-prior; q-next=p2-next; p2-next=q;q-prior=p2; q-next-prior=q; p1=p1-prior; p2=p2-next; 2.11有序表中的元素递增排列。以单链表存储。高效算法。Mink maxkvoid delete_Link(LinkList &L,Elemtype mink,Elemtype maxk) p=L; /p指向头结点 while(p-next-datanext; q=p-next; while(q-datanext=q-next; free(q); q=p-next; 2.12 void union_Link(LinkList LA,LinkList LB,LinkList &LC) pa=LA-next; pb=LB-next; while(LA-next!=NULL &LB-next!=NULL) if(pa-datadata) LA-next=pa-next; pa-next=LC-next; LC-next=pa; else LB-next=pb-next; pb-next=LC-next; LC-next=pb; while(LA-next!=NULL) /如果LB中结点已经全部处理完，现在只需将LA中结点依次插入到LC中 LA-next=pa-next; pa-next=LC-next; LC-next=pa; while(LB-next!=NULL) /如果LA中结点已经全部处理完，现在只需将LB中结点依次插入到LC中 LBnext=pb-next; pbnext=LC-next; LC-next=pb; 2.13有两个元素递增排列的有序表a和b。构造c为交集元素。void Union_Sq(SqList LA, SqList LB, SqList &LC) i=0;j=0; k=1; LC.elem0=-9999; /LC中第一个元素空间不用，为了操作方便，可设一个顺序表中不存在的值while(iLA.length & jLB.length)if(LA.elemi=LB.ememj) /如果LA中元素较小，将其插入到LC中if(LA.elemi!=LC.elemk-1) /如果LA中当前元素与LC中K前一个元素不相等，则插入当前元素 LC.elemk+=LA.elemi+; LC.length+;else i+;else /如果LB中元素较小，将其插入到LC中if(LB.elemj!=LC.elemk-1) /如果LB中当前元素与LC中K前一个元素不相等，则插入当前元素 LC.elemk+=LB.elemj+; LC.length+;else j+;while(iLA.length) /