《数据结构——用C语言描述》+课后题答案

http://www.zydg.net/computer/book/read/data-structure/h971111102.html

习题解答(唐策善版)(其他版本在上面)

第一章 绪论（参考答案）

1.3 (1) O(n)

(2) (2) O(n)

(3) (3) O(n) (4) (4) O(n1/2)

(5)

(5) 执行程序段的过程中，x,y值变化如下：

循环次数 x y

0（初始） 91 100 1 92 100 2 93 100 ?? ?? ?? 9 100 100 10 101 100 11 91 99 12 92 100 ?? ?? ?? 20 101 99 21 91 98 ?? ?? ?? 30 101 98

31 91 97

到y=0时，要执行10*100次，可记为O（10*y）=O（1） 1.5 2100 , (2/3)n , log n 2n , n1/2 , n3/2 , (3/2)n , nlogn2 , 2, n! 第二章 线性表(参考答案)

在以下习题解答中，假定使用如下类型定义： （1）顺序存储结构： #define MAXSIZE 1024

typedef int ElemType;// 实际上，ElemType可以是任意类型 typedef struct

{ ElemType data[MAXSIZE];

int last; // last表示终端结点在向量中的位置 }sequenlist;

（2）链式存储结构（单链表） typedef struct node {ElemType data;

struct node *next； }linklist;

（3）链式存储结构（双链表） typedef struct node {ElemType data;

struct node *prior,*next；

, n n

}dlinklist; （4）静态链表 typedef struct {ElemType data; int next; }node;

node sa[MAXSIZE];

2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。

头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。 开始结点：即上面所讲第一个元素的结点。

2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。 2·3

void insert(ElemType A[],int elenum,ElemType x)

// 向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。 { int i=0,j;

while (i=i;j--) A[j+1]=A[j];// 向后移动元素 A[i]=x; // 插入元素 } // 算法结束

2·4

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 { int num=0; // 计数，最终应等于n int start=0; // 记录开始位置（下标） while (num

{ temp=A[start]; //暂存起点元素值，temp与向量中元素类型相同 empty=start; //保存空位置下标

next=(start-K+n) %n; // 计算下一右移元素的下标 while (next !=start)

{ A[empty]=A[next];// 右移

num++; // 右移元素数加1 empty=next;

next=(next-K+n) %n; // 计算新右移元素的下标 }

A[empty]=temp; // 把一轮右移中最后一个元素放到合适位置 num++;

start++; // 起点增1，若num

} // 算法结束 算法二

算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ ElemType temp;

for(i=0;i<(n-k)/2;i++) //左面n-k个元素逆置

{temp=A[i]; A[i]=A[n-k-1-i]; A[n-k-1-i]=temp; } for(i=1;i<=k;i++) //右面k个元素逆置

{temp=A[n-k-i]; A[n-k-i]=A[n-i]; A[n-i]=temp; } for(i=0;i

{temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; } } // 算法结束 2·5

void insert(linklist *L,ElemType x)

// 带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。 { linklist *p=L->next, *pre=L，*s;

// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱 s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出 s->data=x;

while (p && p->data<=x) {pre=p; p=p->next;} // 查找插入位置 pre->next=s; s->next=p; // 插入元素 } // 算法结束 2·6

void invert(linklist *L)

// 本算法将带头结点的单链表L逆置。 //算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。

{ linklist *p=L->next,*s;

// p为工作指针，指向当前元素，s为p的后继指针

L->next=null;//头结点摘下，指针域置空。算法中头指针L始终不变 while (p)

{s=p->next; // 保留后继结点的指针 p->next=L->next; // 逆置 L->next=p;

p=s; // 将p指向下个待逆置结点 }

} // 算法结束 2·7

(1) int length1(linklist *L)

// 本算法计算带头结点的单链表L的长度 { linklist *p=L->next; int i=0;

// p为工作指针，指向当前元素，i 表示链表的长度 while (p)

{ i++; p=p->next; } return(i); } // 算法结束

(2) int length1(node sa[MAXSIZE]) // 本算法计算静态链表s中元素的个数。 { int p=sa[0].next, i=0;

// p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1时链表结束 while (p！=-1)

{ i++; p=sa[p].next; }

return(i); } // 算法结束 2·8

void union_invert(linklist *A,*B,*C)

// A和B是两个带头结点的递增有序的单链表，本算法将两表合并成 // 一个带头结点的递减有序单链表C，利用原表空间。 { linklist *pa=A->next,*pb=B->next,*C=A,*r;

// pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置 //元素的后继指针, 使逆置元素的表避免断开。

//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。 C->next=null;//头结点摘下，指针域置空。算法中头指针C始终不变 while (pa && pb) // 两表均不空时作

if (pa->data<=pb->data) // 将A表中元素合并且逆置 { r=pa->next; // 保留后继结点的指针 pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

else // 将B表中元素合并且逆置 { r=pb->next; // 保留后继结点的指针 pb->next=C->next; // 逆置

C->next=pb;

pb=r; // 恢复待逆置结点的指针 }

// 以下while (pa)和while (pb)语句，只执行一个 while (pa) // 将A表中剩余元素逆置 { r=pa->next; // 保留后继结点的指针 pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

while (pb) // 将B表中剩余元素逆置 { r=pb->next; // 保留后继结点的指针 pb->next=C->next; // 逆置

C->next=pb;

pb=r; // 恢复待逆置结点的指针 }

free(B);//释放B表头结点 } // 算法结束

2·9

void deleteprior(linklist *L)

// 长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点 { linklist *p=s->next,*pre=s; // p为工作指针，指向当前元素， // pre为前驱指针，指向当前元素*p的前驱

while (p->next!=s) {pre=p; p=p->next;} // 查找*s的前驱 pre->next=s;

free(p); // 删除元素 } // 算法结束

2·10

void one_to_three(linklist *A,*B,*C)

// A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法//将A表分成

// 三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。

{ linklist *p=A->next,r;

// p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。 //算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。 B=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出 B->next=null; // 准备循环链表的头结点

C=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出 C->next=null; // 准备循环链表的头结点 while(p)

{ r=p->next; // 用以记住后继结点

if (p->data>=’a’&&p->data<=’z’||p->data>=’A’&& p->data<=’Z’) {p-> next=A->next; A->next=p;} // 将字母字符插入A表

else if (p->data>=’0’&&p->data<=’9’)

{p->next=B->next; B->next=p;} // 将数字字符插入B 表 else {p->next=C->next; C->next=p;}// 将其它符号插入C 表

p=r; // 恢复后继结点的指针 }//while

} // 算法结束 2·11

void locate(dlinklist *L)

// L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,

// 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。 { linklist *p=L->next,*q;

//p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。 while (p && p->data !=x) p=p->next; // 查找值为x的结点。 if (!p) return (“不存在值为x的结点”);

else { p->freq++; // 令元素值为x的结点的freq域加1 。 p->next->prir=p->prior; // 将p结点从链表上摘下。 p->prior->next=p->next;

q=p->prior; // 以下查找p结点的插入位置

while (q !=L && q->freqprior;

p->next=q->next; q->next->prior=p;// 将p结点插入 p->prior=q; q->next=p； }

} // 算法结束

第三章 栈和队列(参考答案)

// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构 // 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 1 1 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1

设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2) 3.2 证明：由jpk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由

以上两条，不可能存在i

3.3 void sympthy(linklist *head, stack *s) //判断长为n的字符串是否中心对称 { int i=1; linklist *p=head->next;

while (i<=n/2) // 前一半字符进栈 { push(s,p->data); p=p->next; }

if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点 while (p && p->data==pop(s)) p=p->next; if (p==null) printf(“链表中心对称”)； else printf(“链表不是中心对称”)； } // 算法结束 3.4

int match()

//从键盘读入算术表达式，本算法判断圆括号是否正确配对 （init s;//初始化栈s scanf(“%c”,&ch);

while (ch!=’#’) //’#’是表达式输入结束符号

switch (ch)

{ case ’(’: push(s,ch); break;

case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);} pop(s); }

if (!empty(s)) printf(“括号不配对”); else printf(“括号配对”); } // 算法结束

3.5

typedef struct // 两栈共享一向量空间 { ElemType v[m]; // 栈可用空间0—m-1 int top[2] // 栈顶指针 }twostack;

int push(twostack *s,int i, ElemType x)

// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素， // 本算法是入栈操作

{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满 else {switch (i)

{case 0: s->v[++(s->top)]=x; break; case 1: s->v[--(s->top)]=x; break;

default: printf(“栈编号输入错误”); return(0); }

return(1); // 入栈成功 }

} // 算法结束

ElemType pop(twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作 { ElemType x;

if (i!=0 && i!=1) return(0);// 栈编号错误 else {switch (i)

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top--];break;

case 1: if(s->top[1]==m) return(0);//栈空

else x=s->v[s->top++]; break;

default: printf(“栈编号输入错误”);return(0); }

return(x); // 退栈成功 }

} // 算法结束

ElemType top (twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作 { ElemType x; switch (i)

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top]; break;

case 1: if(s->top[1]==m) return(0);//栈空

else x=s->v[s->top]; break;

default: printf(“栈编号输入错误”);return(0); }

return(x); // 取栈顶元素成功 } // 算法结束 3．6

void Ackerman(int m,int n) // Ackerman 函数的递归算法 { if (m==0) return(n+1);

else if (m!=0 && n==0) return(Ackerman(m-1,1); else return(Ackerman(m-1,Ackerman(m,n-1)) } // 算法结束 3．7

(1) linklist *init(linklist *q)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空

{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出 q->next=q; return (q); } // 算法结束

(2) linklist *enqueue(linklist *q，ElemType x)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队 { s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出 s->next=q->next; // 将元素结点s入队列 q->next=s;

q=s; // 修改队尾指针 return (q); } // 算法结束

(3) linklist *delqueue(linklist *q)

//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法 { if (q==q->next) return (null); // 判断队列是否为空 else {linklist *s=q->next->next; // s指向出队元素

if (s==q) q=q->next; // 若队列中只一个元素，置空队列 else q->next->next=s->next;// 修改队头元素指针

free (s); // 释放出队结点 }

return (q);

} // 算法结束。算法并未返回出队元素 3.8

typedef struct

{ElemType data[m];// 循环队列占m个存储单元

int front,rear; // front和rear为队头元素和队尾元素的指针

// 约定front指向队头元素的前一位置，rear指向队尾元素

}sequeue;

int queuelength(sequeue *cq)

// cq为循环队列，本算法计算其长度

{ return (cq->rear - cq->front + m) % m; } // 算法结束 3.9

typedef struct

{ElemType sequ[m];// 循环队列占m个存储单元

int rear,quelen; // rear指向队尾元素,quelen为元素个数 }sequeue;

(1) int empty(sequeue *cq)

// cq为循环队列，本算法判断队列是否为空 { return (cq->quelen==0 ? 1: 0); } // 算法结束

(2) sequeue *enqueue(sequeue *cq，ElemType x) // cq是如上定义的循环队列，本算法将元素x入队 {if (cq->quelen==m) return(0); // 队满

else { cq->rear=(cq->rear+1) % m; // 计算插入元素位置

cq->sequ[cq->rear]=x; // 将元素x入队列

cq->quelen++; // 修改队列长度 }

return (cq); } // 算法结束

ElemType delqueue(sequeue *cq)

// cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素 {if (cq->quelen==0) return(0); // 队空

else { int front=(cq->rear - cq->quelen + 1+m) % m;// 出队元素位置 cq->quelen--; // 修改队列长度 return (cq->sequ[front]); // 返回队头元素 }

} // 算法结束

第四章 串 (参考答案)

在以下习题解答中，假定使用如下类型定义： #define MAXSIZE 1024 typedef struct

{ char data[MAXSIZE];

int curlen; // curlen表示终端结点在向量中的位置 }seqstring;

typedef struct node {char data;

struct node *next ； }linkstring;

4.2 int index(string s,t)

//s,t是字符串，本算法求子串t在主串s中的第一次出现，若s串中包含t串，返回其 //第一个字符在s中的位置，否则返回0 {m=length(s); n=length(t); i=1;

while(i<=m-n+1)

if(strcmp(substr(s,i,n),t)==0) break; else i++;

if(i<=m-n+1) return(i);//模式匹配成功 else return(0);//s串中无子串t }//算法index结束

4.3 设A=” ”, B=”mule”, C=”old”, D=”my” 则：

（a） （a） strcat（A,B）=”mule” （b） （b） strcat(B,A)=”mule”

（c） （c） strcat(strcat(D,C),B)=”myoldmule” （d） （d） substr(B,3,2)=”le” （e） （e） substr(C,1,0)=” ” （f） （f） strlen(A)=0 （g） （g） strlen(D)=2 （h） （h） index(B,D)=0 （i） （i） index(C,”d”)=3

（j） （j） insert(D,2,C)=”moldy” （k） （k） insert(B,1,A)=”mule” （l） （l） delete(B,2,2)=”me” （m） （m） delete(B,2,0)=”mule” （n） （n） replace(C,2,2,”k”)=”ok” 4.4 将S=“（xyz）*”转为T=“（x+z）*y”

S=concat(S, substr(S,3,1)) // ”(xyz)*y” S=replace(S,3,1,”+”) // ”(x+z)*y” 4.5

char search(linkstring *X, linkstring *Y)

// X和Y是用带头结点的结点大小为1的单链表表示的串，本算法查找X中 第一个不在Y中出现的字符。算法思想是先从X中取出一个字符，到Y中去查找，如找到，则在X中取下一字符，重复以上过程；若没找到，则该字符为所求

{ linkstring *p, *q,*pre; // p,q为工作指针，pre控制循环 p=X->next; q=Y->next; pre=p; while (p && q)

{ ch=p->data; // 取X中的字符 while (q && q->data!=ch) q=q->next; // 和Y中字符比较

if (!q) return(ch); // 找到Y中没有的字符

else { pre=p->next; // 上一字符在Y中存在，

p=pre; // 取X中下一字符。

q=Y->next; // 再从Y的第一个字符开始比较 } }

return(null); // X中字符在Y中均存在 }// 算法结束 4.6

int strcmp(seqstring *S, seqstring *T)

// S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1 {int i=0;

while (s->ch[i]!=’\\0’ && t->ch[i]!=’\\0’) if (s->ch[i]>t->ch[i]) return(1);

else if (s->ch[i]ch[i]) return(-1); else i++; // 比较下一字符

if (s->ch[i]!=’\\0’&& t->ch[i]==0) return(1);

else if (s->ch[i]==’\\0’&& t->ch[i]!=0) return(-1); else return(0); }// 算法结束 4.7

linkstring *invert(linkstring *S, linkstring *T)

// S和T是用带头结点的结点大小为1的单链表表示的串，S是主串，T是 // 模式串。本算法是先模式匹配，查找T在S中的第一次出现。如模式匹 // 配成功，则将S中的子串（T串）逆置。 {linkstring *pre,*sp, *tp;

pre=S; // pre是前驱指针，指向S中与T匹配时，T 中的前驱 sp=S->next; tp=T->next;//sp 和tp分别是S和T串上的工作指针 while (sp && tp)

if (sp->data==tp->data) // 相等时后移指针 {sp=sp->next; tp=tp->next;}

else // 失配时主串回溯到下一个字符，子串再以第一个字符开始 {pre=pre->next; sp=pre->next; tp=T->next;}

if (tp!=null) return (null); // 匹配失败，没有逆置 else // 以下是T串逆置

{tp=pre->next; // tp是逆置的工作指针，现在指向待逆置的第一个字符

pre->next=sp; // 将S中与T串匹配时的前驱指向匹配后的后继 while (tp!=sp) { r=tp->next;

tp->next=pre->next; pre->next=tp; tp=r } }

}// 算法结束

第五章 多维数组和广义表（参考答案） 5.1 A[2][3][2][3]

A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202

A0210 , A0211 , A0212

将第一维的0变为1后，可列出另外18个元素。以行序为主（即行优先）时，先改

变右边的下标，从右到左进行。

5.2 设各维上下号为c1?d1，c2?d2，c3?d3，每个元素占l个单元。

LOC(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l 推广到n维数组！！（下界和上界）为（ci，di），其中1<=i<=n.则：其数据元素的存储位置为：

LOC（aj1j2….jn）=LOC（ac1c2…cn）+[（d2-c2+1） ?（dn-cn+1）(j1-c1)+(d3-c3+1) ?（dn-cn+1） n

(j2-c2)+?+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=LOC(ac1c2c3)+ ∑αi(ji-ci) i=1

n

其中αi∏（dk-ck+1）（1<=i<=n）

k=i+1

若从c开始，c数组下标从0开始，各维长度为bi（1<=i<=n）则：

LOC（aj1j2…jn）=LOC(a00…0)+(b2* b3*?* bn*j1+ b3* ?* bn*+ j2?+ bn* jn-1+ jn)*l

n

=LOC(a00…0)+ ∑αiji 其中：αi=l，α

5.3 (1) k=2*i+j ( 0<=k<3n-2 ) (2) i=(k+1)/3 ( 0<=k<3n-2 ) j=k-2*i

5.4

void saddlepoint(int a[m][n]);

// a是m行n列的二维数组,本算法求所有马鞍点

// b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数 // c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数 {for(i=0;i

{min=a[i,0]; // 最小值初始化

b[0]=0; k=1; // b数组记最小值的列号，k记最小值的个数 for(j=1;j

if (a[i][j]

else if (a[i][j]==min) {b[k+1]=j; k++;} // 有相等的最小值 for (jj=0;jj

while (kk=a[i][kk]) kk++;

if(kk>=m)printf(“马鞍点 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]); } // END OF for jj

} // END OF for i

最坏时间复杂度为O(m*(n+n*m)). (最坏时所有元素相同，都是马鞍点)

解法2: 若矩阵中元素值互不相同,则用一维数组row记下各行最小值，再用一维数组col记下各列最大值， 相等者为马鞍点。

for (i=0;i

{row[i]=a[i][0]; // 最小值初始化

i-1

=bi*αi ，1

for (j=1;j

if (a[i][j]

}

for (j=0;j

{col[j]=a[0,j]; // 最大值初始化

for (i=1;i

if (a[i][j]>col[j]) col[j]=a[i][j]; // 重新确定最大值 }

for (i=0;i

if(row[i]==col[j])

printf(“马鞍点 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]);

时间复杂度O( (m*n)).

解法3: 设定两个数组： max[0..n-1] 记各列的最大值所在行号

min[0..m-1] 记各行的最小值所在列号

第j 列的最大值为A[max[j]][j],第i行的最小值是A[i][min[i]] void saddlepoint(int a[m][n]);

// a是m行n列的二维数组,本算法求所有马鞍点 { int max[]=0,min[]=0;for(i=0;i

for (j=0; j

{ if (A[i][j]>A[max[j]][j]) max[j]=i; // 重新确定第j列最大值的行号 if (A[i][j]

}

for (i=0;i

{j=min[i]; // a[i][j]是否是马鞍点

if( max[j]==i) printf(“马鞍点 A[%d][%d]=%d”,i,j,a[i][j]); } // END OF for jj }

时间复杂度为O(m*n+m).

5.5 （1）三元组表（行号 0—5，列号 0—5）

S=（（0，0，15），（0，3，22），（0，5，-15），（1，1，11），（1，2，3），（2，3，-6），（4，0，91），（5，2，28）） （2）

5.6算法分析：两矩阵A和B相加的结果是一矩阵C，其元素Cij有三种情况；（1）Cij=Aij（Bij =0）；（2）Cij=Bij（Aij =0）；（3）Cij=Aij+Bij 。在（3）种情况下，要看结果是否为0，C矩阵只有非零元素。

Void matrixaddition(crosslist *A,*B)

//稀疏矩阵A和B用十字链表存储结构，本算法将稀疏矩阵B加到矩阵A上 {ca=A->next;cb=B->next;

while(ca!=A&&cb!=B)

//设pa和pb为矩阵A和B想加时的工作指针 {pa=ca->right;pb=cb->right;}

if(pa==ca)ca=ca->next;//A表在该行无非0元素； else

if(pb==cb)cb=cb->next//B表在该行无非0元素； else if(pb->colcol)//B的非0元素插入A中； {j=pb->col;pt=chb[j];pre=pt// 取到表头指针； while(pt->down_colcol)

{pre=pt;pt=pt->down;}

pre->down=pt->down;//该结点从B表相应列摘下 i=pb->right;pt=chb[i];pre=pt;//取B表行表头指针 while(pt->right->rowrow {pre=pt;pt=pt->right;}

pre->right=pt->riht;//该结点从B表相应行链表中摘下。 Pbt=pb;pb=pb->right;//B表移至下一结点 //以下是将pbt插入A表的相应列链表中

j=pbt->col;pt=cha[j];pre=pt;

while(pt->down !=cha[j]&&pt->down->rowrow)

{pre=pt;pt=pt->down}

pre->down=pbt;pbt->down=pt;

//以下是将pbt插入A表相应行链表中

i=pbt->right;pt=cha[i];pre=pt;

while(pt->right !=cha[i]&&pt->right-colcol) {pre=pt;pt=pt->right;} pre->right=ptb;

ptb->right=pt;

}//end of “if (pb->colcol)

else if(pa->col=pb->col)//处理两表中行列相同的非0元素 {v=pa->data+pb->data; if(v !=0)

{pa->data+=pb->data;pa=pa->right;

将pb从行链表中删除；pb=pb->right; }

else{将pa,pb从链表中删除;然后 pa=pa->right; pb=pb->right; } 5.7 (1) head((p,h,w))=p

(2) tail((b,k,p,h))=(k,p,h) (3) head(((a,b),(c,d)))=(a,b) (4) tail(((a,b),(c,d)))=((c,d)) (5) head(tail(((a,b),(c,d)))=(c,d) (6) tail(head(((a,b),(c,d))))=(b)

5.8 (1) (2)

5.9(1)

第6章 树和二叉树（参考答案）

6.1

(1)根结点a

6.2

三个结点的树的形态： 三个结点的二叉树的形态：

（2） （3） （1） （1） （2） （4） （5）

6．3 设树的结点数是n，则

n=n0+n1+n2+??+nm+ (1) 设树的分支数为B，有

n=B+1

n=1n1+2n2+??+mnm+1 (2) 由（1）和（2）有：

n0=n2+2n3+??+(m-1)nm+1 6.4

(1) ki-1 (i为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1

(4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构

1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D # E F # G # # # # H

注：#为空结点 6.6

(1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7

(1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8

int height(bitree bt)

// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild);

br=height(bt->rchild);

return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }

}// 算法结束

6.9

void preorder(cbt[],int n,int i);

// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数

A B ^ C ^ D ^ E ^ F ^ ^ G ^ ^ H ^

// 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0)

{ while(i<=n)

{visit(cbt[i]); // 访问根结点

if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 }

if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束

//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示 void preorder(bt[],int n,int i);

// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]);

preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束

6.10

int equal(bitree T1,bitree T2);

// T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价

// T1和T2只有一棵为空，另一棵非空，则不等价

// T1和T2均非空，且根结点值相等，则比较其左、右子树

{if (T1==null && T2==null) return(1); // 同为空二叉树

else if (T1==null || T2==null) return(0); // 只有一棵为空

else if (T1->data!=T2->data) return(0);// 根结点值不等 else return(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild)) //判左右子树等价 }// 算法结束

6．11

void levelorder (bitree ht); {本算法按层次遍历二叉树ht} {if (ht!=null)

{initqueue(q); {处始化队列，队列元素为二叉树结点的指针} enqueue(q,ht); {根结点指针入队列}

while (!empty(q))

{ p=delqueue(q);

visit(p); // 访问结点

if (p->lchild!=null) enqueue (q,p->lchild); //若左子女非空，则左子女入队列

if (p->rchild!=null) enqueue (q,p->rchild)； //若右子女非空，则右子女入队列 }

}

} // 算法结束 6．12

void preorder (bitree *t); (前序非递归遍历)

{ bitree *s[n+1]; // s是指针数组，数组中元素为二叉树节点的指针 top=0;

while (t!=null || top!=0)

{ while (t!=null) { visit(*t); s[++top]=t; t=t->lchild } if (top!=0) { t=s[top--]; t=t->rchild;} }

} // 算法结束

void inorder (bitree *t); (中序非递归遍历) {bitree *s[n+1];

top=0;

while ((t!=null || top!=0)

{ while (t!=null) { s[++top]=t; t=t->lchild }

if (top!=0) { t=s[top--]; visit(*t); t=t->rchild; } } // 算法结束

void postorder (bitree *t); (后序非递归遍历) {typedef struct node

{ bitree *t; tag:0..1 } stack; stack s[n+1] ; top=0;

while (t || top)

{ while (t) { s[++top].t=t; s[top].tag=0; t=t->lchild; } while (top && s[top].tag==1) { printf(s[top--].t->data:3);} if (top) { s[top].tag=1; t=s[top].t->rchild ;} }

} // 算法结束

6.13

bitree *dissect(bitree **t,ElemType x)

// 二叉树t至多有一个结点的数据域为x，本算法拆去以x为根的子树 // 拆开后的第一棵树用t表示，成功拆开后返回第二棵二叉树

{bitree *p,*find;

if (*t!=null)

{ if ((*t)->data==x) // 根结点数据域为x {p=*t; *t=null; return(p);

}

else {find=(dissect(&(*t)->lchild),x); // 在左子树中查找并拆开 // 若在左子树中未找到，就到右子树中查找并拆开 if (!find) find=(dissect(&(*t)->rchild),x); return(find); } }

else return(null); // 空二叉树 } // 算法结束

6.14

int search(bitree t,ElemType x)

// 设二叉树t中，值为x的结点至多一个，本算法打印x的所有祖先 // 算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到 // 值为x的结点时，栈中元素都是x的祖先 { typedef struct { bitree p; int tag; }snode; snode s[]; int top=0;

while (t && t->data !=x || top)

{ while (t && t->data !=x) // 沿左分支向下

{ s[++top].p=t; s[top].tag=0; t=t->lchild; } if (t->data==x) //

{for (i=1;i<=top;++i) printf(“%c\\n”,s[i].p->data);// 输出，设元素为字符

return(1); } else

while (top>0 && s[top].tag==1) top--;//退出右子树已访问的结点

if (top>0) // 置访问标志1，访问右子树 {s[top].tag=1;t=s[top].p; t=t->rchild; } }

return(0); // 没有值为x的结点 } // 算法结束

6.15 中序序列BDCEAFHG

后序序列DECBHGFA

A B F

前序序列 ABCDEFGH 6.16 后序线索树：

E null

只有空指针处才能加线索。 线索链表：

6.17

bitree *search(bitree *p)

// 查找前序线索二叉树上给定结点p的前序后继

^ 1 G 1 1 H 1 1 0 0 1 E 1 0 F 1 0 B 1 0 A 0 H B C A D E H C G D E F 0 C 0

{ if (p->ltag==1) return(p->rchild)； // 左标记为1时，若p的右子树非空，p的右子树的根p->rchild为p的后继；若右子树为空，p->rchild指向后继

else return(p->lchild); // 左标记为0时，p的左子女p->lchild为p的后继 . } // 算法结束

6.18 bitree *search（b：tree *p）

//在后序线索二叉树中查找给定结点的后序前驱的算法

{ if(p->rtag==0) return(p->rchild); //p有右子女时，其右子女p->rchild是p的后序前驱 else return(p->lchild);

//p的左标记为0，左子女p->lchild是后序前驱, 否则，线索p->lchild指向p的后序前驱 } 6.19

前序序列：ABCDEFGHIJKLMPQRNO 后序序列：BDEFCAIJKHGQRPMNOL 6.21

F D P E J Q K R O N I B A G L C H M

6.22

7,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。

哈夫曼编码：a：0010

b：10 c：00000 d：0001 e：01 f：00001 g：11 h：0011

第七章图（参考答案）

7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；

（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通； （3）任一顶点I的度是第I行非0元素的个数。 7．2（1）任一顶点间均有通路，故是强连通； （2）简单路径 V4 V3 V1 V2; （3） 0 1 ∞ 1 ∞ 0 1 ∞ 1 ∞ 0 ∞ ∞ ∞ 1 0 邻接矩阵 V1 V2 V3 V4 邻接表

V4 | V3 |^ V1 | ^ V2 | ^ V3 |^

V1 V2 V3 V4 逆邻接表

7．3（1）邻接表 V1 V2 V3 V4 V5 V6 5 | 6 | 5 | 5 | 3 | 5 | 3 | 1 | ^ 4 | 3 | 1 | 4 | 1 | ^ 6 | 4 | 2 | 1 | ^ 5 | ^ 1 | ^ 4 | 6 | 2 | ^ V1 |^ V3 |^ V1 |^ V4 | ^ V2 | ^ （2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1

（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V2 7．4（1）① adjlisttp g; vtxptr i,j; //全程变量 ② void dfs(vtxptr x)

//从顶点x开始深度优先遍历图g。在遍历中若发现顶点j，则说明顶点i和j间有路径。 { visited[x]=1; //置访问标记 if (y= =j)

{ found=1;exit(0);}//有通路，退出

else { p=g[x].firstarc;//找x的第一邻接点 while (p!=null)

{ k=p->adjvex;

if （!visited[k]）dfs(k); p=p->nextarc;//下一邻接点 }

}

③ void connect_DFS (adjlisttp g)

//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i

//到顶点j的路径。设 1<=i ,j<=n,i<>j.

{ visited[1..n]=0;found=0;

scanf (&i,&j); dfs (i);

if (found) printf （” 顶点”,i,”和顶点 ”,j,”有路径 ”）；

else printf （” 顶点”,i,”和顶点 ”,j,”无路径 ”）； }// void connect_DFS (2)宽度优先遍历

全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。 void bfs(vtxptr x) //

{ initqueue(q);enqueue(q,x); while (!empty(q));

{ y=delqueue(q); if (y= =j)

{ found=1;exit(0);}//有通路，退出 else {p=g[x].firstarc;//第一邻接点 while (p!=null) {k=p->adjvex;

if (! Visted[k]) enqueue(q,k); p=p->nextarc }

}// if(y= =j)

}//while(!empty(q))

7．5。假定该有向图以邻接表存储，各顶点的邻接点按增序排列 DFS序列：V1,V3,V6,V7,V4,V2,V5,V8

BFS序列：V1,V3,V4,V6,V7,V2,V5,V8

DFS森林 BFS森林 V1 V3 V4 V6 V7

7．6简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。 Adjlisttp g ; visited[1..n]=0; Int found =0;//全程变量

Int dfs(btxptr x)

//从k顶点深度优先遍历图g，看是否存在k的简单回路 { visited[x]=1;

V2 V1 V2

V3 V4 V5 V5 V6

V8

V7

V8

p=g[x].firstarc;

while(p!=null) { w=p->adjvex; if(w= =k)

{ found=1;exit(0);}//有简单回路，退出 if (!visited[k] ) dfs(w ); p=p->nextarc; }//while(p!=null) }// dfs

7．7 （1）PRIM算法的最小生成树

2 a c 2 a a d a 1 c b 2 b 2 2 b 2 d a d b 2 e b 2 2 d 1 c e b 2 a 1 c f 1 h c d 2 2 e 2 b 2 2 1 e g 1 f 1 a d 1 1 1 a 1 1 1 h

（2）KRUSKAL算法的最小生成树

d c 1

1 c 1 e g 2 b 2 2 e g a d 1 1 1 a h

（权值相同的边选取无顺序） 7．8 所选顶点 初态 3 2 6 4 f h 1 1 1

已选定点的集合 {1} {1，3} {1，3，2} {1，3，2，6} {1，3，2，6，4} 尚未被选顶点的集合 DIST [2] [3] [4] [5] [6] {2，3，4，5，6} {2，4，5，6} {4，5，6} {4，5} {5} 20 15 ∞ ∞ ∞ 19 ∞ ∞ 25 ∞ 29 25 29 29 29 {1，3，2，6，4，5} {} 5 注：选定点4和5时无优先顺序，二者最短路径均为29

7．9

0 8 ∞ A0= 3 0 ∞ 5 2 0

0 8 ∞ A1= 3 0 ∞

5 2 0

0 8 ∞ A2= 3 0 ∞

5 2 ∞

0 8 ∞ A3= 3 0 ∞ 5 2 0 7．10 V1

1 2 0

path0 = 1 2 0

1 2 3

0:1->1

1:1->2

∞:1到3没有直接通路

path1同path0,加入顶点1后无变化

path2同path1

本题不好，终态和初态无变化 V3 V6 V4 V2 V6 V5 V6 V2 V3 V4 V3 V4 V6 V4 V3 V2 V6 V1 V6 V2 V5 共七种

V3 V4 V3 V4 V6 V1 V2 V3 V4 用TOPOSORT算法求得第七种，即V5,V6,V1,V2,V3,V4.

用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为0顶点用栈结构存储，初始时从顶点1到顶点N扫描，入度为0的顶点进栈，得V5在栈顶。 7．11

void toposort_dfs （graph g；vtptr v）

//从顶点v开始，利用深度优先遍历对图g进行拓扑排序。

//基本思想是利用栈s存放顶点，首先出栈的顶点是出度为0的顶点，是拓扑序列中最后一个顶//点。若出栈元素个数等于顶点数，则拓扑排序成功，输出的是逆拓扑排序序列。 { visited[1..n]=0;top=0;num=0;//初始化；top为栈顶指针，num记出栈元素数 s[++top]=v;//顶点入栈

while (top!=0)

{w=firstadj(g,v);//求顶点v的第一邻接点

while (w！=0) // w!=0的含义是w存在 { if ( !visited[w]) s[++top]=w;

w=nextadj(g,v,w);//求下一个邻接点

}

if (top!=0) {v=s[top--]; num++; printf(v);}//输出顶点 }

printf(“\\n”);

if (num

V6 a12=4 顶点 Ve Vl V1 0 0 V2 5 9 V3 6 6

V4 12 12 V5 15 16 V6 16 20 V7 17 17 V8 19 20 V9 22 22 V10 24 24 a4 6 6 0 a5 6 13 7 a6 12 13 1 a7 12 12 4 a8 15 16 0 a9 12 16 4 a10 15 16 1 a11 17 17 0 a12 16 20 4 a13 19 20 1 a14 22 22 0 关键路径 V1->V3->V4->V7->V9->V10 长 22 关键活动 a3,a4,a7,a11,a14

顶点 Ve Vl V1 0 0 V2 5 9 V3 6 6 V4 12 12 V5 15 16 V6 16 20 V7 17 17 V8 19 20 V9 22 22 V10 24 24 活动 e l l-e a1 0 0 0 a2 5 9 4 a3 0 0 0 a4 6 6 0 a5 6 13 7 a6 12 13 1 a7 12 12 4 a8 15 16 0 a9 12 16 4 a10 15 16 1 a11 17 17 0 a12 16 20 4 a13 19 20 1 a14 22 22 0 关键路径 V1->V3->V4->V7->V9->V10 长 22 关键活动 a3,a4,a7,a11,a14 第八章 排序（参考答案） 本章所用数据结构

#define N 待排序记录的个数 typedef struct { int key;

ElemType other; }rectype;

rectype r[n+1]; // r为结构体数组

8.2

稳定排序有：直接插入排序、起泡排序、归并排序、基数排序 不稳定排序有：希尔排序、直接选择排序、堆排序 希尔排序例：49，38， 49，90，70，25 直接选择排序例：2， 2，1 堆排序例：1，2，2

8.3

void StlinkedInsertSort(s , n);

// 对静态链表s[1..n]进行表插入排序， 并调整结果，使表物理上排序 { #define MAXINT 机器最大整数 typedef struct { int key; int next; }rec;

rec s[n+1]; // s为结构体数组

s[0].key=maxint; s[1].next=0; //头结点和第一个记录组成循环链表 i=2; //从第2个元素开始，依次插入有序链表中

while (i<=n)

{q=0; p=s[0].next; // p指向当前最小元素，q是p的前驱 while (p!=0 && s[p].key

s[i].next=p; s[q].next=i; // 将第个元素链入 i++；

} // while(i<=n) 静态链表的插入 // 以下是重排静态链表，使之物理有序 i=1; p=s[0].next; while (i<=n)

{WHILE (p

{ s[i]??s[p]; s[i].next=p;

p=q; i++; } }

}//算法结束 8.4

void TwoWayBubbleSort( rectype r[n+1]; int n)

// 对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡 { int i=1, exchange=1; // 设标记 while (exchange)

{ exchange=0; // 假定本趟无交换

for (j=n-i+1 j>=i+1;j--) // 向前起泡，一趟有一最小冒出

if (r[j]r[j-1]; exchange=1;} // 有交换 for (j= i+1;j>=n-I;j++) // 向后起泡，一趟有一最大沉底

if (r[j]>r[j+1]) {r[j]?>r[j+1]; exchange=1;} // 有交换

i++;

} // end of WHILE exchange }//算法结束

8.5

（1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成

相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。 （2）最好的初始排列：4，1，3，2，6，5，7

8.6

void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 { typedef struct

{ int low,high; }node node s[n+1]； int top;

int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n; while (top>0)

{ss=s[top].low; tt=s[top].high; top--; if (ss

{ k=quickpass(r,ss,tt);

if (k-ss>1) {top++; s[top].low=ss; s[top].high=k-1;} if (tt-k>1) {top++; s[top].low=k+1; s[top].high=tt;} }

} // 算法结束

int quickpass(rectype r[];int s,t) {i=s; j=t; rp=r[i]; x=r[i].key; while （i

{while (i

while (i=r[j].key) i++; if (i

} // 一次划分算法结束 8.7

void QuickSort(rectype r[n+1]; int n)

// 对r[1..n]进行快速排序的非递归算法 对8.6算法的改进 { typedef struct

{ int low,high; }node

node s[n+1]； int top;

int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n;

ss=s[top].low; tt=s[top].high; top--; flag=true; while (flag || top>0)

{k=quickpass(r,ss,tt);

if (k-ss>tt-k) // 一趟排序后分割成左右两部分 {if (k-ss>1) // 左部子序列长度大于右部，左部进栈 {top++; s[top].low=ss; s[top].high=k-1; } if (tt-k>1) ss=k+1; // 右部短的直接处理 else flag=false; // 右部处理完，需退栈 }

else if (tt-k>1) //右部子序列长度大于左部，右部进栈 {top=top+1; s[top].low=k+1; s[top].high=tt; } if (k-ss>1) tt=k-1 // 左部短的直接处理 else flag=false // 左部处理完，需退栈 }

if (!flag && top>0)

{ss=s[top].low; tt=s[top].high; top--; flag=true;} } // end of while (flag || top>0) } // 算法结束

int quickpass(rectype r[];int s,t) // 用“三者取中法”对8.6进行改进 { int i=s, j=t, mid=(s+t)/2; rectype tmp;

if (r[i].key>r[mid].key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp } if (r[mid].key>r[j].key) {tmp=r[j];r[j]=r[mid];

if (tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp } }

{tmp=r[i];r[i]=r[mid];r[mid]=tmp }

// 三者取中：最佳2次比较3次移动；最差3次比较10次移动 rp=r[i]; x=r[i].key; while （i

{while (i

while (i=r[j].key) i++; if (i

r[i]=rp; return (i);

} // 一次划分算法结束

8.8

viod searchjrec（rectype r[]，int j）

//在无序记录r[n]中，找到第j（0<=ji在0~i、1或i+1~n+1之间查 //找，直到/i=j为止。

{ int quichpass (rectype r[],int,int) // 函数声明 i=quichpass(r,0,n-1); // 查找枢轴位置 whilehile(i!=j)

if (j

8.9

viod rearrange (rectype r[],int n)

//本算法重排具有n个元素的数r，使取负值的关键字放到取非负值的关键字之前。 { int i=0,j=n-1; rp=r[0];

while(i

{while(i=0) j--;

if(i

while(i

if(i

}//while(i

void arrange(rectype r[n+1]; int n)

// 对r[1..n]进行整理，使关键字为负值的记录排在非负值的记录之前 [ int i=0, j=-1;rp=r[0]; while (i

{ while (i=0) j--;

if (i

if (i

r[i]=rp;// }//算法结束

//本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢 //记录比较，而是按正负区分，提高了效率 8.10

typedef struct node {ElemType data; struct node *next; }linklist;

void simpleselect(linklist *head) //head是单链表的头指针，本算法对其进行直接选择排序。设p指向无序区第一个记录（开始是链表的第一个记录），用q指向一趟排序中的最小记录，为简便起见，将p和q所指结

点的数据交换。

{p=head->next;

while (p->next!=null) // 剩最后一个元素时，排序结束 { q=p; // 设当前结点为最小

s=p->next; // s指向待比较结点 while (s!=null)

if (s->data>q->data) s=s->next;

else {q=s; s=s->next; }// 用指向新的最小

if (q!=p) {x=q->data; q->data=p->data; p->data=x; } p=p->next; // 链表指针后移，指向下一个最小值结点 }

}//算法结束

8.11

按极小化堆取调整（若已是极大化堆则维持不变） （1）

（2）

（3）

（4）

8.11

void heapadjust(K[]，n)

//待排序元素在向量K中，从K1到Kn已是堆，现将第n+1个元素加入，本算法这n+1个元素调整成堆。

{rp=K[n+1]; x=K[n+1].key; // 用rp暂存第n+1个元素，x为其关键字

int c=n+1, f=c/2;

// 设c表示第n+1个元素的下标，f是其双亲的下标，本算法将子女与双亲比较，若符合堆的定义，则排序结束；否则将双亲和子女交换。之后，双亲的下标为新的子女，再与新的双亲比较，直至根结点（无双亲） while (f>0)

if (K[f].key<=x) break; // 已符合堆的定义，排序结束 else {K[c]=k[f]; c=f; f=c/2; } // 仅将双亲移至子女

K[c]=rp;// 将暂存记录rp（原第n+1个记录）放入合适位置 }//算法结束

// 利用上述排序思想，从空堆开始，一个一个添加元素的建堆算法如下： void heapbuilder(rectype R[])

// 向量R的第1到第n个元素为待排序元素，本算法将这n个元素建成堆。 {for (i=0;i

void sort(rectype r[],int n)

// 对具有n个元素的数组进排序。算法思想是先对数组扫描一遍，形成若干最大有序子 //列，再两两归并，最后完成排序。各子序列的长度（上界和下界）存储在循环队列中，//队头指针指向队头元素的前一位置，队尾指针指向队尾元素。 #define m 100 //子队列长度

{ int q[m+1]; i=1; front=0; rear=0;

while (i<=n-1) // 该循环求出rear个子序列

{ if(r[i+1].key>= r[i].key) i++; q[++rear]=i; // 一个子序列上界 I++; //I指向下一子序列下界

}

if(q[rear]

//以下为两两归并，当最后只剩下一个有序子序列（即|rear-front=1|）时，合并结束。 while((front+1)%m!=rear)

{ newrear=rear;

while((front+1)%m!=rear) //从r合并到r1中合并 { low=q[front]+1; //取两个子序列界 mid=q[++front%m];

if(front+1%m!=rear) high=q[++front%m]; else high=mid; merge(r,r1,low,mid,high);

newrear=(newrear+1)%m;

q[newrear]=high; //新子序列上界

}

q[front]=0; rear=newrear; //下一轮归并初始化 while((front+1)%m!=rear) //从n拷入r中 { low= q[front]+1;

mid=q[++front%m];

if(front+1%m!=rear) high=q[++front%m] else high=mid; merge(r1,r,low,mid,high);

newrear=++rear%m; q[newrear]=high;

}

q[front]=0; rear=newrear; // 下一轮归并从第一个元素开始 }// 最外层的while((front+1)%m!=rear)

void merge(rectype a[], a1[],int l,m,h)

//设a数组中a[l…..m]和a1[m+1…..h]有序，本算法使l….h有序，并拷贝到a1中 { i=l;j=m+1;k=l-1;

while(i<=m&&j<=h)

if a[i].key<=a[j].key a1[++k]=a[i++] else a1[++k]=a[j++]

while(i<=m) a1[++k]=a[i++]; while(j<=h) a1[++k]=a[j++]; }

8.14 void CountSort(rectype r[]; int n); // 对r[0..n-1]进行计数排序

{ int c[n] = {0};

// c数组初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j

for (i=0;i

if (r[i]>r[j]) c[i]=c[i]+1

else c[j]=c[j]+1;

for (i=0;i

while (c[i]!=i) //若c[i] = i，则r[i] 正好是第i个元素;否则，需要调整 { k=c[i];

temp=r[k]; r[k]=r[i]; r[i]=temp; // r[k]和r[i]交换 c[i]=c[k]; // 将c[k]存入c[i], c[k]=k; // r[k]已是第k个记录 // while (c[i]!=i)

8.15

# define D 10 // 假设每个关键字长度为10 typedef struct

{ char key[D]; // 关键字用字符数组表示 anytype:otheritem; // 元素的其他信息

int next; // 指针域

}rcdnode;

rcdnode r[n]; // 为n个英文单词为关键字的记录排序

int f[27],e[27];

int distribute(int i; int p)

//静态链表r中的记录按key[i+1]，……..，key[D]有序，p指向链表中第一记录。本算法 //第I位关键字key[i]建立子表，同一子表中 的key[i]值相同。f[i]和e[i]分别指向各子表 //中第一个记录和最后一个记录。0<=j<=27，key[i]为空格时，j=0；而key[i]为字母时，j= //该字母的ASCII码-64。f[i]=0表示第j个子表为空 {for(j=0;j<=27;j++) f[j]=0; // 子表初始化为空表 while(p!=0) //p=0表示链表到尾

{if(r[p].key[i]= = ’ ’) j=0;

else j=r[p].key[i]-64; if(f[j]= =0) f[j]=p; else f[e[j]].next=p;

e[j]=p; //将p所指结点插入第j个子表 }p=r[p].next; // p指向下一个元素 } //for

int collet(int i)

// 本算法按key [i]自小到大将f[j]不等于0所指各子表链成一个链表，e[j]为相应子表的尾//指针，，函数返回链接后链表头指针。 {j=0;

while(f[j]= =0) j++; // 找第一个非空子表 p=f[j];t=e[j]; // p为链表头指针 while (j<=27)

{ j++;

while(j<=27&&f[j]= =0) j++; // 找下一个非空子表 if(f[j]!=0) { r[t].next=f[j]; t=e[j]} // 链接两个非空子表 }

r[t].next=0; // 置链表尾 return(p); }//collect

int radixwordsort( )

// n个英文单词为关键字的元素存放在静态链表的数据域中。本算法按基数排序思想对这些//英文字母进行排序。排序后按关键字自小到大升序相链，算法返回指向第一个记录的下标//值。

{ for(i=0;i

for(i=d;i>0;i--)

{p=distribute(i,p); p=collect(i); } return(p) }

8.16 见8.3

8.17

s=┌logkm┐//s为归并趟数，m为顺串个数，k为归并路数 因为m=100和s=3

所以k>=5，故至少取5路归并即可

第九章 查找（参考答案）

9.1 int seqsearch( rectype r[], keytype k)

// 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据 // 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r[0].key=k; i=n;

while (r[i].key>k) i--;

if (i>0 && r[i].key==k) return(i); else return(0)

} // 算法结束

查找过程的判定树是单支树。 查找成功的平均查找长度为

ASL=∑PICI =1/n*∑i = 1/2*(n+1)

查找不成功的平均查找长度为 ASL=1/(n+1)(∑i+(n+1))=(n+2)/2. 9.2

typedef struct lnode

{int freq; // 访问频率域 keytype key; // 关键字 ElemType other;

struct lnode *prior,*next; // 双向链表 }seqlist;

typedef struct snode

{int freq; // 访问频率域 keytype key; // 关键字 ElemType other; }snode;

void locate(seqlist L,keytype X)

// 在链表中查找给定值为X的结点，并保持访问频繁的结点在前 //调用本函数前，各结点的访问频率域（freq）值均为0。 {seqlist *p; // p是工作指针 p=L->next; // p指向第一元素

while (p!=null && p->key!=X) p=p->next; // 查找X结点 if (p==null) {printf(“no X”); return; } else {q=p->prior; // q是p的前驱

p->next->prior=p->prior; // 先将p结点从链表中摘下 q->next=p->next;

while (q!=L && q->freqprior; // 找p结点位置 q->next->prior=p; // 将p结点插入链表 p->next=q->next; p->prior=q; q->next=p;

} // 算法结束

void locate(snode L[],int n;keytype X)

// 在具有n个元素顺序存储的线性表L中查找给定值为X的结点，并保持 // 访问频繁的结点在前。调用本函数前，各结点的访问频率域值为0。 { int i=0, freq;

L[n].key=X; // 监视哨

while (L[i].key!=X) i++;

if (i==n) {printf(“no X”); return; }

else { freq=L[i].freq;

while ( L[i-1].freq

} // 算法结束 9.3

10 5 15 2 7 12 18 1 3 6 8 11 13 16 19 4 9 14 17 20

注：判定树中的编号为元素在有序表中的序号

9.4 int binsearch(rectype s[],int low,int high, keytype k) // 有序的顺序表s,其元素的低端和高端下标分别为low和 high. // 本算法递归地折半查找关键字为k的数据元素，若存在，则返回其在有序 // 顺序表中的位置，否则，返回0。 { if (low<=high)

{mid=(low+high)/2; if (s[mid].key

return binsearch(s,mid+1,high,k);

else if (s[mi].key>k

return(binsearch(s,low,mid-1,k)

else return(mid); }

else return(0); } // 算法结束

9.5 int level(bstnode *bst, keytype K)

// 在二叉排序树bst中，求关键字K所在结点的层次 {bstnode *p; // p为工作指针 int num=0; // 记层数 p=bst;

while (p && p->key!=K) // 二叉排序树不空 且关键字不等 if (p->keyrchild; } // 沿右子树 else { num++; p=p->lchild; } // 沿左子树 if (p->key==K) return (++num); // 查找成功 else return(0); // 查找失败 } // 算法结束 其递归算法如下：

int level(bstnode *bst, keytype K，int num)

// 在二叉排序树中，求关键字K所在结点的层次的递归算法，调用时num=0 {if (bst==null) return 0;

else if (bst->key==K) return ++num;

else if (bst->keyrchild,K,num++); else return(bst->lchild,K,num++); } // 算法结束

9.6 bstnode *ancestor(bstnode *bst)

// bst是非空二叉排序树根结点的指针。

// A和B是bst树上的两个不同结点，本算法求A和B的最近公共祖先。 // 设A和B的关键字分别为a和b，不失一般性，设a

{ bstnode *p=bst;

if (p->key==a) { printf(“A 是B的祖先。\\n”); return(p); }

else if (p->key==b) { printf(“B 是A的祖先。\\n”); return(p); }

else if (p-key>a && p->keykey>b) return(ancestor(p->lchild)); // 沿左子树 else return(ancestor(p->rchild)); // 沿右子树 } // 算法结束

9.7 int bstree(bstnode *bst, bstnode *pre)

// bst是二叉树根结点的指针,pre总指向当前访问结点的前驱，调用本函数 // 时为null。本算法判断bst是否是二叉排序树。设一全程变量flag,初始值 // 为1，调用本函数后，若仍为1，是二叉排序树，否则，不是二叉排序树。 {if (bst!=null)

{bstree(bst->lchild,pre);

if (pre==null) pre=bst;

else if (pre->key>bst->key)

{printf (“非二叉排序树\\n”);flag=0; return 0;} else pre=p;

bstree(bst->rchild,pre); } }

9.8（1）

DEC NOV

ASL=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12

JAN FEB MAR APR JUN MAY SEP AUG JUL OCT

本文来源：https://www.bwwdw.com/article/ehm3.html