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

讨论小课堂1

数据结构课程主要讨论哪三个方面？

1.逻辑结构

2.存储结构

3.数据操作

1.算法和程序的区别是什么呢？

【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足

有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没

有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方

面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表

了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设

计语言来描述，则它就是一个程序。

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同

的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优

劣由各种算法的执行来体现。

要设计一个好的算法通常要考虑以下的要求。

⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。

⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。

⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。

⑷高效。有效使用存储空间和有较高的时间效率。

2,你认为应该如何评估一个数据结构或算法的有效性。

【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时

间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编

码和易于调试。

3,讨论数据结构的重要性。

【参考答案］如今计算机的应用已深入到社会生活的各个领域，计算机处理的

对象由单纯的数值发展到字符、图象、声音等，表示这些对象的数据成分往往

不是单一的，而是多成分且形成一定的结构。因此，在程序设计中，除了应精

心设计算法外，还应精心组织数据（包括原始数据、中间结果、最终结果）

使之形成一定的组织形式（数据结构），以便让计算机尽可能高效率地处理。在

实际程序设计的实践中，数据结构和算法是不同的但又是互相联系的两个方面。

我们甚至还可以说，问题的算法往往取决于选定的数据结构。所以N.Wirth教

授认为程序设计=算法+数据结构。

我们已经初步地学习了高级语言（例如pascal）的程序设，掌握了一些程序设

计方法与技巧。然而，这些方法与技巧对于现实的程序设计工作来说，是远远

不够的。以下举几个例子加以说明。

例1求真分数117/29的值，求到小数点后50位

例2求真分数7/27的值，精确到小数点后50位。

1.输出117/29的值。

2.a<—余数。b<—29

3.aa*10o

4.输出a/b的商。

5.a<一余数。

6.如未达要求，转3,否则结束。

例3从键盘输入若干个数，并将其排序输出。相同的数，只输出一个。本

例似乎不难，可以采取的

策略之一：用一个数组来存放输入的数，然后排序输出。

策略之二：边输入边排序。

我们注意到：输出只能是不同的数，因而这是一个搜索加排序的问题。所

以，不论采取那一种策略，用数组这一种结构不是最佳的结构，因为效率很低。

事实上，若用二叉树作为存储结构，效率则会大大提高。

例4工作安排的可行性问题。为了直观了解工作环节之间的制约关系，通

常用"有向图”来表示这种安排。

高等数学

习题1

1.抽象数据类型的定义由哪几部分组成？

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)voidpro1()(2)voidpro2()

{{

n=2;y=0;

While(n%2==0)x=5/y;

n=n+2;printf("%d,%d\n,x,y);

printf("％d\n”,n);}

)

这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？

1.7【参考答案】：(1)是一个死循环，违反了算法的有穷性特征。(2)出现除零

错误，违反了算法的可行性特征。

8.分析并写出下面的各语句组所代表的算法的时间复杂度。

(1)for(i=0;i<n;i++)

for(j=0;j<m;j++)

A[i][j]=0;

【参考答案】：o(m*n)

(2)k=0;

for(i=l;i<=n;i++){

for(j=i;j<=n;j++)

k++;

)

【参考答案】:0(n2)

(3)i=l;

while(i<=n)

i=i*3;

【参考答案】：3T(n)Wn即：T(n)Wlog3n=O(log3n)所以:T(n)=0(log3n)

(4)k=0;

for(i=l;i<=n;i++){

for(j=i;j<=n;j++)

for(k=j;k<=n;k++)

x+=delta;;

}

【参考答案10(n3)

(5)for(i=0,j=n-l;i<j;i++,j--)

{t=a[i];a[i]=a[j];a[i]=t;}

【参考答案1基本语句共执行了n/2次，T(n)=O(n)

(6)x=0;

for(i=l;i<n;i++)

for(j=l;j<=n-i;j++)

x++；

【参考答案】：因为x++共执行了n-l+n-2+......+1=n(n-l)/2,所以执行时间为。

(I?)

%)=£力务-止。12

i=lJW+11=1L

讨论小课堂2

I.在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍

为非递减有序。(注意：对比顺序存储结构和链式存储结构表示。)

【参考答案】

⑴方法一：顺序存储结构

voidinsert(ElemTypex)

{i=length-l;

while(i>=O&&elem[i]>x)

{elem[i+l]=elem[i];

i—；

)

elem[i+l]=x;length++;

)

⑵方法二：链式存储结构

voidinsert(ElemTypex)

{NodeType*p,*q,*s;

p=L;q=q->next;

while(q!=NULL&&q->data<=x)

{p=q;q=q->next;}

s=newNodeType;

s->data=x;

p->next=s;s->next=q;

)

2.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的

元素。问：如何改进此算法，使得算法效率提高？

voidDeletaz(ElemTypex)

{inti=0,j;

while(i<length&&elem[i]<x)i++;

if(i==length)cout«MX不存在"vvendl;

else{while(elem[i]==x)

{for(j=I;j<length;j++)elemfj]=elemfj+l];

length-;}

【答案】

voiddelete(ElemTypex)

{inti=O,j,n;

while(i<length&&elem[i]<x)i++;

ifi(i==length)cout«4nox9,«endl;

else{

while(elem[i]==x)

{n++;i++;}

for(j=i;j<length-1;j++)

elem[j-n]=elem[j];

length=length-n;

)

)

3.试设计一个算法，将线性表中前m个元素和后n个元素进行互换，即将线

性表

(aj,,•••,am,b],b2,—,bn)改变成

(bj,b2,…,bn,aj,a2,…，am)

要求采用顺序存储结构及链式存储结构分别完成，并比较采用这两种存储结

构，其算法效率哪种存储结构更好？

【答案】试设计一个算法，顺序表中前m个元素和后n个元素进行互换，即

将线性表

网也,…,am，bl,b2,…,bn)改变成

