数据结构第二章习题教程文件

数据结构第二章题习

精品文档

2.5 已知顺序线性表A和B中各存放一个英语单词，字母均为小写。试编写一个判别哪一个单词在字典中排在前面的算法。

int compare (Sqlist A,Sqlist B)

{ //返回值为-1，A中的单词在前，返回值为1，B中的单词在前。 j=0; while(j

{ if(A.elem[j]B.elem[j]) return 1; else j++; } if(A.lenght>B.length) return 1; else return -1; }

2.6 顺序表的就地逆置 void Invert_sq(Sqlist &A) {

for(i=0;i

K=A.elem[i]; A.elem[i]=A.elem[A.length-i-1]; A.elem[A.length-i-1]=k; } }

2.7 ha和hb两个指针，链表长度为m，n。将他们链接到一起。 void Cat_LinkList(LinkList ha,LinkList hb,LinkList &hc) {

If(m

{ P=ha; while(p->next) 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.8

void 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，时间复杂度n void 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 maxk void delete_Link(LinkList &L,Elemtype mink,Elemtype maxk) { p=L; //p指向头结点

while(p->next->data<=mink) p=p->next; q=p->next; while(q->datanext=q->next; free(q); q=p->next; }}

收集于网络，如有侵权请联系管理员删除