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

010203操作受限的线性表：栈、队列线性结构→线性表→数据元素受限的线性表：串线性结构线性表类型的定义：（a1,a2,…,an）线性表的存储形式：顺序存储和链式存储方式，以及各自的优缺点顺序存储：连续存储单元存储，分静态和动态2种链式存储：单链表、静态链表、双链表、循环链表线性表的应用：一元多项式相加第四章线性表知识要点：线性表回顾第四章习题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；3在长度为n的顺序表上进行插入运算，有几个可插入的位置？在第i（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素？在长度为n的顺序表上进行删除运算，有几个可删除的数据元素？删除第i（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素？第i个位置上插入，需向右移动n-i+1个数据元素长度为n,有n+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-next4.6若线性表中的数据元素以值递增有序排列（数据元素的类型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于min且小于max的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（说明：min和max是给定的两个参变量，可以设定为任意的整数值。）VoidDelete(LinkListhead){LinkListp,q;p=head;while(p-next!=NULL){if(p-next-datamaxp-next-datamin){q=p-next;p-next=q-next;free(q);}elsep=p-next;}}4.8若有一个以head为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以3，得余数0,1,2。试按这3种不同的情况，把原有的链表分解成3个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的数据结点数目。voiddecomposition(LinkListah,LinkListbh,LinkListch){ intk,num0=0,num1=0,num2=0; LinkListpa,pb,pc,q; pa=ah; bh=(LNode*)malloc(sizeof(LNode)); ch=(LNode*)malloc(sizeof(LNode)); bh-