2010年计算机考研基础班讲义 数据结构基础 计算机考研小组(100).

Presentation on theme: "2010年计算机考研基础班讲义 数据结构基础 计算机考研小组(100)."— Presentation transcript:

1 2010年计算机考研基础班讲义 数据结构基础 计算机考研小组(100)

2 第一章 绪论 什么是数据结构 直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。
数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这就是数据结构。

3 学习数据结构的重要性 “数据结构”在计算机科学中是一门综合性的专业基础课, 在考研中占很大的分值。
数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

4 §1.2数据结构的概念 一、基本概念 数据：能输入计算机且被能计算机处理的一切对象。 数据元素：对现实世界中某独立个体的数据描述。
数据项：具有独立意义的最小数据单位。 数据类型：每个数据项必须属于某确定的数据类型。 基础

5 §1.3数据的逻辑结构 一、基本概念 数据对象：具有相同特征的数据元素的集合。
关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。

6 §1.3数据的逻辑结构 二、数据的逻辑结构 设D表示数据元素的集合，R表示D上的关系的集合，则一个数据结构B可表示为：
B = （ D ，R ） 由此可见数据结构由两部分构成 （1）表示各元素的信息 D （2）表示数据之间关系的信息R 一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元组<a,b>表示a是b的前驱，b是a的后继。

7 §1.3 数据的逻辑结构 线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。
§1.3 数据的逻辑结构 三、数据结构的分类 线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。 树状结构：除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。 网状结构：各结点可以有多个前驱或多个后继。

8 §1.4 数据的存储结构 数据结构在计算机中的表示称为数据的存储结构。
§1.4 数据的存储结构 数据结构在计算机中的表示称为数据的存储结构。 数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。 四种基本的存储方式： 1、顺序方式 顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。

9 §1.4 数据的存储结构 2、链接方式 链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。 3、索引方式 在线性结构中，各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,… … an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。

10 §1.4 数据的存储结构 4、散列方式 利用该结点的值确定该结点的存储单元地址。

11 §1.5 数据运算和算法 1、数据运算 按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。 1）插入：往数据结构中添加新的结点称为插入。 2）删除：把指定的结点从数据结构中删除。 3）更新：改变指定结点的值或者改变某些结点的关系称为更新。 4）查找：在数据结构中查找某些满足条件的结点。 5）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。

12 §1.5 数据运算和算法 2、算法 算法是对特定问题求解步骤的一种描述。 算法应具有的几个特征：
§1.5 数据运算和算法 2、算法 算法是对特定问题求解步骤的一种描述。 算法应具有的几个特征： 1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。 2）确定性：算法的每一步骤应定义明确，没有二义。 3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。

13 §1.5 数据运算和算法 3、算法的评价 对算法评价的几个指标 空间复杂度 空间复杂度是指执行算法所需要的辅助空间大小。 时间复杂度
§1.5 数据运算和算法 3、算法的评价 对算法评价的几个指标 空间复杂度 空间复杂度是指执行算法所需要的辅助空间大小。 时间复杂度 时间复杂度是指执行完算法所需的运算次数。

14 第二章 线性表 线性表是一种最简单、最常用的数据结构。 线性表的主要存储结构有两种：顺序存储结构和链接存储结构。

15 §2.1 线性表的定义及基本运算 一、线性表的定义
§2.1 线性表的定义及基本运算 一、线性表的定义 线性表是由n(n≥0)个性质相同的数据元素a1,a2,a3,…an组成的有限序列，记为(a1,a2,a3,…an)。 二、线性表的基本运算 （1）置线性表为空表； （2）求线性表的长度； （3）读取线性表中的第i个元素； （4）修改线性表中的第i个元素； （5）查找线性表中具有某个特征值的数据元素；

16 §2.1 线性表的定义及基本运算 二、线性表的基本运算 （6）在线性表的第i个数据元素之前或之后插入一个新的数据元素；
§2.1 线性表的定义及基本运算 二、线性表的基本运算 （6）在线性表的第i个数据元素之前或之后插入一个新的数据元素； （7）删除线性表中第i个数据元素或满足给定条件的第一个数据元素； （8）对线性表中的所有元素按照给定的关键字大小进行排序。

17 §2.2 线性表的顺序存储结构及运算 一、线性表的顺序存储结构 线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。 线性表在c语言中用一维数组表示。 c语言的描述 Typedef int ET; #define maxlen 1000 ET s[maxlen];

18 §2.2 线性表的顺序存储结构及运算 线性表C语言描述的说明：
§2.2 线性表的顺序存储结构及运算 一、线性表的顺序存储结构 线性表C语言描述的说明： 在C语言中，数组的下标是从0开始的，数据结构中的结点的序号是从一开始的。因此在线性表中的第一个元素是指S[0]。 两个相邻结点ai和a i+1的存储位置记为 LOC（ ai ）和LOC（ a i+1 ），则结点满足以下关系 LOC（ a i+1 ）= LOC（ ai ）+1

