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

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

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

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

4、明 。例1求真分数117/29的值，求到小数点后50位例2求真分数7/27的值，精确到小数点后50位。1 .输出117 /29的值。2 . a <余数。b<293 . 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 .有下列两段描述：n=2;While(n%2=0)n=n+2;printf( %dn”,n);(1) void pro1( )(2)void pro2()y=0;x=5/y;printf( %d,%dn,x

7、,y)这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？1.7【参考答案】：(1)是一个死循环，违反了算法的有穷性特征。(2)出现除零错误，违反了算法的可行性特征。8 .分析并写出下面的各语句组所代表的算法的时间复杂度。(1) for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0；【参考答案】：O (m*n) 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;【参考答案】：3T(n)&n 即：T

8、(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;i<j;i+,j-)t=ai; ai= aj; ai=t;【参考答案】：基本语句共执行了 n/2次，T(n)=O (n)(6) x=0;for(i=1; i<n; i+)for (j=1; j<=n-i; j+)x+;【参考答案】:因为x+共执行了 n-

9、1+n-2+1= n(n-1)/2,所以执行时间为O2(n2)-1)2蔺f n n-1F5)二工 gi=办二 jf+i i=i讨论小课堂21 .在一个非递减有序线性表中，插入一个值为 X的元素，使插入后的线性表仍为非递减有序。(注意：对比顺序存储结构和链式存储结构表示。)【参考答案】方法一：顺序存储结构void insert(ElemType x) i=length-1;while(i>=0&&elemi>x)elemi+1=elemi;i-;elemi+1=x;length+;方法二：链式存储结构void insert(ElemType x) NodeType *

10、p,*q,*s;p=L;q=q->next;while(q!=NULL&&q->data<=x)p=q;q=q->next;s=new NodeType;s->data=x;p->next=s; s->next=q;2 .观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为元素。问：如何改进此算法，使得算法效率提高？void Deletaz(ElemType x) int i=0,j;while (i<length&& elemi<x) i+;if(i=l ength) cout<<

11、”Wf在 " <<endl;else while(elemi=x) for(j=I;j<length;j+) elemj=elemj+1;length-;【答案】void delete(ElemType x) int i=0,j,n;while(i<length&&elemi<x) i+;if(i=length) cout<< “ no x ” <<endl;elsewhile(elemi=x)n+;i+;for(j=i;j<length-1;j+)elemj-n=elemj;length=length-n;

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

13、i, 2, 3, 4, 5改变成i, 2, 3, 4, 5,a, b,c, d, e, f, g i ij123abcdefg4512345abcdefg算法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 );

