anyview 数据结构习题集 第10章答案

注意：此处代码可能并非最优化结果，等待代码优化中。。。。 ◆1.16② 试写一算法，如果三个整数X，Y和Z 的值不是依次非递增的，则通过交换，令其为 非递增。

要求实现下列函数：

void Descend(int &x, int &y, int &z); /* 按从大到小顺序返回x，y和z的值 */

void Descend(int &x, int &y, int &z) /* 按从大到小顺序返回x，y和z的值 */ {

int temp;

if(x1.17③ 已知k阶裴波那契序列的定义为 f0=0, f1=0, …, fk-2=0, fk-1=1; fn=fn-1+fn-2+…+fn-k, n=k,k+1,…

试编写求k阶裴波那契序列的第m项值的函数算法， k和m均以值调用的形式在函数参数表中出现。 要求实现下列函数：

Status Fibonacci(int k, int m, int &f);

/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/ /* 否则（比如，参数k和m不合理）返回ERROR */

Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ //没想到m竟然是从0开始的∵ ∵ {

int i; long temp; int a[1000];

if(k<=1||m<0){return ERROR;} for(i=0;ifor(temp=1,i=k+1;i<=m;++i){

if(temp>MAXINT) return ERROR;

temp=temp-a[i-k-1]+a[i-1]; a[i]=temp; }

f=a[m];

return OK; }

1.18③ 假设有A、B、C、D、E五个高等院校进行田径对抗赛， 各院校的单项成绩均以存入计算机并构成一张表，表中每一 行的形式为

项目名称 性别 校名 成绩 得分

编写算法，处理上述表格，以统计各院校的男、女总分和团 体总分，并输出。 要求实现下列函数：

void Scores(ResultType *result, ScoreType *score);

/* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, */

/* 并以特殊记录 {“”, male, „ „, “”, 0 }（域scorce=0）*/ /* 表示结束 */

相关数据类型定义如下：

typedef enum {female,male} Sex; typedef struct{

char *sport; // 项目名称

Sex gender; // 性别（女：female；男：male）

char schoolname; // 校名为’A',’B',’C',’D'或’E’ char *result; // 成绩

int score; // 得分（7,5,4,3,2或1） } ResultType; typedef struct{

int malescore; // 男子总分 int femalescore; // 女子总分 int totalscore; // 男女团体总分 } ScoreType;

void Scores(ResultType *result, ScoreType *score)

/* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, */ /* 并以特殊记录 {\"\（域scorce=0）*/ /* 表示结束

*/ //感觉这道题题意有点模糊....

{

int i,j;

for(j=0;j<5;++j){ i=0;

score[j].malescore=0; score[j].femalescore=0; while(result[i].score!=0) {

if('A'+j==result[i].schoolname){ if(male==result[i].gender)

score[j].malescore+=result[i].score; if(female==result[i].gender)

score[j].femalescore+=result[i].score; }

score[j].totalscore=score[j].malescore+score[j].femalescore; ++i; } } }

◆1.19④ 试编写算法，计算i!×2^i的值并存入数组 a[0..ARRSIZE-1]的第i-1个分量中 (i=1,2,…,n)。 假设计算机中允许的整数最大值为MAXINT，则当n> ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT时，应 按出错处理。注意选择你认为较好的出错处理方法。 要求实现下列函数：

Status Series(int ARRSIZE, int a[]);

/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */

Status Series(int ARRSIZE, int a[])

/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ {

int i=1,temp=1; while(i<=ARRSIZE){

if(MAXINT/temp<2*i)return OVERFLOW; temp*=2; temp*=i; a[i-1]=temp;

++i; }

return OK; }

◆1.20④ 试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + … + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。注意选择你认为较好的输入和输出方法。 要求实现下列函数：

float Polynomial(int n, int a[], float x0); /* 求一元多项式的值P(x0)。 */

/* 数组a的元素a[i]为i次项的系数，i=0,1,…,n */

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ {

int i=1;

float temp=1; float total=a[0];

if(0==n){return total;} while(i<=n){ temp*=x;

total+=a[i]*temp; ++i;

} return total; }

数据结构习题集 第2章答案

◆2.11② 设顺序表L中的数据元素递增有序。 试写一算法，将x插入到L的适当位置上，并保 持该表的有序性。 要求实现下列函数：

void InsertOrderList(SqList &L, ElemType x) /* 在有序的顺序表 L 中保序插入数据元素 x */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList;

void InsertOrderList(SqList &L, ElemType x) // 在有序的顺序表 L 中保序插入数据元素 x {

ElemType *p,*q; p=L.elem;

while(*p//p为大于X的第一个元素指针 if(L.length==L.listsize){

L.elem=(ElemType *)realloc(L.elem,L.listsize+10); if(L.elem){

exit(OVERFLOW); }

L.listsize+=10; }

for(q=L.elem+L.length-1;q>=p;q--){ *(q+1)=*q; } *p=x;

++L.length; }

◆2.12③ 设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表， A‟和B‟分别为A和B中除去最大共同前缀后的子表（例如，

A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大 的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后 的子表分别为A‟=(x,z)和B‟=(y,x,x,z)）。若A‟=B‟=空表， 则A=B；若A‟=空表，而B‟≠ 空表，或者两者均不为空表， 且A‟的首元小于B‟的首元，则AB。试写一个比 较A和B大小的算法。（注意：在算法中，不要破坏原表A 和B，也不一定先求得A‟和B‟才进行比较）。 要求实现下列函数：

char Compare(SqList A, SqList B); /* 比较顺序表A和B, */

/* 返回‟<', 若A /* '=', 若A=B; */ /* '>„, 若A>B */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList;

char Compare(SqList A, SqList B) // 比较顺序表A和B, // 返回'<', 若A', 若A>B {

char a,b;

int la=1,lb=1;

while(la<=A.length&&lb<=B.length){

if(*(A.elem+la-1)>*(B.elem+lb-1)){return '>';}

else if(*(A.elem+la-1)<*(B.elem+lb-1)){return '<';} ++la; ++lb; }

if(A.length==B.length) return '='; //此处应先判断长度是否相等！！ if(la==A.length+1){return '<';} if(lb==B.length+1){return '>';} }

2.13② 试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。 实现下列函数：

LinkList Locate(LinkList L, ElemType x);

// If „x‟ in the linked list whose head node is pointed // by „L‟, then return pointer pointing node „x‟, // otherwise return „NULL‟ 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

LinkList Locate(LinkList &L, ElemType x)

// If 'x' in the linked list whose head node is pointed // by 'L', then return pointer ha pointing node 'x', // otherwise return 'NULL' {

LinkList p=L->next; while(p){ if(x==p->data){ return p; }

p=p->next; }

return NULL; }

2.14② 试写一算法在带头结点的单链表结构上实现线性表 操作Length(L)。 实现下列函数： int Length(LinkList L);

// Return the length of the linked list // whose head node is pointed by „L‟ 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

int Length(LinkList L)

// Return the length of the linked list // whose head node is pointed by 'L' {

int i=0;

LinkList p=L; while(p->next){ ++i;

p=p->next; }

return i; }

2.17② 试写一算法，在无头结点的动态单链表上实现 线性表操作INSERT(L,i,b)，并和在带头结点的动态单 链表上实现相同操作的算法进行比较。 实现下列函数：

void Insert(LinkList &L, int i, ElemType b); 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

//思路不是很清晰，很多细节问题，调试了很长时间

//主要考虑问题：1、i为0或负数时 2、i在链表长度内 3、i为链表长度+1时 4、代码精简

void Insert(LinkList &L, int i, ElemType b) {

int j,count;

LinkList p=L,q=L;

if(i<0){exit(OVERFLOW);}

for(count=0;p!=NULL;++count){ p=p->next; }

if(1==i){

p=(LinkList)malloc(sizeof(LNode)); p->data=b; p->next=L; L=p; }

else if (i>1&&i<=count+1){ for(p=L,j=1;j<=i-1&&p;++j){

q=p;//p为第j个元素的指针，q为p的j-1个指针 p=p->next; }

p=(LinkList)malloc(sizeof(LNode));

p->data=b;

p->next=q->next; q->next=p; } }

2.18② 同2.17题要求。试写一算法， 实现线性表操作DELETE(L,i)。 实现下列函数：

void Delete(LinkList &L, int i); 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

void Delete(LinkList &L, int i) {

int j;

int count=0; LinkList p=L,q; //1、求链表长度 while(p){

p=p->next; ++count; }

//2、查找第i-1号元素 //特殊位置首位、末尾 p=L;

if(1==i){

L=p->next; free(p);

} //i==0时没问题

else if(i>1&&i<=count) {

for(p=L,j=1;jnext; }

q=p->next;

p->next=q->next; free(q); }

}

2.20② 同2.19题条件，试写一高效的算法，删除表中所 有值相同的多余元素 (使得操作后的线性表中所有元素的 值均不相同) 同时释放被删结点空间，并分析你的算法的 时间复杂度。 实现下列函数： void Purge(LinkList &L); 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

void Purge(LinkList &L) {

ElemType last=L->next->data; LinkList q=L->next,p=L->next; while(p){

if(last==p->data&&p!=L->next){ q->next=p->next; free(p); p=q; }

else

{last=p->data;} q=p; p=p->next; } }

