47习题答案.ppt
线性结构线性结构 操作受限的线性表：栈、队列操作受限的线性表：栈、队列 线性结构线性结构线性表线性表 数据元素受限的线性表：串数据元素受限的线性表：串线性表回顾线性表回顾第四章线性表知识要点：第四章线性表知识要点：1 1、线性表类型的定义：（、线性表类型的定义：（a1,a2,ana1,a2,an）2 2、线性表的存储形式：顺序存储和链式存储方式，、线性表的存储形式：顺序存储和链式存储方式，以及以及各自的优缺点各自的优缺点 顺序存储：顺序存储：连续存储单元存储，分静态和动态连续存储单元存储，分静态和动态2 2种种 链式存储：链式存储：单链表、静态链表、双链表、循环链表单链表、静态链表、双链表、循环链表3 3、线性表的应用：一元多项式相加、线性表的应用：一元多项式相加第四章第四章 习题习题4.24.2请给出下述要求的判断条件：请给出下述要求的判断条件：（1 1）以）以headhead为头指针、不带头结点的单链表为空的条件是什为头指针、不带头结点的单链表为空的条件是什么？不为空的条件是什么？么？不为空的条件是什么？为空：为空：head=NULL; head=NULL; 不为空：不为空：head!=NULL;head!=NULL;(2)(2)以以headhead为头指针、带头结点的单链表为空的条件是什么？为头指针、带头结点的单链表为空的条件是什么？不为空的条件是什么？不为空的条件是什么？为空：为空：head-next=NULL; head-next=NULL; 不为空：不为空：head-next!=NULL;head-next!=NULL;(3)(3)以以headhead为头指针、不带头结点的单链环为空的条件是什么为头指针、不带头结点的单链环为空的条件是什么？不为空的条件是什么？不为空的条件是什么？为空：为空：head=NULL; head=NULL; 不为空：不为空：head!=NULL;head!=NULL;(4)(4)以以headhead为头指针、带头结点的单链环为空的条件是什么？为头指针、带头结点的单链环为空的条件是什么？不为空的条件是什么？不为空的条件是什么？为空：为空：head-next=head; head-next=head; 不为空：不为空：head-next!=head;head-next!=head;4.24.2请给出下述要求的判断条件：请给出下述要求的判断条件：（5 5）以）以headhead为头指针、不带头结点的单链表仅含有两个结为头指针、不带头结点的单链表仅含有两个结点的条件是什么？点的条件是什么？ head-next-next=NULLhead-next-next=NULL；(6)(6)以以headhead为头指针、带头结点的单链表仅含有两个结点的为头指针、带头结点的单链表仅含有两个结点的条件是什么？条件是什么？ head-next-next-next=NULL head-next-next-next=NULL；(7)(7)以以headhead为头指针、不带头结点的单链环仅含有两个结点为头指针、不带头结点的单链环仅含有两个结点的条件是什么？的条件是什么？ head-next-next=headhead-next-next=head；(8)(8)以以headhead为头指针、带头结点的单链环仅含有两个结点的为头指针、带头结点的单链环仅含有两个结点的条件是什么？条件是什么？ head-next-next-next=head head-next-next-next=head；4.34.3在长度为在长度为n n的顺序表上进行插入运算，有几个可插的顺序表上进行插入运算，有几个可插入的位置？在第入的位置？在第i i（假设合法）个位置上插入一个数（假设合法）个位置上插入一个数据元素，需要向什么方向平移多少个数据元素？在据元素，需要向什么方向平移多少个数据元素？在长度为长度为n n的顺序表上进行删除运算，有几个可删除的的顺序表上进行删除运算，有几个可删除的数据元素？删除第数据元素？删除第i i（假设合法）个位置上的数据元（假设合法）个位置上的数据元素，需要向什么方向平移多少个数据元素？素，需要向什么方向平移多少个数据元素？长度为长度为n,n,有有n+1n+1个插入位置个插入位置第第i i个位置上插入，需向右移动个位置上插入，需向右移动n-i+1n-i+1个数据元素个数据元素长度为长度为n n，有，有n n个删除位置个删除位置第第i i个位置上删除，需向左移动个位置上删除，需向左移动n-n-i i个数据元素个数据元素4.44.4根据图示回答下面的问题：根据图示回答下面的问题：（1 1）如何访问）如何访问p p结点的数据域？结点的数据域？P-dataP-data（2 2）如何访问）如何访问p p结点的直接前驱结点的数据域？结点的直接前驱结点的数据域？P-prior-dataP-prior-data（3 3）如何访问）如何访问p p结点的直接后继结点的数据域？结点的直接后继结点的数据域？P-next-dataP-next-data4.54.5对于以对于以headhead为头指针的不带头结点的双链环而言，如何判为头指针的不带头结点的双链环而言，如何判断断p p指针所指结点是否为尾元结点？如何判断指针所指结点是否为尾元结点？如何判断p p指针所指结点指针所指结点是否为首元结点？对于以是否为首元结点？对于以headhead为头指针的带头结点的双链环为头指针的带头结点的双链环而言情况又如何？而言情况又如何？不带头结点不带头结点 判断尾元判断尾元 p-next ?= headp-next ?= head 判断首元判断首元 p ?= headp ?= head带头结点带头结点 判断尾元判断尾元 p-next ?= headp-next ?= head 判断首元判断首元 p ?= head-nextp ?= head-next4.64.6若线性表中的数据元素以值递增有序排列（数据元素的类若线性表中的数据元素以值递增有序排列（数据元素的类型为整数类型），且用带头结点的单链表存储。试写出一个型为整数类型），且用带头结点的单链表存储。试写出一个高效算法删除表中所有值大于高效算法删除表中所有值大于minmin且小于且小于maxmax的数据元素（表的数据元素（表中有这样的数据元素时），并说明该算法的时间复杂度。（中有这样的数据元素时），并说明该算法的时间复杂度。（说明：说明：minmin和和maxmax是给定的两个参变量，可以设定为任意的整是给定的两个参变量，可以设定为任意的整数值。）数值。）Void Delete(Void Delete(LinkListLinkList head) head) LinkListLinkList p,qp,q; ; p=head; p=head; while(p-next!=NULL) while(p-next!=NULL) if(p-next-datanext-datamin) if(p-next-datanext-datamin) q=p-next; p-next=q- q=p-next; p-next=q-next;freenext;free(q); (q); p=p-next; p=p-next; 4.7 4.7 若有一个以若有一个以headhead为头指针的带头结点的单链表，为头指针的带头结点的单链表，结点数据域值属于整数类型。现将其数据域值除以结点数据域值属于整数类型。现将其数据域值除以3 3，得余数，得余数0,1,20,1,2。试按这。试按这3 3种不同的情况，把原有种不同的情况，把原有的链表分解成的链表分解成3 3个不同的单链表，且只增设两个头个不同的单链表，且只增设两个头结点空间，不允许另辟空间。写出一个算法实现上结点空间，不允许另辟空间。写出一个算法实现上述要求，并且要求头结点的数据域记录该链表中的述要求，并且要求头结点的数据域记录该链表中的数据结点数目。数据结点数目。void decomposition(LinkList ah,LinkList &bh,LinkList &ch)void decomposition(LinkList ah,LinkList &bh,LinkList &ch) int k;int k;LinkList pa,pb,pc,q;LinkList pa,pb,pc,q;pa=ah;pa=ah;bh=(LNode bh=(LNode * *)malloc(sizeof(LNode);)malloc(sizeof(LNode);ch=(LNode ch=(LNode * *)malloc(sizeof(LNode);)malloc(sizeof(LNode);bh-next=NULL;ch-next=NULL;pb=bh;pc=ch;bh-next=NULL;ch-next=NULL;pb=bh;pc=ch;while(pa-next!=NULL)while(pa-next!=NULL) if(pa-next-data%3=0) k=0;if(pa-next-data%3=0) k=0;else if(pa-next-data%3=1) k=1;else if(pa-next-data%3=1) k=1;elseelsek=2;k=2;switch(k)switch(k)case 0:pa=pa-next;break;case 0:pa=pa-next;break;case 1:case 1:q=pa-next;pa-next=q-next;q-next=pb-next;q=pa-next;pa-next=q-next;q-next=pb-next; pb-next=q;pb=q;break; pb-next=q;pb=q;break;case 2:case 2:q=pa-next;pa-next=q-next; q-next=pc-next; q=pa-next;pa-next=q-next; q-next=pc-next; pc-next=q; pc=q; break; pc-next=q; pc=q; break; 4.9 4.9 设有一个不带头结点的单链表，其结点的值设有一个不带头结点的单链表，其结点的值均为整数，并按绝对值从小到大链接。试将该单均为整数，并按绝对值从小到大链接。试将该单链表改造为结点按绝对值从大到小进行链接。不链表改造为结点按绝对值从大到小进行链接。不允许另辟空间，写出一个算法实现上述要求。允许另辟空间，写出一个算法实现上述要求。*A&C3E head1$Dpqrqp=NULLrr=NULLqpVoid invert(LinkList &head)Void invert(LinkList &head) linklist p,q,r; linklist p,q,r; p=r=NULL; p=r=NULL; q=head; q=head; while(q!=NULL)while(q!=NULL) r=q-next; r=q-next; q-next=p; q-next=p; p=q; p=q; q=r; q=r; head=p; head=p; 4.10 4.10 线性表有两种存储结构，即顺序表和单链表。试问：线性表有两种存储结构，即顺序表和单链表。试问：（1 1）若有）若有N N个线性表同时并存，且在处理过程中各表长度会动个线性表同时并存，且在处理过程中各表长度会动态发生变化，线性表的总数也会自动地改变，在此情况下应态发生变化，线性表的总数也会自动地改变，在此情况下应选用哪种存储结构？为什么？选用哪种存储结构？为什么？应采用链式存储结构，因为采用链式存储时插入删除操应采用链式存储结构，因为采用链式存储时插入删除操作不许移动数据元素作不许移动数据元素（2 2）若线性表的总数基本稳定，且很少进行插入和删除操作）若线性表的总数基本稳定，且很少进行插入和删除操作，但要以最快的速度存取表中元素，那么应采用哪种存储结，但要以最快的速度存取表中元
