数据结构考研必背算法5星

1、数据结构考研必背算法5星文档说明：本文档是针对考研专业课数据结构所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助；线性表1.逆转顺序表中的所有元素void Reverse(int A ,int n)int i,t;for(i=0;i<n/2;i+)t = Ai;Ai = An-i-1;an-i-1 = t; 自我总结：2.

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;elseq = p;p = p->next;if(L->data = X)q = L;L = L->next;free(q);自我总结：3.删除不带头结点单链表L中所有值为X的结点（递归）void Del_X(Linklist &L,Elem

3、type X)LNode *p;if(L=NULL)return ;if(L->data = X)P = L;L = L->next;free(p);Del_X(L,X);elseDel_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);elsepre =

4、 p;p=p->next;注：本算法是在无序单链表中删除满足某种条件的所有结点；如：若是要删除介于max和min之间的所有结点，只需将if语句改为if(p->data>min&&p->data<max)自我总结：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)LNo

5、de *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;elselist2 = (Linklist)malloc(sizeof(LNode);list2 ->data = list1->dat

6、a;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;elseL3 = L2;r = L2;q = L2->next;while(P!=NULL&&q!=NULL)if(p->

7、;data <= q->data)r->next = p;r = p;p = p->next;elser->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-&

8、gt;data <= p2->data)r = p1->next;p1->next = L1->next;L1->next=p1;p1 = r;elser = 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

9、(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

10、);InOrder(T->rchild);中序遍历（非递归）void InOrder(BiTree T)InitStack(S);BiTree p = T;while(p|！IsEmpty(S)if(p)Push(S,p);p = p->lchild;elsePop(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

11、(BiTree T)InitStack(S);BiTree p = T;r = NULL;while(p|!IsEmpty(S)if(p)Push(S,p);p = p->lchild;elseGetTop(S,p);if(p->rchild&&p->rchild!=r)p = p->rchild;Push(S,p);p = p->lchild;elsePop(S,p);Visit(p);r = p;p = NULL;自我总结：4. 层序遍历（自上而下，自左至右）void LevelOrder(BiTree T)InitQueue(Q);BiTre

12、e p;EnQueue(Q,T);while(!IsEmpty(Q)DeQueue(Q,p);Visit(p);if(p->lchild!=NULL)EnQueue(Q,p->lchild);if(p->rchild!=NULL)EnQueue(Q,p->rchild);自我总结：5. 层序遍历（自下而上，自右至左）void InvertLevel(BiTree bt)Stack S;Queue Q;if(bt!=NULL)InitStack(S);InitQueue(Q);EnQueue(Q,bt);while(IsEmpty(Q)=false)DeQueue(Q,p

13、);Push(S,p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);while(IsEmpty(S)=false)Pop(S,p);visit(p->data);自我总结：6. 求二叉树深度（高度）（递归）int Btdepth(BiTree T)if(T=NULL)return 0;Ldep = Btdepth(T->lchild);rdep = Btdepth(T->rchild);if(ldep>rdep)return ldep+1；elseretu

14、rn rdep+1;注：求某一层结点个数，每一层结点个数，树的最大宽度等，都采用此思想自我总结：求二叉树深度（非递归）int Btdepth(BiTree T)if(!T)return 0;int front = -1,rear = -1;int last = 0,level = 0;BiTree QMaxSize;Q+rear=T；BiTree p;while(front<rear)p=Q+front;if(p->lchild)Q+rear=p->lchild;if(p->rchild)Q+rear=p->rchild;if(front=last)level+;

15、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;非递归#define MAX_QUEUE 50void swap(BiTree T)BiTree QUEUEMAX_QUEUE，temp,p=T;int front,rear;if(T!=NULL)QUEUE0=T;front=-1;rear=0;

16、while(front<rear)p=QUEUE+front;temp=p->lchild;p->lchild=p->rchild;p->rchild=temp;if(p->lchild!=NULL)QUEUE+rear=p->lchild;if(p->rchild!=NULL)QUEUE+rear=p->rchild;自我总结：8. 删除二叉树中以某个结点为根结点的子树void DeleteXTree(BiTree bt)if(bt)DeleteXTree(bt->lchild);DeleteXTree(bt->rchild)

17、;free(bt);void Search(BiTree bt,ElemType X)if(bt)if(bt->data=X)DeleteXTree(bt);exit(0);initQueue(Q);EnQueue(Q,bt);while(!IsEmpty(Q)DeQueue(Q,p);if(p->lchild)if(p->lchild->data=X)DeleteXTree(p->lchild);p->lchild=NULL;elseEnQueue(Q,p->lchild);if(p->rchild)if(p->rchild->da

18、ta=X)DeleteXTree(p->rchild);p->rchild=NULL;elseEnQueue(Q,p->rchild);自我总结：9. 建立二叉树（从键盘输入数据，先序遍历递归算法）BiTree Create()char ch;BiTree T;scanf("%c",&ch);if(ch=' ')return NULL;elseT=(BiTree)malloc(sizeof(BTNode);T->data=ch;T->lchild=Create();T->rchild=Create();return

19、 T;自我总结：10. 建立二叉树（从数组获取数据）Bitree CreateBT(int A,int i,int n)BiTree p;if(i>n) return NULL;elsep=(BiTree)malloc(sizeof(BTNode);p->data=Ai;p->lchild=CreateBT(A,2*i,n);p->rchild=CreateBT(A,2*i+1,n);return p;法二：BiTree CreateBT(int A,int n)int i;BiTree *PT;for(i=1;i<=n;i+)if(Ai!=0)PTi=(BiTr

20、ee)malloc(sezeof(BTNode);PTi->data=Ai;elsePTi=NULL;for(i=1;i<=n;i+)if(PTi!=NULL)PTi->lchild=PT2*i;PTi->rchild=PT2*i+1;自我总结：11. 求结点所在的层次：#define MAX_STACK 50int LayerNode(BiTree T,int item)BiTree STACK1MAX_STACK,P=T;int STACK2MAX_STACK,flag,top=-1;while(p!=NULL|top!=-1)while(p!=NULL)STACK

21、1+top=p;STACK2top=0;p=p->lchild;p=STACK1top;flag=STACK2top-;if(flag=0)STACK1+top=p;STACK2top=1;p=p->rchild;elseif(p->data=item)return top+2;p=NULL;自我总结：查找1. 顺序查找：typedef structElemType *elem;int TableLen;SSTable;int Search_Seq(SSTable ST,ElemType key)ST.elem0=key;for(i=ST.TableLen;ST.elemi!

22、=key;-i);return i;递归：int SeqSearch(int A,int n,int key,int i)if(i>=n) return -1;if(Ai=key) return i;else return SeqSearch(A,n,key,i+1);调用:Pos=SeqSearch(A,n,key,0);总结：2. 折半查找：int Binary_Search(SeqList L,ElemType key)int low = 0;high=L.TableLen-1,mid;while(low<=high)mid=(low+high)/2;if(L.elemmid=key)return mid;else if(L.elemmid>key)high=mid-1;elselow = mid+1;retu