数据结构讨论小课堂和习题解答(共53页).doc

《数据结构讨论小课堂和习题解答(共53页).doc》由会员分享，可在线阅读，更多相关《数据结构讨论小课堂和习题解答(共53页).doc（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上讨论小课堂 1数据结构课程主要讨论哪三个方面？1.2.存储结构3.数据操作1.算法和程序的区别是什么呢？【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰

2、当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。2，你认为应该如何评估一个数据结构或算法的有效性。【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。3，讨论数据结构的重要性。【参考答案】：如今计算机的应用已深入到社会

3、生活 的各个领域，计算机处理的对象由单纯的数值 发展到字符、图象、声音等，表示这些对象的数据成分往往不是单一的，而是多成分且形成一定的结构。因此,在程序设计中，除了应精心设计算法外 ，还应精心组织数据（包括原始数据、中间结果 、最终结果），使之形成一定的组织形式（数据结构 ），以便让计算机尽可能高效率地处理。在实际程序设计的实践中 ，数据结构和算法是不同的但又是互相联系的两个方面。我们甚至还可以说 ，问题的算法往往取决于选定的数据结构 。 所以N.Wirth 教授认为 程序设计=算法+数据结构。我们已经初步地学习了高级语言（例如pascal）的程序设,掌握了一些程序设计方法与技巧 。然而，这些

4、方法与技巧对于现实的程序设计工作来说 ，是远远不够的。以下举几个例子加以说明 。例1 求真分数117/29 的值，求到小数点后50位例2 求真分数 7/27 的值，精确到小数点后50 位。1. 输出 117 /29的值。2. a 余数。b293. aa * 10 。4. 输出 a/b 的商。5. a余数。6. 如未达要求，转 3 ，否则结束。例3 从键盘输入若干个数 ，并将其排序输出。相同的数，只输出一个。本例似乎不难 ，可以采取的策略之一：用一个数组来存放输入的数，然后排序输出。策略之二：边输入边排序。我们注意到：输出只能是不同的数 ，因而这是一个搜索加排序的问题。所以，不论采取那一种策略

5、，用数组这一种结构不是最佳的结构，因为效率很低。事实上，若用二叉树作为存储结构，效率则会大大提高。例4 工作安排的可行性问题 。为了直观了解工作环节之间的制约关系，通常用有向图来表示这种安排。 习题11. 抽象数据类型的定义由哪几部分组成？ 1.1【参考答案】：数据对象、数据关系和基本操作三部分。 2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 1.2【参考答案】：线性结构、树型结构、图状结构和集合四类。 3. 你能举出几个你熟悉的序列的例子来吗？ 1.3【参考答案】：如：0，1，2，9,A，B，C，Z。 4. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象

6、数据类型。5.数据结构和数据类型两个概念之间有区别吗？1.5【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。6. 简述线性结构与非线性结构的不同点。1.6【参考答案】：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。7. 有下列两段描述：（1）void pro1( ) (2)void pro2( ) n=2; y=0; While(n%2=0) x=5/y; n=n+2; printf(“%d,%dn,x,y); printf(“%dn”,n); 这两段描述均不能满

7、足算法的特征，试问它们违反了算法的那些特征？1.7【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。8. 分析并写出下面的各语句组所代表的算法的时间复杂度。 (1) for (i=0; in; i+)for (j=0; jm; j+)Aij=0;【参考答案】：O（m*n）(2) k=0; for( i=1; i=n; i+) for (j=i ; j=n; j+) k+; 【参考答案】：O（n2） (3) i=1; while(i=n) i=i*3;【参考答案】：3 T(n)n即：T(n) log3n =O（log3n）所以：T(n)= O（

8、log3n） (4) k=0; for( i=1; i=n; i+) for (j=i ; j=n; j+) for (k=j ; k=n; k+) x += delta; 【参考答案】：O（n3）(5) for(i=0,j=n-1;ij;i+,j- -)t=ai; ai= aj; ai=t;【参考答案】：基本语句共执行了n/2次，T(n)=O（n）(6) x=0;for(i=1; in; i+) for (j=1; j=0&elemix) elemi+1=elemi; i-; elemi+1=x;length+;方法二：链式存储结构void insert(ElemType x) NodeTy

9、pe *p,*q,*s; p=L;q=q-next; while(q!=NULL&q-datanext; s=new NodeType; s-data=x; p-next=s; s-next=q;2.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的元素。问：如何改进此算法，使得算法效率提高？ void Deletaz(ElemType x) int i=0,j; while (ilength& elemix) i+; if(i=length) cout”X不存在”endl; else while(elemi=x) for(j=I;jlength;j+) elemj=elem

10、j+1; length-;【答案】void delete(ElemType x) int i=0,j,n; while(ilength&elemix) i+; if(i=length) cout“no x”endl; else while(elemi=x) n+;i+; for(j=i;jlength-1;j+) elemj-n=elemj; length=length-n; 3试设计一个算法，将线性表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, , , am, b1, b2, , bn ) 改变成(b1, b2, , bn, a1, a2, , am ) 要求采用顺序存储结

