《算法与数据结构C语言习题参考答案1-5章》由会员分享，可在线阅读，更多相关《算法与数据结构C语言习题参考答案1-5章（22页珍藏版）》请在金锄头文库上搜索。
1、1.绪绪 论论1将下列复杂度由小到大重新排序： A2nBn!Cn5D10 000En*log2 (n)【答】10 000n = palist- MAXNUM ) /* 溢出 */printf(“Overflow!n”);return 0; if (ppalist-n-1 ) /* 不存在下标为 p 的元素 */printf(“Not exist! n”); return 0; for(q=palist-n - 1; q=p+1; q-) /* 插入位置及之后的元素均后移一个位置 */palist-elementq+1 = palist-elementq; palist-elementp+1 =
2、 x;/* 插入元素 x */palist-n = palist-n + 1;/* 元素个数加 1 */return 1;2 试写一个删除算法 deleteV_seq(palist, x )，在 palist 所指顺序表中，删除一个值为 x 的元素，返回删除成功与否的标志。【答】数据结构 采用 2.1.2 节中顺序表定义。int deleteV_seq(PseqList palist, p, DataType x ) /* 在 palist 所指顺序表中删除值为 x 的元素 */int p,q; for(p=0;pelementp)for(q=p; qn-1; q+) /* 被删除元素之后的元
3、素均前移一个位置 */palist-elementq = palist-elementq+1;palist-n = palist-n - 1;/* 元素个数减 1 */return 1 ;return 0;3. 设有一线性表 e = (e0, e1 , e2 , , en1 )，其逆线性表定义为 e= (en1 , , e2 , e1 ,e0)。 请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的 空间。【答】数据结构采用 2.1.2 节中顺序表的定义。思路思路考虑对数组 element 进行置逆，即把第一个元素和最后一个元素换位置，把第二个元素和倒数第二个元素换位置。
4、注意注意这种调换的工作只需对数组的前一半元素进行，所以设置整数变量 count 用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进行如上的对元素“换位置”的工作？（提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。 ）顺序表的置逆算法void rev_seq(PSeqList palist)DataType x;int count, i; if (palist-n = 0 | palist-n = 1) return;/*空表或只有一个元素，直接返回*/count = palist-n / 2; for ( i = 0; i elementi;palist-e
5、lementi = palist-elementpalist-n 1 i;palist-elementpalist-n 1 i = x;代价分析该算法中包含一个 for 循环，其循环次数为 n/2。因此，算法的时间代价为 O(n)。4. 已知长度为 n 的线性表 A 采用顺序存储结构，请写一算法，找出该线性表中值最小 的数据元素。 【答】数据结构 采用 2.1.2 节中顺序表定义。思路 设置变量 min，遍历整个表，不断更新当前已经经历过的元素的最小值即可。为方便起见，事先假设表不为空。算法DataType min_seq(PSeqList palist)/*求非空顺序表中的最小数据元素*/D
6、ataType min;int i;min = palist-element0; /*初始化 min*/for ( i = 1; i n; i+) /*min 中保存的总是当前的最小数据*/if (min palist-elementi)min = palist-elementi;return min;代价分析 该算法访问顺序表中每个元素各一次，时间代价为 O(n)。 讨论讨论读者可以试图对上面的算法进行修改，使返回的值不是最小元素的值而是它的下标。5. 已知线性表 A 的长度为 n，并且采用顺序存储结构。写一算法，删除线性表中所有 值为 x 的元素。 【答】数据结构 采用 2.1.2 节中顺
7、序表的定义。思路 为了减少移动次数，可以采用快速检索的思想，用两个变量 i, j 记录顺序表中被处理的两端元素的下标，开始时 i = 0，j = n1，边检索第 i 个元素边增加 i，直到找到一个元素值等于 x，再边检索第 j 个元素边减少 j，直到找到一个元素值不等于 x，把下标为 j 的元素移到下标为 i 的位置后重复上述过程，直到 i j。另用一变量 count 记录删除了多少个元素。算法void delx_seq(PSeqList p, DataType x) /*删除顺序表中所有值为 x 的元素，新顺序表可能不保持原有顺序*/int i = 0, j = p-n 1, count =
8、 0;/*i 定位于顺序表开始处，j 定位于顺序表最后*/while ( i elementi = x) /*找到了一个要删除的元素*/while (p-elementj = x) count+;if ( i = = j) p-n = p-n count 1;return;elsep-elementi = p-elementj;count+;j ;i+;p-n = p-n count;if (p-elementi = x) pn ;代价分析 该算法访问顺序表中每个元素各一次，时间代价为 O (n)。 讨论讨论这个算法使用了一点技巧使得在中间删除元素时，避免了最后一串元素的移动。但是，它破坏了原
9、来线性表中元素之间的顺序关系。如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表，如果元素不是 x，则继续向后；如果元素是 x，则寻找其后第一个不是 x 的元素，将这两个元素互换。具体算法请读者自己实现。6.写一算法，在带头结点的单链表 llist 中，p 所指结点前面插入值为的新结点，并返 回插入成功与否的标志。【答】数据结构 采用 2.1.3 节中单链表定义。思想： 由于在单链表中，只有指向后继结点的指针，所以只有首先找到 p 所指结点的前驱结点， 然后才能完成插入。而找 p 所指结点的前驱结点，只能从单链表的第一个结点开始，使用 与 locate_link 类似的方
10、式进行搜索。 算法：int insertPre_link(LinkList llist,PNode p,DataType x)/* 在 llist 带头结点的单链表中，p 所指结点前面插入值为 x 的新结点 */PNode p1;if(llist=NULL) return 0; p1=llist;while(p1!=NULL /*寻找 p 所指结点的前驱结点*/if(p1=NULL) return 0;PNode q=(PNode)malloc(sizeof(struct Node);/*申请新结点*/if(q=NULL) printf(“Out of space!n”);return 0;q
11、-info=x;q-link=p1-link;p1-link=q;return 1;7.写一算法，在带头结点的单链表 llist 中,删除 p 所指的结点，并返回删除成功与否的 标志。【答】数据结构 采用 2.1.3 节中单链表定义。思想： 由于在单链表中，只有指向后继结点的指针，所以只有首先找到 p 所指结点的前驱结点， 然后才能完成删除。而找 p 所指结点的前驱结点，只能从单链表的第一个结点开始，使用 与 locate_link 类似的方式进行搜索。int deleteP_link(LinkList llist,PNode p) /* 在 llist 带头结点的单链表中，删除 p 所指的结
12、点 */PNode p1;if(llist=NULL)return Null; p1=llist; while(p1!=NULL /*寻找 p 所指结点的前驱结点*/if(p1=NULL)return 0;p1-link=p-link;free(p); /* 删除结点 p */return 1;8. 已知 list 是指向无头结点的单链表的指针变量，写出删除该链表下标为 i 的（第 i+1 个）结点的算法。 【答】数据结构 采用 2.1.3 节中单链表定义。思路 依次遍历表中的每一个结点并计数，到第 i+1 个结点时实行删除。由于链表是无头结点的，所以在删除第一个结点时要特别注意。算法int
13、deleteindex_link_nohead(LinkList * pllist, int i) /*删除单链表中下标为 i 的结点。删除成功返回 TRUE，否则返回 FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i link;free(q);return TRUE;p = (*pllist);j = 0; while (p-link != NULL j+; if (p-link = NULL) return FALSE;/*此元素不存在*/q = p-link;p-link = q-link;free(q);return TRUE;代价分析
14、该算法访问单链表中前面 i 个结点，时间代价为 O(i)，最大不超过 O(n)。 讨论讨论如果函数参数不是 LinkList *类型而是 LinkList 类型，在删除 i=0 的结点时，程序不能正确实现，其原因请读者思考（考虑 C 语言的参数传递方式） 。如果单链表带表头结点，重写本题的算法。比较这两个算法，是否能体会到表头结点的作用。9. 已知 list 是指向无头结点的单链表的指针变量，写出删除该链表中从下标为 i 的 （第 i+1 个）结点开始的连续 k 个结点的算法。 【答】数据结构 采用 2.1.3 节单链表定义。思路 这道题与上题相似，只需要增加计数即可。要注意的是应该判断给出的
15、 i 和 k 是否合理，是不是会超出链表长度。算法int del_link_nohead(LinkList * pllist, int i, int k) /*删除单链表中从下标 i 开始的 k 个结点。删除成功返回 TRUE，否则返回 FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i link;free(q);return TRUE;p = (*pllist);j = 0; while ( p-link != NULL j+; if (p-link = NULL) return FALSE;/*第 i 个结点不存在*/for ( j = 0; j link != NULL; j+) q = p-link;p-link = q-link;free(q);return TRUE;代价分析 该算法访问单链表中前面 i+k 个结点，时间代价为 O(i+k)，最大不超过 O(n)。13. 请设计一个算法，求出循环表中结点的个数。【答】数据结构采用不带头结点的循环链表。struct Node;typedef struct Node * PNode;struct NodeDataType info;PNode link;typedef struct Node * LinkList;思路遍历整个循环链