19 §2.2 线性表的顺序存储结构及运算 二、线性表的运算 1、插入运算的算法描述：
§2.2 线性表的顺序存储结构及运算 二、线性表的运算 1、插入运算的算法描述： int insertqlist(int i,ET x,ET s[],int *np) {int j,n; n=*np; if ((i<1) || (i>n+1)) return(0); else {for (j=n;j>=i;j--) s[j]=s[j-1]; s[j]=x; *np=++n; return(1); }

20 §2.2 线性表的顺序存储结构及运算 二、线性表的运算 2、删除运算的算法描述：
§2.2 线性表的顺序存储结构及运算 二、线性表的运算 2、删除运算的算法描述： int delqlist(int i,ET s[],int *np) {int j,n; n=*np; if ((i<1) || (i>n)) return(0); else {for (j=i;j<n;j++) s[j-1]=s[j]; *np=--n; return(1); }

21 §2.2 线性表的顺序存储结构及运算 二、线性表的运算 3、查找运算的算法描述： int fincl(ET x,ET s[],int n)
§2.2 线性表的顺序存储结构及运算 二、线性表的运算 3、查找运算的算法描述： int fincl(ET x,ET s[],int n) {int j; for (i=0;i<n;i++) if (x==s[i]) break; if (i==n) return(0); return(i+1) }

22 §2.3 线性表的链接存储结构及运算 一、线性链表 用链接方式存储的线性表称线性链表，简称链表。
§2.3 线性表的链接存储结构及运算 一、线性链表 用链接方式存储的线性表称线性链表，简称链表。 线性表的链接存储结构是用一组地址任意的存储单元来存放表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。 数据域 指针域 数据 指针 单链表结点结构

23 §2.3 线性表的链接存储结构及运算 一、线性链表 结点的数据定义形式： typedef struct node { ET data;
§2.3 线性表的链接存储结构及运算 一、线性链表 结点的数据定义形式： typedef struct node { ET data; struct node *link ; } NODE; 结点的内存分配： （NODE *)malloc(sizeof(NODE))

24 §2.3 线性表的链接存储结构及运算 二、单链表及其运算 线性链表的每一个结点只含有一个指针域，这样的线性链表称为单链表。
§2.3 线性表的链接存储结构及运算 二、单链表及其运算 线性链表的每一个结点只含有一个指针域，这样的线性链表称为单链表。 单链表的运算：建表、查找、插入、删除以及判断是否为空表。 1、建立单链表 首先生成表头结点，形成一个空链表，然后在表中逐一增加新的结点。 （1）使用malloc函数，开辟新的存储单元q； （2）读入新结点数据，新结点的指针域为空 （3）把新结点链接到链表上去。

25 建立单链表的算法描述： NODE *create(int n) { NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE)); p->data=0;p->link=NULL; head=p; for (i=1;i<=n;i++) {q=(NODE *)malloc(sizeof(NODE)); scanf("%d",&q->data); q->link=NULL; p->link=q;p=p->link; } return (head);

26 §2.3 线性表的链接存储结构及运算 2、查找链表中的 X 查找链表中是否存在结点X，算法的基本思想为：
§2.3 线性表的链接存储结构及运算 2、查找链表中的 X 查找链表中是否存在结点X，算法的基本思想为： 从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值X 进行比较，直到某个结点的数据域的值等于给定值X （既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回NULL。

27 查找单链表中结点X的算法描述： NODE *found(NODE *head,ET x) {NODE *p; p=head->link; while((p!=NULL)&&(p->data!=x)) p=p->link; return (p); }

28 §2.3 线性表的链接存储结构及运算 3、在单链表中插入新结点X 在链表中的某一结点p 之后插入一个数据为X 的新结点。过程如下：
§2.3 线性表的链接存储结构及运算 3、在单链表中插入新结点X 在链表中的某一结点p 之后插入一个数据为X 的新结点。过程如下： （1）生成一个新结点q ，将X 赋给q->data; （2）修改有关结点的指针域：将原p 结点的后继作为q 结点的后继，q 结点作为p 结点的后继。

29 在单链表中插入新结点X的算法描述： void insert(NODE *head,NODE *p,ET x) {NODE *q; q=(NODE *)malloc(sizeof(NODE)); q->data=x; if (head->link==NULL) {head->link=q;q->link=NULL;} else {q->link=p->link;p->link=q;} }

30 §2.3 线性表的链接存储结构及运算 4、删除单链表中的结点X 删除单链表中的结点X ，并由系统收回其占用的存储空间。过程如下：
§2.3 线性表的链接存储结构及运算 4、删除单链表中的结点X 删除单链表中的结点X ，并由系统收回其占用的存储空间。过程如下： （1）设定两指针p 和q ，p 指针指向被删除结点；q 为跟踪结点，指向被删除结点的前驱结点; （2）p 从表头指针head指向的第一个结点开始向后依次进行搜索。当p->data等于X 时，被删除结点找到。 （3）修改p 的前驱结点q 的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既q->link=p->link，p结点被删除，然后再释放存储空间。

31 在单链表中删除结点X的算法描述： void delete(NODE *head,ET x) {NODE *p,*q; p=head; q=p; p=p->link; while((p!=NULL)&&(p->data!=x)) {q=p;p=p->link;} if (p==NULL) printf("Not found!\n"); else {q->link=p->link;free(p);} }

32 §2.3 线性表的链接存储结构及运算 三、循环链表 链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。
§2.3 线性表的链接存储结构及运算 三、循环链表 链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。 循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出发都可以访问到表中的所有结点。 在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。

33 §2.3 线性表的链接存储结构及运算 三、循环链表 head 非空表（a) 空表（b) head

