数据结构教案.doc

《数据结构教案.doc》由会员分享，可在线阅读，更多相关《数据结构教案.doc（24页珍藏版）》请在三一办公上搜索。

1、第1章 绪论1.2 基本概念和术语一、 数据、数据元素、数据项1 数据：凡能被计算机存储、加工的对象，通称为数据。2 数据元素：是数据的基本单位，通常具有完整、确定的实际意义。3 数据项：是数据不可分割的最小单位。注意：数据、数据元素、数据项是数据组织的三个层次。如：（80，90，100，110，120）、表格二、 数据的逻辑结构1 逻辑结构：数据元素之间的“邻接”关系2 四种逻辑结构线性结构：数据元素之间存在“一对一”的关系树形结构：数据元素之间存在“一对多”的关系图状结构：数据元素之间存在“多对多”的关系集合：数据元素之间没有邻接关系三、 数据的存储结构1 存储结构：数据元素在计算机内的存

2、放方式2 两种存储结构顺序存储：将数据元素依次存放到一组连续的存储单元中。链式存储：将数据元素存放到非连续的存储单元中，并利用指针将各个存储单元链接起来。四、 数据的基本操作 加工型操作：改变数据元素的个数或数据元素的内容 引用型操作：数据元素的个数或数据元素的内容均未改变五、 数据结构1含义：包括三方面的内容：逻辑结构：反映数据元素之间的邻接”关系存储结构：反映数据元素在计算机内的存放方式数据的操作2. 数据按结构分，可分为4类，每一类对应着一种逻辑结构数据逻辑结构线性表线性结构树树型结构图图状结构查找表集合1.3 算法描述1 算法：解决问题的方法和步骤。2 算法的描述方法 框图 非形式语言

3、：如中文 类C语言程序 C语言程序1.4 算法分析1 对同一问题，可以设计多种不同的算法，但必有一种算法的时间效率最高。2 估算一个算法的运行时间 确定问题的输入规模n。 根据问题的特点，选择一种操作作为“标准操作”。（通常以条件判断或赋值语句为标准操作） 确定在给定输入下共执行多少次标准操作，从而算出运行时间T。3 算法的时间复杂度对算法的运行时间T(n)，忽略所有的常数、低次项，忽略最高项的系数，称为算法的时间复杂度，以O表示。运行时间时间复杂度T(n)=c常数阶O(1)T(n)=cn线性阶O(n)T(n)=cn2平方阶O(n2)指数阶O()对数阶O()1.5 指针和结构一、什么是指针1存

4、储单元的地址每一个存储单元由一个或多个字节组成，存储单元中第一个字节的编号称为存储单元的地址。2什么叫指针？指针总是指向某个变量。指针的值是所指向变量的地址，指针的类型是所指向变量的类型。二、指针变量1指针变量的定义类型 *指针变量名;例：int *p;解释：定义一个指针p，它只能指向int型变量。2两个运算符&：取地址运算符，例&i*：指针运算符，例*p例：int *p,i=3; p=&i; printf(%d, %d n,i,*p);说明： &和*互为逆运算，即：&*p=p，*&i=i 定义指针变量时，指针变量名前面的“*”不是指针运算符。 指针可以与整数进行加、减运算。指针n=指针的原值

5、sizeof(指针的类型)n 同类型的两个指针可以相互赋值。三、指针与数组1数组名代表该数组的首地址，例a= =&a02设int a6，则ai ，*(a+i)是等价的&ai ，a+i是等价的3表示数组元素的方法 下标法：例ai 指针法：例*(a+i)4设指针p指向数组a的某一个元素，则p+：使p指向数组的下一个元素；四、结构1定义结构类型 struct 结构名 成员定义列表例：struct person int no; char name6;2定义结构变量struct person x;1 引用结构变量的成员结构变量名成员名2 结构变量的初始化3 结构指针例：已知struct person x

