第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
数据结构考研必背算法5星.pdf
数据结构考研必背算法 5 星
文档说明：本文档是针对考研专业课《数据结构》所编写的，
是对考研数据结构的核心算法进行总结，我们知道，不管是
统考还是非统考，都会涉及至少 10 分的算法题（非统考至
少 25 分），而这些题的答案都是在一些经典算法的思想上进
行改进的，本文总结出必须要熟练掌握的算法，这些算法不
管是考研初期还是冲刺，都应该高度重视，只要对这些代码
进行熟练掌握，才能随机应变，希望对大家有所帮助；
线性表
1.逆转顺序表中的所有元素
t = A[i];
A[i] = A[n-i-1];
a[n-i-1] = t;
int i,t;
for(i=0;inext;
while (P!=NULL){
}
if(L->data == X){
}
if(p->data == X){
}else{
}
q->next = p->next;
free(p);
p=q->next;
2. 删除线性表中数据域为 X 的所有结
q = p;
p = p->next;
q = L;
L = L->next;
free(q);
3.删除不带头结点单链表 L 中所有值为
P = L;
L = L->next;
free(p);
Del_X(L,X);
LNode *p;
if(L==NULL)
return ;
if(L->data == X){
}else{
}
X 的结点（递归）
void Del_X(Linklist &L,Elemtype X){
}
自我总结：
Del_X(L->next,X);
4.删除带头结点单链表 L 中所有值为 X
q = p;
p=p->next;
pre->next = p;
free(q);
if(P->data == X){
}else{
}
LNode *p = L->next,*pre = L, *q;
while(P!=NULL){
}
的结点
void Del_X(Linklist &L,Elemtype X){
}
注：本算法是在无序单链表中删除满足某种
条件的所有结点；如：若是要删除介于 max
和 min 之间的所有结点，只需将 if 语句改为
if(p->data>min&&p->datanext;
5.逆转线性表（不带头）
r = q;
q = p;
p = p->next;
q->next = r;
Linklist p, q, r;
p = L;
q = NULL;
while(p!=NULL){
}
L = q;
void reverse(Linklist &L){
}
带头结点：
Linklist reverse(Linklist L){
}
自我总结：
LNode *pre,*p=L->next,*r=p->next;
p->next = NULL;
while(r!=NULL){
}
L->next = p;
return L;
pre = p;
p = r;
r = r->next;
p->next = pre;
return NULL;
Linklist list2;
if(list1==NULL)
else{
6. 复制线性链表(递归)
Linklist copy(Linklist list1){
(Linklist)malloc(sizeof(LNode));
copy(list1->next);
return list2;
list2
list2 ->data = list1->data;
list2
next
->
=
=
7. 将两个按值有序排列的非空线性表
}
L3 = L1;
r = L1;
p = L1->next;
L3 = L2;
r = L2;
q = L2->next;
}
自我总结：
合并为一个按值有序的线性表
Linklist Mergelist(Linklist L1,Linklist L2){
}
自我总结：
Linklist L3,p = L1,q = L2,r;
if(L1->data <= L2->data){
}else{
}
while(P!=NULL&&q!=NULL){
if(p->data <= q->data){
}else{
}
}
r->next=p!=NULL?p:q;
return L3;
r->next = q;
r = q;
q = q->next;
r->next = p;
r = p;
p = p->next;
8. 将两个按值递增线性表合并为一个
LNode
p2 = p1;
r = p2->next;
p2->next = L1->next;
L1->next = p2;
p2 = r;
r = p1->next;
p1->next = L1->next;
L1->next=p1;
p1 = r;
L1->next = NULL;
while(p1&&p2){
}
if(p1->data <= p2->data){
}else{
}
if(p1){
}
while(p2){
}
free(L2);
按值递减的线性表
void MergeList(LinkList &L1,LinkList &L2){
*r,*p1=L1->next;*p2=L2->next;
}
自我总结：
r = p2->next;
p2->next = L1->next;
L1->next = p2;
p2 = r;
树
1. 先序遍历（递归）
void PreOrder(BiTree T){
}
if(T!=NULL){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
visit(p);
Push(S,p);
p = p->rchild;
while(p!=NULL){
}
Pop(S,p);
p = p->rchild;
InitStack(S);
BiTree p =T;
while(p!=NULL||!IsEmpty(S)){
}
先序遍历（非递归）
void PreOrder(BiTree T){
}
自我总结：
2. 中序遍历（递归）
InOrder(T->lchild);
Visit(T);
InOrder(T->rchild);
if(T!=NULL){
}
void InOrder(BiTree T){
}
中序遍历（非递归）
void InOrder(BiTree T){
InitStack(S);
BiTree p = T;
while(p||！IsEmpty(S)){
if(p){
Push(S,p);
p = p->lchild;
Pop(S,p);
Visit(p);
p=p->rchild;
}
else{
}
}
}
自我总结：
3. 后序遍历（递归）
void PostOrder(BiTree T){
}
if(T!=NULL){
}
PostOrder(T->lchild);
PostOrder(T->rchild);
Visit(T);
Push(S,p);
p = p->lchild;
if(p){
}else{
后序遍历（非递归）
void PostOrder(BiTree T){
InitStack(S);
BiTree p = T;
r = NULL;
while(p||!IsEmpty(S)){
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;
GetTop(S,p);
}
}
}
}
自我总结：
4. 层序遍历（自上而下，自左至右）
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,p);
Visit(p);
if(p->lchild!=NULL)
if(p->rchild!=NULL)
}
void LevelOrder(BiTree T){
}
自我总结：
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
5. 层序遍历（自下而上，自右至左）
InitStack(S);
InitQueue(Q);
EnQueue(Q,bt);
while(IsEmpty(Q)==false){
void InvertLevel(BiTree bt){
Stack S;Queue Q;
if(bt!=NULL){
EnQueue(Q,p->lchild);
if(p->rchild)
EnQueue(Q,p->rchild);
DeQueue(Q,p);
Push(S,p);
if(p->lchild)
}
while(IsEmpty(S)==false){
}
Pop(S,p);
visit(p->data);
}
}
自我总结：
6. 求二叉树深度（高度）（递归）
return rdep+1;
return ldep+1；
if(T==NULL)
return 0;
Ldep = Btdepth(T->lchild);
rdep = Btdepth(T->rchild);
if(ldep>rdep)
else
int Btdepth(BiTree T){
}
注：求某一层结点个数，每一层结点个数，
树的最大宽度等，都采用此思想
自我总结：
求二叉树深度（非递归）
int Btdepth(BiTree T){
if(!T)
int front = -1,rear = -1;
int last = 0,level = 0;
BiTree Q[MaxSize];
Q[++rear]=T；
BiTree p;
while(frontlchild)
if(p->rchild)
Q[++rear]=p->rchild;
Q[++rear]=p->lchild;
return 0;
if(front==last){
}
level++;
last=rear;
}
return level;
}
自我总结：
7. 交换二叉树中所有结点的左右子树
位置（递归）
void swap(BiTree b){
}
if(b){
}
swap(b->lchild);
swap(b->rchild);
temp=b->lchild;
b->lchild=b->rchild;
b->rchild=temp;
非递归
BiTree QUEUE[MAX_QUEUE] ，
#define MAX_QUEUE 50
void swap(BiTree T){
temp,p=T;
int front,rear;
if(T!=NULL){
QUEUE[++rear]=p->lchild;
QUEUE[++rear]=p->rchild;
QUEUE[0]=T;
front=-1;
rear=0;
while(frontlchild;
p->lchild=p->rchild;
p->rchild=temp;
if(p->lchild!=NULL)
if(p->rchild!=NULL)
}
}
}
自我总结：
8. 删除二叉树中以某个结点为根结点
的子树
EnQueue(Q,p->rchild);
}
}
}
自我总结：
if(bt){
}
DeleteXTree(bt);
exit(0);
DeleteXTree(bt->lchild);
DeleteXTree(bt->rchild);
free(bt);
if(bt->data==X){
}
initQueue(Q);
EnQueue(Q,bt);
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p->lchild)
void DeleteXTree(BiTree bt){
}
void Search(BiTree bt,ElemType X){
if(bt){
if(p->lchild->data==X){
DeleteXTree(p->lchild);
EnQueue(Q,p->lchild);
if(p->rchild)
if(p->rchild->data==X){
DeleteXTree(p->rchild);
}else
}else
p->lchild=NULL;
p->rchild=NULL;
9. 建立二叉树（从键盘输入数据，先
序遍历递归算法）
char ch;
BiTree T;
scanf("%c",&ch);
if(ch==' ')
else{
return NULL;
BiTree Create(){
}
自我总结：
T=(BiTree)malloc(sizeof(BTNode));
}
T->data=ch;
T->lchild=Create();
T->rchild=Create();
return T;
10. 建立二叉树（从数组获取数据）
BiTree p;
if(i>n) return NULL;
else{
Bitree CreateBT(int A[],int i,int n){
}
p=(BiTree)malloc(sizeof(BTNode));
}
p->data=A[i];
p->lchild=CreateBT(A,2*i,n);
p->rchild=CreateBT(A,2*i+1,n);
return p;
if(A[i]!=0){
PT[i]=NULL;
PT[i]->data=A[i];
}else{
}
int i;
BiTree *PT;
for(i=1;i<=n;i++){
法二：
BiTree CreateBT(int A[],int n){
PT[i]=(BiTree)malloc(sezeof(BTNode));
}
自我总结：
}
for(i=1;i<=n;i++){
}
if(PT[i]!=NULL){
}
PT[i]->lchild=PT[2*i];
PT[i]->rchild=PT[2*i+1];
11. 求结点所在的层次：
BiTree STACK1[MAX_STACK],P=T;
int STACK2[MAX_STACK],flag,top=-
STACK1[++top]=p;
STACK2[top]=0;
p=p->lchild;
#define MAX_STACK 50
int LayerNode(BiTree T,int item){
1;
while(p!=NULL||top!=-1){
while(p!=NULL){
}
p=STACK1[top];
flag=STACK2[top--];
if(flag==0){
}else{
STACK1[++top]=p;
STACK2[top]=1;
p=p->rchild;
if(p->data==item)
return top+2;
}
}
}
自我总结：
p=NULL;
查找
ST,ElemType
return i;
Search_Seq(SSTable
ElemType *elem;
int TableLen;
ST.elem[0]=key;
for(i=ST.TableLen;ST.elem[i]!=key;--
1. 顺序查找：
typedef struct{
}SSTable;
int
key){
i);
}
递归：
int SeqSearch(int A[],int n,int key,int i){
}
调用:Pos=SeqSearch(A,n,key,0);
总结：
2. 折半查找：
int Binary_Search(SeqList
key){
int low = 0;high=L.TableLen-1,mid;
while(low<=high){
if(i>=n) return -1;
if(A[i]==key) return i;
else return SeqSearch(A,n,key,i+1);
mid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
L,ElemType
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