◆2.21③ 试写一算法，实现顺序表的就地逆置， 即利用原表的存储空间将线性表(a1,a2,…,an) 逆置为(an,an-1,…,a1)。 实现下列函数： void Inverse(SqList &L); 顺序表类型定义如下： typedef struct {

ElemType *elem; int length; int listsize; } SqList;

void Inverse(SqList &L) {

int i;

ElemType *p,temp; p=L.elem;

for(i=0;i*(L.elem+i)=*(L.elem+L.length-i-1); *(L.elem+L.length-i-1)=temp; } }

◆2.22③ 试写一算法，对单链表实现就地逆置。 实现下列函数：

void Inverse(LinkList &L);

/* 对带头结点的单链表L实现就地逆置 */ 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

void Inverse(LinkList &L)

/* 对带头结点的单链表L实现就地逆置 */ {

LinkList last,cur,q;

q=L->next; //保存首元素地址 last=L->next;//上一个指针 cur=L->next; //当前操作的指针 if(cur){

while(cur){//此处没注意，写成了！cur，大意失荆州啊！ cur=L->next;

L->next=cur->next;

cur->next=last; if(cur){last=cur;} }

L->next=last;

q->next=NULL; } }

2.23③ 设线性表A=(a1,…,am), B=(b1,…,bn)，试写 一个按下列规则合并A、B为线性表C的算法，即使得 C=(a1,b1,…,am,bm,bm+1,…,bn) 当m≤n时； 或者 C=(a1,b1,…,an,bn,an+1,…,am) 当m＞n时。

线性表A、B和C均以单链表作存储结构，且C表利用A表和 B表中的结点空间构成。注意：单链表的长度值m和n均未 显式存储。 实现下列函数：

void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依题意，合并带头结点的单链表ha和hb为hc */ 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依题意，合并带头结点的单链表ha和hb为hc */ {

LinkList cur_a,cur_b,cur_c; cur_a=ha->next; cur_b=hb->next;

cur_c=ha;//这里要注意给cur_c赋值，不然地址为空 while(cur_a&&cur_b){

cur_c->next=cur_a;//Lc的next指向a; cur_c=cur_c->next;//cur_c指向c->next cur_a=cur_a->next;//cur_a指向a->next cur_c->next=cur_b;//cur_c的next指向b cur_c=cur_c->next;//cur_c指向b

cur_b=cur_b->next;//cur_b指向b->next }

if(cur_a){

cur_c->next=cur_a; }

if(cur_b){

cur_c->next=cur_b; }

hc=ha;

}

◆2.24④ 假设有两个按元素值递增有序排列的线性表 A和B，均以单链表作存储结构，请编写算法将A表和B表 归并成一个按元素值递减有序（即非递增有序，允许表 中含有值相同的元素）排列的线性表C， 并要求利用原 表（即A表和B表）的结点空间构造C表。 实现下列函数：

void Union(LinkList &lc, LinkList la, LinkList lb); /* 依题意，利用la和lb原表的结点空间构造lc表 */ 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

void Union(LinkList &lc, LinkList &la, LinkList &lb) {

LinkList temp,last,q;

if(la->next->data<=lb->next->data){ q=la->next;last=la->next; }

else {

q=lb->next;last=lb->next; }

while(la->next&&lb->next){

if(la->next->data<=lb->next->data){ temp=la->next;

la->next=temp->next;

temp->next=last; last=temp; }

else{

temp=lb->next;

lb->next=temp->next;

temp->next=last; last=temp; } } //

while(la->next){ temp=la->next;

la->next=temp->next;

temp->next=last; last=temp; }

while(lb->next){ temp=lb->next;

lb->next=temp->next;

temp->next=last; last=temp; }

q->next=NULL; lc=la;

lc->next=temp; }

2.31② 假设某个单向循环链表的长度大于1，且表 中既无头结点也无头指针。已知s为指向链表中某个 结点的指针，试编写算法在链表中删除指针s所指结 点的前驱结点。 实现下列函数：

ElemType DeleteNode(LinkList s);

/* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ 单链表类型定义如下： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList;

ElemType DeleteNode(LinkList s)

/* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ {

ElemType e;

LinkList p,temp=s;

while(temp->next->next!=s){ temp=temp->next; }

e=temp->next->data; p=temp->next; temp->next=s; free(p);

return e; }

2.32② 已知有一个单向循环链表，其每个结点中 含三个域：prev、data和next，其中data为数据域， next为指向后继结点的指针域，prev也为指针域， 但它的值为空(NULL)，试编写算法将此单向循环链 表改为双向循环链表，即使prev成为指向前驱结点 的指针域。 实现下列函数：

void PerfectBiLink(BiLinkList &CL); 双向循环链表类型定义如下： typedef struct BiNode { ElemType data; int freq; // 2.38题用 struct BiNode *prev, *next;

} BiNode, *BiLinkList;

void PerfectBiLink(BiLinkList &CL) {

BiLinkList p; p=CL;

p->next->prev=p; p=p->next; while(p!=CL){

p->next->prev=p; p=p->next; } }

◆2.33③ 已知由一个线性链表表示的线性表中含有 三类字符的数据元素（如：字母字符、数字字符和其 它字符），试编写算法将该线性链表分割为三个循环 链表，其中每个循环链表表示的线性表中均只含一类 字符。 实现下列函数：

void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll); 单链表类型定义如下： typedef struct LNode{ ElemType data;

struct LNode *next; } LNode, *LinkList;

void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) {

LinkList p,cur_c,cur_d,cur_o; p=ll->next; cur_c=lc; cur_d=ld; cur_o=lo; while(p){

if(p->data>='A'&&p->data<='z'){ cur_c->next=p;

cur_c=cur_c->next; }

else if(p->data>='0'&&p->data<='9'){ cur_d->next=p;

cur_d=cur_d->next; }

else{

cur_o->next=p;

cur_o=cur_o->next; }

p=p->next; }

cur_c->next=lc; cur_d->next=ld; cur_o->next=lo; }

2.37④ 设以带头结点的双向循环链表表示的线性 表L=(a1,a2,…,an)。试写一时间复杂度为O(n)的 算法，将L改造为L=(a1,a3,…,an,…,a4,a2)。 实现下列函数：

void ReverseEven(BiLinkList &L); 双向循环链表类型定义如下： typedef struct BiNode { ElemType data; int freq; // 2.38题用 struct BiNode *prev, *next;

} BiNode, *BiLinkList;

void ReverseEven(BiLinkList &L) {

BiLinkList last,p,temp;

int count=0; //用count计结点个数 p=L->next; //p指向第一个元素 while(p!=L->prev){//求链表长度-1 ++count;

p=p->next; }

last=p;//获得最后一个元素的地址 if(count>=2){ p=p->prev;

while(p!=L->next){//当p指向的不是第一个元素时 if(0==count%2){//判断是否序号为偶数的结点 temp=p; p=p->prev;

temp->prev->next=temp->next; temp->next->prev=temp->prev; last->next=temp; temp->prev=last;

last=temp; }

else{//奇号结点则继续往前 p=p->prev; }

--count; }

last->next=L;//构建循环 L->prev=last;//构建循环 } }

◆2.39③ 试对稀疏多项式Pn(x)采用存储量同多项式项 数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为 给定值），并分析你的算法的时间复杂度。 实现下列函数：

float Evaluate(SqPoly pn, float x); /* pn.data[i].coef 存放ai， */ /* pn.data[i].exp存放ei (i=1,2,…,m) */

/* 本算法计算并返回多项式的值。不判别溢出。 */

/* 入口时要求0≤e1 多项式的顺序存储结构:

typedef struct { int coef; int exp; } PolyTerm; typedef struct { PolyTerm *data; int length; } SqPoly;

float Evaluate(SqPoly pn, float x)

/* pn.data[i].coef 存放ai， */ /* pn.data[i].exp存放ei (i=1,2,...,m) */ /* 本算法计算并返回多项式的值。不判别溢出。 */ /* 入口时要求0≤e1int i=0,j=1,cur;//没想到这题目的数据i是从零开始的。 float total=0,temp=1; while(ifor(cur=pn.data[i].exp;j<=cur;++j){ temp*=x; }

total+=temp*(pn.data[i].coef); ++i; } return total; }

◆2.41② 试以循环链表作稀疏多项式的存储结构， 编写求其导函数的算法，要求利用原多项式中的结 点空间存放其导函数（多项式），同时释放所有无 用（被删）结点。 实现下列函数：

void Difference(LinkedPoly &pa);

/* 稀疏多项式 pa 以循环链表作存储结构， */ /* 将此链表修改成它的导函数，并释放无用结点 */ 链式多项式的类型定义： typedef struct PolyNode { int coef; int exp;

struct PolyNode *next;

} PolyNode, *PolyLink; // 多项式元素（项）结点类型 typedef PolyLink LinkedPoly; // 链式多项式

void Difference(LinkedPoly &pa)

/* 稀疏多项式 pa 以循环链表作存储结构， */ /* 将此链表修改成它的导函数，并释放无用结点 */ {

LinkedPoly cur=pa->next,last=pa->next,tail=pa->next;

if(pa->next){//此处改为cur时遇到空表会出错，不知道为什么 if(0==last->exp){cur=cur->next;last->coef=0;} while(cur!=pa){

last->coef=cur->coef*(cur->exp); last->exp=cur->exp-1; tail=last;

last=last->next;

cur=cur->next; }

if(cur=last->next){free(last);tail->next=pa;} } }

