数据结构知识点-个人笔记.docx
《数据结构知识点-个人笔记.docx》由会员分享，可在线阅读，更多相关《数据结构知识点-个人笔记.docx（37页珍藏版）》请在冰点文库上搜索。
《数据结构与算法》复习
第1部分：
1.概念：
数据结构，存储结构，逻辑结构
注：
磁盘文件管理系统是树状结构。
1.1基本概念
（1）数据：
指所有能够输入到计算机中并被计算机程序处理的符号的总称（图像声音都可以通过编码归于数据的范围），范围大
（2）数据项：
数据的不可分割的最小单元
（3）数据元素：
是数据的基本单位，有若干数据项组成，通常作为一个整体考虑
（4）数据对象：
性质相同的数据元素的集合，是数据的一个子集。
例子：
数据项
数据
元素
数据
对象
数据
表A
科目
分数
是否及格
数学
99
是
语文
89
是
表B
姓名
性别
身高
小花
女
100
小草
男
120
其中，A表为成绩表，B表为学生信息表，这两张表就是数据；单独的一张表就称为数据对象，即A和B表都是一个数据对象；每张表中的每一行就称为数据元素；姓名，性别，身高，科目，分数就称为数据项
1.2数据结构
定义：
相互之间存在一种或多种特定关系的数据元素的集合，这种关系包括三方面的内容，即数据逻辑结构，数据存储结构，数据的操作。
2.数据元素是组成数据的基本单位
3.算法，算法分析，算法特性，时间复杂度
3.1算法：
描述求解问题方法操作步骤的集合。
（不是所有的程序都是算法，要满足五个特性）
3.2时间复杂度
3.2.1定义：
在算法分析中，一般用算法中的语句的执行次数来度量算法的时间效率，时间效率也就是时间复杂度。
3.2.2计算方法：
对于问题规模为n的某个函数f（n），算法时间复杂度记为T（n），存在一个正常数c，使cf（n）>T（n）恒成立，则T（n）=Of（n），称Of（n）为时间复杂度。
时间复杂度的大O表示法：
保留最高次数项，令最高次数项的系数为1。
例如O（8）->O
（1），O（2n^3+2n^2）->O（n^3），O（n*log2n）
第2部分
1.线性表的概念，特点，存储结构
1.1．1线性表的概念：
线性表是最简单，最常见，最基本的一种线性结构（数据的逻辑结构的一种），元素之间为线性关系，即除了第一个和最后一个元素之外，所有的元素都有前驱和后继元素，同一个线性表中的数据类型相同。
当数据元素为0时，可以是空表，但是没有空图的说法。
1.1.2线性表的特点：
插入删除算法的时间复杂度为O（n），不适合多次插入或删除
1.2.1线性表的存储方式：
（1）顺序存储（又称顺序表）物理地址相连
a0
A1
A2
A3
A4
A5
A6
A7
A8
A9
（2）链式存储（又称链式表）
数据域
指针域
1.2.2链式表的特点：
可动态分配空间，插入删除算法的时间复杂度为O
（1）
单链表在特定节点插入和删除元素之前需要遍历链表，所以算法的时间复杂度为O（n），对于单链表的求表长，取元素，插入删除，释放掉几个操作的平均时间复杂度都是O（n），但是链表只需比较元素不用移动元素，所以时间效率上优于顺序表
2.顺序存储时插入、删除（移动元素的个数）
（1）定义顺序表的数据类型：
typedefstruct{
Intlist[maxsize];
Intsize}
（2）初始化voidlistinitial（sequence*L）{
L->size=0;}
（3）插入元素：
在i位置前插入一个新的元素，原顺序表中i位置之后的元素都要移动，并修改L->size+1；
Intinsert（sequence*L,inti,intx）{
intj;
if（L->size）>=mavsize{printf（“线性表已满”）}
elseif（i<0||i>L->size）{printf（“参数不合法”）}
else{
for（j=L->size;j>i;i++）//j指向顺序表最后一个元素size-1的后面
{L->list[j]=list[j-1];}//先逐个移动元素
L->list[i]=x;//再插入新的元素
L->size++;//使得线性表的总长度+1
}}
插入算法的时间效率：
平均移动元素的次数看做n/2（即移动一半元素），时间复杂度为O（n）
（4）删除元素:
删除i位置上的元素，将i后面的元素依次往前移，再令L->size-1
intinsert（sequence*L,inti,intx）{
intj;
if（L->size）<=0{printf（“线性表为空，无法删除”）}
elseif（i<0||i>L->size）{printf（“参数不合法”）}
else{
*x=L->list[i];
for（j=i+1;jsize-1;i++）//j指向要删除的元素的后一位
{L->list[j-1]=list[j];}//再将i后面的元素逐个前移
L->size--;
}}
删除算法的时间效率：
任意删除一个元素平均需要移动的次数看做n/2（即移动一半元素）时间复杂度为O（n）
（5）取元素*x=L->list[i];
3.链式存储的插入，删除的语句如何写，如何判空。
（1）定义链式表：
typedefstructNode
{
intdata;//这样定义就是定义了一个数组相当于intdata[]
structNode*next;
}Lnode,*LinkList;//Lnode等价于structnode定义了一个新的数据类型
//Lnode*L等价于LinkListL定义一个指向节点的指针变量
（2）插入元素
Lnode*q=（Lnode*）malloc（sizeof（Lnode））;//分配一个新的节点空间
q->data=ele;//是该结点的数据域赋值为ele
q->next=temp->next;//把插入的节点的指针域指向下一个节点的data域
temp->next=q;//然后让要插入的节点的前一个节点的指针域指向该插入节点的数据域，两者的顺序不能乱，否则的话就丢失了插入节点的后一个节点的指针，找不到他了
（3）删除元素
Lnode*del=temp->next;//单独设置一个指针指向被删除结点以防丢失
temp->next=temp->next->next;//删除del的方法就是更改del-1的指针域,让他指向del+1的数据域，一步成功
free（del）;//释放删除的节点del的空间
（4）单链表判空
1、不带头结点的单链表first为空的判定条件：
first=NULL；
2、带头结点的单链表first为空的判定条件：
first->=NULL；
4.顺序存储与链式存储的优缺点。
顺序表的存储优点是：
方法简单，容易实现；不用为表示节点间的逻辑关系而额外增加储存开销；具有按元素序号随机访问的特点
顺序表的存储缺点是：
对于n较大的顺序表，插入和删除元素需要移动的次数较大，效率低；需要预先分配足够大的空间，可能会导致大量闲置空间或者出现数据溢出；
链式表的优缺点与顺序表相反。
在选择存储方式时，若n较大，多进行插入删除操作，建议用链式存储，若按序号访问元素时，建议按顺序表存储（时间效率为O
（1））
例题：
第3部分
1.字符串的基本操作，什么叫模式匹配、
1.1串的定义：
字符串（也就是串）是0个或多个字符序列组成的有限序列。
l串就是数据元素为单个字符的特殊线性表。
l“qhjkdcbjsb”（隐含结束符\0）就是一个字符串，引号起界定作用，“”表示空串，串长为0
l“”空格串不是空串，串长为空格数
1.2串的存储类型：
顺序存储：
定长顺序存储结构、堆分配存储结构（动态分配连续内存）
链式存储
1.3串的模式匹配：
就是指定一个主串S和子串T，求T在S中第一次出现的位置。
（1）朴素模式匹配（BP算法）
核心思想：
主串S和子串T，S[1]和T[1]比较，S[2]与T[2]比较，直到S[n]与T[n]都是相等的为止，若S[i]与T[i]不相等，则子串向右移动一个（一个字符）继续比较
时间复杂度：
主串S长度为n，子串T长度为m，最多进行m（m-n+1）次，最坏的时间复杂度为O（mn）效率不高
（2）KMP算法
核心思想：
尽量利用已经得到的“部分匹配”的结果信息，不要让i回溯，加快子串右滑的速度，问题由子串决定而不是主串决定的
next数组：
是一个智能数组，指导子串下一步改用几号元素去匹配，next数组的next[1]和next[2]永远为0和1，其余next[n]看n位的前后缀的相同数目
实例：
（1）现有子串i=“ABABAAABA”,求其next数组
i
9
a
b
a
b
a
a
a
b
a
j
0
1
2
3
4
5
6
7
8
9
next
0
1
1
2
3
4
2
2
3
Next数组中对应i数组的值
前缀
后缀
Next[]的值
Next[j1]
0
0
0
Next[j2]
A
A
1
Next[j3]
A
B
1
Next[j4]
A
A
2
Next[j5]
AB
AB
3
Next[j6]
ABA
ABA
4
Next[j7]
A
A
2
Next[j8]
A
A
2
Next[j9]
AB
AB
3
（2）实例，不详细解释
主串是S=“bbsbbcdfbb”子串是“bbsbbs”,求next数组
T
6
b
b
s
b
b
s
J
0
1
2
3
4
5
6
next
0
1
2
1
2
3
主串是S=“sssssvsd”,子串是T=“ssssb”求next数组
S
5
s
s
s
s
B
l
0
1
2
3
4
5
Next
0
1
2
3
4
Next数组中对应i数组的值
前缀
后缀
Next[]的值
Next[j1]
0
0
0
Next[j2]
s
s
1
Next[j3]
s
s
2
Next[j4]
ss
ss
3
Next[j5]
sss
sss
4
KMP算法的时间复杂度：
O（m+n）
第4部分
1.栈的基本概念与特点
栈和队列也是线性表，只是操作受限制的线性表，他们线性表的区别在于线性表可以在在任意位置插入或删除元素，而栈只能在栈顶操作，队列只能在队尾操作。
1.1栈的特点：
后进先出（LIFO）可看做装电池，只能对栈顶进行操作
1.2存储方式：
顺序存储和链式存储
有n个元素的栈的顺序存储栈的链式存储
2.栈的两种存储结构的基本操作，如何入栈，出栈，判空？
操作
栈
存储方式类型
顺序栈
链式栈
定义数据类型
Typedefstruct{
Intstack[maxsize];
Inttop;
}sequencestack;
Typedefstructsnode{
Intdata;
Intsnode*next;
}singlelinkednode;
初始化
S->top=0;
取栈顶
*d=S.stack[S.top-1];
Singlelinkednode*p=head->next;
*d=p->data;
入栈
S->stack[S->top]=x;
S->top++;
移动top指针
Singlelinkednode*p；
p->data=x;
p->next=head->next；//先执行
head->next=p;//后执行
出栈
S->top--;
直接移动top指针，不用删除原栈顶
head->next=head->next->next;
free（p）;//需要释放出栈的元素
判空
if（S->top==0）
printf（“stackisempty”）;
If（head->next==null）
Printf（“stackisempty”）;
例题：
3.栈的应用举例（进制转换，递归，迷宫，表达式求值等）
栈的应用
内容
进制转换
算法原理：
辗转相除法算法公式：
N=（Ndiv2）*2+Nmod2
递归
迷宫
表达式求值
例1：
A+（B-C/D）*E（也称为中缀表达式）
前缀表达式为：
+A*-B/CDE即运算符在数值前面
后缀表达式为：
ABCD/-E*+运算符在数值后面
例2：
[（a+b）+c*（d+e）+f]*（g+h）
前缀表达式为：
*++ab*+cdeg+gh
后缀表达式为：
ab+cde+*+f+gh+*
例题：
4.队列的基本概念与特点
4.1队列的特点：
先进先出（FIFO）可看做排队买冰淇淋，只能对队头和队尾进行操作
4.2存储方式：
顺序存储和链式存储（注意front和rear的位置）
队列的顺序存储队列的链式存储
4.3假溢出问题
队列中因为多次出队入队而导致的存储空间不足的问题——解决办法：
循环队列
front+1==[front+1]%maxsize;
5.队列的两种存储结构的基本操作，队空，队满，环形队列，假溢出？
队列的操作
循环队列
链式队列
定义数据类型
Typedefstruct{
Intqueue[maxsize];
Intrear,front,count;
}seqrencequeue;
定义节点类型
Typedefstructqnode{
Intdata；
Structqnode*next;
}linkedqueuenode;
定义队列的结构体
Typedefstruct{
Linkedqueuenode*front;
Linkedqueuenode*front;
}Lqueue;
判空与判满
方法一：
使用count记录元素个数
队列已满count>0&&rear==front;
或count==maxsize;
队列已空count==0;
方法二：
加设标志位出队时置０入队时置１
队列已满：
tag==1&&rear==front
队列已空：
tag==0&&rear==front
方法三：
用掉一个存储单元（默认）
队列已满：
front=＝（rear+1）%MaxQueueSize
队列已空：
rear==front
If（Q.front==null）
Printf（“”queueisempty）;
链式队列不会满
入队（在队尾入队）
SeqrencequeueQ;
Q->queue[Q->rear]=x;
Q->rear=（Q->rear+1）%maxsize;
P=（linkedqueuenode*）malloc（sizeof（linkedqueuenode））
Q->rear=p;
p->next=null;
出队（在队头出队）
*d=Q->queue[Q->front]；
Q->front=[Q->front+1]%maxsize;
P=Q->front;
Q->front=Q->front->next;
Free（p;）
取队头元素
*d=Q->queue[Q->front];
*d=Q.front->data;
例题：
6.队列的应用举例（CPU对资源的管理，图的广度周游等，树的层次周游）
7.写算法：
从把一个队列中的元素存储到栈。
将一个栈中的元素放于队列中的算法（写算法要求会写程序，核心语句一定要会）（可以直接调用pushpop操作）
1.把队列中的元素存到栈中
（1）新建队列与栈并赋值
Q=createEmptyQueue_seq（）;//队列
S=createEmptyStack_seq（）;//栈
（2）取队头：
n=frontQueue_seq（Q）;
（3）将队头入栈顶：
push_seq（S,n）;
（4）出队：
popQueue_seq（Q）;
2.把栈中的元素存到队列中
（1）取出栈顶：
n=top_seq（S）;
（2）将栈顶入队尾：
pushQueue_seq（Q,n）;
（3）出栈:
popStack_seq（S）;
第5部分
1.二叉树的概念，性质1-6
1.1树：
即树形结构，是数据逻辑结构的一种。
（1）特点：
每个结点最多一个前驱结点，多个后继结点
（2）度的概念：
结点的度就是结点的孩子数，树的度就是所有结点的度的最大值。
（3）深度的概念：
根的层次为0，依次往下数。
（4）实例：
磁盘文件的目录结构。
（5）有序树与无序树：
即对子树是否加以区别。
1.2.1二叉树：
结点有限，区分左右子树的有序树。
二叉树不是树的特殊情况，树与二叉树的区别在于二叉树是有序的。
1.2.2二叉树的分类
1.2.3二叉树的性质
1.2.4二叉树的存储方式
（1）顺序存储：
采用一组连续的存储单元存放二叉树的节点，没有节点的地方需要^补上。
（2）链式存储：
用一条链表储存二叉树，一个节点有数据域和两个左右孩子的指针组成，若没有左/右孩子用^表示
lchild
data
rchild
1.3线索二叉树
1、定义：
增加节点标志域，利用这些指针把节点的前驱和后继的节点的信息连接起来，建立线索二叉树，主要是为了保留在各种遍历时得到的节点前驱和后继节点信息（即保留在各种遍历时产生的线性关系）。
Lefttag
lchild
data
rchild
righttag
2、实例：
中序周游的结果是：
CDBAEGHTF,有边相连就无需用虚线相连，无边相连则用虚线连起来
2.二叉树的周游，中，先—>后，画树
先序周游
中序周游
后序周游
顺序
根左右
左根右
左右根
实例
*+ab-cd
A+b*c-d
Ab+cd-*
递归运算
voidpostOrder（BNodep）{
if（p==NULL）return;
visit（p）;
postOrder（leftChild_btree（p））;
postOrder（rightChild_btree（p））;}
voidpostOrder（BNodep）{
if（p==NULL）return;
postOrder（leftChild_btree（p））;
visit（p）;
postOrder（rightChild_btree（p））;}
voidpostOrder（BNodep）{if（p==NULL）return;
postOrder（leftChild_btree（p））;
postOrder（rightChild_btree（p））;
visit（p）;}
3.二叉树的存储结构，写出链式存储结构
4.写算法：
二叉树的中序，先序，后序的递归算法，求叶子结点算法
求叶子节点的算法代码：
Voidcontleaf（BiTreeT,int*count）{
If（T）{If（（!
T->lchild）&&（!
T->rlichild））
*Count）++;//计算根节点
Countleaf（T-）lchild,count）;//递归调用求左子树的节点
Countleaf（T-）rchild,count）;//递归调用求右子树的节点
}}
5.哈夫曼算法及哈夫曼编码，WPL的计算
5.1哈夫曼树相关概念
（1）路径长度：
从A->B所经过的分支序列称路径，经过的分支个数称为路径长度
（2）带权路径长度：
若二叉树中的叶节点都带有权值，从根节点到叶节点的路径长度与相应的叶节点权值乘积之和称为该树的带权路径长度（WPL）
WPL=wi*pi在[1,n]求和
（3）哈夫曼树：
一组带权的叶节点可以构造多个二叉树，其中WPL最小的树称为哈夫曼树或最优二叉树。
（4）假设哈夫曼树叶子节点的个数为m，则哈夫曼树的分支节点为m-1，总共节点个数为2m-1
5.2哈夫曼树的构造：
原则是将权值大的结点靠近根。
根节点的值等于所有叶子节点的权值之和
例子：
用7，10，1,3,4,6,17构造一棵哈夫曼树
5.3哈夫曼树编码：
在哈夫曼树中把每个节点引向左孩子上的边标为0，引向右孩子的边标为1，再从上至下写出节点的编码
6.二叉树与树的转换
6.1树的表示方法
6.1.1父指针表示法
6.1.2孩子链表表示法
6.1.3孩子兄弟表示法
增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针，即左分支存放孩子节点，有分支存放兄弟节点
6.2树与二叉树的转换
6.2.1树转为二叉树
1、树中同一结点的兄弟相连；
2、保留结点的最左孩子连线，删除其它孩子连线；
3、调整位置；
1.2.3.
6.2.2二叉树转为树
即把所有右孩子节点变为兄弟节点
1.2.
6.2.3森林转为树
森林中各树先各自转为二叉树;依次连到前一个二叉树的右子树上
6.2.4树转为森林
沿着右孩子链搜索，把所有右孩子连线去掉；把得到的每棵二叉树转换为树
第6部分
1.图的概念、图的存储结构，由图写矩阵或由矩阵画图，矩阵的特点，时空复杂度。
1.1图的概念：
由顶点集合及顶点间的关系集合组成的一种数据结构。
图是一种非线性结构，图形结构是数据的逻辑结构的一种，节点使一对多的关系，不具有明显的分层关系。
图的基本术语
解释及注意事项
无向图
若n个顶点的无向图有n（n-1）/2条边,称为无向完全图
有向图
若n个顶点的有向图有n（n-1）条边,称为有向完全图
无向完全图
在无向图中任意两个顶点之间都有连线
有向完全图
在有向图中任意两个顶点之间都有连线
度
顶点的度=出度+入度
出度
顶点指出去的边
入度
指向顶点的边
权值
权值可以表示从前一
升级会员 