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

1、word讨论小课堂 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 < 余数。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",&quo

6、t;A，B，C，Z"。 4. 简述以下术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。5.数据结构和数据类型两个概念之间有区别吗？1.5【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。6. 简述线性结构与非线性结构的不同点。1.6【参考答案】：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。7. 有以下两段描述：1void pro1( ) (2)void pro2( ) n=2; y=0; While(n%2=0) x=5/y;

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

8、ile(i<=n) i=i*3;【参考答案】：3 T(n)n即：T(n) log3n =Olog3n所以：T(n)= Olog3n (4) k=0; for( i=1; i<=n; i+) for (j=i ; j<=n; j+) for (k=j ; k<=n; k+) x += delta; 【参考答案】：On3(5) for(i=0,j=n-1;i<j;i+,j- -)t=ai; ai= aj; ai=t;【参考答案】：根本语句共执行了n/2次，T(n)=On(6) x=0;for(i=1; i<n; i+) for (j=1; j<=n-i;

9、j+)x+;【参考答案】：因为x+共执行了n-1+n-2+1= n(n-1)/2，所以执行时间为On2讨论小课堂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 *p,*q,*s; p=

10、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.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的元素。问：如何改良此算法，使得算法效率提高？ void Deletaz(ElemType x) int i=0,j; while (i<length&& elemi<x) i+; if(i=length) cout<<X不存

11、在<<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; else while(elemi=x) n+;i+; for(j=i;j<length-1;j+) elemj-n=elemj; length=length-n; 3试设计一

12、个算法，将线性表中前 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 之前

13、直至 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 =

14、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; j<A.length; i+,j+ ) x = A.elemj;for ( k=j; k>i; k- ) A.elemj = A.elemj-1; A.elemi = x;算法的时间复杂度:为: O(m´n)算

15、法设计: 将 (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 && i<m ) / 查询结点 amta = ta->next; i+; / whileif ( ta && ta->

16、;next ) / m < 表长 hb = ta->next; tb = hb; while (tb->next) tb = tb->next; / 查询表尾 bn修改指针 算法的时间复杂度:为:O(ListLength(L)4讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比拟。【答案】存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储物理结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关：

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

18、3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算时机自动地将后继的各个单元向前移动。答：123都不正确。2. 有如以下图所示线性表，经过daorder 算法处理后，线性表发生了什么变化？画出处理后的线性表。 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=8 1 2 3 4 5 6 7 8 答：经过daorder 算法处理后，线性表发生了逆置。处理后

19、的线性表为：8 7 6 5 4 3 2 1 3试比拟顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：1在做插入和删除操作时，需移动大量元素；2由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；3表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两局部，一局部存放结点值，另一局部存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。4试写出一个计算链表

20、中结点个数的算法，其中指针指向该链表的第一个结点。答：int linklist_num(linklist L,Lnode *p) int n=0;While(p)n+;p=p->next;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)

21、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写一

22、个算法将一单链表逆置。要求操作在原链表上进行。答：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-&g

23、t;next;While(q&&q->dada<=x)p=q;q=q->next;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)mall

24、oc(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开始

25、报数，再数到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;i<m;i+) p=q; q=q->next; /* 报数到第m个人

26、 */ 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,

27、*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=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，

28、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.

29、简述顺序存储队列的“假溢出现象的防止方法及怎样判定队列满和空的条件。【答案】：3、设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质“删除在队头而“插入在队尾，所以当队尾指针rear等于m-1时，假设front不等于-1，那么队列中仍有空闲单元，所以队列并不是真满。这时假设再有入队操作，会造成假“溢出。其解决方法有二，一是将队列元素向前“平移占用0至rear-front-1；二

30、是将队列看成首尾相连，即循环队列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节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车

31、厢之前。v 【参考答案】：v void trains(char *elem) v int i,k; v k=0; v for(i=0;i<length;i+) v if(elemi=S) /软席车厢Sv push(); v pop(); v v else v push(); v k+ v while(k>0)pop();k-; v 5.对于一个具有N个单元N>>2的循环队列，假设从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2T2>T1个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。v

32、【分析】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; cin>>n; cin>>t1;cin>>t2;

33、m=n+2; if (t1>=t2) cout<<"error!"   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; &#

34、160;      if (i%t2=0) front=(front+1 )%m;                 cout<<i<<" "cout<<y;         return 0;习题31.假定有编号为A、B、C、D的四辆列车，自右向左顺序开进一个栈式结构的站台

35、，如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开出站台的顺序有几种？写出每一种可能的序列。如果有n辆列车进行编组呢？如何编程？注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许出栈后回退。图3.16 火车编组栈2.栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈以后栈的状态，然后再画出此时的栈顶元素出栈后的状态。3.写出链表栈的取栈顶元素和置栈空的算法。4.写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。5.对于给定的十进制正整数N，转换成对应的八进制正整数。1写出递归算法。 2写出非递归算法。6.n为大于等于零的整数，试写

