线性表的查找 C语言

清疚 2022-12-20 01:26 187阅读 0赞

还是书上的内容。  
（1）**折半查找**  
我这里先写折半查找（又名二分查找），是一种效率较高的查找方法，就是有个前提，查找数据的前提是数据本身是从小到大的有序排列的。只适用于有序表。时间复杂度为：![在这里插入图片描述][20201109103126367.png_pic_center]  
代码如下：

int SearchList3(SSTable ST,int key)//折半查找（二分查找），前提必须是从小到大的有序排序 
    { 
    	int mid,
    		low = 1,
    		high = ST.length;//初始化完成 
    	while(low<high)
    	{ 
    		mid = (low+high)/2; 
    		if(key == ST.Elem[mid].key)//找到待查找元素 
    			return mid;
    		else if(key<ST.Elem[mid].key)//继续在前一子表进行查找 
    			high = mid-1;
    		else//继续在后一子表进行查找 
    			low = mid+1;
    	}
    	return 0;//表中不存在待查元素 
    }

（2）**顺序查找**  
1.无脑查找（自己起的名字，不要介意）  
没有什么特殊条件，只是无脑的从前往后找（或者从后往前找）直到所有数据都遍历结束。  
2.设置监视哨的顺序查找  
数据中的数值\[0\]元素起到监视哨的作用，也是从前往后查找（或者从后往前查找）直到出现要查找的值为止，若不出现则也是遍历了所有数据元素结束。时间复杂度为O(n)。  
完整代码如下（该代码中没有折半查找，折半查找需要特定的输入有序排列）：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100 //顺序表最大容量 
    
    typedef struct 
    { 
    	int key;//数据域 
    	int otherinfo;//其他域 
    }ElemType;
    typedef struct//顺序表 
    { 
    	ElemType *Elem;//存储空间基地址 
    	int length;//当前长度 
    }SSTable;
    
    void InitList(SSTable &ST)//顺序表的初始化 
    { 
    	ST.Elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);//为顺序表申请空间 
    	ST.length = 0;//使顺序表长度初始化为0 
    }
    
    void MyList(SSTable &ST)//创建顺序表 
    { 
    	printf("输入数据："); 
    	while(1)//创建一个死循环 
    	{ 
    		ST.length++;//表长自加1 
    		scanf("%d",&ST.Elem[ST.length].key);//输入表数据，这里是从[1]开始输入 
    		if(getchar()=='\n')//死循环结束条件 
    			break;
    	}
    }
    
    void OutputList(SSTable ST)//顺序表的输出 
    { 
    	int i;
    	printf("打印：");
    	for(i=0;i<ST.length;i++)//利用循环遍历顺序表 
    		printf("%d ",ST.Elem[i+1].key);
    	printf("\n");
    }
    
    int SearchList1(SSTable ST,int key)//顺序查找 
    { //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0 
    	int i;
    	for(i=ST.length;i>=i;i--)//从后往前查找 
    	{ 
    		if(ST.Elem[i].key == key)
    			return i;
    	}
    	return 0;
    }
    
    int SearchList2(SSTable ST,int key)//设置监视哨的顺序查找 
    { //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0 
    	int i;
    	ST.Elem[0].key = key;//“哨兵” 
    	for(i=ST.length;ST.Elem[i].key!=key;i--);//从后往前找 
    	return i;
    } 
    
    int main()
    { 
    	SSTable ST; 
    	InitList(ST);//初始化顺序表 
    	MyList(ST);//创建顺序表 
    	OutputList(ST);//顺序表的输出 
    	printf("%d ",SearchList1(ST,15));//顺序查找函数 ，函数中的数据是为了方便测试代码，可更换成变量 
    	printf("%d ",SearchList2(ST,16));
    	free(ST.Elem);
    	return 0;
    }

结果演示：  
![在这里插入图片描述][20201109104408802.png_pic_center]  
（完）

[20201109103126367.png_pic_center]: /images/20221120/5c4d8b0ce9964ac097deaa2a02d75e5b.png
[20201109104408802.png_pic_center]: https://img-blog.csdnimg.cn/20201109104408802.png#pic_center