数据结构课件完整版

2023/5/14数据结构1数据结构

2023/5/14数据结构2讲课安排：串讲全书内容典型习题分析前年、去年考题分析

2023/5/14数据结构3第一章概论数据结构及其概念

如何评价一个算法2023/5/14数据结构4第一章概论1.1数据结构的概念一、术语1.数据(Data):

是信息的载体，能被计算机识别、存储、加工处理。2.数据元素(DataElement):

数据的基本单位,即数据集合中的一个个体。也称元素、

结点、顶点、记录数据项:是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素由数据项(dataitem)组成2023/5/14数据结构5

3、数据类型(DataType):

是具有相同性质的计算机数据的集合及在这个集合上的一组操作。原子数据类型(atomicdatatype)结构数据类型(aggregatedatatype)4、数据结构

数据的逻辑结构

数据的存储结构

数据的运算：既对数据施加的操作2023/5/14数据结构6逻辑结构：(有时直接称为数据结构）线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)非线性结构：树、图、多维数组、广义表说明：1、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关2023/5/14数据结构7存储结构：顺序存储方法：数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法：用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成分为稠密索引和稀疏索引散列存储方法：确定散列函数后，根据结点的关键字直接计算出该结点的存储地址。2023/5/14数据结构8关系：逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的。逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现（亦称映象）数据的运算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系2023/5/14数据结构9例：一个学生成绩表：是一个数据结构每行是一个结点（或记录），由学号、姓名、各科成绩及平均成绩等数据项组成。逻辑关系：线性结构存储结构：表的运算：2023/5/14数据结构10

逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义

算法是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。第一章概论1.3算法描述2023/5/14数据结构11

二、算法应具有的五个特性：（1）输入一个算法有零个或多个的输入，它们是算法 开始前给出的最初量（2）输出一个算法至少有一个输出，它们是同输入

有某种关系的量（3）有穷性每一条指令的执行次数必须是有限的（4）确定性每一条指令必须有确切的含义，无二义性（5）可行性每条指令的执行时间都是有限的。2023/5/14数据结构12第一章概论一、算法评价五要素

（1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（5）健壮性1.4算法分析2023/5/14数据结构13第一章概论二、算法的时间复杂度

一个算法所耗费的时间:该算法中每条语句的执行时间之和。每条语句的执行时间：该语句的执行次数乘以该语句执行一次所需时间。频度：语句重复执行的次数算法的时间耗费T(n)=每条语句的执行的时间

=（语句频度×语句执行一次所需时间）

=语句频度算法的时间复杂度：就是算法的时间耗费T(n)2023/5/14数据结构14第一章概论三、（渐进）时间复杂度(O(f(n))当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简称时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。例：顺序查找2023/5/14数据结构15五、空间复杂度S(n)：

算法所耗费的存储空间，仍是问题规模n的函数。第一章概论2023/5/14数据结构16第一章概论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。2023/5/14数据结构17第二章线性表本章要学习的主要内容1、线性表的逻辑结构及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双链表、静态链表4、顺序表和链表的比较2023/5/14数据结构182.1线性表的概念及运算1.描述:

线性表是由n(n>=0)个数据元素(点)a1,a2,….,ai,….,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n>0)记为：(a1,a2,….,ai,…..,an)一、逻辑结构注意:1.数据元素ai是一个抽象的符号

2.ai可取各种数据类型

3.一般情况下,同一线性表中的元素具有相同的数据类型

4.i是元素的序号(1<=i<=n)2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继2023/5/14数据结构19线性表的常见基本运算包括：

（1）置空表SETNULL(L)

（2）建表CREATLIST(L)二、线性表的运算

（4）取结点GET(L,i)

（5）定位LOCATE(L,x)

（6）插入INSERT(L,x,i)

（7）删除DELETE(L,i)

（3）求表长LENGTH(L)复杂的运算可以由这些基本运算组合来实现2023/5/14数据结构202.2线性表的顺序存储1、顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。3、存储地址的计算：

LOC(ai)=LOC(a1)+(i-1)*c1<=i<=n

