数据结构考研笔记整理（全）
一、第二章线性表
●考纲内容
●一、线性表的基本概念
●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑
结构，实现线性表的存储结构为顺序表或者链表
●二、线性表的实现
●1、顺序表
●定义(静态分配)
●#define MaxSize 50 \\  typedef struct{  \\  ElemType data[MaxSize];\\  int
length;\\ }SqList;
●定义(动态分配)
●#define MaxSize 50\\ typedef strcut{\\  EleType *data;  //指示动态非配
数组的指针\\  int MaxSize,length;\\ }SqList;
●c的动态分配语句为
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
●c++动态分配语句为L.data=new ElemType[InitSize];
●插入操作
●删除操作
●按值寻
●2、链表
●单链表
●单链表的定义
●
●头插法建立单链表
●
●尾插法建立单链表
●
●按序号查getElem(LinkList L,int i)和按值查locateElem(LinkList
L,ElemType e)
●插入结点（后插）
●p=getElem(L,i-1);  //查插入位置的前驱结点\\ s.;\\
<=s;
●将前插操作转化为后插操作，即先将s插入的p的后面然后调换s
和p的数据域
●s.;\\ p.;\\ temp=p.data;\\ p.data=s.data;\\
s.data=temp;
●删除结点
●p.getElem(L,i-1);\\ ;\\ p.;\\ free(q);
●双链表（结点中有prior指针和next指针）
●循环链表
●静态链表
●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一
个元素的数组下标二叉树的基本性质
●三、线性表的应用
●使用的时候如何选择链表还是顺序表？
●表长难以估计，经常需要增加、删除操作——链表；表长可以估计，查询
比较多——顺序表
●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法
和查算法的应用
●小知识点（选择题）
二、第三章栈，队列和数组
●考纲内容
●一、栈和队列的基本概念
●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表
●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表
●二、栈和队列的顺序存储结构
●栈的顺序存储
●
●队列的顺序存储
●进队：队不满时，送值到队尾元素，再将队尾指针加一
●出队：队不空时，取队头元素值，再将队头指针加一
●判断队空：Q.front==Q.rear==0;
●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的
后一个位置，也就是即将要插入的位置）
●初始：Q.front==Q.rear
●队满：(Q.rear+1)%MaxSize=Q.front
●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize
●入队，队尾指针进ar=(Q.rear+1)%MaxSize
●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
●三、栈和队列的链式存储结构
●栈的链式存储
●
●队列的链式存储
●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的
最后一个结点，与顺序存储不同，通常带有头结点
●四、多维数组的存储
●行优先：00，01，02，10，11，12
●列优先：00，10，01，11，02，12
●五、特殊矩阵的压缩存储
●对称矩阵
●三角矩阵
●三对角矩阵（带状矩阵）
●稀疏矩阵
●将非零元素及其相应的行和列构成一个三元组存储
●十字链表法
●六、栈、队列、数组的应用
●栈在括号匹配中的应用
●栈在递归中的应用
●函数在递归调用过程中的特点：最后被调用的函数最先执行结束
●队列在层次遍历中的应用
●二叉树的层次遍历
●1跟结点入队
●2若队空，则结束遍历，否则重复3操作
●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若
有右孩子，则右孩子入队
●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征
●小知识点(选择题)
●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)
●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享
空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响
●双端队列是指允许两端都可以进行入队和出队操作的队列
●输出受限的双端队列：允许两端插入，只允许一端删除
●输入受限的双端队列：允许两端删除，只允许一端插入
三、第四章串
●考纲内容
●字符串模式匹配
●暴力算法
●注意指针回退时的操作是i=i-j+2;j=j+1;
●kmp算法
●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-
1个字符组成的串
●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从
1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则
next数组不需要加一
●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则
nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];
●小知识点
●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字
符；2串的操作对象通常是子串而不是某一个字符
四、第五章树与二叉树
●考纲内容
●一、树的基本概念
●定义
●树是一种递归的数据结构，是一种逻辑结构
●树的性质
●结点数为n，则边的数量为n-1
●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该
结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，
对应一个度，只有根结点上面无边，故结点树=度数之和+1）
●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最
多有m^{i-1}个结点）
●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m
个孩子，则由等比数列的求和公式可以推导出该式子）
●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度
为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n
\leq (m^h-1)/(m-1)）
●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1
个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结
点的度小于等于m，而度为m的树一定有一个结点的度数为m）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。