Ⅰ 編寫順序查找演算法的程序
查找演算法集：順序查找、二分查找、插值查找、動態查找(數組實現、鏈表實現)
// search.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "LinkTable.h"
#define MAX_KEY 500
//------------------------------數組實現部分----------------------------------
/**//*
無序數組順序查找演算法函數nsq_Order_Search<用數組實現>
參數描述：
int array[] :被查找數組
int n :被查找數組元素個數
int key :被查找的關鍵值
返回值:
如果沒有找到: nsq_Order_Search = -1
否則: nsq_Order_Search = key數組下標
*/
int nsq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = key;
/**//*for循環後面的分號必不可少*/
for(i=0;key!=array[i];i++);
return(i<n?i:-1);
}
/**//*
有序數組順序查找演算法函數sq_Order_Search<用數組實現>
參數描述：
int array[] :被查找數組
int n :被查找數組元素個數
int key :被查找的關鍵值
返回值:
如果沒有找到: sq_Order_Search = -1
否則: sq_Order_Search = key數組下標
*/
int sq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = MAX_KEY;
/**//*for循環後面的分號必不可少*/
for(i=0;key>array[i];i++);
if(i<n && array[i] == key)
return(i);
else
return(-1);
}
/**//*
有序數組二分查找演算法函數sq_Dichotomy_Search0<用數組實現>
參數描述：
int array[] :被查找數組
int n :被查找數組元素個數
int key :被查找的關鍵值
返回值:
如果沒有找到: sq_Dichotomy_Search0 = -1
否則: sq_Dichotomy_Search0 = key數組下標
*/
int sq_Dichotomy_Search0(int array[],int n,int key)
...{
int low,high,mid;
low = 0;
high = n - 1;
while(low<=high)
...{
mid = (high+low)/2;
if(array[mid] == key)
return(mid);
/**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/
/**//*否則,在[low,mid-1]*/
if(key > array[mid])
low = mid + 1;
else
high = mid - 1;
}
return(-1);
}
/**//*
有序數組插值查找演算法函數sq_Dichotomy_Search1<用數組實現>
(插值查找演算法是二分查找演算法的改進)
參數描述：
int array[] :被查找數組
int n :被查找數組元素個數
int key :被查找的關鍵值
返回值:
如果沒有找到: sq_Dichotomy_Search1 = -1
否則: sq_Dichotomy_Search1 = key數組下標
*/
int sq_Dichotomy_Search1(int array[],int n,int key)
...{
int low,high, //二分數組的上,下標
pos; //查找碼的大致(估算)位置
low = 0;
high = n-1;
while(low <= high)
...{
pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;
/**//*找到關鍵值,中途退出*/
if(key == array[pos])
return(pos);
if(key > array[pos])
low = pos + 1;
else
high = pos - 1;
}
/**//*沒有找到,返回-1*/
return(-1);
}
//------------------------------數組實現部分----------------------------------
//------------------------------鏈表實現部分----------------------------------
/**//*
無序鏈表順序查找演算法函數nlk_Order_Serach<用鏈表實現>
[查找思想:遍歷鏈表的所有節點]
參數描述：
Node *head :被查找鏈表的首指針
int key :被查找的關鍵值
返回值:
如果沒有找到: nlk_Order_Serach = NULL
否則: nlk_Order_Serach = 鍵值為key的節點的指針
*/
Node *nlk_Order_Serach(Node *head,int key)
...{
for(;head!=NULL && head->data != key;head = head->link);
return(head);
}
/**//*
有序鏈表順序查找演算法函數lk_Order_Serach<用鏈表實現>
[查找思想:依次遍歷鏈表的節點,發現節點不在key的范圍時提前結束查找]
參數描述：
Node *head :被查找鏈表的首指針
int key :被查找的關鍵值
返回值:
如果沒有找到: lk_Order_Serach = NULL
否則: lk_Order_Serach = 鍵值為key的節點的指針
*/
Node *lk_Order_Search(Node *head,int key)
...{
for(;head!=NULL && head->data < key;head=head->link);
/**//*當遍歷指針為NULL或沒有找到鍵值為key的節點,返回NULL(表明沒有找到)*/
/**//*否則,返回head(表明已經找到)*/
return(head==NULL || head->data != key ? NULL : head);
}
/**//*
有序鏈表動態查找演算法函數lk_Dynamic_Search<用鏈表實現>
[查找思想:依次遍歷鏈表的節點,發現節點不在key的范圍時提前結束查找]
參數描述：
Node *head: 被查找鏈表的首指針
Node **p; 鍵值為key的節點的前驅指針(回傳參數)
Node **q: 鍵值為key的節點指針(回傳參數)
int key : 被查找的關鍵值
注意:
當 *p == NULL 且 *q != NULL,鏈表的首節點鍵值為key
當 *p != NULL 且 *q != NULL,鏈表的中間(非首,尾)節點鍵值為key
當 *p != NULL 且 *q == NULL,鏈表的尾節點鍵值為key
當 *p == NULL 且 *q == NULL,鏈表是空鏈表
*/
void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)
...{
Node *pre,*cur;
pre = NULL;
cur = head;
for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)
*p = pre;
*q = cur;
}
/**//*
有序鏈表動態插入演算法函數lk_Dynamic_Insert<用鏈表實現>
參數描述：
Node *head: 被插入鏈表的首指針
int key : 被插入的關鍵值
返回值:
lk_Dynamic_Search = 插入鍵值為key的節點後的鏈表首指針
*/
Node *lk_Dynamic_Insert(Node *head,int key)
...{
Node
*x, //插入節點的前驅節點
*y, //插入節點的後續節點
*p; //插入的節點
p = (Node *)malloc(sizeof(Node));
p->data = key;
p->link = NULL;
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
...{
p->link = x;
head = p;
}
else
...{
p->link = x->link;
x->link = p;
}
ListLinkTable(head,"插入節點");
return(head);
}
/**//*
有序鏈表動態刪除演算法函數lk_Dynamic_Delete<用鏈表實現>
參數描述：
Node *head: 被刪除鏈表的首指針
int key : 被刪除的關鍵值
返回值:
lk_Dynamic_Delete = 刪除鍵值為key的節點後的鏈表首指針
*/
Node *lk_Dynamic_Delete(Node *head,int key)
...{
Node *x, //刪除節點的前驅節點
*y; //刪除的節點
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
/**//*因為x=NLLL時,y指向首指針*/
head = y->link;
else
x->link = y->link;
free(y);
ListLinkTable(head,"刪除節點");
return(head);
}
//------------------------------鏈表實現部分----------------------------------
int main(int argc, char* argv[])
...{
Node *head;
//Node *p,*x,*y;
int KEY;
int count,i;
//int result;
KEY = 11;
//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");
//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);
//printf("查找結果是：數組[%d] = %d ",result,TestArray2[result]);
head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);
ListLinkTable(head,"原始");
/**//*
p = lk_Order_Search(head,KEY);
if(p==NULL)
printf(" 查找結果是：指定鏈表中沒有[數據域 = %d]的節點! ",KEY);
else
printf(" 查找結果是：節點.Data = %d 節點.Link = %d 節點.Addr = %d ",p->data,p->link,p);
*/
printf("輸入插入節點的個數： ");
scanf("%d",&count);
for(i=0;i<count;i++)
...{
printf("輸入插入節點的數據域： ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
...{
printf("輸入刪除節點的數據域： ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 應用程序正在運行...... ");
return 0;
}
Ⅱ 順序查找演算法和折半查找演算法的時間復雜度各是多少
假設對n個元素的折半查找需要消耗的時間為t(n)。容易知道：
如果n
=
1，則t(n)
=
c1
如果n
>
1，則t(n)
=
t(n/2)
+
c2
其中n/2需要取整，c1、c2都是常數
對於正整數n，可以有：
t(n)
=
t(n/2)
+
c2
=
t(n/4)
+
2*c2
=
t(n/8)
+
4*c2
=
...
=
t(n/(2的k次方))
+
k*c2
一直推演下去，直到n/(2的k次方)等於1，也就是k
=
log2(n)，此時等式變為：
t(n)
=
t(1)
+
k*c2
=
c1
+
log2(n)*c2
於是時間復雜度為log2(n)。注意log2(n)和log(n)其實是同樣的復雜度，因為它們之間僅僅差了一個常量系數而已。
這個是不嚴格的推導，因為沒有考慮整數除以2之後可能有餘數的情況。但即使有餘數，也是不影響時間復雜度的。
Ⅲ 求求求！！！計算機懂行的人解答！！題目:用偽代碼寫順序查找演算法，包含目標找到或找不到時演算法的終止條
functioninOrderSearch(array[],keyword)
{
i←0
Whilei<=array.length
Ifarray[i]=keyword
Thenreturni
EndIf
i←i+1
EndWhile
returnnotFound
}
Ⅳ 對比順序查找,二分查找和哈希查找演算法,它們各自的特點是什麼
順序查找,二分查找和哈希查找演算法,它們各自的特點是：
1.對比順序查找的特點就是從表的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功;如果到最後一個元素仍沒有目標元素，則查找失敗。
2.二分查找的特點就是從表中間開始查找目標元素。如果找到一致元素，則查找成功。如果中間元素比目標元素小，則仍用二分查找方法查找表的後半部分(表是遞增排列的)，反之中間元素比目標元素大，則查找表的前半部分。
3.哈希演算法的特點是是使用給定數據構造哈希表，然後在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。
Ⅳ 順序查找演算法的時間復雜度是多少吖
順序查找法的平均比較次數為（n+1）/2次，則其時間復雜度就是(n+1)/2，當n->無窮大時，該表達式與n為同階無窮大，記為O(n)，這是高等數學里就有的表示法 。
拓展：
順序查找法定義為假定要從n個整數中查找x的值是否存在，從頭到尾逐個查找，其代碼實現方法可參考網路：http://ke..com/link?url=ADQC6d-aG44ewQH55e1ip96IYHussYf_-n11y4CM6iZaHyz9VTma
Ⅵ 索引順序查找演算法
索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
不知道答案與兄台的問題是否一致，也是網上找的，不對請見諒哈~~
Ⅶ 順序查找法
int seek(int a[10],int key)
{int i;
for(i=0;i<5;i++)
if(key==a[i])
return i;
return -1;
}
main()
{int a[5],i,key,loc;
printf("enter 5 numbers:\n");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
printf("enter key:\n");
scanf("%d",&key);
if(seek(a,key)==-1)
printf("not find!");
else
{loc=seek(a,key);
printf("find and loctiong is:%d",loc);
}
}
你的本意是如果找到則輸出find and loctiong is:%d，但你的程序中，else語句只執行了loc=seek(a,key);而printf("find and loctiong is:%d",loc);則不管有沒有找到都會執行。。。。只是當找到時，輸出的是關鍵字的下標，沒找到時，則輸出一個隨機數，如果不理解的話，歡迎繼續追問~~~
Ⅷ 順序查找法平均查找長度是多少
最好的情況：目標在第一個,一次找到
·····
最壞的情況：目標在最後一個,n次找到
那麼：
平均長度：
（1+2+···+n）/n
=(n(n+1)/2)/n
=(n+1)/2
Ⅸ 用類c描述順序查找演算法
順序查找法就是，把給出的數據，和數組中的每一個數據進行比較，發現相同的數據時，把該數據，在數組中的位置返回回來。
目的是，為了查找到相關的數據位置，然後根據這個位置，進行下一步操作。
這個或許能幫助你更好的解決問題：
http://jingyan..com/article/d169e186aa0d28436711d879.html
Ⅹ 數據結構 順序查找演算法和折半查找演算法
//順序查找
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));
}