数据结构的第4-7习题的答案.ppt

线性结构,操作受限的线性表：栈、队列线性结构线性表数据元素受限的线性表：串,线性表回顾,第四章线性表知识要点：1、线性表类型的定义：（a1,a2,an）2、线性表的存储形式：顺序存储和链式存储方式，以及各自的优缺点顺序存储：连续存储单元存储，分静态和动态2种链式存储：单链表、静态链表、双链表、循环链表3、线性表的应用：一元多项式相加,第四章习题,4.2请给出下述要求的判断条件：（1）以head为头指针、不带头结点的单链表为空的条件是什么？不为空的条件是什么？为空：head=NULL;不为空：head!=NULL;(2)以head为头指针、带头结点的单链表为空的条件是什么？不为空的条件是什么？为空：head-next=NULL;不为空：head-next!=NULL;(3)以head为头指针、不带头结点的单链环为空的条件是什么？不为空的条件是什么？为空：head=NULL;不为空：head!=NULL;(4)以head为头指针、带头结点的单链环为空的条件是什么？不为空的条件是什么？为空：head-next=head;不为空：head-next!=head;,4.2请给出下述要求的判断条件：（5）以head为头指针、不带头结点的单链表仅含有两个结点的条件是什么？head-next-next=NULL；(6)以head为头指针、带头结点的单链表仅含有两个结点的条件是什么？head-next-next-next=NULL；(7)以head为头指针、不带头结点的单链环仅含有两个结点的条件是什么？head-next-next=head；(8)以head为头指针、带头结点的单链环仅含有两个结点的条件是什么？head-next-next-next=head；,4.3在长度为n的顺序表上进行插入运算，有几个可插入的位置？在第i（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素？在长度为n的顺序表上进行删除运算，有几个可删除的数据元素？删除第i（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素？长度为n,有n+1个插入位置第i个位置上插入，需向右移动n-i+1个数据元素长度为n，有n个删除位置第i个位置上删除，需向左移动n-i个数据元素,4.4根据图示回答下面的问题：（1）如何访问p结点的数据域？P-data（2）如何访问p结点的直接前驱结点的数据域？P-prior-data（3）如何访问p结点的直接后继结点的数据域？P-next-data4.5对于以head为头指针的不带头结点的双链环而言，如何判断p指针所指结点是否为尾元结点？如何判断p指针所指结点是否为首元结点？对于以head为头指针的带头结点的双链环而言情况又如何？不带头结点判断尾元p-next?=head判断首元p?=head带头结点判断尾元p-next?=head判断首元p?=head-next,4.6若线性表中的数据元素以值递增有序排列（数据元素的类型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于min且小于max的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（说明：min和max是给定的两个参变量，可以设定为任意的整数值。）VoidDelete(LinkListhead)LinkListp,q;p=head;while(p-next!=NULL)if(p-next-datanext-datamin)q=p-next;p-next=q-next;free(q);elsep=p-next;,4.8若有一个以head为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以3，得余数0,1,2。试按这3种不同的情况，把原有的链表分解成3个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。,voiddecomposition(LinkListah,LinkList,4.9设有一个不带头结点的单链表，其结点的值均为整数，并按绝对值从小到大链接。试将该单链表改造为结点按绝对值从大到小进行链接。不允许另辟空间，写出一个算法实现上述要求。,head,p,q,r,q,p=NULL,r,r=NULL,q,p,Voidinvert(LinkList,4.10线性表有两种存储结构，即顺序表和单链表。试问：（1）若有N个线性表同时并存，且在处理过程中各表长度会动态发生变化，线性表的总数也会自动地改变，在此情况下应选用哪种存储结构？为什么？应采用链式存储结构，因为采用链式存储时插入删除操作不需要移动数据元素（2）若线性表的总数基本稳定，且很少进行插入和删除操作，但要以最快的速度存取表中元素，那么应采用哪种存储结构？为什么？应采用顺序存储结构，因为采用顺序存储时可以随机存取，提高存取表中元素的速度。,栈回顾,第五章栈知识要点：1、栈类型的定义：（a1,a2,an），只在栈顶进行插删操作，先进后出。2、栈的存储形式：顺序存储：链式存储：3、栈的应用：表达式求值,5.2设计一个算法，判断某输入字符串是否具有中心对称关系，例如ababbaba，baxzxab皆具有中心对称性（具有中心对称性的字符串称为回文）。思路：采用顺序栈解决。voidjudge()SqStackS;InitStack(,5.5已知函数F(n)=n+1当n=0时n*F(n/2)当n0时式中，n为正整数。写出它的递归算法。Intf(intn)if(n=0)return1;returnn*f(int(n/2);,5.8写出下列程序的输出结果。（说明：该程序中用到的栈S是数据元素为char类型的栈。）Voidmain()stackS;charx,y;InitStack(S);x=c;y=y;push(S,x);push(S,n);push(S,y);pop(S,x);push(S,a);push(S,x);pop(S,x);push(S,n);,While(!StackEmpty(S)pop(S,y);printf(“%c”,y);printf(“%c”,x);,结果：nancy,5.9已知一个栈S的输入序列为abcd，下面两个序列是否能通过栈的push和pop操作输出？如果能，请写出操作序列；如果不能，请说明原因。（x表示入栈，s表示出栈）（1）dbca；（2）cbda。（1）不能（2）xxxssxss,5.10写一个算法将给定十进制数转换为二进制数。voidconversion()initstack(s);/初始化一个空栈cinn;/输入要转换的十进制整数nwhile(n)/当n不为0时执行push(s,n%2);n=n/2;/余数进栈while(!stackempty(s)/当栈不为空时进行pop(s,e);coute;while(e!=ande!=#)push(s,e);cine;if(e=#)return0;cine;while(e!=#)if(StackEmpty(s)return0;pop(s,c);if(e!=c)return0;cine;if(!StackEmpty(s)return0;return1;/IsReverse,队列回顾,第六章队列知识要点：1、队列类型的定义：（a1,a2,an），只在队首进行删除操作，在队尾进行插入操作，先进先出。2、队列的存储形式：链式存储：顺序存储：循环队列,6.1循环队列的优点是什么？如何判别它的空和满？由于队列的顺序存储结构中从队尾入队、从队首出队，可能会造成存储空间实际未满，但又数据元素无法入队的情况，即虚溢出现象，而循环队列将整个队列看成一个环，则可以解决虚溢出问题。对于循环队列Q，其存储空间大小为MAXQSIZE，则：队空条件：Q.front=Q.rear队满条件：(Q.rear+1)%MAXQSIZE=Q.front6.2设长度为n的链队列用循环单链表表示，若只设头指针，则入列操作、出列操作实现的时间开销是多少？若只设尾指针呢？若只设头指针：入列、出列操作实现时间开销分别为O(n)和O(1)若只设尾指针：入列、出列操作实现时间开销分别为O(1)和O(1),6.4用两个栈实现一个队列，并分析你的算法的时间复杂度。思路：利用栈S1和S2模拟一个队列，其中S1栈用于插入元素，S2栈用于删除元素时辅助空间，每次删除元素时将S1栈的所有元素出栈并进栈到S2栈中。算法实现为：StatusEnQueue(stack时间复杂度T(n)=O(n),6.6简述下列算法的功能（假设栈和队列的元素类型均为int类型）。Voidalg(QueueQ)stackS;inte;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q,e);push(S,e);while(!StackEmpty(S)Pop(Q,e);EnQueue(S,e);实现功能：将队列Q逆置。,串回顾,第七章串知识要点：1、串类型的定义：“a1,a2,an”2、串的存储形式：顺序存储：堆存储：链式存储：块链结构,7.2已知：S1=”Imagirl.”，S2=”girl”，S3=”isverynice.”，试求下列各运算的结果：StrIndex(S1,S2);StrLength(S1);Concat(S,S2,S3)；答：StrIndex(S1,S2)=7StrLength(S1)=11Concat(S,S2,S3)=”girlisverynice.”,7.7将串的各字符均相同且长度大于1的子串称为该串的一个等值子串。试写算法实现：输入字符串S，以#为结束符；如果串S中不存在等值子串，则输出“无等值子串”，否则输出串S的一个长度最大的等值子串。如，若S=“abc345b6a7c”，则输出“无等值子串”；若S=“abcaaabbac”，则输出“aaa”。,voidEqSubString(chars)inti,j,k,head,max,count;printf(“请输入字符串：”);for(k=0;k+)/输入串scanf(“%c”,7.8试编写一个算法，将两个字符串S1和S2进行比较，若S1S2则输出一个正数；若S1=S2，则输出0；若S1next=Q.rear,5、栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是b,d,c,f,e,a则栈S的容量至少应该是_；,3,6、非空队列中，头指针始终指向_，而尾指针则始终指向队列_元素的_一个位置；,队列头元素尾下,7、栈和队列的共同特点是_；,只允许在端点处进行插入和删除元素,8、对不带头结点的链式队列，其队头指针指向队头结点，对尾指针指向队尾结点，则进行出队操作时队头指针_修改，对尾指针_修改，填写(要或不要或可能要)；,可能要可能要,三、阅读下列程序段，请说明这些程序段所描述的算法的功能。,(1)Statusalgol(stacks)(2)statusalgol2(stacks,inte)inti,n=0,a255;stackt;intd;while(!stackempty(s)initstack(t);n+;while(!stackempty(s)pop(s,an);pop(s,d);for(i=1;i2从栈T中出来后变为3y-*ay2/-的操作步骤。,XSXXXSSSXXSXXSXXSSSS,(1)Intcount(linklistHS)linklistp;p=HS;while(p)n+;p=p-next;return(n);,1、在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的算法；,五、根据题意要求回答问题。,2、为什么具有N个存储空间的循环队列满时整个队列只有N-1个元素？,(2)一般环状队列的头和尾其中之一要进行特殊处理，否则队空或满时只凭Q.rear=Q.front是无法判断的，一般处理方法是将Q.rear指向下一个要插入的位置，这样虽然牺牲了一个单元的存储空间，但很容易区分队列的空与满。,串补充习题,一、选择题（下列各小题均有一个答案是正确的）,1、串是一种特殊的线性表，其特殊性表现在()A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可要是多个字符2、空串与空格串之间的关系是()A、相等的B、不相等的C、等值的D、无法确定的3、设S=efghij则SubString(str,s,3,2)的值是()A、efB、ijC、hiD、gh4、S1=ABCDEFGS2=PQRST,则subs(S1,2,len(S2)A、BCDEFB、BCDEFGC、BCDED、CDEFG5、同上con(subs(S1,2,len(S2),subs(s1,len(S2),2)A、BCDEFEFB、BCDEFC、BCDEFGD、BCDPQRST,（）,B,D,D,A,A,（）,（）,（）,（）,二、填空题（请用正确答案填充下列空白）,1、设S1=GOOD,S2=,S3=BYE!则con(con(S1,S2),S3)=_2、两个串相等的充分必要条件是：_3、S1=ABCDEFG,S2=9898,S3=#,S4=012345,则Substr(M,S1,4,len(S3)=_,Replace(S1,M,S3)=_,PP=index(s2,8)=_,Substr(H,S4,pp,len(S2)=_,Con(S1,H)=_,GOOD