-
数据结构考研必背算法
5
星
文档说明：
本文档是针对考研 专业课
《数据结构》
所编写的，
是对考研数据结构的核心算法进行总结，我们知道，不 管是
统考还是非统考，都会涉及至少
10
分的算法题（非统考至
少
2 5
分）
，
而这些题的答案都是在一些经典算法的思想上进
行改进的，本文总结 出必须要熟练掌握的算法，这些算法不
管是考研初期还是冲刺，都应该高度重视，只要对这些代码
进行熟练掌握，才能随机应变，希望对大家有所帮助；
线性表
1.
逆转顺序表中的所有元素
void Reverse(int A[ ],int n){
int i,t;
for(i=0;i
t = A[i];
A[i] = A[n-i-1];
a[n-i-1] = t;
}
}
自我总结：
2.
删除线性表中数据域为
X
的所有结
点；
void Del_X(Linklist &L,Elemtype X){
Linklist p,q = L;
p = L->next;
while (P!=NULL){
if(p->data == X){
q->next = p->next;
free(p);
p=q->next;
}else{
q = p;
p = p->next;
}
}
if(L->data == X){
q = L;
L = L->next;
free(q);
}
}
自我总结：
3.
删除不带头结点单链表
L
中 所有值为
X
的结点（递归）
void Del_X(Linklist &L,Elemtype X){
LNode *p;
if(L==NULL)
return
if(L->data == X){
P = L;
L = L->next;
free(p);
Del_X(L,X);
}else{
Del_X(L->next,X);
}
}
自我总结：
4.
删除带头结点单链表
L
中所有值为
X
的结点
void Del_X(Linklist &L,Elemtype X){
LNode *p = L->next,*pre = L, *q;
while(P!=NULL){
if(P->data == X){
q = p;
p=p->next;
pre->next = p;
free(q);
}else{
pre = p;
p=p->next;
}
}
} 注：
本算法是在无序单链表中删除满足某种
条件的所有结点；
如：
若是要 删除介于
max
和
min
之间的所有结点，
只需将
if语句改为
if(p->data>min&&p->data
5.
逆转线性表（不带头）
void reverse(Linklist &L){
Linklist p, q, r;
p = L;
q = NULL;
while(p!=NULL){
r = q;
q = p;
p = p->next;
q->next = r;
}
L = q;
}
带头结点：
Linklist reverse(Linklist L){
LNode *pre,*p=L->next,*r=p->next;
p->next = NULL;
while(r!=NULL){
pre = p;
p = r;
r = r->next;
p->next = pre;
}
L->next = p;
return L;
}
自我总结：
6.
复制线性链表
(
递归
)
Linklist copy(Linklist list1){
Linklist list2;
if(list1==NULL)
return NULL;
else{
list2
=
(Linklist)malloc(sizeof(LNode));
list2 ->data = list1->data;
list2
->
next
=
copy(list1->next);
return list2;
}
}
自我总结：
7.
将两个按值有序排列的非空线性表
合并为一个按值有序的线性表
Linklist Mergelist(Linklist L1,Linklist L2){
Linklist L3,p = L1,q = L2,r;
if(L1->data <= L2->data){
L3 = L1;
r = L1;
p = L1->next;
}else{
L3 = L2;
r = L2;
q = L2->next;
}
while(P!=NULL&&q!=NULL){
if(p->data <= q->data){
r->next = p;
r = p;
p = p->next;
}else{
r->next = q;
r = q;
q = q->next;
}
}
r->next=p!=NULL?p:q;
return L3;
}
自我总结：
8.
将两个按值递增线性表合并为一个
按值递减的线性表
void
MergeList(LinkList
&L1,LinkList
&L2){
LNode
*r,*p1=L1->next;*p2=L2->next;
L1->next = NULL;
while(p1&&p2){
if(p1->data <= p2->data){
r = p1->next;
p1->next = L1->next;
L1->next=p1;
p1 = r;
}else{
r = p2->next;
p2->next = L1->next;
L1->next = p2;
p2 = r;
}
if(p1){
p2 = p1;
}
while(p2){
r = p2->next;
p2->next = L1->next;
L1->next = p2;
p2 = r;
}
free(L2);
}
}
自我总结：
树
1.
先序遍历（递归）
void PreOrder(BiTree T){
if(T!=NULL){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
先序遍历（非递归）
void PreOrder(BiTree T){
InitStack(S);
BiTree p =T;
while(p!=NULL||!IsEmpty(S)){
while(p!=NULL){
visit(p);
Push(S,p);
p = p->rchild;
}
Pop(S,p);
p = p->rchild;
}
}
自我总结：
2.
中序遍历（递归）
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
Visit(T);
InOrder(T->rchild);
}
}
中序遍历（非递归）
void InOrder(BiTree T){
InitStack(S);
BiTree p = T;
while(p||
！
IsEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
}
else{
Pop(S,p);
Visit(p);
p=p->rchild;
}
}
}
自我总结：
3.
后序遍历（递归）
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T);
}
}
后序遍历（非递归）
void PostOrder(BiTree T){
InitStack(S);
BiTree p = T;
r = NULL;
while(p||!IsEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
}else{
GetTop(S,p);
if(p->rchild&&p->rchild!=r){
p = p->rchild;
Push(S,p);
p = p->lchild;
}else{
Pop(S,p);
Visit(p);
r = p;
p = NULL;
}
}
}
}
自我总结：
4.
层序遍历（自上而下，自左至右）
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:43，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/565154.html