34 (1)在头指针为head的循环链表查找值为x的前驱结点。
NODE *looknode(head,x) ET x;NODE *head; {NODE *p; p=head; while ((p->link!=head)&& (((p->link)->data)!=x)) p=->link; return (p); }

35 (2)在头指针为head的循环链表在值为x的结点之前插入一个值为b的新结点。
NODE insnode(head,x,b) ET x,b;NODE *head; {NODE *p,*q; p=(NODE *)malloc(sizeof(NODE)); p->data=b; q=looknode(head,x); p->link=q->link; q->link=p; return ; }

36 (3)在头指针为head的循环链表中，删除值为x的结点。
Void delnode (head,x) ET x;NODE *head; {NODE *p,*q; q=looknode(head,x); if (q->link==head) {printf(“No this node the list!\n”) return;} p=q->link;q->link=p->link;free(p); return ; }

37 §2.3 线性表的链接存储结构及运算 四、循环链表
§2.3 线性表的链接存储结构及运算 四、循环链表 一个链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。

38 五、双向链表 ∧ ∧ head 带头结点的双向链表 llink data rlink 双向链表的结点结构

39 §2.4 数组 一、数组的定义 数组是由一组类型相同的数据元素构造而成。 若数组元素只含有一个下标，这样的数组称为一维数组。
§2.4 数组 一、数组的定义 数组是由一组类型相同的数据元素构造而成。 若数组元素只含有一个下标，这样的数组称为一维数组。 当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。

40 §2.4 数组 二、数组的存储结构 数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。 三、规则矩阵的压缩存储
§2.4 数组 二、数组的存储结构 数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。 三、规则矩阵的压缩存储 有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用压缩存储。 所谓压缩存储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够体现矩阵的逻辑结构。

41 §2.4 数组 四、稀疏矩阵及存储 当一个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀疏矩阵的存储方式常采用压缩存储。方法有两种：三元组表和十字链表。 1、在稀疏矩阵中，每一个非零元素可以用它所在的行号 i、列号 j以及元素值 a i j组成的三元组( i, j, a i j)来表示。 三元组的结点定义： typedef struct node { int r, c ; ET v; }NODE;

42 §2.4 数组 r c v Ma[0] 5 6 1 4 2 3 9 7 Ma[1] Ma[2] Ma[3] A= Ma[4] Ma[5] Ma[6]

43 §2.4 数组 r c v Mb[0] 5 6 1 4 3 9 2 7 Mb[1] Mb[2] Mb[3] B= Mb[4] Mb[5] Mb[6]

44 §2.4 数组 实现矩阵转置的算法： int syz(NODE ma[],NODE mb[]) int i,j,n,t,k;
§2.4 数组 实现矩阵转置的算法： int syz(NODE ma[],NODE mb[]) int i,j,n,t,k; {if (ma[0].v==0) return (0); n=ma[0].c;t=ma[0].v; mb[0].r=n;mb[0].c=ma[0].r;mb[0].v=t; k=1; for (j=1;j<=n;j++) for (i=1;i<=t;i++) if (ma[i].c==j) {mb[k].r=ma[i].c; mb[k].c=ma[i].r; mb[k].v=ma[i].v;k++;} return (1); }

45 §2.4 数组 2、稀疏矩阵的链接存储 稀疏矩阵的链接存储是一种即带行指针又带列指针的链接存储结构。对稀疏矩阵的链接存储是对其相应的三元组线性表进行链接存储，链接表中的每一结点表示一个非零元素的三元组，每一个结点即处于同一行的单链表中又处于同一列的单链表中，即处于所在行的单链表和所在列单链表的交叉点处，整个稀疏矩阵由十字交叉链表结构组成，故称为十字链表。 行域 列域 值域 Row Col val Down right 向下域 向右域

46 §2.4 广义表 一、广义表的定义 广义表是线性表的推广，简称为表。它是由n(n≥0)个元素的有限序列。记为：A=(a1,a2,a3,……an)。其中A为表名；n表示广义表的长度，既元素的个数；元素ai可以是数据元素，称为单元素；也可以是表，称为子表或表元素。 广义表是一种递归的数据结构。

