考研數(shù)據(jù)結構算法經典

數(shù)據(jù)結構算法背誦

一、線性表

1.逆轉順序表中的所有元素

算法思想：第一個元素和最后一個元素對調，第二個元素和倒數(shù)第二

個元素對調，……，依此類推。

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ù)域為

item的所有結點

算法思想：先從鏈表的第

2個結點開始，從前往后依次判斷鏈表中的所有結點是否滿足條件,

若某個

結點的數(shù)據(jù)域為

item,則刪除該結點。最后再回過頭來判斷鏈表中的第

1個結點是否滿足條件，若

滿足則將其刪除。

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.逆轉線性鏈表

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.復制線性鏈表(遞歸)

LinkListCopy(LinkListlista)

(

LinkListlistb;

if(lista==NULL)

returnNULL;

else{

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

listb->data=lista->data;

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

returnlistb;

)

)

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

鏈表

LinkListMergeList(LinkListlista,LinkListlistb)

(

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

//listc指向lista和listb所指結點中較小者

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;

//將剩余結點(即未參加比較的且已按升序排列的結點)鏈接到整個

鏈表后面

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

returnlistc;

}

二、樹

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

算法思想：若

P所指結點不為空，則訪問該結點，然后將該結點的地址入棧，然后

再將

P指向其左孩

子結點；若

P所指向的結點為空，則從堆棧中退出棧頂元素(某個結點的地址),

將

P指向其右孩子

結點。重復上述過程，直到

p=NULL且堆棧為空，遍歷結束。

#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所指結點不為空，則將該結點的地址

p入棧，然后再將

P指向其左孩子結點；若

P所

指向的結點為空，則從堆棧中退出棧頂元素（某個結點的地址）送

P，并訪問該結點，然后再將

p指

向該結點的右孩子結點。重復上述過程，直到

p=NULL且堆棧為空，遍歷結束。

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

算法思想：當

P指向某一結點時，不能馬上對它進行訪問，而要先訪問它的左子樹,

因而要將此結點

的地址入棧；當其左子樹訪問完畢后，再次搜索到該結點時（該結點

地址通過退棧得到），還不能對

它進行訪問，還需要先訪問它的右子樹，所以，再一次將該結點的地

址入棧。只有當該結點的右子

樹訪問完畢后回到該結點時，才能訪問該結點。為了標明某結點是否

可以訪問，引入一個標志變量

flag,當

flag=O時表示該結點暫不訪問，

flag=1時表示該結點可以訪問。flag的值隨同該結點的地

址一起入棧和出棧。因此，算法中設置了兩個堆棧，其中

STACK1存放結點的地址，STACK2存放

標志變量

flag,兩個堆棧使用同一棧頂指針

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.二叉樹的按層次遍歷

算法思想：設置一個隊列，首先將根結點（的地址）入隊列，然后依

次從隊列中退出一個元素，每

退出一個元素，先訪問該元素所指的結點，然后依次將該結點的左孩

子結點（若存在的話）和右孩

子結點（若存在的話）入隊列。如此重復下去，直到隊列為空。

#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;

//對應

n個結點申請可容納

n個指針變量的內存空間

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

//若數(shù)組中的某個元素不等于零，則申請相應的結點空間并進行賦值

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;

〃修改結點的指針域的內容，使父結點指向左、右孩子結點

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

算法思想：對二叉樹進行遍歷，遍歷過程中依次記錄各個結點所處的

層次數(shù)以及當前已經訪問過的

結點所處的最大層次數(shù)。每當訪問到某個葉子結點時，將該葉子結點

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

行比較，若前者大于后者，則修改最大層次數(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.求結點所在層次

算法思想：采用后序遍歷的非遞歸算法對二叉樹進行遍歷，遍歷過程

中對每一個結點判斷其是否為

滿足條件的結點，若是滿足條件的結點，則此時堆棧中保存的元素個

數(shù)再加

1即為該結點所在的層次。

#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.交換二叉樹中所有結點的左右子樹的位置

算法思想：按層次遍歷二叉樹，遍歷過程中每當訪問一個結點時，就

將該結點的左右子樹的位置對

調。

#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.刪除二叉樹中以某個結點為根結點的子樹

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

后刪除以該結點為根結點的子樹。

最后把該結點的父結點的相應的指針域置為

NULLo為此，需在算法中設置一個指針變量用以指示當

前結點的父結點。

#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趟插入排序為：在含有

i.1個元素的有序子序列中插入一個元素，使之成為含有

i

個元素的有序子序列。在查找插入位置的過程中，可以同時后移元素。

整個過程為進行

n.1趟插入，

即先將整個序列的第

1個元素看成是有序的，然后從第

2個元素起逐個進行插入，直到整個序列有序

為止。

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個元素和第

2個元素進行比較，若前者大于后者，則兩者交換位置，然后比較

第

2個元素和第

3個元素。依此類推，直到第

n.1個元素和第

n個元素進行過比較或交換為止。上

述過程稱為一趟冒泡排序，其結果是使得

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

±o然后進行第二趟排序，即對前

n.l個元素進行同樣的操作，使得前

nJ個元素中值最大的那

個元素被安排在第

n.1個位置上。一般地，第

i趟冒泡排序是從前

n.

i+1個元素中的第

1個元素

開始，兩兩比較，若前者大于后者，則交換，結果使得前

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

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

有進行過交換元素的操作”，

為此，設立一個標志變量

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

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

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

flag置為

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

flag置

為

lo因為至少要執(zhí)行一趟排序操作，故第一趟排序時，

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)個元素中選擇一個值最小的元素與該

個元素的第

1個元素交換位置，即與整個序列的第

i個元素交換。依此類推，直到

i=n.1為止。也

就是說，每一趟排序從從未排好序的那些元素中選擇一個值最小的元

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

的元素中的第

1個元素交換位置。

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.快速排序

算法思想：在參加排序的序列中任意選擇一個元素（通常稱為分界元

素或基準元素），把小于或等于

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

元素都移到