文档详情

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

发布:2025-04-09约6.54千字共37页下载文档
文本预览下载声明

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-

显示全部
相似文档