数据结构ppt课件完整版

1、数据结构 什么是数据结构 重要性及学习意义 课程特点及学习方法 参考资料序：课程介绍1、数据结构是程序设计的重要组成部分 用计算机解决问题的步骤： 从具体问题中抽象出一个适当的数学模型。 设计一个适合该数学模型的算法。 编写程序。 进行测试、调整、修改，直至解决问题。 瑞士计算机科学家N.writh提出： 程序设计=算法+数据结构 什么是数据结构2、数据结构的主要内容 计算机科学发展的早期主要用来做科学计算，处理一些数值计算问题，这类问题的数学模型为数学方程，但是随其发展，已经不局限于此。例1 电话号码簿的查询问题李王 什么是数据结构例2 学生信息检索河南商专计算机系软件2010级2009级计

2、算机应用会计系 什么是数据结构例3 交通图的查找3、数据结构的定义 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科。是数据的组织、存储和运算的总和。逻辑结构：指数据元素之间的逻辑关系，是从具体问题中抽象出来的数学模型，独立于计算机。存储结构：指数据元素之间的逻辑关系在计算机中的表示，又称物理结构。运算操作：查询，插入，删除 什么是数据结构计算机专业的核心课程之一是程序设计及软件开发的重要基础各类计算机考试、专升本的主要内容学习它，有助于形成计算机处理问题的意识：存储、输入、处理、输出具有复杂问题的解决能力 重要性及学习意义课程特点：理论性强，难度较大

3、学习方法：理解课堂内容：认真听、做笔记勤于习题演练：强调代码要独立写加强上机实践：阶段性调试算法养成独立思考问题、解决问题的习惯 课程特点及学习方法严尉敏、吴伟民：数据结构，清华大学出版社严尉敏、吴伟民：数据结构习题集，清华大学出版社徐士良：实用数据，清华大学出版社李春葆：数据结构习题与解析，清华大学出版社 参考资料主要内容 1.数据结构课程的性质和地位 2.基本概念和术语 3.算法及算法分析 重点、难点 基本概念及术语，算法评价的方法第1章 数据结构概述数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Elem

4、ent):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 如：自然数集N0，1，2，3， 字母集CA，B，C1.1 基本概念和术语数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。1.1 基本概念和术语形式化定义:Data_Structures = （D, S）其中: D是数据元素的有限集， S是D上关系的有限集。包括三个方面： 逻辑结构、存储结构、存储及实现逻辑结构：描述其逻辑关系。

5、可归结为以下四类: 集合结构1.1 基本概念和术语线性结构（一对一）树形结构（一对多）图状结构（多对多）线性结构的形式化描述：Line=(D, R) D= a, b, c, d R=, , 存储结构：逻辑结构在计算机中的表示。分为两类：顺序存储结构:逻辑关系由存储单元的邻接关系体现 即：逻辑上相邻的物理上也相邻。 通常用一维数组来描述。 可延伸为：索引和散列链式存储结构:元素可以任意存储，不要求逻辑上相邻的物理上也相邻，其逻辑关系一般用指针来实现。 注意：任一算法，设计在逻辑结构，但实现在存储结构上。1.1 基本概念和术语数据类型：具有相同性质的操作对象及其运算方法的集合。即：一个值的集合和定

