1、順序查找 原理

順序查找又稱為線性查找，對于順序表和鏈表都是適用的，

目前成都創(chuàng)新互聯(lián)已為成百上千的企業(yè)提供了網(wǎng)站建設、域名、虛擬空間、網(wǎng)站改版維護、企業(yè)網(wǎng)站設計、東至網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。順序表

可以通過數(shù)組下標遞增來順序掃描到每個元素。

在之前(二)數(shù)據(jù)結(jié)構–線性表中順序表使用的是數(shù)組。
在本章中順序表使用指針，就是申請一個堆空間，使用方式和數(shù)組一致。

順序表的類型結(jié)構體

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指針
	int TabelLen; // 存儲動態(tài)數(shù)組里的元素的個數(shù)
} SSTable;

順序查找

步驟

1. 初始化，申請堆空間；并且生成隨機數(shù)，打印順序表
2. for循環(huán)查找

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指針, 申請地址存入elem;
    int TabelLen; // 存儲動態(tài)數(shù)組里的元素的個數(shù)
}SSTable;

// 初始化
void initSSTable(SSTable &ST, int len){ST.TabelLen=len;
    // malloc申請空間
    ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.TabelLen);
    srand(time(NULL)); // 隨機數(shù)生成,方便測試
    for (int i = 0; i< ST.TabelLen; i++) {ST.elem[i] = rand() % 100;
    }
}

// 打印數(shù)組
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、折半查找 原理

折半查找又稱為二分查找，僅適用于有序的順序表
基本思想【在折半查找時用到循環(huán)】
例如：1 12 34 56 66 72 73 81 92 94這10個數(shù)字，找其中任意一個數(shù)(假設為34)

• 用第一個數(shù)字的下標與最后一個數(shù)字的下標相加再除以2，得到66
• 用66和34作比較，如果相等，直接返回存儲位置，如果不等，判斷在除去中間元素的前半部分還是后半部分，(因為是題目中為升序，34<66所以在前半部分)
• 再次進行二分查找，(0+3)/2=1.5; 取1 得到12
• 用12和34進行比較，再次進行折半查找，直至找到為止。
• 如果沒有找到，返回錯誤信息

結(jié)構體

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

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

buf:數(shù)組的起始地址，也可以是指針
num:數(shù)組中的元素個數(shù)
size:數(shù)組中每個元素所占空間的大小
compare:比較規(guī)則，需要自己寫一個函數(shù)，返回int類型，在qsort中調(diào)用
int (*compare)(const void *, const void *)函數(shù)指針，傳遞一個行為給一個函數(shù)。
qsort只能用來排數(shù)組,規(guī)定如果left指針指向的值大于right指針指向的值，返回正值，反之返回負值，相等返回0

步驟

1. 初始化，申請堆空間；并且生成隨機數(shù)
2. 使用qsort進行排序，排序完畢后，打印
3. 輸入要查找的元素存入key中
4. 通過二分查找找的對應的key值，找到輸出位置，沒找到輸出未找到

#include#include#includetypedef int ElemType;
typedef struct {ElemType *elem; // 整型指針, 申請地址存入elem;
    int TabelLen; // 存儲動態(tài)數(shù)組里的元素的個數(shù)
}SSTable;
// 打印數(shù)組
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)); // 隨機數(shù)生成,方便測試
    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;
    }
}
// 函數(shù)名存的是函數(shù)的入口地址，也是一個指針
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;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：(七)數(shù)據(jù)結(jié)構--查找算法-創(chuàng)新互聯(lián)
本文地址：http://weahome.cn/article/ddcdjd.html