数据结构(c语言描述)马秋菊源代码和习题参考答案.pdf

《数据结构(c语言描述)马秋菊源代码和习题参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构(c语言描述)马秋菊源代码和习题参考答案.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题配套 第一章 2C、A、B、B、A、A、D 3 D=A,B,C,E,F,G,H,I,J;R=,4顺序、链式、索引、哈希。*5解：100n22nn至少要多大 6.(n)、(n)、(n)、(n)、(5)当 nm，(n),当 mn，(m)7n!2100lgnn1/2n3/2(3/2)n2nnlgnnn 第二章 1、2AAD 4顺序表 void Delete_SeqListx(SeqList*L,ElemType x)/*删除表中值为x元素*/inti,j;for(i=1;ilength;i+)if(L-elemi=x)for(j=i;jlength-1;j+)L-elemj=L-elemj+1;

2、L-length-;/*向上挪动*/O(n2)A B C E F G H I 题 1-3 图 J 链表 void del_link(LinkList H，int x)/*删除数据域为 x 的结点*/LNode*p，*q;p=H;q=H-next;while(q!=NULL)if(q-data=x)p-next=q-next;free(q);q=p-next;elsep=q;q=q-next;O(n)5 int Delete_SeqListx(SeqList*L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/intj;if(i1|kL-length)/*检查空表及删除位置

3、的合法性*/printf(不存在第i个元素);return ERROR;for(j=i;jlength-k;j+)L-elemj=L-elemj+k;/*向上挪动*/L-length-=k;Return OK;/*删除成功*/O(n)6 void Delete_SeqListx(SeqList*L,ElemType x)/*将表中值为x元素换成y*/inti,j;for(i=1;ilength;i+)if(L-elem=x)L-elemi=y;/*/O(n)7写一算法在循环单链表上实现线性表的 CList_length(L)运算。int link_length(LinkList H)LNode

4、*p;int i=0;p=H;while(p-next!=H)i+;p=p-next;return i;O(n)8 在用头指针表示的单循环链表中，查找开始结点 a1的时间是 O(1)，然而要查找终端结点那么需从头指针开始遍历整个链表，其时间是 O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进展，假设改用尾指针 rear 来表示单循环链表，那么查找开始结点 a1和终端结点 an都很方便，它们的存储位置分别是 rear-next-next 和 rear，显然，查找时间都是 O(1)。9.int Insert_LinkListab(LinkList H,ElemType a,Elem

5、Type b)/*在单链表中值为a的结点前插入一个值为b的结点*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-data!=a)/*q-next&q-next-data!=a*/q=p;p=p-next;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s-data=b;s-next=q-next;/*新结点插入在第i-1个结点的后面*/q-next=s；return OK;/*Insert_LinkListab*/10顺序表 void Reverse_Sq(SqList*L)/*顺序表的就地逆置*/for

6、(i=1，j=L.len;inext;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next;/*把 H 的元素逐个插入新表表头*/q-next=p;s-next=q;H-next=s;/*Reverse_L*/分析：本算法的思想是，逐个地把 L 的当前元素 q 插入新的链表头部，p 为新表表头。11 void merge1(LinkList&A,LinkList&B,LinkList&C)/*把链表 A 和 B 合并为 C,A 和 B 的元素间隔排列,且使用原存储空间*/p=A-next;q=B-next;C=

7、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*/12 Status Delete_Pre(CiLNode s)/*删除单循环链表中结点 p 的直接前驱*/q=p;while(q-next-next!=p)q=q-next;/*找到 p 的前驱的前驱*/s=q-next;q-next=p;free(s);return OK;/*Delete_Pre*/13 Status Insert_SqList(SeqList&L，in

8、t x)if(L-length+1m-1)return ERROR;L-length+;i=L-length;while(L-elemix&i0;)L-elemi+1=L-elemi;i-;L-elemi+1=x;return OK;/*Insert_SqList 14 intInsert_Linkx(LinkList H,ElemType x)/*在值递增单链表中插入一个值为x的结点，仍递增*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-datanext&q-next-datanext;/*查找a结点*/s=(LinkList)malloc(sizeof(L

9、Node);/*申请、填装结点*/s-data=x;s-next=q-next;/*新结点插入*/q-next=s；return OK;/*Insert_Linkx*/15 源程序代码：在测试通过#include#include structnode intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/;structnode*CreatList(intnum)/*建立循环链表*/inti;structnode*ptr1,*head;if(ptr1=(structnode*)malloc(sizeof(structnod

10、e)=NULL)perror(malloc);returnptr1;head=ptr1;ptr1-next=head;for(i=1;inext=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);ptr1-next=head;returnhead;ptr1=ptr1-next;ptr1-next=head;returnhead;main()inti,n=30,m;/*人数 n 为 30 个*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;inumber=i

11、;head-cipher=rand();head=head-next;m=rand();/*m 取随机数*/i=0;/*因为我没方法删除 head 指向的节点，只会删除 head 的下一节点，所以只能从 0 数起。*/while(head-next!=head)/*当剩下最后一个人时，退出循环*/if(i=m)ptr=head-next;/*ptr 记录数到 m 的那个人的位置*/printf(number:%dn,ptr-number);printf(cipher:%dn,ptr-cipher);m=ptr-cipher;/*让 m 等于数到 m 的人的密码*/head-next=ptr-n

12、ext;/*让 ptr 从链表中脱节，将前后两个节点连接起来*/head=hea/d-next;/*head 移向后一个节点*/free(ptr);/*释放 ptr 指向的内存*/i=0;/*将 i 重新置为 0，从 0 再开始数*/else head=head-next;i+;printf(number:%dn,head-number);printf(cipher:%dn,head-cipher);free(head);/*让最后一个人也出列*/16 void SqList_Intersect(SqList A,SqList B,SqList&C)/*求元素递增排列的线性表 A 和 B 的元

13、素的交集并存入 C 中*/i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj)C.elem+k=A.elemi;/当发现了一个在 A,B 中都存在的元素,/就添加到 C 中 i+;j+;/*while*/*SqList_Intersect*/17 Status DuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的 pre 域*/p=H;while(q-next!=H)p-next-pre=p;p=p-next;return OK;/*DuLNode_Pre*/第三章 栈与队列

