考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典_第1頁
考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典_第2頁
考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典_第3頁
考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典_第4頁
考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典_第5頁
已閱讀5頁,還剩37頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

數(shù)據(jù)結(jié)構(gòu)算法背誦

一、線性表

1.逆轉(zhuǎn)順序表中的所有元素

算法思想:第一個(gè)元素和最后一個(gè)元素對調(diào),第二個(gè)元素和倒數(shù)第二

個(gè)元素對調(diào),……,依此類推。

voidReverse(intA[],intn)

(

inti,t;

for(i=0;i<n/2;i++)

(

t=A[i];

A[i]=A[n-i-l];

A[n-i-lJ=t;

)

)

2.刪除線性鏈表中數(shù)據(jù)域?yàn)?/p>

item的所有結(jié)點(diǎn)

算法思想:先從鏈表的第

2個(gè)結(jié)點(diǎn)開始,從前往后依次判斷鏈表中的所有結(jié)點(diǎn)是否滿足條件,

若某個(gè)

結(jié)點(diǎn)的數(shù)據(jù)域?yàn)?/p>

item,則刪除該結(jié)點(diǎn)。最后再回過頭來判斷鏈表中的第

1個(gè)結(jié)點(diǎn)是否滿足條件,若

滿足則將其刪除。

voidPurgeItem(LinkList&list)

LinkListp,q=list;

p=list->next;

while(p!=NULL)

if(p->data==item){

q->next=p->next;

free(p);

p=q->next;

}else{

q=p;

p=p->next;

)

)

if(list->data==item)

q=list;

list=list->next;

free(q);

)

}

3.逆轉(zhuǎn)線性鏈表

voidReverse(LinkList&list)