14、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; j<A.length; i+,j+ ) x = A.elemj;for ( k=j; k>i; k-)A.elemj = A.elemj-1;A.elemi = x;算法的时间复杂度：为：O(m")算法设计:将（b1, b2,，bn处表的当前位置上删除之后再插入al到之前，并将am设为表尾。ta->next=

15、NULL;tb->next = L->next;L->next = hb;void exchange( SLink &L, int m ) /互换链表中前 m个和后n个结点ta = L; i = 0;while ( ta && i<m ) / 查询结点 amta = ta->next; i+; whileif ( ta && ta->next ) / m < 表长hb = ta->next; tb = hb;while (tb->next) tb = tb->next; / 查询表尾 bn 修改

16、指针算法的时间复杂度：为:O(ListLength(L)4.讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较【答案】存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系数据的逻辑结构一只抽象反映数据元素的逻辑关系数据的存储(物理)结构一数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关：算法设计一逻辑结构算法实现一存储结构顺序表：可以实现随机存取：0(1)插入和删除时需要移动元素：0(n)需要预分配存储空间；适用于不常进行修改操作、表中元素相对稳定”的场 合。链表：只能进

17、行顺序存取：0(n)插入和删除时只需修改指针：0(1)不需要预分配存储空间；适用于修改操作频繁、事先无法估计最大表长”的场合。应用问题的算法时间复杂度的比较例如，以线性表表示集合进行运算的时间复杂度为0 (n2),而以有序表表示集合进行运算的时间复杂度为 0 (n)习题21 .判断下列概念的正确性(1)线性表在物理存储空间中也一定是连续的。(2)链表的物理存储结构具有同链表一样的顺序。(3)链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。答：(1) (2) (3)都不正确。2 .有如下图所示线性表，经过daorder算法处理后，线性表发生了什么变化？画

18、 出处理后的线性表。void daorder() int i, j, n ; ElemType x;n=length/2;for( i=0 ; i<n; i+ ) j=length-i-1;x=elemi; elemi=elemj; elemj=x;elem0 elem7假设 length=812345678答：经过daorder算法处理后，线性表发生了逆置。处理后的线性表为:876543213 .试比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统 一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，

19、存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必 须预先分配较大的空间，往往使存储空间不能得到充分利用；（ 3）表的容量难 以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放 结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。4 .试写出一个计算链表中结点个数的算法，其中指针p指向该链表的第一个结 点。答：int linklist_num（linklist L,Lnode *p） int n=0;While（p）n+;p=p->next;Return

20、n:5 .试设计实现在单链表中删去值相同的多余结点的算法。（a）为删除前，（b）为删除后。j MI * 15 |18 人(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->next;elses=r->next;q->next=s;free(r);r=s;P=p->next;6 .有一个线性表(a1,a2,an)它存储在有附加表头结点的单链表中，写一个算法， 求出

21、该线性表中值为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-

22、>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->dada<=x)p=q;q=q->next;R=(Lnode *)malloc(Lnode);r->dada=x;r->next=q;p->next=

23、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

24、=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/* 结点的结构

25、定义*/ 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;i<m;i+) p=q; q=q->next; printf( “ %6-d”>n,uqm);/*p->next=q->next; free(q); q=p->next;printf( “ %6nd” ,-q>num);free(q); /* outs */*/*/* 报数到第m

26、个人 */输出第 m 个人的编号*/* 第 m 个人出列*/* 输出最后一个结点的编号值*/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->dada<=q->dada)r=p;p=p->next;Elses=q;q=

27、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 56 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）得到后，栈中元素

28、剩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。设队头

29、指针为front ,队尾指针是rear ,约定front 指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear 等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以 当队尾指针rear等于m-1时，若front不等于-1 ,则队列中仍有空闲单元，所 以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二， 一是将队列元素向前“平移”（占用0至rear-front-1 ）；二是将队列看成首尾 相连，即循环队列（0.m-1 ）。在循环队列下，仍定义front=rear时为队空，而 判断队满则用两种办法，一是用“牺牲一个单元”,即r