47 第三章 栈与队列 栈与队列是线性表中最重要的、实际应用最广泛的特例。栈和队列的逻辑结构和线性表相同，只是运算规则有更多的限制。
第三章 栈与队列 栈与队列是线性表中最重要的、实际应用最广泛的特例。栈和队列的逻辑结构和线性表相同，只是运算规则有更多的限制。 本章的基本内容： 1、栈和队列的定义； 2、栈和队列的存储表示； 3、栈和队列基本运算的实现算法以及栈和 队列的应用。

48 §3.1 栈 一、栈的定义 栈( Stack )是一种特殊的线性表，栈的插入和删除操作均在表的一端进行。允许插入和删除的一端称为栈顶( Top )，另一端称为栈底( Bottom )。 若给定栈 S=( a0 , a1 , a2 , a3 ,… ai , … an-1 ),则称an-1栈顶元素，称a0 为栈底元素。 栈顶 Top an-1 a1 a0 栈底 Bottom

49 §3.1 栈 栈的主要运算有： (1) 进栈，向栈顶插入一个新元素； (2) 出栈，删除栈顶元素； (3) 读栈，读取栈顶元素；
§3.1 栈 栈的主要运算有： (1) 进栈，向栈顶插入一个新元素； (2) 出栈，删除栈顶元素； (3) 读栈，读取栈顶元素； (4) 置空栈，将栈置为空栈； (5) 判栈空，判断一个栈是否为空。

50 §3.1.2 栈的存储结构及其运算 1、栈的顺序存储结构及运算
§ 栈的存储结构及其运算 1、栈的顺序存储结构及运算 与第二章讨论的一般的顺序存储结构的线性表一样，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。因此，我们可以使用一维数组s[MAXLEN]来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置，以数组小下标的一端作为栈底，通常以top=-1时为空栈，在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。

51 §3.1.2 栈的存储结构及其运算 用C语言定义的顺序存储结构的栈如下： # define MAXLEN /*最大元素数*/
§ 栈的存储结构及其运算 用C语言定义的顺序存储结构的栈如下： # define MAXLEN /*最大元素数*/ int s[MAXLEN]; int top ; 鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。 假设有一个栈T=(a, b, c, d, e, f) ,则栈T所对应的顺序存储结构用图形表示如下：

52 §3.1.2 栈的存储结构及其运算 6 Top 5 5 5 Top 4 4 4 4 Top 3 3 3 3 2 2 2 2 1 1 1 1
§ 栈的存储结构及其运算 MAXLEN-1 … … MAXLEN-1 f e d c b a MAXLEN-1 g f e d c b a MAXLEN-1 e d c b a 6 Top 5 5 5 Top 4 4 4 4 Top 3 3 3 3 2 2 2 2 1 1 1 1 Top -1

53 §3.1.2 栈的存储结构及其运算 (1)置空栈 void stack(s) int s[ ]; { top = -1;} (2)判定空栈
§ 栈的存储结构及其运算 (1)置空栈 void stack(s) int s[ ]; { top = -1;} (2)判定空栈 int empty(s) { if (top == -1) return (1); else return (0); }