这里：LOC(a1)为结点a1的存储起址(基地址），c为每个结点所占存储单元数。一、顺序表2、顺序表：采用顺序存储方法存储的线性表称顺序表。顺序表是一种随机存取结构2023/5/14数据结构21

typedef

int

datetype;#definemaxsize1024

typedef

struct{datatype

data[maxsize];

intlast;}sequenlist;4、顺序表的描述：说明:(1).datatype是表中的数据类型,依具体情况而定(2).向量下标可以看作表中结点的相对地址(3).

顺序表的长度为last+1(4).结点的引用:定义一个顺序表：sequenlist*L;

(*L).data[0]a1(*L).data[1]a2....

(*L).data[(*L).last]ana1a2...anMaxsize-1(*L).last01last2023/5/14数据结构22二、顺序表上的基本运算（实现）2.2线性表的顺序存储SETNULL（L）： (*L).last=-1LENGTH(L): (*L).last+1GET(L,i): (*L).data[i-1]LOCATE(L,x)INSERT(L,x,i)DELETE(L,i)

2023/5/14数据结构23顺序表的特点：

用物理位置上的邻接关系表示结点间的逻辑关系顺序表的优点：（1）无须增加额外的存储空间表示结点间的逻辑关系。（2）可以方便地随机存取表中任一结点。顺序表的缺点：（1）插入和删除运算不方便，通常须移动大量结点，效率较低。（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。2023/5/14数据结构242.3线性表的链式存储一、链表1、链式存储：用一组任意的存储单元存储线性表,逻辑上相邻的结点在物理位置上不一定相邻，结点间的逻辑关系由存储结点时附加的指针字段表示2、链表：采用链式存储方法的线性表称为链表。2023/5/14数据结构252.3.1单链表1、单链表的特点：每个结点只有一个链域，指向其直接后继

（尾结点除外）。4、单链表的存储结构描述如下：

typedef

int

dataype;

typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;2、结点结构：datanext3、图示法表示单链表a1a2an.....^head因为单链表由头指针唯一决定2023/5/14数据结构26说明：区分指针变量和结点变量:p,*p结点的动态分配和释放

typedef

int

datatype;

typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;

申请一个结点p=(linklist*)malloc(sizeof(linklist));释放一个结点free(p);2023/5/14数据结构272.3.2单链表上的基本运算（实现）1.建立单链表（1）头插法建表（2）尾插法建表方法:从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域,然后将新结点插入当前链表中,直到结束。头插法建表：将新结点插入到当前链表的表头ds优点：算法简单缺点：链表中结点次序和输入次序相反cbaHead^122023/5/14数据结构28Linklist*CREATLIST(){charch;linklist*head,*s;head=NULL;ch=getchar();dscbaHead^12while(ch!=‘$’){s=malloc(sizeof(linklist));s->data=ch;

s->next=head;head=s;ch=getchar();}returnhead;}2023/5/14数据结构292.3.2单链表上的基本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr^^不带头结点的尾插法：插入时，第一个结点的处理与其 它结点的处理有区别。

结束时，空表和非空表的处理有区别。2023/5/14数据结构30Linklist*CREATLISTR(){charch;linklist*head,*s,*r;head=NULL;

r=NULL;

ch=getchar();

while(ch!=‘$’){s=malloc(sizeof(linklist));

s->data=ch;

if(head=NULL)head=s

elser->next=s;

r=s;ch=getchar();}if(r!=NULL)r->next=NULL;returnhead;}2023/5/14数据结构312.3.2单链表上的基本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr^^不带头结点的尾插法：插入时，第一个结点的处理与其 它结点的处理有区别。

结束时，空表和非空表的处理有区别。带头结点的尾插法：1）链表第一个位置上的操作与其 它位置上的操作相一致。

2）空表和非空表的处理相一致。2023/5/14数据结构322.3.2单链表上的基本运算（实现）Linklist*CREATLISTR1(){charch;linklist*head,*s,*r;head=malloc(sizeof(linklist));r=head;ch=getchar();while(ch!=“$”){s=malloc(sizeof(linklist));s->data=ch;r->next=s;

r=s;ch=getchar();}

r->next=NULL;returnhead;}dsrcHeadr^^2023/5/14数据结构332.3.2单链表上的基本运算（实现）

二、查找运算（1）按序号查找GET（L，i）

给定一个序号，在单链表中查找该序号对应的结点，

若结点存在，则返回该结点的指针，否则返回空指针。方法：非随机存储结构的链表，决定了上述查找运算只能通过扫描单链表来完成。设置一个计数器j一个p，初始指向头结点P向后每移动一个位置j++当j=i时返回2023/5/14数据结构34按值查找即在链表中查找是否有值等于给定值key的结点。若有则返回首次找到的其值为key的结点的指针，否则返回NULL。算法描述如下：

linklist*locate(head,key)

linklist*head;

datatyekey;

{linklist*p;

p=headnext;

在等概率的情况下，该算法的平均时间复杂度亦为O(n)（2）按值查找LOCATE（head，key）2.3.2单链表上的基本运算（实现）while(p!=NULL)

if(pdata!=key)

p=pnext;

elsebreak;

returnp;

}2023/5/14数据结构353.插入运算

（1）后插操作:在指针p所指结点之后插入xs

（2）前插操作:在指针p所指结点之前插入Headp时间复杂度度O(1)xs平均时间复杂度O(n)先从头指针起,顺链找到*p的前趋结点*q.Headpq2023/5/14数据结构36Headpax3.插入运算:将前插操作转变为后插操作xsxsaINSERTBEFORE(p,x)linklist*p;datatypex;{linklist*s;s=malloc(sizeof(linklist));s->data=p->data;s->next=p->next;p->data=x;p->next=s;}时间复杂度O(1)应尽量将单链表上的插入操作转化为后插操作！2023/5/14数据结构374.删除运算时间复杂度O(1)删除指定结点的直接后继Headprr=p->next;p->next=r->next;free(r);删除指定结点时间复杂度O(n)链表的优点:在链表上实现插入、删除运算无须移动结点，仅须修改指针改进?2023/5/14数据结构382.单循环链表的特点：链表尾结点的next域不为空，而是指向头结点或开始结点。（优点：从任一结点开始，均可找到其前趋和后继结点。）3、引入单循环链表的目的在于方便一些运算的实现。

实用中常采用尾指针单循环链表,而不是头指针单循环链表。4、单循环链表上的操作与单链表基本一致

差别仅在于：循环控制条件不是判空，而是判断是否等于头指针或尾指针。2.3.3单循环链表1.循环链表:是一种首尾相接的链表单循环链表双循环链表2023/5/14数据结构39

1.

双链表的特点：每个结点有两个指针域，分别指向其直接

前趋和后继。2.双链表存储结构描述如下：

typedef

struct

dnode{datatypedata;

struct

dnode*prior,*next;}dlinklist;

dlinklist*head;

对于双向链表，当将头、尾结点链起来时，便成了双向循环链表。2.3.4双链表

priornextdata为了指示双链表，也须引入一个头指针head，指向其开始结点。2023/5/14数据结构403.双向链表基本运算的实现：（1）删除运算（2）插入运算插入和删除都非常方便p->prior->next=p=p->next->prior删除运算DELETENODE（p）

/*删除双链表结点*p*/dlinklist*p;{p->prior->next=p->next;p->next->prior=p->prior;free(p);}Headp2023/5/14数据结构41插入运算DINSERTBEFORE(p,x)dlinklist*p;datatypex;{dlinklist*s;Pxss=malloc(sizeof(dlinklist));s->data=x;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;}2023/5/14数据结构422.3.5静态链表

实现方法

存储空间

分配和释放

静态链表

游

标

预分配的一个连续空间

用户定义

动态链表

指

针

内存所有可用空间

系统提供

静态链表与动态链表的区别2023/5/14数据结构43

2、静态链表存储结构描述如下：

＃definemaxsize1024 typedefintdatatype; typedef

intcursor;typedefstruct{datatypedata;数据域

cursornext;游标

}node;nodenodepool[maxsize];存储池

cursorav;游标变量

2.3.5静态链表1、用数组和“游标”实现链式存储的方法是：

事先定义一个规模较大的结构数组作为备用结点空间（即存储池），当申请结点空间时，从存储池中取出结点，当释放结点空间时，将其归还于存储池内。采用这种方法实现的链表称为静态链表。12Maxsize-13NULL012Maxsize-1av0nodepool[maxsize]2023/5/14数据结构44说明:静态链表也可以用头指针L唯一指示,L为cursor类型

3、可用空间表:将存储池中所有空闲结点链成一个头指针为av的单链表,构成一个可用空间表2023/5/14数据结构452.3.5静态链表12Maxsize-13NULL012Maxsize-1av1nodepool[maxsize]初始化：INITALIZE(){inti;for(i=0;i<maxsize-1,i++)nodepool[i].next=i+1;nodepool[maxsize-1].next=NULL;av=1;}动态链表由系统分配和回收结点空间,静态链表由程序员编程分配和释放结点2023/5/14数据结构464、节点的分配与回收GETNODE():将表av上的第一个结点取出，并把该结点的位置付给pCursorGETNODE(){cursorp;if(av==NULL)p=NULL;else{p=av; av=nodepool[av].next; }returnp;}FREENODE(p)将p所指的结点插入到表av的头上。FREENODE(p){nodepool[p].next=av;av=p}2023/5/14数据结构475、静态链表基本运算的实现

:

初始化可用空间表创建静态链表表尾插入结点在指定结点前插入结点删除指定结点查找指定结点?说明:静态链表和动态链表在逻辑上是一致的,静态链表和动态链表上的运算的实现是一样的,只要注意游标和指针的对应关系就可以了2023/5/14数据结构483.1栈3.1.1栈的概念及运算1定义：栈（Stack）是仅在表的一端进行插入和删除运

算的线性表

栈顶(top)为进行插入和删除运算的一端

栈底(bottom)为另一端2特点:

最先入栈的元素总是最后出栈，而最后入栈的元素则总是最先出栈，因此，栈又被称为后进先出(LastInFirstOut)的线性表。栈顶栈底a1a2an退栈进栈……第三章栈和队列2023/5/14数据结构493栈的基本运算包括：（1）置空栈SETNULL（S）（2）判栈空EMPTY（S）:布尔函数（3）入栈PUSH(S，x)（4）出栈POP（S）（5）取栈顶TOP（S）栈顶栈底a1a2an退栈进栈……2023/5/14数据结构503.1.2顺序栈1定义：顺序栈是采用顺序存储结构的栈，c语言中通过数组来实现。栈顶指针top为指示栈顶位置的变量，用数组元素的下标来表示。2顺序栈存储结构描述：

typedefintdatatype;#definemaxsize100;

typedefstruct

{datatypedata[maxsize];

inttop;}seqstack;seqstack*s;2023/5/14数据结构513栈顶指针和栈中元素的关系：seqstacks;4321

0top=-1top=34321

0DCBA4321

0BAtop=1

空栈入栈出栈Sdata[0]toptoptoptypedefstruct

{datatypedata[maxsize];

inttop;}seqstack;seqstack*s;2023/5/14数据结构524顺序栈上基本运算的实现：1）置栈空setnull(s)2）判栈空intempty(s)3）进栈

seqstack*push(s,x)4）退栈

datatypepop(s)5）取栈顶

datatypetop(s)

2023/5/14数据结构535技巧

为了充分利用向量存储空间，多个栈共用一段存储空间。缺点：使栈运算的实现更复杂。.........栈1栈2栈1底栈1顶栈2顶栈2底栈1空：top1=-1栈2空:top2=maxsize栈满:top1+1=top22023/5/14数据结构543.1.3链栈1定义：采用链式存储结构的栈称为链栈。

链栈实际上是操作受限的单链表，其插入和删除操

作均在表头进行。2链栈的存储结构描述如下：

typedefintdatatype;typedef

structnode{datatypedata;structnode*next;}

linkstack;linkstack*top;2023/5/14数据结构55链栈中的结点动态产生,因而可以不考虑上溢问题栈底^top

datanext栈顶链栈示意图当top=NULL时，链栈为空。3链栈示意图2023/5/14数据结构564链栈上基本运算的实现：

1）

进栈

PUSHLSTACK(top,x)

Linkstack*PUSHLSTACK(top,x)linkstack*top;datatypex;{linkstack*p;p=malloc(sizeof(linkstack));

p->data=x;p->next=top;returnp;}2023/5/14数据结构57Linkstack*POPLSTACK(top,datap)

linkstack*top;

datatype*datap;{linkstack*p;

if(top==NULL){printf(“underflow”);returnNULL;}

else{*datap=top->data;

p=top;

top=top->next;

free(p);

returntop;

} }

2）

退栈

*POPLSTACK(top,datap)

2023/5/14数据结构583.2栈的应用举例1.文字编辑器2.

函数的递归调用（p47)2023/5/14数据结构593.3队列1定义：队列(queue)

