2022年数据结构课后习题答案第二章 .pdf

《2022年数据结构课后习题答案第二章 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课后习题答案第二章 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章线性表 ( 参考答案 ) 在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define MAXSIZE 1024 typedef int ElemType;/ 实际上， ElemType可以是任意类型typedef struct ElemType dataMAXSIZE; int last; / last表示终端结点在向量中的位置sequenlist; （2）链式存储结构（单链表）typedef struct node ElemType data; struct node *next； linklist; （3）链式存储结构（双链表）typedef struct node

2、ElemType data; struct node *prior,*next；dlinklist; （4）静态链表typedef struct ElemType data; int next; node; node saMAXSIZE; 2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用， 所以链表的名字往往用头指针来标识。如：链表的头指针是 la，往往简称为“链表la” 。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品） ，其

3、指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。23 void insert(ElemType A,int elenum,ElemType x) / 向量 A目前有 elenum 个元素，且递增有序， 本算法将 x 插入到向量 A中，并保持向量的递增有序。 int i=0,j; while (ielenum & Ai=i;j-) Aj+1=Aj;/ 向后移动元素Ai=x; / 插入元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

4、- - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - / 算法结束24 void rightrotate(ElemType A,int n,k) / 以向量作存储结构，本算法将向量中的n 个元素循环右移 k 位，且只用一个辅助空间。 int num=0; / 计数，最终应等于n int start=0; / 记录开始位置（下标） while (numn) temp=Astart; /暂存起点元素值， temp与向量中元素类型相同 empty=start; /保存空位置下标 next=(start-K+n) %n; / 计算下一右移元素的下

5、标 while (next !=start) Aempty=Anext;/ 右移 num+; / 右移元素数加 1 empty=next; next=(next-K+n) %n; / 计算新右移元素的下标 Aempty=temp; / 把一轮右移中最后一个元素放到合适位置 num+; start+; / 起点增 1，若 numn则开始下一轮右移。 / 算法结束算法二算法思想：先将左面 n-k 个元素逆置， 接着将右面 k 个元素逆置， 最后再将这n 个元素逆置。void rightrotate(ElemType A,int n,k) / 以向量作存储结构，本算法将向量中的n 个元素循环右移 k

6、 位，且只用一个辅助空间。 ElemType temp; for(i=0;i(n-k)/2;i+) /左面 n-k 个元素逆置 temp=Ai; Ai=An-k-1-i; An-k-1-i=temp; for(i=1;i=k;i+) /右面 k 个元素逆置 temp=An-k-i; An-k-i=An-i; An-i=temp; for(i=0;inext, *pre=L，*s; / p为工作指针，指向当前元素，pre 为前驱指针，指向当前元素的前驱名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

7、 - - 第 2 页，共 6 页 - - - - - - - - - s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出s-data=x; while (p & p-datanext; / 查找插入位置 pre-next=s; s-next=p; / 插入元素 / 算法结束26 void invert(linklist *L) / 本算法将带头结点的单链表L 逆置。/ 算法思想是先将头结点从表上摘下，然后从第一个元素结点开始， 依次前插入以 L 为头结点的链表中。 linklist *p=L-next,*s; / p为工作指针，指向当前元素，s

8、为 p 的后继指针L-next=null;/头结点摘下，指针域置空。算法中头指针L 始终不变 while (p) s=p-next; / 保留后继结点的指针 p-next=L-next; / 逆置L-next=p; p=s; / 将 p 指向下个待逆置结点 / 算法结束27 (1) int length1(linklist *L) / 本算法计算带头结点的单链表L 的长度 linklist *p=L-next; int i=0; / p为工作指针，指向当前元素，i 表示链表的长度 while (p) i+; p=p-next; return(i); / 算法结束(2) int length1(

9、node saMAXSIZE) / 本算法计算静态链表s 中元素的个数。 int p=sa0.next, i=0; / p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1 时链表结束 while (p！=-1) i+; p=sap.next; return(i); / 算法结束28 void union_invert(linklist *A,*B,*C) / A和 B是两个带头结点的递增有序的单链表，本算法将两表合并成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3

10、 页，共 6 页 - - - - - - - - - / 一个带头结点的递减有序单链表C，利用原表空间。 linklist *pa=A-next,*pb=B-next,*C=A,*r; / pa,pb为工作指针，分别指向A表和 B表的当前元素， r 为当前逆置/ 元素的后继指针 , 使逆置元素的表避免断开。/ 算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。C-next=null;/头结点摘下，指针域置空。算法中头指针C始终不变 while (pa & pb) / 两表均不空时作 if (pa-datadata) / 将 A表中元素合并且逆置 r=pa-next; / 保留后

11、继结点的指针 pa-next=C-next; / 逆置C-next=pa; pa=r; / 恢复待逆置结点的指针 else / 将 B表中元素合并且逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置C-next=pb; pb=r; / 恢复待逆置结点的指针 / 以下 while (pa)和 while (pb)语句，只执行一个 while (pa) / 将 A表中剩余元素逆置 r=pa-next; / 保留后继结点的指针 pa-next=C-next; / 逆置C-next=pa; pa=r; / 恢复待逆置结点的指针 while (pb) / 将 B

12、表中剩余元素逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置C-next=pb; pb=r; / 恢复待逆置结点的指针 free(B);/释放 B表头结点 / 算法结束29 void deleteprior(linklist *L) / 长度大于 1 的单循环链表， 既无头结点， 也无头指针， 本算法删除 *s 的前驱结点 linklist *p=s-next,*pre=s; / p为工作指针，指向当前元素，/ pre为前驱指针，指向当前元素*p 的前驱 while (p-next!=s) pre=p; p=p-next; / 查找*s 的前驱 pr

13、e-next=s; free(p); / 删除元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - / 算法结束210 void one_to_three(linklist *A,*B,*C) / A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法 / 将 A表分成/ 三个带头结点的循环单链表A、B和 C ，分别含有字母、数字和其它符号的同一类字符，利用原表空间。 linklist *p=A-next,

14、r; / p为工作指针，指向A表的当前元素， r 为当前元素的后继指针 , 使表避免断开。/ 算法思想是取出当前元素， 根据是字母、 数字或其它符号， 分别插入相应表中。B=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 B-next=null; / 准备循环链表的头结点C=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 C-next=null; / 准备循环链表的头结点while(p) r=p-next; / 用以记住后继结点if (p-data= a&p-datadata= A& p-data

15、next=A-next; A-next=p; / 将字母字符插入 A表else if (p-data=0&p-datanext=B-next; B-next=p; / 将数字字符插入 B 表 else p-next=C-next; C-next=p;/ 将其它符号插入 C 表p=r; / 恢复后继结点的指针 /while / 算法结束211 void locate(dlinklist *L) / L是带头结点的按访问频度递减的双向链表，本算法先查找数据x, / 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。 linklist *p=L-next,*q; /p 为工作

16、指针，指向L 表的当前元素， q 为 p 的前驱，用于查找插入位置。 while (p & p-data !=x) p=p-next; / 查找值为 x 的结点。 if (!p) return (“不存在值为 x 的结点” ); else p-freq+; / 令元素值为 x 的结点的 freq 域加 1 。 p-next-prir=p-prior; / 将 p 结点从链表上摘下。 p-prior-next=p-next; q=p-prior; / 以下查找 p 结点的插入位置 while (q !=L & q-freqprior; p-next=q-next; q-next-prior=p;/ 将 p 结点插入 p-prior=q; q-next=p； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - / 算法结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -