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

数据结构考研必背算法5星文档说明：本文档是针对考研专业课数据结构所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助；线性表1.逆转顺序表中的所有元素void Reverse(int A ,int n)int i,t;for(i=0;inext;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,Elemtype 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 = p;p=p-next;注：本算法是在无序单链表中删除满足某种条件的所有结点；如：若是要删除介于max和min之间的所有结点，只需将if语句改为if(p-datamin&p-datanext;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;elselist2 = (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 data)L3 = L1;r = L1;p = L1-next;elseL3 = L2;r = L2;q = L2-next;while(P!=NULL&q!=NULL)if(p-data 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-data 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(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;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(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);BiTree 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);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(ldeprdep)return ldep+1；elsereturn 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(frontlchild)Q+rear=p-lchild;if(p-rchild)Q+rear=p-rchild;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;非递归#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;while(frontlchild;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);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-data=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 T;自我总结：10. 建立二叉树（从数组获取数据）Bitree CreateBT(int A,int i,int n)BiTree p;if(in) 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;idata=Ai;elsePTi=NULL;for(i=1;ilchild=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)STACK1+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!=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(lowkey)high=mid-1;elselow = mid+1;return -