数据结构讨论小课堂和习题解答.doc

讨论小课堂 11.算法和程序的区别是什么呢？【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。2，你认为应该如何评估一个数据结构或算法的有效性。【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。3，讨论数据结构的重要性。【参考答案】：如今计算机的应用已深入到社会生活 的各个领域，计算机处理的对象由单纯的数值 发展到字符、图象、声音等，表示这些对象的数据成分往往不是单一的，而是多成分且形成一定的结构。因此,在程序设计中，除了应精心设计算法外 ，还应精心组织数据（包括原始数据、中间结果 、最终结果），使之形成一定的组织形式（数据结构 ），以便让计算机尽可能高效率地处理。在实际程序设计的实践中 ，数据结构和算法是不同的但又是互相联系的两个方面。我们甚至还可以说 ，问题的算法往往取决于选定的数据结构 。 所以N.Wirth 教授认为 程序设计=算法+数据结构。我们已经初步地学习了高级语言（例如pascal）的程序设,掌握了一些程序设计方法与技巧 。然而，这些方法与技巧对于现实的程序设计工作来说 ，是远远不够的。以下举几个例子加以说明 。例1 求真分数117/29 的值，求到小数点后50位例2 求真分数 7/27 的值，精确到小数点后50 位。1. 输出 117 /29的值。2. a 余数。b293. aa * 10 。4. 输出 a/b 的商。5. a余数。6. 如未达要求，转 3 ，否则结束。例3 从键盘输入若干个数 ，并将其排序输出。相同的数，只输出一个。本例似乎不难 ，可以采取的策略之一：用一个数组来存放输入的数，然后排序输出。策略之二：边输入边排序。我们注意到：输出只能是不同的数 ，因而这是一个搜索加排序的问题。所以，不论采取那一种策略 ，用数组这一种结构不是最佳的结构，因为效率很低。事实上，若用二叉树作为存储结构，效率则会大大提高。例4 工作安排的可行性问题 。为了直观了解工作环节之间的制约关系，通常用有向图来表示这种安排。 习题11. 抽象数据类型的定义由哪几部分组成？ 1.1【参考答案】：数据对象、数据关系和基本操作三部分。 2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 1.2【参考答案】：线性结构、树型结构、图状结构和集合四类。 3. 你能举出几个你熟悉的序列的例子来吗？ 1.3【参考答案】：如：0，1，2，9,A，B，C，Z。 4. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。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); 这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？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（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) NodeType *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=elemj+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 ) 要求采用顺序存储结构及链式存储结构分别完成，并比较采用这两种存储结构，其算法效率哪种存储结构更好？【答案】试设计一个算法，顺序表中前 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, g54gfedcba3213gfedcba54321ji算法 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 ); 算法 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 ) / 互换链表中前 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讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。【答案】存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关： 算法设计 逻辑结构 算法实现 存储结构 顺序表：可以实现随机存取：O(1) 插入和删除时需要移动元素：O(n) 需要预分配存储空间; 适用于“不常进行修改操作、表中元素相对稳定”的场合。 链表：只能进行顺序存取：O(n) 插入和删除时只需修改指针：O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为O(n2), 而以有序表表示集合进行运算的时间复杂度为O(n)习 题 21判断下列概念的正确性(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) 删除前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=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)/*在递增有序的单链表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=( LinkList)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时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，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个人出列 */ 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-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、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。【答案】：3、设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针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情况下，若删除时导致front=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）个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。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+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.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i 的系数。图3.17是指数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。讨论小课堂4重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组中，例如123放入,456放入，。编程统计其共有多少个整数，并输出这些数。【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。算法如下：int CountInt（）/* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/int i=0，a； /* 整数存储到数组a，i记整数个数*/ char ch;scanf(%d,&ch)；/* 从左到右读入字符串*/while（ch!=#） /*#是字符串结束标记*/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，否则，需用长整型数组及变量。2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。例如：若S=“abceebccadddddaaadd!”， 则最长重复子串为“ddddd”。位置是9。【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。算法如下：int LongestString(char s,int n)/*串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。*/int index=0,max=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);/*算法结束*/算法中用ilength);if(temp=NULL)return(0);for(int i=0;ilength;i+)tempi=S-chi;/* 先把串S放入临时串temp中*/free(S-ch);S-ch=(char*)malloc(S-length+T.length); /* 为S分配新的空间*/for(int i=0;ilength;i+)S-chi=tempi;for(int j=0;jchi+j=T.chj;return(1);.4设计一算法，将字符串S中从pos位置开始共num 个字符构成的子串用字符串X来代替(X的长度可以不同于num)。答：Typedef struct char *ch; /*串数组*/ int length; /*串长*/HString;void Strrepl (HString *S, int pos, int num,HString X) if (pos S-length+1) printf(n 位置错误!);return; /*位置不合法*/ char S1S-length ; /* S1 作为辅助串空间用于暂存 S */ if (X.length) /*X 非空，则为S重新分配空间并替换X*/char *p=S-ch; i=0;while (i S-length)S-ch = new charpos + X.length ;Else S- ch = new charS-length-num + X.length ; /* 为S重新分配串值存储空间*/for ( i=0, k=0; ichk+ = S1i; /*保留插入位置之前的子串*/j = 0;while (jchk+ = X.chj+; /* 替换X*/while ( ilength)S-chk+ = S1i+; /* 复制替换部分后的子串*/S-length+=T.length; /* 置串 S 的长度*/ /* if */ /* Strrepl*/5试设计一个算法，测试一个串t的值是否为回文（即从左面读起与从右面读起内容一样）。答：int isSym(char *str,int length) /*判断一个字符串是否为回文,0是，-1不是for(int i=0;ilength/2;i+) if(stri != strlength-i-1) return -1; return 0;6编写一个算法，统计在输入字符串中各个不同字符出现的频度。答：#include int main() int charcount256; int i; char ch; /*初始化*/ for(i=0;i256;i+) charcounti = 0; while(ch = getchar() != n) charcount (int)ch +; /*输出*/ for(i=0;i256;i+) if( charcounti) printf(%c - %dn, i, charcounti); return 0; 7设s=”00001000010100001”, t =”0001”,说明其在朴素模式匹配算法中的匹配过程。答： i=3第一趟匹配 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(1)0 0 0 1 j=3 i=5 第二趟匹配0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(2) 0 0 0 1 j=4 8设计一个算法Replace(w,x), 将当前字符串所有子串w用另一个字符串x来替换。字符串w和x的长度可以不同。答：参考习题4和匹配算法。讨论小课堂5参考内容1设mn阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA1.(t+1),1.3，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？【参考答案】：稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用mn个单元，只有当3(t+1) mn时，用LTMA表示A才有意义。解不等式得t mn/3-1。2特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？【参考答案】：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律。因此，可以对非零元素分配单元(这里，对值相同元素只分配一个单元)，将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能；而稀疏矩阵是指非零元素和矩阵容量相比很小(tmn)，且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同。最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取功能。3已知A为稀疏矩阵，试从空间和