(

LinkListp,q,r;

p=list;

q=NULL;

while(p!=NULL)

r=q;

q=p;

p=p->next;

q->next=r;

list=q;

4.復(fù)制線性鏈表(遞歸)

LinkListCopy(LinkListlista)

(

LinkListlistb;

if(lista==NULL)

returnNULL;

else{

listb=(LinkList)malloc(sizeof(LNode));

listb->data=lista->data;

listb->next=Copy(lista->next);

returnlistb;

)

)

5.將兩個(gè)按值有序排列的非空線性鏈表合并為一個(gè)按值有序的線性

鏈表

LinkListMergeList(LinkListlista,LinkListlistb)

(

LinkListlistc,p=lista,q=listb,r;

//listc指向lista和listb所指結(jié)點(diǎn)中較小者

if(lista->data<=listb->data){

listc=lista;

r=lista;

p=lista->next;

}else{

listc=listb;

r=listb;

q=listb->next;

while(p!=NULL&&q!=NULL)

if(p->data<=q->data){

r->next=p;

r=p;

p=p->next;

}else{

r->next=q;

r=q;

q=q->next;

//將剩余結(jié)點(diǎn)(即未參加比較的且已按升序排列的結(jié)點(diǎn))鏈接到整個(gè)

鏈表后面

r->next=(p!=NULL)?p:q;

returnlistc;

}

二、樹

1.二叉樹的先序遍歷(非遞歸算法)

算法思想:若

P所指結(jié)點(diǎn)不為空,則訪問該結(jié)點(diǎn),然后將該結(jié)點(diǎn)的地址入棧,然后

再將

P指向其左孩

子結(jié)點(diǎn);若

P所指向的結(jié)點(diǎn)為空,則從堆棧中退出棧頂元素(某個(gè)結(jié)點(diǎn)的地址),

P指向其右孩子

結(jié)點(diǎn)。重復(fù)上述過程,直到

p=NULL且堆棧為空,遍歷結(jié)束。

#defineMAX_STACK50

voidPreOrderTraverse(BTreeT)

(

BTreeSTACK[MAX_STACK],p=T;

inttop=-1;

while(p!=NULLIItop!=-l)

while(p!=NULL)

VISIT(p);

STACK[++top]=p;

p=p->lchild;

p=STACK[top-];

p=p->rchild;

)

)

2.二叉樹的中序遍歷(非遞歸算法)

算法思想:若

P所指結(jié)點(diǎn)不為空,則將該結(jié)點(diǎn)的地址

p入棧,然后再將

P指向其左孩子結(jié)點(diǎn);若

P所

指向的結(jié)點(diǎn)為空,則從堆棧中退出棧頂元素(某個(gè)結(jié)點(diǎn)的地址)送

P,并訪問該結(jié)點(diǎn),然后再將

p指

向該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。重復(fù)上述過程,直到

p=NULL且堆棧為空,遍歷結(jié)束。

#defineMAX_STACK50

voidInOrderTraverse(BTreeT)

BTreeSTACK[MAX_STACK],p=T;

inttop=-1;

while(p!=NULLIItop!=-l);

(

while(p!=NULL)

(

STACK[++top]=p;

p=p->lchild;

)

p=STACK[top-];

VISIT(p);

p=p->rchild;

3.二叉樹的后序遍歷(非遞歸算法)

算法思想:當(dāng)

P指向某一結(jié)點(diǎn)時(shí),不能馬上對它進(jìn)行訪問,而要先訪問它的左子樹,

因而要將此結(jié)點(diǎn)

的地址入棧;當(dāng)其左子樹訪問完畢后,再次搜索到該結(jié)點(diǎn)時(shí)(該結(jié)點(diǎn)

地址通過退棧得到),還不能對

它進(jìn)行訪問,還需要先訪問它的右子樹,所以,再一次將該結(jié)點(diǎn)的地

址入棧。只有當(dāng)該結(jié)點(diǎn)的右子

樹訪問完畢后回到該結(jié)點(diǎn)時(shí),才能訪問該結(jié)點(diǎn)。為了標(biāo)明某結(jié)點(diǎn)是否

可以訪問,引入一個(gè)標(biāo)志變量

flag,當(dāng)

flag=O時(shí)表示該結(jié)點(diǎn)暫不訪問,

flag=1時(shí)表示該結(jié)點(diǎn)可以訪問。flag的值隨同該結(jié)點(diǎn)的地

址一起入棧和出棧。因此,算法中設(shè)置了兩個(gè)堆棧,其中

STACK1存放結(jié)點(diǎn)的地址,STACK2存放

標(biāo)志變量

flag,兩個(gè)堆棧使用同一棧頂指針

top,且

top的初始值為

.lo

#defineMAX_STACK50

voidPostOrderTraverse(BTreeT)

BTreeSTACK1[MAX_STACKJ,p=T;

intSTACK2[MAX_STACK],flag,top=-1;

while(p!=NULLIItop!=-l)

while(p!=NULL){

STACKl[++top]=p;

STACK2[top]=0;

p=p->lchild;

p=STACK1[top];

flag=STACK2[top-];

if(flag==0){

STACKl[++top]=p;

STACK2[top]=1;

p=p->rchild;

}else{

VISIT(p);

p=NULL;

4.二叉樹的按層次遍歷

算法思想:設(shè)置一個(gè)隊(duì)列,首先將根結(jié)點(diǎn)(的地址)入隊(duì)列,然后依

次從隊(duì)列中退出一個(gè)元素,每

退出一個(gè)元素,先訪問該元素所指的結(jié)點(diǎn),然后依次將該結(jié)點(diǎn)的左孩

子結(jié)點(diǎn)(若存在的話)和右孩

子結(jié)點(diǎn)(若存在的話)入隊(duì)列。如此重復(fù)下去,直到隊(duì)列為空。

#defineMAX_QUEUE50

voidLayeredOrderTraverse(BTreeT)

BTreeQUEUE[MAX_QUEUE],p;

intfront,rear;

if(T!=NULL)

(

QUEUE[0]=T;

front=-1;

rear=0;

while(front<rear)

p=QUEUE[++front];

VISIT(P);

if(p->lchild!=NULL)

QUEUE[++rear]=p->lchild;

if(p->rchild!=NULL)

QUEUE[++rearJ=p->rchild;

5.建立二叉樹(從鍵盤輸入數(shù)據(jù),先序遍歷遞歸算法)

BTreeCreateBT()

charch;

BTreeT;

sacnf("%c",&ch);

if(ch==")

returnNULL;

else{

T=(BTree)malloc(sizeof(BTNode));

T->data=ch;

T->Ichild=CreateBT();

T->rchild=CreateBT();

returnT;

6.建立二叉樹(從數(shù)組獲取數(shù)據(jù))

BTreeCreateBT(intA[],inti,intn)

BTreep;

if(i>n)

returnNULL;

else{

p=(BTree)malloc(sizeof(BTNode));

p->data=A[i];

p->lchild=CreateBT(A,2*i,n);

p->rchild=CreateBT(A,2*i+l,n);

returnp;

)

)

T=CreateBT(A,1,n);

BTreeCreateBT(intA[],intn)

inti;

BTree*pT;

//對應(yīng)

n個(gè)結(jié)點(diǎn)申請可容納

n個(gè)指針變量的內(nèi)存空間

pT=(BTree*)malloc(sizeof(BTree)*n);

//若數(shù)組中的某個(gè)元素不等于零,則申請相應(yīng)的結(jié)點(diǎn)空間并進(jìn)行賦值

for(i=l;i<=n;i++)

if(A[i]!=0){

pT[i]=(BTree)malloc(sizeof(BTNode));

pT[i]->data=A[i];

}else{

pT[i]=NULL;

〃修改結(jié)點(diǎn)的指針域的內(nèi)容,使父結(jié)點(diǎn)指向左、右孩子結(jié)點(diǎn)

for(i=l;i<=n;i++)

(

if(pT[i]!=NULL)

pT[i]->lchild=pT[2*i];

pT[i]->rchild=pT[2*i+l];

7.求二叉樹的深度(遞歸算法)

intDepth(BTreeT)

(

intIdepth,rdepth;

if(T==NULL)

return0;

else{

Idepth=Depth(T->lchild);

rdepth=Depth(T->rchild);

if(Idepth>rdepth)

returnldepth+1;

else

returnrdepth+1;

)

)

8.求二叉樹的深度(非遞歸算法)

算法思想:對二叉樹進(jìn)行遍歷,遍歷過程中依次記錄各個(gè)結(jié)點(diǎn)所處的

層次數(shù)以及當(dāng)前已經(jīng)訪問過的

結(jié)點(diǎn)所處的最大層次數(shù)。每當(dāng)訪問到某個(gè)葉子結(jié)點(diǎn)時(shí),將該葉子結(jié)點(diǎn)

所處的層次數(shù)與最大層次數(shù)進(jìn)

行比較,若前者大于后者,則修改最大層次數(shù)為該葉子結(jié)點(diǎn)的層次數(shù),

否則不作修改。遍歷結(jié)束時(shí),

所記錄的最大層次數(shù)即為該二叉樹的深度。本算法使用的是非遞歸的

中序遍歷算法(其它遍歷順序

也可以)。

#defineMAX_STACK50

intDepth(BTreeT)

(

BTreeSTACK1[MAX_STACK],p=T;

intSTACK2[MAX_STACK];

intcurdepth,maxdepth=0,top=-1;

if(T!=NULL)

(

curdepth=1;

while(p!=NULLIItop!=-)

while(p!=NULL)

(

STACK1[++top]=p;

STACK2[top]=curdepth;

p=p->lchild;

curdepth++;

p=STACK1[top];

curdepth=STACK2[top—J;

if(p->lchild==NULL&&p->rchild==NULL)

if(curdepth>maxdepth)

maxdepth=curdepth;

p=p->rchild;

curdepth++;

)

)

returnmaxdepth;

9.求結(jié)點(diǎn)所在層次

算法思想:采用后序遍歷的非遞歸算法對二叉樹進(jìn)行遍歷,遍歷過程

中對每一個(gè)結(jié)點(diǎn)判斷其是否為

滿足條件的結(jié)點(diǎn),若是滿足條件的結(jié)點(diǎn),則此時(shí)堆棧中保存的元素個(gè)

數(shù)再加

1即為該結(jié)點(diǎn)所在的層次。

#defineMAX_STACK50

intLayerNode(BTreeT,intitem)

BTreeSTACK1[MAX_STACK],p=T;

intSTACK2[MAX_STACK],flag,top=-l;

while(p!=NULLIItop!=-l)

while(p!=NULL)

STACKl[++top]=p;

STACK2[top]=0;

p=p->lchild;

p=STACK1[top];

flag=STACK2[top-];

if(flag==0){

STACKl[++top]=p;

STACK2[top]=1;

p=p->rchild;

}else{

if(p->data==item)

returntop+2;

p=NULL;

)

)

)

10.交換二叉樹中所有結(jié)點(diǎn)的左右子樹的位置

算法思想:按層次遍歷二叉樹,遍歷過程中每當(dāng)訪問一個(gè)結(jié)點(diǎn)時(shí),就

將該結(jié)點(diǎn)的左右子樹的位置對

調(diào)。

#defineMAX_QUEUE50

voidExchangeBT(BTreeT)

BTreeQUEUE[MAX_QUEUE],temp,p=T;

intfront,rear;

if(T!=NULL)

(

QUEUE[0]=T;

front=-1;

rear=0;

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;

11.刪除二叉樹中以某個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹

算法思想:先序遍歷找到符合條件的結(jié)點(diǎn)(其它遍歷方法亦可),然

后刪除以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹。

最后把該結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)的指針域置為

NULLo為此,需在算法中設(shè)置一個(gè)指針變量用以指示當(dāng)

前結(jié)點(diǎn)的父結(jié)點(diǎn)。

#defineMAX_STACK50

BTreeDeleteSubtree(BTree&T,intitem)

(

BTreeSTACK[MAX_STACK],q,p=T;

inttop=-1;

if(T->data==item)

(

DestroyBT(T);

T=NULL;

returnNULL;

I

else

while(p!=NULLIItop!=-l)

while(p!=NULL)

if(p->data==item)

(

if(q->lchild==p)

q->lchild=NULL;

else

q->rchild=NULL;

DestroyBT(p);

returnT;

STACK[++top]=p;

q=p;

p=p->lchild;

q=STACK[top-];

p=q->rchild;

)

}

三、查找

1.順序查找的遞歸算法

intRecurSeqSearch(intA[],intn,intkey,inti)

(

if(i>=n)

return-1;

if(A[i]==key)

returni;

else

returnRecurSeqSearch(A,n,key,i+1);

)

pos=RecurSeqSearch(A,n,key,0);

2.折半查找

intBinSearch(intA[],intn,intkey)

(

intlow=0,high=n-1,mid;

while(low<=high)

(

mid=(low+high)/2;

if(key=A[mid])

returnmid;

if(key>A[mid])

low=mid+1;

else

high=mid-1;

}

return-1;

)

3.折半查找的遞歸算法

intRecurBinSearch(intA[],intlow,inthigh,intkey)

(

intmid;

if(low>high)

return-1;

else{

mid=(low+high)/2;

if(key==A[mid])

returnmid;

if(key>A[mid])

returnRecurBinSearch(A,mid+1,high,key);

else

returnRecurBinSearch(A,low,mid-1,key);

pos=RecurBinSearch(A,0,n-1,key);

4.在按值遞增排列且長度為

n的線性表中折半查找并插入一元素

voidBinlnsert(intA[],int&n,intkey)

(

intj,low=0,high=n-l,mid;

while(low<=high)

(

mid=(low+high)/2;

if(key>A[mid])

low=mid+1;

else

high=mid-1;

for(j=n;j>low;j--)

AU]=AU-1];

A[low]=key;

n++;

)

5.在按值遞增排列且長度為

n的線性表中折半查找值不小于

key的最小元素

voidBinSearch(intA[J,intn,intkey)

intlow=0,high=n-l,mid;

while(low<=high)

(

mid=(low+high)/2;

if(key==A[mid])

returnmid;

if(key>A[mid])

low=mid+1;

else

high=mid-1;

if(low<=n-1)

returnlow;

else

return-1;

四、排序

1.插入排序

算法思想:第

i趟插入排序?yàn)椋涸诤?/p>

i.1個(gè)元素的有序子序列中插入一個(gè)元素,使之成為含有

i

個(gè)元素的有序子序列。在查找插入位置的過程中,可以同時(shí)后移元素。

整個(gè)過程為進(jìn)行

n.1趟插入,

即先將整個(gè)序列的第

1個(gè)元素看成是有序的,然后從第

2個(gè)元素起逐個(gè)進(jìn)行插入,直到整個(gè)序列有序

為止。

voidInsertSort(intA[],intn)

(

inti,j,temp;

for(i=l;i<=n-1;i++)

if(A[i]<A[i-l])

j=i-l;

temp=A[i];

while(j>=0&&temp<A[j])

(

AU+l]=A[j];

j-s

)

A[j+1]=temp;

)

)

}

2.折半插入排序

算法思想:算法同直接插入排序,只不過使用折半查找的方法來尋找

插入位置。

voidBinInsertSort(intA[],intn)

(

inti,j,low,high,mid,temp;

for(i=l;i<=n-1;i++)

temp=A[i];

low=0;

high=i-1;

while(low<=high)

mid=(low+high)/2;

if(temp>A[mid])

low=mid+1;

else

high=mid-1;

)

for(j=i;j>low;j—)

AU]=AU-1];

A[low]=temp;

)

3.冒泡排序

算法思想:首先將第

1個(gè)元素和第

2個(gè)元素進(jìn)行比較,若前者大于后者,則兩者交換位置,然后比較

2個(gè)元素和第

3個(gè)元素。依此類推,直到第

n.1個(gè)元素和第

n個(gè)元素進(jìn)行過比較或交換為止。上

述過程稱為一趟冒泡排序,其結(jié)果是使得

n個(gè)元素中值最大的那個(gè)元素被安排在最后一個(gè)元素的位置

±o然后進(jìn)行第二趟排序,即對前

n.l個(gè)元素進(jìn)行同樣的操作,使得前

nJ個(gè)元素中值最大的那

個(gè)元素被安排在第

n.1個(gè)位置上。一般地,第

i趟冒泡排序是從前

n.

i+1個(gè)元素中的第

1個(gè)元素

開始,兩兩比較,若前者大于后者,則交換,結(jié)果使得前

n.i+1個(gè)元素中最大的元素被安排在第

i+1個(gè)位置上。顯然,判斷冒泡排序結(jié)束的條件是“在一趟排序中沒

有進(jìn)行過交換元素的操作”,

為此,設(shè)立一個(gè)標(biāo)志變量

flag,flag=1表示有過交換元素的操作,

flag=0表示沒有過交換元素的操

作,在每一趟排序開始前,將

flag置為

0,在排序過程中,只要有交換元素的操作,就及時(shí)將

flag置

lo因?yàn)橹辽僖獔?zhí)行一趟排序操作,故第一趟排序時(shí),

flag=lo

voidBubbleSort(intA[],intn)

(

inti,j,temp,flag=1;

for(i=n-l;i>=1&&flag==1;i—)

(

flag=0;

for(j=O;j<i;j++)

if(A[j]>A[j+l])

temp=A[j];

A「]=AU+1];

A[j+1]=temp;

flag=1;

)

4.選擇排序

算法思想:第

i趟排序從序列的后

i+1(i=l,2,...,n.l)個(gè)元素中選擇一個(gè)值最小的元素與該

個(gè)元素的第

1個(gè)元素交換位置,即與整個(gè)序列的第

i個(gè)元素交換。依此類推,直到

i=n.1為止。也

就是說,每一趟排序從從未排好序的那些元素中選擇一個(gè)值最小的元

素,然后將其與這些未排好序

的元素中的第

1個(gè)元素交換位置。

voidSelectSort(intA[],intn)

inti,j,min,temp;

for(i=0;i<n;i++)

min=1;

for(j=i+l;j<n;j++)

if(A[min]>A[j])

min=j;

)

if(min!=i)

temp=A[min];

A[min]=A[i];

A[i]=temp;

5.快速排序

算法思想:在參加排序的序列中任意選擇一個(gè)元素(通常稱為分界元

素或基準(zhǔn)元素),把小于或等于

分界元素的所有元素都移到分界元素的前面,把大于分界元素的所有

元素都移到

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論