是一端进行删除另一端进行插入的线性表。

允许插入的一端称为队尾(rear)

，允许删除的一端称为队头(front)。2特点：先入队(即插入队尾）的元素必将被先删除(即出队）。因此，队列是一种先进先出(FirstInFirstOut)的线性表。3.3.1队列的概念及运算出队入队队头队尾a1a2…an2023/5/14数据结构603队列的基本运算：（1）SETNULL（Q）置队空（2）EMPTY（Q）判队空（3）FRONT（Q）取队头元素,队中元素保持不变（4）ENQUEUE（Q,x)将元素x入队（5）DEQUEUE（Q）出队,函数返回原队头元素2023/5/14数据结构613.3.2顺序队列1定义：采用顺序存储结构的队列称为顺序队列。

规定：front总是指向当前队头元素的前一个位置

rear指向当前队尾元素的位置2顺序队列存储结构描述如下：

typedefstruct{datatypedata[maxsize];intfront,rear;}sequeue;sequeue*sq;2023/5/14数据结构6243210sq->rear

sq->frontsq->rear43210DCBA43210DC

空队列ABCD入队AB出栈sq->frontsq->frontsq->rear3顺序队列指针图示4顺序队列基本运算初始时，sqrear=sqfront=-1,在不考虑溢出的情况下，入队和出队的运算如下：

入队：sqrear++;sqdata[sqrear]=x;出队：sqfront++;2023/5/14数据结构63队空：

sqrear=sqfront队满：

sqrear－sqfront=maxsize下溢：队空时，若要进行出队操作时发生上溢：队满时，进行入队操作时出现。“假上溢”：当sq->rear=maxsize-1但队列并不满

时进行入队操作.sqrear=4sqfront=143210edcba这种情况（即sq->rear=maxsize-1)下若要进行入队运算,sqrear的值将超出下标范围，故不能进行这种运算，但此时整个队列空间并没用完。4几种特殊情况2023/5/14数据结构64解决“假上溢”的方法有两种：

