数据结构复习

二、顺序表及其应用：

• 顺序查找算法：从顺序表的一端开始顺序扫描，将给定的k值一次与顺序表中各元素的关键字比较

int SeqSearch(List L,KeyType k)
{
    //在顺序表L中顺序查找其关键字等于k的元素，若找到返回该元素的位置，否则为0 
    L.r[0].key=k;    //0号单元做为监视哨 
    int i=L.lengrh;
    while(L.r[i].key!=k)
        i--;
    retutn i;
 } 

　　ASL=(求和公式1到n)PiCi = (n+1)/2

• 二分查找算法(折半查找):要求待查找的数据元素必须按关键字的大小有序排列的顺序表

int BinSrch(List *L,KeyType k)
{
	//在顺序表L中二分查找其关键字等于k的元素，若找到返回该元素的位置 
	int low,high,mid,i;
	low=i=0;
	high=L->length-1;	//置区间初值 
	while(low<=high)
	{
		mid=(low+high)/2;
		if (k == L->r[mid].key)	//找到待查元素 
		{
			i = mid;
			break;
		}
		else if (k < L->r[mid].key)
			high = mid - 1;		//未找到，则在前半去查找 
		else low = mid + 1;		//继续在后半区查找 	
	}
	retutn i;
 } 

　　ASL=log₂(n+1)-1=log₂n

• 分块查找算法：索引顺序查找，每个索引项记录该块的起始位置，以及该块中的最大关键字(最小)。索引表按关键字有序排列

　　思想：(1)应用二分查找算法或简单顺序查找算法，将给定值key与索引表中的关键字比较，以确定待查元素所在的块

　　　　　(2)应用简单顺序查找算法，在相应块内查找关键字为key的数据元素

　　ASL=log₂(n/s+1)+s/2

• 三种查找算法性能比较：简单顺序查找算法效率最低，其次是分块查找，而二分查找算法的时间性能最好。

数据结构复习

原文：https://www.cnblogs.com/hly97/p/12158523.html