(b],b2,…，如,al,a2,…，am)。

算法1：进行三次“逆转顺序表”的操作。

算法2：从bl开始，从原地删除之后插入到al之前直至bn。

例如：具体实例：{a,b,c,d,e,f,g,l,2,3,4,5}改变成{1,2,3,4,5,a,b,

c,d,e,f,g}|iI'

123abcdeg45

□

12345abcdefg

算法1:

voidinvert(ElemTypeR[],ints,intt)

/*本算法将数组R中下标自s到t的元素逆置，即将(Rs,Rs+1,

Rt-1,Rt)改变为(Rt,Rt-l,…，Rs+l,Rs)*/

voidexchange(SqListA;intm){

/*本算法实现顺序表中前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:

voidexchange(SqListA,intm){

/*实现顺序表A中前m个元素和后n个元素互换*/

for(i=0;j=m;j<A.length;i++,j++){

x=A.elem[j];

for(k=j;k>i;k-)

A.elem[j]=A.elem[j-1];

A.elem[i]=x;

算法的时间复杂度:为：O(mxn)

算法设计：

将(bl,b2,…,bn)从链表的当前位置上删除之后再插入al到之前，并

将am设为表尾。

tahb

ta->next=NULL;

tb->next=L->ncxt:

I->next=hh:

voidexchange(SLink&L,intm){

//互换链表中前m个和后n个结点

ta=L;i=0;

while(ta&&i<m){//查询结点am

ta=ta->next;i++;

}//while

if(ta&&ta->next){//m<表长

hb二ta->next;tb二hb;

while(tb->next)tb=tb->next;//查询表尾bn修改指针

算法的时间复杂度:为:O(ListLength(L))

4.讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。

【答案】存储结构分为：

⑴顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻

辑关系

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关

系

⑵数据的逻辑结构一只抽象反映数据元素的逻辑关系

数据的存储(物理)结构一数据的逻辑结构在计算机存储器中的实现

⑶数据的逻辑结构与存储结构密切相关：

算法设计一逻辑结构

算法实现一存储结构

⑷顺序表：

可以实现随机存取：0(1)

插入和删除时需要移动元素：0(n)

需要预分配存储空间；

适用于“不常进行修改操作、表中元素相对稳定'’的场

小

口0

链表：

只能进行顺序存取：0(n)

插入和删除时只需修改指针：0(1)

不需要预分配存储空间；

适用于“修改操作频繁、事先无法估计最大表长”的场合。

——应用问题的算法时间复杂度的比较

例如，以线性表表示集合进行运算的时间复杂度为0(n2),

而以有序表表示集合进行运算的时间复杂度为0(n)

习题2

1.判断下列概念的正确性

(1)线性表在物理存储空间中也一定是连续的。

(2)链表的物理存储结构具有同链表一样的顺序。

(3)链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地

将后继的各个单元向前移动。

答：(1)(2)(3)都不正确。

2.有如下图所示线性表，经过daorder算法处理后，线性表发生了什么变化？画

出处理后的线性表。

voiddaorder()

{inti,j,n;ElemTypex;

n=length/2;

for(i=0;i<n;i++)

{j=length-i-l;

x=elemfi];elem[i]=elem[j];elem[j]=x;

elem[O].......elem[7]彳段设length=8

12345678

答：经过daorder算法处理后，线性表发生了逆置。处理后的线性表为:

8765432

3.试比较顺序存储结构和链式存储结构的优缺点。

答：

顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统

一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必

须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难

以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放

结点值，另一部分存放表示结点间关系的指针。

优点：插入和删除元素时很方便，使用灵活。

缺点：存储密度小，存储空间利用率低。

4.试写出一个计算链表中结点个数的算法，其中指针P指向该链表的第一个结

点。

答：intlinklist_num（linklistL,Lnode*p）

{intn=0;

While（p）{n++;p=p-〉next;}

Returnn:

）

5.试设计实现在单链表中删去值相同的多余结点的算法。（a）为删除前，（b）为

删除后。

H*|*+|10I+|l5|4|l8||15|HI。I人I

(a)删除前

H—>|・+h。I+Il5|卜|18口

(b)删除后

答：voidDeletaz(LinklistL)

{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};

else{s=r->next;q->next=s;free(r);r=s;}

}

P=p->next;

6.有一个线性表(al,a2,…,an),它存储在有附加表头结点的单链表中，写一个算

法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为零。

答：intlinklist_x(linklistL,datatypex)

{inti=0;Lnode*p;

P=L->next;

While(p&&p->dada!=x){i++；p=p->next;}

If(!p)retum0;

ElsereturnI;

)

7.写一个算法将一单链表逆置。要求操作在原链表上进行。

答：voidreverse(LinkListL)

{p=L->next;

L->next=NULL;

while(p)

{q=p->next;

p->next=L->next;

L->next=p;

p=q；

8.在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍

为非递减有序。分别用向量和单链表编写算法。

答：voidinsert_x(LinklistL,Datatypex)

/*在递增有厚的单链表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=r;

9.写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点

不存在，则插在表尾。

答：voidInsert_LinkList(LinkListL,DataTypea,DataTypeB)

{/*在值的结点后插入值为B的结点，表中若无a则B接在表尾*/

LinkListp,q,s;

s=(LinkList)malloc(sizeof(structnode));

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=l,m=3时新的序

列应为：3,1,5,2,4。

答：

typedefstructnode/*结点的结构定义*/

{intnum;/*编号子域*/

structnode*next;/*指针域*/

}JOS;

voidouts(JOS*h,intm)

{inti;JOS*q=h,*p;

print/W")；

while(q->next!=q)

{for(i=l;i<m;i++){p=q;q=q->next;}/*报数到第m个人*/

printf(“％6d”,q->num);/*输出第m个人的编号*/

p->next=q->next;free(q);/*第m个人出列*/

q=p->next;

)

printff%6d\n”,q->num);/*输出最后一个结点的编号值*/

free(q);

}/*outs*/

11.设有两个单链表A、B,其中元素递增有序，编写算法将A、B归并成一个

按元素值递减(允许有相同值)有序的链表C,要求用A、B中的原结点形

成，不能重新申请结点。

答：voidunit(LinklistA,LinklistB,LinklistC)

{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;}

Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;}

)

If(!p)r->next=q;free(B)

讨论小课堂3

【参考内容】

1.如果输入序列为123456,试问能否通过栈结构得到以下两个序列:435

612和135426;请说明为什么不能实现或如何才能得到。

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入栈并退栈，得最终结果135426c

2、不能得到序列2,5,3,4,6o栈可以用单链表实现，这就是链栈。由于

栈只在栈顶操作，所以链栈通常不设头结点。

3.简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条

件。

【答案】：

3、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元

素在向量中的下标从。到mT。设队头指针为front,队尾指针是rear,约定front

指向队头元素的前一位置，rear指向队尾元素。当front等于T时队空，rear

等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以

当队尾指针rear等于m-1时，若front不等于T,则队列中仍有空闲单元，所

以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，

一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾

相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而

判断队满则用两种办法，一是用“牺牲一个单元”，即rear+l=front（准确记是

（rear+1）%m=front,m是队列容量）时为队满。另一种解法是“设标记”方法，

如设标记tag,tag等于0情况下，若删除时导致front=rear为队空；tag=l情

况下，若因插入导致front=rear则为队满。

4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N

节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出

对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之

>t.

刖。

♦【参考答案】：

♦voidtrains(char

❖{inti,k;

♦k=0;

♦for(i=0;i<length;i+,

if(elem[i]=='S')〃软席车厢S

♦{push();

♦pop();

♦)

❖else

♦{push();

❖k++)

♦while(k>0){pop();k—;}

♦：♦}

5.对于一个具有N个单元(N»2)的循环队列，若从进入第一个元素开始每隔

T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2(T2>T1)

个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进

队时将发生溢出。

♦【分析】

刻

时o89

数

个X32

取

放+

时刻n

12

数

个10

334+-3

取

放

+-

N=2

♦先放后取:6时刻，放了4次，3个为溢出

❖放取同时:8时刻，放了5次，3个为溢出

如果同一时刻先放后取：

intmain()

{inty=l,i=0,n,m9front=0,rear=l;

cin»n;cin»tl;cin»t2;m=n+2;

if(tl>=t2)cout«Herror!H;

else{

while((rear+l)%m!=front)

{i++；

if(i%tl==O){rear=(rear+l)%m;y++;}

if(i%tl==O&&(rear+l)%m==front)break;

if(i%t2==0){front=(front+l)%m;}

)

cout«i«"";cout«y;

return0;

))

习题3

1.假定有编号为A、B、C、D的四辆列车，自右向左顺序开进一个栈式结

构的站台，如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开

出站台的顺序有几种？写出每一种可能的序列。如果有n辆列车进行编组呢？

如何编程？

注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许

出栈后回退。

ABCD

图3.16火车编组栈

2.已知栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次

进栈以后栈的状态，然后再画出此时的栈顶元素出栈后的状态。

3.写出链表栈的取栈顶元素和置栈空的算法。

4.写出计算表达式3+4/25*8-6时，操作数栈和运算符栈的变化情况表。

5.对于给定的十进制正整数N,转换成对应的八进制正整数。

(1)写出递归算法。

(2)写出非递归算法。

6.已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非

递归算法。

q/、f〃+1当〃=0时

〃*/(〃/2)当〃w0时

7.假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢(分别

以H和S表示)等待调度。试编写算法，输出对这n节车厢进行调度的操作(即

入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。

8.课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元

素的前一位置，队尾指针指向队尾元素。

(1)试画出有2个元素A、B的循环队列图，及将这2个元素出队后队列

的状态图。

注：假设MAXSIZE=6,front=5,完成本题要求的图示。若erar=5,

情况如何？

(2)试画出有2个元素C、D的链表队列图，及将这2个元素出队后链表

队列的状态图。

9.对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。

10.对于一个具有n个单元(n〉>2)的循环队列,若从进入第一个元素开始，

每隔tl个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2

2tl)个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几

个元素进队时将发生溢出。

11.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元

素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算

法。

12.二项式(a+b)1展开后，其系数构成杨辉三角形。利用队列写出打印

杨辉三角形前n行的程序。即逐行打印二项展开式(a+b)1的系数。图3.17

是指数i从1到6的(a+b):的展开式系数所构成的杨辉三角形。

讨论小课堂4

重点掌握串的匹配运算及应用，可结合实际的题目进行讨论来加深对串的一

些运算的理解和掌握。

1.输入一个字符串，内有数字和非数字字符，如：akl23x45617960?302gef4563,

将其中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a

[0],456放入a[1],...........。编程统计其共有多少个整数，并输出这些

数O

【参考答案】在一个字符串内，统计含多少整数的问题，核心是如何将数从字符

串中分离出来。从左到右扫描字符串，初次碰到数字字符时，作为一个整数的开

始。然后进行拼数，即将连续出现的数字字符拼成一个整数，直到碰到非数字字

符为止，一个整数拼完，存入数组，再准备下一整数，如此下去，直至整个字符

串扫描到结束。

算法如下：

intCountlnt()

/*从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数。

*/

{inti=0,a[];/*整数存储到数组a,i记整数个数*/

charch;

scanf("%d",&ch)；/*从左到右读入字符串*/

while(ch!=#)/*'#'是字符串结束标记*/

if((ch)>=48&&(ch)<=57)/*是数字字符*/

{num=0；/*数初始化*/

while((ch)>=48&&(ch)<=57&&ch!='#')/*拼数*/

{num=num*10+'ch'-'0'；

scanf("%d",&ch)；

)

a[i]=num；i++；

if(ch!='#')scanf("%d",&ch)；/*若拼数中输入了则不再输入*/

}while(ch!='#')/*结束*/

Printf(“共有％个整数，它们是：")；

for(j=0；j<i；j++)

{printfT%d”;a[j];”")；

if((j+1)%10==0)printf("\n");}/*每10个数输出在一行上*/

}/*算法结束*/

假定字符串中的数均不超过32767,否则，需用长整型数组及变量。

2.以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及

其位置并分析算法的时间复杂度。例如：若S="abceebccadddddaaadd!”，则最长

重复子串为"ddddd”。位置是9。

【参考答案】设以字符数组s表示串，重复子串的含义是由一个或多个连续相等

的字符组成的子串，其长度用max表示，初始长度为0,将每个局部重复子串的

长度与max相比，若比max大，则需要更新max,并用index记住其开始位置。

算法如下：

intLongestString(chars[],intn)

/*串用一维数组s存储，长度为n,本算法求最长重复子串，返回其长度。

*/

{intindex=0,max=0;/*index记最长的串在s串中的开始位置，max记其长

度*/

intlength=l,i=O,start=O;/"length记局部重复子串长度，i为字符数组下标

*/

while(i<n-l)

if(s[i]==s[i+l]){i++;length++;}

else/*上一个重复子串结束*/

{if(max<length){max=length;index=start;}

/*当前重复子串长度大，则更新max*/

i++;start=i;length=l;

/*初始化下一重复子串的起始位置和长度*/

)

Printf("最长重复子串的长度为:%d“;max;”在串中的位置:%d”;index);

return(max);

}/*算法结束*/

算法中用i<n-l来控制循环次数，因C数组下标从0开始，故长度为n的串，

其最后一个字符下标是n-1,当i最大为n-2时，条件语句中s[i+l]正好是

即最后一个字符。子串长度的初值数为1,表示一个字符自然等于其身。

算法的时间复杂度为0(n),每个字符与其后继比较一次。

习题4

习题4

1.填空

(1)在计算机软件系统中，有两种处理字符串长度的方法：一种是采用显式，

第二种是隐式。

(2)一个字符串相等的充要条件是长度和对应字符都相

等O

(3)串是指有限个字符组成的序列:空串是指长度的串:

空格串是指_____________________

一个或多个空格组成的串。

(4)设S="LAM-AJTEACHER”,其长度是」4―。

(5)若n为主串长，m为子串长，则串的击典匹配算法最坏的情况下需要比

较字符的总次数为O(m*n)。

2.空串和空格串有何区别？字符串中的空格符有何意义？空串在串的处理中有

何作用？

答：空串时长度为0的字符串；空格串是一个或多个字符组成的字符串。字符串

中的空格符充当界符的作用。空串在串的处理中可作为任意串的子串。

3.设计一算法，将两个字符串连接起来，要求不能利用strcat。函数。

答：

Typedefstruct

{char*ch;/*串数组*/

intlength;/*串长*/

JHString;

intStrConcat(HString*S,HStringT)

(

char*temp;temp=(char*)malloc(S->length);

if(temp==NULL)return(O);

for(inti=O;i<S->length;i++)temp[i]=S->ch[i];/*先把串S放入临时串

temp中*/

free(S->ch);

S->ch=(char*)malloc(S->length+T.length);/*为S分配新的空间*/

for(inti=O;i<S->length;i++)S->ch[i]=temp[i];

for(intj=O;j<T.length;j++)S->chfi+j]=T.ch[j];

return(l);.

4.设计一算法，将字符串S中从pos位置开始共num个字符构成的子串用字符

串X来代替(X的长度可以不同于num)。

答：

Typedefstruct

{char*ch;/*串数组*/

intlength;/*串长*/

}HString;

voidStrrepl(HString*S,intpos,intnum,HStringX)

(

if(pos<1||pos>S->length+l)

{printf(n\n位置错误!");retum;}/*位置不合法*/

charSl[S->length];/*S1作为辅助串空间用于暂存S*/

if(X.length)

/*X非空，则为S重新分配空间并替换

X*/

char*p=S->ch;i=0;

while(i<S.length)

Sl[i++]=*(p+i);/*暂存串S*/

if(pos+num>S->length)S->ch=newcharfpos+X.length];

ElseS->ch=newchar[S->length-num+X.length];

/*为s重新分配串值存储空间*/

for(i=0,k=0;i<pos-1;i++)

S->ch[k++]=Sl[i];/*保留插入位置之前的子串*/

j=o；

while(j<X.length)

S->ch[k++]=X.ch[j++];/*替换X*/

while(i<S->Iength)

S->ch[k++]=Sl[i++];/*复制替换部分后的子串*/

S->length+=T.length;/*置串S的长度*/

}/*if*/

}/*Strrepl*/

5.试设计一个算法，测试一个串t的值是否为回文(即从左面读起与从右面读

起内容一样)。

答：

intisSym(char*str,intlength)/*判断一个字符串是否为回文,0是，-1

不是

{for(inti=0;i<length/2;i++)

{if(str[i]!=str[length-i-l])

return-1;

)

return0;

}

6.编写一个算法，统计在输入字符串中各个不同字符出现的频度。

答：

#include<stdio.h>

intmain()

(

intcharcount[256];

inti;

charch;

/*初始化*/

for(i=0;i<256;i++)

charcount[i]=0;

while((ch=getchar())!='\n')

charcountf(int)ch]++;

/*输出*/

for(i=0;i<256;i++)

if(charcount[i])printf(n%c-%d\n",i,charcount[i]);

return0;

7.设s="00001000010100001”,t="0001”,说明其在朴素模式匹配算法中的匹配过

程。

答：

Ii=3

第一趟匹配00001000010100001

(1)0001

tj=3

Ii=5

第二趟匹配00001000010100001

(2)0001

Ij=4

8.设计一个算法Replaced,x),将当前字符串所有子串w用另一个字符串x来替

换。字符串w和x的长度可以不同。

答：参考习题4和匹配算法。

讨论小课堂5

［参考内容］

1.设mXn阶稀疏矩阵A有t个非零元素，其三元组表表示为

LTMAri..(t+l),1..3］,试问：非零元素的个数t达到什么程度时用LTMA表示A

才有意义？

【参蚩答案］稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素

个数tu,共占用三元组表LTMA的3(t+l)个存储单元，用二维数组存储时占用m

Xn个单元，只有当3(t+l)<mXn时，用LTMA表示A才有意义。解不等式得

t<mXn/3-lo

2.特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？

【参考答案］特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律。

因此，可以对非零元素分配单元(这里，对值相同元素只分配一个单元)，将非零

元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可

以用简单公式表示，仍具有随机存取功能；而稀疏矩阵是指非零元素和矩阵容量

相比很小(t«mXn),且分布没有规律。用十字链表作存储结构自然失去了随机

存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要

扫描三元组表，下标不同的元素，存取时间也不同。最好情况下存取时间为0(1),

最差情况下是0(n),因此也失去了随机存取功能。

3.已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表

两种不同的存储结构，完成求矩阵元素之和，并分析运算的优缺点。

【参考答案工设稀疏矩阵A为m行n歹U，如果采用二维数组常规存储，则其空

间复杂度为O(mXn)。因为要将所有的句镇元素累加起来，需要使用一个两层的

嵌套循环结构，所以其时间复杂度为O(mXn)。如果采用三元组顺序表进行压缩

存储，假设稀疏矩阵中有t个非零元素，则其空间复杂度为0(t),将所有的矩阵

元素累加起来只需要将三元组顺序表扫描一遍，其时间复杂度也为0(。。当t<<m

Xn时，采用三元组顺序表存储可以获得较好的时间及空间性能。

4.广义表和线性表的区别与联系。

【参考答案】：广义表是线性表的推广，线性表是广义表的特例。当广义表中的

元素都是原子时，即为线性表。

习题5

1.设矩阵A为

2004

0030

0300

_4000

(1)若将A看作对称矩阵，画出对其进行压缩存储的存储表示，并讨论如何

存取A中元素a/OWi,卜4)。

(2)若将A看作稀疏矩阵，画出A的十字链表存储结构。

【参考答案工

下标1234567891a

2000304000

234

2.已知广义表A=(((a)),(b),c,(a),(((d,e)))),解答下列问题：

(1)写出表的长度和深度。

(2)用求头部和尾部的方式求出eo

【参考答案]

(1)表的长度为5,深度为4。

(2)e=head(tail(head(head(head(tail(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)2Ox2o)按特殊矩阵压缩存储的方式将其5条对角

线上的元

素存于数组中，计算元素A[15,15]的存储位置。(东北大学1998年考研

题)

【参考答案工如果以行序为主，A[15,15]为第3+4+5X12+3=70个，存储位置为

70-10-1=59；如果按对角线顺序，A[15,15]为第18+19+15=52个，存储位置为

52-10-1=41o

5.若矩阵Amxn中的某个元素a”是第i行中的最小值，同时又是第j列中的

最大值，则

称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amxn,试编写求出

矩阵中所有马鞍点的算法，并分析所写算法在最坏情况下的时间复杂度。

【参考答案工

在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该

列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在的行号和

列号输出。

voidAndian(intA[][],intm,intn)

〃求解矩阵A的所有马鞍点

{for(i=0;i<n;i++)

{d=A[i][0];

k=0;

for(j=l;j<m;j++)

if(A[i][j]<d)

{d=A[i][j];

k=j;

)

for(j=0;j<n;j++)

if(A[j][k]>d)break;

if(j==n)cout«”outputAndian,,«I«k«A[i][k];

)

)

本算法的时间主要耗费在for循环的嵌套上；外层for循环共执行n次，内

层第一个for循环执行m次，第二个for循环在最坏情况下执行n次，所以该算

法在最坏情况下的时间复杂度为(XmXn+M)或0(吟。

6.二维数组A的每个元素是由6个字符组成的串，行下标的范围是[0,8],

列下标的范围是[0,9],试问：

(1)存放二维数组A至少需要多少个字节？

(2)二维数组A的第8列和第5行共占用多少个字节？

(3)如果A按照行优先方式存储，则元素A[8][5]的起始地址与当A按列优先

方式存储时的哪个元素的起始地址一致。

【参考答案工

(1)因为二维数组A为9行10歹U，共有90个元素；所以存放A至少需要90

X6=540个存储单元。

(2)因为二维数组A的第8列和第5行共有10+9-1=18个元素(注意行列有一

个交叉元素)；所以共占108个字节。

(3)因为二维数组A的元素A[8][5]按行优先存储的起始地址为

LOC(a85)=LOC(a0o)+(8X10+5)Xc=LOC(aoo)+85Xc；

设二维数组A的元素按列优先存储的起始地址为LOC(aij)LOC(aoo)+(9

Xj+i)Xc；解此方程，得到i=4,j=9；所以元素A网⑸的起始地址与当A按列优

先方式存储时的元素A[4][9]地址一致。

7.假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B,要

求B也用三元组表示。

【参考答案】：三元组表示中要求按行的顺序存放，所有转置过程不能直接将行

下标和列下标转换，还必须使得列按顺序存放。因此在A中首先找出第一列中

的所有元素，它们是转置矩阵中第一行非0元素，并把它们依次放在转置矩阵三

元组数组B中；然后依次找出第二列中的所有元素，把它们依次放在数组B中；

按照同样的方法逐列进行，直到找出第n列的所有元素，并把它们依次放在数组

B中。

voidtranspose(TSMatrixA,TSMatrix*B)

/*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组*/

{