数据结构完整版教学课件全书电子讲义(最新).ppt

《数据结构完整版教学课件全书电子讲义(最新).ppt》由会员分享，可在线阅读，更多相关《数据结构完整版教学课件全书电子讲义(最新).ppt（352页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构目目 录录 第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 栈和队列栈和队列第四章第四章 字符串、数字符串、数组和广义表组和广义表第五章第五章 树树第六章第六章 图图第七章第七章 查找查找第八章第八章 排序排序1.1 1.1 数据结构与算法数据结构与算法1.1.1、基本概念数据数据：对现实世界的事物采用计算机能识别、存储和处理的形式所进行的描述。简言之，数据是计算机程序能加工和处理的对象或数据就是计算机化的信息。数据元素数据元素：数据的基本单位，又称为结点。在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素可由若干个数据项组成。如一本书的书目信息为一数据元素，

2、而书目信息中的每一项（如书名、作者名等）为一个数据项。数据项是数据的不可分割的最小单元。数据对象数据对象：性质相同的数据元素的集合是数据的一个子集。基本概念(续)数据结构：数据结构：相互之间存在一种或多种特定关系的数据元素的集合。数据结构是指数据对象及其相互关系和构造方法。一个数据结构DS可以形式地用一个二元组表示为：DS=（D，R）其中：D是数据结构中的数据（称为结点）的非空集，R是定义在D上的关系的非空有限集合。结构是指结点之间的关系，数据结构就是结点的有限集合和关系的有限集合。数据结构中，结点及结点间的相互关系是数据的逻辑结构，数据结构在计算机中的存储内容，一般包括结点的值和结点间的关系

3、，数据结构的存储形式是数据的存储结构（或物理结构）基本概念(续)数据结构：数据结构：数据结构按逻辑关系的不同分为线性结构和非 线性结构两大类，其中非线性结构又分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。在计算机中表示信息的最小单位是二进制数的一位叫做位（bit），可以用一个或若干位组合起来形成的一个位串表示一个数据元素或结点。元素或结点可看成是数据元素在计算机中的映象有【顺序映象、非顺序映象】，由此存储结构可分为【顺序存储结构、链式存储结构】。顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助指示元素存储地址的指针表示数据元素之间的

4、逻辑关系。数据类型：数据类型：指某种程序设计语言所允许使用的 变量种类。1.1.2算法的概念和特性 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。在计算机科学中算法则是描述计算机解决给定问题的操作过程。算法的特性是有穷性、确定性、可行性、输入和输出。1、有穷性：求解问题的步骤是有限的，且每一步都可在有限时间内完成。2、确定性：在任何情况下，对同一问题的求解结果必须是唯一的。3、可行性：算法的实现必须在法律上，经济上，技术上都可行。4、输入：没有输入，对问题的求解方法仅能适用于这一个特定问题。5、输出：没有输出，看不到结果，对问题的求解将失去任何意义。

5、1.2 1.2 算法的描述和分析算法的描述和分析1.2.1算法的描述w 算法需要用一种语言来描述，同时，算法可有各种描述方法以满足不同的需求。例如，一个需在计算机上运行的程序（程序也是算法）必须严格按照语法规定用机器语言或汇编语言或高级语言编写，而一个为了人的阅读和交流的算法可以用伪码语言或框图等其它形式来描述。伪码语言是一种包括高级程序语言诉三种基本控制结构（顺序、判定和重复）和自然语言成分的“面向读者”的语言。w 本书采用C语言描述数据结构及相应的算法。1.2.2 算法的分析 一、从时间方面分析w 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。一个算法是由控制结