数据结构习题集 第3章答案

◆3.17③ 试写一个算法，识别依次读入的一个以@ 为结束符的字符序列是否为形如‟序列1&序列2′模式 的字符序列。其中序列1和序列2中都不含字符‟&'， 且序列2是序列1的逆序列。例如，‟a+b&b+a‟是属该 模式的字符序列，而‟1+3&3-1′则不是。 实现下列函数:

Status match(char *str);

/* 若str是属该模式的字符序列，*/ /* 则返回TRUE，否则返回FALSE */ Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

Status match(char *str)

/* 若str是属该模式的字符序列，*/ /* 则返回TRUE，否则返回FALSE */ {

//文档没有说明字符串是以@结尾的

//也没有说栈的类型是SqStack，用Stack时编译出错 SqStack s; SElemType c; Status flag=1; InitStack(s); char *cur=str; while('&'!=*cur){ Push(s,*cur); ++cur; } //入栈 ++cur;

if(!GetTop(s,c)&&*cur!='@'){flag=0;}//判断栈空 while(*cur!='@' ){ Pop(s,c);

if(c!=*cur){flag=0;break;} ++cur;

}//依次出栈匹配

if(GetTop(s,c)){flag=0;}//再次判断是否非空

return flag; }

3.18② 试写一个判别表达式中开、闭括号是否配对出现的算法。 实现下列函数：

Status MatchCheck(SqList exp); /* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表

Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */ /* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ /* 注：本函数不使用栈 */ /*****************************/

// 此题top指针和cur指针要很仔细地运用，还有判错条件也要小心 {

ElemType *cur,*top,*base; base=exp.elem;//模拟栈底

top=cur=base+1;//模拟栈顶(top)和当前元素(cur) if(')'==*cur){ return FALSE;

} //判断第一个字符是否为右括号 if(0==exp.length){ return TRUE;

}//判断是否为空顺序表

while(cur<=base+exp.length-1){//依次遍历 if('('==*cur){//当元素为左括号时 if(top!=cur){ *top=*cur; *cur='0'; }

++top;

}//top始终指向第二个元素 ////////////////////////////

else if(')'==*cur){ if(top==base){ return FALSE; }

if('('==*(top-1)){ *(--top)='0'; *cur='0'; } }

//////////////////////////// ++cur; }

