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

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

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

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

4、法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。在计算机科学中算法则是描述计算机解决给定问题的操作过程。 算法的特性是有穷性、确定性、可行性、输入和输出。1、有穷性：求解问题的步骤是有限的，且每一步都可在有限时间内完成。2、确定性：在任何情况下，对同一问题的求解结果必须是唯一的。 3、可行性：算法的实现必须在法律上，经济上，技术上都可行。4、输入：没有输入，对问题的求解方法仅能适用于这一个特定问题。5、输出：没有输出，看不到结果，对问题的求解将失去任何意义。1.2 算法的描述和分析1.2.1算法的描述 算法需要用一种语言来描述，同时，算法可有各种描述方法

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

6、法，通常的做法是，从算法中选取一种对于所研究的的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复的次数作为算法的时间复杂度。算法的时间复杂度通常记作 T（n）=O(f(n) ，其中，n为问题的规模，f(n)表示算法中基本操作重复执行的次数是问题规模n的某个函数。上式表示随问题规模n的增大算法执行时的增长率与f(n)的增长率相同。从时间方面分析f(n)和T(n)是同数量级的函数，大写字母O表示f(n)与T(n)只相差一个常数倍。算法的时间复杂发表要用数量级的形式表示后，一般可简化为分析循环体内基本操作的执行次数即可。例1.1：（1）x+; (2) for(i=1;in;i+)x+; (

7、3) for(i=1;in;i+)x=x+1;含基本操作“x增1”的语句x+的频度分别为1，n, n2 则这三上程序段的时间复杂度分别为O（1），O（n）和O（n2）分别称为常量阶，线性阶和平方阶。算法还可呈现的时间复杂度有：对数阶O（log2n），指数阶O（2n）等。算法的分析2 二、从空间方面分析类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记为S(n)=O(f(n)其中，n为问题的规模（或大小）。算法在运行过程序中需辅助存储空间的大小。在这里我们不多作讨论。举例 (1)P4.二.下列程序段的时间复杂度是（）。for (i=1;i=n;i+) Ai=0;7.下列程序段的时

8、间复杂度是（）。 s=0;for (i=1;i=n;i+) for (j=1;j=n;j+) s=s+bi j;sum=s;举例 (2)P5.三.1、分析下列程序段的时间复杂度。. i=1;While(i=n) i=i*2; .举例 (3)P5、三、5、设n为正数。试确定下列各程序段中前面加记号的语句的频度：i=1;k=0;While(i=n-1)k+=10*i;i+; k=0;for(i=1;i=n;i+)for(j=1;j0时该线性表可记为：（A0,A1,Ai,An-1）其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）

9、和终点(An-1)外，每个数据元素都有且只有一个直接前趋和一个直接后继。Ai+1是Ai的直接前驱，Ai+1是Ai的直接后继。线性表中的数据元素可以是各式各样的，但同一线性表中的元素必定有相同的特性，即属同数据对象，相邻数据元素辶间存在着有序关系。线性表是一个相当灵活的数据结构，其表长可根据不同的操作增长或缩短。对线性表进行的基本操作有：存取、插入、删除、合并、分解、查找、排序、求线性表的长度等。 2.2 线性表的顺序存储结构2.2.1 顺序分配线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数

10、据元素的存储位置，则第i+1个数据元素的存储位置为： loc(Ai)=Loc(A0)+i*L.因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用语言的一维数组实现，数组的类型随数据元素的属性而定。2.2.2 线性表的操作 线性表结构简单、易于实现，但插入或删除一个元素时需对其后继的全部元素逐个进行移动（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。所以，这种结构仅适用于数据元素个数不

11、经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。 (一)线性表插入操作(1) 1、在数组中下标为i的元 素前插入一个新元素。例2.1 某语言程序中，整型数组的个元数组成一个线性表。为了在i位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右： 举例（续）分析：初始条件V,i,b执行条件：0i98执行结果：1 成功0 不成功N-S流程图如右： 图举例（续） 用函数实现算法如下： int ins1( int V , int i, int b) int j；if(i9

12、8) printf(“The value of i is out of rangen”)； return 0; /*插入失败*/ for (j=99；ji；j-) vj=vj-1;/*后移*/ vi=b； /*插入*/return 1； /*插入成功 */线性表的插入操作（2）2、在有序表中插入一个新元素 例2.2 设有一个有序线性表，用数组结构实现，最大元素个数为n。设当前元素个数是m。要求在该有序表中插入一个值为x的元素。当x=63时，插入前后的有序表的示意图如右： 举例（续）分析：初始条件：a,n,m,x插入条件：m=n) printf(“插入失败”);return 0; /*插入失败*

13、/for(i=m-1; i=0& aix ;i-) ai+1=ai; /*后移*/ai+1=x; m+; /*插入*/return 1; /*插入成功 */（二）线性表的删除(1)1删除下标为i的 数据元素例2.3 为在V0到V99中删除一个元素Vi,引用del1函数。删除前后的线性表的示意图如右 举例（续）分析：初始条件： 数组V，删除下标i删除条件：0i99执行结果：1成功,0不成功N-S流程图如右: 举例（续）Del1函数定义如下：int del1 (int v ,int i )int j;if (i99) printf(“the value of I is out of rangen”

14、);return 0; /*删除失败*/for (j=i; j99; j+) Vj=Vj+1; /*从vI+1到v99逐个前移*/ V99=0; /*数组最后一个元素清0或某种结束标记*/return 1; /*删除成功 */线性表的删除操作(2)2在有序顺序表中删除一个数据元素例2.4 在有序表中删除一个值为x的数据元素。当x的值为78时删去前后的线性表的示意图如右：举例（续）分析：初始条件：数组a, 数组元素个数n,删除元素值 x查找a中是否有x值的元素：有x,则删除成功，返回1；无x,则删除不成功，返回0。NS流程图如右：举例（续）对应算法实现函数如下：int del2(int a,in

15、t n,int x)int i,j;for(j=0;jn;j+) if(aj= =x)i=j;break;if (j= =n) printf(“找不到x，删除不成功”);return 0; /*找不到x，删除不成功*/for(;idata=ai； -link-data=ai+1。 2.3.2 线性链表的运算设p链表中某一结点的指针，可以说明如下：NODE *p；申请一个结点可用C语言的标准存储分配库函数malloc。调用如下：p = (NODE * ) malloc ( sizeof (NODE);当用完后释放结点占用空间时调用函数free free(p); （一）线性链表的建立例.5 建立一

16、个如图所示的链表。例2.5 函数定义如下NODE * create_linklist(NODE * head,int x,int y,int z) NODE * p, *q;p=(NODE *)malloc(sizeof(NODE);head=p;p-data=x;q=(NODE *)malloc(sizeof(NODE);p-link=q;p=q;p-data=y;q=(NODE *)malloc(sizeof(NODE);p-link=q;p=q;p-data=z;p-link=NULL;return (head);（二）线性链表的插入操作设链表结点类型的定义为：typedef struc

17、t node int data; struct node *link;NODE;在链接存储的线性表中插入一个键值为x的新结点，分以下四种不同情况：1、在某指针P所指结点之后插入；2、插入首结点之前，使新结点为新的首结点；3、接在线性表的末尾；4、在有序链表中插入，使新的线性表依旧有序。 分情况讨论（1）1、在线性链表中某指针p所指结点之后插入值为x的结点算法的NS流程图 插入结点的函数函数定义如下：void lq_insl(p,x)NODE *p; /*新结点在P所指结点之后*/int x; /*新结点的键值*/ NODE *u;u=(NODE *)malloc(sizeof(NODE);u-

18、data=x;u-link=p-link;p-link=u; 分情况讨论（2）2、首结点之前插入键值为x的新结点 算法的NS流程图 算法的NS流程图 首结点之前插新结点函数定义void lq_ins2(hpt,x)NODE *hpt; /*链表头指针*/int x; /*新结点的键盘值*/NODE *u;u=(NODE *)malloc(sizeof(NODE);u-data=x;u-link=hpt;hpt=u; 分情况讨论（3）3、在链式存储的线性表的末尾接上一个键值为x的新结点算法的NS流程图 线性表末尾接上新结点函数定义 void lq_ins3(hpt,x)NODE *hpt; /*

19、链表头指针*/int x; /*新结点的键盘值*/ NODE*u,*p;u=(NODE)*malloc(sizeof(NODE);u-data=x;u-link=null;if (hpt=null) /*如链表为空链表*/hpt=u;return;/*x以链表首结点开始顺序走向末尾结点*/for( p=hpt; p-link!=null;p= p-link);p-link=u;分情况讨论（4）4、在有序链式存储线性表中插入一键值为X的新结点(假设x=8)算法的NS流程图 有序链式线性表中插入新结点函数voikd lq_ins4 (hpt,x) /*设链表从小到大有序*/NODE *hpt; /

20、*链表头指针*/int x; /*新结点的键值*/NODE *u,*q,*p;u=(NODE *)malloc(sizeof(NODE);u-data=x; /*从链表首结点开始顺序寻找*/for(p=htp;p&p-datalink);if(p= =hpt) hpt=u;else q-link=u;u-link=p （三）线性链表的删除操作完成删除算法可有以下几个步骤组成： 1、如链表为空链表，则不执行删除操作 2、若链表的首结点的值为指定值，更改链表的头指针为指向首结点的后继结点； 3、在链表中找到指定值的结点； 4、将找到的结点删除删除操作示意图算法的NS流程图 链表中删除指定值的结点的

21、函数定义 int lq_delete(hpt,a)NODE *hpt; /*链表头指针的指针*/int a; /*要删除的结点键值*/NODE p,q; if(q=hpt)=NULL) return 1; /*链表已为空链表*/if(q-data=a) /*要删除链表的首结点*/ hpt=q-link; /*更改链表头指针*/free(q); /*释放被删除结点的空间*/return 0; /*删除成功*/for( ; q-data!=a&q-link!=NULL;p=q,q=q-link); /*寻找*/if(q-data=a) /*找到*/ p-link=q-link; /被删除的结点从链

22、表脱钩*/free(q); /*释放被删除结点的空间*/return 0; /*删除成功*/return 1; /*没有指定值勤的结点，未执行删除操作*/2.3.3 循环链表1.单向循环链表 循环链表是另一种形式的链式存储结构，将单链表的形式稍加改，让表中最后一个结点的指针域指向单链表的首结点，这样就形成了一个环。如图2-26所示。这种结构从表中任一结点出发均可找到其它结点。 单向循环链表的基本操作类似于普通链表，差别在于算法中循环条件不在是p或p-link是否为空，而是它们是否等于头指针。 2.双向链表在单链表中，从任何一个结点能通过指针域找到它的一继结点，但要找它的前趋结点，则需从表头出发

23、顺链查找。双向链表克服了这个缺点。双向链表的每一个结点除数据域外，还包括两个指针域，一个指向该结点的后继结点，另一个指向它的前趋结点，结点结构如图2-27所示。双向链表也可以是循环链表，其结构如图2-28所示示意图双向链表的结点类型可描述如下 struct nodeint data;struct node *ulink,*rlink;typedef struct node DNODE;在循环双向链表中，若P先指向表中结点的指针，则有：(p-rlink)-llink=(p-link)-rlink=p1、插入在双向链表中的p结点后插入一个q结点。假设q结点已生成，如图2-29所示 主要操作步骤如下

24、：q-rlink=p-rlink;q-llink=p;p-rlink=q;(q-rlink)-llink=q; 2、删除在双向链表中删除p结点主要操作步骤如下：（p-llink）-rlink=p-link;(p-rlink)-llink=p-llink;free(p); 例 2-7(1)head是一个链表的头指针，该链表结点的域由小到大排列。函数insert(head,data)将一个值为data新结点插入到链表中，且保证插入后的链表仍是有序的。请在每组中选择正确答案填空。 #include#include #include typedef struct nodeint data;struct

25、 node *next;NODE;例 2-7(2)NODE *insert(NODE *head,int data) NODE *new ,*front, *current; Current=head;While(current!=NULL& (1) ) front=current; current=current-next;new= (2) ;new-data=data;new-next=current;if ( (3) ) head=new;else front-next=new;return head;作业P25 四.1,2第三章 栈和队列 3.1 堆栈 3.2 队列3.1 堆栈3.1.

26、1 堆栈的定义和基本操作栈（stack）是一种特殊的线性表，这种表只能在其一端（称为栈顶top）进行插入和删除操作,如图2-4-1所示。栈的概念来自存货的堆栈，存货时一件一件往上堆，每次取货时都有只能从上面取。栈的存取特征是后进先出（Last In First Out,缩写为LIFO）。栈顶将随着栈中元素的增减而浮动，通过栈顶指针指明当前栈顶元素位置。栈的固定端称为栈底（bottom），栈底指针并不移动。栈的基本操作包括：创建一个栈进栈 栈顶 出栈进栈（push），出栈（pop）读取栈顶元素，判栈空，栈清空（初始化），求当前栈中元素的个数，撤消一个栈等 栈底3.1.2 顺序存储栈可用顺序存储线

27、性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top（习惯称为栈顶指针，注意与指针变量的区别），top指出栈顶表元素在数组中的下标。当栈为空时，top =0;栈满时，top=MAXN(数组元素个数),如图2-4-1所示。顺序存储栈示意图 MAXN-1 MAXN-1 top . . . . . . 1 1top-0 0 栈空 栈满 1、顺序存储栈的进栈操作(1) 顺序存储栈的进栈操作(2)函数如下：int push(NODE stack,int maxn,int top,NODE x)/*设栈点的数据类型为NODE，栈空间最多能存maxn个结点*/if (top=max

28、n) return 1; /*栈满，进栈失败返回*/stack top=x; /*完成进栈运算*/+top;return 0; /*进栈成功，返回0*/2、顺序存储栈出栈操作(1)顺序存储栈出栈操作(2)函数如下：int pop(NODE stack,int top,NODE cp)if(top=0) return 1; /*栈空，出栈失败返回*/-top; cp=stacktop; /*完成出栈运算*/return 0; /*出栈成功，返回*/3.1.3 链式存储栈栈也可以用链表实现，用链表实现的栈称为链式栈。链表的第一个元素是栈顶结点，链表的末尾元素是栈底结点，链表的首表指针是栈顶指针to

29、p ,top为null的空链表是空栈。设栈结点类型为：typedet struct node NODE data; /*栈元值，某种NODE类型*/struct node *link;LNODE;(一) 链式存储栈的进栈函数示意图 top top=p p-link=top p4 X 5 2 null函数定义函数如下：void L_push(NODE x,LNODE *top) /*设栈结点的数据类型为NODE*/LNODE *p=(LNODE *)malloc(sizeof(LNODE);p-data=x;p-link=top;top=p;（二 ）链接存储栈的出栈函数示意图Top p4 5 2

30、 Null 函数定义 int L_pop(NODE *cp,LNODE *top) /*设栈结点的数据类型为NODE*/LNODE *p=top;if(top=NULL) return 1;/*空栈*/*cp=p-data;top=p-link;free(p);return 0;/*出栈成功*/3.2 队 列 一、队列定义、队列是只允许在一端进行插入，另一端正进行删除的线性表，如图3-7所示。 出队 q0 q1 qi qi+1 qn-1 进队 队首 队尾 图3-7 队列示意图 队列中允许删除运算的一端称队首，允许插入运算的一端称为队尾。习惯称在队列中插入结点操作为进队，队列中删除结点的操作为出

31、队。若有队Q=(q0,q1,qn-1),则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出（First In First Out简称FIFO）的特性。队列的基本操作包括：创建一个队列，入列，出队，读取队首元素，判队空，请队列空，求当前队列中的元素个数，撤消一个队列等。3.2.1 顺序存储队列可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需一个游标变量front（习惯上称为头指针），为了指明当前执行进队运算的队尾位置，需要一个游标变量rear（习惯上称为尾指针）。开始时，让队列front度rear都指向数组的前端，这是一个空队列。在队

32、列未满情况下，队列可执行进队运算。进队时，首先让rear加1,变为指向队列新结点的存放下标，然后将新结点送到由rear所指的数组元素中。队列非空时，可执行出队运算。出队时，首先把front所指的队列首结点送到接受结点的变量中，然后让front加1，使front指向新的队首结点。出入队列的状态示意图环形队列(1)若用有MAXN个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决方法是当发生这样的情况时，把队列中的结点移到数组的前端，并修改头指针和尾指针。另一种更好的解决办法是采用环形队列。环形队列就是将实

33、现队列的数组q的首元q0与末元qmax-1连接起来。队空的初态为front=rear=0；在环形队列中，当rear赶上front时，队列满。反之，当front赶上rear时，队列为空。这样队空或队满的条件都同为front=rear，这给程序判别队空或队满带来不便。为此采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法以区别队空和队满。示意图如下：队列出、入队操作示例： 环形队列(2)在下面的入列和出队算法中，queue数组用来存放队列元素，头指针为front，尾指针为rear，数据结构定义如下：#define MAX 50int queueMAX；int front=-1,rear

34、= -1;1、顺序队列的进队列算法：队满时返回eof，否则返回0int insert_queue (int x) if (rear= =MAX-1) return(eof); queue+rear=x; return(0);环形队列(3)2、顺序队列出队列算法：队空时返回eof，否则返回y值int delete_queue() int y ; if (front= =rear) return(eof); y=queue+front; return(y);3、入循环队列int inset_q(int q, int x) int front,rear; if (rear+1)%MAX)= =fro

35、nt) return(eof);else rear=(rear+1)%MAX; qrear=x; return(1); 环形队列（4）4、出循环队列int delete_q(int q, int y) int front,rear; if(front= = rear) return(0); front=(front+1)%MAX; y=qfront; return(y);3.2.2链式存储队列 队列也可以用链表实现，用链表实现的队列称为链式队列。链表的第一个表示是队列首结点，链表的末尾表示是队列的队尾结点，队尾结点的链接指针值为null。队列的头指针hpt指向队列的首结点，队列的尾指针tpt指

36、向队尾结点。当队列的头指针hpt值为null时，队列为空。设有：typedef struct node node data; struct node *link; Lnode;一、链式队列进队函数示意图 tpthpt p A X nullB C null链式队列进队函数定义void Len_queue(Lnode *hpt,Lnode *tpt,node x) Lnode *p=(Lnode *)malloc(sizeof(Lnode); p-data=x; p-link=null; if (hpt= =null)tpt=hpt=p;else tpt = (tpt)-link=p; 二、链式队

37、列出队函数示意图 hpt=hpt-link tpthpt pA B C null链式队列出队函数定义int Lde_queue(Lnode *hpt,Lnode *tpt,node *cp) Lnode *p= hpt; if(hpt= =null) return 1; /* 队空*/*cp= (hpt)-data;hpt=(hpt)-link;if(hpt= = null) tpt=null;free (p);return 0; 举例(1)P33 二1向一个栈顶指针为Top的链栈中插入一个S所指的结点时，其进行的操作是（ ）。2从栈顶指针为Top的链栈中删除一个结点，并将结点保存在X中，进行

38、的操作是（ ）。3在具有N个单元的循环队列中，队满时共有（ ）个元素。4假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为（ ）。5设有数组A0.m作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是（ ）。举例(2)P33 二6在一个链队中，如果F、R分别为队头、队尾指针，则插入S所指结点的操作是（ ）。7栈的逻辑特点是（ ），队列的逻辑特点是（ ），二者的共同特点是（ ）。8（ ）可以作为实现递归函数调用的一种数据结构。9在队列中，新插入的结点只能添加到（ ）。10链队在一定范

39、围内不会出现（ ）的情况，当lq.front= =lq.rear时，队中无元素，此时（ ）。 作业P33 三.1第四章 字符串、数组和广义表 4.1 字符串的基本概念 4.2 字符串的存储结构 4.3 字符串的模式匹配 4.4 数组的基本概念 4.5 矩阵的压缩存储 4.6 广义表 4.1字符串基本概念字符已成为非数值应用重要的处理对象.如文字编辑,情报检索,自然语言翻译和各种事务处理系统等。字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时,称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子

40、串的串相应地称为主串。在C语言中,字符串常量是用一对双引导括起来若干字符来表示。通常称字符在序列中的序号为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示.例4.1:假如a,b,c,d为如下的四个串:a=“BEI”,b=“JING”c=“BEIJING”,d=“BEI JING”则它们的长度为：3，4 ，7和8；并且a和b都是c和d的子串；a在c和d中的位置都是1；而b在c中的位置是在d中的位置是5。另外，每个字符串的最后一个有效字符之后有一个字符串结束符，记为0。字符串通常存于足够大的字符数组中。如要称两个串是相等的，当且仅当这两面个串的值相等。也就是说，只有当

41、两个串的长度相等，并且各对应位置的字符都相等时才相等。4.2字符串的存储结构对于字符串常量，只需作为一个字符的序列存储。对于字符串变量，赋给它一个串名，对串运算时，通过变量名访问其值。其存储分配有两种形式，一是将字符串设计成一种结构类型（如pascal语言和c语言中，字符串都是用字符数组来实现），从字符串名可直接访问到字符串值，字符串值的存储分配是在编译时完成的；另一是字符串值的存储分配在程序运行时完成，在字符串名和字符串值之间需建立一个对照表（称为串名的存储映象），字符串的访问通过串名的存储映象进行。我们称前一种为顺序存储结构，后一种为链式存储结构。4.2.1串的存储结构 和线性表的顺序存储

42、结构类似，用一组地址连续的存储单元存储串的字符序列。在C语言中用一维数组来实现。（一）紧缩格式假定，一个存储单元可存放K个字符，而且给出的串长度为N，那么此字符串的字符串值就要占N/K个存储单元紧缩格式是以字符为单位依次将字符存放在存储单元里。（PASCAL语言中的紧缩数组）（二）非紧缩格式在一个存储单元中存放一个字符，所需存储单元个数就是串长。紧缩格式可节省存储空间，但在进行串运算时需要花费较时间去分离同一存储单元中的字符。4.2.2串的链式存储结构和线性表的链式存储结构类似，也可采用链表方式存储串值。由于串结构的特殊性结构中的每个数据元素是一个字符，则可用链表存储串值时，存在一个“结点大小

43、”的问题，即每个结点可以存放一个字符，也可存放多个字符。 head 结点大小为4示图 head 结点大小为1示图 ABDCEFGHI000A B C D 4.3 字符串的模式匹配设s和t是给定的两个串，在串s中寻找等于t的子串的位置的过程称为模式匹配，其中，s串称为主串，t串称为模式，如在s中找到等于t的子串，则称匹配成功，并返回模式t在s串的序号：反之匹配失败，并返回于序号为零。例4.2 : 1、s=“abcdefg”,t=“efg” 则模式t在主串s中的序号等于52、s=“abcdefg”,t=“abcdg”则t在s中的序号等于03s=“abcdefabc”,t=“abc”如从s串的第一个

44、字符开始搜索则序号等于1；如从s第三个字符开始搜索，则序号等于7。4.3.1模式匹配的BF算法算法的基本思想是：从主串s的第一个字符起和模式的第一趟匹配。第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配过程如下 i=2第一趟匹配 a b a b c a b c a c b a b a b c j=2

45、i=1第二趟匹配 a b a b c a b c a c b a b a j=0 i=6第三趟匹配 a b a b c a b c a c b a b a b c a c j=4 i=3 t在s中的模式匹配过程(续) i=3第四趟匹配 a b a b c a b c a c b a b a j=0 i=4第五趟匹配 a b a b c a b c a c b a b a j=0 i=10第六趟匹配 a b a b c a b c a c b a b a b c a c j=5方法一： BF算法的实现函数：int index(char s,char t, int start) int I,j,m

46、,n; m=strlen(s); n=strlen(t);if(startm+1 | n=0) return(0);else i=start; /*从S中的第start位开始匹配*/ j=0; while(im & j=n) return(i-n); else return(0); 方法二：BF算法也可用如下函数表示： int simple match(char *s,char *t) int n=strlen(s),m=strlen(t),i,j,k; for(j=0;jn-m;j+) /*顺序考察从si开始的子串*/ for(i=0;im&sj+i=ti;i+) /* 从sj开始的子串与t

47、比较*/ if(i= =m) return j+1; return 0 4.3.2模式匹配的KMP算法在执行简单匹配算法中的字符比较过程中，当出现sj+I!=tI时，有s0sj,sj+1 sj+i-1,sj+i != t0 t1 ti-1 ti 这时，简单匹配算法对字符串S要回溯，回溯到从sj+1开始继续与模式字符串T从头开始逐一字符比较，KMP算法是对正文字符串比较不回溯的算法。如果对于模式字符串t存在一个整数k(kp&*q-1= = ) /* 设定字符串的结束符*/ 15 （4） ; 16 else *q=0; 17 return (5) ; 18 19 void main() 20 21

48、 char str =”we are Chinese “ 22 printf(“%sn”,sdel(str); 23 4.4 数组的基本概念在概念上，数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。在C语言中，约定数组的第一个元素的下标为0，其余依次类推，由n个元素组成的数组，其最后一个元素的下标为n-1。数组元素可以是任何类型的，当元素本身又是数组时就构成多维数组。数组通常是顺序存储的，对于多维数组，C语言按行优先顺序存放。如有以下数组定义： int a110,a289,a3789；

49、则数组a1是一维数组，a2是二维数组，a3是三维数组。记元素X的内存地址为Loc(x),设每个元素所需内存字节数为s，存储元素a1 i,a2ij,a3ijk的内存地址分别可由以下算式确定：内存地址计算Loc(a1i)=Loc(a10)+i*sLoc(a2 ij)=Loc(a200)+(i*9+j)*sLoc(a3ijk)=Loc(a3000)+(i*8+j)*9+k)*s若用C语言的指针来描述，以上算式可分别简成： &a1i=&a10+i &a2ij=&a200+i*9+j &a3ijk)=& a3000+(i*8+j)*9+k当然数组也可按列优先顺序存放。4.5 矩阵的压缩存储4.5.1 特

50、殊矩阵的压缩特殊矩阵：假若值相同的数据元素或者零元 素在矩阵的分布有一定的规律，则我们称此类矩为特殊矩阵。1对称矩阵 若一个n阶矩阵A中的元素满足下述性质：aij=aji , 0i,jn-1则称为n阶对称矩阵。 一维数组下标k与i,j对应关系k= i(i+1)/2+j 当ij(下三角存贮) j(j-1)/2+i 当ij(上三角存贮) 如一一对应需n2个存储单元的矩阵压缩存储仅需1+2+3+ +n= n(n+1)/2 个存储单元。下三角存储数组sak ，如图4-7所示。则LocAij=LocA00+(i(i+1)/2)+j*s 2、三角矩阵若一个n阶矩阵中的元素满足下述性质；当ij时aij=0且

51、oi,jn-1则称为上三角矩阵。下三角矩阵示图 3、对角矩阵所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素皆为零。地址计算公式：LocAij=LocA00+i(2d+1)+(2d+1)+(j-i)*s 4.5.2 稀疏矩阵当非零元素的个数只占矩阵元素总数的25%30%或低于这个有百分数时，我们称这样的矩阵为稀疏矩阵。 1、用三元组数组表示稀疏矩阵可以用一元组（i,j,aij）唯一确定矩阵中的非零元素压缩存储概念，只存稀疏矩阵的非零元素。图4-9稀疏矩阵可表示为（0，1，12），（1，0，7）（1，4，1）（2，2

52、，8）（3，1，6）（4，0，18）（4，2，7）的一维数组。在C语言描述算法的数据结构定义如下：#define MAX 100struct node int row;int colum;int value;tyredef struct node NODE;NODE maxMAX;2、稀疏矩阵的十字链表表示法：在十字链表中，稀疏矩阵的每一行用一个带表头节点的循环表示，每一列也用一个带表头的循环链表表示。在这个结构中，除表头节点外，每一个节点都代表矩阵中的一个非零元素，它由五个域组成；行域（row），列域（col）,值域(val),向下域(down)和向右域(right)。节点结构和存储表示如下

53、： 表结点 行（列）头结点 表头结点 Down rowrightcowvolrightdown00linkmnlink举例（）若有矩阵M如下: 例题目：求一个3*3矩阵对角线元素之和 1.程序分析：利用双重for循环控制输入二维数组，再将aii累加后输出。2.程序源代码：#include void main()float a33,sum=0;int i,j;printf(please input rectangle element:n);for(i=0;i3;i+)for(j=0;j3;j+)scanf(%f,&aij);for(i=0;i3;i+)sum=sum+aii;printf(dui

54、jiaoxian he is %6.2f,sum);例题目：将一个数组逆序输出。1.程序分析：用第一个与最后一个交换。2.程序源代码： #define N 5vod main() int aN=9,6,5,4,1,i,temp;printf(n original array:n);for(i=0;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+)temp=ai;ai=aN-i-1;aN-i-1=temp;printf(n sorted array:n);for(i=0;itag) x= (4) ; else x= (5) ; if(x) return ( (6) );

55、return 0; 作业P56 二.4P57 三.1,4第五章 树 5.1 树的定义和术语 5.2 二叉树 5.3遍历二叉树 5.4 线索二叉树 5.5 树和森林 5.6 树的应用 5.1 树的定义和术语一、树的定义 树（tree）是n(n0)个结点的有限集。在一棵非空树中： （1）有且仅有一个特定的称为根（root）的结点； （2）当n1时，其余结点可分为m(m0)个互不相交的有限集（T1,T2,Tm），其中每一集合本身又是一棵树，并且称为根的子树（subtree）。举 例例51 （a）只有根结点的树 （b）一般的树图5-1-1的（b）中A为根结点，其余结点分成三个互不相交的子集：T1=B，

56、E，F，K，L，T2=C，G，T3=D，H，I，J而T1，T2，T3本身又都是只有一个根结点的树。ALKEFGHIJDCBAM二、树结构中的一些基本术语：（1）结点：包含一个数据元素及若干指向其子树的分支（2）结点的度：结点拥有子树数目称为结点的度。如图5-1-1的（b）中，A的度为3；C的度为1；M的度为0。（3）叶子（或终端）结点：度为零的结点。（4）分支结点（或非终端结点）：除根结点外度不为零的结点，也称为内部结点。 （5）树的度：树内各结点的度的最大值。基本术语(续)（6）孩子：结点的子树的根称为该结点的孩子。如图5-1-1的（b）中，D为A的子树T3的根，则D是A的孩子。（7）双亲：

57、和孩子定义相应地该结点称为孩子的双亲。如图5-1-1的（b）中，A为D的双亲。（8）兄弟：同一个双亲的孩子之间互称兄弟。如图5-1-1的（b）中的H，I，J。（9）祖先：从根到该结点所经过分支上的所有结点。如：M的祖先为A，D，H（10）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如图5-1-1的（b）中B的子孙为E，F，K，L基本术语(续)（11）层次：从根开始定义为第一层，根的孩子为第二层，依次例推。（12）深度（或高度）：树中结点的最大层次。（13）有序树：将树中结点的各子树看成从左到右是有序的。 无序树：树中结点的各子树没有次序的。有序树中最左边的子树的根称第一个孩子，最右

58、边的称为最后一个孩子。（14）森林：是m(m0)棵互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。5.2 二叉树一、 二叉树的定义和性质：1、定义：二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点）并且二叉树的子树有左右之分，其次序不能任意颠倒。2、如图5-2-1所示二叉树的五种基本形态 （a） (b) (c) (d) (e)二叉树的性质(1)性质1：在二叉树的第i层上至多有2i-1个结点（i1）。 (2)性质2：深度为k的二叉树的最大结点数为2k-1(k1)。(3)性质3：对任何一棵二叉树T，如果其终端结点数为n,度为2的结点数为 n2

59、,则n0=n2+1(4)一棵深度为k且有2k-1个结点的二叉树称满二叉树。特点：每层上的结点数都为最大结点数，除终端结点外，每个结点都有两棵子树。二叉树的性质(续)（5）完全二叉树：如深度为k，有N个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到N的结点一一对时，称之为完全二叉树。 完全二叉树的特点是：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上。显然一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。 二叉树的性质(续)（6）完全二叉树的两个特性： 性质4：具有n个结点的完全二叉树的深度为Log2n+1。 性质5：如

60、果对一棵有n个结点的完全二叉树（其深度为Log2n+1）的结按顺序编号，则任一结点i(1in)有：如i=1,则结点i是二叉树的根结点，若i1，则i的双亲结点为结点i/2;如2in，则i的左孩子是结点2i，否则无左孩子；若2i+1n，则i的右孩子是结点2i+1 ,否则无右孩子。二叉树二、二叉树的存储结构 （一）顺序存储结构 用一组连续的存储单元存储二叉树的数据元素，按满二叉树的结点顺序编号依次存放二叉树中数据元素。 0 1 2 3 4 5 T(6)图5-3完全二叉树ABCDEFABCDEF二叉树的存储结构（二）链式存储结构链表的结点至少包含：数据域和左右指针域的链有时还需增一指向双亲的指针域，有