2023年《数据结构—用C语言描述》课后习题超详细解析答案.pdf
《2023年《数据结构—用C语言描述》课后习题超详细解析答案.pdf》由会员分享,可在线阅读,更多相关《2023年《数据结构—用C语言描述》课后习题超详细解析答案.pdf(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、优秀学习资料 欢迎下载 数据结构课后习题参考答案 第一章 绪论 1.3 (1)O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中,x,y 值变化如下:循环次数 x y 0(初始)91 100 1 92 100 2 93 100 9 100 100 10 101 100 11 91 99 12 92 100 20 101 99 21 91 98 30 101 98 31 91 97 到 y=0 时,要执行 10*100 次,可记为 O(10*y)=O(n)1.5 2100,(2/3)n ,log2n ,n1/2 ,n3/2 ,(3/2)n ,
2、nlog2n,2 n ,n!,n n 第二章 线性表(参考答案)在以下习题解答中,假定使用如下类型定义:(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 st
3、ruct node ElemType data;struct node *prior,*next;dlinklist;(4)静态链表 typedef struct ElemType data;int next;优秀学习资料 欢迎下载 node;node saMAXSIZE;2.1 头指针:指向链表的指针。因为对链表的所有操均需从头指针开始,即头指针具有标识链表的作用,所以链表的名字往往用头指针来标识。如:链表的头指针是 la,往往简称为“链表 la”。头结点:为了链表操作统一,在链表第一元素结点(称为首元结点,或首结点)之前增加的一个结点,该结点称为头结点,其数据域不无实际意义(当然,也可以存
4、储链表长度,这只是副产品),其指针域指向头结点。这样在插入和删除中头结点不变。开始结点:即上面所讲第一个元素的结点。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;/插入元素 /算法结束 24 void rightrotate(ElemType A,int n,k)/以向
5、量作存储结构,本算法将向量中的 n 个元素循环右移 k 位,且只用一个辅助空间。int num=0;/计数,最终应等于 n int start=0;/记录开始位置(下标)while(numn)temp=Astart;/暂存起点元素值,temp 与向量中元素类型相同 empty=start;/保存空位置下标 next=(start-K+n)%n;/计算下一右移元素的下标 while(next!=start)Aempty=Anext;/右移 num+;/右移元素数加 1 empty=next;next=(next-K+n)%n;/计算新右移元素的下标 Aempty=temp;/把一轮右移中最后一个
6、元素放到合适位置 num+;start+;/起点增 1,若 numn则开始下一轮右移。/算法结束 算法二 算法思想:先将左面 n-k 个元素逆置,接着将右面 k 个元素逆置,最后再将这 n 个元素逆置。void rightrotate(ElemType A,int n,k)/以向量作存储结构,本算法将向量中的 n 个元素循环右移 k 位,且只用一个辅助空间。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
7、;An-k-i=An-i;An-i=temp;for(i=0;inext,*pre=L,*s;/p为工作指针,指向当前元素,pre 为前驱指针,指向当前元素的前驱 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
8、=L-next,*s;/p为工作指针,指向当前元素,s 为 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 len
9、gth1(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 是两个带头结点的递增有序的单链表,本算法将两表合并成 /一个带头结点的递减有序单链表 C,利用原表空间。linklist*pa=A-next,*pb=B-next,*C=A,*r;型链式存储结构单链表链式存储结构双链表静态链表表
10、示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载/pa,pb 为工作指针,分别指向 A表和 B表的当前元素,r 为当前逆置/元素的后继指针,使逆置元素的表避免断开。/算法思想是边合并边逆置,使递增有序的单链表合并为递减有序的单链表。C-next=null;/头结点摘下,指针域置空。算法中头指针 C 始终不变 while(pa&pb)/两表均不空时作 if(pa-datadata)/将 A表中元素合并且逆置 r=pa-next;/保留后继结点的指针 pa-next=C-next;/逆置
11、 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表中剩余元素逆置 r=pb-next;/保留后继结点的指针 pb-next=C-next;/逆置 C-
12、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-ne
13、xt!=s)pre=p;p=p-next;/查找*s 的前驱 pre-next=s;free(p);/删除元素 /算法结束 210 void one_to_three(linklist*A,*B,*C)/A是带头结点的的单链表,其数据元素是字符字母、字符、数字字符、其他字符。本算法/将 A表分成 /三个带头结点的循环单链表 A、B和 C,分别含有字母、数字和其它符号的同一类字符,利用原表空间。linklist*p=A-next,r;/p为工作指针,指向 A表的当前元素,r 为当前元素的后继指针,使表避免断开。/算法思想是取出当前元素,根据是字母、数字或其它符号,分别插入相应表中。B=(link
14、list*)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 next=A-next;A-next=p;/将字母字符插入 A表 else if(p-data=0&p-datanext=B-next;B-next=p;/将数字字符插入 B 表 else p-next=
15、C-next;C-next=p;/将其它符号插入 C 表 p=r;/恢复后继结点的指针 /while /算法结束 211 void locate(dlinklist*L)/L是带头结点的按访问频度递减的双向链表,本算法先查找数据 x,/查找成功时结点的访问频度域增 1,最后将该结点按频度递减插入链表中适当位置。linklist*p=L-next,*q;/p 为工作指针,指向 L表的当前元素,q 为 p 的前驱,用于查找插入位置。while(p&p-data!=x)p=p-next;/查找值为 x 的结点。if(!p)return(“不存在值为x 的结点”);else p-freq+;/令元素值
16、为 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;/算法结束 第三章 栈和队列(参考答案)型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料
17、欢迎下载/从数据结构角度看,栈和队列是操作受限的线性结构,其顺序存储结构 /和链式存储结构的定义与线性表相同,请参考教材,这里不再重复。3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1 1 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 1 1 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 设入栈序列元素数为 n,则可能的出栈序列数为 C2nn=(1/n+1)*(2n!/(n!)2)3.2 证明:由 jk 和 pjpk 说明 pj在 pk之前出栈,即在 k 未进栈之前 pj已出栈,之后 k 进栈,然后 pk出栈;由 j
18、pk 说明 pj在 pk之后出栈,即 pj被 pk 压在下面,后进先出。由以上两条,不可能存在 ijk 使 pjpknext;while(idata);p=p-next;if(n%2!=0)p=p-next;/奇数个结点时跳过中心结点 while(p&p-data=pop(s)p=p-next;if(p=null)printf(“链表中心对称”);else printf(“链表不是中心对称”);/算法结束 3.4 int match()/从键盘读入算术表达式,本算法判断圆括号是否正确配对(init s;/初始化栈 s scanf(“%c”,&ch);while(ch!=#)/#是表达式输入结束
19、符号 switch(ch)case(:push(s,ch);break;case):if(empty(s)printf(“括号不配对”);exit(0);pop(s);if(!empty(s)printf(“括号不配对”);else printf(“括号配对”);/算法结束 3.5 typedef struct /两栈共享一向量空间 ElemType vm;/栈可用空间 0m-1 int top2 /栈顶指针 twostack;int push(twostack*s,int i,ElemType x)/两栈共享向量空间,i 是 0 或 1,表示两个栈,x 是进栈元素,/本算法是入栈操作 if(
20、abs(s-top0-s-top1)=1)return(0);/栈满 else switch(i)case 0:s-v+(s-top)=x;break;case 1:s-v-(s-top)=x;break;型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 default:printf(“栈编号输入错误”);return(0);return(1);/入栈成功 /算法结束 ElemType pop(twostack*s,int i)/两栈共
21、享向量空间,i 是 0 或 1,表示两个栈,本算法是退栈操作 ElemType x;if(i!=0&i!=1)return(0);/栈编号错误 else switch(i)case 0:if(s-top0=-1)return(0);/栈空 else x=s-vs-top-;break;case 1:if(s-top1=m)return(0);/栈空 else x=s-vs-top+;break;default:printf(“栈编号输入错误”);return(0);return(x);/退栈成功 /算法结束 ElemType top(twostack*s,int i)/两栈共享向量空间,i 是
22、 0 或 1,表示两个栈,本算法是取栈顶元素操作 ElemType x;switch(i)case 0:if(s-top0=-1)return(0);/栈空 else x=s-vs-top;break;case 1:if(s-top1=m)return(0);/栈空 else x=s-vs-top;break;default:printf(“栈编号输入错误”);return(0);return(x);/取栈顶元素成功 /算法结束 36 void Ackerman(int m,int n)/Ackerman 函数的递归算法 if(m=0)return(n+1);else if(m!=0&n=0)
23、return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1)/算法结束 37(1)linklist *init(linklist*q)/q是以带头结点的循环链表表示的队列的尾指针,本算法将队列置空 q=(linklist*)malloc(sizeof(linklist);/申请空间,不判断空间溢出 q-next=q;return(q);/算法结束 (2)linklist *enqueue(linklist*q,ElemType x)/q是以带头结点的循环链表表示的队列的尾指针,本算法将元素 x 入队 s=(linklist*)m
24、alloc(sizeof(linklist);/申请空间,不判断空间溢出 s-next=q-next;/将元素结点 s 入队列 q-next=s;q=s;/修改队尾指针 型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 return(q);/算法结束 (3)linklist *delqueue(linklist*q)/q 是以带头结点的循环链表表示的队列的尾指针,这是出队算法 if(q=q-next)return(null);/判断队列
25、是否为空 else linklist*s=q-next-next;/s指向出队元素 if(s=q)q=q-next;/若队列中只一个元素,置空队列 else q-next-next=s-next;/修改队头元素指针 free(s);/释放出队结点 return(q);/算法结束。算法并未返回出队元素 3.8 typedef struct ElemType datam;/循环队列占 m个存储单元 int front,rear;/front和 rear 为队头元素和队尾元素的指针 /约定 front指向队头元素的前一位置,rear 指向队尾元素 sequeue;int queuelength(se
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构用C语言描述 2023 数据结构 语言 描述 课后 习题 详细 解析 答案
限制150内