11、构及链式存储结构分别完成，并比较采用这两种存储结构，其算法效率哪种存储结构更好？【答案】试设计一个算法，顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, a2, , am, b1, b2, , bn ) 改变成 (b1, b2, , bn, a1, a2, , am ) 。 算法 1：进行三次“逆转顺序表”的操作。算法 2：从 b1开始，从原地删除之后插入到 a1 之前直至 bn。例如：具体实例： a, b, c, d, e, f, g ,1, 2，3，4，5改变成1, 2，3，4，5,a, b, c, d, e, f, g54gfedcba3213gfedcba54321

12、ji算法 1：void invert( ElemType R，int s， int t ) /* 本算法将数组 R 中下标自 s 到 t 的元素逆置， 即将（Rs, Rs+1, , Rt-1, Rt ） 改变为（Rt, Rt-1, , Rs+1, Rs ）*/ void exchange ( SqList A; int m ) /*本算法实现顺序表中前 m 个元素和后 n 个元素的互换*/ n = A.length m; invert( A.elem, 0, A.length ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); 算法

13、 2:void exchange( SqList A, int m ) /* 实现顺序表 A 中前 m 个元素和后 n 个元素互换*/for ( i=0; j = m; ji; k- ) A.elemj = A.elemj-1; A.elemi = x;算法的时间复杂度:为: O(mn)算法设计: 将 (b1, b2, , bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。a1a2amb1b2bnLtahbtbta-next=NULL;tb-next = L-next;L-next = hb;void exchange( SLink &L, int m ) / 互换链

14、表中前 m 个和后 n 个结点 ta = L; i = 0; while ( ta & inext; i+; / whileif ( ta & ta-next ) / m next; tb = hb; while (tb-next) tb = tb-next; / 查询表尾 bn修改指针 算法的时间复杂度:为:O(ListLength(L)4讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。【答案】存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 数据的逻辑结构只抽象反映数据元素的逻辑

15、关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关： 算法设计 逻辑结构 算法实现 存储结构 顺序表：可以实现随机存取：O(1) 插入和删除时需要移动元素：O(n) 需要预分配存储空间; 适用于“不常进行修改操作、表中元素相对稳定”的场合。 链表：只能进行顺序存取：O(n) 插入和删除时只需修改指针：O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为O(n2), 而以有序表表示集合进行运算的时间复杂度为O(n)习 题 21判断下列概念的正

16、确性(1) 线性表在物理存储空间中也一定是连续的。(2) 链表的物理存储结构具有同链表一样的顺序。(3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。答：（1）（2）（3）都不正确。2. 有如下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化？画出处理后的线性表。 void daorder() int i, j, n ; ElemType x;n=length/2; for( i=0 ; inext;Return n:5试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。1015181510H(a)

17、删除前181510H(b) 删除后答：void Deletaz(Linklist L) Lnode *p,*q,*r,*s; P=l-next;while (p) q=p;r=q-next;while(r)if(r-data!=p-data)q=r;r=r-next;elses=r-next;q-next=s;free(r);r=s; P=p-next; 6. 有一个线性表(a1,a2,.,an)，它存储在有附加表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为零。答：int linklist_x(linklist L,datatype x)int i

18、=0;Lnode *p;P=L-next;While(p&p-dada!=x)i+;p=p-next;If(!p)return 0;Else return I;7写一个算法将一单链表逆置。要求操作在原链表上进行。答：void reverse (LinkList L) p=L-next; L-next=NULL; while (p) q=p-next; p-next=L-next; L-next=p; p=q; 8在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法。答：void insert_x(Linklist L,Datatype x)

19、/*在递增有序的单链表L中插入值为x的元素，使得插入后L仍然有序*/Lnode *p,*q,*r;P=L;q=p-next;While(q&q-dadanext;R=(Lnode *)malloc(Lnode);r-dada=x;r-next=q;p-next=r;9写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点不存在，则插在表尾。答: void Insert_LinkList( LinkList L, DataType a, DataType B) /* 在值为a 的结点后插入值为B的结点，表中若无a则B接在表尾 */ LinkList p,q,s ; s=( LinkL

20、ist)malloc(sizeof(struct node); s-data=B; s-next=NULL; q=L; p=L-next; while( p!=NULL & p-data!=a ) q=p; p=p-next; if(p)s-next=p-next;p-next=s;else s-next=q-next;q-next=s; 10试用循环链表为存储结构，写一个约瑟夫(Josephu)问题的算法。约瑟夫问题是：有N个人围成一圈，从第i个人开始从1报数，数到m时，此人就出列。下一个人重新从1开始报数，再数到m时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，

21、N=5， i=1, m=3 时新的序列应为：3, 1, 5, 2, 4。答：typedef struct node /* 结点的结构定义 */ int num; /* 编号子域 */ struct node *next; /* 指针域 */ JOS;void outs(JOS *h, int m) int i; JOS *q=h, *p; printf(“n “); while (q-next!=q) for(i=1;inext; /* 报数到第m个人 */ printf(“%6d”,q-num); /* 输出第m个人的编号 */ p-next=q-next; free(q); /* 第m个人

22、出列 */ q=p-next; printf(“%6d n”,q-num); /* 输出最后一个结点的编号值 */ free(q); /* outs */11. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。答：void unit(Linklist A,Linklist B,Linklist C)Lnode *p,*q,*r,*s;P=A-next;q=next;C=A;r=C;While(p&q)if(p-dadadada)r=p;p=p-next;Elses=q;q=q-next;s

23、-next=r-next;r-next=s;r=s;If(!p)r-next=q;free(B)讨论小课堂 3【参考内容】1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。2. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？【答案】1、输入序列为，不能得出，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到的过程如下：1入栈并出栈，得到部分输出

24、序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果。2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。【答案】：3、设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时

25、为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0.m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致fr

26、ont=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之前。v 【参考答案】：v void trains(char *elem) v int i,k; v k=0; v for(i=0;i0)pop();k-; v 5.对于一个具有N个单元（N2）的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2（T2T1）

27、个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。v 【分析】v 时刻t: 0 1 2 3 4 5 6 7 8 9 v 个数： 1 1 2 1 2 2 3-2 2 3 2v 放取： + + - + + - + -v 时刻t: 10 11 12 13v 个数： 3 3 4-3 v 放取： + + - vv N=2 v 先放后取： 6时刻，放了4次，3个为溢出v 放取同时： 8时刻，放了5次，3个为溢出如果同一时刻先放后取： int main( ) int y=1,i=0, n, m, front=0,rear=1; cinn; cint1;cint2; m=n

28、+2; if (t1=t2) couterror!; else while(rear+1)%m!=front) i+; if (i%t1=0) rear=(rear+1 )%m; y+; if (i%t1=0&(rear+1)%m=front) break; if (i%t2=0) front=(front+1 )%m; couti ;cout2)的循环队列,若从进入第一个元素开始，每隔t1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。11.假设以带头结点的循环链表表示队列，并且只设

29、一个指针指向队尾元素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i 的系数。图3.17是指数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。讨论小课堂4重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组中，例如123放入,456放入，。编程统计其

30、共有多少个整数，并输出这些数。【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。算法如下：int CountInt（）/* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/int i=0，a； /* 整数存储到数组a，i记整数个数*/ char ch;scanf(%d,&ch)；/* 从左到右读入字符串*/while（ch!=#）

31、/*#是字符串结束标记*/if（ch）=48 & (ch)=48 & (ch)=57 & ch!=#）/* 拼数*/num=num10+ch-；scanf(%d,&ch)； ai=num；i+；if（ch!=#）scanf(%d,&ch)；/* 若拼数中输入了#，则不再输入*/ while（ch！#） /* 结束*/Printf(”共有%d”,I,”个整数，它们是：”)；for（j=；ji；j+）printf(“%d”;aj;” “)； if（j+1）10=0）printf(“n”); /*每10个数输出在一行上*/* 算法结束*/假定字符串中的数均不超过32767，否则，需用长整型数组及变量

32、。2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。例如：若S=“abceebccadddddaaadd!”， 则最长重复子串为“ddddd”。位置是9。【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。算法如下：int LongestString(char s,int n)/*串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。*/int index=0,ma

33、x=0; /*index记最长的串在s串中的开始位置，max记其长度*/ int length=1,i=0,start=0; /*length记局部重复子串长度，i为字符数组下标*/ while(in-1) if(si=si+1) i+; length+; else /*上一个重复子串结束*/if(maxlength) max=length; index=start; /*当前重复子串长度大，则更新max*/i+;start=i;length=1; /*初始化下一重复子串的起始位置和长度*/Printf(“最长重复子串的长度为:%d“;max;”在串中的位置:%d”;index);return(max);/*算法结束*/算法中用in-1来控制循环次数，因C数组下标从0 开始，故长度为n的串，其最后一个字符下标是n-1，当i最大为n-2时，条件语句中si+1正好是sn-1，即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。算法的时间复杂度为O(n)，每个字符与其后继比较一次。习题4习题41填空（1）在计算机软件系统中，有两种处理字符串长度的方法：一种是采用 显式 ，第二种是 隐式 。（2）一个字符串相等的充要条件是 长度 和 对应字符都相等