【資料結構】查找

查找的基本概念

查找表：由同一類型的資料元素（或記錄）構成的集合

靜态查找表：查找的同時對查找表不做修改操作（如插入和删除）

動态查找表：查找的同時對查找表具體修改操作

關鍵字：記錄中某個資料項的值，可用來識别一個記錄

主關鍵字：唯一辨別資料元素

次關鍵字：可以表示若幹個資料元素

平均查找長度：關鍵字的平均比較次數，也成平均搜尋長度

線性表的查找

順序查找

● 應用範圍：順序表或線性連結清單表示的靜态查找表

表内元素之間無序

● 順序表的表示：

typedef struct{
    ElemType *R;  //表基址
    int length;   //表長
}SSTable;

● 順序查找的性能分析：

空間複雜度：一個輔助空間

時間複雜度：

1）查找成功時的平均查找長度設表中各記錄查找機率相等 ASLs(n)=(1+2+……+n)/n=(n+1)/2

2）查找不成功的平均查找長度 ASLf=n+1

● 順序查找算法特點：

①算法簡單，對表結構無任何要求（順序和鍊式）

②n很大時查找效率較低

③改進措施：非等概論查找時，可按照查找機率進行排序

折半查找

【資料結構】查找

● 算法描述：

int Search_Bin(SSTable ST,int key)
{   //在有序表ST中折半查找其關鍵字等于key的資料元素。若找到，則函數值為該元素在表中的位置，否則為0
	low=1;
	high=ST.length;//置查找區間初值
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==ST.R[mid].key)
		return mid;//找到待查元素
		else if (key<ST.R[mid].key)
		high=mid-1;//繼續在前一字表進行查找
		else
		low=mid+1;//繼續在後一字表進行查找
	}//while
	return 0;//表中不存在待查元素
}

● 折半查找的性能分析：

查找過程：每次将待查記錄所在區間縮小一半，比順序查找效率高，時間複雜度為O（log2n)

适用條件：采用順序存儲結構的有序表，不宜用于鍊式結構

● 折半查找算法特點：

優點：比較次數少，查找效率高

缺點：對表結構要求高，隻能用于順序存儲的有序表

分塊查找

分塊查找（塊間有序，塊内無須）

● 分塊查找算法特點：

優點：在表中插入或删除資料元素時，隻要找到該元素對應的塊，就可以在該塊内進行插入和删除運算。由于塊内無序，故插入和删除比較容易，無需進行大量移動

缺點：要增加一個索引表的存儲空間并對初始索引表進行排序運算

樹表的查找

二叉排序樹

● 二叉排序樹的定義

二叉排序樹或者是一顆空樹，或者是具有以下性質的二叉樹：

（1）若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

（2）若它的右子樹不空，則左子樹上所有結點的值均大于它的根結點的值；

（3）它的左右子樹也分别為二叉排序樹。

● 二叉排序樹的重要性質

中序周遊一棵二叉樹時可以得到一個結點值遞增的有序序列

● 二叉排序樹的二叉連結清單存儲表示

typedef struct ElemType{
    char key;  //關鍵字項
}ElemType;    //每個結點的資料域的類型
typedef struct BSTNode{
    ElemType data;    //結點資料域
    BSTNode *lchild,*rchild;    //左右孩子指針
}BSTNode,*BSTree;

● 二叉排序樹的遞歸查找算法：

//算法7.4　二叉排序樹的遞歸查找
BSTree SearchBST(BSTree T,char key)
{
   //在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的資料元素
    //若查找成功，則傳回指向該資料元素結點的指針，否則傳回空指針
    if((!T)||key==T->data.key)
	return T;
	else if(key<T->data.key)
	return SearchBST(T->lchild,key);
	else
	return SearchBST(T->rchild,key); 
}

● 二叉排序樹的插入算法

//算法7.5　二叉排序樹的插入
void InsertBST(BSTree &T,ElemType e ) {
    //當二叉排序樹T中不存在關鍵字等于e.key的資料元素時，則插入該元素
    if(!T) {                                //找到插入位置，遞歸結束
        BSTree S = new BSTNode;                    //生成新結點*S
        S->data = e;                          //新結點*S的資料域置為e

        S->lchild = S->rchild = NULL;    //新結點*S作為葉子結點
        T =S;                            //把新結點*S連結到已找到的插入位置

    }
    else if (e.key< T->data.key)
        InsertBST(T->lchild, e );            //将*S插入左子樹
    else if (e.key> T->data.key)
        InsertBST(T->rchild, e);            //将*S插入右子樹
}// InsertBST

● 二叉排序樹的建立算法

//算法7.6　二叉排序樹的建立
void CreateBST(BSTree &T ){
    //依次讀入一個關鍵字為key的結點，将此結點插入二叉排序樹T中
	T=NULL;
	ElemType e;
	cin>>e.key;
	while(e.key!=ENDFLAG)
	{
		InsertBST(T,e);
		cin>>e.key;
	}
}

【資料結構】查找