6、构（顺序、分支和重复三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复的次数作为算法的时间复杂度。算法的时间复杂度通常记作 T（n）=O(f(n)，其中，n为问题的规模，f(n)表示算法中基本操作重复执行的次数是问题规模n的某个函数。上式表示随问题规模n的增大算法执行时的增长率与f(n)的增长率相同。从时间方面分析wf(n)和T(n)是同数量级的函数，大写字母O表示f(n)与T(n)只相差一个常数倍。w算法的时间复杂发表要用数量级的形

7、式表示后，一般可简化为分析循环体内基本操作的执行次数即可。w例1.1：（1）x+;w (2)for(i=1;in;i+)x+;w (3)for(i=1;in;i+)x=x+1;w含基本操作“x增1”的语句x+的频度分别为1，n,n2 则这三上程序段的时间复杂度分别为O（1），O（n）和O（n2）分别称为常量阶，线性阶和平方阶。算法还可呈现的时间复杂度有：对数阶O（log2n），指数阶O（2n）等。算法的分析2w 二、从空间方面分析w类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记为wS(n)=O(f(n)w其中，n为问题的规模（或大小）。算法在运行过程序中需辅助存储空间的大小

8、。在这里我们不多作讨论。举例(1)wP4.二.w下列程序段的时间复杂度是（）。wfor(i=1;i=n;i+)wAi=0;w7.下列程序段的时间复杂度是（）。ws=0;wfor(i=1;i=n;i+)wfor(j=1;j=n;j+)ws=s+bij;wsum=s;举例(2)wP5.三.w1、分析下列程序段的时间复杂度。w.wi=1;wWhile(i=n)wi=i*2;w.举例(3)wP5、三、w5、设n为正数。试确定下列各程序段中前面加记号的语句的频度：i=1;k=0;wWhile(i=n-1)wk+=10*i;wi+;k=0;wfor(i=1;i=n;i+)wfor(j=1;j0时该线性表可

9、记为：（A0,A1,Ai,An-1）其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）和终点(An-1)外，每个数据元素都有且只有一个直接前趋和一个直接后继。Ai+1是Ai的直接前驱，Ai+1是Ai的直接后继。w线性表中的数据元素可以是各式各样的，但同一线性表中的元素必定有相同的特性，即属同数据对象，相邻数据元素辶间存在着有序关系。w线性表是一个相当灵活的数据结构，其表长可根据不同的操作增长或缩短。对线性表进行的基本操作有：存取、插入、删除、合并、分解、查找、排序、求线性表的长度等。2.2 2.2 线性表的顺序存储结构线性表

10、的顺序存储结构2.2.1 顺序分配w线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置，则第i+1个数据元素的存储位置为：loc(Ai)=Loc(A0)+i*L.w因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用语言的一维数组实现，数组的类型随数据元素的属性而定。2.2.2 线性表的操作w 线性表结构简单、易于实现，但插入或删除一个元素时需对其后继的全部元

11、素逐个进行移动（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。所以，这种结构仅适用于数据元素个数不经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。(一)线性表插入操作(1)w 1、在数组中下标为i的元 素前插入一个新元素。w例2.1 某语言程序中，整型数组的个元数组成一个线性表。为了在i位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右：举例（续）w分析：w初始条件V,

12、i,bw执行条件：0i98w执行结果：1 成功w0 不成功wN-S流程图如右：图举例（续）w用函数实现算法如下：wintins1(intV,inti,intb)wintj；wif(i98)wprintf(“Thevalueofiisoutofrangen”)；wreturn0;/*插入失败*/wwfor(j=99；ji；j-)wvj=vj-1;/*后移*/wvi=b；/*插入*/wreturn1；/*插入成功*/w线性表的插入操作（2）2、在有序表中插入一个新元素 例2.2 设有一个有序线性表，用数组结构实现，最大元素个数为n。设当前元素个数是m。要求在该有序表中插入一个值为x的元素。当x=6

13、3时，插入前后的有序表的示意图如右：举例（续）w分析：初始条件：a,n,m,xw插入条件：m=n)printf(“插入失败”);wreturn 0;w/*插入失败*/wfor(i=m-1;i=0&aix;i-)w ai+1=ai;/*后移*/wai+1=x;m+;/*插入*/wreturn 1;/*插入成功*/w（二）线性表的删除(1)1删除下标为i的 数据元素例2.3 为在V0到V99中删除一个元素Vi,引用del1函数。删除前后的线性表的示意图如右 举例（续）分析：初始条件：数组V，删除下标i删除条件：0i99执行结果：1成功,0不成功N-S流程图如右:举例（续）Del1函数定义如下：in

14、t del1(int v,int i)int j;if(i99)printf(“the value of I is out of rangen”);return 0;/*删除失败*/for(j=i;j99;j+)Vj=Vj+1;/*从vI+1到v99逐个前移*/V99=0;/*数组最后一个元素清0或某种结束标记*/return 1;/*删除成功*/线性表的删除操作(2)w2在有序顺序表中删除一个数据元素w例2.4 在有序表中删除一个值为x的数据元素。当x的值为78时删去前后的线性表的w示意图如右：举例（续）w分析：w初始条件：数组a,数组元素个数n,删除元素值 xw查找a中是否有x值的元素：有

15、x,则删除成功，返回1；无x,则删除不成功，返回0。wNS流程图如右：举例（续）w对应算法实现函数如下：wintdel2(inta,intn,intx)winti,j;wfor(j=0;jn;j+)wif(aj=x)i=j;break;wif(j=n)wprintf(“找不到x，删除不成功”);wreturn0;/*找不到x，删除不成功*/wwfor(;idata=ai；-link-data=ai+1。2.3.2 线性链表的运算w设p链表中某一结点的指针，可以说明如下：wNODE *p；w申请一个结点可用C语言的标准存储分配库函数malloc。调用如下：wp=(NODE*)malloc(siz

16、eof(NODE);w当用完后释放结点占用空间时调用函数freew free(p);（一）线性链表的建立w例.5 建立一个如图所示的链表。例2.5 函数定义如下wNODE*create_linklist(NODE*head,int x,int y,int z)w NODE*p,*q;wp=(NODE*)malloc(sizeof(NODE);whead=p;wp-data=x;wq=(NODE*)malloc(sizeof(NODE);wp-link=q;wp=q;wp-data=y;wq=(NODE*)malloc(sizeof(NODE);wp-link=q;wp=q;wp-data=z;

17、wp-link=NULL;wreturn(head);w（二）线性链表的插入操作w设链表结点类型的定义为：wtypedef struct nodew int data;w struct node*link;wNODE;w在链接存储的线性表中插入一个键值为x的新结点，分以下四种不同情况：w1、在某指针P所指结点之后插入；w2、插入首结点之前，使新结点为新的首结点；w3、接在线性表的末尾；w4、在有序链表中插入，使新的线性表依旧有序。分情况讨论（1）1、在线性链表中某指针p所指结点之后插入值为x的结点算法的NS流程图插入结点的函数w函数定义如下：wvoid lq_insl(p,x)wNODE*p;

18、/;/*新结点在P所指结点之后*/wint x;/*新结点的键值*/w NODE*u;wu=(NODE*)malloc(sizeof(NODE);wu-data=x;wu-link=p-link;wp-link=u;w 分情况讨论（2）2、首结点之前插入键值为x的新结点 算法的NS流程图算法的NS流程图首结点之前插新结点函数定义wvoid lq_ins2(hpt,x)wNODE*hpt;/*链表头指针*/wint x;/*新结点的键盘值*/wNODE*u;wu=(NODE*)malloc(sizeof(NODE);wu-data=x;wu-link=hpt;whpt=u;w 分情况讨论（3）3

19、、在链式存储的线性表的末尾接上一个键值为x的新结点算法的NS流程图 线性表末尾接上新结点函数定义 wvoid lq_ins3(hpt,x)wNODE*hpt;/*链表头指针*/wint x;/*新结点的键盘值*/w NODE*u,*p;wu=(NODE)*malloc(sizeof(NODE);wu-data=x;wu-link=null;wif(hpt=null)/*如链表为空链表*/whpt=u;return;ww/*x以链表首结点开始顺序走向末尾结点*/wfor(p=hpt;p-link!=null;p=p-link);wp-link=u;w分情况讨论（4）4、在有序链式存储线性表中插入

20、一键值为X的新结点(假设x=8)算法的NS流程图 有序链式线性表中插入新结点函数wvoikd lq_ins4(hpt,x)/*设链表从小到大有序*/wNODE*hpt;/*链表头指针*/wint x;/*新结点的键值*/wNODE*u,*q,*p;wu=(NODE*)malloc(sizeof(NODE);wu-data=x;/*从链表首结点开始顺序寻找*/wfor(p=htp;p&p-datalink);wif(p=hpt)hpt=u;welse q-link=u;wu-link=pw （三）线性链表的删除操作完成删除算法可有以下几个步骤组成：1、如链表为空链表，则不执行删除操作 2、若链表

21、的首结点的值为指定值，更改链表的头指针为指向首结点的后继结点；3、在链表中找到指定值的结点；4、将找到的结点删除删除操作示意图算法的NS流程图 链表中删除指定值的结点的函数定义 wint lq_delete(hpt,a)wNODE*hpt;/*链表头指针的指针*/wint a;/*要删除的结点键值*/wNODE p,q;wif(q=hpt)=NULL)return 1;/*链表已为空链表*/wif(q-data=a)/*要删除链表的首结点*/w hpt=q-link;/*更改链表头指针*/wfree(q);/*释放被删除结点的空间*/wreturn 0;/*删除成功*/wfor(;q-data

22、!=a&q-link!=NULL;p=q,q=q-link);/*寻找*/wif(q-data=a)/*找到*/w p-link=q-link;/被删除的结点从链表脱钩*/wfree(q);/*释放被删除结点的空间*/wreturn 0;/*删除成功*/wreturn 1;/*没有指定值勤的结点，未执行删除操作*/w2.3.3 循环链表w1.单向循环链表w 循环链表是另一种形式的链式存储结构，将单链表的形式稍加改，让表中最后一个结点的指针域指向单链表的首结点，这样就形成了一个环。如图2-26所示。这种结构从表中任一结点出发均可找到其它结点。w 单向循环链表的基本操作类似于普通链表，差别在于算法

23、中循环条件不在是p或p-link是否为空，而是它们是否等于头指针。2.双向链表w在单链表中，从任何一个结点能通过指针域找到它的一继结点，但要找它的前趋结点，则需从表头出发顺链查找。w双向链表克服了这个缺点。双向链表的每一个结点除数据域外，还包括两个指针域，一个指向该结点的后继结点，另一个指向它的前趋结点，结点结构如图2-27所示。双向链表也可以是循环链表，其结构如图2-28所示示意图双向链表的结点类型可描述如下 struct nodewint data;wstruct node*ulink,*rlink;wwtypedef struct node DNODE;w在循环双向链表中，若P先指向表中

24、结点的指针，则有：w(p-rlink)-llink=(p-link)-rlink=p1、插入w在双向链表中的p结点后插入一个q结点。假设q结点已生成，如图2-29所示w主要操作步骤如下：wq-rlink=p-rlink;wq-llink=p;wp-rlink=q;w(q-rlink)-llink=q;2、删除w在双向链表中删除p结点w主要操作步骤如下：w（p-llink）-rlink=p-link;w(p-rlink)-llink=p-llink;wfree(p);例2-7(1)whead是一个链表的头指针，该链表结点的域由小到大排列。函数insert(head,data)将一个值为data新

25、结点插入到链表中，且保证插入后的链表仍是有序的。请在每组中选择正确答案填空。w#includew#includew#includewtypedefstructnodewwintdata;wstructnode*next;wNODE;例2-7(2)wNODE*insert(NODE*head,intdata)wwNODE*new,*front,*current;wCurrent=head;wWhile(current!=NULL&(1)wwfront=current;wcurrent=current-next;wwnew=(2);wnew-data=data;wnew-next=current;

26、wif(3)whead=new;welsewfront-next=new;wreturnhead;作业P25四.1,2第三章第三章 栈和队列栈和队列 3.1 堆栈 3.2 队列3.1 堆栈3.1.1 堆栈的定义和基本操作w栈（stack）是一种特殊的线性表，这种表只能在其一端（称为栈顶top）进行插入和删除操作,如图2-4-1所示。栈的概念来自存货的堆栈，存货时一件一件往上堆，每次取货时都有只能从上面取。栈的存取特征是后进先出（Last In First Out,缩写为LIFO）。栈顶将随着栈中元素的增减而浮动，通过栈顶指针指明当前栈顶元素位置。栈的固定端称为栈底（bottom），栈底指针并不

27、移动。w栈的基本操作包括：创建一个栈进栈 栈顶 出栈w进栈（push），出栈（pop）w读取栈顶元素，判栈空，w栈清空（初始化），求当前栈w中元素的个数，撤消一个栈等w 栈底3.1.2 顺序存储栈w可用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top（习惯称为栈顶指针，注意与指针变量的区别），top指出栈顶表元素在数组中的下标。当栈为空时，top=0;栈满时，top=MAXN(数组元素个数),如图2-4-1所示。顺序存储栈示意图w wMAXN-1 MAXN-1 top w .w .w .w 1 1wtop-0 0w 栈空 栈满 1、顺序存储栈的进栈操作(

28、1)w顺序存储栈的进栈操作(2)w函数如下：wint push(NODE stack,int maxn,int top,NODE x)/*设栈点的数据类型为NODE，栈空间最多能存maxn个结点*/wif(top=maxn)return 1;/*栈满，进栈失败返回*/wstack top=x;/*完成进栈运算*/w+top;wreturn 0;/*进栈成功，返回0*/w2、顺序存储栈出栈操作(1)顺序存储栈出栈操作(2)w函数如下：wint pop(NODE stack,int top,NODE cp)wif(top=0)return 1;/*栈空，出栈失败返回*/w-top;wcp=stac

29、k top;/*完成出栈运算*/wreturn 0;/*出栈成功，返回*/w3.1.3 链式存储栈w栈也可以用链表实现，用链表实现的栈称为链式栈。链表的第一个元素是栈顶结点，链表的末尾元素是栈底结点，链表的首表指针是栈顶指针top,top为null的空链表是空栈。w设栈结点类型为：wtypedet struct node wNODE data;/*栈元值，某种NODE类型*/wstruct node*link;wLNODE;(一)链式存储栈的进栈函数w示意图 top top=p p-link=topw w p4X52null函数定义w函数如下：wvoid L_push(NODE x,LNODE

30、*top)/*设栈结点的数据类型为NODE*/wLNODE*p=(LNODE*)malloc(sizeof(LNODE);wp-data=x;wp-link=top;wtop=p;w（二）链接存储栈的出栈函数w示意图wTopw p452Null函数定义 int L_pop(NODE*cp,LNODE*top)/*设栈结点的数据类型为NODE*/wLNODE*p=top;wif(top=NULL)return 1;/*空栈*/w*cp=p-data;wtop=p-link;wfree(p);wreturn 0;/*出栈成功*/w3.2 3.2 队队 列列 w一、队列定义、w队列是只允许在一端进行

31、插入，另一端正进行删除的线性表，如图3-7所示。出队 q0 q1 qi qi+1 qn-1 进队 队首 队尾w 图3-7 队列示意图 w队列中允许删除运算的一端称队首，允许插入运算的一端称为队尾。习惯称在队列中插入结点操作为进队，队列中删除结点的操作为出队。w若有队Q=(q0,q1,qn-1),则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出（First In First Out简称FIFO）的特性。w队列的基本操作包括：创建一个队列，入列，出队，读取队首元素，判队空，请队列空，求当前队列中的元素个数，撤消一个队列等。3.2.1 顺序存储队列w可以用顺

32、序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需一个游标变量front（习惯上称为头指针），为了指明当前执行进队运算的队尾位置，需要一个游标变量rear（习惯上称为尾指针）。w开始时，让队列front度rear都指向数组的前端，这是一个空队列。在队列未满情况下，队列可执行进队运算。进队时，首先让rear加1,变为指向队列新结点的存放下标，然后将新结点送到由rear所指的数组元素中。队列非空时，可执行出队运算。出队时，首先把front所指的队列首结点送到接受结点的变量中，然后让front加1，使front指向新的队首结点。出入队列的状态示意图环形队列(1)w若用有MAXN个元素的数

33、组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决方法是当发生这样的情况时，把队列中的结点移到数组的前端，并修改头指针和尾指针。另一种更好的解决办法是采用环形队列。w环形队列就是将实现队列的数组q的首元q0与末元qmax-1连接起来。队空的初态为front=rear=0；在环形队列中，当rear赶上front时，队列满。反之，当front赶上rear时，队列为空。这样队空或队满的条件都同为front=rear，这给程序判别队空或队满带来不便。为此采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法以区

34、别队空和队满。示意图如下：w队列出、入队操作示例：环形队列(2)在下面的入列和出队算法中，queue数组用来存放队列元素，头指针为front，尾指针为rear，数据结构定义如下：#define MAX 50int queueMAX；int front=-1,rear=-1;1、顺序队列的进队列算法：队满时返回eof，否则返回0int insert_queue(int x)if(rear=MAX-1)return(eof);queue+rear=x;return(0);环形队列(3)2、顺序队列出队列算法：队空时返回eof，否则返回y值wint delete_queue()w int y;w i

35、f(front=rear)return(eof);w y=queue+front;w return(y);w3、入循环队列wint inset_q(int q,int x)w int front,rear;w if(rear+1)%MAX)=front)return(eof);welse rear=(rear+1)%MAX;w qrear=x;w return(1);w w环形队列（4）4、出循环队列int delete_q(int q,int y)int front,rear;if(front=rear)return(0);front=(front+1)%MAX;y=qfront;retur

36、n(y);3.2.2链式存储队列 队列也可以用链表实现，用链表实现的队列称为链式队列。链表的第一个表示是队列首结点，链表的末尾表示是队列的队尾结点，队尾结点的链接指针值为null。队列的头指针hpt指向队列的首结点，队列的尾指针tpt指向队尾结点。当队列的头指针hpt值为null时，队列为空。设有：wtypedef struct nodew node data;w struct node*link;w Lnode;一、链式队列进队函数w示意图 tptwhpt p AXnullBCnull链式队列进队函数定义wvoid Len_queue(Lnode*hpt,Lnode*tpt,node x)w

37、 Lnode*p=(Lnode*)malloc(sizeof(Lnode);w p-data=x;w p-link=null;w if(hpt=null)tpt=hpt=p;welse tpt=(=(tpt)-link=p;w 二、链式队列出队函数w示意图 hpt=hpt-link tptwhpt pABCnull链式队列出队函数定义wint Lde_queue(Lnode*hpt,Lnode*tpt,node*cp)w Lnode*p=hpt;w if(hpt=null)return 1;/*队空*/w*cp=(hpt)-data;whpt=(hpt)-link;wif(hpt=null)t

38、pt=null;wfree(p);wreturn 0;w 举例(1)wP33二w1向一个栈顶指针为Top的链栈中插入一个S所指的结点时，其进行的操作是（）。w2从栈顶指针为Top的链栈中删除一个结点，并将结点保存在X中，进行的操作是（）。w3在具有N个单元的循环队列中，队满时共有（）个元素。w4假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为（）。w5设有数组A0.m作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是（）。举例(2)wP33二w6在一个链队中，如果F、R分别为队

39、头、队尾指针，则插入S所指结点的操作是（）。w7栈的逻辑特点是（），队列的逻辑特点是（），二者的共同特点是（）。w8（）可以作为实现递归函数调用的一种数据结构。w9在队列中，新插入的结点只能添加到（）。w10链队在一定范围内不会出现（）的情况，当lq.front=lq.rear时，队中无元素，此时（）。作业wP33三.1第四章第四章 字符串、数组和广义表字符串、数组和广义表 4.1 字符串的基本概念 4.2 字符串的存储结构 4.3 字符串的模式匹配 4.4 数组的基本概念 4.5 矩阵的压缩存储 4.6 广义表 4.1字符串基本概念字符串基本概念w字符已成为非数值应用重要的处理对象.如文字编

40、辑,情报检索,自然语言翻译和各种事务处理系统等。w字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时,称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的串相应地称为主串。在C语言中,字符串常量是用一对双引导括起来若干字符来表示。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示.w例4.1:假如a,b,c,d为如下的四个串:wa=“BEI”,b=“JING”wc=“BEIJING”,d=“BEIJING”w则它们的长度为：3，4，7和8

41、；并且a和b都是c和d的子串；a在c和d中的位置都是1；而b在c中的位置是在d中的位置是5。w另外，每个字符串的最后一个有效字符之后有一个字符串结束符，记为0。字符串通常存于足够大的字符数组中。w如要称两个串是相等的，当且仅当这两面个串的值相等。也就是说，只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。4.24.2字符串的存储结构字符串的存储结构w对于字符串常量，只需作为一个字符的序列存储。对于字符串变量，赋给它一个串名，对串运算时，通过变量名访问其值。其存储分配有两种形式，一是将字符串设计成一种结构类型（如pascal语言和c语言中，字符串都是用字符数组来实现），从字符串名可直接

42、访问到字符串值，字符串值的存储分配是在编译时完成的；另一是字符串值的存储分配在程序运行时完成，在字符串名和字符串值之间需建立一个对照表（称为串名的存储映象），字符串的访问通过串名的存储映象进行。我们称前一种为顺序存储结构，后一种为链式存储结构。4.2.14.2.1串的存储结构串的存储结构w 和线性表的顺序存储结构类似，用一组地址连续的存储单元存储串的字符序列。在C语言中用一维数组来实现。w（一）紧缩格式w假定，一个存储单元可存放K个字符，而且给出的串长度为N，那么此字符串的字符串值就要占N/K个存储单元w紧缩格式是以字符为单位依次将字符存放在存储单元里。（PASCAL语言中的紧缩数组）w（二）

43、非紧缩格式w在一个存储单元中存放一个字符，所需存储单元个数就是串长。紧缩格式可节省存储空间，但在进行串运算时需要花费较时间去分离同一存储单元中的字符。4.2.2串的链式存储结构w和线性表的链式存储结构类似，也可采用链表方式存储串值。由于串结构的特殊性结构中的每个数据元素是一个字符，则可用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可存放多个字符。w head w 结点大小为4示图w head w 结点大小为1示图 ABDCEFGHI000A B C D 4.3 字符串的模式匹配字符串的模式匹配w设s和t是给定的两个串，在串s中寻找等于t的子串的位置的过程称为模式匹

44、配，其中，s串称为主串，t串称为模式，如在s中找到等于t的子串，则称匹配成功，并返回模式t在s串的序号：反之匹配失败，并返回于序号为零。w例4.2:w 1、s=“abcdefg”,t=“efg”w则模式t在主串s中的序号等于5w2、s=“abcdefg”,t=“abcdg”w则t在s中的序号等于0w3s=“abcdefabc”,t=“abc”w如从s串的第一个字符开始搜索则序号等于1；如从s第三个字符开始搜索，则序号等于7。4.3.1模式匹配的BF算法w算法的基本思想是：从主串s的第一个字符起和模式的第一趟匹配。第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起再重新和

45、模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为零。w如果s=“ababcabcacbab”wt=“abcac”t在s中的模式匹配过程如下w i=2w第一趟匹配 a b a b c a b c a c b a bw a b cw j=2w i=1w第二趟匹配 a b a b c a b c a c b a b w a w j=0w i=6w第三趟匹配 a b a b c a b c a c b a b w a b c a cw j=4w i=3 t在s中的模

46、式匹配过程(续)w i=3w第四趟匹配 a b a b c a b c a c b a b w aw j=0w i=4w第五趟匹配 a b a b c a b c a c b a b w a j=0w w i=10w第六趟匹配 a b a b c a b c a c b a bw a b c a c w j=5w方法一：BF算法的实现函数：wintindex(chars,chart,intstart)wintI,j,m,n;wm=strlen(s);wn=strlen(t);wif(startm+1|n=0)return(0);welsewi=start;/*从S中的第start位开始匹配*/

47、wj=0;wwhile(im&j=n)return(i-n);welsereturn(0);ww方法二：BF算法也可用如下函数表示：wintsimplematch(char*s,char*t)wintn=strlen(s),m=strlen(t),i,j,k;wfor(j=0;jn-m;j+)/*顺序考察从si开始的子串*/wfor(i=0;im&sj+i=ti;i+)/*从sj开始的子串与t比较*/wif(i=m)returnj+1;wwreturn0w4.3.2模式匹配的KMP算法w在执行简单匹配算法中的字符比较过程中，当出现sj+I!=tI时，有ws0sj,sj+1 sj+i-1,sj+

48、i w !=wt0 t1 ti-1 ti w这时，简单匹配算法对字符串S要回溯，回溯到从sj+1开始继续与模式字符串T从头开始逐一字符比较，KMP算法是对正文字符串比较不回溯的算法。如果对于模式字符串t存在一个整数k(kp&*q-1=)/*设定字符串的结束符*/w15（4）;w16else*q=0;w17return (5);w18w19voidmain()w20w21charstr=”weareChinese“w22printf(“%sn”,sdel(str);w234.4 4.4 数组的基本概念数组的基本概念在概念上，数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素

49、对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。在C语言中，约定数组的第一个元素的下标为0，其余依次类推，由n个元素组成的数组，其最后一个元素的下标为n-1。数组元素可以是任何类型的，当元素本身又是数组时就构成多维数组。数组通常是顺序存储的，对于多维数组，C语言按行优先顺序存放。如有以下数组定义：int a110,a289,a3789；则数组a1是一维数组，a2是二维数组，a3是三维数组。记元素X的内存地址为Loc(x),设每个元素所需内存字节数为s，存储元素a1 i,a2ij,a3ijk的内存地址分别可由以下算式确定：内存地址计算wLoc(a1i)=Lo

50、c(a10)+i*swLoc(a2 ij)=Loc(a200)+(i*9+j)*swLoc(a3ijk)=Loc(a3000)+(i*8+j)*9+k)*sw若用C语言的指针来描述，以上算式可分别简成：w&a1i=&a10+iw&a2ij=&a200+i*9+jw&a3ijk)=&a3000+(i*8+j)*9+kw当然数组也可按列优先顺序存放。4.5 4.5 矩阵的压缩存储矩阵的压缩存储4.5.1 特殊矩阵的压缩特殊矩阵：假若值相同的数据元素或者零元 素在矩阵的分布有一定的规律，则我们称此类矩为特殊矩阵。1对称矩阵 若一个n阶矩阵A中的元素满足下述性质：aij=aji,0i,jn-1则称为n