（1）当元素出队或出现假上溢时，移动队列元素。

sqrear=4sqfront=143210edcbaedc43210sqrear=2sqfront=-1移动元素后（2）采用循环队列：即sq->data[0]接在sq->data[maxsize-1]之后循环队列的示意图054321sqrear=0sqfront=42023/5/14数据结构65采用循环队列后，进行入队和出队运算时，头、尾指针加1操作应如下进行：出队：sqfront=(sqfront+1)%maxsize;

入队：

sqrear=(sqrear+1)%maxsize;循环队列如何判断队空和队满?

方法一：引入标志flag

若(sqfront=sqrear)&&(flag=0),则队空,不能出栈。若(sqfront=sqrear)&&(flag=1),则队满,不能入栈。054321sqrear=5sqfront=5054321sqfront=5sqrear=42023/5/14数据结构66

方法二：牺牲一个元素的空间（sq->data[sq->front])，避免队满时头、尾指针指向同一位置。

若sqfront=sqrear，则队空。若(sqrear+1)%maxsize=sqfront，则队满。054321sqrear=1sqfront=1054321sqfront=5sqrear=42023/5/14数据结构673.3.3链队列1、定义：采用链式存储结构的队列称为链队列。（是限制在表头删除在表尾插入的单链表）2、链队列存储结构描述

