数据结构教案

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

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

3、描述方法广框图非形式语言：如中文类C语言程序< C语言程序1.4算法分析1. 对同一问题，可以设计多种不同的算法，但必有一种算法的时间效率最高。2. 估算一个算法的运行时间 确定问题的输入规模 n。 根据问题的特点，选择一种操作作为“标准操作。(通常以条件判断或赋值语句为标准操作) 确定在给定输入下共执行多少次标准操作，从而算出运行时间T。3. 算法的时间复杂度对算法的运行时间 T(n),忽略所有的常数、 低次项，忽略最高项的系数，称为算法的时 间复杂度，以0表示。运行时间时间复杂度T(n )=c常数阶0(1)T( n)=c n线性阶0(n)2T(n)=cn2平方阶0(n )T(n) =

4、c 2n指数阶0( 2n)T(n) = c log ；对数阶0( logn)1.5指针和结构 一、什么是指针1存储单元的地址 每一个存储单元由一个或多个字节组成， 存储单元中第一个字节的编号称为存储单元的 地址。2什么叫指针？指针总是指向某个变量。 指针的值是所指向变量的地址， 指针的类型是所指向变量的类 型。二、指针变量1指针变量的定义类型 * 指针变量名 ;例： int *p;解释：定义一个指针p，它只能指向int型变量。2两个运算符& ：取地址运算符，例 &i* ：指针运算符，例 *p例： int *p,i=3;p=&i;printf("%d, %d n

5、",i,*p);说明： & 和*互为逆运算，即：&*p=p ， *&i=i 定义指针变量时，指针变量名前面的“*不是指针运算符。 指针可以与整数进行加、减运算。指针土 n=指针的原值土 sizeof(指针的类型)xn 同类型的两个指针可以相互赋值。三、指针与数组1数组名代表该数组的首地址，例a= =&a02设 int a6 ，那么ai , *(a+i)是等价的&ai ， a+i 是等价的3表示数组元素的方法下标法：例 ai指针法：例 *(a+i)4设指针p指向数组a的某一个元素，那么p+ :使p指向数组的下一个元素；四、结构1定义结构类型str

6、uct 结构名 成员定义列表 例： struct person int no;char name6;2定义结构变量struct person x;1 引用结构变量的成员 结构变量名成员名2 结构变量的初始化3 结构指针例： struct person x,*p; p=&x;那么表示 x 的 no 成员有三种形式： x.no ， p->no ， (*p).no第 2章 线性表2 1 线性表的定义1线性表的表示形式：L= ( al , a2, a3,，3n)2线性表的根本操作 每种操作都采用一个函数来完成，这些函数是自定义函数，使用之前必须先定义。2 2 线性表的顺序存储结构一、顺序

7、表的类型定义 顺序表实际是一个结构变量，包括两个域： datas：存放线性表的元素，last:存放线性表的长度。 typedef struct 类型 datasmaxsize;int last; sequenlist;sequenlist L;二、为线性表L= ('a', 'b', 'c', 'd',)创立一个顺序表，要求L的第1个元素存入数组的 1 号元素中。typedef struct char datas20;int last; sequenlist;void main() sequenlist L;char ch;int

8、i=1;ch=getchar();while(ch!='n') L.datasi=ch;i+; ch=getchar();L.last=i-1;for(i=1;i<=L.last;i+)printf("%4c",L.datasi);printf("n");三、根本操作在顺序表上的实现1. insert(a,x,i):将元素x插入到顺序表a的第i号元素之前2. delete(a,i):删除顺序表a的第i 号元素第3章 链式存储结构3. 1 线性表的链式存储结构一、顺序表的优缺点优点:空间利用率高，可以随机读取表中任一元素。 缺点:插入

9、、删除操作要移动大量的数据，时间性能差。二、单链表1. 单链表的组成每个单链表由多个结点组成，每个结点包含两个域:数据域data :存放线性表的元素指针域next :存放下一个结点的地址2. 单链表的类型定义typedef struct node 类型 data;struct node *next; linklist;linklist *head;说明：不带头结点的单链表为空的条件： head=null 带头结点的单链表为空的条件： head->next=null 3单链表的建立(尾插入法)例：为L= ('a', 'b', 'c', 

10、9;d',)创立单链表。#include "malloc.h"#include "stdio.h"typedef struct node char data;struct node *next; linklist;void main() char ch;last 指向最后的结点/定义三根指针,head 指向头结点, t 指向新产生的结点,linklist *head, *t, *last;t=malloc(sizeof(linklist);t->next=NULL;head=t;last=t;ch=getchar();while(ch!=&

11、#39;n') t=malloc(sizeof(linklist);t->data=ch;t->next=NULL;last->next=t;last=t;ch=getchar();4单链表的插入需设置两支指针：p、 t 。p：指向待插入结点的前一个结点t:指向新产生的结点5.单链表的删除需设置两支指针：p、t。p：指向待删除结点的前一个结点 t:指向待删除结点三、其它链表"单链表w 单向循环链表循环链表.双向循环链表双向链表1. 循环链表最后一个结点的指针域不是 NULL，而是指向头结点。2. 双链表每个结点包含三个域：一个数据域和两个指针域。双链表的特点

12、是找结点的前趋和后继都很容易。第4章栈和队列4. 1栈一、栈的定义1. 根本概念栈顶、栈底、进栈、出栈、空栈2. 栈的表示形式S= ai , a2, a3,，an按ch,a2,33,，On顺序进栈，但按an,，sfe,a?,ai顺序出栈。ai称为栈底元素，an称为栈顶元素。栈又称后进先出线性表LIFO 表。二、栈的顺序存储结构1. 顺序栈的类型定义顺序栈实际上是一个结构变量，包括两个域：data：存放栈中元素，top：存放栈顶元素所在单元的编号。typedef struct类型 datamaxsize;int top; seqstack;seqstack s;栈空条件：s.top= 0;栈满条

13、件： s.top=maxsize-11号2. 为S= ('a', 'b', 'c', 'd',)创立一个顺序栈，要求S的第1个元素存入数组的元素中。typedef struct char data20;int top; seqstack;void main() seqstack s;char ch;int i=1;ch=getchar();while(ch!='n') s.datai=ch;i+;ch=getchar();s.top=i-1;for(i=1;i<=S.top;i+)printf("%

14、-4c",s.datai);printf("n");三、栈的链式存储结构1 .链栈的类型定义typedef struct node 类型 data;struct node *next; linkstack;linkstack *top; 链栈总是以栈顶指针 top 开头, top 用于标识整个链栈。 链栈只会出现栈空情况,栈空条件为:top=NULL 。2.链栈的建立(头插入法)例：为S= ('a', 'b', 'c', 'd',)创立一个链栈。#include "malloc.h"

15、;#include "stdio.h"typedef struct node char data;struct node *next; linkstack;void main() linkstack *top,*t;char ch;top=NULL;ch=getchar();while(ch!='n') t=malloc(sizeof(linkstack);t->data=ch;t->next=top;top=t;ch=getchar();printf(" 出栈顺序为 :n");while(top->next!=NULL

16、) printf("%-4c",top->data);top=top->next;printf("n");4 2 队列一、队列的定义1根本概念队头、队尾、空队2队列的表示形式：Q= ( a1 , a2 , a3,，爲)按ai, a?, a3，an顺序进队，仍按 ai, a?, a3，a顺序出队。 队列又称先进先出线性表( FIFO 表)二、队列的顺序存储结构1顺序队的类型定义顺序队实际上是一个结构变量，包括三个域：data：存放队列的元素；front ：存放队头元素所在单元的前一个单元的编号；rear :存放队尾元素所在单元的编号。typed

17、ef 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;ch=getchar();while(ch!='n') q.datai=ch;i+;ch=getchar();q.front=

18、-1;q.rear=i-1;/输出队列元素for(i=0;i<=q.rear;i+)printf("%-4c",q.datai);printf("n");3.顺序队的队空、队满队空条件：q.fron t=q.rear队满条件：q.rear=maxsize-1队真满：q.front = -1;q.rear= maxsize-11队假满：q.front 丰-1;q.rear= maxsize-14 顺序队的插入、删除操作 插入新元素：rear后移而front不变q.rear=q.rear+1;q.dataq.rear=x; 删除元素：front后移而r

19、ear不变q.fron t=q.fr on t+1;三、循环队1 为充分利用存储空间，克服“假满，可以把数组看作首尾相接的圆环，形成“循环队2 循环队的性质 存储单元的编号从 0开始，按顺时针方向，编号逐渐增大，最后一个存储单元的编号为 maxsize-1。 在循环队中，当q.rear=maxsize-1时，只要数组有两个以上的存储单元为空，就可以把新元素插入到空单元中。 当队列中元素的个数为maxsize-1时，就认为队满。3 循环队的插入、删除操作 插入新元素：rear顺时针移动而front不变q.rear=(q.rear+1)% maxsize;q.dataq.rear=x; 删除元素：

20、front顺时针移动而rear不变q.fron t=(q .fron t+1)%maxsize;4循环队的队空、队满队空条件：q.fron t=q.rear队满条件：(q.rear+1)% maxsize=q.fr ont四、队列的链式存储结构1 链队的类型定义 链队是一个含有队头指针front和队尾指针rear的单链表； front指向队头结点的前一个结点，rear指向队尾结点； 链队由包含 front 和 rear 的结构变量 lq 标识。 typedef struct node_st 类型 data;struct node_st *next; node;typedef struct no

21、de *front;node * rear; linkqueue;linkqueue lq;2链队的建立(尾插入法)例：为Q= ('a', 'b', 'c', 'd',)创立一个链队。#include "malloc.h"#include "stdio.h"typedef struct node_st char data;struct node_st *next; node;typedef struct node *front;node * rear; linkqueue;void main

22、() char ch;linkqueue lq;node *p;p=malloc(sizeof(node);p->next=NULL;lq.front=p;lq.rear=p;ch=getchar();while(ch!='n') p=malloc(sizeof(node);p->data=ch;p-> next=NULL; Iq.rear- >n ext=p; lq.rear=p; ch=getchar();/输出队列中的元素p=lq .front->n ext;while(p!=NULL) prin tf("%-4c",p-

23、>data); p=p->n ext;prin tf("n );3. 链队的队空条件Iq.fron t=lq.rear4.各式链式存储结构比拟表有无头结点用何指针标识创立方法链表有头指针head尾插入法链栈无栈顶指针top头插入法链队有由包含front和rear的结构变量lq标识。尾插入法第6章树和二叉树6. 1树的定义和根本操作一、树型结构和线性结构树型结构：每个结点可以有多个直接后继线性结构：每个结点只有一个直接后继二、树的定义树是n n?0个结点的有限集合，任意一棵非空树满足： 有且只有一个根结点； 其余结点被分成假设干个互不相交的集合，每个集合又是一棵树。三、树的

24、特点 除根结点外，每个结点有且只有一个直接前趋； 除最底层的结点外，每个结点可以有多个直接后继； 假设某棵树有多个结点，那么每个结点可以看作根结点，要么是整棵树的根结点，要么是某 棵子树的根结点。四、根本术语 结点的度、树的度 叶子结点、分支结点度为0的结点称为叶子结点；度大于0的结点称为分支结点。 孩子结点、双亲结点、兄弟结点具有同一双亲的结点互为兄弟 结点的子孙、结点的祖先 结点的层数、树的高度结点的层数：从树根开始算起，根的层数为1；树的高度：树中所有结点层数的最大值。6. 2二叉树一、二叉树的定义：参考 P73二、二叉树的性质i J(1) 二叉树的第i层上最多有2 个结点。(2) 深度

25、为k的二叉树最多有2k -1个结点。(3) 满二叉树：除最底层的结点外，其余结点的度均为2的二叉树。(4 )完全二叉树：如果对一棵满二叉树的最底层从最右边开始，连续删去假设干个结点，就 得到完全二叉树。(5)对一棵完全二叉树的结点进行编号，那么对编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1，双亲结点的编号为 -i 2三、二叉树的存储结构1顺序存储结构：先将二叉树的结点依次编号，再将结点存入一维数组中，数组元素的序号对应结点的编号。对二叉树的结点进行编号，编号原那么是： 根结点的编号为1。 对于编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1。 满二叉树、完全二叉树一

26、般采用顺序存储结构，一般二叉树那么采用链式存储结构。2链式存储结构： 二叉链表：每个结点包括三个域：数据域data,左指针域Ichild，右指针域rchild 对二叉树的访问只能从根指针root开始，二叉树为空的条件：root=NULL 。四、二叉树的遍历1什么叫二叉树的遍历？按照一定规律访问二叉树的所有结点，使得每个结点均被访问一次且仅被访问一次。2. 二叉树由三局部组成：根结点、左子树、右子树3. 三种遍历次序 先根遍历：根结点、左子树、右子树 中根遍历：左子树、根结点、右子树 后根遍历：左子树、右子树、根结点6. 3树和森林、对树中各结点编号从根结点开始，按层依次编号，且根结点的编号为0

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

28、据域数据域左指针域孩子域右指针域兄弟域三、树与二叉树的转换1树转换为二叉树 将树转换为二叉树，只要将树中各结点的第一个孩子看作左孩子，第一个兄弟看作 右孩子即可。 任一棵树对应的二叉树的右子树必空。2. 森林转换为二叉树 将每棵树先转换为二叉树 Bl, B2,，Bn 以Bi为基准，将B2作为Bi根结点的右子树，将 B3作为B2根结点的右子树,3. 二叉树转换为森林 将二叉树根结点的右子树撤去，得到多棵二叉树Bi, B2,，Bn 将二叉树分别转换为树 Ti, T2,，Tn。四、树的遍历广先根遍历：根结点、各棵子树V后根遍历：各棵子树、根结点层次遍历6. 4哈夫曼树和判定树一、根本术语1叶子结点的

29、路径长度：从根结点到某个叶子结点所经过的分支数。2树的路径长度：树中各叶子结点的路径长度之和。3叶子结点的权：各叶子结点出现的概率。4. 带权路径长度WPL 各个叶子结点的权 Wi与相应的路径长度li乘积之和，称为树的带权路径长度。nWPL 八 whi T二、哈夫曼树1. 什么叫哈夫曼树？带权路径长度WPL最小的二叉树，称为哈夫曼树。特点： 一般地说，权值越大的叶子结点离根越近。 哈夫曼树的时间性能最好，是最优的二叉树。 哈夫曼树中各结点的度只能是0或2。 具有 n 个结点的哈夫曼树共有 2n-1 个结点。2如何构造一棵哈夫曼树？参考P883哈夫曼编码对一棵哈夫曼树约定： 指向左孩子的分支表示

30、为 0，指向右孩子的分支表示为 1。取从根 到叶子结点一路上的“ 0或“ 1组成的序列，称为叶子结点的前缀编码。三、分类和判定树1用于描述分类问题的二叉树称为判定树。判定树的每个分支结点对应一种判断，每个叶子结点对应一种分类结果。2一个分类问题对应着假设干棵判定树，其中必有一棵判定树的WPL 最小， WPL 又称平均比拟次数。3一棵判定树对应着一种算法，哈夫曼树对应的算法的时间性能最好。4如何对一个分类问题写最优的算法？ 对分类结果画哈夫曼树； 根据哈夫曼树写算法；第 7章 图 7 1 图的定义和术语 一、图的定义图 G 由顶点集 V 和边集 E 组成，记为 G= V ， E。 最简单的图只有

31、一个顶点； 每条边由其连接的两个顶点表示：例：无向边 v1 ， v2 ；有向边 v1 ，v2， v2 ，v1 二、术语1邻接点假设顶点 vi，vj 存在一条边，那么 vi，vj 互为邻接点。在有向边Vj , Vj中，称vi为起点，Vj为终点。 2顶点的入边，出边假设存在一条有向边Vi, Vj，那么称它为Vi的出边，Vj的入边。 3顶点的入度，出度 顶点的度：与顶点 V 相关联的边数，记为 DV； 顶点的入度，出度：在有向图中，顶点 V 的入边的数目，称为入度，记为ID V；顶点 V 的出边的数目，称为出度，记为ODV；DV= IDV+ ODV4. 无向完全图，有向完全图无向完全图：任意两个顶点

32、之间都存在一条边的无向图；有向完全图：任意两个顶点之间都存在方向相反的两条边的有向图；5. 子图设有两个图G= (V,E)和G'=(V,E'),假设V是V的子集，E'是E的子集，那么G是G的子图。6. 连通图和连通分量连通：在无向图中，假设两个顶点有路径，那么称两顶点是连通的；连通图：任意两个顶点都连通的无向图；连通分量：无向图中的极大连通子图。7. 强连通图和强连通分量强连通：在有向图中，假设 Vi至U Vj , Vj至U Vi都有路径，那么称 Vi , Vj是强连通的； 强连通图：任意两个顶点都强连通的有向图；强连通分量：有向图中的极大连通子图。&带权图：又

33、称网-带权有向图(有向网) 带权无向图(无向网)7. 2图的存储结构一、邻接矩阵1邻接矩阵的构建 将各个顶点排成一行和一列，形成矩阵。 假设行、列顶点之间存在一条边，那么对应元素记1，否那么，对应元素记 0。2. 邻接矩阵的特点无向图的邻接矩阵是对称的，有向图的邻接矩阵一般不对称。3用邻接矩阵表示加权图只要把1元素换成相应边的权值，0元素换成R即可。4. 邻接矩阵的用途便于查找每个顶点的度、入度、出度。无向图：每个顶点的度等于该顶点相应的行或列中1元素的个数。有向图：每个顶点的出度等于该顶点相应行中1元素的个数，入度等于相应列中1元素的个数。二、邻接链表树的孩子链表、图的邻接链表组织结构相同。

34、1邻接链表的构建 为每个顶点建立一个邻接链表，一个图有几个顶点，就有几个邻接链表。 顶点x的邻接链表是一个带头结点的单链表，用于存储与x相邻接的顶点序号。 将所有头结点组织成一维数组。2 邻接链表的用途便于求顶点的度、出度。无向图：每个顶点的度等于它的邻接链表中表结点的个数。有向图：每个顶点的出度等于它的邻接链表中表结点的个数。3. 如何求顶点的入度？构造一个逆邻接链表，即顶点x的逆邻接链表存储的是与 x的入边相关联的顶点序号。注：一个图的邻接矩阵是唯一的，但邻接表一般不唯一。7. 3图的遍历1树的遍历-先根遍历：根结点、各棵子树Y后根遍历：各棵子树、根结点匚层次遍历2. 图的遍历：适应于无向

35、图，也适应于有向图。深度优先搜索遍历：类似树的先根遍历。I广度优先搜索遍历：类似树的层次遍历3. 深度优先搜索遍历：首先访问出发点 Vi，然后任选一个 Vi的未访问过的邻接点 Vj,以Vj为新的出发点继续 进行深度优先搜索。深度优先搜索遍历、广度优先搜索遍历得到的顶点序列不唯一。7. 4图的应用一、最小生成树1. 什么叫生成树？从n个顶点的连通图 G中，取它的全部顶点和 n-1条边构成子图 G ,如果这些边刚好 将G的全部顶点连通但又不形成回路，那么称子图G是G的一棵生成树。注意：一个连通图可以有多棵生成树。 生成树是边数极少的连通子图。 连通分量：指极大连通子图。 根据图的宽度优先遍历或深度

36、优先遍历可构造生成树。2. 最小生成树生成树的权：各条边权值之和权值最小的生成树，称为最小生成树。 带权无向图才可构造最小生成树。求造价最低的通讯网问题，实际是求最小生成树问题。3构造最小生成树的算法：Prim 普里姆算法二、拓扑排序1拓扑序列在有向图中，假设不存在回路，那么所有顶点可排成一个线性序列，以便列出各顶点的前后关系，称此序列为拓扑序列。2 拓扑排序：实现有向图的一个拓扑序列的过程。任何一个有向无环图，其全部顶点可以排成一个拓扑序列，且其拓扑序列不唯一。假设图中入度为0的顶点和出度为0的顶点都是唯一的，那么其拓扑序列是唯一的。3构成有向图拓扑序列的过程 从图中选择一个入度为 0的顶点

37、，输出该顶点。 从图中删除该顶点及其相关联的所有边。 重复执行1, 2,直到找不到入度为 0的顶点。二、最短路径1 最短路径问题 带权有向图才存在最短路径问题。 图的路径长度：一条路径上各条边的权值之和。2. 求一个源点到其余各个顶点的最短路径：Dijkstra迪杰斯特拉算法从源点到其余各个顶点的最短路径中，先求最短的一条，再求次短的一条，以此顺序， 最后求最长的一条。3. Dijkstra算法描述 假设S为顶点集合，初值为源点 v0。 首先从v0出发的所有边中找出权值最小的边的终点参加到S中。 下一条最短路径是终点不在S中，中间只经过 S中的顶点且路径长度最短，找到后将终点参加到S中。 反复

38、执行3,直到所有顶点都参加到 S中。例：根据P115图7.17，求顶点V1到其余各顶点的最短路径。终占八、V2V3V4V5集合S第1次10OO30100V1 , V2第2次106030100V1 , V2, V4第3次10503090V1 , V2, V4 , V3第4次10503060V1 , V2, V4 ,V3, V5V1到各顶点的最短路径是：V1T V2: (V1, V2)V1t V4: (V1, V4)V1t V3: (V1, V4, V3)V1t V5: (V1, V4, V3, V5)第8章查找8. 1根本概念、各种数据的逻辑结构数据逻辑结构特点线性表线性结构数据兀素之间存在着一

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