严蔚敏《数据结构（c语言版）习题集》全答案

说明: 1. 本文是对严蔚敏《数据结构(c语言版)习题集》一书中所有算法设计题目的解决方案,主要作者为kaoyan.com计算机版版主一具.以下网友:siice,龙抬头,iamkent,zames,birdthinking等为答案的修订和完善工作提出了宝贵意见,在此表示感谢;

2. 本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义); 3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20, 10.40;

4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效果;

5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.请将你发现的错误或其它值得改进之处向作者报告: yi-ju@263.net 第一章 绪论 1.16

void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 {

scanf(\

if(xy; //<->为表示交换的双目运算符,以下同 if(yz;

if(xy; //冒泡排序 printf(\}//print_descending 1.17

Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f {

int tempd;

if(k<2||m<0) return ERROR; if(m

else if (m==k-1) f=1; else {

for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k至第m个元素的值 {

sum=0;

for(j=i-k;j

f=temp[m]; }

return OK; }//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 1.18

typedef struct{

char *sport;

enum{male,female} gender;

char schoolname; //校名为'A','B','C','D'或'E' char *result; int score; } resulttype; typedef struct{

int malescore; int femalescore; int totalscore; } scoretype;

void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中 {

scoretype score; i=0;

while(result[i].sport!=NULL) {

switch(result[i].schoolname) {

case 'A':

score[ 0 ].totalscore+=result[i].score;

if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score; break; case 'B':

score.totalscore+=result[i].score;

if(result[i].gender==0) score.malescore+=result[i].score; else score.femalescore+=result[i].score; break;

…… …… …… }

i++； }

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

printf(\

printf(\ printf(\ printf(\ }

}//summary 1.19

Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint {

last=1;

for(i=1;i<=ARRSIZE;i++) {

a[i-1]=last*2*i;

if((a[i-1]/last)!=(2*i)) reurn OVERFLOW; last=a[i-1]; return OK; }

}//algo119

分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 1.20

void polyvalue() {

float ad; float *p=a;

printf(\ scanf(\

printf(\ for(i=0;i<=n;i++) scanf(\ printf(\ scanf(\

p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) {

sum+=xp*(*p++); xp*=x; }

printf(\}//polyvalue

第二章 线性表

2.10

Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素 {

if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;

for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件 a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k; return OK; }//DeleteK

2.11

Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 {

if(va.length+1>va.listsize) return ERROR; va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK;

}//Insert_SqList 2.12

int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A

for(i=1;A.elem[i]||B.elem[i];i++)

if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i]; return 0; }//ListComp 2.13

LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针 {

for(p=l->next;p&&p->data!=x;p=p->next); return p; }//Locate 2.14

int Length(LinkList L)//求链表的长度 {

for(k=0,p=L;p->next;p=p->next,k++); return k; }//Length 2.15

void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc {

hc=ha;p=ha;

while(p->next) p=p->next; p->next=hb; }//ListConcat 2.16 见书后答案. 2.17

Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b {

p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) {

q.next=p;L=q; //插入在链表头部 } else {

while(--i>1) p=p->next;

q->next=p->next;p->next=q; //插入在第i个元素的位置 }

}//Insert 2.18

Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素 {

if(i==1) L=L->next; //删除第一个元素 else {

p=L;

while(--i>1) p=p->next;

p->next=p->next->next; //删除第i个元素 }

}//Delete 2.19

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 {

p=L;

while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 {

q=p->next;

while(q->datanext; //q是第一个不小于maxk的元素 p->next=q; }

}//Delete_Between 2.20

Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素 {

p=L->next;q=p->next; //p,q指向相邻两元素 while(p->next) {

if(p->data!=q->data) {

p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步 } else {

while(q->data==p->data) {

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

p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else }//while

}//Delete_Equal 2.21

void reverse(SqList &A)//顺序表的就地逆置 {

for(i=1,j=A.length;iA.elem[j]; }//reverse 2.22

void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2 {

p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头 }

q->next=p;s->next=q;L->next=s; }//LinkList_reverse

分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 2.23

void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 {

p=A->next;q=B->next;C=A; while(p&&q) {

s=p->next;p->next=q; //将B的元素插入 if(s) {

t=q->next;q->next=s; //如A非空,将A的元素插入 }

p=s;q=t; }//while }//merge1 2.24

void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间 {

pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素 while(pa||pb) {

if(pa->datadata||!pb) {

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表 } else {

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 }

pre=pc; }

C=A;A->next=pc; //构造新表头 }//reverse_merge

分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25

void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中 {

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j]) {

if(A.elem[i]B.elem[j]) j++; if(A.elem[i]==B.elem[j]) {

C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素, i++;j++; //就添加到C中 }

}//while

}//SqList_Intersect 2.26

void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题 {

p=A->next;q=B->next;

pc=(LNode*)malloc(sizeof(LNode)); while(p&&q) {

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next; else {

s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; pc->next=s;pc=s;

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

}//while C=pc;

}//LinkList_Intersect

2.27

void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中 {

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j]) {

if(A.elem[i]

else if(A.elem[i]>B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) {

A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素 i++;j++; //且C中没有,就添加到C中 }

}//while

while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True 2.28

void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题 {

p=A->next;q=B->next;pc=A; while(p&&q) {

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next; else if(p->data!=pc->data) {

pc=pc->next;

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

}//while

}//LinkList_Intersect_True 2.29

void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) {

i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置 while(i

if(B.elem[j]

else if(B.elem[j]>C.elem[k]) k++; else {

same=B.elem[j]; //找到了相同元素same while(B.elem[j]==same) j++;

while(C.elem[k]==same) k++; //j,k后移到新的元素 while(i

}//while

while(i

A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。 A.length=m;

}// SqList_Intersect_Delete

分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的 元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30

void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题 {

p=B->next;q=C->next;r=A-next; while(p&&q&&r) {

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next; else {

u=p->data; //确定待删除元素u

while(r->next->datanext; //确定最后一个小于u的元素指针r if(r->next->data==u) {

s=r->next;

while(s->data==u) {

t=s;s=s->next;free(t); //确定第一个大于u的元素指针s }//while

r->next=s; //删除r和s之间的元素 }//if

while(p->data=u) p=p->next; while(q->data=u) q=q->next; }//else }//while

}//LinkList_Intersect_Delete 2.31

Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱 {

p=s;

while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p p->next=s; return OK; }//Delete_Pre 2.32

Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域 {

for(p=L;!p->next->pre;p=p->next) p->next->pre=p; return OK; }//DuLNode_Pre 2.33

Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. {

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) {

if(isalphabet(s->data)) {

p->next=s;p=s; }

else if(isdigit(s->data)) {

q->next=s;q=s; } else {

r->next=s;r=s; }

}//while

p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_Divide 2.34

void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值 {

p=L.left;pre=NULL; while(p) {

printf(\ q=XorP(p->LRPtr,pre);

pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针

}

}//Print_XorLinkedList 2.35

Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x {

p=L.left;pre=NULL;

r=(XorNode*)malloc(sizeof(XorNode)); r->data=x;

if(i==1) //当插入点在最左边的情况 {

p->LRPtr=XorP(p.LRPtr,r); r->LRPtr=p; L.left=r; return OK; }

j=1;q=p->LRPtr; //当插入点在中间的情况 while(++j

q=XorP(p->LRPtr,pre); pre=p;p=q;

}//while //在p,q两结点之间插入

if(!q) return INFEASIBLE; //i不可以超过表长 p->LRPtr=XorP(XorP(p->LRPtr,q),r); q->LRPtr=XorP(XorP(q->LRPtr,p),r); r->LRPtr=XorP(p,q); //修改指针 return OK;

}//Insert_XorLinkedList 2.36

Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素 {

p=L.left;pre=NULL;

if(i==1) //删除最左结点的情况 {

q=p->LRPtr;

q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); return OK; }

j=1;q=p->LRPtr; while(++j

q=XorP(p->LRPtr,pre); pre=p;p=q;

}//while //找到待删结点q

if(!q) return INFEASIBLE; //i不可以超过表长 if(L.right==q) //q为最右结点的情况 {

p->LRPtr=XorP(p->LRPtr,q); L.right=p;free(q); return OK; }

r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点 p->LRPtr=XorP(XorP(p->LRPtr,q),r);

r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针 free(q); return OK;

}//Delete_XorLinkedList 2.37

void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点 {

p=L.next;

while(p->next!=L&&p->next->next!=L) {

p->next=p->next->next; p=p->next;

} //此时p指向最后一个奇数结点

if(p->next==L) p->next=L->pre->pre;

else p->next=l->pre;

p=p->next; //此时p指向最后一个偶数结点 while(p->pre->pre!=L) {

p->next=p->pre->pre; p=p->next; }

p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //调整pre链的结构,同2.32方法 }//OEReform

分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38

DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 {

p=L.next;

while(p.data!=x&&p!=L) p=p->next; if(p==L) return NULL; //没找到 p->freq++;q=p->pre;

while(q->freq<=p->freq) q=q->pre; //查找插入位置 if(q!=p->pre) {

p->pre->next=p->next;p->next->pre=p->pre; q->next->pre=p;p->next=q->next; q->next=p;p->pre=q; //调整位置 }

return p;

}//Locate_DuList 2.39

float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值 {

PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) {

while(exexp) xp*=x0; sum+=q->coef*xp; q++; }

return sum;

}//GetValue_SqPoly 2.40

void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3 {

PolyTerm *p,*q,*r;

Create_SqPoly(P3); //建立空多项式P3 p=P1.data;q=P2.data;r=P3.data; while(p->coef&&q->coef) {

if(p->expexp) {

r->coef=p->coef; r->exp=p->exp; p++;r++; }

else if(p->expexp) {

r->coef=-q->coef; r->exp=q->exp; q++;r++; } else {

if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中 {

r->coef=p->coef-q->coef;

r->exp=p->exp;r++; }//if p++;q++; }//else }//while

while(p->coef) //处理P1或P2的剩余项 {

r->coef=p->coef; r->exp=p->exp; p++;r++; }

while(q->coef) {

r->coef=-q->coef; r->exp=q->exp; q++;r++; }

}//Subtract_SqPoly 2.41

void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导 {

p=L->next;

if(!p->data.exp) {

L->next=p->next;p=p->next; //跳过常数项 }

while(p!=L) {

p->data.coef*=p->data.exp--;//对每一项求导 p=p->next; }

}//QiuDao_LinkedPoly 2.42

void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B {

p=L->next;

A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {

if(p->data.exp!=2*(p->data.exp/2)) {

pa->next=p;pa=p; } else {

pb->next=p;pb=p; }

p=p->next; }//while

pa->next=A;pb->next=B; }//Divide_LinkedPoly

第三章 栈与队列

3.15

typedef struct{

Elemtype *base[2]; Elemtype *top[2];

}BDStacktype; //双向栈类型

Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws {

tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0];

tws.top[1]=tws.base[1]; return OK; }//Init_Stack

Status push(BDStacktype &tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈 {

if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x;

else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push

Status pop(BDStacktype &tws,int i,Elemtype &x)//x出栈,i=0表示低端栈,i=1表示高端栈 {

if(i==0) {

if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; }

else if(i==1) {

if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; }

else return ERROR; return OK; }//pop 3.16

void Train_arrange(char *train)//这里用字符串train表示火车,'H'表示硬席,'S'表示软席 {

p=train;q=train; InitStack(s); while(*p) {

if(*p=='H') push(s,*p); //把'H'存入栈中 else *(q++)=*p; //把'S'调到前部 p++; }

while(!StackEmpty(s)) {

pop(s,c);

*(q++)=c; //把'H'接在后部 }

}//Train_arrange 3.17

int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 {

InitStack(s);

while((e=getchar())!='&') push(s,e);

while((e=getchar())!='@') {

if(StackEmpty(s)) return 0; pop(s,c);

if(e!=c) return 0; }

if(!StackEmpty(s)) return 0; return 1; }//IsReverse 3.18

Status Bracket_Test(char *str)//判别表达式中小括号是否匹配 {

count=0;

for(p=str;*p;p++) {

if(*p=='(') count++;

else if(*p==')') count--; if (count<0) return ERROR; }

if(count) return ERROR; //注意括号不匹配的两种情况 return OK; }//Bracket_Test 3.19

Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配 {

InitStack(s);

for(p=str;*p;p++) {

if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') {

if(StackEmpty(s)) return ERROR; pop(s,c);

if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR;

if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配 } }//for

if(!StackEmpty(s)) return ERROR; return OK;

}//AllBrackets_Test 3.20

typedef struct {

. int x; int y;

} coordinate;

void Repaint_Color(int g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为color {

old=g[i][j]; InitQueue(Q);

EnQueue(Q,{I,j});

while(!QueueEmpty(Q)) {

DeQueue(Q,a); x=a.x;y=a.y; if(x>1)

if(g[x-1][y]==old) {

g[x-1][y]=color;

EnQueue(Q,{x-1,y}); //修改左邻点的颜色 }

if(y>1)

if(g[x][y-1]==old) {

g[x][y-1]=color;

EnQueue(Q,{x,y-1}); //修改上邻点的颜色 }

if(x

if(g[x+1][y]==old) {

g[x+1][y]=color;

EnQueue(Q,{x+1,y}); //修改右邻点的颜色 }

if(y

if(g[x][y+1]==old) {

g[x][y+1]=color;

EnQueue(Q,{x,y+1}); //修改下邻点的颜色 } }//while

}//Repaint_Color

分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢?

3.21

void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new {

p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号 InitStack(s); //s为运算符栈 while(*p) {

if(*p是字母)) *q++=*p; //直接输出 else {

c=gettop(s);

if(*p优先级比c高) push(s,*p); else {

while(gettop(s)优先级不比*p低) {

pop(s,c);*(q++)=c; }//while

push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while

}//NiBoLan //参见编译原理教材 3.22

int GetValue_NiBoLan(char *str)//对逆波兰式求值 {

p=str;InitStack(s); //s为操作数栈 while(*p) {

if(*p是数) push(s,*p); else {

pop(s,a);pop(s,b);

r=compute(b,*p,a); //假设compute为执行双目运算的过程 push(s,r); }//else p++; }//while

pop(s,r);return r; }//GetValue_NiBoLan 3.23

Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new {

p=str;Initstack(s); //s的元素为stringtype类型 while(*p) {

if(*p为字母) push(s,*p); else {

if(StackEmpty(s)) return ERROR; pop(s,a);

if(StackEmpty(s)) return ERROR; pop(s,b);

c=link(link(*p,b),a); push(s,c); }//else p++; }//while pop(s,new);

if(!StackEmpty(s)) return ERROR; return OK;

}//NiBoLan_to_BoLan

分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b). 3.24

Status g(int m,int n,int &s)//求递归函数g的值s {

if(m==0&&n>=0) s=0;

else if(m>0&&n>=0) s=n+g(m-1,2*n); else return ERROR; return OK; }//g 3.25

Status F_recursive(int n,int &s)//递归算法 {

if(n<0) return ERROR; if(n==0) s=n+1; else {

F_recurve(n/2,r); s=n*r; }

return OK; }//F_recursive

Status F_nonrecursive(int n,int s)//非递归算法 {

if(n<0) return ERROR; if(n==0) s=n+1; else {

InitStack(s); //s的元素类型为struct {int a;int b;} while(n!=0) {

a=n;b=n/2;

push(s,{a,b}); n=b; }//while s=1;

while(!StackEmpty(s)) {

pop(s,t); s*=t.a; }//while }

return OK;

}//F_nonrecursive 3.26

float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法 {

if(abs(p^2-A)<=e) return p;

else return sqrt_recurve(A,(p+A/p)/2,e); }//Sqrt_recurve

float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非递归算法 {

while(abs(p^2-A)>=e) p=(p+A/p)/2; return p;

}//Sqrt_nonrecursive 3.27

这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详细写出. 3.28

void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q {

Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 {

p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x;

p->next=Q->next; //直接把p加在Q的后面 Q->next=p;

Q=p; //修改尾指针 }

Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x {

if(Q==Q->next) return INFEASIBLE; //队列已空 p=Q->next->next; x=p->data;

Q->next->next=p->next; free(p); return OK; }//DeCiQueue 3.29

Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法 {

if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示\空\表示\满\ return OVERFLOW; Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法 {

if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front];

if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue

分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值. 3.30

Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法 {

if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法 {

if(Q.length==0) return INFEASIBLE;

head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释 x=Q.base[head]; Q.length--; }//DeCyQueue 3.31

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {

InitStack(S);InitQueue(Q); while((c=getchar()!='@') {

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 }

while(!StackEmpty(S)) {

Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR;

}

return OK;

}//Palindrome_Test 3.32

void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项 {

InitCyQueue(Q); //其MAXSIZE设置为k for(i=0;i

for(i=0;i

m=i%k;sum=0;

for(j=0;j

Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项 printf(\ }

}//GetFib_CyQueue 3.33

Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作 {

if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满 avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2; if(x>=avr) //根据x的值决定插入在队头还是队尾 {

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE; } //插入在队尾 else {

Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } //插入在队头 return OK; }//EnDQueue

Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作 {

if(Q.front==Q.rear) return INFEASIBLE; //队列空 x=Q.base[Q.front];

Q.front=(Q.front+1)%MAXSIZE; return OK; }//DeDQueue 3.34

void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列 {

r=train;

InitDQueue(Q); while(*r) {

if(*r=='P') {

printf(\

printf(\实际上等于不入队列,直接输出P车厢 }

else if(*r=='S') {

printf(\

EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列 } else {

printf(\

EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列 }

}//while

while(!DQueueEmpty(Q))

{

printf(\ DeDQueue(Q);

}//while //从头端出队列的车厢必然是先S后H的顺序 }//Train_Rearrange

第四章 串

4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {

StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 }

}//String_Reverse 4.11

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r {

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++) {

StrAssign(c,SubString(s,i,1));

for(j=1;j

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中 if(k>Strlen(t)) StrAssign(r,Concat(r,c)); } }//for

}//String_Subtract 4.12

int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 {

for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围

if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++; }//if return n; }//Replace

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果? 4.13

int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数 {

for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++) if(!StrCompare(SubString(s,i,Strlen(t)),t)) {

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)); StrAssign(S,Concat(head,tail)); //把head,tail连接为新串 n++; }//if return n,

}//Delete_SubString

4.14

Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new {

Initstack(s); //s的元素为Stringtype类型 for(i=1;i<=Strlen(str);i++) {

r=SubString(str,i,1); if(r为字母) push(s,r); else {

if(StackEmpty(s)) return ERROR; pop(s,a);

if(StackEmpty(s)) return ERROR; pop(s,b);

StrAssign(t,Concat(r,b));

StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c push(s,c); } }//for

pop(s,new);

if(!StackEmpty(s)) return ERROR; return OK;

}//NiBoLan_to_BoLan

分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序. 4.15

void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本 {

for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i]; }//StrAssign 4.16

char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s

for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++); if(i>s[0]&&i>t[0]) return 0; else if(i>s[0]) return -t[i]; else if(i>t[0]) return s[i]; else return s[i]-t[i]; }//StrCompare 4.17

int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 {

for(n=0,i=1;i<=S[0]-T[0]+1;i++) {

for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);

if(k>T[0]) //找到了与T匹配的子串:分三种情况处理 {

if(T[0]==V[0])

for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l];

else if(T[0]

for(l=S[0];l>=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; }

else //新子串长度小于原子串时:先将后部左移 {

for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; }

S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if

}//for return n;

}//String_Replace 4.18

typedef struct {

char ch; int num; } mytype;

void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数 {

mytype T[MAXSIZE]; //用结构数组T存储统计结果 for(i=1;i<=S[0];i++) {

c=S[i];j=0;

while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过 if(T[j].ch) T[j].num++; else T[j]={c,1}; }//for

for(j=0;T[j].ch;j++)

printf(\}//StrAnalyze 4.19

void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r {

r[0]=0;

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

c=s[i];

for(j=1;j

for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t中 if(k>t[0]) r[++r[0]]=c; } }//for

}//Subtract_String

4.20

int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数 {

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

for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++); if(j>m) //找到了与t匹配的子串 {

for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除 s[0]-=t[0];n++; } }//for return n;

}//Delete_SubString 4.21

typedef struct{

char ch;

LStrNode *next;

} LStrNode,*LString; //链串结构

void StringAssign(LString &s,LString t)//把串t赋值给串s {

s=malloc(sizeof(LStrNode)); for(q=s,p=t->next;p;p=p->next) {

r=(LStrNode*)malloc(sizeof(LStrNode)); r->ch=p->ch; q->next=r;q=r; }

q->next=NULL; }//StringAssign

void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在. {

for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next) {

p->ch=q->ch;pre=p; }

while(q) {

p=(LStrNode*)malloc(sizeof(LStrNode)); p->ch=q->ch;

pre->next=p;pre=p; }

p->next=NULL; }//StringCopy

char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s

for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next); if(!p&&!q) return 0;

else if(!p) return -(q->ch); else if(!q) return p->ch; else return p->ch-q->ch; }//StringCompare

int StringLen(LString s)//求串s的长度(元素个数) {

for(i=0,p=s->next;p;p=p->next,i++); return i; }//StringLen

LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针 {

p=malloc(sizeof(LStrNode)); for(q=p,r=s->next;r;r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串s

for(r=t->next;r;r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串t q->next=NULL; return p; }//Concat

LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串 {

p=malloc(sizeof(LStrNode));q=p;

for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r for(i=1;i<=len;i++,r=r->next) {

q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; } //复制串t q->next=NULL; return p; }//Sub_String 4.22

void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c之后 {

p=t.head;

while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符c if(!p) //没找到

{

t.tail->next=s.head;

t.tail=s.tail; //把s连接在t的后面 } else {

q=p->next;

r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个 for(j=0;jch[j]='#'; //原结点p包含c及其以前的部分 for(j=i;j

r->ch[j]=p->ch[j];

p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#' }

p->next=s.head; s.tail->next=r;

r->next=q; //把串s插入到结点p和r之间 }//else

t.curlen+=s.curlen; //修改串长 s.curlen=0;

}//LString_Concat

int Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0 {

for(i=0;ich[i]!=c;i++); if(i==CHUNKSIZE) return 0; else return i+1; }//Find_Char 4.23

int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0 {

InitStack(S);

p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++) {

if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串 else if(k>(S.curlen+1)/2) {

Pop(S,c); //将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c) return 0; //失配 }

if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块 {

p=p->next; i=0; } }//for

return 1; //成功匹配 }//LString_Palindrome 4.24

void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t {

if(t.ch) free(t.ch);

t.ch=malloc((s1.length+s2.length)*sizeof(char)); for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];

for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length; }//HString_Concat 4.25

int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数 {

for(n=0,i=0;i<=S.length-T.length;i++) {

for(j=i,k=0;k

{

if(T.length==V.length)

for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换 S.ch[i+l-1]=V.ch[l-1];

else if(T.length

for(l=S.length-1;l>=i+T.length;l--) S.ch[l+V.length-T.length]=S.ch[l]; for(l=0;l

else //新子串长度小于原子串时:先将后部左移 {

for(l=i+V.length;l

S.length+=V.length-T.length; i+=V.length;n++; }//if }//for return n;

}//HString_Replace 4.26

Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前 {

if(pos<1) return ERROR;

if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾 S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char)); for(i=S.length-1;i>=pos-1;i--)

S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置 for(i=0;i

S.ch[pos+i-1]=T.ch[pos]; //插入串T S.length+=T.length; return OK;

}//HString_Insert 4.27

int Index_New(Stringtype s,Stringtype t)//改进的定位算法 {

i=1;j=1;

while(i<=s[0]&&j<=t[0]) {

if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])) { //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个 i=i+j-2; j=1; } else {

i++;j++; }

}//while

if(j>t[0]) return i-t[0]; }//Index_New 4.28

void LGet_next(LString &T)//链串上的get_next算法 {

p=T->succ;p->next=T;q=T; while(p->succ) {

if(q==T||p->data==q->data) {

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

else q=q->next;

}//while }//LGet_next 4.29

LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针 {

p=pos;q=T->succ; while(p&&q) {

if(q==T||p->chdata==q->chdata) {

p=p->succ; q=q->succ; }

else q=q->next; }//while if(!q) {

for(i=1;i<=Strlen(T);i++) p=p->next; return p;

} //发现匹配后,要往回找子串的头 return NULL; }//LIndex_KMP 4.30

void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度 {

for(maxlen=0,i=1;i

for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动 {

if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数 else k=0; //失配时k归零

if(k>maxlen) //发现了比以前发现的更长的重复子串 {

lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录 } }//for }//for if(maxlen) {

printf(\ printf(\ }

else printf(\}//Get_LRepSub

分析:i代表\错位值\本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明\重复子串\是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2). 4.31

void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度 {

if(S[0]>=T[0]) {

StrAssign(A,S);StrAssign(B,T); } else {

StrAssign(A,T);StrAssign(B,S);

} //为简化设计,令S和T中较长的那个为A,较短的那个为B for(maxlen=0,i=1-B[0];i

if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正 {

jmin=1;jmax=i+B[0];

}//B有一部分在A左端的左边 else if(i>A[0]-B[0]) {

jmin=i;jmax=A[0];

}//B有一部分在A右端的右边 else {

jmin=i;jmax=i+B[0]; }//B在A左右两端之间.

//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax. for(k=0,j=jmin;j<=jmax;j++) {

if(A[j]==B[j-i]) k++; else k=0; if(k>maxlen) {

lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for if(maxlen) {

if(S[0]>=T[0]) {

lpsS=lps1;lpsT=lps2; } else {

lpsS=lps2;lpsT=lps1;

} //将A,B上的位置映射回S,T上的位置

printf(\ printf(\ }//if

else printf(\}//Get_LPubSub

分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。

第五章 数组和广义表

5.18

void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间 {

for(i=1;i<=k;i++)

if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p for(i=0;i

j=i;l=(i+k)%n;temp=A[i]; while(l!=i) {

A[j]=temp; temp=A[l]; A[l]=A[j];

j=l;l=(j+k)%n; }// 循环右移一步 A[i]=temp; }//for }//RSh

分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个\循环链\上面.举例如下: n=15,k=6,则p=3.

第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次.

虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19

void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 {

for(i=0;i

for(min=A[i][0],j=0;j

if(A[i][j]

if(A[i][j]==min) //判断这个(些)最小值是否鞍点 {

for(flag=1,k=0;k printf(\ } }//for

}//Get_Saddle

5.20

本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复. 5.21

void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 {

C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;

}//TSMatrix_Add 5.22

void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上 {

for(i=1;i<=A.tu;i++)

A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A.tu+1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ne=A.data[pa].e+B.data[pb].e; if(ne) //和不为0 {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=ne; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

A.data[pc].i=x;

A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } else {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

A.data[pc].i=x;

A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } }//for A.tu=pc;

for(i=A.tu;i

typedef struct{

int j; int e; } DSElem;

typedef struct{

DSElem data[MAXSIZE];

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

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

Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元组矩阵的元素A[i][j]的值e {

for(s=cpot[i];s

e=A.data[s]; return OK; }

return ERROR;

}//DSMatrix_Locate 5.24

typedef struct{

int seq; //该元素在以行为主序排列时的序号 int e; } SElem;

typedef struct{

SElem data[MAXSIZE]; int mu,nu,tu;

} SMatrix; //单下标二元组矩阵类型

Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e {

s=i*A.nu+j+1;p=1;

while(A.data[p].seq

e=A.data[p].e; return OK; }

return ERROR; }//SMatrix_Locate 5.25

typedef enum{0,1} bool;

typedef struct{

int mu,nu;

int elem[MAXSIZE]; bool map[mu][nu];

} BMMatrix; //用位图表示的矩阵类型

void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法 {

C.mu=A.mu;C.nu=A.nu; pa=1;pb=1;pc=1;

for(i=0;i

for(j=0;j

if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0 {

C.elem[pc]=A.elem[pa]+B.elem[pb]; C.map[i][j]=1; pa++;pb++;pc++; }

else if(A.map[i][j]&&!B.map[i][j]) {

C.elem[pc]=A.elem[pa]; C.map[i][j]=1; pa++;pc++; }

else if(!A.map[i][j]&&B.map[i][j]) {

C.elem[pc]=B.elem[pb]; C.map[i][j]=1; pb++;pc++; } }

}//BMMatrix_Add 5.26

void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵 {

for(i=0;i

if(A.rhead[i])

for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表 printf(\ }

}//Print_OLMatrix 5.27

void OLMatrix_Add(OLMatrix &A,OLMatrix B)//把十字链表表示的矩阵B加到A上 {

for(j=1;j<=A.nu;j++) cp[j]=A.chead[j]; //向量cp存储每一列当前最后一个元素的指针 for(i=1;i<=A.mu;i++) {

pa=A.rhead[i];pb=B.rhead[i];pre=NULL; while(pb) {

if(pa==NULL||pa->j>pb->j) //新插入一个结点 {

p=(OLNode*)malloc(sizeof(OLNode)); if(!pre) A.rhead[i]=p; else pre->right=p; p->right=pa;pre=p;

p->i=i;p->j=pb->j;p->e=pb->e; //插入行链表中 if(!A.chead[p->j]) {

A.chead[p->j]=p; p->down=NULL; } else {

while(cp[p->j]->down) cp[p->j]=cp[p->j]->down; p->down=cp[p->j]->down; cp[p->j]->down=p; }

cp[p->j]=p; //插入列链表中 }//if

else if(pa->jj) {

pre=pa;

pa=pa->right; } //pa右移一步

else if(pa->e+pb->e) {

pa->e+=pb->e;

pre=pa;pa=pa->right; pb=pb->right; } //直接相加 else {

if(!pre) A.rhead[i]=pa->right; else pre->right=pa->right;

p=pa;pa=pa->right; //从行链表中删除 if(A.chead[p->j]==p)

A.chead[p->j]=cp[p->j]=p->down;

else cp[p->j]->down=p->down; //从列链表中删除 free (p); }//else }//while }//for

}//OLMatrix_Add

分析:本题的具体思想在课本中有详细的解释说明. 5.28

void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导 {

for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp) {

if(p->tag) Mul(p->hp,p->exp);

else p->coef*=p->exp; //把指数乘在本结点或其下属结点上 p->exp--; }

pre->tp=NULL;

if(p) free (p); //删除可能存在的常数项 }//MPList_PianDao

void Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x {

for(p=L;p;p=p->tp) {

if(!p->tag) p->coef*=x; else Mul(p->hp,x); } }//Mul 5.29

void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法 {

C=(MPLNode*)malloc(sizeof(MPLNode)); if(!A->tag&&!B->tag) //原子项,可直接相加 {

C->coef=A->coef+B->coef; if(!C->coef) {

free(C); C=NULL; } }//if

else if(A->tag&&B->tag) //两个多项式相加 {

p=A;q=B;pre=NULL; while(p&&q) {

if(p->exp==q->exp) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp;

MPList_Add(A->hp,B->hp,C->hp); pre->tp=C;pre=C; p=p->tp;q=q->tp; }

else if(p->exp>q->exp) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=A->hp; pre->tp=C;pre=C; p=p->tp; } else {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=B->hp; pre->tp=C;pre=C; q=q->tp; }

}//while while(p) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=p->hp;

pre->tp=C;pre=C; p=p->tp; }

while(q) {

C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=q->hp;

pre->tp=C;pre=C; q=q->tp;

} //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题 }//else if

else if(A->tag&&!B->tag) //多项式和常数项相加 {

x=B->coef;

for(p=A;p->tp->tp;p=p->tp);

if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项 if(!p->tp->coef) {

free(p->tp); p->tp=NULL; } else {

q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q;

} //否则新建常数项,下同 }//else if else {

x=A->coef;

for(p=B;p->tp->tp;p=p->tp);

if(p->tp->exp==0) p->tp->coef+=x; if(!p->tp->coef) {

free(p->tp); p->tp=NULL; } else {

q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q; }

}//else

}//MPList_Add 5.30

int GList_Getdeph(GList L)//求广义表深度的递归算法 {

if(!L->tag) return 0; //原子深度为0 else if(!L) return 1; //空表深度为1 m=GList_Getdeph(L->ptr.hp)+1; n=GList_Getdeph(L->ptr.tp); return m>n?m:n; }//GList_Getdeph 5.31

void GList_Copy(GList A,GList &B)//复制广义表的递归算法 {

if(!A->tag) //当结点为原子时,直接复制 {

B->tag=0;

B->atom=A->atom; }

else //当结点为子表时 {

B->tag=1; if(A->ptr.hp) {

B->ptr.hp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.hp,B->ptr.hp); } //复制表头 if(A->ptr.tp) {

B->ptr.tp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.tp,B->ptr.tp); } //复制表尾 }//else

}//GList_Copy

5.32

int GList_Equal(GList A,GList B)//判断广义表A和B是否相等,是则返回1,否则返回0 { //广义表相等可分三种情况:

if(!A&&!B) return 1; //空表是相等的

if(!A->tag&&!B->tag&&A->atom==B->atom) return 1;//原子的值相等 if(A->tag&&B->tag)

if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp)) return 1; //表头表尾都相等 return 0; }//GList_Equal 5.33

void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次 {

if(!A) return;

if(!A->tag) printf(\ else {

GList_PrintElem(A->ptr.hp,layer+1);

GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次 }

}//GList_PrintElem 5.34

void GList_Reverse(GList A)//递归逆转广义表A {

if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转 {

D=C->ptr.hp;

A->ptr.tp->ptr.hp=A->ptr.hp;A->ptr.hp=D; //交换表头和表尾 GList_Reverse(A->ptr.hp);

GList_Reverse(A->ptr.tp); //逆转表头和表尾 }

}//GList_Reverse 5.35

Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针 {

scanf(\ if(ch==' ') {

L=NULL;

scanf(\

if(ch!=')') return ERROR; return OK; }

L=(GList)malloc(sizeof(GLNode)); L->tag=1;

if(isalphabet(ch)) //输入是字母 {

p=(GList)malloc(sizeof(GLNode)); //建原子型表头 p->tag=0;p->atom=ch; L->ptr.hp=p; }

else if(ch=='(') Create_GList(L->ptr.hp); //建子表型表头 else return ERROR; scanf (\

if(ch==')') L->ptr.tp=NULL;

else if(ch==',') Create_GList(L->ptr.tp); //建表尾 else return ERROR; return OK; }//Create_GList

分析:本题思路见书后解答. 5.36

void GList_PrintList(GList A)//按标准形式输出广义表 {

if(!A) printf(\空表

else if(!A->tag) printf(\原子 else {

printf(\

GList_PrintList(A->ptr.hp); if(A->ptr.tp) {

printf(\

GList_PrintList(A->ptr.tp);

} //只有当表尾非空时才需要打印逗号 printf(\ }//else

}//GList_PrintList 5.37

void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子 {

if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x); else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x) {

q=A;

A=A->ptr.tp; //删去元素值为x的表头 free(q);

GList_DelElem(A,x); }

if(A->ptr.tp) GList_DelElem(A->ptr.tp,x); }//GList_DelElem 5.39

void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素 {

InitQueue(Q);

for(p=L;p;p=p->ptr.tp) EnQueue(Q,p); while(!QueueEmpty(Q)) {

DeQueue(Q,r);

if(!r->tag) printf(\ else

for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); }//while

}//GList_PrintElem_LOrder

分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.

第六章 树和二叉树

6.33

int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 {

if(u==v) return 1; else {

if(L[v])

if (Is_Descendant(u,L[v])) return 1; if(R[v])

if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 }

return 0;

}//Is_Descendant_C 6.34

int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0 {

for(p=u;p!=v&&p;p=T[p]); if(p==v) return 1; else return 0; }//Is_Descendant_P

6.35

这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 6.36

int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法 {

if(!B1&&!B2) return 1;

else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild)) return 1; else return 0; }//Bitree_Sim 6.37

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 {

InitStack(S);

Push(S,T); //根指针进栈 while(!StackEmpty(S)) {

while(Gettop(S,p)&&p) {

visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p);

if(!StackEmpty(S)) {

pop(S,p);

push(S,p->rchild); //向右一步 }

}//while

}//PreOrder_Nonrecursive 6.38

typedef struct {

BTNode* ptr;

enum {0,1,2} mark;

} PMType; //有mark域的结点指针类型

void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈 {

PMType a;

InitStack(S); //S的元素为PMType类型 Push (S,{T,0}); //根结点入栈 while(!StackEmpty(S)) {

Pop(S,a);

switch(a.mark) {

case 0:

Push(S,{a.ptr,1}); //修改mark域

if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树 break; case 1:

Push(S,{a.ptr,2}); //修改mark域

if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树 break; case 2:

visit(a.ptr); //访问结点,返回 }

}//while

}//PostOrder_Stack

分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作. 6.39

typedef struct {

int data;

EBTNode *lchild; EBTNode *rchild; EBTNode *parent; enum {0,1,2} mark;

} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型

void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈 {

p=T;

while(p)

switch(p->mark) {

case 0:

p->mark=1;

if(p->lchild) p=p->lchild; //访问左子树 break; case 1:

p->mark=2;

if(p->rchild) p=p->rchild; //访问右子树 break; case 2: visit(p);

p->mark=0; //恢复mark值 p=p->parent; //返回双亲结点 }

}//PostOrder_Nonrecursive

分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历. 6.40

typedef struct {

int data;

PBTNode *lchild; PBTNode *rchild; PBTNode *parent;

} PBTNode,PBitree; //有双亲指针域的二叉树结点类型

void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树 {

p=T;

while(p->lchild) p=p->lchild; //向左走到尽头 while(p) {

visit(p);

if(p->rchild) //寻找中序后继:当有右子树时 {

p=p->rchild;

while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头 }

else if(p->parent->lchild==p) p=p->parent; //当自己是双亲的左孩子时后继就是双亲 else {

p=p->parent;

while(p->parent&&p->parent->rchild==p) p=p->parent; p=p->parent;

} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先 }//while

}//Inorder_Nonrecursive 6.41

int c,k; //这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)//求先序序列为k的结点的值 {

if(T) {

c++; //每访问一个子树的根都会使前序序号计数器加1 if(c==k) {

printf(\

exit (1); } else {

Get_PreSeq(T->lchild); //在左子树中查找 Get_PreSeq(T->rchild); //在右子树中查找 } }//if

}//Get_PreSeq

main() {

...

scanf(\

c=0; //在主函数中调用前,要给计数器赋初值0 Get_PreSeq(T,k); ... }//main 6.42

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 6.43

void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 {

T->lchild<->T->rchild; //交换左右子树

if(T->lchild) Bitree_Revolute(T->lchild);

if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 }//Bitree_Revolute 6.44

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {

if(T->data==x) {

printf(\找到了值为x的结点,求其深度 exit 1; } else {

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 }

}//Get_Sub_Depth

int Get_Depth(Bitree T)//求子树深度的递归算法 {

if(!T) return 0; else {

m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }

}//Get_Depth 6.45

void Del_Sub_x(Bitree T,int x)//删除所有以元素x为根的子树 {

if(T->data==x) Del_Sub(T); //删除该子树 else {

if(T->lchild) Del_Sub_x(T->lchild,x);

if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找 }//else

}//Del_Sub_x

void Del_Sub(Bitree T)//删除子树T {

if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }//Del_Sub 6.46

void Bitree_Copy_Nonrecursive(Bitree T,Bitree &U)//非递归复制二叉树 {

InitStack(S1);InitStack(S2); push(S1,T); //根指针进栈

U=(BTNode*)malloc(sizeof(BTNode)); U->data=T->data; q=U;push(S2,U);

while(!StackEmpty(S)) {

while(Gettop(S1,p)&&p) {

q->lchild=(BTNode*)malloc(sizeof(BTNode)); q=q->lchild;q->data=p->data; push(S1,p->lchild); push(S2,q); } //向左走到尽头 pop(S1,p); pop(S2,q);

if(!StackEmpty(S1)) {

pop(S1,p);pop(S2,q);

q->rchild=(BTNode*)malloc(sizeof(BTNode)); q=q->rchild;q->data=p->data; push(S1,p->rchild); //向右一步 push(S2,q); }

}//while

}//BiTree_Copy_Nonrecursive

分析:本题的算法系从6.37改写而来. 6.47

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列 EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

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

}//LayerOrder 6.48

int found=FALSE;

Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)//求二叉树T中结点p和q的最近共同祖先 {

Bitree pathp[ 100 ],pathq[ 100 ] //设立两个辅助数组暂存从根到p,q的路径 Findpath(T,p,pathp,0); found=FALSE;

Findpath(T,q,pathq,0); //求从根到p,q的路径放在pathp和pathq中

for(i=0;pathp[i]==pathq[i]&&pathp[i];i++); //查找两条路径上最后一个相同结点 return pathp[--i]; }//Find_Near_Ancient

void Findpath(Bitree T,Bitree p,Bitree path[ ],int i)//求从T到p路径的递归算法 {

if(T==p) {

found=TRUE; return; //找到 }

path[i]=T; //当前结点存入路径

if(T->lchild) Findpath(T->lchild,p,path,i+1); //在左子树中继续寻找

if(T->rchild&&!found) Findpath(T->rchild,p,path,i+1); //在右子树中继续寻找 if(!found) path[i]=NULL; //回溯 }//Findpath 6.49

int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 {

InitQueue(Q); flag=0;

EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) {

DeQueue(Q,p); if(!p) flag=1;

else if(flag) return 0; else {

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 }

}//while return 1;

}//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针. 6.50

Status CreateBitree_Triplet(Bitree &T)//输入三元组建立二叉树 {

if(getchar()!='^') return ERROR; T=(BTNode*)malloc(sizeof(BTNode)); p=T;p->data=getchar(); getchar(); //滤去多余字符 InitQueue(Q); EnQueue(Q,T);

while((parent=getchar())!='^'&&(child=getchar())&&(side=getchar())) {

while(QueueHead(Q)!=parent&&!QueueEmpty(Q)) DeQueue(Q,e); if(QueueEmpty(Q)) return ERROR; //未按层序输入 p=QueueHead(Q);

q=(BTNode*)malloc(sizeof(BTNode)); if(side=='L') p->lchild=q;

else if(side=='R') p->rchild=q; else return ERROR; //格式不正确 q->data=child; EnQueue(Q,q); }

return OK;

}//CreateBitree_Triplet 6.51

Status Print_Expression(Bitree T)//按标准形式输出以二叉树存储的表达式 {

if(T->data是字母) printf(\ else if(T->data是操作符) {

if(!T->lchild||!T->rchild) return ERROR; //格式错误

if(T->lchild->data是操作符&&T->lchild->data优先级低于T->data) {

printf(\

if(!Print_Expression(T->lchild)) return ERROR;

printf(\

} //注意在什么情况下要加括号

else if(!Print_Expression(T->lchild)) return ERROR;

if(T->rchild->data是操作符&&T->rchild->data优先级低于T->data) {

printf(\

if(!Print_Expression(T->rchild)) return ERROR; printf(\ }

else if(!Print_Expression(T->rchild)) return ERROR; }

else return ERROR; //非法字符 return OK;

}//Print_Expression 6.52

typedef struct{

BTNode node; int layer;

} BTNRecord; //包含结点所在层次的记录类型

int FanMao(Bitree T)//求一棵二叉树的\繁茂度\{

int countd; //count数组存放每一层的结点数 InitQueue(Q); //Q的元素为BTNRecord类型 EnQueue(Q,{T,0});

while(!QueueEmpty(Q)) {

DeQueue(Q,r);

count[r.layer]++;

if(r.node->lchild) EnQueue(Q,{r.node->lchild,r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild,r.layer+1}); } //利用层序遍历来统计各层的结点数

h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++)

if(count[i]>maxn) maxn=count[i]; //求层最大结点数 return h*maxn; }//FanMao

分析:如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上会复杂一些,你能写出来吗? 6.53 int maxh;

Status Printpath_MaxdepthS1(Bitree T)//求深度等于树高度减一的最靠左的结点 {

Bitree pathd;

maxh=Get_Depth(T); //Get_Depth函数见6.44 if(maxh<2) return ERROR; //无符合条件结点 Find_h(T,1); return OK;

}//Printpath_MaxdepthS1

void Find_h(Bitree T,int h)//寻找深度为maxh-1的结点 {

path[h]=T; if(h==maxh-1) {

for(i=1;path[i];i++) printf(\ exit; //打印输出路径 } else {

if(T->lchild) Find_h(T->lchild,h+1); if(T->rchild) Find_h(T->rchild,h+1); }

path[h]=NULL; //回溯 }//Find_h 6.54

Status CreateBitree_SqList(Bitree &T,SqList sa)//根据顺序存储结构建立二叉链表 {

Bitree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针 if(!sa.last) {

T=NULL; //空树 return; }

ptr[1]=(BTNode*)malloc(sizeof(BTNode)); ptr[1]->data=sa.elem[1]; //建立树根 T=ptr[1];

for(i=2;i<=sa.last;i++) {

if(!sa.elem[i]) return ERROR; //顺序错误 ptr[i]=(BTNode*)malloc(sizeof(BTNode)); ptr[i]->data=sa.elem[i]; j=i/2; //找到结点i的双亲j

if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子 else ptr[j]->lchild=ptr[i]; //i是j的左孩子 }

return OK;

}//CreateBitree_SqList 6.55

int DescNum(Bitree T)//求树结点T的子孙总数填入DescNum域中,并返回该数 {

if(!T) return -1;

else d=(DescNum(T->lchild)+DescNum(T->rchild)+2); //计算公式 T->DescNum=d; return d; }//DescNum

分析:该算法时间复杂度为O(n),n为树结点总数.注意:为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回-1而不是0. 6.56

BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针 {

if(p->lchild) return p->lchild; else return p->rchild; }//PreOrder_Next

分析:总觉得不会这么简单.是不是哪儿理解错了? 6.57

Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针 {

if(p->rtag) return p->rchild; //p有后继线索 else if(!p->parent) return NULL; //p是根结点

else if(p==p->parent->rchild) return p->parent; //p是右孩子 else if(p==p->parent->lchild&&p->parent->tag) return p->parent; //p是左孩子且双亲没有右孩子 else //p是左孩子且双亲有右孩子 {

q=p->parent->rchild;

while(!q->ltag||!q->rtag) {

if(!q->ltag) q=q->lchild; else q=q->rchild;

} //从p的双亲的右孩子向下走到底 return q; }//else

}//PostOrder_Next 6.58

Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)//在中序线索二叉树T的结点p下插入子树x {

if(!p->ltag&&!p->rtag) return INFEASIBLE; //无法插入 if(p->ltag) //x作为p的左子树 {

s=p->lchild; //s为p的前驱

p->ltag=Link; p->lchild=x; q=x;

while(q->lchild) q=q->lchild;

q->lchild=s; //找到子树中的最左结点,并修改其前驱指向s q=x;

while(q->rchild) q=q->rchild;

q->rchild=p; //找到子树中的最右结点,并修改其前驱指向p }

else //x作为p的右子树 {

s=p->rchild; //s为p的后继 p->rtag=Link; p->rchild=x; q=x;

while(q->rchild) q=q->rchild;

q->rchild=s; //找到子树中的最右结点,并修改其前驱指向s q=x;

while(q->lchild) q=q->lchild;

q->lchild=p; //找到子树中的最左结点,并修改其前驱指向p }

return OK;

}//Insert_BiThrTree 6.59

void Print_CSTree(CSTree T)//输出孩子兄弟链表表示的树T的各边 {

for(child=T->firstchild;child;child=child->nextsib) {

printf(\ Print_CSTree(child); }

}//Print_CSTree 6.60

int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目 {

if(!T->firstchild) return 1; //叶子结点 else {

count=0;

for(child=T->firstchild;child;child=child->nextsib) count+=LeafCount_CSTree(child); return count; //各子树的叶子数之和 }

}//LeafCount_CSTree 6.61

int GetDegree_CSTree(CSTree T)//求孩子兄弟链表表示的树T的度 {

if(!T->firstchild) return 0; //空树 else {

degree=0;

for(p=T->firstchild;p;p=p->nextsib) degree++;//本结点的度 for(p=T->firstchild;p;p=p->nextsib) {

d=GetDegree_CSTree(p);

if(d>degree) degree=d; //孩子结点的度的最大值 }

return degree; }//else

}//GetDegree_CSTree 6.62

int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T的深度 {

if(!T) return 0; //空树

else {

for(maxd=0,p=T->firstchild;p;p=p->nextsib)

if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度 return maxd+1; }

}//GetDepth_CSTree 6.63

int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度 {

return SubDepth(A.r); }//GetDepth_CTree

int SubDepth(int T)//求子树T的深度 {

if(!A.nodes[T].firstchild) return 1;

for(sd=1,p=A.nodes[T].firstchild;p;p=p->next) if((d=SubDepth(p->child))>sd) sd=d; return sd+1; }//SubDepth 6.64

int GetDepth_PTree(PTree T)//求双亲表表示的树T的深度 {

maxdep=0;

for(i=0;i

dep=0;

for(j=i;j>=0;j=T.nodes[j].parent) dep++; //求每一个结点的深度 if(dep>maxdep) maxdep=dep; }

return maxdep; }//GetDepth_PTree 6.65

char Pred,Ind; //假设前序序列和中序序列已经分别储存在数组Pre和In中

Bitree Build_Sub(int Pre_Start,int Pre_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表 {

sroot=(BTNode*)malloc(sizeof(BTNode)); //建根 sroot->data=Pre[Pre_Start];

for(i=In_Start;In[i]!=sroot->data;i++); //在中序序列中查找子树根 leftlen=i-In_Start;

rightlen=In_End-i; //计算左右子树的大小 if(leftlen) {

lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1); sroot->lchild=lroot;

} //建左子树,注意参数表的计算 if(rightlen) {

rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End); sroot->rchild=rroot;

} //建右子树,注意参数表的计算 return sroot; //返回子树根 }//Build_Sub

main() {

...

Build_Sub(1,n,1,n); //初始调用参数,n为树结点总数 ... }

分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标. 6.66

typedef struct{

CSNode *ptr;

CSNode *lastchild;

} NodeMsg; //结点的指针和其最后一个孩子的指针

Status Bulid_CSTree_PTree(PTree T)//由树T的双亲表构造其孩子兄弟链表 {

NodeMsg Treed;

for(i=0;i

Tree[i].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[i].ptr->data=T.node[i].data; //建结点 if(T.nodes[i].parent>=0) //不是树根 {

j=T.nodes[i].parent; //本算法要求双亲表必须是按层序存储 if(!(Tree[j].lastchild)) //双亲当前还没有孩子

Tree[j].ptr->firstchild=Tree[i].ptr; //成为双亲的第一个孩子 else //双亲已经有了孩子

Tree[j].lastchild->nextsib=Tree[i].ptr; //成为双亲最后一个孩子的下一个兄弟 Tree[j].lastchild=Tree[i].ptr; //成为双亲的最后一个孩子 }//if }//for

}//Bulid_CSTree_PTree 6.67

typedef struct{

char data; CSNode *ptr;

CSNode *lastchild;

} NodeInfo; //结点数据,结点指针和最后一个孩子的指针 Status CreateCSTree_Duplet(CSTree &T)//输入二元组建立树的孩子兄弟链表 {

NodeInfo Treed; n=1;k=0;

if(getchar()!='^') return ERROR; //未按格式输入 if((c=getchar())=='^') T=NULL; //空树

Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[0].data=c;

Tree[0].ptr->data=c;

while((p=getchar())!='^'&&(c=getchar())!='^') {

Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[n].data=c;

Tree[n].ptr->data=c;

for(k=0;Tree[k].data!=p;k++); //查找当前边的双亲结点 if(Tree[k].data!=p) return ERROR; //未找到:未按层序输入 r=Tree[k].ptr;

if(!r->firstchild)

r->firstchild=Tree[n].ptr;

else Tree[k].lastchild->nextsib=Tree[n].ptr;

Tree[k].lastchild=Tree[n].ptr; //这一段含义同上一题 n++; }//while return OK;

}//CreateCSTree_Duplet 6.68

Status CreateCSTree_Degree(char node[ ],int degree[ ])//由结点的层序序列和各结点的度构造树的孩子兄弟链表 {

CSNode * ptrd; //树结点指针的辅助存储 ptr[0]=(CSNode*)malloc(sizeof(CSNode));

i=0;k=1; //i为当前结点序号,k为当前孩子的序号 while(node[i]) {

ptr[i]->data=node[i]; d=degree[i]; if(d) {

ptr[k++]=(CSNode*)malloc(sizeof(CSNode)); //k为当前孩子的序号 ptr[i]->firstchild=ptr[k]; //建立i与第一个孩子k之间的联系

for(j=2;j<=d;j++) {

ptr[k++]=(CSNode*)malloc(sizeof(CSNode));

ptr[k-1]->nextsib=ptr[k]; //当结点的度大于1时,为其孩子建立兄弟链表 }//for }//if i++;

}//while

}//CreateCSTree_Degree 6.69

void Print_BiTree(BiTree T,int i)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0 {

if(T->rchild) Print_BiTree(T->rchild,i+1);

for(j=1;j<=i;j++) printf(\打印i个空格以表示出层次 printf(\打印T元素,换行 if(T->lchild) Print_BiTree(T->rchild,i+1); }//Print_BiTree

分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左. 6.70

Status CreateBiTree_GList(BiTree &T)//由广义表形式的输入建立二叉链表 {

c=getchar();

if(c=='#') T=NULL; //空子树 else {

T=(CSNode*)malloc(sizeof(CSNode)); T->data=c;

if(getchar()!='(') return ERROR;

if(!CreateBiTree_GList(pl)) return ERROR; T->lchild=pl;

if(getchar()!=',') return ERROR;

if(!CreateBiTree_GList(pr)) return ERROR; T->rchild=pr;

if(getchar()!=')') return ERROR; //这些语句是为了保证输入符合A(B,C)的格式 }

return OK;

}//CreateBiTree_GList 6.71

void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0 {

for(j=1;j<=i;j++) printf(\留出i个空格以表现出层次 printf(\打印元素,换行 for(p=T->firstchild;p;p=p->nextsib) Print_CSTree(p,i+1); //打印子树 }//Print_CSTree 6.72

void Print_CTree(int e,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次 {

for(j=1;j<=i;j++) printf(\留出i个空格以表现出层次 printf(\打印元素,换行 for(p=T.nodes[e].firstchild;p;p=p->next) Print_CSTree(p->child,i+1); //打印子树 }//Print_CSTree

main() {

...

Print_CTree(T.r,0); //初次调用时i=0 ... }//main 6.73

char c; //全局变量,指示当前字符

Status CreateCSTree_GList(CSTree &T)//由广义表形式的输入建立孩子兄弟链表 {

c=getchar();

T=(CSNode*)malloc(sizeof(CSNode)); T->data=c;

if((c=getchar())=='(') //非叶结点 {

if(!CreateCSTree_GList(fc)) return ERROR; //建第一个孩子 T->firstchild=fc;

for(p=fc;c==',';p->nextsib=nc,p=nc) //建兄弟链 if(!CreateCSTree_GList(nc)) return ERROR; p->nextsib=NULL;

if((c=getchar())!=')') return ERROR; //括号不配对 }

else T->firtchild=NULL; //叶子结点 return OK;

}//CreateBiTree_GList

分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断. 6.74

void PrintGlist_CSTree(CSTree T)//按广义表形式输出孩子兄弟链表表示的树 {

printf(\

if(T->firstchild) //非叶结点 {

printf(\

for(p=T->firstchild;p;p=p->nextsib) {

PrintGlist_CSTree(p);

if(p->nextsib) printf(\最后一个孩子后面不需要加逗号 }

printf(\ }//if

}//PrintGlist_CSTree 6.75

char c;

int pos=0; //pos是全局变量,指示已经分配到了哪个结点

Status CreateCTree_GList(CTree &T,int &i)//由广义表形式的输入建立孩子链表 {

c=getchar();

T.nodes[pos].data=c;

i=pos++; //i是局部变量,指示当前正在处理的子树根 if((c=getchar())=='(') //非叶结点 {

CreateCTree_GList();

p=(CTBox*)malloc(sizeof(CTBox)); T.nodes[i].firstchild=p;

p->child=pos; //建立孩子链的头

for(;c==',';p=p->next) //建立孩子链 {

CreateCTree_GList(T,j); //用j返回分配得到的子树根位置 p->child=j;

p->next=(CTBox*)malloc(sizeof(CTBox)); }

p->next=NULL;

if((c=getchar())!=')') return ERROR; //括号不配对 }//if

else T.nodes[i].firtchild=NULL; //叶子结点 return OK;

}//CreateBiTree_GList

分析:该算法中,pos变量起着\分配\结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n. 6.76

void PrintGList_CTree(CTree T,int i)//按广义表形式输出孩子链表表示的树 {

printf(\

if(T.nodes[i].firstchild) //非叶结点 {

printf(\

for(p=T->firstchild;p;p=p->nextsib) {

PrintGlist_CSTree(T,p->child);

if(p->nextsib) printf(\最后一个孩子后面不需要加逗号 }

printf(\ }//if

}//PrintGlist_CTree

第七章 图

7.14

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) {

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK;

}//Build_AdjList 7.15

//本题中的图G均为有向无权图,其余情况容易由此写出

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

G.arcs[i][j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v {

n=G.vexnum;

if((m=LocateVex(G,v))<0) return ERROR;

G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点

for(i=0;i

G.arcs[i][m]=G.arcs[i][n];

G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加. Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc 7.16

//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL;

if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; }

G.arcnum++; return OK; }//Insert_Arc 7.17

//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出. Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v {

if((m=LocateVex(G,v))<0) return ERROR; n=G.vexnum;

for(i=0;i

if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点 {

q=G.xlist[i].firstin;

G.xlist[i].firstin=q->hlink; free(q);G.arcnum--; }

else //否则 {

for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink); if(p) {

q=p->hlink;

p->hlink=q->hlink; free(q);G.arcnum--; }

}//else }//for

for(i=0;i

if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点 {

q=G.xlist[i].firstout;

G.xlist[i].firstout=q->tlink; free(q);G.arcnum--; }

else //否则 {

for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink); if(p) {

q=p->tlink;

p->tlink=q->tlink; free(q);G.arcnum--; }

}//else }//for

for(i=m;i

G.xlist[i]=G.xlist[i+1]; //修改表头向量 for(p=G.xlist[i].firstin;p;p=p->hlink) p->headvex--;

for(p=G.xlist[i].firstout;p;p=p->tlink) p->tailvex--; //修改各链中的顶点序号 }

G.vexnum--; return OK; }//Delete_Vex 7.18

//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.

Status Delete_Arc(AMLGraph &G,char v,char w)////在邻接多重表表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.adjmulist[i].firstedge->jvex==j)

G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else {

for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); if (!p) return ERROR; //未找到 p->ilink=p->ilink->ilink; } //在i链表中删除该边

if(G.adjmulist[j].firstedge->ivex==i)

G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink; else {

for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink); if (!p) return ERROR; //未找到 q=p->jlink;

p->jlink=q->jlink; free(q);

} //在i链表中删除该边 G.arcnum--; return OK; }//Delete_Arc 7.19

Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表 {

InitAMLGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.adjmulist[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++)

{

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(EBox*)malloc(sizeof(EBox)); p->ivex=i;p->jvex=j;

p->ilink=NULL;p->jlink=NULL; //边结点赋初值

if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p; else {

q=G.adjmulist[i].firstedge; while(q) {

r=q;

if(q->ivex==i) q=q->ilink; else q=q->jlink; }

if(r->ivex==i) r->ilink=p;//注意i值既可能出现在边结点的ivex域中, else r->jlink=p; //又可能出现在边结点的jvex域中 }//else //插入i链表尾部

if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p; else {

q=G.adjmulist[i].firstedge; while(q) {

r=q;

if(q->jvex==j) q=q->jlink; else q=q->ilnk; }

if(r->jvex==j) r->jlink=p; else r->ilink=p;

}//else //插入j链表尾部 }//for return OK;

}//Build_AdjList 7.20

int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0 {

for(x=0;x

for(z=0;z

if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//图不可传递的条件 }//if return 1; }//Pass_MGraph

分析:本算法的时间复杂度大概是O(n^2*d). 7.21

int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0 {

for(x=0;x

for(p=G.vertices[x].firstarc;p;p=p->nextarc) {

y=p->adjvex;

for(q=G.vertices[y].firstarc;q;q=q->nextarc) {

z=q->adjvex;

if(z!=x&&!is_adj(G,x,z)) return 0; }//for }//for

}//Pass_ALGraph

int is_adj(ALGraph G,int m,int n)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0 {

for(p=G.vertices[m].firstarc;p;p=p->nextarc) if(p->adjvex==n) return 1;

return 0; }//is_adj 7.22

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else

}//exist_path_DFS 7.23

int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS 7.24

void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j);

visited[j]=1;

Push(S,j); //向左走到尽头 }

}//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {

visit(k);

visited[k]=1; Push(S,k);

} }//if }//while

}//Straverse_Nonrecursive

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7.25 见书后解答. 7.26

Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点 {

int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号 n=G.vexnum;

FindInDegree(G,indegree); InitStack(S);

for(i=1;i

if(!indegree[i]) Push(S,i); //零入度结点入栈 count=0;

while(!StackEmpty(S)) {

Pop(S,i);

new[i]=n--; //记录结点的拓扑逆序序号 count++;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!(--indegree[k])) Push(S,k); }//for }//while

if(count

for(i=1;i<=n;i++) printf(\ return OK; }//TopoNo

分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵. 7.27

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len 7.28

int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径

int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度 {

path[k]=u; //加入当前路径中 visited[u]=1;

if(u==v) //找到了一条简单路径 {

printf(\

for(i=0;path[i];i++) printf(\打印输出 }

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