




版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 農(nóng)網(wǎng)配電營業(yè)工專業(yè)試題庫(附參考答案)
- 2025年國家公務(wù)員考試公共基礎(chǔ)知識仿真模擬試卷及答案(共十套)
- 零售業(yè)務(wù)經(jīng)理管理
- 鉚接工藝流程
- 晉升述職報(bào)告案例
- 綜合布線基本知識
- 防范支付風(fēng)險(xiǎn)保障資金安全
- 鐵路安全教育進(jìn)校園
- 防欺防暴安全教育
- 中級銀行業(yè)法律法規(guī)與綜合能力-2023年中級銀行從業(yè)資格考試《法律法規(guī)與綜合能力》預(yù)測試卷4
- 學(xué)前教育學(xué)00383-歷年真題-試卷
- 洼田飲水試驗(yàn)課件
- 【培訓(xùn)課件】卓越績效評價(jià)準(zhǔn)則導(dǎo)入培訓(xùn)
- 淡馬錫模式解讀匯總課件
- 2022年鄭州衛(wèi)生健康職業(yè)學(xué)院單招職業(yè)適應(yīng)性測試筆試試題及答案解析
- 穴位貼敷技術(shù)操作流程圖及評分標(biāo)準(zhǔn)
- 湖北省黃岡市基層診所醫(yī)療機(jī)構(gòu)衛(wèi)生院社區(qū)衛(wèi)生服務(wù)中心村衛(wèi)生室地址信息
- 個(gè)人有關(guān)事項(xiàng)報(bào)告表(全)
- 角膜上皮損傷-臨床診治專家共識-課件
- 電力排管檢驗(yàn)批
- 畢業(yè)論文-樓道節(jié)能燈的設(shè)計(jì)與實(shí)現(xiàn)
評論
0/150
提交評論