typedef

struct{linklist*front,*rear;}linkqueue;linkqueue*q;

为了运算实现的方便，在队头结点前引入一个头结点。初始时（即队空）链队的头、尾指针均指向头结点。

^frontrearq头结点qrearfrontrearq头结点

^qfront队头结点q->front=q->rear2023/5/14数据结构681）入队ENQUEUE（q,x)类似于单链表的尾插法2023/5/14数据结构692）出队qrearfrontrearq头结点

^qfront队头结点*sfrontrearq头结点a1*s

^frontrearq头结点S=q->front->next;q->front->next=s->next;free(s);队列长度等于1时，不但修改头结点的指针域，还需尾指针。队列长度大于1时，只需修改头结点的指针域，尾指针不变。2023/5/14数据结构70解决方法：出队时只修改头指针，删除头结点，使链队列上的队头结点成为新的链表的头结点，队列上的第2个结点成为队头结点。即物理上删除头结点，逻辑上删除对头结点。即使当前队列长度为1，也不用修改尾指针。qrearfrontrearq头结点

^队头结点*s2023/5/14数据结构71串(即字符串）是一种特殊的线性表，其每个结点仅由一个字符组成。4.1串及其运算4.1.1串的基本概念

1.串(string):是由零个或多个字符组成的有限序列。 一般记为S=“a1a2...an”,

其中：S为串名，a1a2…an为串值；ai(1<=i<=n)可

以是字母、数字和其它字符；

注意：仅含一个空格的串（“”）和空串（“”）是不同的两个串。2.串长度：串中所含的字符个数

空串：长度为零的串（不含任何字符，和空格串严格区分）第四章串2023/5/14数据结构724.子串在主串中的序号：子串在主串中第一次出现时其第一个字符在主串中的序号。S1=“Iamastudent.”S2=“student”S2在S1中的序号为83.子串：串中任意个连续的字符组成的子序列,该串相应称为主串。空串为任意串的子串，任意串为其自身的子串。

两串相等当且仅当两串长度相等且对应位置上的字符相同。5.

在程序中使用的串可分为串常量和串变量S2=“student”将串常量命名为S2

charobject[]=“datastructure”第四章串2023/5/14数据结构734.1.2串的基本运算

串的基本运算有九种，具体如下（p61）（1）赋值：=

（2）联接：strcat(ST1,ST2)

（3）求串长：strlen(S)

（4）求子串：substr(S,i,j)

（5）比较串的大小：strcmp(S,T)

（6）插入：insert(S1,i,S2)

（7）删除：delete(S,i,j)

（9）置换：replace(S1,i,j,S2)，repl(S,T,V)2023/5/14数据结构744.2串的存储结构

串可以分别采用顺序、链式和索引存储结构实现存储。1）用字符数组描述1、顺序存储

串中的字符被顺序地存储在内存中相邻的存储单元中。采用顺序存储结构的串称为顺序串。

Howareyou?\０…….串S的顺序存储示意图S=“Howareyou?”#definemaxsize32chars[maxsize];2023/5/14数据结构75

２）

顺序串存储结构描述：

#definemaxsize128; typedefstruct {charch[maxsize]; intcurlen; }seqstring;串字符存储空间串长度

缺点：顺序串上插入、删除运算不方便。2023/5/14数据结构762.链式存储

采用链式存储结构的串称为链串，链串中结点的数据域既可存储单个字符，也可存储多个字符，结点数据域存储字符的个数称为结点的大小。

显然，结点大小大于1的链串，其结点的存储密度提高了，但同时也带来了问题：

(1)如何处理链串的最后一个结点，因为串所含字符数不一定是结点大小的整数倍。

(2)插入、删除运算实现起来不方便。(p64)2023/5/14数据结构77

typedefstructlinknode{chardata;structlinknode*next;}linkstring;linkstring*s;如果结点大小不为1，则此处应说明一个字符数组。

链串存储结构描述如下：

2023/5/14数据结构781）带长度的名字表

2）带末指针的名字表

3）带特征位的名字表

4）带位移量的名字表3.索引存储特点：将串的串名作为关键字组织名字表(即索引表)，名字表中的每一项记录了串名和串值存放单元的起址及确定串长的有关数据。

名字表一般采用顺序存储方式存储。其组织形式主要有如下几种：(p65)2023/5/14数据结构79

本节讨论子串定位运算(也称模式匹配)在顺序串上的实现,及在链串上的实现．子串定位运算的含意：4.3串运算的实现设有两个顺序串S和T，且：

S=“s0s1s2…..sn-1”目标

T=“t0t1t2…...tm-1”模式

匹配有两种结果：若在S中找到了模式为T的子串（若有多个模式为T的子串，只需找出第一个）时，则返回该子串在S中的位置，这种情况称为匹配成功；否则称为匹配失败。2023/5/14数据结构80

1.朴素的匹配算法基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S中的位置，否则，T再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。

ababcabcacbababcac2023/5/14数据结构81

1.朴素的匹配算法基本思想：初始时，从S的第一个字符开始将T的第一个字符与其进行比较，若相等，则继续逐个比较后续字符，如匹配成功，则返回子串在S中的位置，否则，将T向右移动一个字符位置，从T的第一个字符开始与S中第二个字符进行比较，并在相等的情况下逐个比较后续字符，进行第二趟匹配，成功则返回子串在S中的位置，否则，T再向右移动一个字符位置，进行第三趟匹配，如此反复，或匹配成功，或当T右移到无法与S继续进行比较时，匹配失败。

ababcabcacbababcac2023/5/14数据结构82

ababcabcacbab设S=“ababcabcacbab”T=“abcac”abcaci=0j=0i=1j=1i=2j=2i指针回溯的位置为：i=i-j+1（i的值为1）

1.朴素的匹配算法2023/5/14数据结构83

ababcabcacbab设S=“ababcabcacbab”T=“abcac”abcaci=1j=0i指针回溯的位置为：i=i-j+1（i的值为2）2023/5/14数据结构84设S=“ababcabcacbab”T=“abcac”

ababcabcacbababcaci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指针回溯的位置为：i=i-j+1（i的值为3）2023/5/14数据结构85

ababcabcacbab设S=“ababcabcacbab”T=“abcac”abcaci=3j=0i指针回溯的位置为：i=i-j+1（i的值为4）2023/5/14数据结构86

ababcabcacbab设S=“ababcabcacbab”T=“abcac”abcaci=4j=0i指针回溯的位置为：i=i-j+1（i的值为5）2023/5/14数据结构87

ababcabcacbab设S=“ababcabcacbab”T=“abcac”abcaci=5j=0i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5返回子串的位置为：i-j+1=6（串的起始位置从1开始算起）2023/5/14数据结构88

intindex(s,t)seqstring*s,*t;{ inti=0,j=0; while((i<scurlen)&&(j<tcurlen)) if(sch[i]==tch[j]{i++;j++;} else {i=i-j+1;j=0; } if(j==tcurlen)return(i-j+1)elsereturn(-1);}朴素的模式匹配算法描述如下：2023/5/14数据结构895.1多维数组一、多维数组的概念多维数组可以看成是向量（一维数组）的扩展1、二维数组：

可以看成是m个行向量和n个列向量组成的向量逻辑特征：

除边界外，每个元素aij恰好有两个直接前趋和两个直接后继。ai-1,jai,jai+1,jai,j-1ai,j+1Amn=a11a12…a1na21a22…a2n………am1am2…amn2023/5/14数据结构902.三维及多维数组三维数组Amnp:

可看成有p个二维数组（m*n)所组成的向量每个元素aijk同属于三个向量（二维数组）最多有3个直接前趋和直接后继（除角、边、面上的结点）推广：多维数组An1n2…nm可看成nm个（m-1）维数组所构成的向量任一元素ai1i2…im都属于m个向量，最多有m个直接前趋和m个直接后继 2023/5/14数据结构91对于数组，通常只有两种操作：

(1)取值：给定一组下标，存取相应的数据元素；

(2)修改：给定一组下标，修改相应数据元素中的某一个或几个数据项的值。二、多维数组的运算说明：对于数组，通常只进行读、写操作，不进行元素的插入和删除操作。因此，一般采用顺序存储结构表示数组。2023/5/14数据结构921、两种顺序存储方法：

(1)行优先顺序(rowmajororder)(c,pascal语言采用）

特点：将数组元素按行向量排列(以二维数组为例）(2)列优先顺序(columnmajororder)(fortran语言采用）

特点：将数组元素按列向量排列(以二维数组为例）a11a12…...a1na21a22……a2n…am1am2amn

第1行第2行第m行a11a21…...am1a12a22……am2………a1na2namn

第1列第2列第n列三、顺序存储方法2023/5/14数据结构932、特点

顺序存储的数组是一个随机存取结构，即只要知道开始元素的存储起址、维数和每一维的上、下界及单个元素所占单元数，便可将数组元素的存储地址表示为其下标的线性函数。(以二维数组为例,且数组采用行优先顺序）

LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*dd为单个元素所占单元数开始元素的存储起址n为列数c语言中因数组下标从0开始，因此上面的式子应改为：

LOC(aij)=LOC(a00)+(i*n+j)*d2023/5/14数据结构945.2矩阵的压缩存储压缩存储:

前提：非零元素呈某种规律分布或矩阵中有大量零元素定义：多个值相同的元素只分配一个存储空间，值为0的

元素不分配空间采用压缩存储的矩阵分为两类：特殊矩阵和稀疏矩阵。5.2.1特殊矩阵特殊矩阵：指的是非零元素或零元素的分布有一定规律的矩阵。对特殊矩阵常采用一维数组存储。需解决的问题：如何将二维数组元素下标转换成一维数组元素下标。2023/5/14数据结构95

1.对称矩阵

1）定义:已知n阶方阵A，若其元素满足如下性质：

aij=aji0<=i,j<=n-1

则称A为对称矩阵。让每两个对称的元素共享一个存储空间，即只存储上三角或下三角矩阵元素。

需存储元素的个数为n(n+1)/2，该数决定了一维数组s的大小。2)存储方法：a00a10a11a20a21a22……an-1,0an-1,1an-1,2…an-1,n-12023/5/14数据结构963)确定aij与s[k]的对应关系

a:

若i>=j则k=i*(i+1)/2+jb:

若i<j则k=j*(j+1)/2+i(这是由对称性质决定的）

注意：进行压缩存储后，没有改变原采用二维数组存储时能进行随机访问的特性。综合a、b，令I=max(i,j),J=min(i,j)，则

k=I*(I+1)/2+Jloc(aij)=loc(sa[k])=loc(sa[0])+k*d

=loc(sa[0])+(I*(I+1)/2+J)*da00a10a11a20a21a22…aij

an-1,0an-1,1an-1,2…an-1,n-12023/5/14数据结构972.三角矩阵（方阵）1）分类：三角矩阵以主对角线划分，可分为上三角矩阵和下三角矩阵。a00cc…ca10a11c…a20a21…c…………an-1,0an-1,1an-1,2…an-1,n-12023/5/14数据结构982.三角矩阵（方阵）2）存储方法：只需存储非常数三角中的所有元素，另外再加一个存储单元存储常数C。

非常数三角中的所有元素个数为n(n+1)/2,外加一个常数,总共有n(n+1)/2+1个元素，可用一维数组s[n*(n+1)/2+1]存储，常数存于最后一个存储单元。1）分类：三角矩阵以主对角线划分，可分为上三角矩阵和下三角矩阵。2023/5/14数据结构99上三角矩阵中aij与s[k]的对应关系：下三角矩阵中aij与s[k]的对应关系：

i*(2n-i+1)/2+j-ii<=jk=n*(n+1)/2i>j

i*(i+1)/2+ji>=jk=n*(n+1)/2i<ja00a01…a0,n-1ca11…a1,n-1……aii…aij…cc…an-1,n-13)存储地址的计算i*n-(i-1)*i/22023/5/14数据结构1003.对角矩阵特点：所有的非零元素都集中在以对角线为中心的带状区域中。带状区域外的所有元素均为零。以三对角矩阵为例（p75)三对角矩阵中所有非零元素为3*n-2,可用一维数组s[3*n-2]存储.再次强调：特殊矩阵的压缩存储没有改变原采用二维数组存储时所具有的随机存取特性。

2023/5/14数据结构1015.2.2稀疏矩阵稀疏矩阵的压缩存储通常有两种方式：三元组表和十字链表。稀疏矩阵：非零元素的个数远远少于矩阵元素的总数的矩阵（s<<m*n)。压缩存储：只存储非零元素1、基本概念压缩存储特点：由于非零元素的分布是无规律的，在进行压缩存储后，将破坏原采用二维数组存储时所具有的随机存储特性。2023/5/14数据结构1021）定义：用一个三元组(i,j,aij)来表示稀疏矩阵中的一个非零元素aij,将表示稀疏矩阵中所有非零元素的三元组按行优先的原则顺序排列，得到一个其结点均为三元组的线性表，该表称为三元组表（结构数组）。A4*4=050000300-2006000015231-2306ijvB4*5=05000003000-200060000所以，为了唯一确定一个稀疏矩阵，还必须存储矩阵的行、列数。为了运算实现的方便，通常将稀疏矩阵的行、列数与三元组表存储在一起。2、三元组表2023/5/14数据结构1032）稀疏矩阵用三元组表实现压缩存储时的存储结构描述#defineSMAX16typedefstruct

{inti,j;datatypev;}node;typedefstruct{intm,n,t；

nodedata[SMAX];}spmatrix;spmatrix*a;定义三元组结构

定义三元组表结构2023/5/14数据结构1043)运算：

稀疏矩阵采用三元组表实现存储后，其矩阵运算的实现比采用二维数组存储时要复杂。2023/5/14数据结构105a)矩阵的转置运算

