(七)数据结构--查找算法-创新互联

1、顺序查找 原理

顺序查找又称为线性查找，对于顺序表和链表都是适用的，

目前成都创新互联已为成百上千的企业提供了网站建设、域名、虚拟空间、网站改版维护、企业网站设计、东至网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。顺序表

可以通过数组下标递增来顺序扫描到每个元素。

在之前(二)数据结构–线性表中顺序表使用的是数组。
在本章中顺序表使用指针，就是申请一个堆空间，使用方式和数组一致。

顺序表的类型结构体

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指针
	int TabelLen; // 存储动态数组里的元素的个数
} SSTable;

顺序查找

步骤

1. 初始化，申请堆空间；并且生成随机数，打印顺序表
2. for循环查找

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指针, 申请地址存入elem;
    int TabelLen; // 存储动态数组里的元素的个数
}SSTable;

// 初始化
void initSSTable(SSTable &ST, int len){ST.TabelLen=len;
    // malloc申请空间
    ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.TabelLen);
    srand(time(NULL)); // 随机数生成,方便测试
    for (int i = 0; i< ST.TabelLen; i++) {ST.elem[i] = rand() % 100;
    }
}

// 打印数组
void log(SSTable ST){for (int i = 0; i< ST.TabelLen; i++) {printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

int getSSTable(SSTable ST, ElemType key){for (int i = 0; i< ST.TabelLen; i++) {if (ST.elem[i]==key){return i;
        }
    }
    return -1;
}

int main() {SSTable ST;
    initSSTable(ST, 10);
    log(ST);
    printf("please input search key\n");
    ElemType key;
    scanf("%d",&key);
    int ret=getSSTable(ST, key);
    if (ret!=-1){pprintf("search element success an key=%d\n",ret);
    } else {printf("search element failed\n");
    }
    return 0;
}

链表可以通过指针next来依次扫描每个元素。

2、折半查找 原理

折半查找又称为二分查找，仅适用于有序的顺序表
基本思想【在折半查找时用到循环】
例如：1 12 34 56 66 72 73 81 92 94这10个数字，找其中任意一个数(假设为34)

• 用第一个数字的下标与最后一个数字的下标相加再除以2，得到66
• 用66和34作比较，如果相等，直接返回存储位置，如果不等，判断在除去中间元素的前半部分还是后半部分，(因为是题目中为升序，34<66所以在前半部分)
• 再次进行二分查找，(0+3)/2=1.5; 取1 得到12
• 用12和34进行比较，再次进行折半查找，直至找到为止。
• 如果没有找到，返回错误信息

结构体

在此处使用了qsort,使用方法：

#includevoid qsort(void *buf,size_t num, size_t size, int (*compare)(const void *, const void *));

buf:数组的起始地址，也可以是指针
num:数组中的元素个数
size:数组中每个元素所占空间的大小
compare:比较规则，需要自己写一个函数，返回int类型，在qsort中调用
int (*compare)(const void *, const void *)函数指针，传递一个行为给一个函数。
qsort只能用来排数组,规定如果left指针指向的值大于right指针指向的值，返回正值，反之返回负值，相等返回0

步骤

1. 初始化，申请堆空间；并且生成随机数
2. 使用qsort进行排序，排序完毕后，打印
3. 输入要查找的元素存入key中
4. 通过二分查找找的对应的key值，找到输出位置，没找到输出未找到

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指针, 申请地址存入elem;
    int TabelLen; // 存储动态数组里的元素的个数
}SSTable;
// 打印数组
void log(SSTable ST){for (int i = 0; i< ST.TabelLen; i++) {printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
// 初始化
void initSSTable(SSTable &ST, int len){// 多申请了一个位置，为了存哨兵
//     ST.TabelLen=len+1;
    ST.TabelLen=len;
    // malloc申请空间
    ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.TabelLen);
    srand(time(NULL)); // 随机数生成,方便测试
    for (int i = 0; i< ST.TabelLen; i++) {// 因为0存哨兵，所以下标从1开始
        // for (int i = 1; i< ST.TabelLen; i++) { // 因为0存哨兵，所以下标从1开始
        ST.elem[i] = rand() % 100;
    }
}
// 函数名存的是函数的入口地址，也是一个指针
int compare(const void *left, const void *right){return *(ElemType *)left-*(ElemType *)right; // left指针指向的值-right指针指向的值
}
// 二分查找
int BinarySearch(SSTable &ST,ElemType key){// 定义low high
    int low=0;
    int high=ST.TabelLen-1;
    int mid;
    while (low<=high){mid=(low+high)/2;
        if (key>ST.elem[mid]){low=mid+1;
        } else if (keyhigh=mid-1;
        } else {return mid;
        }
    }
    return -1;
}
int main() {SSTable ST;
    initSSTable(ST, 10);
    log(ST);
    // 排序
    qsort(ST.elem,ST.TabelLen,sizeof(ElemType),compare);
    log(ST);
    ElemType key;
    printf("please input search key\n");
    scanf("%d",&key);
    // 二分查找
    int pos=BinarySearch(ST,key);
    if (pos!=-1){printf("search element success an key=%d\n",pos);
    } else{printf("search element failed\n");
    }
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：(七)数据结构--查找算法-创新互联
文章URL：http://www.cdkjz.cn/article/ddcdjd.html