54 §3.1.2 栈的存储结构及其运算 (3)进栈 int push(s, x) int s[ ], x;
§ 栈的存储结构及其运算 (3)进栈 int push(s, x) int s[ ], x; { if ( top ==MAXLEN -1) { printf(“stack overflow!\n”); return (1); } else top=top+1; s[top]=x; return (0);

55 §3.1.2 栈的存储结构及其运算 (4)出栈 int popsh(s, y) int s[ ], *y; { if (top == -1)
§ 栈的存储结构及其运算 (4)出栈 int popsh(s, y) int s[ ], *y; { if (top == -1) { printf(“stack underflow!\n”); return (1);} else {*y=s[top]; top=top-1; return (0); }

56 § 栈的存储结构及其运算 多栈共享邻接空间 在计算机系统软件中，各种高级语言的编译系统都离不开栈的使用。常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间，但实际中很难准确地估计。另一面方面，若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补。这就是栈的共享邻接空间。

57 §3.1.2 栈的存储结构及其运算 双向栈在一维数组中的实现
§ 栈的存储结构及其运算 双向栈在一维数组中的实现 栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stack[MAXLEN]，则可以利用栈的“栈底位置不变，栈顶位置动态变化”的特性，两个栈底分别为-1和MAXLEN-1，而它们的栈顶都往中间方向延伸。因此，只要整个数组stack[MAXLEN]未被占满，无论哪个栈的入栈都不会发生上溢。 MAXLEN-1 自由区 lefttop righttop

58 §3.1.2 栈的存储结构及其运算 { ET data; struct node *link; }NODE; 2、 栈的链式存储结构
§ 栈的存储结构及其运算 2、 栈的链式存储结构 栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。 链栈的结点类型C语言定义为： typedef struct node { ET data; struct node *link; }NODE;

59 §3.1.2 栈的存储结构及其运算 (1)入栈 新元素x 入栈的C 语言描述：
§ 栈的存储结构及其运算 (1)入栈 新元素x 入栈的C 语言描述： NODE *pushstack (NODE *top, ET x) { NODE *p; p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->link=top; top=p; return (top); }

60 §3.1.2 栈的存储结构及其运算 (2)出栈 栈顶元素出栈算法的C语言描述：
§ 栈的存储结构及其运算 (2)出栈 栈顶元素出栈算法的C语言描述： NODE *popstack(NODE *top, ET *p) { NODE *q; if (top != NULL) { *q=top; *p=top->data; top=top->link; free(q); } return (top);

61 §3.1.2 栈的存储结构及其运算 3、栈的应用举例 表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。
§ 栈的存储结构及其运算 3、栈的应用举例 表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。 (1)中缀算术表达式：将运算符置于两个操作数中间的算术表达式，称中缀表达史。 （2）后缀表达式：将运算符置于两个操作数的后面的算术表达式称为后缀表达式。这种表达式不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行。计算机在处理这种表达式时，只需对其扫描一遍，就可完成计算。

62 §3.2 队列 在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。
§3.2 队列 在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。 队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业的输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。

63 §3.2 队列 计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样，高速设备就不必每次等待低速设备处理完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。

64 §3.2 队列 a0, a1, a2, a3, a4, ……,a i … … a n-1 一、队列的定义及运算
§3.2 队列 一、队列的定义及运算 队列也是一种特殊的线性表，它是只允许在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队首。 若给定队列q=(a0, a1, a2, a3, a4, ……, a n-1)，我们称a0是队首元素，a n-1是队尾元素。 出队 入队 a0, a1, a2, a3, a4, ……,a i … … a n-1

65 第四章 递归 递归是程序设计中一个重要的算法设计方法和技术。递归子程序是通过调用自身来完成与自身要求相同的子问题的求解,并利用系统内部功能自动实现调用过程中信息的保存与恢复，而省略了程序设计中的许多细节操作，简化了程序设计过程,使程序设计人员可以集中注意力于主要问题求解上。

66 §4.1 递归的定义 递归就是一个事件或对象部分由自己组成。 递归算法包括递推和回归两部分
§4.1 递归的定义 递归就是一个事件或对象部分由自己组成。 递归算法包括递推和回归两部分 （1）递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。 （2）就是指当“简单的问题得到解后，回归到原问题的解上。

67 §4.2 递归的实现 1、采用递归算法具备的条件 （1）所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解法相同。
§4.2 递归的实现 1、采用递归算法具备的条件 （1）所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解法相同。 （2）必须具备终止递归的条件。程序中不能出现无终止的递归调用，而只能出现有限次的，有终止的递归调用。

68 §4.2 递归的实现 2、递归算法示例: n！（阶乘）算法的求解。 int fact(int n) { if (n= =0)
§4.2 递归的实现 2、递归算法示例: n！（阶乘）算法的求解。 int fact(int n) { if (n= =0) { s=1; return 1;} else { s=n*fact(n-1); return s; } } void main() { int n; n= fact(5); printf(“n=%d\n”,n}

69 4.3 阶乘递归的实现 ReLoc6 fact(1) 1 ReLoc5 fact(2) 2 ReLoc4 fact(3) 3 ReLoc3
4.3　阶乘递归的实现 ReLoc6 fact(0)=1 fact(1) 1 ReLoc5 s=fact(1)=1*fact(0)=1 fact(2) 2 ReLoc4 s=fact(2)=2*fact(1)=2 fact(3) 3 ReLoc3 s=fact(3)=3*fact(2)=6 fact(4) 4 ReLoc2 s=fact(4)=4*fact(3)=24 fact(5) 5 ReLoc1 s=fact(5)=5*fact(4)=120 main() 参数表 返回地址 调用者 活动记录进退栈示意图

70 输出s=120.00 fact(5)=120 fact(4)=24 fact(3)=6 fact(2)=2 fact(1)=1
主函数 mani() N=fact(5) 第一层调用 n=5 s=5*fact(4) 第二层调用 n=4 s=4*fact(3) 第三层调用 n=3 S=3*fact(2) 第四层调用 n=2 S=2*fact(1) 第五层调用 n=1 S=1 fact(1)=1 fact(2)=2 fact(3)=6 fact(4)=24 fact(5)=120 输出s=120.00 递归调用过程示意图 从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。

71 例 汉诺塔 传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。 移动时的规则： 每次只能移动一个盘子； 只能小盘子在大盘子上面； 可以使用任一柱子。 当工作做完之后，就标志着世界永远和平。 x y z n –1 n

72 分析： 设三根柱子分别为 x，y, z , 盘子在x柱上，要移到z柱上。 1、当n=1时，盘子直接从 x 柱移到 z 柱上； 2、当n>1时, 则①设法将前n–1个盘子借助z，从x移到y柱上，把 盘子n从x移到z柱上； ② 把n–1个盘子从y移到z柱上。

73 Hanoi问题 void Hanoi ( int n, char x, char y, char z )
{ //将 n 个 编号从上到下为 1…n 的盘子从 x 柱，借助 y 柱移到 z 柱 if ( n = = 1 ) move ( x , 1 , z ) ; //将编号为 1 的盘子从 x 柱移到 z 柱 else { //将 n -1个 编号从上到下为1…n-1的盘子从 x 柱，借助 y 柱移到 z 柱 Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; //将编号为 n 的盘子从 x 柱移到 z 柱 //将 n -1个 编号从上到下为 1…n-1的盘子从 y 柱，借助 x 柱移到 z 柱 Hanoi ( n-1 , y , x , z ); } } //Hanoi

74 第五章 串 在计算机的各方面应用中，非数值处理问题的应用越来越多。如程序源代码，在事务处理系统中，用户的姓名和地址及货物的名称、规格等，都是作为一种字符串数据进行处理的。 字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。

75 §5.1 串的基本概念 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃a0a1a2…an-1〃 (n≥0)
§5.1 串的基本概念 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃a0a1a2…an-1〃 (n≥0) 其中：s为串名，用双引号括起来的字符序列是串的值；ai(0≤i≤n-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Null string），如：s=〃〃，它的长度为零；仅由空格组成的的串称为空格串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’m a student〃的长度为13。

76 §5.2 串的存储结构 一、顺序存储 和线性表一样，可以用一组连续的存储单元依次存放串中各字符。利用字符单元地址的顺序表示串中字符的相邻关系。 struct string { char ch_string[maxlen]; int len ; }; 当计算机按字(Word)为单位编址时，一个存储单元由若干字节组成。这时，顺序存储结构有紧凑格式和非紧凑格式两种。

77 §5.3 串的基本运算 串的基本运算有赋值、串连接、求串长、取子串、子串定位、判断两个串是否相等、插入子串，删除子串等。在本节中，我们尽可能以C语言的库函数表示其中的一些运算，若没有库函数，则用自定义函数说明。 struct string { char ch_string[maxlen]; int len ; };

78 1、串连接 所谓串连接就是把一个串连接在另一个串的末尾，组成一个新串。
Struct string concat(s1,s2) struct string s1,s2; {struct string s; int i; if (s1.len+s2.len<=maxlen) { for (i=0;i<s1.len;i++ ) s.ch_string[i]= s1.ch_string[i]; for (i=0;i<s2.len;i++ ) s.ch_string[s1.len+i]= s2.ch_string[i]; s.len=s1.len+s2.len;} else s.len=0; return (s); }

79 2、串相等判断 当两个串的长度相等且各对应位置上的字符都相等时，两个字符串才相等。
int equal(s1,s2) struct string s1,s2; { int i; if (s1.len != s2.len) return (0); else {for (i=0; i<s1.len ;i++) if (s1.ch_string[i]!=s2.ch_string[i]) return (1); }

80 3、取子串 所谓取子串就是在给定字符串中从指定位置开始连续取出若干字符，然后将取出的字符作为子串的值。
struct string substr(s,n1,n2) struct string s; int n1,n2; { struct string sub; int i; if ((n1>=1)&&(n1<=s.len)&&(n2>=1)&& (n2<=s.len-n1+1)) {for (i=0; i<=n2 ;i++) sub.ch_string[i]=s.ch_string[n1+i] sub.len=n2; } else sub.len=0; return (sub); }

81 4、插入子串 所谓插入子串就是在指定位置上插入一个子串。
struct string insert(s,s1,n) struct string s,s1; int n; { struct string sub1,sub2,str; if ((s.len+s1.len<=maxlen)&&(n>=1)&& (n<=s.len+1)) { sub1=substr(s,1,n-1); sub2=substr(s,n,s.len-n+1); str=concat(concat(sub1,s1),sub2); } else str.len=0; return (str); }

82 5、子串定位 所谓子串定位就是给出子串在母串中的位置。子串的定位操作也称模式匹配。
int index(s,s1) struct string s,s1; { int i , j , k ; i=0; while (i<=s.len – s1.len) {j=i ; k=0 ; while ((k<s1.len)&&(s.ch_s[j]==s1.ch_s[k])) { j=j+1;k=k+1; } if (k==s1.len) return (i+1); else i=i+1; } return (0); }

83 第七章 树形结构 数据结构可分为线性结构和非线性结构两大类 树形结构：是一类非常重要的非线性结构，它用于描述数据之间的层次关系
第七章 树形结构 数据结构可分为线性结构和非线性结构两大类 树形结构：是一类非常重要的非线性结构，它用于描述数据之间的层次关系 本章主要介绍树、二叉树的定义、性质及存储结构

84 §7.1 树 1、树的定义 树(Tree)是包含n(n>0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：
§7.1 树 1、树的定义 树(Tree)是包含n(n>0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件： (1) 有且仅有一个结点K0它对于关系N来说没有前驱，称K0为树的根结点； (2) 除K0外，K中的每一个结点对于关系N来说有且仅有一个前驱； (3)K中各结点对关系N来说可以有m个后继

85 §7.2 树的常用术语 树的结点：包含一个数据元素及若干指向其子树的分支 结点的度：结点所拥有的子树的个数称为该结点的度
§7.2 树的常用术语 树的结点：包含一个数据元素及若干指向其子树的分支 结点的度：结点所拥有的子树的个数称为该结点的度 叶子：度为零的结点，又称终端结点 树的深度：树中各结点层次的最大值称为该树的深度

86 §7.3 二叉树 二叉数的定义 二叉数的存储结构：顺序存储结构、链式存储结构
§7.3 二叉树 二叉数的定义 二叉数的存储结构：顺序存储结构、链式存储结构 二叉数的遍历：就是按某一种规则访问树中的每一个结点，且使得每个结点均被访问一次，而且仅被访问一次。 二叉数的遍历方法：前序遍历、中序遍历、后序遍历

87 第九章 查找 查找(Searching) 又称检索。就是从一个数据元素集合中找出某个特定的数据元素；
第九章 查找 查找(Searching) 又称检索。就是从一个数据元素集合中找出某个特定的数据元素； 它是数据处理中经常使用的一种重要的操作，尤其是当所涉及的数据量较大时，查找算法的优劣对整个软件的效率影响很大； 本章首先介绍关于查找的基本概念，然后讨论查找的各种方法，最后对各种查找方法作一比较。

88 §9.1 查找的基本概念 查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合 对查找表进行的操作有以下四种
§9.1 查找的基本概念 查找表(Search Table) 是由同一类型的数据元素(或记录)构成的集合 对查找表进行的操作有以下四种 (1)查询某个特定的数据元素是否在查找表中 (2)检索某个特定的数据元素的各种属性 (3)在查找表中插入一个数据元素 (4)从查找表中删除某个数据元素

89 §9.1 查找的基本概念 静态查找表(Static Search Table) 若只对查找表进行查找和检索两种操作,则称此查找表为静态查找表
§9.1 查找的基本概念 静态查找表(Static Search Table) 若只对查找表进行查找和检索两种操作,则称此查找表为静态查找表 动态查找表(Dynamic Search table) 若再查找过程中同时插入查找表中不存在的记录,或从查找表中删除已存在的某个记录,则称此类表为动态查找表 关键字(Key) 标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录)

90 §9.2 线性表的查找 顺序查找(sequential Search) 也称线性查找,是一种最简单的查找方法,它属于静态查找 顺序查找方法
§9.2 线性表的查找 顺序查找(sequential Search) 也称线性查找,是一种最简单的查找方法,它属于静态查找 顺序查找方法 顺序查找的基本思想:从表的一端开始,顺序扫描线性表,依次用待查找的关键字值与线性表里各结点的关键字值逐个比较,若在表中找到了某个记录的关键字与待查找的关键字值相等,表明查找成功;如果找遍所有结点也没有与待查找的关键字值相等,则表明查找失败

91 §9.2 线性表的查找 main() {int a[100]={0,12,5,36,58,21,61,15,16,32,17};
§9.2 线性表的查找 main() {int a[100]={0,12,5,36,58,21,61,15,16,32,17}; int i,key; printf ("Input the Key:"); scanf ("%d",&key); a[0]=key; for (i=10;a[i]!=key;i--); if (i==0) printf ("Searching Fail!\n"); else {printf ("Searching Success!\n"); printf ("a[%d]=%d\n",i,key);} }

92 §9.2 线性表的查找 折半查找(binary Search)
§9.2 线性表的查找 折半查找(binary Search) 也称为二分查找,是一种效率较高的查找方法,查找时要求表中的结点按关键字的大小排序 折半查找方法 折半查找的基本思想:首先用要查找的关键字值与中间位置结点的关键字值相比较(这个中间结点把线性表分成了两个子表).比较结果相等,则查找成功;若不相等,再根据要查找的关键字值与该中间结点关键字值的大小确定下一步查找在哪个子表中进行

93 #include <stdio.h>
main() {int a[100]={0,5,13,19,22,37,56,64,75,80,88,92}; int low=1,high=11,mid,key,flag=0; printf ("Input the Key:"); scanf ("%d",&key); while (low<=high) {mid=(low+high)/2; if (key==a[mid]) {printf ("Searching Success!"); printf ("a[%d]=%d\n",mid,key); flag=1;break;} else if (key<a[mid]) high=mid-1; else low=mid+1; } if (flag==0) printf ("Searching Fail!\n");

94 §第十章 排 序 排序是在数据处理中经常使用的一种重要的算法。如何进行排序，特别是高效率的排序是计算机应用中的重要课题。
§第十章 排　序 排序是在数据处理中经常使用的一种重要的算法。如何进行排序，特别是高效率的排序是计算机应用中的重要课题。 排序的目的：是方便查找 排序分为：内部排序、外部排序 本章主要介绍几种常用的内部排序方法：插入排序、选择排序、交换排序的基本思想、排序步骤及实现方法

95 §10.1 排序的基本概念 关键字(Key) 标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录)
§10.1 排序的基本概念 关键字(Key) 标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录) 排序(Sorting) 是将一组记录按照记录中某个关键字进行有序（递增或递减）排列过程

96 §10.2 内部排序 插入排序 插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，并且插入后使文件仍然有序。 直接插入排序
§10.2 内部排序 插入排序 插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，并且插入后使文件仍然有序。 直接插入排序 每一趟将一个待排序的记录，按关键字的大小插入到已经排序的部分文件中适当位置，直到全部插入完成

97 main() {int a[100]={0,19,1,23,17,19,55,84,15}; int i,j; for(i=2;i<=8;++i) if(a[i]<a[i-1]) { a[0]=a[i]; for(j=i-1;a[0]<a[j];--j) a[j+1]=a[j]; a[j+1]=a[0]; } for(i=1;i<=8;i++) printf("%d ",a[i]); printf("\n"); }

98 §10.2 内部排序 折半插入排序 由于插入排序的基本操作是在一个有序表中进行查找和插入，而查找操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排列（Binary Insertion Sort），又称为二分法插入排序。

99 main() {int a[100]={0,19,1,23,17,19,55,84,15}; int i,j,low,high,m; for(i=2;i<=8;++i) if(a[i]<a[i-1]) {a[0]=a[i];low=1;high=i-1; while(low<=high) {m=(low+high)/2; if(a[0]<a[m]) high=m-1; else low=m+1;} for(j=i-1;j>=high+1;--j) a[j+1]=a[j]; a[high+1]=a[0];} for(i=1;i<=8;i++) printf("%d ",a[i]); printf("\n"); }

100 §10.2 内部排序 冒泡排序 冒泡排序的基本思想：将待排序的序列中的关键字r1.key与第二个关键字r2.key进行比较（从小到大），如果r1.key>r2.key则交换r1和r2记录序列中的位置，否则不交换，然后再接着对当前序列中的第二个和第三个记录作同样的比较，依次类推，直到序列中最后两个记录处理完为止。

101 main() {int a[100]={0,5,7,3,8,2,9,1,4}; int i,j,flag,temp; flag=1; for(i=1;i<9 && flag==1;i++) {flag=0; for(j=0;j<9-i;j++) if (a[j]>a[j+1]) {flag=1; temp=a[j];a[j]=a[j+1]; a[j+1]=temp;} } for(i=1;i<=8;i++) printf("%d ",a[i]); printf("\n");

102 §10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法
§10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法 排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。

103 void q_sort(int *a,int left,int right)
{ int partition; /* 分割元素 */ int temp, i,j,k; if ( left < right ) /* 是否继续分割 */ { i = left; /* 分割的最左 */ j = right + 1; /* 分割的最右 */ partition = a[left]; /* 取第一个元素 */ do { do { /* 从左往右找 */ i++; } while( a[i] < partition ); do { /* 从右往左找 */ j--; } while( a[j] > partition ); if ( i < j ) { temp = a[i]; a[i] = a[j]; a[j] = temp; } /* 交换数据 */ } while( i < j ); temp= a[left]; a[left] = a[j]; a[j] = temp;/* 交换数据 */ printf("输出结果: "); for ( k = left; k <= right; k++) /* 输出处理数据 */ printf("%d ",a[k]); printf("\n"); /* 换行 */ q_sort(a,left,j-1); /* 快速排序递归调用 */ q_sort(a,j+1,right); /* 快速排序递归调用 */ }

104 §10.2 内部排序 选择排序 直接选择排序的基本思想：从待排序的所有记录中，选取关键字最小的记录并将它与原始序列的第一个记录交换位置，然后从去掉了关键字最小的记录的剩余记录中选择关键字最小的记录与原始记录中的第二个记录交换位置。

105 main() {int a[100]={0,5,7,3,8,2,9,1,4}; int i,j,k,w; for(i=1;i<8;i++) {k=i; for(j=i+1;j<9;j++) if (a[j]<a[k]) k=j; if (k!=i) {w=a[i];a[i]=a[k];a[k]=w;} } for(i=1;i<=8;i++) printf("%d ",a[i]); printf("\n");

106 §10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法
§10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法 排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。

107 §10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法
§10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法 排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。

108 §10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法
§10.2 内部排序 快速排序 快速排序是由冒泡排序改进而得的，是一种分区交换排序方法 排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。