30、ear+1=front（准确记是（rear+1 ） %m=front, m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag , tag等于0情况下，若删除时导致front=rear 为队空；tag=1情 况下，若因插入导致front=rear则为队满。4 .假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N节硬席或软席车厢（程序中可分别用 H和S表示）等待调度，试编写算法，输出 对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之 前。【参考答案】：void trains(char *elem) int i,k;k=0;for(i=0;i<

31、;length;i+) if(elemi= S ) 软席车厢 S push()； pop()；elsepush()； k+while(k>0)pop();k-;5 .对于一个具有N个单元(N>>2的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2 (T2>T1)求出在第几个元素进个时间单位处理完一个元素并令其出队， 试编写一个算法, 队时将发生溢出。【分析】时亥ij t:012个数：112放取：+时亥ij t: 1011个数：33放取： +3 4561223-2-+ -12134-3+ -N=2先放后取： 6时刻，放了

32、 4次，3个为溢出放取同时： 8时刻，放了 5次，3个为溢出如果同一时刻先放后取：int main( ) int y=1,i=0, n, m, front=0,rear=1;cin>>n; cin>>t1;cin>>t2; m=n+2;if (t1>=t2) cout<<"error!”;elsewhile(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) fr

33、ont=(front+1 )%m; cout<<i<<" "cout<<y;return 0;习题31 .假定有编号为 A B G D的四辆列车，自右向左顺序开进一个栈式结 构的站台，如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开 出站台的顺序有几种？写出每一种可能的序列。 如果有n辆列车进行编组呢? 如何编程？注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许 出栈后回退。A B C D图3.16火车编组栈2 .已知栈采用链式存储结构，初始时为空，试画出 a,b,c,d四个元素依次 进栈以后栈的状态，然后再画

34、出此时的栈顶元素出栈后的状态。3 .写出链表栈的取栈顶元素和置栈空的算法。4 .写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。5 .对于给定的十进制正整数 N,转换成对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。6 .已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非 递归算法。f(n)=n +1当n = 0时n* f (n/2)当n#0时7 .假设如题3.1所述火车调度立勺入口处有 n节硬席或软席车厢(分别 以H和S表示)等待调度。试编写算法，输出对这n节车厢进行调度的操作(即 入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢

35、之前。8 .课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元 素的前一位置，队尾指针指向队尾元素。(1)试画出有2个元素A、 B的循环队列图，及将这2个元素出队后队列 的状态图。注：假设 MAXSIZE=6 front=5 ,完成本题要求的图示。若 erar=5 , 情况如何？(2)试画出有2个元素C、D的链表队列图，及将这2个元素出队后链表 队列的状态图。9 .对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。10 .对于一个具有n个单元(n>>2)的循环队列，若从进入第一个元素开始，每隔 t1 个时间单位进入下一个元素，同时从进入第一个元素开始，每隔 t

36、2(t2>t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。11 . 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。12 . 二项式 (a + b) i 展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n 行的程序。即逐行打印二项展开式(a + b) i 的系数。图3.17是指数 i 从 1 到 6 的 (a + b) i 的展开式系数所构成的杨辉三角形。讨论小课堂4重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。

37、1 . 输入一个字符串，内有数字和非数字字符，如： ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组a中，例如 123放入a0 ,456放入a 1, 。编程统计其共有多少个整数，并输出这些数。【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。 然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。算法如下：int CountInt()/* 从键盘输入字符串

38、，连续的数字字符算作一个整数，统计其中整数的个数。*/int i=0, a口； /*整数存储到数组a, i记整数个数*/char ch;scanf( d ,&ch/*从左到右读入字符用*/while( ch!= #) /* #是字符串结束标记 */if( ( ch) >=48 && (ch)<=57 ) /* 是数字字符*/num= 0 ;/*数初始化*/while( ( ch) >=48 && (ch)<=57 && ch!= #) /* 拼数 */num=num* 10+ 'ch-'。'

39、；scanf( %d ,&ch)ai=num； i+；if (ch!= '#'scanf( " %d ,&chy*若拼数中输入了 #'则不再输入*/ while (ch!=拼 /* 结束*/Printf( 共有 ” %d” ,I, 个整数，它们是： ”) ；for (j= 0 ; j<i; j+)printf("%d 司;”“)if( ( j+1)10=0) printf( n“” ); */每 10个数输出在一行上*/ /*算法结束*/假定字符串中白数均不超过 32767,否则，需用长整型数组及变量。2 .以顺序存储结构表示用

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

41、0; /*index记最长的用在s用中的开始位置，max记其长 度*/int length=1,i=0,start=0; /*length记局部重复子用长度，i为字符数组下标 */while(i<n-1)if(si=si+1) i+; length+;else/*上一个重复子用结束*/if(max<length) max=length; index=start; /*当前重复子用长度大，则更新max*/i+;start=i;length=1;/*初始化下一重复子用的起始位置和长度*/Printf(最长重复子用的长度为：d "max;在用中白位置：d" ；inde

42、x);return (max);/*算法结束*/算法中用i<n-1来控制循环次数，因C数组下标从0开始，故长度为n的用， 其最后一个字符下标是n-1,当i最大为n-2时，条件语句中si+1正好是sn-1, 即最后一个字符。子用长度的初值数为 1,表示一个字符自然等于其身。算法的时间复杂度为O(n),每个字符与其后继比较一次。习题4习题41.填空(1)在计算机软件系统中，有两种处理字符串长度的方法：一种是采用 显式, 第二种是隐式 。(2)一个字符串相等的充要条件是长度 和对应字符都相(3)串是指 有限个字符组成的序列;空串是指 长度 的串;空格用是指一个或多个空格组成的由。(4)设 s=

43、 UAM A-TEACHSR,其长度是 _14。(5)若n为主用长，m为子用长，则用的卡典匹配算法最坏的情况下需要比 较字符的总次数为。(m*n)。2 .空用和空格用有何区别？字符串中的空格符有何意义？空用在用的处理中有 何作用？答：空用时长度为0的字符用；空格用是一个或多个字符组成的字符串。字符串中的空格符充当界符的作用。空用在用的处理中可作为任意用的子用。3 .设计一算法，将两个字符串连接起来，要求不能利用 strcat ()函数。答：Typedef structchar *ch; /* 用数组 */ int length; /* 用长*/ HString;int StrConcat(HS

44、tring *S, HString T) char *temp;temp=(char *)malloc(S->length);if(temp=NULL)return(0);for(int i=0;i<S->length;i+)tempi=S->chi; /* 先把用 S放入临时申 temp 中*/free(S->ch);S->ch=(char*)malloc(S->length+T.length); /* 为 S 分配新的空间 */for(int i=0;i< S->length;i+)S->chi=tempi;for(int j=0

45、;j< T.length;j+)S->chi+j=T.chj; return(1);.4 .设计一算法，将字符串S中从pos位置开始共num个字符构成的子用用字符 用X来代替(X的长度可以不同于num)。Typedef structchar *ch; /* 用数组 */ int length;/* 用长*/HString;void Strrepl (HString *S, int pos, int num,HString X) if (pos < 1 | pos > S->length+1) printf("n位置错误!)return;/*位置不合法*/

46、char S1S->length ;/* S1作为辅助用空间用于暂存S */if (X.length)/*X非空，则为S重新分配空间并替换X*/char *p=S->ch; i=0; while (i < S.length)S1i+ = *(p+i);/* 暂存用 S*/if(pos+num>S->length) S->ch = new charpos + X.length ;Else S-> ch = new charS->length-num + X.length ;/*为S重新分配用值存储空间*/for ( i=0, k=0; i<p

47、os-1; i+)S->chk+ = S1i;j = 0;while (j<X.length)S->chk+ = X.chj+;while ( i<S->length)S->chk+ = S1i+;S->length+=T.length; /* if */ /* Strrepl*/*保留插入位置之前的子用*/*替换X*/*复制替换部分后的子用*/*置用S的长度*/5 .试设计一个算法，测试一个用t的值是否为回文(即从左面读起与从右面读 起内容一样)。答：int isSym(char *str,int length) /*判断一个字符串是否为回文,0是，

48、-1不是for(int i=0;i<length/2;i+) if(stri != strlength-i-1)return -1;return 0;6 .编写一个算法，统计在输入字符串中各个不同字符出现的频度 答：#include <stdio.h>int main()int charcount256;int i;char ch;/*初始化*/for(i=0;i<256;i+)charcounti =0;while(ch = getchar() !='n')charcount (int)ch +;/*输出*/for(i=0;i<256;i+)if

49、( charcounti) printf("%c - %dn", i, charcounti);return 0;7 .设s=" 00001000010100001 "，t= "说01在朴素模式匹配算法中的匹配过 程。第一趟匹配(1)第二趟匹配(2)I i=3 000010000101000010 0 0 11j=3|i=500001000010100001 0 0 0 1j=48.设计一个算法Replace(w,x),将当前字符串所有子用w用另一个字符串x来替 换。字符串w和x的长度可以不同。答：参考习题4和匹配算法。讨论小课堂5参考内容1

50、.设mXn阶稀疏矩阵A有t个非零元素，其三元组表表示为 LTMA1.(t+1),1.3,试问：非零元素的个数t达到什么程度时用LTMA表示A 才有意义？【参考答案】：稀疏夕!阵A有t个非零元素，加上行数 mu、列数nu和非零元素 个数tu,共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用 m Xn个单元，只有当3(t+1)< mXn时，用LTMA表示A才有意义。解不等式得 t< m x n/3-1。2 .特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 【参考答案】：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律。 因此，可以对非零元素分配

51、单元(这里，对值相同元素只分配一个单元)，将非零 元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可 以用简单公式表示，仍具有随机存取功能；而稀疏矩阵是指非零元素和矩阵容量 相比很小(t<<mxn),且分布没有规律。用十字链表作存储结构自然失去了随机 存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同。最好情况下存取时间为 O(1), 最差情况下是O(n),因此也失去了随机存取功能。3 .已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表 两种不同的存储结构，完成求矩阵元素之和，并分

52、析运算的优缺点。【参考答案】：设稀疏矩阵A为m行n歹I，如果采用二维数组常规存储，则其空 间复杂度为O(mxn)。因为要将所有的旬镇元素累加起来， 需要使用一个两层的 嵌套循环结构，所以其时间复杂度为O(mxn)。如果采用三元组顺序表进行压缩 存储，假设稀疏矩阵中有t个非零元素，则其空间复杂度为 O(t),将所有的矩阵 元素累加起来只需要将三元组顺序表扫描一遍， 其时间复杂度也为O(t)。当t<< m x n时，采用三元组顺序表存储可以获得较好的时间及空间性能。4 .广义表和线性表的区别与联系。【参考答案】：广义表是线性表的推广，线性表是广义表的特例。当广义表中的 元素都是原子时，

53、即为线性表。习题51 .设矩阵A为2 0 0 40 0 3 0|0 3 0 0# 0 0 0_(1)若将A看作对称矩阵，画出对其进行压缩存储的存储表示，并讨论如何存取A中元素aj(0&i, j<4)。(2)若将A看作稀疏矩阵，画出A的十字链表存储结构。【参考答案】：下标 12345678g102000304000123412342 .已知广义表A=(a), (b), c, (a), (d, e),解答下歹问题:(1)写出表的长度和深度。(2)用求头部和尾部的方式求出e。【参考答案】(1)表的长度为5，深度为4。(2)e=head(tail(head(head(head(tail(

54、tail(tail(tail(A)3 .设广义表为 A=(a,b,(c,d),(e,(f,g),(h,j),则式 head(tail(head(tail(tail(A) 的值为什么？(华北计算机技术研究所2001 年考研题 )【参考答案】： (g)4 .设有5对角矩阵，A=(aij)20x20,按特殊矩阵压缩存储的方式将其5条对角线上的元素存于数组B-10:m中，计算元素A15,15的存储位置。(东北大学1998年考研 题)【参考答案】：如果以行序为主，A15,15为第3+4+5X 12+3=70个，存储位置为 70-10-1=59;如果按对角线顺序， A15,15为第18+19+15=52个

55、，存储位置为 52-10-1=41。5,若矩阵Amxn中的某个元素aij是第i行中的最小值，同时又是第j歹I中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amxn,试编写求出矩阵中所有马鞍点的算法，并分析所写算法在最坏情况下的时间复杂度。【参考答案】：在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在的行号和列号输出。void Andian(int A, int m, int n)/求解矩阵A 的所有马鞍点 for(i=0; i<n; i+) d=Ai0;k=0;for(j=1; j<m; j+)if(Aij<d)d=Aij;k=j;for(j=0;j<n;j+)if(Ajk>d) break;if(j=n) cout<<” output Andian” <<I<<