数据结构第二章习题教程文件
- 格式：doc
- 大小：23.50 KB
- 文档页数：4
数据结构第二章习题 精品文档
收集于网络，如有侵权请联系管理员删除 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->data
{ p->next=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->data<=pb->data)
{ 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中
{ LB>next=pb->next; pb>next=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.elem[0]=-9999; //LC中第一个元素空间不用，为了操作方便，可设一个顺序表中不存在的值
while(i
{
if(LA.elem[i]<=LB.emem[j]) //如果LA中元素较小，将其插入到LC中
if(LA.elem[i]!=LC.elem[k-1]) //如果LA中当前元素与LC中K前一个元素不相等，则插入当前元素
{ LC.elem[k++]=LA.elem[i++]; LC.length++;}
else i++;
else //如果LB中元素较小，将其插入到LC中
if(LB.elem[j]!=LC.elem[k-1]) //如果LB中当前元素与LC中K前一个元素不相等，则插入当前元素
{ LC.elem[k++]=LB.elem[j++]; LC.length++;}
else j++;
}
while(i
if(LA.elem[i]!=LC.elem[k-1])
{ LC.elem[k++]=LA.elem[i++]; LC.length++;}
while(j
if(LB.elem[j]!=LC.elem[k-1])
{ LC.elem[k++]=LB.elem[j++]; LC.length++;}
}