6、义在这个值集上的一组操作的总称。 如：int：3276832767；+、*、抽象数据类型(Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）1.1 基本概念和术语 讨论每一种数据结构时,均要介绍其上的运算。 一般的，运算可分为下列两种基本类型：（1）加工型运算：运算后改变了原结构中数据元素的个数或数据元素的内容。（2）引用型运算：运算不改变结构中数据元素的个数和元素的内容，只从结构中提取某些信息作为运算的结果。1.2 运算 常用的基本运算主要包括：插入(

7、加工型):在原结构的指定位置上增添新的数据元素。删除(加工型):将原结构中的某个指定的数据元素删除。查找(引用型):从结构中找出满足条件的数据元素的位置。读取(引用型):使用结构中满足条件的数据元素的内容。更新(加工型):更换结构中某个数据元素的内容。 使用这些基本运算，可以构成其他的复杂运算1.2 运算一、算法的概念 是为了解决某类问题而定义的一个有限长的操作序列。 一个算法必须满足五个重要特性： 1、有穷性：有限的指令，每个指令在有限的时间内完成 2、确定性：每一条指令都有明确的含义，相同的条件下执行线路是确定的 3、可行性：每个步骤都是切实可行，足够基本 4、输入：一个算法可以有一个或多

8、个输入，也可以没有输入（隐含输入） 5、输出：一个算法可以有一个或多个输出1.3 算法及算法分析1、正确性，首先要满足算法需求，其次对算法的“正确性”的理解有以下四个层次：2、易读性，一个好的算法主要是与他人交流共享，晦涩难懂的算法不利于交流、调试、维护。3、健壮性，对于非法数据能够给出合理反应4、高效性，主要有两方面，运行时间和占用空间，即时间复杂度和空间复杂度此外，还要考虑算法的可维护性。二、算法的设计要求程序不含语法错误对于随意的几组合法数据输入能够得出符合要求的结构对于精心设计的典型、有刁难性的合法数据能够得出符合要求的结果程序对所有的合法的输入数据都能得出符合要求的结果1.3 算法及

9、算法分析1、算法的时间复杂度 算法在整个运行过程中消耗的时间。 影响运行时间的因素： 算法选用的策略问题的规模编程语言编译程序产生的目标代码的质量机器运行指令的速度衡量算法运行时间的方法 事后统计 缺点：必须执行程序；容易受其他硬件、软件因素影响 事前估计1.3 算法及算法分析二、算法分析(时间、空间) 讨论算法主要讨论随着问题规模的增长，算法执行时间的增长率，通常用一个函数来表示： 它表示随着问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称为算法的渐进时间复杂度，简称时间复杂度。1.3 算法及算法分析算法的时间复杂度怎么分析算法的时间复杂度呢？运行时间 = 算法中每条语句执

10、行时间之和。每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。例: for (i = 0; i n; i+ ) n+1 for ( j = 0; j y) x=5; else x=10; T(n)=O(1)算法的时间复杂度(3) for(i=1;i=n;i+) ai=i; T(n)=O(n)(4) n=100; for(i=1;i=n;i+) ai=i; T(n)=O(1)(5) x=0; for(i=1

11、;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+;=O(n3)T(n)=(6) i=s=0; while(s 1 b, i = 1 第二章 线性表顺序表的C语言实现#define maxlen 1000typedef int elemtype; elemtype elemmaxlen; int len; typedef struct SqList; SqList *L,*p;顺序表的运算1.顺序表的查找 对于给定的数据元素，找出其在线性表中的位置int SqSearch(SqList * L, elemtype x)/在顺序表L中查找数据元素x在表中第一次

12、出现的位置 int j; for(j=0; jlen; j+) if (L-elemj=x) return (j+1); return (0);x=38x=39L-Len=7 23 0 75 1 41 2 38 3 54 4 62 5 17 6 7 8第二章 线性表时间复杂度：O（n）如按序号查找： O（1）顺序表的运算2.顺序表的插入 在线性表（n个元素）的第i个位置前插入一个元素 int SqInsert(SqList * L, elemtype x,int i ) 初始条件：线性表L已存在， 1in+1 操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。实现步骤：将第n至第i

13、位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断: 插入位置i 是否合法?表是否已满?第二章 线性表第二章 线性表顺序表的运算int SqInsert(SqList * L, elemtype x, int i)/在顺序表L的第i个数据元素之前插入一个数据元素x int j,n; n=L-len; if(in+1) printf(Error!); return (0); if(n=maxlen) printf(Overflow!); return (0); for(j=n; j=i; j-)L-elemj=L-elemj-1; L-elemi-1=x; L-l

14、en+; return (1); 23 0 75 1 41 2 38 3 54 4 62 5 17 6 7 8L-len=7SqInsert( L,66,5)第二章 线性表顺序表的运算线性表的插入算法的时间复杂度 插入算法中，其时间主要消耗在移动数据元素上，数据的移动次数与插入元素的位置有关(讨论等概率)。所有可能的元素移动次数合计： 0+1+n = n(n+1)/2共有多少种插入形式? 连头带尾有n+1种!故插入时的平均移动次数为： n(n+1)/2（n+1） n/2 O(n)第二章 线性表顺序表的运算3.顺序表的删除： 将线性表（n个元素）的第i个数据元素删除 int SqDelete(S

15、qList * L,int i, elemtype * p) 初始条件：线性表L已存在且非空，1iListLength(L) 操作结果：删除L的第i个元素，并用*p返回其值，L的长度减1。实现步骤：将第i+1 至第n 位的元素向前移动一个位置；表长减1。 注意：事先需要判断，删除位置i 是否合法?第二章 线性表顺序表的运算int SqDelete(SqList * L, int i, elemtype *p)/在顺序表L中删除第i个数据元素，*p返回其值 int j,n; n=L-len; if(in) printf(Error!); return (0); *p=L-elemi-1; for

16、(j=i-1;jelemj=L-elemj+1; L-len-; return (1); 23 0 75 1 41 2 38 3 54 4 62 5 17 6L-len=7SqDelete( L, 4, p)第二章 线性表顺序表的运算线性表的删除算法的时间复杂度 删除算法中，其时间主要消耗在移动数据元素上，数据的移动次数与删除元素的位置有关所有可能的元素移动次数合计 0+1+n-1 = n(n-1)/2共有多少种删除形式? 有n种!删除时的平均移动次数为： n(n-1)/2n （n-1）/2 O(n)第二章 线性表顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点

17、插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序表第二章 线性表2.3 线性表的链式存储结构 1.单链表线性表的链式存储结构简称链表，其特点为：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素数据域 指针域结点每个数据元素，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置第二章 线性表例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)19 WANG NULL数据域指针域1 LI 43存储地址31h头指针7 QIAN 1313

18、SUN 125 WU 3731 ZHAO 737 ZHENG 1943 ZHOU 25WUZHENGhZHAOQIANSUNLIZHOUWANG2.3 线性表的链式存储结构 第二章 线性表结点：数据元素的存储映像。由数据域和指针域两部分组成；链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构,结点只有一个指针域的链表，称为单链表或线性链表。头指针：指向链表中第一个结点的指针。头结点：有时候为了操作方便在单链表的第一个结点之前添加一个结点，该结点和表中的其他结点结构相同，只是数据域不存放数据，或闲置不用，或存放其他信息。HZHAOQIANSUNLIZHOU

19、WUZHENGWANG2.3 线性表的链式存储结构 第二章 线性表类型定义typedef struct Node elemtype data;struct Node * next; LinkList;LinkList *h, *p;生成一个LinkList型新结点： p=(LinkList *)malloc(sizeof(LinkList);系统回收p结点：free(p)a1a2an h空单链表：hp2.3 线性表的链式存储结构 第二章 线性表单链表的算法(1)查找 查找单链表中是否存在结点x，若有则返回指向x结点的指针；否则返回NULLLinkList *LinkSearch(LinkLis

20、t *h,elemtype x)/ 在单链表中查找数据元素值为x的节点 LinkList *p; p=h-next; while( p!=NULL & p-data !=x) p=p-next; return (p);时间复杂度O（n）a1a2Xan hppp(2)取指定位置（第i个）的元素int GetElem(LinkList *h, int i, elemtype * e)/把链表h中第i个元素的值存入在指针e的目标变量中 LinkList p; int j; p=h-next; j=1; while( p!=NULL & jnext; j+; if(p=NULL) return 0;

21、*e = p-data; return 1; 单链表的算法第二章 线性表a1a2a3a4 hpj=1pj=2pj=3(3)插入 在链表（n个元素）的第i (1i n+1)个位置前插入一个元素,成功返回1，否则返回0。 ai-1aisxpai-1aisxp单链表的算法第二章 线性表 s=(LinkList *)malloc(sizeof(LinkList); s-data=x; s-next=p- next; p-next=s;int LinkInsert ( LinkList *h, int i, elemtype x ) /把链表h中第i个元素之前插入值为x的结点 LinkList *p,*

22、s; int j; p=h; j=0;while(p !=NULL & jnext; j+; if(p=NULL) return 0; / 参数 i不合法，s=(LinkList *)malloc(sizeof(LinkList);s-data=x; / 创建新元素的结点s-next=p- next; p-next=s; / 修改指针,完成插入return 1; 单链表的算法第二章 线性表完整算法： int LinkDelete ( LinkList *h, int i, elemtype *s) LinkList *p,*q; int j; p=h; j=0; while (p-next !

23、=NULL & j next; j+; if (p-next=NULL) return 0; / 删除位置不合理 q = p-next; p-next = q-next;/ 修改指针*s = q-data; free(q);/ 释放结点空间 return 1; ai-1aipai+1q(4)删除 将链表（n个元素）的第i（1in）个数据元素删除单链表的算法第二章 线性表 void LinkCreate(LinkList *h, int n) /逆序建立带头结点的单链表。LinkList *p; int i; h-next = NULL;/ 先建立一个带头结点的空的单链表for (i=n; i

24、0; i -) p=(LinkList *)malloc(sizeof(LinkList); scanf(%d,&p-data) ; / 输入元素值 p-next = h-next; h-next = p; / 插入在头结点之后 (5)单链表的建立：建立一个含有n个元素的单链表单链表的算法第二章 线性表例 ：设计算法逆置线性表中的元素（单链表逆置）a1a2an hanan-1a1 hvoid reverse(LinkList *h) LinkList *p,*q; p=h-next; h-next=NULL; while(p!=NULL) q=p-next; p-next=h-next; h-

25、next=p; p=q; void reverse(LinkList *h) /无头结点 LinkList *p,*q; if(h!=NULL&h-next!=NULL) p=h-next; h-next=NULL; while(p!=NULL) q=p-next; p-next=h; h=p; p=q; 单链表的算法第二章 线性表pq第二章 线性表有时候为了方便操作，将链表的最后一个结点的指针域改为指向链表的头结点或第一个节点，使得链表构成一个环，成为循环链表。ha1a2anh空循环单链表：2.3 线性表的链式存储结构 2.循环链表第二章 线性表循环单链表的查找运算（查找值为x的结点）Lin

26、kList *LLinkSearch(LinkList *h, elemtype x)/ 在循环单链表中查找数据元素值为x的结点 LinkList *p; p=h-next; while( p!=h & p-data !=x) p=p-next; if(p!=h) return p; else return NULL;2.3 线性表的链式存储结构 3.双向链表:每个结点增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。前驱指针数据域后继指针typedef struct DuNode elemtype data; struct DuNode * pr

27、ior,* next; DuLinkList;hh 和单链表类似，双链表一般也带头结点，从而使某些运算变得方便，将头结点和尾结点链接起来也能构成双向循环链表。第二章 线性表2.3 线性表的链式存储结构 双向链表的对称性：设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p-prior)-next = p =(p-next)-prioraiai-1Pxs双向链表运算（1）插入第二章 线性表s-prior=p-prior p-prior-next=ss-next=p p-prior=s注意次序2.3 线性表的链式存储结构 int DuLinkInsert ( DuLinkList *h

28、, int i, elemtype x )/在双向循环链表h中第i个数据元素之前插入一个数据元素x DuLinkList *p,*s; int j;p=h-next; j=1;while(p !=h & jnext; j+; if(p=h) return 0; / 参数不合法s=(DuLinkList *)malloc(sizeof(DuLinkList);s-data=x; / 创建新元素的结点 s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; / 修改指针 return 1;第二章 线性表2.3 线性表的链式存储结构 双向链表的删除

29、aiai+1ai-1Pp-next-prior=p-prior;p-prior-next=p-next;第二章 线性表2.3 线性表的链式存储结构 int DuLinkDelete ( DuLinkList *h, int i, elemtype *s) /在双向循环链表L中删除第i个数据元素DuLinkList *p; int j;p=h-next; j=1;while(p !=h & jnext; j+; if(p=h)return 0; p-prior-next=p-next; p-next-prior=p-prior; / 修改指针*s = p-data; free(p);/ 释放结点

30、空间 return 1;第二章 线性表2.3 线性表的链式存储结构 第二章 线性表4.静态链表：利用一维数组实现的链表a1a2a3a4 h数据域指针域下标10a121a232a343a4-145hav数据域指针域下标10a121a252a343a4-14x356hav2.3 线性表的链式存储结构 顺序表：相邻数据元素的存放地址也相邻（逻辑与物理统一；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高,可以实现随机存取。缺点：插入或删除元素时不方便。链表：相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元

31、素时很方便，使用灵活。缺点：存储密度小（top = 0; 进栈 int push (SqStack * s, elemtype x)/ 若栈的存储空间不满，则插入 元素 x 为新的栈顶元素 if (s-top = maxnum) / 栈已满，无法插入 return 0;s-stacks-top = x; / 插入新的元素s-top +; / 栈顶指针后移return 1;3.1 栈（Stack）（2）顺序栈的操作 出栈int pop (SqStack * s, elemtype * p) / 若栈不空，则删除s的栈顶元素，用 *p 返回其值 if (s-top = 0) return 0; s

32、-top -; / 栈顶指针前移 *p = s-stacks-top; / 返回栈顶元素 return 1; 取栈顶元素int GetTop (SqStack * s, elemtype * e) / 若栈不空，则用 *e 返回s的栈顶元素if (s-top = 0) return 0;*e = s-stacks-top-1; / 返回栈顶元素return 1; 3.1 栈（Stack） 判断栈是否为空 int StackEmpty (SqStack * s) /判断顺序栈S是否为空栈 if (s-top = 0) return 1; else return 0; M-105 6 7 94 8

33、 45 56 23 11top0top13.1 栈（Stack）（3）共享栈#define M 500 typedef struct elemtype stackM;int top2;DuStack;（1）类型描述.topbottom两栈共享的数据结构描述typedef struct Node elemtype data; struct Node * next;LinkStack;LinkStack * top;3.1 栈（Stack）3.栈的链式存储结构int LPush(LinkStack * top,elemtype x)/把数据元素x插入到链栈的顶部 LinkStack * p; p=

34、(LinkStack *) malloc (sizeof(LinkStack); if(p=null) printf(overflow!); return(0); p-data = x; p-next = top-next; top-next = p; return 1；3.1 栈（Stack）（2）链栈操作int LPop(LinkStack * top,elemtype * p)/栈顶数据元素出栈，并用*p保存其值 LinkStack * q; q=top-next; if(q=null) printf(stack empty!); return(0); top-next = q-next

35、; *p = q-data; free(q); return 1;3.1 栈（Stack）（2）链栈操作（1）数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 24.栈的应用3.1 栈（Stack）算法描述： void conversion( int n ) initstack(s); w

36、hile(n!=0) push(s,n%8); n=n/8; while(! StackEmpty(s) pop(s,e); printf(“%d”,e); 3.1 栈（Stack）（2）括号匹配的检验 假设表达式中允许包含两种括号：圆括号和方括号，则（ （）或（ ）等为正确的匹配，（ ）或（ （ ）或 ( ( ) ) ）均为错误的匹配。每一个出现的左括号都要等待与之匹配的右括号的的出现;如果有多个左括号在等待，则这些左括号要排成一队，且为逆序的（最后的左括号期待急迫程度最高）。每一个出现的右括号，都要有以之匹配的左括号在等待，而且这个左括号排在第一位。什么样的情况是“不匹配”的情况呢？来的右

37、括号非所“期待”的；来的是“不速之客”；直到结束，也没有到来所期待的。 3.1 栈（Stack） 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。 （3）表达式的求值表达式 = 操作数 运算符 操作数 在计算机中，对这种二元表达式可以有三种不同的标识方法。假设 Exp = S1 + OP + S2则称 OP + S1 + S2 为表达式的前缀表示法（简称前缀式）称 S1 + OP + S2 为表达式的中缀表示法（简称中缀式）称 S1 + S2 + OP 为表达式的后缀表示法（简称后缀式）基本思想为：如果来的是左括号，则入栈。如果来的是

38、右括号，则判断栈是否为空，如果栈不空判断是否匹配；最后，栈应该为空。 3.1 栈（Stack）综合比较可得下列结论： 三式中的操作数之间的相对次序相同,运算符的相对次序不同”； 中缀式丢失了括弧信息，致使运算的次序不确定； 前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式； 后缀式的运算规则为：每个运算符和之前紧靠它的两个操作数构成一个最小表达式；表达式不需要使用括号运算符在式中出现的顺序恰为表达式的运算顺序若 Exp=ab +(c-d/e) f 则： 前缀式为：+a b- c/ d e f 中缀式为：ab + c d / e f 后缀式为：a bc d

39、 e /- f +3.1 栈（Stack） 运算过程为：对后缀式从左向右扫描，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。由此可见，在运算过程中保存操作数的结构应该是个栈。 基本思想为：设置一个栈，从左到右扫描后缀表达式。每读到一个操作数，就将其入栈；每读到一个运算符，就从栈顶取出两个操作数，完成此操作符的运算，并将计算结果作为一个新的操作数入栈。一直到整个表达式扫描完，最后位于栈顶位置的元素值就是该表达式的值。如何从后缀表达式求值？3.1 栈（Stack） 如何由原表达式转换成后缀式

40、？ 原表达式和后缀式两者中运算符出现的次序有什么不同。 例1 原式：a*b/c*d-e+f 后缀式：ab*c/d*e-f+例2 原式：a+b*c-d/e*f 后缀式：abc*+de/f*-为此,引入运算符的“优先数”的概念 运算符: # ( + - * / * 优先数: -1 0 1 1 2 2 3 对原表达式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符，如果它的优先数“高或等于”后面的运算，则它的运算先进行，否则就得等待在它之后出现的所有优先数高于它的“运算”都完成之后再进行。 3.1 栈（Stack）1) 设立运算符栈；2) 设表达式的结束符为#，预设运算符栈的栈底为#；

41、3) 若当前字符是操作数，则直接发送给后缀式；4) 若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式；5) 若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式；6) (对它之前后的运算符起隔离作用，则若当前运算符为(时进栈；7) )可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为(止。 3.1 栈（Stack） void transform(char exp ) / 从合法的表达式exp求后缀式InitStack(S); push(S, # ); p = exp; ch = *p;while (!S

42、tackEmpty(S) if (!IN(ch, OP) printf(%c,ch);else switch (ch) case ( : push(S, ch); break; case ) : pop(S, c); while (c!= ( ) printf(%c,c); Pop(S, c) break; defult :c=Gettop(s); while( precede(c,ch) ) printf(%c,c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / elseif ( ch!= # ) p+; ch = *p; / while

43、/ transform 若c的优先数大于或等于ch,precede(c,ch)值为true3.1 栈（Stack）（4）函数的嵌套调用 当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：1) 将所有的实在参数、返回地址等信息传递给被调用函数保存；2) 为被调用函数的局部变量分配存储区；3) 将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，应该完成：1) 保存被调函数的计算结果；2) 释放被调函数的数据区；3) 依照被调函数保存的返回地址将控制转移到调用函数。当多个函数嵌套调用时，由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行栈式管理

44、。3.1 栈（Stack） 一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。 为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需要一个“递归工作栈”。作用：将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数；保存本层的参数和局部变量，以便从下一层返回时重新使用它们 递归过程执行过程中所占用的数据区，称之为递归工作栈。 每一层的递归参数等数据合成一个记录，称之为递归工作记录。 栈顶记录指示当前层的执行情况，称之为当前活动记录。（5）递归的实现3.1 栈（Stack）1、队列的定义及常用操作 定义：限定只能

45、在表的一端进行插入，在表的另一端进行删除的线性表。 允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。在队尾进行插入操作称为入队，在队头进行删除操作称为出队。特点：先进先出（First In First Out，LIFO）。3.2 队列（Queue） 3.2 队列（Queue） 常用操作： （1）队列的初始化：初始化一个空队列。 （2）入队：向队列中插入一个新的队尾元素。 （3）出队：删除队列的队头元素。 （4）求队长：计算队列中元素的个数。 （5）判队空：如果队列为空返回真值，否则返回假值。 （6）判队满：如果队列为满返回真值，否则返回假值。2、队列的顺序存储结构（1

46、）类型描述typedef struct elemtype queuemaxnum; int front,rear;SqQueue;3.2 队列（Queue） 初始化建空队列时，令 front=rear=0，每当插入一个新的队尾元素后，尾指针rear增1；每当删除一个队头元素之后，头指针 front增1。因此，在非空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的下一个位置。 设想这个数组的存储空间是个“环”，认定“7”的下一个位置是“0”，我们称为循环队列。 什么时候队列为空？什么时候队列为满？front=rear(rear+1)%maxnum=front队列的长度为多少？(rear-f

47、ront+maxnum)%maxnum3.2 队列（Queue） typedef struct Node elemtype data; struct Node * next;QNode;typedef struct QNode * front; QNode * rear;LinkQueue;3.2 队列（Queue） 3、队列的链式存储结构int InitQueue(LinkQueue * q)/构造一个空队列q q-front=q-rear=(QNode * )malloc(sizeof(QNode); if(q-front=NULL) printf(Over flow!); return(

48、0); q-front-next=NULL; return 1;链队列初始化3.2 队列（Queue） 入队int EnLQue(LinkQueue * q,elemtype x)/数据元素x插入链队q中成为新的队尾元素QNode * p;p=(QNode * )malloc(sizeof(QNode);if(p=NULL) printf(Over flow!); return(0);p-data=x;p-next=NULL;q-rear-next=p; / 修改尾结点的指针q-rear=p; / 移动队尾指针return(1);3.2 队列（Queue） 出队int DeLQue(LinkQ

49、ueue * q, elemtype * p) / 若队列不空,则删除当前队列q中的头元素，用p返回其值Qnode *s; if (q-front = q-rear ) / 链队列为空 return 0; s = q-front-next; * p = s-data;/ 返回被删元素q-front-next = s-next; / 修改头结点指针if(q-rear = s) q-rear = q-front; free(s);/ 释放被删结点return 1; 3.2 队列（Queue） 3.2 队列（Queue） 4、队列的应用（1）输入/输出缓冲区问题 操作系统解决主机与外部设备之间速度的

50、不匹配问题，要借用缓冲区来实现。缓冲区一般采用先进先出的原则进行，可采用队列实现。（2）计算机资源竞争问题 多终端计算机系统中，多个用户向操作系统提出占用CPU的申请，操作系统按其请求时间先后排成队列，每次把CPU分配给队首的用户。 第四章 串第四章 串本章内容 1. 串的定义及常用操作 2. 串的存储结构 3. 串的模式匹配 4. 串的应用本章重点、难点 串类型的定义和存储结构学习要点1、了解串的概念；2、熟悉串的基本运算的定义；3、熟练掌握串的基本算法。4.1 串的定义及常用操作一、定义及相关术语 1.串 零个或多个字符组成的有限序列。 一般记为：S=“a1a2.an” 其中，S是串名，引

51、号括起的字符序列是串值；串中所包含的字符个数称为串的长度。 2.空串长度为零的串，它不包含任何字符。 3.空格串由一个或多个空格组成的串 4.子串串中任意个连续的字符组成的子序列。 5.主串包含子串的串 6.字符在串中的位置字符在序列中的序号 7.子串在主串中的位置子串在主串中第一次出现时，子串的第一个字符在主串中的位置。8.两个串相等 两个串的长度相等，并且各个对应位置的字符都相等时才相等。二、串的常用操作1.串变量赋值 ：有一个串的常量或串变量为另一串变量赋值 2.判断两个串是否相等：若相等返回真值，否则返回假值3.连接两个串：将第二个串接到第一个串的末尾4.求串长：统计字符串的字符的个数

52、5.求子串：在个主串中求从指定位置开始的指定长度的子串6.子串的定位：求指定子串在主串中第一次出现的位置7.子串的替换：在主串中用把一个子串替换为另一子串8.串的插入：在字符串的指定位置插入字符串9.串的删除：从字符串的指定位置开始删除连续基于个字符4.1 串的定义及常用操作一、串的顺序存储结构4.2 串的存储结构#define maxlen 100 /定义字符串的最大长度typedef struct char datamaxlen+1; /多一个元素存储结束标志0 int len;SeqString; 常用运算：（1）串连接 concat (s1, s2)把串 s2 连接在串s1的后面，形成

53、新串。两种方法：定长一维数组实现和动态内存分配 1. 串的定长顺序存储结构SeqString * concat(SeqString * s1, SeqString *s2) int i,j; SeqString *t; t=(SeqString *)malloc(sizeof(SeqString); for(i=0; ilen; i+) t-datai = s1-datai; if(s1-len+s2-len= maxlen) for(j=0; jlen; j+) t-data i+=s2-dataj; t-len=s1-len+s2-len; else for( j=0; idatai=s2

54、-dataj; t-datamaxlen=0; t-len=maxlen; return(t);4.2 串的存储结构（2）求子串 substring (s, pos, len)求串s的第 pos 个字符起长度为 len 的子串。SeqString * substring (SeqString *s, int pos, int len ) SeqString *t; int i;if (poss-len|lens-len-pos+1) return NULL;t=(SeqString *)malloc(sizeof(SeqString); for ( i = 0; i data i = s-da

55、ta pos + i - 1 ; t-data len =0; t-len=len; return t;4.2 串的存储结构（3）子串的插入 StrInsert(s, pos, t ) 在串 s 的第 pos 个字符之前插入串 t。int StrInsert(SeqString * s, int pos, SeqString * t ) int i; if(t-len=0) printf(“空串！n”); return 0 ; if(poss-len+1) printf(“位置错！”)；return 0; if(s-len+t-lenmaxlen) printf(“溢出！”)；return 0

56、; for(i=s-len; i=pos-1; i-) s-datai+ t-len=s-datai; for(i=0;ilen;i+) s-datapos-1+i=t-datai; s-len = s-len+ t-len return 1;4.2 串的存储结构4.2 串的存储结构typedef struct char *ch; /存储字符串的首地址 int len;String; 常用运算：（1）串连接 concat (s1, s2)为新串t分配大小s1和s2长度之和的空间，然后依次复制s1和 s2的内容。2. 串的动态顺序存储结构 仍以一组地址连续的存储单元存储串值，只是在程序执行过程中

57、动态分配存储空间。String concat(String s1, String s2) int i,j; String t; t.ch=(char *)malloc(s1.len+s2.len+1)*sizeof(char); /多定义一个空间存储字符串结束标志 for(i=0; is1.len; i+) t.chi = s1.chi; for(j=0; j=pos-1; i-) s.chi+ t.len=s.chi; for(i=0; ilen=0 ) printf(“匹配串为空！”); return 0; if(poss-len) printf(“位置错！”); return 0; i=

58、pos; j=1; while (ilen & jlen) if (s-datai=t-dataj) +i; +j; else i=i-j+2; j=1; /重新开始匹配 if (jt-len) return (i-t-len) ; else return 0; 算法实现：4.3 串的模式匹配4.4 串操作的应用 文本编辑 文本编辑程序是一个面向用户的系统服务程序，广泛应用于源程序的输入和修改。其实质是修改字符数据的形式或格式，其基本操作包括串的查找，插入和删除等基本功能。 可将文本划分为若干页，每页又有若干行。具体操作中可将文本看作字符串，称为文本串。页是文本串的子串，行又是页的子串。先为文

59、本串建立相应的页表和行表，即建立各子串的存储映象。 页表给出页号和该页的起始行号. 行表则指示每一行的行号、起始地址和该行子串的长度。为查找方便，行表是按行号递增顺序存储的。然后需在文本编辑程序中设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。从而实现基本操作。第五章 数组和广义表第五章 数组和广义表本章内容 1.数组 2.矩阵的压缩存储 3.广义表本章重点、难点 数组的存储、特殊矩阵的压缩存储、广义表5.1 数组1.数组的定义及常用操作 数组是由n(n1)个相同类型的数据元素a0，a1，an-1构成的有限序列 。其数组元素可以是基本数据类型，可以是复杂数据类型。当数组元素也是数

60、组时，一维数组扩充为二维数组(矩阵)。 二维数组同样满足数组的定义。一个二维数组可以被看成是特殊的一维数组，其中，每个元素又是一个一维数组。多维数组可以按同样的方法类推。常用操作：取值操作：给定一组下标，读其对应的数据元素 ；赋值操作：给定一组下标，存储或修改与其相对应的数据元素；2.数组的顺序存储结构及基本运算 5.1 数组 多维数组，通常有两种映象方法：即“以行(序)为主(序)”的映象方法和“以列(序)为主(序)”的映象方法。a0,2a0,1a0,0a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2La0,1a1,0a0,0a1,1a0,2a1,2L对于mn二维数组(