第二章 线性表.doc

习 题 二一、单选题1.在一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)之前插入一个新元素时，需要从年向前依次移 B 个元素。 A n-i B n-i+1 C n-i-1 D i 2.在一个长度为n的顺序存储的线性表中，删除第i个元素(1in+1)时，需要从前向后依次前移 A 个元素。3.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A n B n/2 C (n+1)/2 D (n-1)/24.在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行 B 。 A HL=p;p-next=HL; B p=next=HL; HL=p; C p-next=HL; p=HL; D p-next=HL-next;HL-next=p;5.在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行 D 。 A q-next=p-next;p-next=q; B p-next=q-next;q=p; C q-next=p-next;p-next=q D p-next=q-next;q-next=p;6.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 C 。 A p=q-next;p-next=q-next; B p=q-next;q-next=p; C p=q-next;q-next;q-next=q; D q-next=q=-Next-next;q-next=q;二、填空题1.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 ，另一个叫 指针 域。2.在下面数组a中链接存储着一个线性表，表头指针为a0.next，则该线性表为 (38,56,25,60,42,74) 。 a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 3.对于一个长度为l的顺序存储的线性表，在表头插入元素的时间复杂度帾 o(n) ，在表尾插入元素的时间复杂度为 O(1) 。4.对于一个单链接存储的线性表，在表头插入结点祫时话里有话复杂度为 o(1) ，在表尾插入元素的时间复杂度为 o(n) 。5.在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 i-1 ，后继元素的下标为 i+1 。6.在线性表的单链接存储中，若一个元素所在结点的地址为p，则后继结点的地址为 p-next ，若假定p为一个数组a中的下标，则其后继结点的下标为 ap.next 。7.在循环单链接表中，最后一个结点的指针域指向 表头 结点。8.在双向链接表中每个结点包含有两个针域，一个指向其 前驱 结点，另一个指向其 后继 结点。9.在循环双向链接表中表头结点的左指针域指向 表尾 结点，最后一个结点的右指针域指向 表头 结点。10.在以HL为表头指针的带表头附加结点的单链接表中，链表为空的条件分别为 HL-next=NULLHL-next=HL 。11.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 ai.next=a1.next;a1.next=i; 。12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个结点，并将该结点下标赋给i，具体操作为 i=a1.next;a1.next=ai.next; 。13.在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时，所进行的操作描述为 p=ai.next;ai.next=ap.next;i=p; 。14.在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为 aj.next=ai.next;ai.next=j; 。三、普通题1.解：(79,62,34,57,26,48)解：(26,34,48,57,62,79)解：(48,56,57,62,79,34)解：(56,57,79,34)解：(26,34,39,48,57,62)2.解： 为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)(8(56,4),(57,7),(79,5),(34,0)3.对于List类型的线性表,编写出下列每个算法。 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。解： ElemType DMValue(List&L) /从线性表中删除具有最小值的元素并由函数返回,空出的位置 /由最后一个元素填补,若线性表为空则显示出错信息并退出运行 if(ListEmpty(L) cerrList is Empty!end1; exit(1); ElemType x; x=L.list0; int k=0; for(int i=1;iL.size;i+) ElemType y=L.listi; if(yx)x=y;k=i; L.listk=L.listL.size-1; L.size-; return x; 从线性表中删除第i个元素并由函数返回。解：int Deletel(List& L,int i) /从线性表中删除第i个元素并由函数返回 if(iL.size) cerrIndex is out range!end1; exit(1); ElemType x; x=L.listi-1; for(int j=i-1;jL.size-1;j+) L.listj=L.listj+1; L.size-; return x; 向线性表中第i个元素位置插入一个元素。解：void Inser1(List& L,int i,ElemType x) /向线性表中第i个元素位置插入一个元素 if(iL.size+1) cerrIndex is out range!end1; exit(1); if(L.size=MaxSize) cerrList overflow!i-1;j-) L.listj+1=L.listj; L.listi-1=x; L.size+; 从线性表中删除具有给定值x的所有元素。解：void Delete2(List& L,ElemType x) /从线性表中删除具有给定值x的所有元素 int i=0; while(iL.size) if(L.listi=x) for(int j=i+1;jL.sizr;j+) L.listj-1=L.listj; L.size-; else i+; 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete3(List& L,ElemType s,ElemType t) /从线性表中删除其值在给定值s和t之间的所有元素 int i=0; while(i=s)&(L.listi=t) for(int j=i+1;jL.size;j+) L.listj-i=L.listj; L.size-; else i+; 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t) /从有序表中删除其值在给定值s和t之间的所有元素 int i=0; while(iL.size)/从有序表L中查找出大于等于s的第一个元素 if(L.listis)i+; else break; if(iL.size) While(i+jL.size)&(L.listi+j=t) j+;/求出s和t之间元素的个数 for(int k=i+j;kMaxSize) cerrList overflow!end1; exit(1); int i=0,j=0,k=0; while(iL1.size)&(jL2.size) if(L1.listi=L2.listj) /将L1中的元素赋给L L.listk=L1.listi; i+; else /将L2中的元素赋给L L.listk=L2.listj; j+; k+; while(iL1.size) /将L1中剩余的元素赋给L L.listk=L1.listi; i+;k+; while(jL2.size) /将L2中剩余的元素赋给L L.listk=L2.listj; j+;k+; L.size=k; 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9,2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。解：void Delete5(List& L) /从线性表中删除所有其值重复的元素,使其所有元素的值均不同 int i=0; while(iL.size) int j=i+1; while(jL.size) /删除重复值为L.listi的所有元素 if(L.listj=L.listi) for(int k=j+1;knext; /p指向下一个待逆序的结点 /将q结点插入到已陈序单链表的表头 q-next=HL; HL=q; 删除单链表中的第i个结点。解：void Delete1(LNode*&HL,int i) /删除单链表中的第i个结点 if(i1|HL=NULL) cerrIndex is out range!next; j+; if(cp=NULL) cerrIndex is out range!next; else ap-next=cp-next; delete cp; 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。解：ElemType MaxValue(LNode*HL) /从单链表中查找出所有元素的最大值，该值由函数返回 if(HL=NULL) cerrLinked list is empty!data; LNode*p=HL-next; while(p!=NULL) if(maxdata) max=p-data; p=p-next; return max; 统计出单链表中结点的值等于给定值x的结点数。解：int Count(LNode*HL,ElemType x) /统计出单链表中结点的值等于给定值x的结点数 int n=0; while(HL!=NULL) if(HL-data=x) n+; HL=HL-next; return n; 根据一维数组an建立一个单链表，使单链表中元素的次序与an中元素的次序相同，并使该算法的时间复杂度为O(n)。解：void Create(LNode*&HL,ElemType a,int n) /根据一维数组an建立一个单链表 InitList(HL); for(int i=n-1;i=0;i-) InsertFront(HL,ai; 将一个单链表重新链接成有序单链表。解：void OrderList(LNode*&HL) /将一个单链表重新链接成有序单链表 LNode* p=HL;/p指向待处理的第一个结点，初始指向原表头结点 HL=NULL; /HL仍为待建立的有序表的表头指针，禄始值为空 while(p!=NULL) /把原单链表中的结点依次进行有序链接 LNode* q=p; /q指向待处理的结点 p=p-next; /p指向下一个待处理的结点 LNode* ap=NULL,*cp=HL; /cp指向有序表中待比较的结点，ap指向其前驱结点 while(cp!=NULL) /为插入q结点寻找插入位置 if(q-datadata) break; else ap=cp; cp=cp-next; /将q结点插入到ap和cpxf hko pp uj q-next=cp; if(ap=NULL) HL=q; else ap-next=q; 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。解：LNode*Mergel(LNode*&p1,LNode*&p2) /将两个有序单链表合并成一个有序单链表 LNode a; /a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理 /结束后返回a结点的镄针域的值 LNode*p=&a; /p指向结果的有序单链表的表尾结点 p-next=NULL;/初始指向表头附加结点 while(p1!=NULL)&(p2!=NULL) /处理两个表非空的情况 if(p1-datadata) p-next=p1;p1=p1-next; else p-next=p2;p2=p2-; p=p-next; if(p1!=NULL)p-next=p1; if(p2!=NULL)p-next=p2; p1=p2=NULL; return a.next; 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15,16,20)。解：LNode*Merge2(LNode*p1,LNode*p2) /根据两个有序单链表生成一个新的有序单链表 LNode a; /用a作为新的有序单链表的表头附加结点 LNode*p=&a; /p指向结果有序单链表的表尾结点 p-next=NULL; /初始指向表头附加结点 while(p1!=NULL&(p2!=NULL) /处理两个表非空时的情况 LNode*newptr=new LNode; if(p1-datadata) /由p1-data建立新结点，然后p1指针后移 newptr-data=p1-data; p1=p1-next; else /由p2-data建立新结点，然后p2指针后移 newptr-data=p2-data; p2=p2-next; /将newptr结点插入到结果的有序表的表尾 p-next=newptr; p=newptr; while(p1!=NULL) /继续处理p1单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p1-data; p1=p1-next; p-next=newptr; p=newptr; while(p2!=NULL) /继续处理p2单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p2-data; p2=p2-next; p-next=newptr; p=newptr; p-next=NULL; return a.next; 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表保持不变。解：void Separate(LNode*HL,LNode*&p1,LNode*&p2) /根据一个单链表HL按条件拆分生成两个单链表p1和p2 LNode a,b; /a和b结点分别作为p1和p2单链表的表头附加结点 LNode*t1=&a,*t2=&b; /t1和t2分别作为指向p1和p2单链表的 /表尾结点，初始指向表头附加结点 Lnode*p=HL; while(p!=NULL) /每循环一次产生一个新结点，并把它加入到p1或p2单链表 /的未尾 LNode*newptr=new LNode; if(p-data%2=1) newptr-data=p-data; t1-next=newptr; t1=newptr; else newptr-data=p-data; t2-next=newptr; t2=newptr; p=p-next; t1-next=t2-next=NULL; p1=a.next;p2=b.next; /把指向两个单链表的表头结点的指针分别赋给 /p1和p2返回 6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位，不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去直到所有人都出列为止，试求出它们的出列次序。假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2.,n)开始报数，则得到的出列次序为:4,8,5,2,1,3,7,6。 此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。解： void Josephus(int n,int m,int s) /使用带表头附加结点的循环单链表解决约瑟夫问题 /生成表头附加结点，此时循环单链表为空 LNode*HL=new LNode; HL-next=HL; int i; /生成含有n个结点、结点依次为1,2,.n的带表头结点的循环单链表 for(i=n;i=1;i-) /生成新的结点 LNode*newptr=new LNode; newptr-data=i; /把新的结点插入到表头 newptr-next=HL-next; HL-next=newptr; /从表头开始顺序查找出第s个结点，对应第一个开始报数的人 LNode*ap=HL,*cp=HL-next; for(i=1;inext; /若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点 if(cp=HL)ap=HL;cp=HL-next; /依次使n-1个人出列 for(i=1;in;i+) /顺序查找出待出列的人，即为循环结束后cp所指向的结点 for(int j=1;jnext; if(cp=HL)ap=HL;cp=HL-next; /输出cp结点的值，即出列的人 coutdatanext=cp-next; delete cp; /使cp指向被删除结点的后继结点 cp=ap-next; /若cp指向了表头附加结点，则后移ap和cp指针 if(cp=HL)ap=HL;cp=HL-next; /使最后一个人出列 coutnext-datanext; delete HL; 7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点的循环单链表上实现的对应算法。初始化单链表解：void InitList(LNode*HL) HL-next=HL;/将单链表置空 删除单链表中的所有结点，使之成为一个空表void ClearList(LNode*HL) LNode*cp,*np; cp=HL-next;/将指向第一个结点的指针赋给cp while(cp!=HL)/遍历单链表，向系统交回每一个结点。 np=cp-next;/保存下一个结点的指针。 delete cp;/删除当前结点。 cp=np;/使下一个结点成为当前结点。 HL-next=HL;/置单链表为空 得到单链表的长度int ListSize(LNode*HL) LNode*p=HL-next; int i=0; while(p!=HL)i+;p=p-next; return i; 检查单链表是否为空int ListEmpty(LNode*hl) return(HL-next=HL); 得到单链表中第pos个结点中的元素ElemType GetElem(LNode*HL,int pos) if(pos1) cerrpos is out range!next; int i=0; while(p!=HL) i+; if(i=pos)break; p=p-next; if(p!=HL)return p-data; else cerrpos is out range!next; while(p!=HL) coutdatanext; coutnext; while(p!=HL) if(p-data=item) item=p-data; return 1; else p=p-next; return 0; 更新单链表中具有给定值的第一个元素int Updata(LNode* HL,const ElemType& item) LNode* p=HL-next; while(p!=HL)/查找元素 if(p-data=item)break; else p=p-next; if(p=HL)return 0; else/更新元素 p-data=item; return 1; 向单链表的未尾插入一个元素void InsertRear(LNode* HL,const ElemType& item) LNode* newptr; newptr=new LNode; newptr-data=item;/把新元素赋给动态结点*newptr的值域。 LNode* p=HL; while(p-next!=HL)/从表头开始遍历到最后一个结点为止。 p=p-next; newptr-next=HL;p-next=newptr;/把新结点链接到表尾。 向单链表的表头插入一个元素void InsertFront(LNode* HL,const ElemType& item) LNode* newptr; newptr=new LNode; newptr-data=item; newptr-next=HL-next; HL-next=newptr; (11)向单链表中插入一个元素void Insert(LNode* HL,const ElemType& item) LNode* newptr; newptr=new LNode; newptr-data=item; LNode *ap,*cp; ap=HL;cp=HL-next; while(cp!=HL) if(itemdata)break; elseap=cp;cp=cp-next; newptr-next=cp; ap-next=newptr; (12)从单链表中删除表头元素ElemType DeleteFront(LNode* HL) if(HL-next=HL) cerrDeleteing from an empty list!next; HL-next=p-next; ElemType temp=p-data; delete p; return temp; (13)从单链表中删除等于给定值的第一个元素int Delete(LNode* HL,const ElemType& item) LNode*ap=HL,*cp=HL-next; while(cp!=HL) if(cp-data=item)break; elseap=cp;cp=cp-next; if(cp=HL) cerrDeleted element is not exitst!next=cp-next; delete cp; return 1; (14)利用单链表进行数