㈠ C語言編寫數據結構查找演算法
實驗五 查找的實現
一、 實驗目的
1．通過實驗掌握查找的基本概念；
2．掌握順序查找演算法與實現；
3．掌握折半查找演算法與實現。
二、 實驗要求
1． 認真閱讀和掌握本實驗的參考程序。
2． 保存程序的運行結果，並結合程序進行分析。
三、 實驗內容
1、建立一個線性表，對表中數據元素存放的先後次序沒有任何要求。輸入待查數據元素的關鍵字進行查找。為了簡化演算法，數據元素只含一個整型關鍵字欄位，數據元素的其餘數據部分忽略不考慮。建議採用前哨的作用，以提高查找效率。
2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字利用折半查找方法進行查找。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。
一、順序查找
順序查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請輸入您想輸入的%d個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{
i++;
}
if(i==s->length)
{
printf("該表中沒有您要查找的數據！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
順序查找的運行結果：
二、折半查找
折半查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請由大到小輸入%d個您想輸入的個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("該表中沒有您要查找的數據!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。
㈡ 數據結構折半查找演算法的方法
041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也稱折半查找法) int index=0; // 當前數組的首元素下標 int current=n-1; // 數組當前的大小 int k; // 當前數組中間的數的下標 while (index<current) { // 開始二分法查找 k=(index+current)/2; // 除以2代表得到當前數組中間的數的下標 if(a[k]==_value) return k; // 返回要查找的值_value所在的下標 // 否則比較要查找的值_value是在折半後的前半部分還是後半部分 if(a[k]<_value){ // 說明要查找的值在折半後的後半部分 index=k+1; // 令index指向後半部分數組的首元素 } else{ // 說明要查找的值在折半後的前半部分 current=k-1; // 令current等於前半部分數組的長度 } } return -1; // 返回-1代表沒有查找到該值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一組數組必須是有序數對(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在數組中對應的下標是:%d\n",Dichotomy(arr,87,5)); else printf("沒有找到指定的值\n");}// 用一句話概括二分法(折半查找法)的思想就是:在一組有序對數組中反復折半後得到中間數組的下標,然後再進行是否與要查找的值相等,若相等則返回當前要查找的值的下標。 那麼，上面的代碼的注釋與下面一一對應，它在執行的結果會產生兩種情況，第一種,不存在。第二種，存在。先來說說第一種情況 不存在： 1.如果給定要查找的值_value大於數組中最大的數,則index不斷增大從而促使while循環終止 2.如果給定要查找的值_value小於數組中最小的數,則current不斷減少從而促使while循環終止(你自己可以動手在紙上畫一個數組,然後思路跟著代碼走就會知道或設單步調試亦可) 第二種情況 存在： 1.要查找的數_value正好是在數組中間.那麼就執行了一次循環,當然這也是最理想的效果. 否則反復執行2和3:2.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果小於中間的數則說明_value應該在數組中間的前半部分,那麼current=k-1(即令current等於前半部分的長度),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止. 3.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果大於中間的數則說明_value應該在數組中間的後半部分,那麼index=k+1(即令index指向後半部分的第一個下標),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止.
㈢ 數據結構的查找方法
1.順序查找
2.二分查找
3.分塊查找
4.二叉排序樹查找
5.哈希查找
㈣ 數據結構查找演算法這么多有什麼用
程序本身就是這兩者構成，什麼框架都是建立在這兩者之上，
現在的人大多是直接學C#，JAVA，特別是C#，一上來什麼東西都給你封裝，
很多細節程序員是不會知道，什麼東西簡單一拖OK。
不過這些語言的什麼LIST啊，ARRAYLIST等等這些就是一種數據結構，
定義好這形形色色的數據你用起來不覺得更方便了嗎？
我的水平比較低，目前的理解是學習數據結構主要是學習演算法，演算法就是提高你
解決問題的能力，還有就是組織數據的思維方式方法。
我剛完成數據結構學習的第一階段，感覺還是挺有趣的，學到不少知識，最起碼
比WINFORM的拖拖拉拉有趣多了。
㈤ 數據結構 順序查找演算法和折半查找演算法
//順序查找
int findKey(int array[], int length, int key)
{
for (int i = 0; i < length; i++)
if (array[i] == key)
return i;
return -1;
}
//折半查找
int findKeybyBinary(int array[], int low, int high, int key)
{
if (low > high)
return -1;
int mid = (low + high)/2;
if (array[mid] == key)
return mid;
else if (array[mid] < key)
return findbyBinary(array,mid + 1,high, key);
else
return findbyBinary(array,low,mid - 1, key);
}
查找key=41的演算法： 比較次數：3次
void main ()
{
int array[] = {8，15，19，26，33，41，47，52，64，90};
printf("the pos of 41 is %d \n", findKeybyBinary(array, 0, 9, 41));
}
查找key=35的演算法： 比較次數：6次
void main ()
{
int array[] = {12，76，29，15，62，35，33，89，48，20};
printf("the pos of 41 is %d \n", findKey(array, 10, 35));
}
㈥ 【數據結構】幾種重要的查找演算法。
恩你是要問什麼?
順序查找就是按順序查找,復雜度O(n)
二分查找的前提是數據是有序的 一次復雜度O(logn)
例如在數組 A: 1 3 5 7 8 10 12 中
如果要找 10
我們先看中間的數是 7, 10比7大,那麼繼續在右側二分尋找,這是一個遞歸的過程.
偽代碼:
bool find(int L,int R,int What_You_Want) {
if (L > R) return false;
int mid = (L + R) / 2
if (A[mid] == What_You_Want) return true;
else if (A[mid] > What_You_Want) return find(L,mid - 1,What_You_Want);
else return find(mid + 1, R, What_You_Want);
}
二叉搜索樹的原理與二分查找相同
㈦ 數據結構中有哪些查找演算法
和二分查找性能接近的：既然可以二分查找，那麼關鍵字肯定可以滿足全序關系。那麼可以用二叉查找樹，一般的就是平攤O(logn),最壞O(n)。如果用平衡樹，如AVL,Treap,Splay等等，可以做到保持O(logn)的界。
比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)的。這個你最好系統學習一下，尤其是字元串的Hash函數。
㈧ 演算法與數據結構 索引查找的實現
二分查找法、哈希查找法、二叉排序樹查找法等各種查找演算法。1. 線性表上的查找： 主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。 2.樹表上的查找： 樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密。 二叉排序樹，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定。 B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。 3.基本哈希表的查找演算法： 哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。堆排序屬於選擇排序類型的排序，是一樹形選擇排序。堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
vae.la
㈨ 數據結構中，查找演算法最優的是哪一種
折半查找法的平均查找長度隨n增大而呈現對數增長趨勢，因此折半查找法為最優查找演算法
㈩ 數據結構課程設計,綜合查找演算法
#include <stdio.h>
typedef int KeyType;
typedef struct{
KeyType key;
int maths;
int english;
}ElemType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct {
ElemType *elem;
int length;
}SSTable;
int Search_Seq(SSTable ST,KeyType key)
{
int i;
ST.elem[0].key=key;
for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
return i;
}
int Search_Bin(SSTable ST,KeyType key)
{
int low,mid,high;
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1;
}
}
getdata(SSTable * t)
{
FILE *fp;
int i=1;
fp=fopen("stu.txt","r");
fscanf(fp,"%d",&(t->length));
while(i<=t->length)
{
fscanf(fp,"%d %d %d",&(t->elem[i].key),
&(t->elem[i].maths),&(t->elem[i].english) );
i++;
}
fclose(fp);
}
main()
{
ElemType stu[50];
SSTable class;
int i,j,k;
long time;
class.elem=stu;
getdata(&class);
printf("This class has %d students.\n",class.length);
printf("Input stuno you want search:\n");
scanf("%d",&k);
i=Search_Seq(class,k);
j=Search_Bin(class,k);
printf("Maths English\n");
printf("%d %d\n",class.elem[i].maths,class.elem[i].english);
printf("%d %d\n",class.elem[j].maths,class.elem[j].english);
for(i=1;i<=4;i++)
{j=stu[i].maths+stu[i].english;
printf("%d\n",j);
}
}
二叉排序樹
示例
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}