数据结构课后练习 - 第2章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 线性表,2.1,线性表的类型定义,2.2,线性表的顺序表示和实现,2.3,线性表的链式表示和实现,2.4,一元多项式的表示及相加,学习要点,了解,线性表的逻辑结构特性,，即数据元素之间存在着线性关系，在计算机中表示这种关系两类不同的存储结构：,顺序存储结构,和,链式存储结构,。用前者表示的线性表简称为,顺序表,，用后者表示的线性表简称为,链表,。,熟练掌握这两类,存储结构,的描述方法，如一维数组中一个区域,i.j,的上、下界和长度之间的变换公式（,L=j-i+1,i=j-L+1,j=i+L-1,），链表中,指针,p,和,结点*,p,的对应关系（结点*,(p-next),是结点*,p,的后继等），链表中,头结点,、,头指针,和,首元结点,（第一个元素的结点）的区别及,循环链表,、,双向链表,的特点等。,链表是本章的重点和难点，掌握指针操作和内存动态分配的编程技术,。,学习要点,熟练掌握在,顺序存储结构上线性表的基本操作,，如查找、插入和删除的算法。,熟练掌握在各种,链表结构中线性表的基本操作,，能在实际应用中选用适当的链表结构。,能够从时间与空间复杂度方面综合比较线性表两种存储结构的不同特点及其适用场合。,一、判断对错题,1.,线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（）,2.,线性表的链式存储结构优于顺序存储。（）,3.,在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。（）,4.,顺序存储的线性表可以实现随机存取。（）,二、单项选择题,1.,用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是,_,。,A.,当前结点所在的地址域,B.,指针域,C.,空指针域,D.,空闲域,2.,在具有,n,个结点的单链表中，实现,_,的操作，其算法的时间复杂度都是,O(n,),。,A.,遍历链表和求链表的第,i,个结点,B.,在地址为,p,的结点之后插入一个结点,C.,删除开始结点,D.,删除地址为,p,的结点的后继结点,B,A,二、单项选择题,3.,已知一个顺序存储的线性表，设每个结点需占,m,个存储单元，若第一个结点的地址为,da,1,，则第,i,个结点的地址为,_,。,A.da,1,+(i-1)mB.da,1,+im,C.da,1,-imD.da,1,+(i+1)m,4.,在,n,个结点的顺序表中，算法的时间复杂度是,O(1),的操作是,_,。,A.,访问第,i,个结点（,1in,）和求第,i,个结点的直接前驱（,2in,）,B.,在第,i,个结点之后插入一个新结点（,1in,）,C.,删除第,i,个结点（,1in,）,D.,将,n,个结点从小到大排序,A,A二、单项选择题,5.,两个指针,p,和,q,，分别指向单链表的两个元素，,p,所指元素是,q,所指元素前驱的条件是,_,。,A.p-next=q-nextB.p-next=q,C.q-next=pD.p=q,B,三、填空题,1.,在链表中逻辑上相邻的元素的物理位置,_,相连。,2.,在,n,个结点的顺序表中删除一个结点平均需要移动,_,个结点，具体的移动次数取决于,_,。,3.,在单链表中要在已知结点*,p,之前插入一个新结点，需找到,_,。,不一定,(n-1)/2,顺序表的长度与被删元素在表中的位序,结点*,p,的直接前驱结点（的地址）,四、简答题,1.,简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？,从空间上来看：,当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适。但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。,四、简答题,1.,简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？,从时间上来看：,若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。,四、简答题,2.,什么是头指针、头结点、首元结点。,首元结点：,链表中存储的线性表中的第一个数据元素的结点。,头结点：,为了操作的方便，通常在链表的首元结点之前附设一个结点，称头结点。,头指针：,指向链表中的第一个结点（或为头结点或为首元结点）的指针。,四、简答题,3.,在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？,插入结点：,移动元素次数,n-i+1,；,删除结点：,移动元素次数,n-i,。,决定因素：,顺序表的长度以及插入、删除元素在表中的位序。,4.,分析下述三个算法的具体功能。,ListNode*Demo1(LinkList L,ListNode*p),/L,是有头结点的单链表,ListNode,*q=L-next;,while(q&q,-next!=p),q=q-next;,if(q,),return q;,else Error(*p not in L);,算法功能：,寻找*,p,结点的直接前驱结点*,q,。,4.,分析下述三个算法的具体功能。,void Demo2(ListNode*p,ListNode*q),/p,，*,q,是链表中的两个结点,DataType,temp;,temp=p-data;,p-data=q-data;,q-data=temp;,算法功能：,*,p,结点和*,q,结点的值互换。,4.,分析下述三个算法的具体功能。,LinkList,test1(,LinkList,L),/L,是无头结点的单链表,LinkList,*q,*p;,if(L&L-next),q=L;L=L-next;p=L;,while(p-next)p=p-next;,p-next=q;q-next=NULL;,return L;,算法功能：,如果表长度大于,1,，则将首元结点删除并插入到表尾。,或者可以这么说：,把表,(a,1,a,2,a,i,a,n,),改成,(a,2,a,3,a,i,a,n,a,1,),。,5.,设有多项式,请画出 的单链表存储表示。,设 ，求得并画出的单链表存储表示。,9,0,8,1,9,4,5,10,-2,1,22,7,-5,10,A,B,9,0,6,1,9,4,22,7,C,五、程序设计题,1.,对给定的带头结点的单链表,L,，编写一个删除,L,中值为,x,的结点的直接前驱结点的算法。,x,被删结点,p,q,Status,ListDelete,_L(,LinkList,L,，,ElemType,x),/,在带头结点的单链表,L,中，删除值为,x,的结点。,LNode,*p,*q;,p=L;,while(p-next ,/,寻找值为,x,的结点，并令,p,指向其前驱（被删结点）；,/,指针,q,指向*,p,结点的前驱结点。,if(!(p-next)return ERROR;,/,表中不存在值为,x,的结点。,pnext=qnext;,/,删除元素（结点）,x的前驱结点。,free(p);,/,释放结点的存储空间。,return OK;,线性表的结构定义：,-,线性表的动态分配顺序存储结构,-,#define LIST_INIT_SIZE 100,/,顺序表的初始分配量,#define LISTINCREMENT 10,/,顺序表的分配增量,typedef,struct,ElemType,*,elem,;,/,存储空间基址：即数组的起始地址,int,length;,/,顺序表的当前长度：实际的元素个数,int,listsize,;,/,当前分配的存储容量（以,sizeof,（,ElemType,）,为单位）,SqList,;,2.,将一个顺序表中从第,i,个结点开始的,k,个结点删除。,Status,ListDelete_Sq,(,SqList,&L,int,i,int,k),/,在顺序线性表L中从第i个元素开始连续删除k个元素,/i的合法值为1iListLength_Sq(L),/,注意k的取值合法性判断,if(i,L.length,)return ERROR;,/,i的位置不合法,if(k,L.length,)return ERROR;,/,k,的,取值不合法,ElemType,*p,*q;,p=,/需要被删除的第i个元素（下标为i-1）,q=,L.elem,+,L.length,1;,/,从最后一个元素开始,if(k=(q-p)1),/,第,i,个元素后的所有元素均被删除,L.length,=i-1;return OK;,else,for(;k=1;k=1;-k;),for(+p;p next;,/,找到插入位置,while(p!=NULL&p-datanext;,s=(,LinkList,),malloc,(,sizeof(LNode,);,/,生成新结点,s-data=x;,s-next=p;,/,插入结点,q-next=s;,/,LinkListInsert,/-,线性单链表存储结构,-,typedef,struct,LNode,ElemType,data;,/,数据域,struct,LNode,*next;,/,指针域,LNode,*,LinkList,;,/*,LinkList,应该为指向线性单链表结点的指针,结束,