36、出计算以下递归函数f(n)的递归和非递归算法。 f(n)=7. 假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢分别以H和S表示等待调度。试编写算法，输出对这n节车厢进行调度的操作即入栈或出栈操作序列，以使所有的软席车厢都被调整到硬席车厢之前。8.课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素。1试画出有个元素、B的循环队列图，及将这2个元素出队后队列的状态图。 注：假设MAXSIZE=6，front=5，完成此题要求的图示。假设erar=5，情况如何？2试画出有个元素C、D的链表队列图，及将这2个元素出队后链表队列的状态图。9.对于一

37、个具有m个单元的循环队列，写出求队列中元素个数的公式。10.对于一个具有n个单元(n>>2)的循环队列,假设从进入第一个元素开始，每隔t1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2t1)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。11.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点注意不设头指针，试编写出相应的置空队列，入队列和出队列的算法。12.二项式(a + b)i展开后，其系数构成杨辉三角形。利用队列写出打印杨辉三角形前n行的程序。即逐行打印二项展开式(a + b)i 的系数。图3.17是指

38、数i从1到6的(a + b)i的展开式系数所构成的杨辉三角形。讨论小课堂4重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一些运算的理解和掌握。1. 输入一个字符串，内有数字和非数字字符，如：ak123x456 17960302gef4563，将其中连续的数字作为一个整体，依次存放到一数组中，例如123放入,456放入，。编程统计其共有多少个整数，并输出这些数。【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符串中别离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字符为止，一

39、个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符串扫描到结束。算法如下：int CountInt/* 从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。*/int i=0，a； /* 整数存储到数组a，i记整数个数*/ char ch;scanf(%d,&ch)；/* 从左到右读入字符串*/whilech!=# /*#是字符串结束标记*/ifch>=48 && (ch)<=57/* 是数字字符*/num=； /*数初始化*/whilech>=48 && (ch)<=57 && ch!=#

40、/* 拼数*/num=num10+ch-；scanf(%d,&ch)； ai=num；i+；ifch!=#scanf(%d,&ch)；/* 假设拼数中输入了#，那么不再输入*/ whilech！# /* 结束*/Printf(共有%d,I,个整数，它们是：)；forj=；j<i；j+printf(“%d;aj; “)； ifj+110=0printf(“n); /*每10个数输出在一行上*/* 算法结束*/假定字符串中的数均不超过32767，否那么，需用长整型数组及变量。2. 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

41、例如：假设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,

42、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;index);return(max);/*算法结束*/算法中用i<n-1来控制循环次数，因C数组下标从0

43、开始，故长度为n的串，其最后一个字符下标是n-1，当i最大为n-2时，条件语句中si+1正好是sn-1，即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。算法的时间复杂度为O(n)，每个字符与其后继比拟一次。习题4习题41填空1在计算机软件系统中，有两种处理字符串长度的方法：一种是采用 显式 ，第二种是 隐式 。2一个字符串相等的充要条件是 长度 和 对应字符都相等 。3串是指 有限个字符组成 的序列；空串是指 长度 的串；空格串是指 一个或多个空格组成 的串。4设s=“IAMATEACHER,其长度是_14_。5假设n为主串长，m为子串长，那么串的古典匹配算法最坏的情况下需要比

44、拟字符的总次数为 m*n 。2空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有何作用？答：空串时长度为0的字符串；空格串是一个或多个字符组成的字符串。字符串中的空格符充当界符的作用。空串在串的处理中可作为任意串的子串。3设计一算法，将两个字符串连接起来，要求不能利用strcat函数。答：Typedef struct char *ch; /*串数组*/ int length; /*串长*/HString;int StrConcat(HString *S, HString T) char *temp;temp=(char *)malloc(S->length);if(tem

45、p=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;j< T.length;j+)S->chi+j=T.chj;return(1);.4设计一算法，将字符串S中从pos位置开始共num 个字符构成

46、的子串用字符串X来代替(X的长度可以不同于num)。答：Typedef struct char *ch; /*串数组*/ int length; /*串长*/HString;void Strrepl (HString *S, int pos, int num,HString X) if (pos < 1 | pos > S->length+1) printf("n 位置错误!");return; /*位置不合法*/ char S1S->length ; /* S1 作为辅助串空间用于暂存 S */ if (X.length) /*X 非空，那么为S重

47、新分配空间并替换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<pos-1; i+)S->chk+ = S1i; /*保存插入位置之前的子串*/j = 0;while (j<X.le

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

49、0;     if(stri != strlength-i-1)                        return -1;                return 0;6编写一

50、个算法，统计在输入字符串中各个不同字符出现的频度。答：#include   <stdio.h>     int   main()           int   charcount256;     int   i;     char   ch;     /*初始化*/    for(i=0;i<256;i+)     charcounti   = &

51、#160; 0;     while(ch   =   getchar()   !=   'n')     charcount   (int)ch     +;     /*输出*/     for(i=0;i<256;i+)     if(   charcounti)   printf("%c   -   %dn",   i,

52、60; charcounti);     return   0;     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设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA1.(t+1),1.3，试问：非零元素的个数t到达什么程度时用LTMA表示A才有意义？【参考答案】：稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m×n个单元，只有当3(t+1)< m×n时，用LTMA表示A才