顺序查找的思路

常用算法解析及其应用场景

算法是计算机科学中最基础的概念之一。在日常生活中，我们无时无刻不在接触着各种算法，从谷歌搜索到智能手机里各种APP的推荐算法，都离不开算法的支持和应用。在这篇文章中，我将为大家介绍常用的算法和它们的应用场景。

一、排序算法

排序算法是程序中最常用的一种算法，其目的是将数据按一定方式进行排列。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序。

1、冒泡排序

冒泡排序是一种简单的排序算法，它的思路是从头到尾扫描一遍需要排序的数据，每一次将相邻两个元素进行比较并交换位置。这个过程类似于水泡在水中上浮，一遍扫描结束后，最大的元素就会像水泡一样浮到最上面。

冒泡排序的时间复杂度为O(n²)，如果需要排序的数据量很大，那么执行起来会比较慢。不过它的优点在于代码简单易懂，并且实现起来很容易。

2、选择排序

选择排序的思路是每次从数据中选择一个最小（或最大）的元素，并将其放置在序列的起始位置。按照这样的方式，每次只需要找到一个元素，就可以将数据序列排列好。

选择排序的时间复杂度也为O(n²)，但它比冒泡排序要稍微快一点。

3、插入排序

插入排序的思路是将数据分为已排序区间和未排序区间两部分。不断地将未排序区间的元素逐一与已排序区间的元素相比较，找到合适的位置插入。重复执行这个过程，最终就能将整个数据序列排列好。

插入排序的时间复杂度也为O(n²)，但它的执行速度相对于冒泡排序和选择排序要慢一些。不过它的优点在于它在处理小数据量时非常高效，并且在排序过程中需要的额外内存很少。

4、归并排序

归并排序的思路是将数据分成两个子序列，分别进行排序，最后将排序好的子序列进行合并。在合并的过程中，需要使用到一个额外的数组来存储数据。

归并排序的时间复杂度为O(nlogn)，执行效率相对较高。尤其是在处理大数据量时，它表现得十分出色。

5、快速排序

快速排序的思路不同于以上几种排序算法，它是一种分治法的排序算法。快速排序的过程是不断地将数据序列划分为两部分，并递归地对这两个子序列进行排序。

#include "stdio.h"

#include"stdlib.h"

#include"string.h"

#define MAX 31

typedef struct

{ int *k;

int *elem;

char *aa;

int length;

}SSTable;

int lw_Search(SSTable ST,int key)

{

int i;

ST.elem[0]=key;

for(i=ST.length;ST.elem[i]!=ST.elem[0];--i);

return i;

}

int lw_Search2(SSTable ST,int n,int key)

{

int low=1;int high=ST.length;int mid,a=0;

while(low<=high)

{

mid=(low+high)/2;

printf("第%d次查找:在[%d,%d]中找到元素ST[%d]: %d\n",++a,low,high,mid,ST.k[mid]);

if(ST.k[mid]==key)

return mid;

else if(ST.k[mid]>key)

high=mid-1;

else

low=mid+1;

}

return 0;

}

int lw_bubble(SSTable ST,int n)

{int i,j,temp;int *a;

for(i=1;i

for(j=i+1;j<=n;j++)

if(ST.k[i]>ST.k[j])

{ temp=ST.k[i];

ST.k[i]=ST.k[j];

ST.k[j]=temp;

}

}

int lw_prit(SSTable ST,int n)

{

int i;int *a;

for(i=1;i

printf("%-8d",ST.k[i]);

顺序查找、单链表查找、折半查找

线性表查找

在查找表的组织⽅式中，线性表是最简单的⼀种。我们在学习线性表的时候对线性表操作的实现中就涉及到查找操作的实现，只不过当时没有考虑到效率或者其他的问题，只采⽤了最

简单的⼀次循环遍历进⾏查找。

顺序查找（Sequential Search）

顺序查找（Sequential Search）的查找过程为：从表的⼀端开始，依次将记录的关键字和给定值进⾏⽐较，若某个记录的关键字和给定值相等，则查找成功；若在扫描整个表后仍未

找到关键字和给定值相等的记录则表⽰查找失败。

顺序查找⽅法既适⽤于线性表的顺序存储结构，也适⽤于线性表的链式存储结构。

对于顺序存储结构查找成功时可以返回其在顺序表中的位置，对于链式存储结构在查找成功时则可以返回该元素的指针，即结点所在地址。

假设有⼀个学⽣结构体定义如下：

[C代码]

typedef struct _student

{

int stu_number; // 学号

char name[20]; // 姓名

char gender[4]; // 性别

// 其他信息略

}STUENDT;

typedef int KEY_TYPE; // 关键字类型，此处以学⽣的学号作为查询关键字

学⽣学号唯⼀，因此可以将学号作为主关键字来区分学⽣。

下⾯以在⼀个学⽣信息集合中根据主关键字学号来查找某个学⽣为例，分别从顺序存储结构和链式存储结构介绍顺序查找算法的实现。

顺序表的定义

#define MAX_SIZE 100 // 顺序表最⼤长度

typedef STUDENT ELEM_TYPE; // 线性表元素类型

typedef struct

{

ELEM_TYPE data[MAX_SIZE]; // 使⽤数组存储顺序表数据

int length; // 顺序表长度

}SSTABLE; // 顺序查找表

// 注：为了贴合“查找”的主题，这⾥的顺序表我们取名为SSTABLE，即顺序查找表（Sequential Search Table）。

1. 实验项目的目的和任务

顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：

1) 从键盘输入10个整数，产生顺序表，并输入结点值。

2) 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。

3) 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。

4) 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。

2. 上机实验内容

1. 定义一个整型数组。用于存放顺序表的数据元素

2. 设计一个函数，完成顺序表的建立。

从键盘输入10个整数，产生顺序表，并输入结点值。

3. 设计一个函数，完成顺序表的查找。

从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。

4. 设计一个函数，完成顺序表的插入。

从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。

5. 设计一个函数，完成顺序表的删除。

从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。

6. 设计一个函数，用于顺序显示当前线性表中的所以元素。

3. 主要实验方法

程序主框架已经设计好。见SqList.C文件。请按要求设计各个函数，并完成正确调用。

下面是SqList.C里的内容

#include

#include

#define N 10 //顺序表的最大容量

int length=0; //顺序表的当前元素个数

void main()

{

int List[N];

char ch,exit='N';

do

{

system("CLS");