数据结构实用教程(第三版)课后答案

⑺ 将两个有序表合并成一个新的有序表并由变量返回。 解：void Merge(List& L1,List& L2,List& L3)

//将两个有序表合并成一个新的有序表并由变量返回 {

if(L1.size+L2.size>MaxSize){ cerr<<\ exit(1); }

int i=0,j=0,k=0;

while((i

else{ //将L2中的元素赋给L L.list[k]=L2.list[j]; j++;

file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 5／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt } k++; }

while(i

while(j

L.size=k; }

⑻ 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9, 2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。 解：void Delete5(List& L)

//从线性表中删除所有其值重复的元素,使其所有元素的值均不同 {

int i=0;

while(i

. . .

while(j

{ //删除重复值为L.list[i]的所有元素 if(L.list[j]==L.list[i]){

for(int k=j+1;k

4.对于结点类型为LNode的单链接表,编写出下列每个算法。

⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则 逆序链接后变为an,an-1,...a1。 解：void Contrary(LNode*&HL)

//将一个单多办实事有按逆序链接 {

LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点 HL=NULL;//HL仍为逆序后的表头指针，禄始值为空

file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 6／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt while(p!=NULL)

{ //把原单链表中的结点依次进行逆序链接 LNode*q=p; //q指向待处理的结点

p=p->next; //p指向下一个待逆序的结点 //将q结点插入到已陈序单链表的表头 q->next=HL; HL=q; } }

⑵ 删除单链表中的第i个结点。 解：void Delete1(LNode*&HL,int i) //删除单链表中的第i个结点 {

if(i<1||HL==NULL){

cerr<<\ exit(1); }

. . .

LNode*ap,*cp;

ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点 int j=1;

while(cp!=NULL) if(j==i)

break; //cp结点即为第i个结点 else{ //继续向后寻找 ap=cp;

cp=cp->next; j++; }

if(cp==NULL){

cerr<<\ exit(1); }

if(ap==NULL) HL=HL->next; else

ap->next=cp->next; delete cp; }

⑶ 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息

并停止运行。

解：ElemType MaxValue(LNode*HL)

//从单链表中查找出所有元素的最大值，该值由函数返回

file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 7／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt {

if(HL==NULL){

cerr<<\ exit(1); }

ElemType max=HL->data; LNode*p=HL->next; while(p!=NULL){

if(maxdata) max=p->data; p=p->next; }

return max;

. . .

}

⑷ 统计出单链表中结点的值等于给定值x的结点数。 解：int Count(LNode*HL,ElemType x)

//统计出单链表中结点的值等于给定值x的结点数 {

int n=0;

while(HL!=NULL){

if(HL->data==x) n++; HL=HL->next; }

return n; }

⑸ 根据一维数组a[n]建立一个单链表，使单链表中元素的次序与a[n]中元素的次序相同， 并使该算法的时间复杂度为O(n)。

解：void Create(LNode*&HL,ElemType a[],int n) //根据一维数组a[n]建立一个单链表 {

InitList(HL);

for(int i=n-1;i>=0;i--) InsertFront(HL,a[i]; }

⑹ 将一个单链表重新链接成有序单链表。 解：void OrderList(LNode*&HL)

//将一个单链表重新链接成有序单链表 {

LNode* p=HL;//p指向待处理的第一个结点，初始指向原表头结点 HL=NULL; //HL仍为待建立的有序表的表头指针，禄始值为空 while(p!=NULL)

{ //把原单链表中的结点依次进行有序链接

file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 8／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt LNode* q=p; //q指向待处理的结点

p=p->next; //p指向下一个待处理的结点 LNode* ap=NULL,*cp=HL;

//cp指向有序表中待比较的结点，ap指向其前驱结点 while(cp!=NULL)

{ //为插入q结点寻找插入位置 if(q->datadata)

. . .

break; else{

ap=cp;

cp=cp->next; }

} //将q结点插入到ap和cpxf hko pp uj q->next=cp; if(ap==NULL) HL=q; else

ap->next=q; } }

⑺ 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。 解：LNode*Mergel(LNode*&p1,LNode*&p2)

//将两个有序单链表合并成一个有序单链表 {

LNode a; //a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理

//结束后返回a结点的镄针域的值

LNode*p=&a; //p指向结果的有序单链表的表尾结点 p->next=NULL;//初始指向表头附加结点 while((p1!=NULL)&&(p2!=NULL)) {//处理两个表非空的情况 if(p1->datadata){ p->next=p1;p1=p1->next; } else{

p->next=p2;p2=p2->; }

p=p->next; }

if(p1!=NULL)p->next=p1; if(p2!=NULL)p->next=p2; p1=p2=NULL; return a.next; }

file:///D|/-------------------上架商品------...程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 9／21 页）[2010-3-16 22:06:59]

file:///D|/-------------------上架商品---------------/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt

. . .