c语言第三章习题答案,数据结构(C语言版)习题集答案第三章.doc_weixin_39935092的博客-程序员宝宝

技术标签: c语言第三章习题答案  

数据结构(C语言版)习题集答案第三章.doc

习题三3.1 3.10 3.13 3.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.51 给定操作序列P1P2P3PiPn(Pk为S或X,k1,2,n )是合法的,当且仅当满足下列条件a. 序列中包含的S的个数和X的个数相等;b. 对于任意的j(1jn);有P1P2P3Pj子序列中所包含的S的个数大于等于X的个数;2证明设P1P2P3PiPn ,Q1Q2Q3QiQn是两个不同的合法序列; 两者不同, kmini| PiQi , 1in 且k1, PkQk (因P1 ,Q1肯定是S,否则不合法) 即,P1P2P3Pk-1 和Q1Q2Q3Qk-1是相等的,但PkQk由此可知两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同,由于PkPk不妨设PkX,而QkS;这样,在操作序列P1P2P3PiPn中的第k-1步后输出的第一个元素是目前栈中的元素,而对于操作序列Q1Q2Q3QiQn中的第k-1步后输出的第一个元素是目前还在栈外的元素。所以输出序列不同。即两个不同的合法操作序列,不可能得到相同的输出序列。证毕3.6 用反证法证明假设存在这样的输出序列,P1PiPjP kPn ,满足ijk,使PjPkPi ;因Pi在这三个数中最大,且Pi最先出栈,按照题意所给进栈顺序,在Pi出栈时Pj和P k都还在栈中;又因,PjP k ,所以Pj比P k先进栈,则出栈顺序应该是P k先出栈而不是Pj先出栈,矛盾证毕3.10 1 输出序列为0,5,9,12,14,152 由于输入的数据个数不定,采用单链表存储输入的元素,又因是先输入的,后累加到累加器里,所以用链栈的形式存储。(类型定义与书本上第二章相同)void test LinkList L ,P; int x,sum; LNULL; 建立空链表sum0; printfsum; scanfx;读入第一个数 whilex PLinkListmallocsizeofLNode;产生一个结点 P-datax; P-nextL; LP;插入在链头 scanfx;读下一个数 whileL sumsumL-data;取值累加 printfsum;输出 PL-next; freeL; LP; 3.15 所用类型定义如下define Stack_Init_Size 100typedef struct stack SElemType base0,base1,*top0,*top1; int StackSize ; DuSqStack;void InistackDuSqStack tws tws.base0 SElemType*mallocStack_Init_Size*sizeofSElemType; iftws.base0 exitOVERFLOW; tws.top0 tws.base0; tws.base1tws.top1tws0.base0 Stack_Init_Size-1; tws.StackSize Stack_Init_Size; InistackStatus Push DuSqStack tws ,int i , SElemType x将元素x插在第i个栈中if tws.top0tws.top1 return OVERFLOW;switchicase 0 *tws.top0x; tws.top0;break;case 1 *tws.top1x; tws.top1;break;return OK; PushStatus Pop DuSqStack tws ,int i , SElemType x将第i个栈的栈顶元素弹出,由x带回switchicase 0 iftws.base0tws.top0 return ERROR; x*tws.top0;break;case 1 iftws.base1tws.top1 return ERROR; x*tws.top0;break;return OK; Pop3.17Status judge 判断输入的字符序列是否为型如序列1序列2,其中序列2是序列1的逆序列InitStackS; 初始化栈Scgetchar ;读第一个字符whilec c pushs,c; cgetchar ;ifc return FALSE;cgetchar ;读下一个whilec EmptyStacks pops,e; ifce return FALSE; cgetchar ;ifc EmptyStacks return TRUE;return FALSE; judge3.19Status judgedSqList LL为数据元素类型为字符的顺序存储的线性表,表示一个表达式,判断该表达式的括号是否匹配InitStackS;初始化栈Sforj0;jL.length;j switchL.elemj case case case pushS, L.elemj ;break; case case case ifEmptyStackS return FALSE; else PopS,e; switchL.elemj case ife return FALSE;break; case ife return FALSE;break; case ife return FALSE;break; ifEmptyStackS return TRUE;else return FALSE; judged3.24 int gint m,int n 不考虑输入参数的非法性ifm0 n0 return 0;else ifm0 n0 return gm-1,2*nn; g329 类型定义define MAX_Init_Size 100typedef struct QElemType *base; int front,rear ,tag; SqQueue;Status InitQueueSqQueue Q 初始化一个队列Q.base QelemType* mallocMAX_Init_Size*sizeofQelemType;IfQ.base exitOVERFLOW;G.frontQ.rearQ.tag0;表示队列为空return OK; InitQueueStatus EnQueueSqQueue Q , QelemType x将元素x入队列, 若队列满则返回函数值ERROR,否则返回OKifQ.frontQ.rearQ.tag1 return ERROR;Q.baseQ.rearx;Q.rearQ.rear1MAX_Init_Size;ifQ.frontQ.rear Q.tag1;尾指针追上头指针return OK; EnQueueStatus DelQueueSqQueue Q , QelemType x删除队头元素,让x带回,若队列为空则返回函数值ERROR,否则返回OKifQ.frontQ.rearQ.tag0 return ERROR;xQ.baseQ.front;Q.front Q.front1 MAX_Init_Size;ifQ.frontQ.rear Q.tag0;头指针追上尾指针return OK;DelQueue3.31Status Ispalindrome 判断输入的字符序列是否为回文,是返回TRUE ,否则返回FALSEInitStackS; 初始化栈SInitQueueQ;初始化一个队列Qcgetchar ;读第一个字符whilec pushS,c; 入栈EnQueueQ,c;入队列cgetchar ;whileEmptyStackS PopS,e; DelQueueQ,c; ifce return FALSE;return TRUE; Ispalindrome3.24 Status gint m,int n,int s求递归函数g的值sifm0n0 s0;else ifm0n0 sngm-1,2*n;else return ERROR;return OK;g 3.29 Status EnCyQueueCyQueue Q,int x带tag域的循环队列入队算法ifQ.frontQ.rearQ.tag1 tag域的值为0表示空,1表示满return OVERFLOW;Q.baseQ.rearx;Q.rearQ.rear1MAXSIZE;ifQ.frontQ.rear Q.tag1; 队列满EnCyQueue Status DeCyQueueCyQueue Q,int x带tag域的循环队列出队算法ifQ.frontQ.rearQ.tag0 return INFEASIBLE;Q.frontQ.front1MAXSIZE;xQ.baseQ.front; ifQ.frontQ.rear Q.tag1; 队列空return OK;DeCyQueue分析当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39935092/article/details/117042109