14、 1假定有编号A、B、C的3辆列车顺序开进一个栈式构造的站台，请写出每一种开出站台的列车编号顺序(注：每一列车开出栈开出站台后，不允许再进栈)。2指出下述程序段的功能是什么？void Demo1(SeqStack*S)int i;arra16;n=16；initStack(&S);for(i=0,inext=NULL;s=(LinkStack*)mallocsizeofLinkStack;s-top=p;判栈空 int Empty_LSLinkStack*s return s-top-next=NULL;入栈 LinkStack *Push_LSLinkStack*s,ElemType x S

15、tackNode *p=(StackNode*)mallocsizeofStackNode;p-data=x;p-next=s-top-next;/*将元素 x 插入链栈顶*/s-top-next=p;return s;出栈 int Pop_LS(LinkStack*s,ElemType *y)StackNode *p;if Empty_LS s printf(Stack Underflow.);/*下溢*/return OVERFLOW;else *y=s-top-next-data;=s-top-next;s-top-next=p-next;free(p);return OK;取栈顶元素

16、int GetTop(LinkStack*s,ElemType*y)if(Empty_LS(s)printf(Stack underflow.);/*下溢*/return OVERFLOW;else*y=s-top-next-data;return OK;4 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

17、=)&c!=()return ERROR;if(*p=)&c!=return ERROR;if(*p=)&c!=return ERROR;/*必须与当前栈顶括号匹配*/*for*/if(!StackEmpty(s)return ERROR;return OK;/*AllBrackets_Test*/或 int PairBracket(char*S)/*检查表达式中括号是否配对*/int i;SeqStack T;/*定义一个栈*/InitStack(&T);for(i=0;istrlen(S);i+)if(Si=()Push(&T，Si);/*遇(时进栈*/if(Si=)Pop(&T);/*遇

18、)时出栈*/return!EmptyStack(&T);/*由栈空否返回正确配对与否*/5写出计算表达式5+3*3/6-7时操作数和算符栈的变化情况。表达式5+3*4/6-7的求值过程 步骤 运算符栈 OPTR 对象栈 OPND 读字符 主要操作 1#5 5+3*3/6-7#5 入栈 OPND 2#+5+3*3/6-7#+入栈 OPTR 3#+5，3 3*3/6-7#3 入栈 OPND 4#+*5，3*3/6-7#*入栈 OPTR 5#+*(5，3 3/6-7#(入栈 OPTR 6#+*(5，3，3 4/6-7#3 入栈 OPND 7#+*(/5，3，3/6-7#/入栈 OPTR 8#+*(/

19、5，3，3，6 6-7#6 入栈 OPND 9#+*(5，3，-7#3，6 出栈 OPND，/出栈 OPTR 求 4/6OPND 10#+*(-5，3，-7#-入栈 OPTR 11#+*(-5，3，7 7#7 入栈 OPND 12#+*(5，3，#0.5，7 出栈 OPND，-出栈 OPTR OPND 13#+*5，3，#(出栈 14#+5，#3，OPND，*出栈 OPTR OPND 15#5，OPND，*出栈 OPTROPND 16#RERTURN()6对于给定的十进制正整数，输出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。(1)递归算法。void conversion1(

20、int N,int R)if(N0)push(S,n);n=n-1;while(!EmptyStack(S)Pop(S,i);f=f*i;return(f);8.void huiwen()Init_LS(s);printf(Please input a string:n);for(i=0;(i20)&(ai=getchar()!=n);+i);/*输入字符串*/for(j=0;ji/2;+j)/*字符串的前一半入栈*/Push_LS(s,aj);for(j=i-i/2;jrear-sq-front sq-rear=sq-front count=m-(sq-front-sq-rear)sq-re

21、arfront 11循环队列的优点是什么？如何判别它的空和满？优点：防止假溢出；判别循环队列的空：return(sq-rear=sq-front)；判别循环队列的满：return(sq-rear+1)%MAXSIZE=sq-front)12假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素位置(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。typedef struct qnode ElemType data;struct qnode*next;QCNode;/*链式循环链队列结点的类型*/typedef struct QCNode *rear;LCQueue;/*

22、只设一个指向队尾元素的指针*/1置空队算法：void Init_LCQueue(LCQueue *Lcq)p=(QCnode*)malloc(sizeof(QCNode);/*申请头结点*/p-next=p;Lcq-rear=p;2判队空算法：int Empty_LCQueue(LCQueue*Lcq)return Lcq-rear-next=Lcq-rear;/*或 Lq-rear=NULL;*/3入队算法：void In_LCQueue(LCQueue*Lcq,ElemType x)/*进队操作*/LCQueue*p;p=(QCNode*)malloc(sizeof(QCNode);/*申

23、请新结点*/p-data=x;p-next=Lcq-rear-next;Lcq-rear-next=p;Lcq-rear=p;/*In_LCQueue*/4出队算法：int Out_LCQueue(LCQueue*Lq,ElemType*y)LCQueue p;if(Empty_LCQueue(Lq)printf(队空);return OVERFLOW;/*队空,出队失败*/else p=Lcq-rear-next-next;/*队头第一个数据元素结点*/Lcq-rear-next-next=p-next;*y=p-data;/*队头元素放 y 中*/free(p);return OK;13假

24、设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针，用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队列的算法。typedef struct queuenode ElemType elemMAXSIZE;/*队列中数据元素的存储空间*/int front,count;/*队头指针、队中元素数量*/CirQueue;/*以上是结点类型的定义*/void Init_Queue(CirQueue *Q)/*置空队*/Q-front=Q-count=0;int Empty_Queue(CirQueue*Q)/*判队空*/return(Q-count=

25、0);int In_Queue(CirQueue*Q,ElemType x)/*入队*/if(Q-count=MAXSIZE)printf(队已满，不可以入队);return OVERFLOW;Q-elem(sq-front+sq-count)%MAXSIZE=x;sq-count+;return OK;int Out_Queue(CirQueue*Q,ElemType *y)/*出队*/if(Empty_Queue(Q)printf(队已空，无元素可以出队);return OVERFLOW);*y=sq-elemsq-front;/*读出队头元素*/sq-front=(sq-front+1)

26、%MAXSIZE;sq-count-;return OK;int Front_Queue(CirQueue*Q,ElemType *y)/*取队头元素*/if(Empty_Queue(Q)printf(队空，无元素可取);return OVERFLOW);*y=sq-elemsq-front;/*读出队头元素*/return OK;14设长度为n的链队列用单循环链表表示，假设只设头指针，那么入队出队操作的时间复杂度是多少？假设只设尾指针呢？假设只设头指针，那么入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(n)；假设只设尾指针，那么入队操作的时间复杂度都是O(1)。*15写一个算法，

27、借助于栈将一个单链表置逆。第 4 章 数组 1请按行和按列优先顺序列出二维数组A34的所有元素在内存中的存储次序，开始结点为a00。a00 a10 a20 a01 a11 a21 a02 a12 a22 a03 a13 a23 2写出三维数组地址计算公式。设三维数组 Amn*p，先行，列，最后 Z 方向 LOCAijk=LOCA00 0+(imn+jm+k)L 3设有三对角矩阵A nn，将其三条对角线上的元素逐行地存储到向量B03n-3中，使得Bk=aij，求：用i,j表示k的下标变换公式。Aij之间的对应关系为：k=2i+j 4二维数组 M 的元素是 4 个字符每个字符占一个存储单元组成的串

28、，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5，M 按行存储时元素 M35的起始地址与 M 按列存储时元素 的起始地址一样。A.m24 B.M34 C.M35 D.M43 M35 与 M 存储时元素 M35 起始地址一样。5数组 A 中，每个元素 A 的存储占 3 个单元，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的单元个数是1，假设该数组按行存放时，元素 A85的起始地址是2，假设该数组按列存放时，元素 A85的起始地址是。1 A.80 B.100 C.240 D.270 2 A.SA+141 B

29、.SA+144 C.SA+222 D.SA+225 3 A.SA+141 B.SA+180 C.SA+222 D.SA+225 1C.2 C.3 A 6对于二维数组 Amn，其中 m=80，n=80，先读入 m，n，然后读入该数组的全部元素，对如下三种情况分别编写相应函数：(1)求数组A边界元素之和。int sum(L)int row,col,sum=0;for(row=0;rown;row+)sum=L0row;sum=sum+Lm-1row;/*列*/for(col=0;coln;col+)sum=Lcol0;sum=sum+Lcolm-1;/*行*/(2)求从 A00开始的互不相邻的各元

30、素之和；int sum2(L)int row,col,sum1=0,sum2=0;for(row=0;rown;row+,row+)for(col=0;coln;col+,col+)sum1=sum1+Lrowcol;sum2=sum2+Lrow+1col+1;(3)当m=n时，分别求两条对角线的元素之和，否那么打印m!=n的信息。int sum2(L)int row,col,sum3=0,sum3=0;if(m!=n)printf(m!=n!n);else for(row=0;rowrheadi;while(q)&(q-colright;if(!q)printf(“not searched!

31、;return NULL;)p=M-cheadj;while(q)&(q-rowdown;if(!p)printf(“not searched!;return NULL;)return p;2数据元素的值x，查找 x 在A中的行、列号；QLNode *searchx(CrossList M,ElemType x)int i;/*mu,nu*/for(i=1;irheadi;if(q)&(q-vx)q=q-right;else return q;9简述广义表和线性表的区别和联络。答：一样点：线性；不同点：数据元素分为原子和广义表。10设广义表L=(),()，试问head(L),tail(L)，L

32、的长度、深度各为多少？head(L)=()tail(L)=()L的长度为2。11求以下广义表运算的结果(1)head(a,b,c)=(a,b,c)；(2)tail(b,d,p,h)=()；(3)head(a,b),(c,d)=(a,b),(c,d)；(4)tail(a,b),(c,d)=()；(5)head(tail(a,b),(c,d)=()；(6)tail(head(a,b),(c,d)=()第 6 章 树 1.根据题意画出树的形状为右图：a 是根结点，mndfjkl 是叶结点；c 是 g 的双亲；c，a 是 g 的祖先；j，k 是 g 的孩子；imn 是 e 的子孙；d 是 e 的兄弟；

33、g，h 是 f 的兄弟；b 的层次是 2；n 的层次是 5；树的深度是 5；以 c 为根的子树深度是 3；树的度数是 3。2三个结点的二叉树如下所示：有五种形态：(1)(2)(3)(4)(5)树的形状 a c b f g d e l j k i m m h C B A D L K M N 图 6-29 (a)(b)3分别写出图 6-28(a)所示的二叉树的前序、中序和后序遍历序列。前序 ABCDEF 中序 ACEDB 后序 EDCBA 4画出图 6-28(b)所示二叉树顺序存储和二叉链表的存储构造。5请画出如图 6-29 所示两棵二叉树的顺序存储构造，并比较每棵二叉树所用的存储空间的大小。(b

34、)所用的存储空间的大 6一棵完全二叉树的第 3 层上有 4 个叶子结点，问该二叉树最多有多少个结点？7 个结点 B A C D E A B C D G E F H I(b)(a)图 6-28 7一棵二叉树只存在度数为 0 或度数为 2 的结点，度数为 2 的结点有 19 个，问度数为0 的结点有多少个？20 个，分析：根据公式 n0=n2+1，有 n0=19+1=20 8写出用非递归实现二叉树的中序遍历算法，并分析其时间复杂度和栈所需要的最大容量。二叉树的中序遍历的非递归算法。void Inorder2BTNode*bt /*利用栈实现前序遍历非递归算法*/p=bt；top=-1；while(

35、p|top-1)if(p)/*二叉树非空*/+top；stop=p；/*根结点指针进栈*/p=p-lchild；/*p 移向左孩子*/else /*栈非空*/p=stop；-top；/*双亲结点指针出栈*/printf(p-data)；/*访问根结点，输出结点*/p=p-rchild；/*p 移向右孩子*/*Inorder2*/9假设某二叉树的前序遍历序列为 ABCDEFGHI 和中序遍历序列为 BCAEDGHFI，试画出该二叉树。并写出后序遍历的结果。10设二叉树以二叉链表形式存储，写一算法交换各结点的左右子树。void Exchange1(BTNode*bt)/*交换左右子树的第一种方法*

36、/if(*bt)/*这里以指针为参数使交换在实参结点上进展*/BTNode p;Exchange1(&(*bt)-lchild);Exchange1(&(*bt)-rchild);p=(*bt)-lchild;(*bt)-lchild=(*bt)-rchild;(*bt)-rchild=p;void Exchange2(BTNode*bt)A B D C H E F G I /*交换左右子树的第二种方法*/if(bt)BTNode*p;p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;Exchange2(bt-lchild);Exchange2(bt-rc

37、hild);/*Exchange2*/11设二叉树以二叉链表形式存储，写出一个求叶子结点总个数的算法。void Leaf_BiTree(BTNode*T)/*求树的深度及叶子结点个数*/if(T)if(T-lchild=NULL&T-rchild=NULL)printf(%cn,T-data);count+;Leaf_BiTree(T-lchild,j);Leaf_BiTree(T-rchild,j);/*Leaf_BiTree*/12画出 6-28(b)所示二叉树对应的森林。13画出图 6-28(b)所示二叉树所对应的中序线索二叉树。中序遍历序列为 DGBAECHFI 14写出在中序线索二叉

38、树上查找值为 x 的结点的算法。A B C D G E F H I A B C D G E F H I 15对给定的一组权值：15，2，9，13，8，20，22，构造一棵哈夫曼树，并计算出带权途径长度。16写出实现图 6-27(c)所示将百分制转换为五级分断定过程的算法。第 8 章 习 题 1对图 7-22 所示的有向图中，试求出：(1)每个顶点的入度和出度；ID0=1,OD0=1 ID1=2,OD1=1 ID2=1,OD2=2 ID3=0,OD3=2 ID4=3,OD4=0 ID5=1,OD5=2(2)邻接矩阵；(3)写出该图的邻接表。0 0 0 0 1 0 1 0 0 0 0 0 0 1

39、0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 A=V0 V1 V2 V3 V5 V4 图 7-22 有向图 V0 V1 V2 V3 0 5 4 1 4 2 1 1 V4 V5 2求如图 7-22 所示图的每个结点的入度和出度和总度数，并编写算法。每个结点的总度数：OD0=2 OD1=3 OD2=3 OD3=2 OD4=3 OD5=3 假设用邻接矩阵存储构造，入度和出度和总度数的算法如下：void Mages(Mgraph *ma)Mgraph ma;int indVERTEX_MAX=0,outdVERTEX_MAX=0,totledVERTEX_MA

40、X=0;for(i=0;in;i+)/*求出度*/for(j=0;in;j+)If(ma-arcsij=1)outdi+;for(i=0;in;i+)/*求出度*/for(j=0;in;j+)If(ma-arcsji=1)indi+;for(i=0;in;i+)totledi=indi+outdi;printf(vertex id od toteldn);/*求总度数*/for(i=0;in;i+)printf(%s%d%d%dn,G-adjlisti.vertex,indi,outdi,totledi);3 对于 n 个顶点构成的无向图 或有向图，采用邻接矩阵和邻接表两种方式进展存储，写出下

41、面要求的算法：(1)求图中的边数；有向图邻接矩阵 int Mages(Mgraph *ma)int ages=0;for(i=0;in;i+)/*求出度*/for(j=0;in;j+)If(ma-arcsij=1)ages+;return Mages;假设是无向图，最后 Mages 要除以 2。有向图邻接表存储构造求边数：void f_ind(ALGraph*G)int i;int ALages;/*三个变量分别为入度、出度和总度数*/EdgeNode*p;for(i=0;in;i+)/*求出度*/p=G-adjlisti.firstedge;while(p!=NULL)ALages+;p=p

42、-next;return ALages;假设是无向图，最后 ALages 要除以 2。(2)任意两个顶点的邻接关系；邻接矩阵存储构造 void Mcnn(Mgraph *ma)for(i=0;in;i+)/*求出度*/for(j=0;in;j+)If(ma-arcsij=1)printf(“v%d,v&d)n,i,j);return Mages;邻接表存储构造 void conn(ALGraph*G)EdgeNode*p;for(i=0;in;i+)/*求出度*/p=G-adjlisti.firstedge;while(p!=NULL)printf(“v%d,v&d)n,i,p-adjvex)

43、;p=p-next;(3)每个顶点的度，有向图的入度和出度。邻接表存储 void f_ind(MGraph*G)int i;int ALages;/*三个变量分别为入度、出度和总度数*/EdgeNode*p;for(i=0;in;i+)/*求出度*/p=G-adjlisti.firstedge;while(p!=NULL)ALages+;p=p-next;return ALages;有向图邻接表 void f_ind(ALGraph*G)int i;int indVERTEX_MAX=0,outdVERTEX_MAX=0,totledVERTEX_MAX=0;/*三个变量分别为入度、出度和总度

44、数*/EdgeNode*p;for(i=0;in;i+)/*求出度*/p=G-adjlisti.firstedge;while(p!=NULL)outdi+;p=p-next;for(i=0;in;i+)/*求入度，依次扫描每个链表*/p=G-adjlisti.firstedge;while(p!=NULL)indp-adjvex+;p=p-next;for(i=0;in;i+)totledi=indi+outdi;printf(vertex id od toteldn);/*求总度数*/for(i=0;in;i+)printf(%s%d%d%dn,G-adjlisti.vertex,indi

45、,outdi,totledi);4对于如图 7-23 所示的无向图，完成如下题目：(1)画出邻接表。A B C D 3 4 2 4 2 E F 3 1 2 0 5 3 10 5 3 14 4 A B C D E F 3 2 3 5 3 5 3 5 7 4 6 (2)写出邻接矩阵；(3)深度优先遍历:ABCDEF 广度优先遍历 ABECDF 5强连通分量。6 n-1,2(n-1)7对带权途径无向图 7-24，求解下面的问题：(1)求该图的邻接矩阵。(2)最小生成树两种情况 2 1 0 0 1 0 3 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0

46、0 1 0 1 0 A=V0 V1 V2 V3 V5 V4 1 2 2 1 0 10 5 7 2 2 36 4 6 6 3 5 5 8对于图 7-25 所示的连通图，分别用 Prim 和 Kruskal 算法构造其最小生成树。Prim 算法构造其最小生成树过程从 A 点开始 Kruskal 算法构造其最小生成树过程 A B C D F E 2 6 6 3 5 4 4 A B C D E G H F 5 3 1 4 2 6 5 2 7 A B C D F E 2 6 6 5 3 4 A C A C D A C D 3 1 3 1 3 B 2 A C D 1 3 B 2 E 4 A C D 1 3

47、 B 2 E 4 4 F A C D 1 3 B 2 E 4 4 F H 2 G 5 A C D 1 B E F H G A C D 1 B 2 E F H G 9根据 dijkstra 算法求出图 7-24 中顶点 A 到各个顶点之间的最短途径。终点 从 A 到各终点的 Dist 值和最短途径的求解过程 i=1 i=2 i=3 i=4 i=5 B 2(A,B)C 5(A,B,C)D 10(A,B,C,D)E 6(A,E)6(A,E)6(A,E)F 12(A,B,C,F)12(A,B,C,F)12(A,B,C,F)B C E D F S A,B A,B,C A,C,D,E(A,B,C,D)(A,B,C,F)A C D 1 B 2 E F H 2 G A C D 1 3 B 2 E F H 2 G A C D 1 3 B 2 E 4 F H 2 G A C 1 3 B 2 E 4 4 F H 2 G D A C 1 3 B 2 E 4 4 F H 2 G D 5