《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》
作者: [美]Ellis Horowitz 霍羅維茲
譯者: 朱仲濤
出版社: 清華大學(xué)出版社
ISBN: 9787302186960
在 豆瓣讀書(shū) 中查看本書(shū)
算法綜論
- 對(duì)于大規(guī)模計(jì)算機(jī)系統(tǒng)家肯，設(shè)計(jì)高效算法是解決問(wèn)題的核心。
- 算法的定義：算法是指令的有限集合昆烁，順序執(zhí)行這些指令种冬，可以完成特定任務(wù)盟广。
- 輸入：從外界獲取零個(gè)或多個(gè)量
- 輸出：產(chǎn)生至少一個(gè)量
- 確定性：每條指令清晰穆壕、無(wú)二義性
- 有限性：算法對(duì)所有情形都能在執(zhí)行有限步之后結(jié)束毯欣。
- 有效性：每條指令都是基本可執(zhí)行的呀非。
- 計(jì)算理論范疇中的算法與程序有不同含義燎孟，計(jì)算理論中的程序無(wú)需滿(mǎn)足上述的4（有限性）禽作。例如，操作系統(tǒng)的工作模式是一個(gè)無(wú)限循環(huán)揩页、無(wú)終止地等待為所有任務(wù)服務(wù)旷偿，這個(gè)系統(tǒng)程序從不結(jié)束，除非系統(tǒng)出錯(cuò)而崩潰爆侣。
查找策略：折半查找
分析
假定n≥1個(gè)有序整數(shù)存儲(chǔ)在數(shù)組list之中萍程，list[0]≤list[1]≤...≤...≤list[n-1]。我們想知道整數(shù) searchnum是否出現(xiàn)在這個(gè)表中,如果是,則返回下標(biāo)index兔仰，searchnum=list[index]茫负；否則返回-1。由于這個(gè)表有序乎赴，可以用以下方法查找給定點(diǎn)值：
令left忍法、right分別表示表中待查范圍的左右端點(diǎn)潮尝，初值為：
left=0;
right=n-1;
middle為表中點(diǎn)下標(biāo)值：
middle=(left+right)/2;
searchnum和list[middle]比較的結(jié)果，有三種可能：
-
searchnum < list[middle]：如果searchnum在表中饿序，它一定在位置
0與middle-1之間勉失。所以：
right=middle-1;
-
searchnum == list[middle]：返回
middle。 -
searchnum > list[middle]：如果searchnum在表中嗤堰，它一定在位置
middle+1與n-1之間戴质。所以：
left=middle+1;
當(dāng)searchnum還沒(méi)找到度宦，同時(shí)尚有沒(méi)檢查的其他整數(shù)踢匣，則重新計(jì)算middle，重復(fù)查找過(guò)程戈抄。
確定不再有待查找的數(shù)據(jù)：left和right是全表的兩個(gè)端點(diǎn)离唬，查找在兩者之間進(jìn)行，一旦left大于right划鸽，則說(shuō)明再也沒(méi)有待查找的數(shù)據(jù)了输莺。
代碼實(shí)現(xiàn)
迭代實(shí)現(xiàn)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8
int binsearch(int list[],int searchnum,int left,int right);//定義折半查找函數(shù)原型
int main(){
int list[N];
//隨機(jī)生成N個(gè)整數(shù)
srand((unsigned)time(NULL));
for(int i=0;i<N;i++){
list[i]=rand()%100;
}
//打印初始化結(jié)果
printf("初始化list：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//使用簡(jiǎn)單的冒泡排序?qū)ist從小到大排序
for(int i=0;i<N;i++){
for(int j=i;j<N;j++){
if(list[i]>list[j]){
int t=list[i];
list[i]=list[j];
list[j]=t;
}
}
}
//打印排序結(jié)果
printf("list排序后：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//獲取用戶(hù)輸入，用戶(hù)需輸入欲查找的數(shù)字
int searchnum;
printf("請(qǐng)輸入欲查找的整數(shù)裸诽。若整數(shù)存在嫂用，程序?qū)⒎祷卣麛?shù)的下標(biāo)；若不存在丈冬，返回-1：\n");
scanf("%d",&searchnum);
//調(diào)用折半查找函數(shù)
int result=binsearch(list,searchnum,0,N-1);
//輸出結(jié)果
printf("查找結(jié)果\n%d",result);
return 0;
}
int binsearch(int list[],int searchnum,int left,int right){
int middle,temp;
while(left<=right){
middle=(left+right)/2;
//判斷searchnum與list[middle]相比的大小關(guān)系
//searchnum == list[middle] temp=0
//searchnum > list[middle] temp=1
//searchnum < list[middle] temp=-1
temp=(searchnum==list[middle])?0:(searchnum>list[middle])?1:-1;
//根據(jù) searchnum與list[middle]相比的大小關(guān)系 調(diào)整left right的值
switch(temp){
case 0:return middle;
case 1:left=middle+1;break;
case -1:right=middle-1;break;
}
}
return -1;
}
2. 遞歸實(shí)現(xiàn)：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8
int binsearch(int list[],int searchnum,int left,int right);//定義折半查找函數(shù)原型
int main(){
int list[N];
//隨機(jī)生成N個(gè)整數(shù)
srand((unsigned)time(NULL));
for(int i=0;i<N;i++){
list[i]=rand()%100;
}
//打印初始化結(jié)果
printf("初始化list：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//使用簡(jiǎn)單的冒泡排序?qū)ist從小到大排序
for(int i=0;i<N;i++){
for(int j=i;j<N;j++){
if(list[i]>list[j]){
int t=list[i];
list[i]=list[j];
list[j]=t;
}
}
}
//打印排序結(jié)果
printf("list排序后：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//獲取用戶(hù)輸入嘱函，用戶(hù)需輸入欲查找的數(shù)字
int searchnum;
printf("請(qǐng)輸入欲查找的整數(shù)。若整數(shù)存在埂蕊，程序?qū)⒎祷卣麛?shù)的下標(biāo)往弓；若不存在，返回-1：\n");
scanf("%d",&searchnum);
//調(diào)用折半查找函數(shù)
int result=binsearch(list,searchnum,0,N-1);
//輸出結(jié)果
printf("查找結(jié)果\n%d",result);
return 0;
}
int binsearch(int list[],int searchnum,int left,int right){
int middle,temp;
if(left<=right){
middle=(left+right)/2;
//判斷searchnum與list[middle]相比的大小關(guān)系
//searchnum == list[middle] temp=0
//searchnum > list[middle] temp=1
//searchnum < list[middle] temp=-1
temp=(searchnum==list[middle])?0:(searchnum>list[middle])?1:-1;
//根據(jù) searchnum與list[middle]相比的大小關(guān)系 調(diào)整left right的值
switch(temp){
case 0:return middle;
case 1:return binsearch(list,searchnum,middle+1,right);
case -1:return binsearch(list,searchnum,left,middle-1);
}
}
return -1;
}
遞歸
- 什么時(shí)候用遞歸表述算法更合適蓄氧？一種判據(jù)：如果問(wèn)題的表述本身就是遞歸定義函似，那么自然而然，采用遞歸方法就很合適喉童。例如：求解階乘撇寞，求解Fibonacci數(shù)列，求解二項(xiàng)式系數(shù)堂氯。
遞歸實(shí)現(xiàn)置換
問(wèn)題描述
給定n≥1個(gè)元素的集合,打印這個(gè)集合所有可能的置換重抖。
例如,給定集合{a,b,c}，它的所有置換是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}祖灰。
問(wèn)題分析
容易看出钟沛，給定n個(gè)元素,共有n!種置換。 我們通過(guò)觀察集合{a,b,c,d}局扶，得到生成所有置換的簡(jiǎn)單算法,以下是算法的構(gòu)造過(guò)程:
- a跟在(b,c,d)的所有置換之后恨统。
- b跟在(a,c,d)的所有置換之后叁扫。
- c跟在(a,b,d)的所有置換之后。
- d跟在(a,b,c)的所有置換之后畜埋。
“跟在所有……置換之后”是構(gòu)建遞歸算法的關(guān)鍵,這句話(huà)啟發(fā)我們莫绣，如果解決了n-1個(gè)元素的置換問(wèn)題,則n個(gè)元素的置換問(wèn)題就可以解決了。
代碼實(shí)現(xiàn)
注意：
- 程序中的list是字符數(shù)組
- 開(kāi)始調(diào)用函數(shù)的形式是perm(list,0,n-1)悠鞍。這個(gè)函數(shù)遞歸生成所有置換,直到i=n对室。
- 每次遞歸調(diào)用perm都生成參數(shù)list、i咖祭、n的局部新副本,每次調(diào)用i都會(huì)改變掩宜，而n不變。
- 參數(shù)list是指向數(shù)組的指針么翰，數(shù)組的值在調(diào)用過(guò)程也保持不變牺汤。
代碼：
（書(shū)P13，尚有錯(cuò)誤）
#include <stdio.h>
#define SWAP(x,y,t)( (t)=(x),(x)=(y),(y)=(t) )
void perm(char *list,int i,int n);
int main(){
char * list="abcd";
perm(list,0,3);
return 0;
}
void perm(char *list,int i,int n){
int temp;
if(i==n){
for(int j=0;j<=n;j++){
printf("%c",list[j]);
}
printf("\n");
}else{
for(int j=i;j<=n;j++){
SWAP(list[i],list[j],temp);
perm(list,i+1,n);
SWAP(list[i],list[j],temp);
}
}
}
