《数据结构考研必背算法5星(共10页).docx》由会员分享,可在线阅读,更多相关《数据结构考研必背算法5星(共10页).docx(10页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上数据结构考研必背算法5星文档说明:本文档是针对考研专业课数据结构所编写的,是对考研数据结构的核心算法进行总结,我们知道,不管是统考还是非统考,都会涉及至少10分的算法题(非统考至少25分),而这些题的答案都是在一些经典算法的思想上进行改进的,本文总结出必须要熟练掌握的算法,这些算法不管是考研初期还是冲刺,都应该高度重视,只要对这些代码进行熟练掌握,才能随机应变,希望对大家有所帮助;专心-专注-专业线性表1.逆转顺序表中的所有元素void Reverse(int A ,int n)int i,t;for(i=0;inext;while (P!=NULL)if(p-dat
2、a = 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(Li
3、nklist &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-nex
4、t;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. 将两个
5、按值有序排列的非空线性表合并为一个按值有序的线性表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;自我总结
6、: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;L
7、1-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 InO
8、rder(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);Vi
9、sit(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);BiTr
10、ee 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(
11、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;注:求某一层结点个数,每一层结点个数,树的最大宽度等,都采用此思想自我总结
12、:求二叉树深度(非递归)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-lchi
13、ld);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
14、+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)DeleteX
15、Tree(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=Crea
16、te();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
17、=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;S
18、TACK2top=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) retur
19、n 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 -1;递归:typedef structElemType *elem;int length;SSTable;int BinSearchRec(SSTable ST,ElemType key,int l
20、ow,int high)if(lowhigh) return 0;mid=(low+high)/2;if(keyST.elemmid)BinSearchRec(ST,key,mid+1,high);else if(keyST.elemmid)BinSearchRec(ST,key,low,mid-1);else return mid;自我总结:3. 在按值递归排序且长度为n的线性表中折半查找并插入一个元素void BinInsert(int A,int n,int key)int j,low=0,high=n-1,mid;while(lowAmid)low=mid+1;elsehigh=mid-1;for(j=n;jlow;j-)Aj=Aj-1;Alow=key;n+;自我总结:4. 在按值递增排列且长度为n的线性表中折半查找值不小于key的最小元素void BinSearch(int A,int n,int key)int low=0,high=n-1,mid;while(lowAmid)return mid+1;elsehigh=mid-1;if(low=n-1)return low;elsereturn -1;自我总结: