数据结构总结2

秒速五厘米 2022-08-19 11:20 126阅读 0赞

**数据结构知识点总结整理**  
**0、常考基础必知必会**  
A. 排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法；  
B. 查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别？  
C. 链表和数组的区别，在什么情况下用链表什么情况下用数组？  
D. 栈和队列的区别？  
E. 多态，举例说明；overload 和 override 的区别？  
F. 字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。 strcpy  
和 memcpy？  
G. 继承、多继承？  
H. 面向对象有什么好处？  
I. 说说 static 的与众不同之处，如果一个变量被声明为 static，它会被分配在哪里？在什么时候  
分配空间等？  
J. 什么是虚函数、纯虚函数、虚的析构函数，用途？  
K. 内存泄漏及解决方法？  
网络部分：  
OSI 模型 7 层结构，TCP/IP 模型结构？  
B. TCP/UDP 区别？  
C. TCP 建立连接的步骤？  
D. 香农定理？  
**1、二叉树三种遍历的非递归算法（背诵版）**  
本贴给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，  
直接用于考研答题。  
**1.先序遍历非递归算法**  
\#define maxsize 100  
typedef struct  
\{  
Bitree Elem\[maxsize\];  
int top;  
\}SqStack;  
void PreOrderUnrec(Bitree t)  
\{  
SqStack s;  
StackInit(s);  
p=t;  
while (p!=null || !StackEmpty(s))  
\{  
while (p!=null) //遍历左子树  
\{  
visite(p->data);  
push(s,p);  
p=p->lchild;  
\}//endwhile  
if (!StackEmpty(s)) //通过下一次循环中的内嵌 while 实现右子树遍历  
\{  
p=pop(s);  
p=p->rchild;  
\}//endif  
\}//endwhile  
\}//PreOrderUnrec  
**2.中序遍历非递归算法**  
\#define maxsize 100  
typedef struct  
\{  
Bitree Elem\[maxsize\];  
int top;  
\}SqStack;  
void InOrderUnrec(Bitree t)  
\{  
SqStack s;  
StackInit(s);  
p=t;  
while (p!=null || !StackEmpty(s))  
\{  
while (p!=null) //遍历左子树  
\{  
push(s,p);  
p=p->lchild;  
\}//endwhile  
if (!StackEmpty(s))  
\{  
p=pop(s);  
visite(p->data); //访问根结点  
p=p->rchild; //通过下一次循环实现右子树遍历  
\}//endif  
\}//endwhile  
\}//InOrderUnrec  
**3.后序遍历非递归算法**  
\#define maxsize 100  
typedef enum\{L,R\} tagtype;  
typedef struct  
\{  
Bitree ptr;  
tagtype tag;  
\}stacknode;  
typedef struct  
\{  
stacknode Elem\[maxsize\];  
int top;  
\}SqStack;  
//后序遍历  
void PostOrderUnrec(Bitree t)  
\{  
SqStack s;  
stacknode x;  
StackInit(s);  
p=t;  
do  
\{  
while (p!=null) //遍历左子树  
\{  
x.ptr = p;  
x.tag = L; //标记为左子树  
push(s,x);  
p=p->lchild;  
\}  
while (!StackEmpty(s) &&s.Elem\[s.top\].tag==R)  
\{  
x = pop(s);  
p = x.ptr;  
visite(p->data); //tag 为 R，表示右子树访问完毕，故访问根结点  
\}  
if (!StackEmpty(s))  
\{  
s.Elem\[s.top\].tag =R; //遍历右子树  
p=s.Elem\[s.top\].ptr->rchild;  
\}  
\}while (!StackEmpty(s));  
\}//PostOrderUnrec  
**4.层次遍历算法**  
// 二叉树的数据结构  
structBinaryTree  
\{  
int value; // 不写模板了，暂时用整形代替节点的数据类型  
BinaryTree \*left;  
BinaryTree \*right;  
\};  
BinaryTree\*root; // 已知二叉树的根节点  
**//层次遍历**  
voidLevel( const BinaryTree \*root )  
\{  
Queue \*buf = new Queue(); // 定义一个空队列，假设此队列的节点数据类型也是整形  
的  
BinaryTree t; // 一个临时变量  
buf.push\_back(root); //令根节点入队  
while( buf.empty == false ) // 当队列不为空  
\{  
p = buf.front(); // 取出队列的第一个元素  
cout<<p->value<<' ';  
if( p->left != NULL ) // 若左子树不空，则令其入队  
\{  
q.push( p->left );  
\}  
if( p->right != NULL ) // 若右子树不空，则令其入队  
\{  
q.push( p->right );  
\}  
buf.pop(); // 遍历过的节点出队  
\}  
cout<<endl;  
\} **2**  
**、线性表**  
（1） 性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，  
双向循环链表。  
（2）单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等  
都是较为常见的考查方式。  
（3）单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好  
处。  
**3、栈与队列**  
你可以问一下自己是不是已经知道了以下几点：  
(1)栈、队列的定义及其相关数据结构的概念，包括：**顺序栈**，**链栈**，**共享栈**，**循环队列**，  
**链队**等。栈与队列存取数据（请注意包括：存和取两部分）的特点。  
(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法： **n!阶乘问题，**  
**fib 数列问题，hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的**  
**关系**等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。  
(3)栈的应用：**数值表达式的求解**，**括号的配对**等的原理，只作原理性了解，具体要求考查  
此为题目的算法设计题不多。  
(4)**循环队列**中判队空、队满条件，循环队列中入队与出队（循环队列在插入时也要判断其  
是否已满，删除时要判断其是否已空）算法。  
【循环队列的队空队满条件  
为了方便起见，约定：初始化建空队时，令  
front=rear=0,  
当队空时：front=rear，  
当队满时：front=rear 亦成立，  
因此只凭等式 front=rear 无法判断队空还是队满。  
有两种方法处理上述问题：  
（1）另设一个标志位以区别队列是空还是满。  
（2）少用一个元素空间，约定以“队列头指针 front 在队尾指针 rear 的下一个位置上”作  
为队列“满”状态的标志。  
**队空时： front=rear，**  
**队满时： (rear+1)%maxsize=front**】  
如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不  
看书，并不是可以不作题哦。  
  
循环队列的主要操作：  
(1)创建循环队列  
(2)初始化循环队列  
(3)判断循环队列是否为空  
(4)判断循环队列是否为满  
(5)入队、出队  
//空出头尾之间的一个元素不用  
\#include  
\#include  
\#define MAXSIZE 100  
typedef struct  
\{  
intelem\[MAXSIZE\];  
intfront, rear;  
\}Quque; //定义队头  
int initQue(Quque \*\*q) //初始化  
\{  
(\*q)->front=0;  
(\*q)->rear=0;  
\}  
int isFull(Quque \*q)  
\{  
if(q->front==(q->rear+1)%MAXSIZE)//判满(空出一个元素不用) 刘勉刚  
return 1;  
else  
return 0;  
\}  
int insertQue(Quque \*\*q,int elem)  
\{  
if(isFull(\*q))return -1;  
(\*q)->elem\[(\*q)->rear\]=elem;  
(\*q)->rear=((\*q)->rear+1)%MAXSIZE;//插入  
return0;  
\}  
int isEmpty(Quque \*q)  
\{  
if(q->front==q->rear)//判空  
return 1;  
else  
return 0;  
\}  
int deleteQue(Quque \*\* q,int \*pelem)  
\{  
if(isEmpty(\*q))  
return 0;  
\*pelem=(\*q)->elem\[(\*q)->front\];  
(\*q)->front=((\*q)->front +1)%MAXSIZE;  
return0;  
\}  
**4、串**  
串一章需要攻破的主要堡垒有：  
1. 串的基本概念，串与线性表的关系（