《数据结构基础》
作者: [美]Ellis Horowitz 霍罗维兹
译者: 朱仲涛
出版社: 清华大学出版社
ISBN: 9787302186960
在 豆瓣读书 中查看本书

算法综论

• 对于大规模计算机系统，设计高效算法是解决问题的核心。
• 算法的定义：算法是指令的有限集合，顺序执行这些指令，可以完成特定任务。

1. 输入：从外界获取零个或多个量
2. 输出：产生至少一个量
3. 确定性：每条指令清晰、无二义性
4. 有限性：算法对所有情形都能在执行有限步之后结束。
5. 有效性：每条指令都是基本可执行的。

• 计算理论范畴中的算法与程序有不同含义，计算理论中的程序无需满足上述的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]比较的结果，有三种可能：

1. searchnum < list[middle]：如果searchnum在表中，它一定在位置0与middle-1之间。所以：

right=middle-1;

2. searchnum == list[middle]：返回middle。
3. 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}，得到生成所有置换的简单算法,以下是算法的构造过程:

1. a跟在(b,c,d)的所有置换之后。
2. b跟在(a,c,d)的所有置换之后。
3. c跟在(a,b,d)的所有置换之后。
4. 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);
        }
    }
}