6、,*p; p=&x;则表示x 的no成员有三种形式：x.no，p-no，(*p).no 第2章 线性表21 线性表的定义1线性表的表示形式： L=（a1，a2，a3，an）2线性表的基本操作 每种操作都采用一个函数来完成，这些函数是自定义函数，使用之前必须先定义。22 线性表的顺序存储结构一、顺序表的类型定义顺序表实际是一个结构变量，包括两个域：datas：存放线性表的元素，last：存放线性表的长度。typedef struct 类型 datasmaxsize; int last; sequenlist;sequenlist L;二、为线性表L=（a，b，c，d，）创建一个顺序表，要求L的第

7、1个元素存入数组的1号元素中。typedef struct char datas20; int last; sequenlist;void main() sequenlist L; char ch; int i=1; ch=getchar(); while(ch!=n) L.datasi=ch; i+; ch=getchar(); L.last=i-1;for(i=1;inext=null3单链表的建立（尾插入法）例：为L=（a，b，c，d，）创建单链表。#include malloc.h#include stdio.htypedef struct node char data; struct

8、 node *next; linklist;void main() char ch; /定义三根指针，head指向头结点，t指向新产生的结点，last指向最后的结点 linklist *head, *t, *last; t=malloc(sizeof(linklist); t-next=NULL; head=t; last=t; ch=getchar(); while(ch!=n) t=malloc(sizeof(linklist); t-data=ch; t-next=NULL; last-next=t; last=t; ch=getchar(); 4单链表的插入需设置两支指针：p、t。p：

9、指向待插入结点的前一个结点t：指向新产生的结点5单链表的删除需设置两支指针：p、t。p：指向待删除结点的前一个结点t：指向待删除结点三、其它链表 单链表单向循环链表（循环链表）双向循环链表（双向链表）1 循环链表最后一个结点的指针域不是NULL，而是指向头结点。2 双链表每个结点包含三个域：一个数据域和两个指针域。双链表的特点是找结点的前趋和后继都很容易。第4章 栈和队列41 栈一、栈的定义1基本概念栈顶、栈底、进栈、出栈、空栈2栈的表示形式S=（a1，a2，a3，an）按a1，a2，a3，an 顺序进栈，但按an，a3，a2，a1顺序出栈。a1称为栈底元素，an称为栈顶元素。栈又称后进先出线

10、性表（LIFO）表。二、栈的顺序存储结构1顺序栈的类型定义顺序栈实际上是一个结构变量，包括两个域：data：存放栈中元素，top：存放栈顶元素所在单元的编号。typedef struct 类型 datamaxsize; int top; seqstack;seqstack s;栈空条件：s.top= 0；栈满条件：s.top=maxsize-12为S=（a，b，c，d，）创建一个顺序栈，要求S的第1个元素存入数组的1号元素中。typedef struct char data20; int top; seqstack;void main() seqstack s; char ch; int i=

11、1; ch=getchar(); while(ch!=n) s.datai=ch; i+; ch=getchar(); s.top=i-1;for(i=1;idata=ch;t-next=top;top=t; ch=getchar(); printf(出栈顺序为:n);while(top-next!=NULL) printf(%-4c,top-data); top=top-next;printf(n);42 队列一、队列的定义1基本概念队头、队尾、空队2队列的表示形式：Q=（a1，a2，a3，an）按a1，a2，a3，an 顺序进队，仍按a1，a2，a3，an 顺序出队。队列又称先进先出线性表

12、（FIFO表）二、队列的顺序存储结构1顺序队的类型定义顺序队实际上是一个结构变量，包括三个域：data：存放队列的元素；front：存放队头元素所在单元的前一个单元的编号；rear：存放队尾元素所在单元的编号。typedef struct 类型 datamaxsize; int front, rear; seqqueue;seqqueue q;2顺序队的建立例：为Q=（a，b，c，d，）创建一个顺序队。typedef struct char data20; int front, rear; seqqueue;void main() seqqueue q; char ch; int i=0; c

13、h=getchar(); while(ch!=n) q.datai=ch; i+; ch=getchar(); q.front= -1; q.rear=i-1; /输出队列元素for(i=0;inext=NULL; lq.front=p; lq.rear=p; ch=getchar(); while(ch!=n) p=malloc(sizeof(node); p-data=ch;p-next=NULL;lq.rear-next=p;lq.rear=p;ch=getchar(); /输出队列中的元素 p=lq.front-next; while(p!=NULL) printf(%-4c,p-da

14、ta); p=p-next; printf(n);3链队的队空条件lq.front=lq.rear4 各式链式存储结构比较表有无头结点用何指针标识创建办法链表有头指针head尾插入法链栈无栈顶指针top头插入法链队有由包含front和rear的结构变量lq标识。尾插入法第6章 树和二叉树61 树的定义和基本操作一、树型结构和线性结构树型结构：每个结点可以有多个直接后继线性结构：每个结点只有一个直接后继二、树的定义树是n（n0）个结点的有限集合，任意一棵非空树满足： 有且只有一个根结点； 其余结点被分成若干个互不相交的集合，每个集合又是一棵树。三、树的特点 除根结点外，每个结点有且只有一个直接前

15、趋； 除最底层的结点外，每个结点可以有多个直接后继； 若某棵树有多个结点，则每个结点可以看作根结点，要么是整棵树的根结点，要么是某棵子树的根结点。四、基本术语 结点的度、树的度 叶子结点、分支结点度为0的结点称为叶子结点；度大于0的结点称为分支结点。 孩子结点、双亲结点、兄弟结点具有同一双亲的结点互为兄弟 结点的子孙、结点的祖先 结点的层数、树的高度结点的层数：从树根开始算起，根的层数为1；树的高度：树中所有结点层数的最大值。62 二叉树一、二叉树的定义：参考P73二、二叉树的性质（1）二叉树的第i层上最多有个结点。（2）深度为k的二叉树最多有个结点。（3）满二叉树：除最底层的结点外，其余结点

16、的度均为2的二叉树。（4）完全二叉树：如果对一棵满二叉树的最底层从最右边开始，连续删去若干个结点，就得到完全二叉树。（5）对一棵完全二叉树的结点进行编号，则对编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1，双亲结点的编号为三、二叉树的存储结构1顺序存储结构：先将二叉树的结点依次编号，再将结点存入一维数组中，数组元素的序号对应结点的编号。对二叉树的结点进行编号，编号原则是： 根结点的编号为1。 对于编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1。 满二叉树、完全二叉树一般采用顺序存储结构，一般二叉树则采用链式存储结构。2链式存储结构： 二叉链表：每个结点包括三个域：数

17、据域data，左指针域lchild，右指针域rchild 对二叉树的访问只能从根指针root开始，二叉树为空的条件：root=NULL。四、二叉树的遍历1什么叫二叉树的遍历？按照一定规律访问二叉树的所有结点，使得每个结点均被访问一次且仅被访问一次。2二叉树由三部分组成：根结点、左子树、右子树3三种遍历次序 先根遍历：根结点、左子树、右子树 中根遍历：左子树、根结点、右子树 后根遍历：左子树、右子树、根结点63 树和森林一、对树中各结点编号从根结点开始，按层依次编号，且根结点的编号为0。二、树的存储结构 双亲链表 孩子链表 孩子兄弟链表1双亲链表（1）每个结点包含两个域名：数据域：存放该结点的数

18、据元素指针域：存放该结点之双亲的编号（2）将所有结点组织成一维数组，并以各结点的编号作为数组元素的序号。2孩子链表（1）为每个结点建立一个“孩子链表”。（2）结点x的孩子链表是一个带头结点的单链表，用于存储该结点的所有孩子的编号。（3）将所有头结点组织成一维数组。3孩子兄弟链表（1）每个结点含有三个域：数据域：存放该结点的数据元素孩子域：用于指向该结点的第一个孩子兄弟域：用于指向该结点的第一个兄弟（2）二叉树的二叉链表与树的孩子兄弟链表在组织结构完全相同。二叉链表孩子兄弟链表数据域数据域左指针域孩子域右指针域兄弟域三、树与二叉树的转换1树转换为二叉树 将树转换为二叉树，只要将树中各结点的第一个

19、孩子看作左孩子，第一个兄弟看作右孩子即可。 任一棵树对应的二叉树的右子树必空。2森林转换为二叉树 将每棵树先转换为二叉树B1，B2，Bn 以B1为基准，将B2作为B1根结点的右子树，将B3作为B2根结点的右子树，3二叉树转换为森林 将二叉树根结点的右子树撤去，得到多棵二叉树B1，B2，Bn 将二叉树分别转换为树T1，T2，Tn。四、树的遍历 先根遍历：根结点、各棵子树 后根遍历：各棵子树、根结点 层次遍历64哈夫曼树和判定树一、基本术语1叶子结点的路径长度：从根结点到某个叶子结点所经过的分支数。2树的路径长度：树中各叶子结点的路径长度之和。3叶子结点的权：各叶子结点出现的概率。4带权路径长度（

20、WPL）各个叶子结点的权wi与相应的路径长度li乘积之和，称为树的带权路径长度。二、哈夫曼树1什么叫哈夫曼树？带权路径长度WPL最小的二叉树，称为哈夫曼树。特点： 一般地说，权值越大的叶子结点离根越近。 哈夫曼树的时间性能最好，是最优的二叉树。 哈夫曼树中各结点的度只能是0或2。 具有n个结点的哈夫曼树共有2n-1个结点。2如何构造一棵哈夫曼树？（参考P88）3哈夫曼编码 对一棵哈夫曼树约定：指向左孩子的分支表示为0，指向右孩子的分支表示为1。取从根到叶子结点一路上的“0”或“1”组成的序列，称为叶子结点的前缀编码。三、分类和判定树1用于描述分类问题的二叉树称为判定树。判定树的每个分支结点对应

21、一种判断，每个叶子结点对应一种分类结果。2一个分类问题对应着若干棵判定树，其中必有一棵判定树的WPL最小，WPL又称平均比较次数。3一棵判定树对应着一种算法，哈夫曼树对应的算法的时间性能最好。4如何对一个分类问题写最优的算法？ 对分类结果画哈夫曼树； 根据哈夫曼树写算法；第7章 图71 图的定义和术语一、图的定义图G由顶点集V和边集E组成，记为G=（V，E）。 最简单的图只有一个顶点； 每条边由其连接的两个顶点表示：例：无向边（v1 ，v2）；有向边，二、术语1邻接点 若顶点vi，vj存在一条边，则vi，vj互为邻接点。在有向边中，称vi为起点，vj为终点。2顶点的入边，出边 若存在一条有向边

22、，则称它为vi的出边，vj的入边。3顶点的入度，出度 顶点的度：与顶点v相关联的边数，记为D（v）； 顶点的入度，出度：在有向图中，顶点v的入边的数目，称为入度，记为ID（v）； 顶点v的出边的数目，称为出度，记为OD（v）； D（v）= ID（v）+ OD（v）4无向完全图，有向完全图无向完全图：任意两个顶点之间都存在一条边的无向图；有向完全图：任意两个顶点之间都存在方向相反的两条边的有向图；5 子图设有两个图G=（V，E）和G=（V，E），若V是V的子集，E是E的子集，则G是G的子图。6 连通图和连通分量连通：在无向图中，若两个顶点有路径，则称两顶点是连通的；连通图：任意两个顶点都连通的无

23、向图；连通分量：无向图中的极大连通子图。7 强连通图和强连通分量强连通：在有向图中，若vi到vj，vj到vi都有路径，则称vi，vj是强连通的；强连通图：任意两个顶点都强连通的有向图；强连通分量：有向图中的极大连通子图。8带权图：又称网 带权有向图（有向网） 带权无向图（无向网）72 图的存储结构一、邻接矩阵1邻接矩阵的构建 将各个顶点排成一行和一列，形成矩阵。 若行、列顶点之间存在一条边，则对应元素记1，否则，对应元素记0。2邻接矩阵的特点无向图的邻接矩阵是对称的，有向图的邻接矩阵一般不对称。3用邻接矩阵表示加权图只要把1元素换成相应边的权值，0元素换成即可。4 邻接矩阵的用途便于查找每个顶

24、点的度、入度、出度。无向图：每个顶点的度等于该顶点相应的行或列中1元素的个数。有向图：每个顶点的出度等于该顶点相应行中1元素的个数，入度等于相应列中1元素的个数。二、邻接链表树的孩子链表、图的邻接链表组织结构相同。1邻接链表的构建 为每个顶点建立一个邻接链表，一个图有几个顶点，就有几个邻接链表。 顶点x的邻接链表是一个带头结点的单链表，用于存储与x相邻接的顶点序号。 将所有头结点组织成一维数组。2邻接链表的用途便于求顶点的度、出度。无向图：每个顶点的度等于它的邻接链表中表结点的个数。有向图：每个顶点的出度等于它的邻接链表中表结点的个数。3如何求顶点的入度？构造一个逆邻接链表，即顶点x的逆邻接链

25、表存储的是与x的入边相关联的顶点序号。注：一个图的邻接矩阵是唯一的，但邻接表一般不唯一。73 图的遍历1树的遍历 先根遍历：根结点、各棵子树 后根遍历：各棵子树、根结点 层次遍历2图的遍历：适应于无向图，也适应于有向图。 深度优先搜索遍历：类似树的先根遍历。 广度优先搜索遍历：类似树的层次遍历3深度优先搜索遍历：首先访问出发点Vi，然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索。深度优先搜索遍历、广度优先搜索遍历得到的顶点序列不唯一。74 图的应用一、最小生成树1什么叫生成树？从n个顶点的连通图G中，取它的全部顶点和n-1条边构成子图G，如果这些边刚好将G的全部

26、顶点连通但又不形成回路，则称子图G是G的一棵生成树。注意： 一个连通图可以有多棵生成树。 生成树是边数极少的连通子图。 连通分量：指极大连通子图。 根据图的宽度优先遍历或深度优先遍历可构造生成树。2最小生成树 生成树的权：各条边权值之和权值最小的生成树，称为最小生成树。 带权无向图才可构造最小生成树。求造价最低的通讯网问题，实际是求最小生成树问题。3构造最小生成树的算法：Prim（普里姆）算法二、拓扑排序1拓扑序列在有向图中，若不存在回路，则所有顶点可排成一个线性序列，以便列出各顶点的前后关系，称此序列为拓扑序列。2拓扑排序：实现有向图的一个拓扑序列的过程。任何一个有向无环图，其全部顶点可以排

27、成一个拓扑序列，且其拓扑序列不唯一。若图中入度为0的顶点和出度为0的顶点都是唯一的，则其拓扑序列是唯一的。3构成有向图拓扑序列的过程 从图中选择一个入度为0的顶点，输出该顶点。 从图中删除该顶点及其相关联的所有边。 重复执行1，2，直到找不到入度为0的顶点。三、最短路径1最短路径问题 带权有向图才存在最短路径问题。 图的路径长度：一条路径上各条边的权值之和。2求一个源点到其余各个顶点的最短路径：Dijkstra 迪杰斯特拉）算法从源点到其余各个顶点的最短路径中，先求最短的一条，再求次短的一条，以此顺序，最后求最长的一条。3Dijkstra算法描述 假设S为顶点集合，初值为源点v0。 首先从v0

28、出发的所有边中找出权值最小的边的终点加入到S中。 下一条最短路径是终点不在S中，中间只经过S中的顶点且路径长度最短，找到后将终点加入到S中。 反复执行（3），直到所有顶点都加入到S中。例：根据P115图7.17，求顶点V1到其余各顶点的最短路径。终点V2V3V4V5集合S第1次1030100V1，V2第2次106030100V1，V2，V4第3次10503090V1，V2，V4，V3第4次10503060V1，V2，V4，V3，V5V1到各顶点的最短路径是：V1V2：（V1，V2）V1V4：（V1，V4）V1V3：（V1，V4，V3）V1V5：（V1，V4，V3，V5）第8章 查找81 基本概

29、念一、各种数据的逻辑结构数据逻辑结构特点线性表线性结构数据元素之间存在着一对一的逻辑关系。树树型结构数据元素之间存在着一对多的逻辑关系。图图状结构数据元素之间存在着多对多的逻辑关系。查找表集合数据元素之间不存在任何关系。二、查找表1定义：查找表是一种以集合为逻辑结构，以查找为核心运算的数据结构。例：一个平面表格，当各条记录可以任意排列时，就成为查找表。2关键字：由一个或多个数据项组成，可标识若干条记录；主键：由一个或多个数据项组成，能唯一标识一条记录。3查找：在查找表中寻找关键字值等于给定值的记录，若找到，则返回记录号；否则，则查找失败。4静态查找表和动态查找表静态查找表：只做建表、查找操作；

30、动态查找表：做建表、查找、插入、删除操作。82 静态查找表 静态查找表的存储结构：顺序表、有序表、索引顺序表一、 顺序表上的查找1 顺序表的类型定义typedef struct int key; 类型 data; . ELEMENT;typedef struct ELEMENT rmaxsize; int len; SSTABLE;2 在顺序表上实现查找运算，采用“顺序查找法”对顺序表从后往前依次查找关键字值等于给定值k的记录，若找到，则返回记录的序号。3 查找长度：记录的键值与给定值的比较次数，称为查找长度。它用来衡量查找算法的时间性能。 查找成功的平均查找长度ASL= （n为记录条数） 查

31、找不成功的平均查找长度为：n二、 有序表上的查找1 查找表中各元素之间无任何逻辑关系，但各元素的键值存在次序关系。2 有序表：各元素按关键字值升序（或降序）排列的顺序表。3 在有序表上实现查找运算，采用“二分查找法”每次将查找区间中间位置上的记录键值与给定值k作比较，若不等则缩小查找区间，直到查找成功，或查找区间长度为0。例：在有序表（5，12，30，45，70，73，80，85，89，100，103，109）查找关键字值为85的记录，则二分查找法的过程为：5，12，30，45，70，73，80，85，89，100，103，109 1 2 3 4 5 6 7 8 9 10 11 12第1次查找

32、：low=1，high=12，则mid=6第2次查找：low=7，high=12，则mid=9第3次查找：low=7，high=8，则mid=7第4次查找：low=8，high=8，则mid=8（8号记录的关键字值为85，查找成功。）三、 索引顺序表上的查找1 索引顺序表由两部分组成：一个顺序表和一个索引表，且满足： 顺序表的记录键值“按块有序”。 对于顺序表的每一块，索引表有相应的一个“索引项”，每个索引项含两大域：块起始位置和块内最大键值。2在索引顺序表上实现查找运算，采用“分块查找法” 确定待查键值所在的块。（索引表） 在块内查找待查的键值。（顺序表） 小结：三种查找法的比较：顺序查找二

33、分查找分块查找查找效率最低最高居中限制最少最多居中83 动态查找表 静态查找表（顺序表、有序表、索引顺序表）查找表 动态查找表（二叉排序树、散列表）一、 二叉排序树对二叉树进行中根遍历，若得到的结点键值的序列是逐渐递增的有序序列，则称为二叉排序树。特点：任一结点的键值大于其左子树上所有结点的键值，小于其右子树上所有结点的键值。二、 二叉排序树的生成 生成二叉排序树的过程就是一个反复插入结点的过程，且保证插入结点后仍为一棵二叉排序树。 含有n个结点的二叉排序树的形态不唯一，但中根遍历的结果是唯一的。三、二叉排序树的查找对二叉排序树查找，若查找成功，则返回指向该结点的指针，否则返回null。四、 二叉排序树的删除从二叉排序树删除一个结点后，要保证仍为一棵二叉排序树。设待删结点为P： P为叶子结点 P只有一棵非空子树：以P的非空子树的根结点取代P P有两棵非空子树：以P的左孩子A取代P，并将P的右子树插入到A的右子树中。2015241216111413PA202412111413A16