数据结构Word下载.docx
《数据结构Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构Word下载.docx（19页珍藏版）》请在冰点文库上搜索。
特点：
可以随机访问
•插入:
若有n个元素的顺序表，在第i个元素之前插入，也即插入元素作为第i个元素
i=n+1时移动元素次数为0；
i=1时移动元素次数为n；
一般情况n-i+1；
等概率情况下平均n/2.
•删除
i=1时移动元素次数为n-1；
i=n时移动元素次数为0；
一般情况移动次数n-i；
等概率平均情况（n+1）/2.
•插入、删除的基本操作为元素移动
时间复杂度为O（n）
3.线性表的链式存储结构（存储空间可以连续也可以不连续）
•链表（结点、头指针、尾结点、带头结点的链表）
特点：
不能随机访问
4.单向链表
•静态法（说明变量）建立链表
•尾插法建立链表（头指针、q始终指向尾结点、p生成新结点）
•头插法建立链表（头指针、q始终指向头结点、p生成新结点）
•插入（在第i个结点前插入新结点，p生成新结点，q指向第
i-1个结点…）
•删除（删除第i个结点，q指向第i个结点的前驱（第i-1个结
点），p指向第i个结点）
•四种操作都必须知道操作位置结点的前驱结点的指针
第3章栈和队列
1.栈
•栈是运算受限的线性表
插入、删除限定在表的尾部进行（栈顶）
•栈顶、栈底、空栈、栈顶元素
•顺序栈（连续的存储空间）
用结构体变量实现的顺序栈
结构体变量
规定：
栈底为数组下标为0的一端
溢出：
栈顶指针（下标）为-1时为空，栈顶为MaxSize-1时
栈满
上溢（满）、下溢（空）
•链栈（用链式存储结构实现的栈）
•可以用不带头结点的单向链表实现链栈
•存储结构structnode*top；
•基本操作：
初始化、判栈空、进栈、出栈（与不带头
链栈只有空和非空两种状态，没有栈满的情况
2.队列
•队列是运算受限的线性表
允许在队尾插入，在队头删除
•队头、队尾、空队列
顺序队列（顺序存储的队列）
用结构体变量实现的顺序队列
结构体变量数组（队元素）
整型变量1:
front（队头指针）
整型变量2:
rear（队尾指针）
队列初始化：
队头指针、队尾指针均置为0
队头指针front指向队头元素
队尾指针rear指向队尾元素的下一个位置
队列为空时front=rear
队列满时rear=MaxSize
上溢：
队列已满进行入队操作
假上溢：
队列未满，但尾指针已超越存储空间上界
下溢：
队列已空，要进行出队操作
操作：
初始化、判队空、入队、出队、取队头元素
3.循环队列
•为解决“假上溢”问题
•设想队列为一个首尾相接的圆环
•为了区别循环队列的队满和队空规定少用一个存储空间
尾指针加1等于头指针时为队满
即：
（rear+1）%MaxSize=front
当front=rear时为队空
第4章树
1.树的基本术语
叶结点（终端结点）、分支结点（非叶结点）
结点的度（引出结点的个数）
孩子结点、双亲结点、兄弟结点
结点的层数、树的深度
3.二叉树的基本概念和性质
性质1
二叉树上终端结点数等于双分支结点数加1，（哈夫曼树中除叶结点外全是双分支结点）
要求：
在结点总数、叶结点数、双分支结点数、单分支结点数之间能进行相关计算
•性质2
二叉树上第i层至多有2i-1个结点
•性质3
深度为h的二叉树最多有2h-1个结点
1+2+4+8=24-1=15
性质4
二叉树中顺序编号为i的结点
左孩子：
2i
右孩子：
2i+1
术语：
满二叉树完全二叉树
•要求：
完全二叉树总结点数、层数、最高层的结点数之间的计算
4.二叉树的存储结构
•顺序存储
树的序号与一维数组的下标对应
•链接存储结构
5.二叉树的遍历
•递归定义：
二叉树或者是一棵空树，或者是一棵由一个根结点和互不相交的分别称为根的左子树和右子树所组成的非空树（左、右子树可以为空树），左、右子树也同样是一棵二叉树
•遍历：
按照一定次序访问每个结点一次且仅一次
•遍历规则：
（先左后右，以访问根的次序区分遍历方法）
先序：
根、左子树、右子树
中序：
左子树、根、右子树
后序：
左子树、右子树、根
•递归算法程序（p55）
•手工遍历
例
后序遍历：
5,4,2,6,9,8,7,3,1
例
中序遍历：
CBDAEGF
先序遍历：
ABCDEFG
后序遍历：
CDBGFEA
•二叉树的非递归遍历算法（了解）
•二叉树的其它运算（了解）
6.哈夫曼树
•结点的带权路径长度（路径长×
结点的权）
•树的带权路径长度
WPL=WiLi
所有叶结点的带权路径长度之和：
4x3＋2x2+1x1=…
•哈夫曼树（最优树）
n个带权叶结点的所有二叉树中，WPL最小的树
性质：
除叶结点外其余结点全为双分支结点（要求掌握哈夫曼树总结点数、叶结点数、分支结点数之间的计算）
构造Huffman树和Huffman编码
例：
权重：
a,b,c,d,e
3,5,6,7,9
a:
000
b:
001
c:
10
d:
11
e:
01
7.由遍历序列确定二叉树
•先序中序（先序确定根结点，中序划分左右子树）
•后序中序（后序确定根结点，中序划分左右子树）
例先序遍历序列为stuwv，中序遍历序列为uwtvs
由先序：
s是根，由中序：
左子树uwtv，右子树为空
t是左子树根，由中序：
左子树uw，右子树v
u是左子树根，由中序：
左子树空，右子树w
efcdb，中序ecfbd
由后序：
b为根由中序：
左子树ecf，右子树d
c为根由中序：
左子树e，右子树f
前序：
bcefd
先序遍历：
bfdec，中序fbedc
左子树f，右子树edc
d为根由中序：
左子树e，右子树c
后序：
fecdb
第5章图
1.图的基本概念
•顶点的度
无向图的度：
以该顶点为一个端点的边数
•图的逻辑结构
多对多的关系（例：
交通图）
•有关术语
权：
边权（数值）
网：
带权图（边上带权）
树权：
（图中所有边上的权值总和）
•其它术语（略）
2.图的基本定理
•图的边数等于所有顶点度数（之和）的一半（隐含度数为偶数）
3.图的存储结构
•邻接矩阵
•邻接表
4.图的遍历
从某一初始点出发，按一定搜索方法访问所有顶点一次且仅一次
•深度优先搜索遍历：
能走则走，不能走退回一步再走，结果不唯一
A.a,b,e,c,d,f（错）
B.a,e,d,f,c,b（对）
广度优先搜索遍历（类似于树的层次遍历）
访问初始点，及其所有邻接点（次序可任意）
再按上述访问结点的次序进行广度搜索遍历（按序层层搜索，地毯式）
•A.a,b,c,e,d,f（错）
•B.a,b,c,e,f,d（对）
5.图的生成树和最小生成树
•树是连通而不含回路的图，n个顶点的树必含有n-1条边
•对一个连通图G，取全部顶点和一部分边组成一个子图G’，若G’是一棵树，称它为G的一棵生成树
•连通图一定存在生成树，同一个连通图可以有不同的生成树
•连通网（连通带权图）可以有不同的生成树
•对于一个带权连通图，其中具有最小权的生成树称为最小生成树
6.图的相关算法（了解）
•求最小生成树
•最短路径（从一个顶点到其余各顶点的最短路径）
•拓扑排序
第6章排序
1.基本概念
•排序
•稳定的排序方法
关键字相等的记录经排序后保持它们原来的前后关系
•不稳定的排序方法
关键字相等的记录经排序后可能改变它们原来的前后关系
2.插入排序
•直接插入排序：
每一趟从无序子表中将一个待排的记
•录按其关键字大小放到已排好序的子序列的适当位置
例
47,83,41,53,68
47
47,83
414783
41475383
4147536883
65，49，116，43，26，92，80，55，100用直接插入排序，当要把第7个元素80插入到已排好序的子表时，需进行多少次元素的比较
2643496592116||80
3次
•折半插入排序
利用折半查找寻找插入位置
3.交换排序
•冒泡排序
n个元素，从左到右两两比较，必要时交换
共需要n-1趟冒泡
第i趟要进行n-i次元素间比较
若某一趟冒泡中没有进行元素的交换（0次交换），则序列已排好序
•快速排序
选取划分元素，i，j分别指向序列起、止位置，
从后向前（j）扫描找到小于分割元素的元素，
占位（i）,i=i+1;
从前向后（i）扫描找到大于分割元素的元素，
占位（j）,j=j-1;
i等于j时完成一趟快速排序
↓↓
例55,50,75,53,45,105
55
↓↓
55，50，75，53，45，105
↓↓
45，50，75，53，45，105从后向前
45，50，75，53，75，105从前向后
↓↓
45，50，53，53，75，105从后向前
45，50，53，55，75，105
（55归位）
4.选择排序
•直接选择排序
第1趟：
让a[1]与a[2]…a[n]比较找到最小元素的下标
k1，让a[1]与a[k1]交换
第2趟：
让a[2]与a[3]…a[n]比较找到最小元素的下标
k2，
……
共进行n-1趟选择
•堆排序
•堆和特殊性质完全二叉树的对应
堆{14,40,30,50,80,65,50,100}
•小根堆：
任意非叶结点的值小于等于左、右孩子结点的值
•大根堆：
任意非叶结点的值大于等于左、右孩子结点的值
•筛选法建堆
例：
序列{47,87,72,107,21,37,62,57}
（初始树）（堆）
•堆排序：
用筛选法建n个元素的堆，交换堆顶元素和最后一个元素，再用筛选法建n-1个元素的堆…
第7章查找
•名词
查找表：
同一类型记录的集合
关键字：
记录中的某个数据项（的值）.可以用以确
定识别记录
主关键字：
记录中的某个数据项（的值）.可以用以
确定唯一的一个记录
次关键字：
确定多个记录
•平均查找长度
查找的基本操作是“比较”
ASL=CiPi:
Ci是查找到第i个记录的比较次数
Pi是查找第i个记录的概率
2.线性表的查找
•顺序查找：
等概率条件下
ASL=1/ni=（n+1）/2
•改进的顺序查找（顺序表末尾设一个监视哨），查找不成功比较n+1次
•折半查找和折半查找对应的判定树
查找表（顺序存储）中记录相应的关键字值必须有序（升序或降序）
查找表6,14,20,21,38,56,68,78,85,85,100
序号012345678910
（1）画出折半查找的判定树
（2）查找到68要进行多少次元素间的比较（3次）
（3）要查32，经多少次查找确定查不到（4次）
（4）等概率条件下，平均查找长度
ASL=（1X1+2X2+3X4+4X4）/11=…
判定树：
3.分块查找
•查找表分块：
块间有序、每块无序
•索引表：
索引表中一个记录对应一块
索引表记录：
块内最大关键字
块中第一个记录的位置（地址指针）
查找步骤：
折半查找确定块，块内顺序查找
4.树表的查找
•二叉排序树
三要素：
（a）根结点大于左子树上所有结点的值（或等于）
（b）根结点小于右子树上所有结点的值（或等于）
（c）左、右子树也分别是一棵二叉排序树
二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值（x）
•二叉排序树的插入操作（也可用来构造二叉排序树）
（1）给定序列{9,18,6,10,22,11,8,20,7},依次取序
列中的数构造一棵二叉排序树
（2）给出中序遍历的序列
6,7,8,9,10,11,18,20,22
•对二叉排序树进行中序遍历所得的序列是有序序列
（由小到大）
•二叉排序树的删除操作（分4种情况，了解）
•删除原则是删除后使得到的树是二叉排序树
5.哈希表及其查找
•相关名词
哈希函数：
记录的关键字存储地址
哈希表：
存放查找表中记录的序列，存储位置是以关键字为自变量由哈希函数计算所得到的数值
哈希查找（散列查找）原理：
在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系
•哈希函数构造法、处理冲突的方法（掌握）
升级会员 