A=

00-3200000012000B=转置

0200000010-30020

01213120-3232

ijvA的三元组表

ijv

02-3102311322B的三元组表转置后例：spmatrix*a;

a->m==3;a->n==5;a->t==4;a->data[16]2023/5/14数据结构106传统转置方法介绍基本思想：由于A的列是B的行，因此按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先顺序存放的。为了找到A的每一列中的所有非零元素，需要对三元组表a->data从第一行起扫描一遍，由于a->data是按A的行优先顺序存放的，因此得到的恰是b->data应有的顺序。时间复杂度：O(n*t)>>O(m*n)

01213120-3232

ijvA的三元组表

ijv

02-3102311322B的三元组表转置后2023/5/14数据结构1073、十字链表1)十字链表中结点的结构：

ijv/nextcptrrptr存储行号存储列号存储元素值或指向下一个表头结点列指针域，指向本列下一个非零元素行指针域，指向本行下一个非零元素4)三元组表的优点：结构简单，易于实现，存储密度高。

缺点：不具有随机存储特性；

矩阵中非零元素发生变化时，将会引起三 元组表中大量元素的移动。十字链表h00

00

00

00

00

122

241

31-3

342

00

00

00

35

H1H1H4H2H3H2H5H3A=

0200000010-30020

ijv/nextcptrrptr2023/5/14数据结构1092)十字链表存储结构描述：

typedefstructlnode{inti,j;structlnode*cptr,*rptr;

union{structlnode*next;datatypev;}uval;}link;3)建立十字链表

ijv/nextcptrrptr2023/5/14数据结构110建立十字链表的算法分为两步：

1.建立表头结点的循环链表

2.依次读入非零元素的三元组，每读入一个三元组，生成一个表结点，并将其插入相应行、列链表中的正确位置上。2023/5/14数据结构1115.3广义表的概念广义表(Lists)是n（n>=0)个元素a1,a2,…an的有限序列，其中ai或者是原子或者是一个广义表，通常记为LS=(a1,a2,…,an)1、定义：2023/5/14数据结构112补充说明：对于LS=(a1,a2,…,an)LS:广义表的名字n:广义表的长度。E=(a,E)如果ai是