數(shù)據(jù)結(jié)構(gòu)考研必背算法5星(共18頁)

1、數(shù)據(jù)結(jié)構(gòu)考研必背算法5星文檔說明：本文檔是針對考研專業(yè)課數(shù)據(jù)結(jié)構(gòu)所編寫的，是對考研數(shù)據(jù)結(jié)構(gòu)的核心算法進行總結(jié)，我們知道，不管是統(tǒng)考還是非統(tǒng)考，都會涉及至少10分的算法題（非統(tǒng)考至少25分），而這些題的答案都是在一些經(jīng)典算法的思想上進行改進的，本文總結(jié)出必須要熟練掌握的算法，這些算法不管是考研初期還是沖刺，都應(yīng)該高度重視，只要對這些代碼進行熟練掌握，才能隨機應(yīng)變，希望對大家有所幫助；線性表1.逆轉(zhuǎn)順序表中的所有元素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; 自我總結(jié)：2.

2、 刪除線性表中數(shù)據(jù)域為X的所有結(jié)點；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);自我總結(jié)：3.刪除不帶頭結(jié)點單鏈表L中所有值為X的結(jié)點（遞歸）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);自我總結(jié)：4.刪除帶頭結(jié)點單鏈表L中所有值為X的結(jié)點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;注：本算法是在無序單鏈表中刪除滿足某種條件的所有結(jié)點；如：若是要刪除介于max和min之間的所有結(jié)點，只需將if語句改為if(p->data>min&&p->data<max)自我總結(jié)：5.逆轉(zhuǎn)線性表（不帶頭）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;帶頭結(jié)點：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;自我總結(jié)：6. 復(fù)制線性鏈表(遞歸)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;自我總結(jié)：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;自我總結(jié)：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);自我總結(jié)：樹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;自我總結(jié)：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;自我總結(jié)：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;自我總結(jié)：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);自我總結(jié)：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);自我總結(jié)：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;注：求某一層結(jié)點個數(shù)，每一層結(jié)點個數(shù)，樹的最大寬度等，都采用此思想自我總結(jié)：求二叉樹深度（非遞歸）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;自我總結(jié)：7. 交換二叉樹中所有結(jié)點的左右子樹位置（遞歸）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;自我總結(jié)：8. 刪除二叉樹中以某個結(jié)點為根結(jié)點的子樹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);自我總結(jié)：9. 建立二叉樹（從鍵盤輸入數(shù)據(jù)，先序遍歷遞歸算法）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;自我總結(jié)：10. 建立二叉樹（從數(shù)組獲取數(shù)據(jù)）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;自我總結(jié)：11. 求結(jié)點所在的層次：#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;自我總結(jié)：查找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);調(diào)用:Pos=SeqSearch(A,n,key,0);總結(jié)：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