智能推荐

Oracle 11g 测试ogg中断之后,重新同步操作_weixin_33831673的博客-程序员宝宝

测试ogg中断之后,重新同步操作2018-06-07 17:11 779 1 原创 GoldenGate 本文链接:https://www.cndba.cn/leo1990/article/28391.测试ogg中断之后,重新同步操作1.1.关闭源端抽取进程GGSCI (cndba) 65> info allProgram Status Grou...

hdu1106 排序(字符串分割,strtok+sscanf)_baizhen6460的博客-程序员宝宝

排序Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 75271Accepted Submission(s): 23079Problem Description输入一行数字,如果我们把这行数字中的‘5’都看成空格...

QT 生成.so动态库默认生成.so .so.1 .so.1.0 .so.1.0.0_gjh_helloworld的博客-程序员宝宝_.so .so.1.0.0

QT 生成.so动态库时,会默认生成.so .so.1 .so.1.0 .so.1.0.0四个文件,其中其他三个文件都是指向.so.1.0.0这个实际的库文件的链接文件,为了版本控制。要想直接生成.so作为实际库文件,可以在.pro工程文件中添加CONFIG += plugin项。...

Android系统移植与调试之------->如何修改Android设备添加重启、飞行模式、静音模式等功能(二)..._iteye_7514的博客-程序员宝宝

今天要说的是为Android设备添加重启、飞行模式、静音模式按钮,客户需求中需要添加这项功能,在长按电源键弹出的菜单中没有这些选项,谨以此文记录自己添加这个功能的过程。首先找到长按电源键弹出的对话框,在frameworks\base\policy\src\com\android\internal\policy\impl\GlobalActions.java文件中,修改createDialog(...

杨辉三角的重要结论_Error Man的博客-程序员宝宝_杨辉三角结论

第n行的m个数可表示为C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。 第n行的第m个数和第n-m+1个数相等 ,为组合数性质之一。 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即C(n+1,i)=C(n,i)+C(n,i-1)。 (a+b...

外媒测评iPhone新机:性能卓越,但续航令人失望_网易智能的博客-程序员宝宝

尽管苹果iPhone 12和iPhone 12 Pro即将于10月23日正式开售,但许多媒体已经抢先拿到样机,并对它们进行了测评。今年新款iPhone最大卖点就是支持5G,同时在性能、显...

随便推点

Udesk API v2 使用介绍(一)_udesk小能手的博客-程序员宝宝

作者:张振琦Udesk提供了两个版本的API供用户使用,API v1和API v2。官方推荐使用API v2,今天就来说说API v2的接口如何使用。API v2 提供了客户接口、工单接口、客户公司接口、呼叫中心接口、即时通讯接口、呼叫中心监控接口等等,具体的url和参数大家可以参考Udesk官网:https://www.udesk.cn/doc/apiv2/intro/使用 Udesk 开放接口(v2),需要遵循以下规则:1.API默认的频次限制为 60次/分钟,所以任何API在1分钟内最多.

python中文字符串多余空格_python使用正则表达式去除中文文本多余空格,保留英文之间空格方法详解..._weixin_40004960的博客-程序员宝宝

python使用正则表达式去除中文文本多余空格,保留英文之间空格方法详解在pdf转为文本的时候,经常会多出空格,影响数据观感,因此需要去掉文本中多余的空格,而文本中的英文之间的正常空格需要保留,输入输出如下:input:我今天 赚了 10 个亿,老百姓very happy。output:我今天赚了10个亿,老百姓very happy。代码def clean_space(text):""""处理多余...

浪潮天梭服务器装系统步骤,浪潮天梭TS10000高性能主机系统配置方案.DOC_香菜浪味仙的博客-程序员宝宝

浪潮天梭TS10000高性能主机系统配置方案浪潮天梭TS10000高性能主机系统配置方案部件名称部件型号技术规格数量 机柜系统基础模块TS422019″、42U工业标准机柜、天梭高性能服务器专用机柜;1个承重托盘,支持并柜,含布线系统,散热系统,供电系统1TS10K配件包TS10000配件包,每机柜必配一套1TS10K配件盒TS10000配件盒,(含键盘鼠标)每项目必配一套1PDU-4040个电...

使用领域模型(domain object)来进行索引、搜索_GoodtigerZhao的博客-程序员宝宝

对于讲domain object 映射到关系型数据库中,hibernate等持久性框架做了很多的工作,使得业务逻辑只需要和hibernate等持久层进行交互,而不需要直接和具体的数据库进行交互。这给程序员带来了很大的方便,在业务逻辑处理上,只要针对domain object就可以。使用Lucene进行索引、搜索开发的的时候,最经常碰到的概念就是Document 和Field,在程序中一个不得...

使用IIS在Windows上托管ASP.NET Core(本文仅针对Window服务器)_Fantastic_HQ的博客-程序员宝宝

使用IIS在Windows上托管ASP.NET Core(仅针对服务器)博文背景: 最近有点想用.Net Core进行做毕业设计,于是在阿里云买了一台云服务器,学生价一折超级便宜(看着它提示毕业以后就要恢复原价,要毕业了好心酸呀QWQ),现在是10元一月,博主觉得阿里云最好的在于服务器可以随时更换镜像(0成本快速更换window->Linux),而且服务器网速超级快,基本滿足日常的使用。注意事项:

ajax默认提交请求,默认是同步还是异步,怎么改成同步_余生逆风飞翔的博客-程序员宝宝_ajax默认是同步还是异步

默认提交方式是异步提交,这样做的好处就是能够通过局部刷新的方式提高用户的体验,同时还能节省资料,减少数据库的压力,改成同步的方法就是将async的默认值改成false,一般都是true或者不写,如果改成false就会失去ajax的本身作用...

推荐文章

热门文章

相关标签