王道数据结构2020版本个⼈学习笔记（第⼀轮）持续补充
中……
⽬录
第三章栈和队列
3.1 栈
存储单元？
逻辑结构?
栈的基本操作？
C语⾔标识符？
上溢和下溢？
卡特兰数？
存储单元：⼀个存储单元可以存储⼀个字节（Byte=8bit），计算机的存储器容量是以字节为最⼩单位的，⽐如1KB的存储他有1024个存储单元，⼀个字母占⼀个字节，⼀个汉字占两个字节。⼀个字符等于两个字节。
逻辑结构：线性结构和⾮线性结构，指的是数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储⽆关，是独⽴于计算机的。
栈的基本操作：
InitStack(&S),StackEmpty(S),push,pop,GetTop(S,&x),ClearStack(&S)
C语⾔标识符：标识符的第⼀个字符必须是⼤⼩写英⽂字母或下划线
上溢和下溢：栈的插⼊和删除操作都是在栈顶进⾏的，只可能栈顶指针超出了最⼤范围，从⽽产⽣上溢，⽽不是下溢。
卡特兰数：对于n个不同元素进栈，出栈序列的个数为
3.2 队列
1.队列的顺序存储是怎么进⾏进队操作和出队操作的？
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1（注意先后顺序，题⽬中着重考察）
出队操作：对不空时，先取队头元素值，再将队头指针加1
注意：循环队列的出队操作和进队操作也是如此
2.⽤单链表实现队列时，队头在链表的什么位置？为啥⼦？
最理想的情况是⼀个循环单链表，带头结点，带尾指针。其中头结点头指针负责删除，尾指针负责增加，那么⼊队和出队的时间复杂度都为O（1），这时我们再来看队头指针就应该在链头了。
3.3 栈和队列的应⽤
1.页⾯替换算法是否⽤到队列？
是的，在FIFO，先进先出中⽤到队列
2.栈在表达式求值中，⼀般是⽤于存放操作符的。
3.执⾏函数的时候，局部变量⼀般采⽤什么结构进⾏存储？
栈结构，因为调⽤函数的时候，系统会为调⽤者构造⼀个由参数表和返回地址组成的活动记录，并将记录压⼊系统提供的栈中，若被调⽤函数有局部变量，也要压⼊栈中。
注意：在递归调⽤的过程中，系统为每⼀层的返回点，局部变量，传⼊实参等开辟了递归⼯作栈来进⾏数据存储。递归调⽤函数时，在系统栈中保存的函数信息需满⾜先进后出的特点。
3.4 特殊矩阵的压缩存储
1.三⾓矩阵A中的元素按⾏优先存放在⼀维数组B中，aij元素对应B中数组下标K应当是？
K=2（i-1）+j-1
若已知K，求i和j？
i=(k+1)/3+1,j=k-2i+3
2.什么是稀疏矩阵？拿来⼲嘛？
矩阵元素个数S远远⼤于⾮零个数t，S>>t的矩阵称为稀疏矩阵，⽤来存放⾮零元素，节省存储空间，稀疏矩阵压缩存储后便失去了随机存取特性。
3.什么是⼗字链表？（这部分引⽤了青岛⼤学的课程教学资料）
概念：⼗字链表是有向图的另⼀种链式存储结构。我们也可以把他理解为有向图的邻接表和逆邻接表的结合。有向图中的每⼀条弧对应⼗字链表的⼀个弧节点，每⼀个顶点对应⼀⼗字链表的⼀个顶点节点。
举个例⼦：
如这样的有向图，我们的⼗字链表应该怎么画勒
先来看看邻接表是怎么画的：
邻接表描述了每个点的出度节点，但是有个缺点是，要想知道⼀个点的⼊度节点的话，则需要我们遍历整个邻接表，所以我们引⼊了⼗字链表。
现在修改表头节点的指针域，分别是数据域，⼊度边，出度边
修改弧节点的指针域，分别是，弧尾，弧头（带箭头的那端指向的那个节点），弧头⼀样的下⼀条弧，弧尾⼀样的下⼀条弧
画⼗字链表的步骤是：先把所有的出度边画出来，然后再来画⼊度。
3.5 算法题遇到的⼀些问题
1.为什么在关于⼀些栈，队列，链表函数传递参数要⽤到&，⽽有些⼜不⽤？什么时候⽤？
取地址，我们就可以对这个变量进⾏操作，改变这个变量。不⽤&，就只能得到副本，可以看，但是不能动。⼀句话来说，当你要改变这个变量，就加取地址，不想改就不加。
2.数据结构⾥⾯的基本操作⼀般是可以直接⽤的，下⾯罗列⼀下：
（1）栈的基本操作：                                                （2）队列的基本操作
InitStack(&S)                                                                InitQueue(&Q)
StackEmpty(S)                                                              QueueEmpty(Q)
Push(&S,x)                                                                    EnQueue(&Q,x)
Pop(&S,&x)                                                                  DeQueue(&Q,&x)
GetTop(S,&x)                                                                GetHead(Q,&x)
ClearStack(&S)
3.！是取⾮运算，都快忘了。⽐如stackEmpty(S)是判空，假设是true，那么！stackEmpty(S)之后就是false了。
4.指针的问题：
算法题不建议⽤指针，⾸先王道书上的算法答案本⾝就不⼀定是可运⾏的代码，保险起见能⽤数组就⽤数组吧。
char *str=“abc”和char str[]="abc"有什么区别嗷？
前⾯只能看，不能改。后⾯可以改。
5.算法题更注重的是逻辑清晰，⽽不是代码⼀定要可运⾏。⼀定要把备注写清楚。因为题⽬问也只是问个逻辑，⽽不是编程⽐赛。
第4章树与⼆叉树
4.1 树的基本概念
1.树的定义是递归的，是⼀种递归的数据结构。树作为逻辑结构，同时也是⼀种分层结构。
2.树的路径长度怎么求？
是从树根到每个结点的路径长度的总和
3.常⽤于求解树结点与度之间关系的有：
总结点数=n0+n1+n2+……+nm
总分⽀点数=1n1+2n2+……+mnm
总结点数=总分⽀数+1
4.2 ⼆叉树的概念
题⽬中涉及到的知识点（主要是我个⼈不熟悉知识点）
1.⼆叉排序树的插⼊和删除？
插⼊：
若⼆叉排序树为空，则插⼊结点作为根节点插⼊到空树中
否则，继续在左右⼦树中查
树中已有，则不再插⼊
树中没有，则查⾄某个叶⼦节点的左⼦树或右⼦树为空为⽌，则插⼊。结点应为该叶⼦结点的左孩⼦或右孩⼦删除：
（1）被删除的结点是叶结点时，直接删除该结点
（2）被删除的结点只有左⼦树或者右⼦树，⽤其左⼦树或者右⼦树的结点替代他即可
举例：
（3）被删除的结点既有左⼦树⼜有右⼦树的时候
A.以其中序前驱值替换之（值替换），然后再删除该前驱结点。前驱是左⼦树中最⼤的结点
B.也可以⽤后继替换之，然后再删除该后继结点。后继是右⼦树中最⼩的结点。
选择AB的策略，主要是看树的⾼度，选择变换后树的⾼度最⼩的那⼀个。
2.树如何转化为⼆叉树？
将树转换成⼆叉树的步骤是：
（1）加线。就是在所有兄弟结点之间加⼀条连线；
（2）抹线。就是对树中的每个结点，只保留他与第⼀个孩⼦结点之间的连线，删除它与其它孩⼦结点之间的连线；（3）旋转。就是以树的根结点为轴⼼，将整棵树顺时针旋转⼀定⾓度，使之结构层次分明。
3.为什么在m叉树的情形下，结点i的第⼀个⼦⼥编号为j=(i-1)*m+2
4.3⼆叉树的遍历和线索⼆叉树
1.先序遍历的⾮递归算法？
思想：边遍历边打印，结点顺序是中左右
代码：
void PreOrder(BiTree T){
InitStack(S);BiTree p=T;//初始化栈，构造遍历指针P
while(p||!IsEmpty(S)){//当p不为空，S不为空时
if(p){//如果p不为空，就将该点输出，且拜访他的左⼦树
visit(p);什么是编程举个例子
push(S,p);
p=p->lchid;
}
else{//如果p的左⼦树遍历完了，就开始回访以前的结点中哪些右⼦树是还没输出的，依次输出
pop(S,p);
p=p->rchild;
}
}
}

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