《数据结构基础》
作者: [美]Ellis Horowitz 霍罗维兹
译者: 朱仲涛
出版社: 清华大学出版社
ISBN: 9787302186960
在 豆瓣读书 中查看本书
算法综论
- 对于大规模计算机系统，设计高效算法是解决问题的核心。
- 算法的定义：算法是指令的有限集合，顺序执行这些指令，可以完成特定任务。
- 输入：从外界获取零个或多个量
- 输出：产生至少一个量
- 确定性：每条指令清晰、无二义性
- 有限性：算法对所有情形都能在执行有限步之后结束。
- 有效性：每条指令都是基本可执行的。
- 计算理论范畴中的算法与程序有不同含义，计算理论中的程序无需满足上述的4（有限性）。例如，操作系统的工作模式是一个无限循环、无终止地等待为所有任务服务，这个系统程序从不结束，除非系统出错而崩溃。
查找策略：折半查找
分析
假定n≥1个有序整数存储在数组list之中，list[0]≤list[1]≤...≤...≤list[n-1]。我们想知道整数 searchnum是否出现在这个表中,如果是,则返回下标index，searchnum=list[index]；否则返回-1。由于这个表有序，可以用以下方法查找给定点值：
令left、right分别表示表中待查范围的左右端点，初值为：
left=0;
right=n-1;
middle为表中点下标值：
middle=(left+right)/2;
searchnum和list[middle]比较的结果，有三种可能：
-
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;
当searchnum还没找到，同时尚有没检查的其他整数，则重新计算middle，重复查找过程。
确定不再有待查找的数据：left和right是全表的两个端点，查找在两者之间进行，一旦left大于right，则说明再也没有待查找的数据了。
代码实现
迭代实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8
int binsearch(int list[],int searchnum,int left,int right);//定义折半查找函数原型
int main(){
int list[N];
//随机生成N个整数
srand((unsigned)time(NULL));
for(int i=0;i<N;i++){
list[i]=rand()%100;
}
//打印初始化结果
printf("初始化list：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//使用简单的冒泡排序将list从小到大排序
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;
}
}
}
//打印排序结果
printf("list排序后：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//获取用户输入，用户需输入欲查找的数字
int searchnum;
printf("请输入欲查找的整数。若整数存在，程序将返回整数的下标；若不存在，返回-1：\n");
scanf("%d",&searchnum);
//调用折半查找函数
int result=binsearch(list,searchnum,0,N-1);
//输出结果
printf("查找结果\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]相比的大小关系
//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;
//根据 searchnum与list[middle]相比的大小关系 调整left right的值
switch(temp){
case 0:return middle;
case 1:left=middle+1;break;
case -1:right=middle-1;break;
}
}
return -1;
}
2. 递归实现：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8
int binsearch(int list[],int searchnum,int left,int right);//定义折半查找函数原型
int main(){
int list[N];
//随机生成N个整数
srand((unsigned)time(NULL));
for(int i=0;i<N;i++){
list[i]=rand()%100;
}
//打印初始化结果
printf("初始化list：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//使用简单的冒泡排序将list从小到大排序
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;
}
}
}
//打印排序结果
printf("list排序后：\n");
for(int i=0;i<N;i++){
printf("[%d]%d\t",i,list[i]);
}
printf("\n");
//获取用户输入，用户需输入欲查找的数字
int searchnum;
printf("请输入欲查找的整数。若整数存在，程序将返回整数的下标；若不存在，返回-1：\n");
scanf("%d",&searchnum);
//调用折半查找函数
int result=binsearch(list,searchnum,0,N-1);
//输出结果
printf("查找结果\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]相比的大小关系
//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;
//根据 searchnum与list[middle]相比的大小关系 调整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;
}
递归
- 什么时候用递归表述算法更合适？一种判据：如果问题的表述本身就是递归定义，那么自然而然，采用递归方法就很合适。例如：求解阶乘，求解Fibonacci数列，求解二项式系数。
递归实现置换
问题描述
给定n≥1个元素的集合,打印这个集合所有可能的置换。
例如,给定集合{a,b,c}，它的所有置换是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}。
问题分析
容易看出，给定n个元素,共有n!种置换。 我们通过观察集合{a,b,c,d}，得到生成所有置换的简单算法,以下是算法的构造过程:
- a跟在(b,c,d)的所有置换之后。
- b跟在(a,c,d)的所有置换之后。
- c跟在(a,b,d)的所有置换之后。
- d跟在(a,b,c)的所有置换之后。
“跟在所有……置换之后”是构建递归算法的关键,这句话启发我们，如果解决了n-1个元素的置换问题,则n个元素的置换问题就可以解决了。
代码实现
注意：
- 程序中的list是字符数组
- 开始调用函数的形式是perm(list,0,n-1)。这个函数递归生成所有置换,直到i=n。
- 每次递归调用perm都生成参数list、i、n的局部新副本,每次调用i都会改变，而n不变。
- 参数list是指向数组的指针，数组的值在调用过程也保持不变。
代码：
（书P13，尚有错误）
#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);
}
}
}