if('0'==*base){return TRUE;}//此处应为base，而不是top return FALSE; }

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号”(” 和 “)”，方括号”[\"和\"]“和花括号”{“和”}”，且这三种括号可按任意的 次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达 式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素 为字符的顺序表中)。 实现下列函数：

Status MatchCheck(SqList exp); /* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ 顺序表类型定义如下： typedef struct { ElemType *elem; int length; int listsize; } SqList; // 顺序表 Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */ {

ElemType *cur=exp.elem; SElemType temp; SqStack s; InitStack(s);

if(0==exp.length){return 1;}

while(cur<=exp.elem+exp.length-1){

if('['==*cur||'('==*cur||'{'==*cur){ Push(s,*cur); }

else{

GetTop(s,temp);

if(StackEmpty(s)){//粗心，栈空时返回的是1而不是0 return 0; }

else if(']'==*cur&&'['==temp){ Pop(s,temp); }

else if(')'==*cur&&'('==temp){ Pop(s,temp); }

else if('}'==*cur&&'{'==temp){ Pop(s,temp); } }

++cur; }

if(StackEmpty(s))return 1;//粗心，栈空时返回的是1而不是0 return 0; }

3.20③ 假设以二维数组g(1..m,1..n)表示一个图像 区域，g[i,j]表示该区域中点(i,j)所具颜色，其值 为从0到k的整数。编写算法置换点(i0,j0)所在区域 的颜色。约定和(i0,j0)同色的上、下、左、右的邻 接点为同色区域的点。 实现下列函数：

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0);

/* 在g[1..m][1..n]中，将元素g[i0][j0] */ /* 所在的同色区域的颜色置换为颜色c */ 表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1]; Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef int SElemType; // 栈Stack的元素类型 Status StackInit(Stack &s, int initsize); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0) /* 在g[1..m][1..n]中，将元素g[i0][j0] */ /* 所在的同色区域的颜色置换为颜色c */ /*

说明：di=1,2,3,4分别为东南西北四个方向，表示的是下一位置在当前位置的哪

个方向！

因为数组的下标的性质，只要知道di就能够退回到上一个位置， 而如果第一个元素四周都没有同色元素之后（栈空），结束程序 */ {

SqStack S; InitStack(S); int x,y,di; char color;

if(i0<=0||i0>m||j0<=0||j0>n){ exit(OVERFLOW); } x=i0; y=j0;

color=g[x][y]; do{

if(x>0&&y>0&&x<=m&&y<=n&&color==g[x][y]){ di=1;//设置方向为东 g[x][y]=c; Push(S,di);

y=y+1;//当前位置切换为东边的元素 }

else{

Pop(S,di);

switch(di){//当前位置非同色或不合法，设置当前位置为上一位置

（回退）

case 1:--y;break; case 2:--x;break; case 3:++y;break; case 4:++x;break; }

++di;

if(di<=4){//若di>4，相当于只回退

switch(di){//切换当前位置到下一位置 case 1:++y;break;//东临 case 2:++x;break;//南 case 3:--y;break;//西 case 4:--x;break;//北 }

Push(S,di); } }

}while(!StackEmpty(S)); }

◆3.21③ 假设表达式由单字母变量和双目四则运 算算符构成。试写一个算法，将一个通常书写形式 且书写正确的表达式转换为逆波兰式。 实现下列函数：

char *RPExpression(char *e); /* 返回表达式e的逆波兰式 */ Stack是一个已实现的栈。 可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s); SElemType Top(Stack s);

char *RPExpression(char *e) /* 返回表达式e的逆波兰式 */

//由于个人水平,折腾了很就才通过 //主要思路如下:

//1 建立优先级表,符号表,栈中元素对应符号

//2 依此读取字符,判断是运算符还是数字,如果数字直接入后缀表达式栈, //如果是运算符,则判断与栈顶元素优先级关系,进行响应操作 /*

容易犯错的地方 1 优先级关系不正确

2 当*p优先级低于运算符栈顶时,出栈,但忘了继续比较 3 忘了字符串长度应该为length+1,因为最后'\\0' 变量说明

OPTR 运算符栈 rpe 后缀表达式栈 opera 数组为运算符表 list 数组为优先级表

pre_optr 记录运算符栈元素的代表数字 */ {

int i=0,j=0,op1,op2,pre=2,count=0; char *p=e,*head,temp,s[100]; Stack OPTR,rpe; int pre_optr[10];

char opera[7]={'+','-','*','/','(',')','#'}; int list[7][7]={{1,1,-1,-1,-1,1,1} ,{1,1,-1,-1,-1,1,1} ,{1,1,1,1,-1,1,1} ,{1,1,1,1,-1,1,1}

,{-1,-1,-1,-1,-1,0,-2} ,{1,1,1,1,-2,1,1}

,{-1,-1,-1,-1,-1,-2,0}}; InitStack(OPTR); InitStack(rpe);

while(*p){ //计算出转换后表达式的长度 if('('!=*p&&')'!=*p){ ++count; } ++p; } p=e;

Push(OPTR,'#'); pre_optr[j]=6;

while(*p){//依此读入字符,进行相应处理 for(i=0;i<7;++i){

if(opera[i]==*p){

break; } }

op2=i;

if(7==op2){//判断是否为数字 Push(rpe,*p); }

else{

op1=pre_optr[j]; pre=list[op1][op2]; if(-2==pre){

return ERROR; }

else if(1==pre){//优先级大于*p if(')'!=*p){

while(1==list[op1][op2]){ Pop(OPTR,temp); --j;

Push(rpe,temp); op1=pre_optr[j]; }

pre_optr[++j]=op2;//记录栈顶符号 Push(OPTR,*p); }

else{//如果为右括号

while(Top(OPTR)!='('){ Pop(OPTR,temp); Push(rpe,temp); --j; }

Pop(OPTR,temp); --j; } }

else if(0==pre){//等于 Pop(OPTR,temp); }

else if(-1==pre){//小于 Push(OPTR,*p);

pre_optr[++j]=op2;//记录栈顶符号 } } ++p;

}//运行到串尾;

while(Top(OPTR)!='#'){ Pop(OPTR,temp); Push(rpe,temp);

}//符号栈中所有元素出栈----转换完成

while(!StackEmpty(rpe)){//栈元素逆转---- Pop(rpe,temp); Push(OPTR,temp); }

p=head=(char *)malloc(count+1);

while('#'!=Top(OPTR)){//将栈元素写入字符串 Pop(OPTR,temp); *p=temp; ++p; }

*p='\\0'; return head; }

3.24③ 试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n>=0

g(m,n) = g(m-1,2n)+n 当m>0,n>=0 并根据算法画出求g(5,2)时栈的变化过程。 实现下列函数：

int G(int m, int n)

/* if m<0 or n<0 then return -1. */ {

if(m<0||n<0){ return -1; }

if(0==m){

return 0; }

else {

return G(m-1,2*n)+n; //刚开始竟然很白痴地写成G(m-1,2n) - -||

} }

3.25④ 试写出求递归函数F(n)的递归算法， 并消除递归： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 实现下列函数：

int F(int n)

/* if n<0 then return -1. */ {

if(n<0){

return -1; }

if(0==n){ return 1; } else{

return n*F(n/2); } }

◆3.28② 假设以带头结点的循环链表表示队列，并且 只设一个指针指向队尾元素结点(注意不设头指针)， 试编写相应的队列初始化、入队列和出队列的算法。 实现下列函数：

Status InitCLQueue(CLQueue &rear);

Status EnCLQueue(CLQueue &rear, ElemType x); Status DeCLQueue(CLQueue &rear, ElemType &x); 带头结点循环链队列CLQueue的类型为以下LinkList类型： typedef struct LNode{ ElemType data; struct LNode *next; } LNode, *LinkList; typedef LinkList CLQueue;

Status InitCLQueue(CLQueue &rear) {

rear=(CLQueue)malloc(sizeof(LNode)); if(!rear){

return FALSE; }

rear->next=rear;

return TRUE; }

Status EnCLQueue(CLQueue &rear, ElemType x) {

CLQueue head,p; head=rear->next;

p=(CLQueue)malloc(sizeof(LNode)); if(!p){

return FALSE; }

p->data=x; p->next=head; rear->next=p; rear=p; return OK; }

Status DeCLQueue(CLQueue &rear, ElemType &x) {

CLQueue head,p; head=rear->next;

if(rear==rear->next){//这里粗心了，忘记考虑队列空的情况 return ERROR; }

p=head->next; x=p->data;

head->next=p->next; free(p); return OK; }

3.29③ 如果希望循环队列中的元素都能得到利用， 则需设置一个标志域tag，并以tag的值为0或1来区 分，尾指针和头指针值相同时的队列状态是”空”还 是”满”。试编写与此结构相应的入队列和出队列的 算法，并从时间和空间角度讨论设标志和不设标志 这两种方法的使用范围（比如，当循环队列容量较 小而队列中每个元素占的空间较多时，那一种方法 较好？）。 实现下列函数：

Status EnCQueue(CTagQueue &Q, QElemType x); Status DeCQueue(CTagQueue &Q, QElemType &x); 本题的循环队列CTagQueue的类型定义如下：

typedef char QElemType; typedef struct {

QElemType elem[MAXQSIZE]; int tag; int front; int rear; } CTagQueue;

Status EnCQueue(CTagQueue &Q, QElemType x) {

if(Q.tag){

return ERROR; }

Q.elem[Q.rear]=x;

if(Q.rear==MAXQSIZE-1){ Q.rear=0; } else{

++Q.rear; }

if(Q.rear==Q.front){ Q.tag=1; }

return OK; }

Status DeCQueue(CTagQueue &Q, QElemType &x) {

if(Q.front==Q.rear&&0==Q.tag){ return ERROR; } else{

x=Q.elem[Q.front];

if(Q.front!=MAXQSIZE-1){ ++Q.front; }

else{

Q.front=0; }

if(Q.front==Q.rear){ Q.tag=0; } }

return OK;

}

◆3.30② 假设将循环队列定义为：以域变量rear 和length分别指示循环队列中队尾元素的位置和内 含元素的个数。试给出此循环队列的队满条件，并 写出相应的入队列和出队列的算法（在出队列的算 法中要返回队头元素）。 实现下列函数：

Status EnCQueue(CLenQueue &Q, QElemType x); Status DeCQueue(CLenQueue &Q, QElemType &x); 本题的循环队列CLenQueue的类型定义如下： typedef char QElemType; typedef struct {

QElemType elem[MAXQSIZE]; int length; int rear; } CLenQueue;

Status EnCQueue(CLenQueue &Q, QElemType x) {

if(MAXQSIZE==Q.length){ return ERROR; }

if(MAXQSIZE-1!=Q.rear){ ++Q.rear;

Q.elem[Q.rear]=x; } else{

Q.rear=0;

Q.elem[Q.rear]=x; }

++Q.length; return OK; }

Status DeCQueue(CLenQueue &Q, QElemType &x) {

if(!Q.length){ return ERROR; }

if(Q.rear+1>=Q.length){

x=Q.elem[Q.rear+1-Q.length];

} else{

x=Q.elem[MAXQSIZE-Q.length+Q.rear+1]; }

--Q.length; return OK; }

◆3.31③ 假设称正读和反读都相同的字符序列为 “回文”，例如，‟abba‟和‟abcba‟是回文，‟abcde‟ 和‟ababab‟则不是回文。试写一个算法判别读入的 一个以‟@'为结束符的字符序列是否是”回文”。 实现下列函数：

Status Palindrome(char *word);

/* 利用栈和队列判定字符序列word是否是回文 */ 可使用栈Stack和队列Queue及其下列操作： Status InitStack(Stack &S); Status Push(Stack &S, ElemType x); Status Pop(Stack &S, ElemType &x); Status StackEmpty(Stack S); Status InitQueue(Queue &Q);

Status EnQueue(Queue &Q, ElemType x); Status DeQueue(Queue &Q, ElemType &x); Status QueueEmpty(Queue Q);

Status Palindrome(char *word)

/* 利用栈和队列判定字符序列word是否是回文 */ {

Stack S; char temp; InitStack(S);

char *p=word,*q=word; while(*p!='@'){ Push(S,*p); ++p; }

while(!StackEmpty(S)){ Pop(S,temp); if(temp!=*q){ break; } ++q;

}

if(StackEmpty(S)){ return TRUE; }

return FALSE; }

数据结构习题集 第4章答案

4.10③ 编写对串求逆的递推算法。 要求实现以下函数： void Reverse(StringType &s); /* Reverse s by iteration. */

StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。

void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s// 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。

StringType SubString(StringType s, int start, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 ” s = ” 的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!!

void Reverse(StringType &s)

/* Reverse s by iteration. */ {

StringType temp;

int i=StrLength(s);

InitStr(temp); //初始化空串

//经测试，StrAssign(temp,'')错误~~原因未知

while(i){

Concat(temp,SubString(s,i,1));

--i; //经测试，while(i--)就回出错~

}

StrAssign(s,temp); }

4.12③ 编写一个实现串的置换操作Replace(&S,T,V)的算法。 要求实现以下函数：

void Replace(StringType &S, StringType T, StringType V); /* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */

StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。

void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s// 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。

StringType SubString(StringType s, int start, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 ” s = ” 的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!!

void Replace(StringType &S, StringType T, StringType V)

/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */ {

int i=1,S_Len,T_Len,V_Len;

StringType r;

S_Len=StrLength(S);

T_Len=StrLength(T);

V_Len=StrLength(V);

InitStr(r);

while(i<=S_Len-T_Len+1){

StrAssign(r,SubString(S,i,T_Len));

if(0==StrCompare(r,T)){

InitStr(r);

Concat(r,SubString(S,1,i-1));

Concat(r,V);

Concat(r,SubString(S,i+T_Len,S_Len-T_Len-i+1));

StrAssign(S,r);

i+=V_Len;

S_Len=StrLength(S);//注意要更新S的长度！

}

else{

++i;

}

} }

4.13③ 编写算法，从串s中删除所有和串t相同的子串。 要求实现以下函数：

void DelSubString(StringType &scrStr, StringType subStr); /* Remove all substring matching „subStr‟ from „scrStr‟. */ StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。

void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s// 返回s中的元素个数，即该串的长度。 StringType Concat(StringType &s, StringType t); // 返回由s和t联接而成的新串。

StringType SubString(StringType s, int start, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时， // 返回s中第start个字符起长度为len的子串，否则返回空串。 // 注意,不要使用 ” s = ” 的形式为 StringType 类型的变量赋值 , // 而要使用 StrAssign 函数!!!

void DelSubString(StringType &scrStr, StringType subStr)

/* Remove all substring matching 'subStr' from 'scrStr'. */ {

int S_Len,T_Len,i=1;

StringType temp;

InitStr(temp);

S_Len=StrLength(scrStr);

T_Len=StrLength(subStr);

while(i<=S_Len-T_Len+1){

StrAssign(temp,SubString(scrStr,i,T_Len));

if(0==StrCompare(temp,subStr)){

InitStr(temp);

Concat(temp,SubString(scrStr,1,i-1));

Concat(temp,SubString(scrStr,T_Len+i,S_Len-T_Len-i+1));

StrAssign(scrStr,temp);

S_Len=StrLength(scrStr);

}

else{

++i; //注意这里删除substr后i不变！！

}

} }

4.17③ 编写算法，实现串的基本操作Replace(&S,T,V)。 要求采用教科书4.2.1节中所定义的定长顺序存储表示， 但不允许调用串的基本操作。 要求实现以下函数：

Status Replace(SString& s, SString t, SString v); /* 用串v替换串s中所有和串t匹配的子串。 */ /* 若有与t匹配的子串被替换，则返回TRUE；*/ /* 否则返回FALSE */

定长顺序串SString的类型定义：

typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string‟s length */

Status Replace(SString& s, SString t, SString v)

/* 用串v替换串s中所有和串t匹配的子串。 */

/* 若有与t匹配的子串被替换，则返回TRUE；*/

/* 否则返回FALSE */

/*这道题要注意的是顺序串元素的移动*/ {

//没通过，强烈怀疑测试数据有问题！！！

int flag=0,i,j,k,pos,step;

step=t[0]-v[0];//得到两个串的长度差

for(i=1;i<=s[0]-t[0]+1;++i){//依次匹配串

for(pos=i,j=1;j<=t[0];++pos,++j){

if(s[pos]!=t[j]){//此处若写成 pos++和j++,那么下面t[0]break;

} //如果不匹配，则退出循环

}

if(t[0]if(0==step){//判断是否需要串元素

for(j=1,k=i;j<=v[0];++k,++j){

s[k]=v[j];

}

}

else if(step<0){//串t长度小于模式串的情况

for(k=s[0];k>=i;--k){

s[k-step]=s[k];

}

for(j=1,k=i;j<=v[0];++k,++j){

s[k]=v[j];

}

}

else {//t的长度大于模式串的情况

for(k=pos;k<=s[0];++k){ //此处因为抄了前面的代码，所以没有注意到细节，导致

结果错误，已改正

s[k-step]=s[k];

}

for(j=1,k=i;j<=v[0];++k,++j){

s[k]=v[j];

}

}

flag=1;//记录成功置换

i+=v[0]-1;//i向后移动

s[0]+=-step;//step为正时s[0]减小，step为负时，s[0]增加，故

}

}

if(flag){

return TRUE;

}

return FALSE; }

4.20③ 编写算法，从串s中删除所有和串t相同的子串。 要求实现以下函数：

Status DelSub(SString &s, SString t); /* 从串s中删除所有和串t匹配的子串。 */ /* 若有与t匹配的子串被删除，则返回TRUE；*/ /* 否则返回FALSE */

定长顺序串SString的类型定义：

typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string‟s length */

Status DelSub(SString &s, SString t)

/* 从串s中删除所有和串t匹配的子串。 */

/* 若有与t匹配的子串被删除，则返回TRUE；*/

/* 否则返回FALSE */ {

int i,j,pos,flag=0;

for(i=1;i<=s[0]-t[0]+1;++i){

for(j=1,pos=i;j<=t[0];++j,++pos){ //模式串匹配

if(s[pos]!=t[j]){

break;

}

}

if(j>t[0]){//删除操作--移动串元素

for(;pos<=s[0];++pos){

s[pos-t[0]]=s[pos];

}

s[0]-=t[0];

flag=1; //标记成功删除

--i; //关键点！！容易出错的地方，删除了元素之后，

//i保持不变，因循环会加1，故

}

}

if(flag){

return TRUE;

}

else{

return FALSE;

} }

4.24③ 采用教科书4.2.2节中所定义的堆分配存储 表示。试写一算法，在串的堆存储结构上实现串基 本操作Concat(&T, s1, s2)。 要求实现以下函数：

Status Concat(HString &S, HString S1, HString S2) /* 用S返回由S1和S2联接而成的新串 */ 堆串HString的类型定义： typedef struct {

char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度 } HString;

//通过了忘记保存....

//并不难，不解释

4.30⑤ 假设以定长顺序存储结构表示串，试设计 一个算法，求串s中出现的第一个最长重复子串及 其位置，并分析你的算法的时间复杂度。

要求实现以下函数：

void CommonStr(SString s, SString &sub, int &loc); /* 求串s中出现的第一个最长重复子串sub及其位置loc */ 定长顺序串SString的类型定义：

typedef unsigned char SString[MAXSTRLEN+1]; /* s[0] is the string‟s length */

//目前对此题没有好的解法，占位

数据结构习题集 第5章答案

5.18⑤ 试设计一个算法，将数组A中的元素 A[0..n-1]循环右移k位，并要求只用一个元素 大小的附加存储，元素移动或交换次数为O(n)。 要求实现以下函数：

void Rotate(Array1D &a, int n, int k); 一维数组类型Array1D的定义： typedef ElemType Array1D[MAXLEN];

void Rotate(Array1D &a, int n, int k)

/* a[n] contains the elements, */ /* rotate them right circlely by k sits */ {

ElemType *p=a,temp; int i,j;

if(0!=k%n){//k不是n的倍数时 for(i=1;i<=k;++i){ temp=a[n-1];

for(j=n-2;j>=0;--j){

a[j+1]=a[j]; }

a[0]=temp; }

} }

5.21④ 假设稀疏矩阵A和B均以三元组表作为存储结构。 试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 要求实现以下函数：

Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);

/* 三元组表示的稀疏矩阵加法: C=A+B */ 稀疏矩阵的三元组顺序表类型TSMatrix的定义： #define MAXSIZE 20 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct {

Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix;

Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) /* 三元组表示的稀疏矩阵加法: C=A+B */ {

int ai,bi,ci,aj,bj,cj,apos,bpos,cpos; apos=bpos=cpos=1;

if(A.mu!=B.mu||A.nu!=B.nu){ return ERROR; }

C.mu=A.mu; C.nu=A.nu;

while(apos<=A.tu&&bpos<=B.tu){ ai=A.data[apos].i; bi=B.data[bpos].i; if(ai>bi){ ci=bi;

while(ci==B.data[bpos].i){ C.data[cpos].i=ci;

C.data[cpos].j=B.data[bpos].j; C.data[cpos].e=B.data[bpos].e; ++bpos; ++cpos; } }

else if(aiwhile(ci==A.data[apos].i){ C.data[cpos].i=ci;

C.data[cpos].j=A.data[apos].j; C.data[cpos].e=A.data[apos].e; ++apos; ++cpos; }

}

else{

ci=ai;

aj=A.data[apos].j; bj=B.data[bpos].j; if(aj>bj){

C.data[cpos].i=ci; C.data[cpos].j=bj;

C.data[cpos].e=B.data[bpos].e; ++cpos; ++bpos; }

else if(ajC.data[cpos].i=ci; C.data[cpos].j=aj;

C.data[cpos].e=A.data[apos].e; ++cpos; ++apos; } else{

cj=ai;

C.data[cpos].e=A.data[apos].e+B.data[bpos].e; if(0!=C.data[cpos].e){ C.data[cpos].i=ci; C.data[cpos].j=aj; ++cpos; }

++apos; ++bpos; } }

}//A稀疏矩阵完或者B稀疏矩阵完。

while(apos<=A.tu){//如果A矩阵中仍有元素 C.data[cpos].i=A.data[apos].i; C.data[cpos].j=A.data[apos].j; C.data[cpos].e=A.data[apos].e; ++cpos; ++apos; }

while(bpos<=B.tu){//如果B矩阵中仍有元素 C.data[cpos].i=B.data[bpos].i; C.data[cpos].j=B.data[bpos].j; C.data[cpos].e=B.data[bpos].e; ++cpos;

++bpos; }

C.tu=--cpos; return OK; }

5.23② 三元组表的一种变型是，从三元组表中去掉 行下标域得到二元组表，另设一个行起始向量，其每 个分量是二元组表的一个下标值，指示该行中第一个 非零元素在二元组表中的起始位置。试编写一个算法， 由矩阵元素的下标值i，j求矩阵元素。试讨论这种方 法和三元组表相比有什么优缺点。 要求实现以下函数：

Status GetElem(T2SMatrix M, int i, int j, ElemType &e); /* 求二元组矩阵的元素A[i][j]的值e */

稀疏矩阵的二元组顺序表＋行起始向量的类型T2SMatrix的定义： typedef struct{ int j; ElemType e; }TwoTuples; typedef struct{

TwoTuples data[MAXSIZE];

int cpot[MAXROW]; // 这个向量存储每一行在二元组中的起始位置 int mu,nu,tu;

} T2SMatrix; // 二元组矩阵类型

Status GetElem(T2SMatrix M, int i, int j, ElemType &e) /* 求二元组矩阵的元素A[i][j]的值e */ {

//竟然忘了这个是稀疏矩阵，e如果不是非零元素就是零元素 //还要判断i j的合法性！！ int cur,last; cur=M.cpot[i]; last=M.cpot[i+1]; e=0;

if(i>M.mu||j>M.nu||i<=0||j<=0){ return ERROR; }

while(curif(M.data[cur].j==j){ e=M.data[cur].e; return OK;

}

++cur; }

return OK; }

5.26③ 试编写一个以三元组形式输出用十字链表 表示的稀疏矩阵中非零元素及其下标的算法。 要求实现以下函数：

void OutCSM(CrossList M, void(*Out3)(int, int, int));

/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */ 稀疏矩阵的十字链表存储表示: typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值

OLNode *right,*down; // 该非零元所在行表和列表的后继链域 }OLNode, *OLink; typedef struct {

OLink *rhead,*chead; // 行和列链表头指针向量基址 int mu,nu,tu; // 稀疏矩阵的行数、列数和非零元个数 }CrossList;

void OutCSM(CrossList M, void(*Out3)(int, int, int)) /* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */ {

int i=1,row,col,e; OLink p,q;

for(i=1;i<=M.mu;++i){ p=M.rhead[i];

while(p){ Out3(p->i,p->j,p->e); p=p->right; } } }

5.30③ 试按表头、表尾的分析方法重写求广义表 的深度的递归算法。 要求实现以下函数： int GListDepth(GList ls);

/* Return the depth of list */ 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union { char atom; struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

int GListDepth(GList ls)

/* Return the depth of list */ {

int max=0,len=0; GList p; if(!ls){

return 1; }

if(ls->tag==ATOM){ return 0; }

for(max=0,p=ls;p;p=p->un.ptr.tp){ len=GListDepth(p->un.ptr.hp); if(maxreturn max+1; }

5.32④ 试编写判别两个广义表是否相等的递归算法。 要求实现以下函数：

Status Equal(GList A, GList B);

/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */ 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union {

char atom; struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

Status Equal(GList A, GList B)

/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */ {

//基本思想：分三种情况1、若果都为原子节点，则判断是否相等 2、如果都为广义表，则递归返回两个广义表比较结果 //3、其它情况直接返回FALSE;

if(ATOM==A->tag&&ATOM==B->tag){//情况1 if(A->un.atom==B->un.atom){ return TRUE; }

else{

return FALSE; } }

else if(LIST==A->tag&&LIST==B->tag){//情况2 return

Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp); }

else{//情况3

return FALSE; } }

5.33④ 试编写递归算法，输出广义表中所有原子项 及其所在层次。 要求实现以下函数：

void OutAtom(GList A, int layer, void(*Out2)(char, int));

/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */ 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union { char atom;

struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

void OutAtom(GList A, int layer, void(*Out2)(char, int))

/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */ {

if(A){

GList p; if(ATOM==A->tag){

Out2(A->un.atom,layer); }

else{

p=A->un.ptr.hp;

OutAtom(p,layer+1,Out2); p=A->un.ptr.tp;

OutAtom(p,layer,Out2);//表尾所在层是当前层，所以此处不能为layer+1 } } }

数据结构习题集 第6章答案

6.33③ 假定用两个一维数组L[1..n]和R[1..n]作为 有n个结点的二叉树的存储结构， L[i]和R[i]分别指 示结点i的左孩子和右孩子，0表示空。试写一个算法 判别结点u是否为结点v的子孙。 要求实现以下函数：

Status Dencendant(Array1D L,Array1D R,int n,int u,int v); /* If node „u‟ is the dencendant of node „v‟, */ /* then return „TRUE‟ else return „FALSE‟. */ /* L[i] is the left child of the i_th node, */ /* R[i] is the right child of the i_th node */ /* in the Binary Tree which has n nodes. */ 一维数组类型Array1D的定义： typedef int Array1D[MAXSIZE];

Status Dencendant(Array1D L,Array1D R,int n,int u,int v) /* If node 'u' is the dencendant of node 'v', */ /* then return 'TRUE' else return 'FALSE'. */ /* L[i] is the left child of the i_th node, */ /* R[i] is the right child of the i_th node */ /* in the Binary Tree which has n nodes. */ {

int flag=0; if(!v){

return FALSE; } else{

if(L[v]==u){ return TRUE; } else{

flag+=Dencendant(L,R,n,u,L[v]); }

if(R[v]==u){ return TRUE; } else{

flag+=Dencendant(L,R,n,u,R[v]); } if(flag){ return TRUE; }

return FALSE;

} }

6.34③ 假定用两个一维数组L[1..n]和R[1..n]作为 有n个结点的二叉树的存储结构， L[i]和R[i]分别指 示结点i的左孩子和右孩子，0表示空。试写一个算法, 先由L和R建立一维数组T[1..n]，使T中第i(i=1,2,…, n)个分量指示结点i的双亲，然后判别结点u是否为结 点v的子孙。 要求实现以下函数：

Status Dencend(Array1D L, Array1D R, int n, int u, int v, Array1D T);

/******************************************************************/ 一维数组类型Array1D的定义： typedef int Array1D[MAXSIZE];

Status Dencend(Array1D L, Array1D R, int n, int u, int v, Array1D T)

/******************************************************************/ {

int i,val;

for(i=1;i<=n;++i){//初始化数组T T[i]=0; }

for(i=1;i<=n;++i){//建立数组T T[L[i]]=i; T[R[i]]=i; } val=T[u]; while(val!=0){ if(val==v){ return TRUE; }

val=T[val]; }

return FALSE; }

6.36③ 若已知两棵二叉树B1和B2皆为空，或者皆 不空且B1的左、右子树和B2的左、右子树分别相似， 则称二叉树B1和B2相似。试编写算法，判别给定两 棵二叉树是否相似。 要求实现下列函数：

Status Similar(BiTree t1, BiTree t2); /* 判断两棵二叉树是否相似的递归算法 */ 二叉链表类型定义： typedef struct BiTNode { TElemType data;

BiTNode *lchild, *rchild; } BiTNode, *BiTree;

Status Similar(BiTree t1, BiTree t2) /* 判断两棵二叉树是否相似的递归算法 */ {

if(!t1&&!t2){//如果两棵树同为空 return TRUE; }

else if(t1&&t2){//如果两棵树同为非空,则返回各个子树的比较结果 return Similar(t1->lchild,t2->lchild)&&Similar(t1->rchild,t2->rchild); }

else{//当两棵树存在不相似的时候时，即一棵为空，一棵非空 return FALSE; } }

6.37③ 试直接利用栈的基本操作写出先序遍历的非递归 形式的算法(提示:不必按3.3.2节介绍的从递归到非递归 的方法而直接写出非递归算法)。 要求实现下列函数：

void PreOrder(BiTree bt, void (*visit)(TElemType)); /* 使用栈，非递归先序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild,*rchild; } BiTNode, *BiTree;

可用栈类型Stack的相关定义：

typedef BiTree SElemType; // 栈的元素类型 Status InitStack(Stack &S); Status StackEmpty(Stack S); Status Push(Stack &S, SElemType e); Status Pop(Stack &S, SElemType &e); Status GetTop(Stack S, SElemType &e);

void PreOrder(BiTree bt, void (*visit)(TElemType)) /* 使用栈，非递归先序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ {

//基本思路：根据工作栈原理，模拟递归的效果~ if(bt){//判断树空 SElemType p=bt; Stack S; InitStack(S);

while(!StackEmpty(S)||p){

while(p){//先序访问根节点、遍历左节点 visit(p->data); Push(S,p); p=p->lchild; }

if(!StackEmpty(S)){//遍历右节点，不小心写成while，错了几次~~ Pop(S,p); p=p->rchild; } } } }

6.38④ 同6.37题条件，写出后序遍历的非递归算法 (提示：为分辨后序遍历时两次进栈的不同返回点， 需在指针进栈时同时将一个标志进栈）。 要求实现下列函数：

void PostOrder(BiTree bt, void (*visit)(TElemType)); /* 使用栈，非递归后序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild,*rchild; } BiTNode, *BiTree;

可用栈类型Stack的相关定义： typedef struct {

BiTNode *ptr; // 二叉树结点的指针类型 int tag; // 0..1

} SElemType; // 栈的元素类型 Status InitStack(Stack &S); Status StackEmpty(Stack S); Status Push(Stack &S, SElemType e); Status Pop(Stack &S, SElemType &e); Status GetTop(Stack S, SElemType &e);

void PostOrder(BiTree bt, void (*visit)(TElemType)) /* 使用栈，非递归后序遍历二叉树bt， */ /* 对每个结点的元素域data调用函数visit */ { Stack S; InitStack(S); SElemType e; BiTree p=bt; int tag=0; if(bt){

e.tag=0;

while(!StackEmpty(S)||p==bt){ while(p&&!tag){ e.ptr=p;

if(p->lchild){//如果存在左子树 p=p->lchild; e.tag=0; }

else{//否则为右子树 p=p->rchild; e.tag=1; }

Push(S,e); }//while GetTop(S,e);

if(!StackEmpty(S)&&e.tag){ Pop(S,e); //叶子结点出栈 p=e.ptr;

visit(p->data);//输出该结点 } if(!StackEmpty(S)){

Pop(S,e); //得到上一层结点 p=e.ptr; if(e.tag){//右子树已经入栈 visit(p->data); p=NULL; }

else{//右子树没入过栈 if(p->rchild){ p=p->rchild; tag=0; e.tag=1; Push(S,e); }

else {//没有右子树 visit(p->data);

p=NULL; } } }

else{//栈空则，p为NULL p=NULL; } }//while

}//if }

6.41③ 编写递归算法，在二叉树中求位于先序序列中 第k个位置的结点的值。 要求实现下列函数：

TElemType PreOrder(BiTree bt, int k); /* bt is the root node of a binary linked list, */ /* Preorder travel it and find the node whose */ /* position number is k, and return its value. */ /* if can‟t found it, then return „#‟. */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

TElemType Get(BiTree bt,int &count,TElemType &e){ if(bt){

if(1==count){ e=bt->data; return 0; } else{

if(bt->lchild){ --count;

Get(bt->lchild,count,e); }

if(bt->rchild){ --count;

Get(bt->rchild,count,e); } } } }

//没想到可以自己添加函数~~方便很多 TElemType PreOrder(BiTree bt, int k) /* bt is the root node of a binary linked list, */ /* Preorder travel it and find the node whose */ /* position number is k, and return its value. */ /* if can't found it, then return '#'. */ {

TElemType e; e='#'; Get(bt,k,e);

return e; }

6.42③ 编写递归算法，计算二叉树中叶子结点的数目。 要求实现下列函数：

void Leaves(BiTree bt, int &x); /* Count the leaf node of the BiTree */ /* whose root node is bt to x. */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

void Leaves(BiTree bt, int &x)

/* Count the leaf node of the BiTree */ /* whose root node is bt to x. */ //题目并没有说x初始化为0，害人不浅啊~~ {

int l1,l2; if(bt){

if(!bt->lchild&&!bt->rchild){ ++x; } else{

Leaves(bt->lchild,x); Leaves(bt->rchild,x); } } }

6.43③ 编写递归算法，将二叉树中所有结点的 左、右子树相互交换。 要求实现下列函数： void Exchange(BiTree &bt);

/* Exchange the left and right leaves of */ /* bitree whose root node is bt */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree; void Exchange(BiTree &bt)

/* Exchange the left and right leaves of */ /* bitree whose root node is bt */ {

BiTree temp;

if(bt){

Exchange(bt->lchild); Exchange(bt->rchild); temp=bt->lchild; bt->lchild=bt->rchild; bt->rchild=temp; } }

6.44④ 编写递归算法：求二叉树中以元素值 为x的结点为根的子树的深度。 要求实现下列函数：

int Depthx(BiTree T, TElemType x);

/* 求二叉树中以值为x的结点为根的子树深度 */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree; int Depth(BiTree T){ int l1,l2; if(!T){ return 0; } else{

l1=Depth(T->lchild)+1; l2=Depth(T->rchild)+1; return (l1>l2)?l1:l2; } }

int Findx(BiTree T,BiTree &p,TElemType x){ if(T){

if(T->data==x){ p=T; return 0; } else{

Findx(T->lchild,p,x); Findx(T->rchild,p,x); } } }

int Depthx(BiTree T, TElemType x)

/* 求二叉树中以值为x的结点为根的子树深度 */ {

BiTree p=NULL; Findx(T,p,x); return Depth(p); }

6.46③ 编写复制一棵二叉树的非递归算法。 要求实现下列函数：

void CopyBiTree(BiTree T, BiTree &TT); /* 基于层次遍历的非递归复制二叉链表 */ 二叉链表类型定义：

typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

可用队列类型Queue的相关定义：

typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q);

Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q);

void CopyBiTree(BiTree T, BiTree &TT) /* 基于层次遍历的非递归复制二叉链表 */ //基本思想：用两个队列来同步操作！ {

BiTree p,p2; Queue Q,Q2; if(!T){ TT=NULL; return; }

TT=(BiTree)malloc(sizeof(BiTNode)); InitQueue(Q); InitQueue(Q2); EnQueue(Q,T); EnQueue(Q2,TT); while(!QueueEmpty(Q)){ DeQueue(Q,p); DeQueue(Q2,p2); p2->data=p->data; if(p->lchild){

EnQueue(Q,p->lchild);

p2->lchild=(BiTree)malloc(sizeof(BiTNode)); if(!p2->lchild){

exit(OVERFLOW); }

EnQueue(Q2,p2->lchild); } else{

p2->lchild=NULL; }

if(p->rchild){ EnQueue(Q,p->rchild);

p2->rchild=(BiTree)malloc(sizeof(BiTNode)); if(!p2->rchild){ exit(OVERFLOW); }

EnQueue(Q2,p2->rchild); } else{

p2->rchild=NULL; } } }

6.47④ 编写按层次顺序(同一层自左至右)遍历二叉树的算法。 要求实现下列函数：

void LevelOrder(BiTree bt, char *ss);

/* travel BiTree bt by level, Return result by ss. */ 二叉链表类型定义：

typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

可用队列类型Queue的相关定义：

typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q);

Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q);

提示：可将遍历元素的值（字符）依次置入ss，并最后以‟\\0′结尾。 也可以用下列字符串函数产生ss：

int sprintf(char *buffer, char *format [, argument, ...]); char *strcat(char *dest, char *src); void LevelOrder(BiTree bt, char *ss)

/* travel BiTree bt by level, Return result by ss. */ {

int i=0; Queue Q; BiTree p; InitQueue(Q); if(bt){

EnQueue(Q,bt); while(!QueueEmpty(Q)){ DeQueue(Q,p); ss[i++]=p->data; if(p->lchild){

EnQueue(Q,p->lchild); }

if(p->rchild){

EnQueue(Q,p->rchild); } }

ss[i]='\\0'; } }

6.49④ 编写算法判别给定二叉树是否为完全二叉树。 要求实现下列函数：

Status CompleteBiTree(BiTree bt);

/* judge if the binary tree whose root is bt */ /* is a complete tree. */ 二叉链表类型定义： typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

可用队列类型Queue的相关定义：

typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q);

Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q); Status CompleteBiTree(BiTree bt)

/* judge if the binary tree whose root is bt */ /* is a complete tree. */ /*基本思路

使用一个栈记录按层次遍历结果，当该结点非NULL时，左右子树入栈

因此，如果该树为完全二叉树时栈内容为XXXX＃＃(X表示非空)，##之间不可能有非空结点 如果非完全二叉树则内容可能为XXX＃XX＃＃也就是在NULL结点间仍有非空结点 只要非空结点与空结点分布情况即可求解

*/ {

int flag=0,top=0; BiTree stack[100]; Queue Q; BiTree p; InitQueue(Q); if(bt){

EnQueue(Q,bt); while(!QueueEmpty(Q)){ DeQueue(Q,p); if(p){

EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); stack[top++]=p->lchild;

stack[top++]=p->rchild; } }//while while(top){

if(flag){

if(stack[--top]==NULL){//在非NULL结点前仍有NULL结点 return FALSE; } } else{

if(stack[--top]!=NULL){//遇到第一个非NULL结点 flag=1; } } } }//if return TRUE; }

6.65④ 已知一棵二叉树的前序序列和中序序列分别 存于两个一维数组中，试编写算法建立该二叉树的二 叉链表。

要求实现以下函数：

void BuildBiTree(BiTree &bt, int ps, char *pre, int is, char *ino, int n);

/* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ 二叉链表类型定义： typedef char TElemType;

typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree;

void BuildBiTree(BiTree &bt, int ps, char *pre, int is, char *ino, int n) /* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ {

//估计此题比较繁琐，待更新 }

数据结构习题集 第7章答案

7.22③ 试基于图的深度优先搜索策略写一算法， 判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(i≠j)。 注意：算法中涉及 的图的基本操作必须在此存储结构上实现。 实现下列函数：

Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex „i‟ to */ /* vertex „j‟ in digraph „g‟. */

/* Array „visited[]„ has been initialed to „false‟.*/ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex;

struct ArcNode *nextarc; } ArcNode;

typedef struct VNode { VertexType data; ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;

//这道题思路很简单，就是简单的深度优先搜索，只不过不用搜索整个图

//只要遍历完含有顶点i的连通子图，然后判断顶点j是否被访问过就可以知道他们 //是否存在路径

int DFS(ALGraph g,int i){ ArcNode *w;

for(w = g.vertices[i].firstarc; w > 0 ;w = w->nextarc){ if(visited[w->adjvex] == FALSE){ visited[w->adjvex] = 1; DFS(g,w->adjvex); } }

return TRUE; }

Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/

{ int n; DFS(g,i);

if(visited[j] != FALSE){ return TRUE; } else{ return FALSE; } }

7.23③ 同7.22题要求。试基于图的广度优先搜索策略写一算法。 实现下列函数：

Status BfsReachable(ALGraph g, int i, int j);

/* Determine whether it exists path from vertex i to */ /* vertex j in digraph g with Breadth_First Search. */ /* Array „visited‟ has been initialed to „false‟. */ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex;

struct ArcNode *nextarc; } ArcNode;

typedef struct VNode { VertexType data; ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph;

Status InitQueue(Queue &q); Status EnQueue(Queue &q, int e); Status DeQueue(Queue &q, int &e); Status QueueEmpty(Queue q); Status GetFront(Queue q, int &e);

//此题与22题差别不大，同样是使用BFS遍历连通子图再判断 //注意判断结点不存在的情况

Status BfsReachable(ALGraph g, int i, int j)

/* Determine whether it exists path from vertex i to */ /* vertex j in digraph g with Breadth_First Search. */ /* Array 'visited' has been initialed to 'false'. */ {

ArcNode *p; Queue q; int e,n; InitQueue(q); if(!i&&!j){

//无奈之举，似乎测试数据有问题 //询问A-G有无路径时，i和j都为0 //这种判断方法不严谨，请勿模仿 return FALSE; }

EnQueue(q,i);

while(!QueueEmpty(q)){//BSF基本用法 DeQueue(q,e); visited[e] = TRUE; p = g.vertices[e].firstarc; while(p){

if(visited[p->adjvex] == FALSE){ EnQueue(q,p->adjvex); }

p = p->nextarc; } }

if(visited[j] != FALSE){//顶点j已被访问 return TRUE; } else{ return FALSE; } }

7.24③ 试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规定具 体的存储结构，而将图Graph看成是一种抽象的数据类型。 实现下列函数：

void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType)); /* Travel the digraph „dig‟ with Depth_First Search. */ 图以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int LocateVex(Graph g, VertexType v); VertexType GetVex(Graph g, int i); int FirstAdjVex(Graph g, int v); int NextAdjVex(Graph g, int v, int w); void visit(char v);

Status InitStack(SStack &s);

Status Push(SStack &s, SElemType x);

Status Pop(SStack &s, SElemType &x); Status StackEmpty(SStack s);

Status GetTop(SStack s, SElemType &e); 这道题测试数据似乎有问题

在内村里面H明明没有指向结点，而测试例子和答案竟然给出H – A，暂时无法解决！ 待更新中…

数据结构习题集 第10章答案

10.23② 试以L.r[k+1]作为监视哨改写教材10.2.1节 中给出的直接插入排序算法。其中，L.r[1..k]为待排 序记录且kvoid InsertSort(SqList &L); 顺序表的类型SqList定义如下： typedef struct { KeyType key; …

} RedType; typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

//-_-!!题目关于LT这个函数什么也没说 void InsertSort(SqList &L) { int i,j;

for(i=2;i<=L.length;++i){ if(LT(L.r[i],L.r[i-1])){ L.r[L.length+1]=L.r[i]; L.r[i]=L.r[i-1];

for(j=i-2;LT(L.r[L.length+1],L.r[j]);--j){ L.r[j+1]=L.r[j]; }

L.r[j+1]=L.r[L.length+1]; }

} }

10.26② 如下所述改写教科书1.4.3节中的起泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型变 量，指示每一趟排序中进行交换的最后一个记录的位置，并 以它作为下一趟起泡排序循环终止的控制值。 实现下列函数：

void BubbleSort(SqList &L);

/* 元素比较和交换必须调用以下比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：”<\" */ /* Status GT(RedType a, RedType b); 比较：\">” */ /* void Swap(RedType &a, RedType &b); 交换 */ 顺序表的类型SqList定义如下： typedef struct {

KeyType key; …

} RedType; typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

比较函数和交换函数:

Status LT(RedType a, RedType b); // 比较函数：”<\" Status GT(RedType a, RedType b); // 比较函数：\">” void Swap(RedType &a, RedType &b); // 交换函数 void BubbleSort(SqList &L)

/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\"<\" */ /* Status GT(RedType a, RedType b); 比较：\">\" */ /* void Swap(RedType &a, RedType &b); 交换 */ //不知道为什么，compare正常，但swap一直为0

//终于发现原因了，原来这里的Swap是大写的，如果小写的话，可以通过，但是最终swap为 0 {

int len=L.length,last=0; int i;

while(len>1){

for(i=1;iif(len!=last){ len=last; } else{ break; } } }

10.32⑤ 荷兰国旗问题：设有一个仅由红、白、兰 这三种颜色的条块组成的条块序列。请编写一个时 间复杂度为O(n)的算法，使得这些条块按红、白、 兰的顺序排好，即排成荷兰国旗图案。 实现下列函数： void HFlag(FlagList &f)

/* “荷兰国旗”的元素为red，white和blue，*/ /* 分别用字符‟0′,‟1′和‟2′表示 */

“荷兰国旗”的顺序表的类型FlagList定义如下： #define red ‟0′ #define white ‟1′ #define blue ‟2′ typedef char ColorType; typedef struct {

ColorType r[MAX_LENGTH+1]; int length; } FlagList;

//基本思路:设置low和high来记录两端的位置，按顺序比较i与0和2的关系 //如果为0则存放在线性表左端，如果为2则存放在线性表右端 void HFlag(FlagList &f) {

ColorType t;

int i=1,low=1,high=f.length;

while(f.r[low]=='0'){ //找到第一个不为0的位置 ++low; ++i; }

while(f.r[high]=='2'){ //找到倒数第一个不为2的结点 --high; }

while(i<=high){

if(f.r[i]=='0'&&low!=i){//如果为0,则与low交换,low!=i的判断极为关键 t=f.r[i]; f.r[i]=f.r[low]; f.r[low]=t; ++low; }

else if(f.r[i]=='2'){//如果为2，则与high交换 t=f.r[i]; f.r[i]=f.r[high]; f.r[high]=t; --high; } else{ ++i; }

while(f.r[low]=='0'){ //找到第一个不为0的位置 ++low; }

while(f.r[high]=='2'){ //找到倒数第一个不为2的结点 --high; }

} }

10.34③ 已知(k1,k2,…,kp)是堆，则可以写一个时 间复杂度为O(log(n))的算法将(k1,k2,…,kp,kp+1) 调整为堆。试编写”从p=1起，逐个插入建堆”的算法， 并讨论由此方法建堆的时间复杂度。 实现下列函数：

void CreateHeap(HeapType &h, char *s); 堆（顺序表）的类型HeapType定义如下： typedef char KeyType; typedef struct { KeyType key; … … } RedType; typedef struct {

RedType r[MAXSIZE+1]; int length;

} SqList, HeapType; /*

基本思路：

题目要求用逐个插入建堆的算法进行建堆，刚看题目莫名奇妙，

把书上调整大顶堆的算法抄上去，没想到这天杀的题目也提示下这个是小顶堆... 仔细看清题目之后，发现这道题目很简单。 假设当前堆已经是小顶堆，当有新的叶子时， 只需要跟它的双亲结点的key值比较， 如果比双亲的key小则交换 一直交换到跟结点。 */

//堆调整函数

void HeapAdjust(HeapType &h,int s,int m){ int j;

KeyType temp; for(j=m;j>s;j/=2){

if(h.r[j].keyvoid CreateHeap(HeapType &h, char *s) { int i; h.length=0;

while(s[i]!='\\0'){//逐个插入 ++h.length;

h.r[h.length].key=s[i];

HeapAdjust(h,1,h.length);//调整堆 ++i; } }

10.35③ 假设定义堆为满足如下性质的完全三叉树： (1) 空树为堆；

(2) 根结点的值不小于所有子树根的值，且所有子树 均为堆。

编写利用上述定义的堆进行排序的算法，并分析推导 算法的时间复杂度。 实现下列函数：

void HeapSort(HeapType &h);

堆（顺序表）的类型HeapType定义如下： typedef char KeyType; typedef struct { KeyType key; … … } RedType; typedef struct {

RedType r[MAXSIZE+1]; int length;

} SqList, HeapType; 比较函数和交换函数:

Status LT(RedType a, RedType b)

{ return a.key Status GT(RedType a, RedType b) { return a.key>b.key ? TRUE : FALSE; } void Swap(RedType &a, RedType &b) { RedType c; c=a; a=b; b=c; } /*

解题思路：

近视、眼花，以为题目说的跟书上的一样，又是直接抄上去，结果老是不对 研究后发现，题目说的是完全三叉树.... 随便列举一棵完全三叉树，仔细观察可以发现， 若双亲的序号为i，则左、中、右子树为3i-1,3i,3i+1; 模仿完全二叉树算法即可轻松得出算法

主要区别在于参数的变化还有三个子树的比较，特别是jvoid HeapAdjust(HeapType &h,int s,int m){ int j; RedType rc;

rc.key=h.r[s].key;

for(j=s*3-1;j<=m;j=3*j-1){ if(jif(jelse if(jif(!LT(rc,h.r[j])){ break; }

h.r[s]=h.r[j]; s=j; }

h.r[s]=rc; }

void HeapSort(HeapType &h)

/* 元素比较和交换必须调用以下比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\"<\" */ /* Status GT(RedType a, RedType b); 比较：\">\" */ /* void Swap(RedType &a, RedType &b); 交换 */ { int i; if(h.length){

for(i=(h.length+1)/3;i>0;--i){ HeapAdjust(h,i,h.length); }

for(i=h.length;i>1;--i){ Swap(h.r[1],h.r[i]); HeapAdjust(h,1,i-1); } } }

10.42④ 序列的”中值记录”指的是：如果将此序列排序 后，它是第n/2个记录。试写一个求中值记录的算法。 实现下列函数：

KeyType MidElement(SqList &L); 顺序表的类型SqList定义如下： typedef struct {

KeyType key; …

} RedType; typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

//此题神奇之处在于没有告诉你找不到时返回'#'; //效率很低的解法：用另外一个线性表储存本来的元素 //然后再用效率很低的选择排序 //最后之间比较

//估计存在一种边排序边计算的方法，有空再研究~ KeyType MidElement(SqList &L) { int i,j; SqList M; RedType t; if(!L.length){ return '#'; }

for(i=1;i<=L.length;++i){ M.r[i]=L.r[i]; }

for(i=1;i<=L.length;++i){ for(j=1;j<=L.length;++j){ if(L.r[i].key>L.r[j].key){ t=L.r[i]; L.r[i]=L.r[j]; L.r[j]=t; } } }

for(i=1;i<=L.length;++i){

if(M.r[i].key==L.r[L.length/2+1].key){ return M.r[i].key; } }

return '#'; }

10.43③ 已知记录序列a[1..n] 中的关键字各不相同，

可按如下所述实现计数排序：另设数组c[1..n]，对每 个记录a[i]， 统计序列中关键字比它小的记录个数存 于c[i]， 则c[i]=0的记录必为关键字最小的记录，然 后依c[i]值的大小对a中记录进行重新排列，试编写算 法实现上述排序方法。 实现下列函数：

void CountSort(SqList &L);

/* 采用顺序表存储结构，L.r存储序列a，L.length为n */ /* 在函数内自行定义计数数组c */ 顺序表的类型SqList定义如下： typedef struct { KeyType key; …

} RedType; typedef struct {

RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; } SqList;

void CountSort(SqList &L)

/* 采用顺序表存储结构，L.r存储序列a，L.length为n */ /* 在函数内自行定义计数数组c */ {

RedType temp[100]; int c[30]; int i,j;

for(i=1;i<=L.length;++i){//初始化计数数组 c[i]=0; temp[i]=L.r[i]; }

for(i=1;i<=L.length;++i){//统计数据 for(j=1;j<=L.length;++j){ if(L.r[j].keyfor(i=0,j=1;i<=L.length-1;++i){ for(j=1;j<=L.length;++j){

if(c[j]==i){//找到排序后第i+1个元素，位置为j L.r[i+1]=temp[j]; } } } }