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

《数据结构的第4-7习题的答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性结构操作受限的线性表：栈、队列线性结构→线性表→数据元素受限的线性表：串线性表回顾第四章线性表知识要点：1、线性表类型的定义：（a1,a2,…,an）2、线性表的存储形式：顺序存储和链式存储方式，以及各自的优缺点顺序存储：连续存储单元存储，分静态和动态2种链式存储：单链表、静态链表、双链表、循环链表3、线性表的应用：一元多项式相加第四章习题4.2请给出下述要求的判断条件：（1）以head为头指针、不带头结点的单链表为空的条件是什么？不为空的条件是什么？为空：head==NULL;不为空：head

2、!=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请给出下述要求的判断

3、条件：（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

4、在长度为n的顺序表上进行插入运算，有几个可插入的位置？在第i（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素？在长度为n的顺序表上进行删除运算，有几个可删除的数据元素？删除第i（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素？长度为n,有n+1个插入位置第i个位置上插入，需向右移动n-i+1个数据元素长度为n，有n个删除位置第i个位置上删除，需向左移动n-i个数据元素4.4根据图示回答下面的问题：（1）如何访问p结点的数据域？P->data（2）如何访问p结点的

5、直接前驱结点的数据域？P->prior->data（3）如何访问p结点的直接后继结点的数据域？P->next->data4.5对于以head为头指针的不带头结点的双链环而言，如何判断p指针所指结点是否为尾元结点？如何判断p指针所指结点是否为首元结点？对于以head为头指针的带头结点的双链环而言情况又如何？不带头结点判断尾元p->next?=head判断首元p?=head带头结点判断尾元p->next?=head判断首元p?=head->next4.6若线性表中的数据元素以值递增有序排列（数据元素的类

6、型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于min且小于max的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（说明：min和max是给定的两个参变量，可以设定为任意的整数值。）VoidDelete(LinkListhead){LinkListp,q;p=head;while(p->next!=NULL){if(p->next->datanext->data>min){q=p->next;p->next=q->next;free(q

7、);}elsep=p->next;}}4.8若有一个以head为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以3，得余数0,1,2。试按这3种不同的情况，把原有的链表分解成3个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。voiddecomposition(LinkListah,LinkList&bh,LinkList&ch){intk,num0=0,num1=0,num2=0;LinkLis

8、tpa,pb,pc,q;pa=ah;bh=(LNode*)malloc(sizeof(LNode));ch=(LNode*)malloc(sizeof(LNode));bh->next=NULL;ch->next=NULL;pb=bh;pc=ch;while(pa->next!=NULL){if(pa->next->data%3==0)k=0;elseif(pa->next->data%3==1)k=1;elsek=2;switch(k){case0:pa=pa->n