考研數(shù)據(jù)結(jié)構(gòu)算法經(jīng)典

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

一、線性表

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

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

個(gè)元素對(duì)調(diào)，……，依此類(lèi)推。

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)開(kāi)始，從前往后依次判斷鏈表中的所有結(jié)點(diǎn)是否滿足條件,

若某個(gè)

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

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

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;

}

二、樹(shù)

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

算法思想：若

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

再將

P指向其左孩

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

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

將

P指向其右孩子

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

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.二叉樹(shù)的中序遍歷（非遞歸算法）

算法思想：若

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

p入棧，然后再將

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

P所

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

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

p指

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

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.二叉樹(shù)的后序遍歷（非遞歸算法）

算法思想：當(dāng)

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

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

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

地址通過(guò)退棧得到），還不能對(duì)

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

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

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

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

flag,當(dāng)

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

flag=1時(shí)表示該結(jié)點(diǎn)可以訪問(wè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ù)的按層次遍歷

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

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

退出一個(gè)元素，先訪問(wèn)該元素所指的結(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ù)(從鍵盤(pán)輸入數(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ù)組獲取數(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;

//對(duì)應(yīng)

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

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

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

//若數(shù)組中的某個(gè)元素不等于零，則申請(qǐng)相應(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.求二叉樹(shù)的深度(遞歸算法)

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.求二叉樹(shù)的深度(非遞歸算法)

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

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

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

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

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

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

所記錄的最大層次數(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)所在層次

算法思想：采用后序遍歷的非遞歸算法對(duì)二叉樹(shù)進(jìn)行遍歷，遍歷過(guò)程

中對(duì)每一個(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.交換二叉樹(shù)中所有結(jié)點(diǎn)的左右子樹(shù)的位置

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

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

調(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.刪除二叉樹(shù)中以某個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)

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

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

最后把該結(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.在按值遞增排列且長(zhǎng)度為

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.在按值遞增排列且長(zhǎng)度為

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è)元素的有序子序列。在查找插入位置的過(guò)程中，可以同時(shí)后移元素。

整個(gè)過(guò)程為進(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.折半插入排序

算法思想：算法同直接插入排序，只不過(guò)使用折半查找的方法來(lái)尋找

插入位置。

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è)元素。依此類(lèi)推，直到第

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

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

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

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

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

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

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

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

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

i趟冒泡排序是從前

n.

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

1個(gè)元素

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

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

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

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

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

flag,flag=1表示有過(guò)交換元素的操作，

flag=0表示沒(méi)有過(guò)交換元素的操

作，在每一趟排序開(kāi)始前，將

flag置為

0,在排序過(guò)程中，只要有交換元素的操作，就及時(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è)元素交換。依此類(lèi)推，直到

i=n.1為止。也

就是說(shuō)，每一趟排序從從未排好序的那些元素中選擇一個(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)元素），把小于或等于

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

元素都移到