数据结构与算法 习题与练习答案.pdfVIP

附录 习题与练习解答 第 1 章 习题与练习解答 一、选择题答案 17：b c c b b d c 二、基本知识题答案 1名词解释答案 数据：一切能够由计算机接受和处理的对象。 数据项：数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。 数据元素：数据的基本单位，在程序中作为一个整体加以考虑和处理，也称为元素、顶 点或记录。它可以由若干个数据项组成。 数据结构：数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的 存储结构和数据的运算三个方面的内容。 数据逻辑结构：数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关， 独立于计算机。 数据物理结构：数据元素及其关系在计算机存储器内的表示，是数据的逻辑结构用计算 机语言的实现，是依赖于计算机语言的。 算法：对特定问题求解步骤的一种描述。它是一个有穷的规则序列，这些规则决定了解 决某一特定问题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和 处理，经过有限的计算步骤后能得到一定的输出。 算法的时间复杂性：是该算法的时间耗费，它是该算法所求解问题规模 n 的函数。当 n 趋向无穷大时，我们把时间复杂性 t(n)的数量级称为算法的渐进时间复杂性。 2答：对算法进行分析的目的有两个。第 1 个目的是可以从解决同一问题的不同算法中 区分相对优劣，选出较为适用的一种。第 2 个目的是有助于设计人员考虑对现有算法进行改 进或设计出新的算法。 3答：算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平 均时间复杂性是研究同样的 n 值时各种可能的输入，取它们运算时间的平均值。 4答：评价好的算法有 4 个方面。一是算法的正确性；二是算法的易读性；三是算法的 健壮性；四是算法的时空效率(运行)。 5答：对算法 a1 和 a2 的时间复杂度 t1 和 t2 取对数，得 nlog2 和 2logn。显然，算法 a2 好于算法 a1。 三、答案 1答：该程序段的时间复杂性为 t(n)=o(n)。 2答：该程序段的时间复杂性 t(n)=o(log10n)。 附录 习题与练习解答 259 3答：该程序段的时间复杂性 t(n)=o(n2)。 4答：该程序段的时间复杂性为 t(n)=o(n)。 第 2 章 习题与练习解答 一、选择题答案 15：a b b b c 610：a d c b b 二、基本知识题答案 1答：链式存储结构克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素， 只需修改指针，时间复杂度为 o(1)；其次，不需要预先分配空间，可根据需要动态申请空间； 其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许 时，就不能克服顺序存储的缺点。 2答：采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用节 点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。 3答：顺序表用节点物理位置的相邻性来反映节点间的逻辑关系，其优点：节省存储、 随机存取，当表长变化较小、主要操作是进行查找时，宜采用顺序表。链表用附加的指针来 反映节点间的逻辑关系，插入和删除操作相对比较方便，当表长变化较大，主要操作是进行 插入和删除时，宜采用链表。 4 答： 双链表比单链表多增加了一个指针域以指向节点的直接前趋， 它是一种对称结构， 因此在已知某个节点之前或之后插入一个新节点、删除该节点或其直接后继都同样方便，操 作的时间复杂度为 o(1)；而单链表是单向结构，对于找一个节点的直接前趋的操作要从开始 节点找起，其时间复杂度为 o(n)。 5答：由于对表的操作常常在表的两端进行，所以对单循环链表，当知道尾指针 rear 后，其另一端的头指针是 rear-next-next(表中带头节点)。这会使操作变得更加容易。 6答：s-prior=p;s-next=p-next;p-next-prior=s;p-next=s; 7答：s-next=p-next;p-next=s;temp=p-data;p-data=s-data;s-data=temp; 8答：多项式 a(x)用链表表示如下： 4 11 9 8 11 3 7 0 heada 8 1 三、算法设计题答案 1. 解：将该线性表逆序可以通过将 a0与 an-1、a1与 an-2两两交换来完成。注 意互相交换的 ai与 aj的数组下标的关系 i+j=n-1，i 从 0 到 n/2-1 变化。实现本题功能的函 数如下： void reverse(int a,int n) int i,j,temp; for(i=0;i0) b.dataj+=a.datai; (b.n)+; else c.datak+=a.datai; (c.n)+; 3. 解：#define n 30 typedef struct seqlist int datan; /*用来存放数据元素*/ int n; /*用来记录数据元素的个数*/ seqlist; void delik(seqlist if (i+ka.n) /*大于数组长度*/ printf(“超出数组下界！“); else for(j=i-1;jn) printf(“error!n“); else p=head; for(j=1;jnext; q=p-next; data=q-data; q-data=p-data; p-data=data; 6. 解：实现本题功能的函数如下。 void search(linklist *head,int x) linklist *p; p=head; while(p-data!=x if(p!=null) printf(“找到！n“); else printf(“未找到！n“); 数据结构与算法 262 7. 解：本题的算法思想：先找到值为 x 的节点*p 和它的前趋节点*q，要删除*q，只需把 *p 的值 x 放到*q 的值域中，再删除节点*p 即可。实现本题功能的函数如下： void delete(linklist * q=head; p=head-next; while(p!=null) p=p-next; if(p=null) printf(“未找到 x！n“); else if(q=head) printf(“x 为第一个节点，无前趋！n“); else q-data=x; q-next=p-next; free(p); 8. 解：实现本题功能的函数如下。 void del_length(linklist * int j; if(i=1) for(j=1;jnext; free(p); else p=head; for(j=1;jnext; /*p 指向要删除的节点的前一个节点*/ for(j=1;jnext; /*q 指向要删除的节点*/ p-next=q-next; free(q); 附录 习题与练习解答 263 9解：实现本题功能的算法如下。 void discreate( linklist *a, linklist * b=a; c=(linklist *)malloc(sizeof(linklist); c-next=null; p=a-next; b-next=null; while(p!=null) r=p-next; if (p-datanext=b-next; b-next=p; else p-next=c-next; c-next=p; p=r; 10解：本题的算法思想：依次查找原单链表(其头指针为 head1)中的每个节点，对每个 节点复制一个新节点并链接到新的单链表(其头指针为 head2)中。 实现本题功能的函数如下： void copy( linklist *head1, linklist * head2=(linklist *)malloc(sizeof(linklist); q=head2; q-data=head1-data; p=head1-next; while(p!=null) s=(linklist *)malloc(sizeof(linklist); s-data=p-data; q-next=s; q=s; p=p-next; q-next=null; 11解：本题的算法思想：在原单链表一半处将其分开，第 5 个节点的 next 域置为空， 为第 1 个单链表的表尾。第 2 个单链表的表头指针指向原单链表的第 6 个节点。实现本题功 能的函数如下，函数返回生成的第 2 个单链表的表头指针，第 1 个单链表仍然使用原单链表 的表头指针。 数据结构与算法 264 linklist *divide( linklist *head1 ) linklist *head2,*prior; head2=head1; for(int i=1;inext; prior-next=null; return head2; 12解：本题的算法思想：将第 1 个链表中的所有偶数序号的节点删除，同时把这些节 点链接起来构成第 2 个单链表。实现本题功能的函数如下： void split(linklist *head1, linklist * odd=head1; head2=head1-next; temp=head2; while(odd!=null /* even 指向偶数序号的节点*/ odd-next= even -next; temp-next= even; temp= even; odd=odd-next; /*odd 指向奇数序号的节点*/ even -next=null; 13解：本题的算法思想：因为是单循环链表，所以只要另设一指针 q 指向 p 用来帮助 判断是否已经遍历一遍即可。实现本题功能的函数如下： void travel(linklist *p) linklist *q=p; while(q-next!=p) printf(“%4d“,q-data); q=q-next; printf(“%4d“,q-data); 14解：本题的算法思想：从头到尾扫描该循环链表，将第 1 个节点的 next 域置为 null，将第 2 个节点的 next 域指向第 1 个节点， 如此直至最后一个节点， 便用 head 指向它。 由于是循环链表，所以判定最后一个节点时不能用 p-next=null 作为条件，而是用 q 指向 第 1 个节点，以 p!=q 作为条件。实现本题功能的函数如下： 附录 习题与练习解答 265 void ivert(linklist * p=head; q=p-next; /*q 指向链表第 2 个节点*/ while(p!=q) r=q; while(r-next !=p) r=r-next; p-next=r; /*节点的 next 逆向*/ p=p-next; q-next=head; 15解：能。本题的算法思想：从 p 开始沿着 next 向右扫描直至遇到开始节点即可遍历 整个链表。实现本题功能的函数如下： typedef int elemtype; typedef struct dlnode /*定义双链表节点类型*/ elemtype data; struct dlnode *prior,*next; /*指向前驱，后继节点*/ dlinklist; void travellist(dlinklist *p) dlinklist *q; q=p; while(q!=p-prior) printf(“%4d“,q-data); q=q-next; printf(“%4d“,q-data); 16解：实现本题功能的算法如下。 void deletepre(dlinklist *p) dlinklist *pre,*q; pre=p-prior; q=pre-prior; if(pre=p) printf(“p 节点无前趋！n“); else q-next=pre-next; p-prior=pre-prior; free(pre); 数据结构与算法 266 17解：实现本题功能的算法如下。 void exchange(linklist * q=head-next; pre=head; while(q!=null q=q-next; if(p-next=null) printf(“p 无后继节点n“); else q=p-next; pre-next=q; p-next=q-next; q-next=p; 18解：实现本题功能的算法如下。 void minivalue(linklist * linklist *p, *pre, *u; p=la; pre=p; while(p-next!=null) if(p-next-data) data) pre=p-next; p=p-next; printf(“最小值=%dn“,pre-data); if(pre-data%2!=0) if(pre-next!=null) t= pre-data; pre-data=pre-next-data; pre-next-data=t; else if(pre-next!=null) 附录 习题与练习解答 267 u=pre-next; pre-next=u-next; free(u); 19解：本题的算法思想：先建立一个待插入的节点，然后依次与链表中的各节点的数 据域比较大小，找到插入该节点的位置，然后插入该节点。实现本题功能的函数如下： void insert(linklist * s=(linklist *)malloc(sizeof(linklist); /*建立一个待插入的节点*/ s-data=x; s-next=null; if(head=null|xdata) /*若单链表为空或 x 小于第 1 个节点 data 域*/ s-next=head; /*插入到表头后面*/ head=s; else q=head; p=q-next; while(p!=null p=p-next; s-next=p; /*插入节点*/ q-next=s; 第 3 章 习题与练习解答 一、选择题 15：b a c a d 611：c c d c a b 二、基本知识题答案 1. 答：栈是限定在表的一端进行插入或删除操作的线性表；队列是元素的添加在表的一 端进行，而元素的删除在表的另一端进行的线性表；栈的特点是后进先出，队列的特点是先 进先出。 2. 答：栈和队列都是线性表，但是是受限的线性表，对插入、删除运算加以限制。栈是 只允许在一端进行插入、删除运算，是后进先出表；而队列是只允许在一端进行插入、另一 端进行删除运算，是先进先出表。 数据结构与算法 268 3. 答：栈的入栈、出栈操作均在栈顶进行，栈顶指针指向栈顶元素处。入栈操作先将栈 顶指针加 1，然后将入栈元素放到栈顶指针所指示的位置上。出栈操作先从栈顶指针指向位 置取值，然后将栈顶指针减 1。 4. 答：在循环队列中，设队首指针指向队首元素，队尾指针指向队尾元素后的一个空闲 元素。在队列不满时，可执行入队操作，此时先送值到队尾指针指向的空闲元素，队尾指针 再加 1(要取模)。在队列不空时，可执行出队操作，此时先从队首指针指向处取值，队首指针 再减 1(要取模)。 5. 答：栈结构主要应用在下列三个方面：算术表达式的求值；子程序的调用与返回； 递归函数的求值。 队列结构主要应用在需要“排队”的事件中如操作系统中的作业调度等。 三、算法设计题答案 1解：用 top 表示栈顶指针，top 为 0 时表示栈为空。如果栈不空，则从 stack0开始存 放元素。实现本题功能的函数如下。 入栈算法： #define n 100 void push(int stack,int if(top+length)n) /*n 为堆栈的大小*/ printf(“上溢出n“); else for(i=0;i=0;i-) xi=stack-top; 2解：设表达式在字符数组 a 中，使用一堆栈 s 来帮助判断。实现本题功能的函数如下。 #define n 100 typedef struct char datan; int top; 附录 习题与练习解答 269 sepstack; int correct(char a ) int i; sepstack s; for(i=0;ir.len) printf(“出界n“); else for(k=i+j;kch=c) p-ch=s; p=p-link; 数据结构与算法 274 5. 解：实现本题功能的函数如下。 void insert(linkstring *a,linkstring *b,int k) int i=1; linkstring *p,*q; p=a; while(ilink; i+; if(p=null) printf(“k 值错！n“); else q=b; while(q!=null) q=q-link; q-link=p-link; p-link=b; 6. 解：实现本题功能的函数如下。 int strcmp(sqstring s,sqstring t) int i,minlen; if (s.lent.datai) return (1); else i+; if (s.len=t.len) return (0); else if (s.lenmax ) head=i; max=count; if (max1 ) printf (“最大等值子串：“); for (k=head;k(n)?(m):(n) /*矩阵行列较大者*/ typedef struct node int row, col; /*行号，列号*/ struct node *down , *right; /*向右和向下的指针*/ union int v; struct node *next; v_next; mnode,*mlink; mlink hds+1; void delnode(mlink l,int i,int j) int m,n; mlink p,q; p=hdi-right; while(p-right!=hdi-right) if(p-col!=j) q=p;p=p-right; if(p-right=hdi-right) printf(“该元素不存在！n“); else q-right=p-right; p=hdj-down; while(p-down!=hdi-down) if(p-row!=i) q=p;p=p-down; if(p-down=hdi-down) printf(“该元素不存在！n“); else q-down=p-down; free(p); 第 6 章 习题与练习解答 一、选择题答案 15：a b b c c 210：b a c c b 数据结构与算法 278 1115：d d b c b 二、基本知识题答案 1答：(1)a 是根节点。 (2)d、h、i、j、f、g 是叶子节点。 (3)b 是 e 的父节点。 (4)h、i、j 是 e 的子孙节点。 (5)d 是 e 的兄弟节点，b 是 c 的兄弟节点。 (6)b 的层数是 2，i 的层数是 4。 (7)树的深度是 4。 (8)以节点 g 为根的子树的深度是 1。 (9)树的度是 3。 2. 答：3 个节点的树为 3 个节点的二叉树为 3. 答：高度为 h 的完全二叉树至少有 1 2h个节点，最多有 1 2h个节点。 4. 答：该二叉树的顺序存储为 9 12 3 4 56 8 79 0 12 3 4 55714131211109815 该二叉树的链式存储为 4 1 5 3 2 6 7 9 8 附录 习题与练习解答 279 5. 答：先序遍历序列：1、2、4、7、3、5、8、6、9。 中序遍历序列：7、4、2、1、8、5、3、6、9。 后序遍历序列：7、4、2、8、5、9、6、3、1。 6. 答： (1) (2) b c d e f g a h i b c de f g a h 7. 答：先序遍历序列：a、b、d、e、f、c、g。 中序遍历序列：d、f、e、b、a、g、c。 后序遍历序列：f、e、d、b、g、c、a。 8. 答：二叉排序树为 119 55 34 88 46 76 97 99 18 11 9 9. 答：本题对应的哈夫曼树为 18 711 3 1 2 465 0 0 0 0 1 11 1 b a e c d 数据结构与算法 280 各字符对应的哈夫曼编码为 a: 10, b: 001, c: 000, d: 11, e: 01。 10建立二叉排序树并计算平衡因子如下图： 由于树中所有节点的平衡因子的绝对值均小于 1，故这是一棵平衡二叉树。 三、算法设计题答案 1. 解：求二叉树节点总数的算法如下。 int countnode(bitree t,int num) /*num 初值为 0*/ if(t!=null) num+; num=countnode(t-lchild,num); num=countnode(t-rchild,num); return num; 求二叉树叶子节点总数的算法如下： int countleaf(bitree t,int num) /*num 初值为 0*/ if(t!=null) if(t-lchild=null num=countleaf(t-lchild,num); num=countleaf(t-rchild,num); return num; 2. 解：本题可以用先序、中序和后序遍历中的任意一种遍历，只要将遍历算法中的访问 根节点改为判断其值是否等于 x 即可。下面是用中序遍历求解的算法，函数返回值为 x 节点 的地址，若没有找到则返回空。 bitree search(bitree t, int x,bitree p) /*p 的初值为 null*/ if(t!=null) 附录 习题与练习解答 281 p=search(t-lchild, x, p); if(t-data=x) p=t; /*找到 x 的地址放在 p 中*/ p=search(t-rchild, x, p); return p; 3. 解：这是一个递归算法，如下。 void create(bitree create(t-lchild, tree, 2*i); create(t-rchild, tree, 2*i+1); 4. 解：按中序序列遍历二叉排序树即按递增次序遍历。递增打印二叉排序树各元素值的 函数如下。 void inorder(bitree printf(“%d“, t-data); inorder(t-rchild); 5. 解：在中序线索二叉树中进行非递归中序遍历，只要从头节点出发，反复找到节点的 后继，直至结束即可。在中序线索二叉树中求节点后继的算法如下。 bithrtree succ(bithrtree p) bithrtree q; if(p-rtag=1) return (p-rchild); else q=p-rchild; while(q-ltag=0) q=q-lchild; return(q); 数据结构与算法 282 由此得到中序遍历线索二叉树的非递归算法如下： void thinorder (bithrtree p) if(p!=null) while(p-ltag=0) p=p-lchild; do printf(“%d“, p-data); p=succ(p); while(p!=null); 6解：在后序序列中，若节点 p 有右子女，则右子女是其前驱，若无右子女而有左子女， 则左子女是其前驱。若节点 p 左右子女均无，设其中序左线索指向某祖先节点 f(p 是 f 右子树 中按中序遍历的第 1 个节点)，若 f 有左子女，则其左子女是节点 p 在后序下的前驱；若 f 无 左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女(这时左子女是 p 的前驱)。还有 一种情况，若 p 是中序遍历的第 1 个节点，节点 p 在中序和后序下均无前驱。 算法如下： bithrtree postpre (bithrtree t, bithrtree p) bithrtree q; if (p-rtag=0) q=p-rchild; /*若 p 有右子女，则右子女是其后序前驱*/ else if (p-ltag=0) q=p-lchild; /*若 p 无右子女而有左子女，则左子女是其后序前驱。*/ else if(p-lchild=null) q=null; /*p 是中序序列第 1 节点，无后序前驱*/ else /*顺左线索向上找 p 的祖先，若存在，再找祖先的左子女*/ while(p-ltag=1 if(p-ltag=0) q=p-lchild; /*p 节点的祖先的左子女是其后序前驱*/ else q=null; /*仅右单枝树(p 是叶子)，已上到根节点，p 节点无后序前驱*/ return(q); 7解：二叉树是递归定义的，其运算最好采取递归方式。 算法如下： int height(bitree t) /*求二叉树 t 的深度*/ int hl, hr; if (t=null) return(0); else 附录 习题与练习解答 283 hl=height(t-lchild); hr=height(t-rchild); if(hlhr) return (hl+1); else return (hr+1); 8解：二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲节点与子女 节点编号间的关系，求下标为 i 和 j 的两节点的双亲，双亲的双亲，等等，直至找到最近的公 共祖先。 算法如下： void ancestor(int a , int n, int i, int j) /*二叉树顺序存储在数组 a1n中，本算法求下标分别为 i 和j 的节点的最近公共祖先节点的值。*/ if(in | jn) printf(“无效的 i 或 j!n“); while(i!=j) if (ij) i=i/2; /*下标为 i 的节点的双亲节点的下标*/ else j=j/2; /*下标为 j 的节点的双亲节点的下标*/ printf(“所查节点的最近公共祖先的下标是%d，值是%d“, i, ai); /*设元素类型整型。 */ 9解：叶子节点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱节点指针 pre，初始为空。第 1 个叶子节点由指针 head 指向，遍历到叶子节点时，就将它前驱的 right 指针指向它，最后一个叶子节点的 right 为空。 算法如下： void inorder(bitree /*中序遍历左子树*/ if(t-lchild=null pre=t; /*处理第 1 个叶子节点*/ else pre-rchild=t; pre=t; /*将叶子节点链入链表*/ inorder(t-rchild,head,pre); /*中序遍历左子树*/ 数据结构与算法 284 pre-rchild=null; /*设置链表尾*/ 10解：若使新插入的叶子节点 s 成为 t 右子树中序序列的第 1 个节点，则应在 t 的右 子树中最左面的节点(设为 p)处插入，使 s 成为节点 p 的左子女。则 s 的前驱是 t，后继是 p。 算法如下： void thrtreeinsert(bithrtree t, bithrtree s) /*在中序线索二叉树 t 的右子树上插入节点 s，使 s 成为 t 右子树中序遍历第 1 个节点*/ bithrtree p; p=t-rchild; /*用 p 去指向 t 的右子树中最左面的节点*/ while(p-ltag=0) p=p-lchild; s-ltag=1; s-rtag=1; /*s 是叶子，其左右标记均为 1*/ s-lchild=t; s-rchild=p; /*s 的前驱是根节点 t，后继是节点 p*/ p-lchild=s; p-ltag=0; /*将 p 的左子女指向 s ，并修改左标志为 0*/ 第 7 章 习题与练习解答 一、选择题答案 15：a、d、(b、d)、b、b 610：c、(a、b)、b、a、b 1115：a、b、a、a、d 二、基本知识题答案 1. 答：图是比树更为复杂的一种非线性数据结构，在图结构中，每个节点都可以和其他 任何节点相连接。 无向图：对于一个图 g，若边集合 e(g)为无向边的集合，则称该图为无向图。 有向图：对于一个图 g，若边集合e(g)为有向边的集合，则称该图为有向图。 子图：设有两个图 g=(v，e)和(,)gv e=，若()v g 是 v(g)的子集，即()( )v gv g , 且()e g 是 e(g)的子集，即()( )e ge g ，则称 g 是 g 的子图。 网络：有些图，对应每条边有一个相应的数值，这个数值称做该边的权。边上带权的图 称为带权图，也称为网络。 2. 答：顶点的度：图中与每个顶点相连的边数，称做该顶点的度。 路径：在一个图中，若从某顶点 p v出发，沿一些边经过顶点 1 v， 2 v， m v到达 q v， 则称顶点序列( p v， 1 v， 2 v， 3 v， m v， q v)为从 p v到 q v的路径。 连通图：在无向图中，若从顶点 i v到顶点 j v之间有路径，则称此二顶点是连通的。如果 图中任意一对顶点都是连通的，则称此图为连通图，否则为非连通图。 非连通图的连通分量：非连通图的每一个连通的部分称做连通分量。 附录 习题与练习解答 285 3. 答：图 g 所对应的邻接矩阵如下。 01010 1 10101 2 01010 3 10101 4 01010 5 = a 12354 图 g 所对应的邻接表如下： 2 4 2 4 2 4 1 3 5 1 3 5 1 2 3 4 5 4. 答：(a)所对应的无向图如图(a)所示，(b)所对应的有向图如图(b)所示。 a b c d b c d e a (a) (b) 5. 答：深度优先搜索得到的顶点访问序列：0、1、3、7、8、4、9、5、6、2； 广度优先搜索得到的顶点访问序列：0、1、2、3、4、5、6、7、8、9。 6. 答：该图的最小生成树如下。 1 1 2 2 7. 答：该有向图的拓扑排序序列为 3、1、4、5、2、6。 数据结构与算法 286 三、算法设计题答案 1. 解：该图对应的邻接表如下。 2 3 1 4 5 4 5 9 1 6 7 2 8 2 8 3 9 3 9 1 2 3 4 5 6 7 8 9 6 7 8 深度优先算法： void dfs(algraph int visitedmaxvernum; /记录顶点是否被访问 void dfstraverseal(algraph for(i=0;iadjvex=0) dfs(g,p-adjvex); /*从 v 的未访问过的邻接点出发进行深度优先搜索*/ p=p-next; 附录 习题与练习解答 287 2. 解：该图对应的邻接矩阵如下。 011000000 1 100110000 2 100001100 3 010000010 4 010000010 5 001000001 6 001000001 7 000110001 8 000001110 9 = a 123546789 广度优先算法： void bfs(mgragh mg, int v) /*以 v 为出发点，对图进行 bfs 遍历*/ int i,j; sqqueue sq; initqueue(sq); /*初始化队列*/ printf(“%d“, v); visitedv=1; enqueue(sq, v); /*入队*/ while(!queueempty(sq) /*判断队列是否为空*/ i=dequeue(sq); /*出队*/ for(j=0;jadjvex=d; p-next=ag.adjlists.firstedge; ag.adjlists.firstedge=p; 4. 解：实现本题功能的算法如下。 void deledge(algraph p=q=ag.adjlists.firstedge; if(p-adjvex=e) q=p-next; ag.adjlists.firstedge=q; free(p); else while(p!=null) if(p-adjvex=e) q-next=p-next; ag.adjlists.firstedge=q; free(p); break; else q=p; p=p-next; 附录 习题与练习解答 289 if(p=null) printf(“无此边,请确认您的输入正确!n“); return; p=q=ag.adjliste.firstedge; if(p-adjvex=s) q=p-next; ag.adjliste.firstedge=q; free(p); else while(p!=null) if(p-adjvex=s) q-next=p-next; ag.adjliste.firstedge=q; free(p); break; else q=p; p=p-next; 5. 解：实现本题功能的算法如下。 int countind(algraph ag, int v) /*求有向图中某点的入度*/ int i,count=0; edgenode * p; for(i=0;iadjvex=v-1) count+; break; else p=p-next; 数据结构与算法 290 return count; 6. 解：实现本题功能的算法如下。 (1) /*建立有向图的邻接表*/ void createalgraph(algraph edgenode *s; printf(“请输入顶点数和弧数(输入格式为:顶点数,弧数):n“); scanf(“%d,%d“, /*读入顶点数和弧数*/ getchar(); printf(“请输入顶点信息(输入格式为:顶点号):n“); for (i=0;iadjvex=j; /*邻接点序号为 j*/ s-next=ag.adjlisti.firstedge; /*将新弧表节点 s 插入到顶点 vi 的弧表头部*/ ag.adjlisti.firstedge=s; (2) void dfs(algraph visited v=1; num+; if(num=ag.n) printf(“%d 是有向图的根。n“,v); num=0; p=ag.adjlistv.firstedge; while (p) if (visitedp-adjvex=0) dfs (ag,p-adjvex,num); 附录 习题与练习解答 291 p=p-next; else p=p-next; void judgeroot(algraph ag,int num) static int i,j; for (i=0;iadjvex=0) dfs(ag, p-adjvex,visited); p=p-next; int connect(algraph ag) int i,flag=1; int visitedmaxvernum; for (i=0; iadjvex=0) dfs(ag, p-adjvex,visited); p=p-next; int getnum(algraph ag) int i,n=1; int visitedmaxvernum; for (i=0; i0) j-; if(inext; /*p 指向待插入的元素*/ while(p!=null) if(p-key = q-key) /*插到表首*/ p=p-next;q=q-next; else while(s!=qs=s-next; if(s=head) q-next=p-next; p-next=s; head=p; p=q-next; pre=s=head; else q-next=p-next; pre-next=p; p-next=s; pre=s=head; p=q-next; 3. 解：实现本题功能的算法如下。 void dbubblesort(seqlist r,int n) int i,j,flag; flag=1; i=1; while(flag!=0) flag=0; for(j=i;jrj+1.key) flag=1; r0=rj; 数据结构与算法 298 rj=rj+1; rj+1=r0; for(j=n-i;ji;j-) if(rj.keyrk.score) k=j; if(i!=k) /*与第 i 个记录交换*/ r0=ri; ri=rk; rk=r0; for(i=1; ip-key) p=p-next; else if(x=p-key) return p; else p=null; return p; 虽然链表中的节点是按递增顺序排列的，但是其存储结构为单链表，查找节点时只能从 头指针开始逐步进行搜索，不能用折半查找。 2. 解：采用顺序存储结构的算法如下，设记录存储在线性表的1n单元中。如果查找 成功，返回关键字为k的记录在线性表中的位置，如果失败则返回0。 int seqsearch(seqlist r,int n,int k) int i; i=1; while(ri.key!=k) else p=head; q=head-next; while(q!=null q=q-next; if(q!=null) x=p-key; p-key=q-key; q-key=x; q=p; return(q); 3. 解： 本题的算法思想： 首先计算要删除的关键字为k的记录所在的位置， 将其置为空(即 删除)，然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录，如果有则将 记录移到原来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下： void delete(seqlist r,int n,int k) int h,h0,h1,count=0; h=k%n; while(rh.key!=k free(p); /*p 无左子女*/ else /*用 p 左子树中的最大值代替 p 节点的值*/ 附录 习题与练习解答 305 q=p-lchild; s=q; while(q-rchild) s=q;q=q-rchild; /*查 p 左子树中序序列最右节点*/ if(s=p-lchild) /*p 左子树的根节点无右子女*/ p-key=s-key; p-lchild=s-lchild; free(s); else p-key=q-key; s-rchild=q-lchild; free(q); 6实现本题功能的函数如下。 typedef int keytype; /*关键字类型设为整型*/ typedef struct node /*节点类型*/ keytype key; /*关键字项*/ int count; /*计数项*/ struct node *lchild,*rchild; /*左右孩子指针*/ bstnode; void search_insertx(bstree t, int x) /*在二叉排序树 t 中查找值为 x 的节点，若查到，则其节点的 count 域值增 1，否则，将其插入到二 叉排序树中。*/ bstree p, f; p=t; while(p!=null if(p-keyrchild; else p=p-lchild; if(!p) /*没查找到值为 x 的节点，插入该节点*/ p=(bstree)malloc(sizeof (bstnode); p-key=x; p-l