查找演算法有序存儲
⑴ 如果數據是有序的,可以採用二分查找演算法以獲得更高的效率對嗎
摘要 二分查找也稱折半查找(Binary Search),它是一種效率較高的查找方法。但是,折半查找要求線性表必須採用順序存儲結構,而且表中元素按關鍵字有序排列。
⑵ 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;
}
折半查找運行結果:
三、實驗總結:
該實驗使用了兩種查找數據的方法(順序查找和折半查找),這兩種方法的不同之處在於查找方式和過程不同,線性表的創建完全相同,程序較短,結果也一目瞭然。
⑶ 什麼是查找法
演算法思想:
將數列按有序化(遞增或遞減)排列,查找過程中採用跳躍式方式查找,即先以有序數列的中點位置為比較對象,如果要找的元素值小於該中點元素,則將待查序列縮小為左半部分,否則為右半部分。通過一次比較,將查找區間縮小一半。
折半查找是一種高效的查找方法。它可以明顯減少比較次數,提高查找效率。但是,折半查找的先決條件是查找表中的數據元素必須有序。
演算法步驟描述:
step1 首先確定整個查找區間的中間位置
mid = ( left + right )/ 2
step2 用待查關鍵字值與中間位置的關鍵字值進行比較;
若相等,則查找成功
若大於,則在後(右)半個區域繼續進行折半查找
若小於,則在前(左)半個區域繼續進行折半查找
Step3 對確定的縮小區域再按折半公式,重復上述步驟。最後,得到結果:要麼查找成功, 要麼查找失敗。
折半查找的存儲結構採用一維數組存放。
折半查找演算法舉例
對給定數列(有序){ 3,5,11,17,21,23,28,30,32,50},按折半查找演算法,查找關鍵字值為30的數據元素。
折半查找的演算法討論:
優點: ASL≤log2n,即每經過一次比較,查找范圍就縮小一半。經log2n 次計較就可以完成查找過程。
缺點:因要求有序,所以要求查找數列必須有序,而對所有數據元素按大小排序是非常費時的操作。另外,順序存儲結構的插入、刪除操作不便利。
考慮:能否通過一次比較拋棄更多的部分(即經過一次比較,使查找范圍縮得更小),以達到提高效率的目的。……?
可以考慮把兩種方法(順序查找和折半查找)結合起來,即取順序查找簡單和折半查找高效之所長,來達到提高效率的目的?實際上這就是分塊查找的演算法思想。
例如:[問題分析] 由於數據按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java風格的代碼舉例:
//使用折半法進行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能說明
雖然二分查找的效率高,但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使採用高效率的排序方法也要花費 O(n lg n) 的時間。
二分查找只適用順序存儲結構。為保持表的有序性,在順序結構里插入和刪除都必須移動大量的結點。因此,二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表。
對那些查找少而又經常需要改動的線性表,可採用鏈表作存儲結構,進行順序查找。鏈表上無法實現二分查找
二分查找的C#實現代碼:
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失敗
}
static void Main(string[] args)
{
Console.WriteLine("請輸入10個遞增數字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("數字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("請輸入一個你要查找的數字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分塊查找又索引查找,它主要用於「分塊有序」表的查找。所謂「分塊有序」是指將線性表L(一維數組)分成m個子表(要求每個子表的長度相等),且第i+1個子表中的每一個項目均大於第i個子表中的所有項目。「分塊有序」表應該包括線性表L本身和分塊的索引表A。因此,分塊查找的關鍵在於建立索引表A。
(1)建立索引表A(二維數組)
索引表包括兩部分:關鍵字項(子表中的最大值)和指針項(子表的第一項在線性表L中位置)
索引表按關鍵字有序的。
例如:線性表L(有序)為:1 2 3 4 5 6 7 8 9 10 11 12
分成m=3個子表:{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A:二維數組:第一列為每個子表的最大值 ,第二列為每個子表的起始地址
即: 4 0
8 4
12 8
(2)利用索引表A,確定待查項X所在的子表(塊)。
(3)在所確定的子表中可以用「折半查找」法搜索待查項X;若找到則輸出X;否則輸出未找到信息。
⑷ 順序查找法適用於查找順序存儲或鏈式存儲的線性表
對。
鏈式存儲的線性表的存取機制是順序的,要想查找位置為i的元素必須採用順序查找法;
順序存儲的線性表的存取機制是隨機的,要想查找位置為i的元素直接用下標法就可以了。
如果要查找元素e在線性表中的位置那麼對這兩種存儲結構而言,必須採用順序查找法了。
(4)查找演算法有序存儲擴展閱讀:
線性表結構特點:
1、均勻性:雖然不同數據表的數據元素可以是各種各樣的,但對於同一線性表的各數據元素必定具有相同的數據類型和長度。
2、有序性:各數據元素在線性表中的位置只取決於它們的序號,數據元素之前的相對位置是線性的,即存在唯一的「第一個「和「最後一個」的數據元素,除了第一個和最後一個外,其它元素前面均只有一個數據元素(直接前驅)和後面均只有一個數據元素(直接後繼)。
⑸ 程序設計問題,查找演算法性能研究,幫下忙謝啦
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
static const int ARRAY_MAX = 10000;
typedef int DataType;
class SequentialStorage
{
public:
DataType data[ARRAY_MAX];
int top;
SequentialStorage()
{
top = -1;
}
void insertData(DataType data)
{
if(top == ARRAY_MAX-1)
return;
this->data[++top] = data;
}
int find(DataType data)
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
};
class OrderlySequenceStorage
{
public:
DataType data[ARRAY_MAX];
int top;
OrderlySequenceStorage()
{
top = -1;
}
void insertData(DataType data)//插入排序
{
if(top == ARRAY_MAX-1)
return;
int i = top;
while(this->data[i] > data&&i != -1)
{
this->data[i+1] = this->data[i];
i--;
}
this->data[i+1] = data;
top++;
}
int find(DataType data)//普通查找
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
int find2(DataType data)//二分法
{
if(this->data[0] > data||this->data[top] < data)
return -1;
if(this->data[0] == data)
return 0;
if(this->data[top] == data)
return top;
int a = 0;
int b = top;
while(true)
{
if(a == b-1)
return -1;
if(this->data[(a+b)/2] == data)
return (a+b)/2;
else if(this->data[(a+b)/2] < data)
a = (a+b)/2;
else
b = (a+b)/2;
}
}
};
typedef struct node
{
DataType data;
struct node *pNext;
}LLSNode;
class LinkedListStorage
{
public:
LLSNode *pHead;
LinkedListStorage()
{
pHead = NULL;
}
void insertData(DataType data)
{
LLSNode *p = (LLSNode *)malloc(sizeof(LLSNode));
p->data = data;
p->pNext = pHead;
pHead = p;
}
LLSNode *find(DataType data)
{
LLSNode *p = pHead;
while(p)
{
if(p->data == data)
return p;
p = p->pNext;
}
return NULL;
}
};
typedef struct node2
{
DataType data;
struct node2 *lchild,*rchild;
}BSTNode;
class BinarySortTree
{
public:
BSTNode *pRoot;
BinarySortTree()
{
pRoot = NULL;
}
void insertData(DataType data)
{
BSTNode *f,*p = pRoot;
while(p)
{
f = p;
if(data < p->data)
p = p->lchild;
else
p = p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
if(pRoot == NULL)
pRoot = p;
else
if(data < f->data)
f->lchild = p;
else
f->rchild = p;
}
BSTNode *find(DataType data)
{
if(pRoot == NULL)
return NULL;
else
return recursion(data,pRoot);
}
BSTNode *recursion(DataType data,BSTNode *p)
{
if(data == p->data||p == NULL)
return p;
else if(data < p->data)
return recursion(data,p->lchild);
else
return recursion(data,p->rchild);
}
void print()
{
if(pRoot != NULL)
printR(pRoot);
}
void printR(BSTNode *p)
{
if(p->lchild != NULL)
printR(p->lchild);
printf("%d\t",p->data);
if(p->rchild != NULL)
printR(p->rchild);
}
};
class CPUTime
{
public:
_int64 getCPUCycleCount(void)
{
_asm _emit 0x0F
_asm _emit 0x31
}
long long arr[1000];
int count;
long long lastCPUCycleCount;
int randCount;
CPUTime()
{
for(int i = 0;i < 1000;i++)
arr[i] = 0;
count = -1;
lastCPUCycleCount = getCPUCycleCount();
randCount = 0;
}
void setTimePoint()
{
arr[++count] = getCPUCycleCount()-lastCPUCycleCount;
lastCPUCycleCount = getCPUCycleCount();
}
int rand()
{
randCount++;
int temp = getCPUCycleCount()%20000;
return (temp*(randCount+temp))%10007;
}
};
int main()
{
SequentialStorage ss;
OrderlySequenceStorage oss;
LinkedListStorage lls;
BinarySortTree bst;
DataType temp1;
CPUTime cpuTime;
for(int i = 0;i < 2000;i++)
{
temp1 = cpuTime.rand();
ss.insertData(temp1);
oss.insertData(temp1);
lls.insertData(temp1);
bst.insertData(temp1);
}
DataType temp[7];
for(int i = 0;i < 7;i++)
temp[i] = ss.data[cpuTime.rand()%2000];
cpuTime.setTimePoint();
for(int i = 0;i < 7;i++)
{
ss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find2(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
lls.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
bst.find(temp[i]);
cpuTime.setTimePoint();
}
int count = 1;
printf("各項存儲結構查找已存在數據的時間(cpu周期):\n");
printf("儲存方式\t\t數據1\t數據2\t數據3\t數據4\t數據5\t數據6\t平均\n");
int a[9];
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("順序存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序順序存儲(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序順序存儲(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("鏈表存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("二叉排序樹存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
system("pause");
}
//我按照課題的要求寫的c++具體實現的代碼,樓主可以編譯運行著試試,你可以參考一下
//我這搜索的是儲存結構里已存在的數據,你也可以按題目的要求用隨機生成的數據
//樓主留下qq吧,我等會把流程圖發給你
//至於其他的,樓主還是自己試著寫寫看吧
⑹ 查找演算法的作用
查找就是在一個數據集合里查找到你需要的數據,查找演算法就是在查找過程中使用的演算法。查找演算法有好多,最基礎的就是線性表查找。
因為提到了演算法,所以需要注意的是時間復雜度跟空間復雜度,進而涉及到數據的存儲方式,比如數組,鏈表,矩陣,樹,圖等等數據結構,這些數據結構可以幫助你降低演算法的復雜度。
如果有興趣,隨便找本數據結構書翻翻,裡面或多或少都會有講解。用關鍵字標識一個數據元素,查找時根據給定的某個值,在表中確定一個關鍵字的值等於給定值的記錄或數據元素。在計算機中進行查找的方法是根據表中的記錄的組織結構確定的。順序查找也稱為線形查找,從數據結構線形表的一端開始,順序掃描,依次將掃描到的結點關鍵字與給定值k相比較,若相等則表示查找成功;若掃描結束仍沒有找到關鍵字等於k的結點,表示查找失敗。二分查找要求線形表中的結點按關鍵字值升序或降序排列,用給定值k先與中間結點的關鍵字比較,中間結點把線形表分成兩個子表,若相等則查找成功;若不相等,再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表,這樣遞歸進行,直到查找到或查找結束發現表中沒有這樣的結點。分塊查找也稱為索引查找,把線形分成若干塊,在每一塊中的數據元素的存儲順序是任意的,但要求塊與塊之間須按關鍵字值的大小有序排列,還要建立一個按關鍵字值遞增順序排列的索引表,索引表中的一項對應線形表中的一塊,
⑺ 索引順序查找演算法
索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是:首先根據給定的索引值K1,在索引表上查找出索引值等於KI的索引項,以確定對應予表在主表中的開始位置和長度,然後再根據給定的關鍵字K2,茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時,若表是順序存儲的有序表,則既可進行順序查找,也可進行二分查找,否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表,數組B是具有inde)dist類型的在主表A 上建立的一個索引表,m為索引表B的實際長度,即所含的索引項的個數,KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中,不僅便於查找單個元素,而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時,只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素,所以整個查找過程的時間復雜度為,若不是採用索引存儲,而是採用順序存儲,即使把它組織成有序表而進行二分查找時,索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置,則索引存儲也便於進行插入和刪除運算,因為其運算過程只涉及到索引表和相應的子表,只需要對相應子表中的元素進行比較和移動,與其它任何子表無關,不像順序表那樣需涉及到整個表中的所有元素,即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法,也同查找演算法類似,其過程為:首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表,確定出對應的子表,然後再根據待插入或刪除元素的關鍵字,在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲,就是鏈接存儲,所以對它們做插入或刪除操作都是很簡單的。
不知道答案與兄台的問題是否一致,也是網上找的,不對請見諒哈~~
⑻ 二分法查找為什麼只適用於順序存儲
舉個例子,在1 2 6 4 5 7 8 9 10中,你要用二分法查找6,你得先把6跟中間的5比較,6很明顯大於5,所以就只能在5 7 8 9 10中查找,這樣很明顯找不到,所以二分法必須要求用於順序排列的數,如果不是順序排列的,二分法就完全沒有意義
⑼ 查找演算法性能研究(順序存儲、有序順序存儲、鏈表存儲、二叉排序樹存儲)
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
static const int ARRAY_MAX = 10000;
typedef int DataType;
class SequentialStorage
{
public:
DataType data[ARRAY_MAX];
int top;
SequentialStorage()
{
top = -1;
}
void insertData(DataType data)
{
if(top == ARRAY_MAX-1)
return;
this->data[++top] = data;
}
int find(DataType data)
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
};
class OrderlySequenceStorage
{
public:
DataType data[ARRAY_MAX];
int top;
OrderlySequenceStorage()
{
top = -1;
}
void insertData(DataType data)//插入排序
{
if(top == ARRAY_MAX-1)
return;
int i = top;
while(this->data[i] > data&&i != -1)
{
this->data[i+1] = this->data[i];
i--;
}
this->data[i+1] = data;
top++;
}
int find(DataType data)//普通查找
{
for(int i = 0;i <= top;i++)
{
if(this->data[i] == data)
return i;
}
return -1;
}
int find2(DataType data)//二分法
{
if(this->data[0] > data||this->data[top] < data)
return -1;
if(this->data[0] == data)
return 0;
if(this->data[top] == data)
return top;
int a = 0;
int b = top;
while(true)
{
if(a == b-1)
return -1;
if(this->data[(a+b)/2] == data)
return (a+b)/2;
else if(this->data[(a+b)/2] < data)
a = (a+b)/2;
else
b = (a+b)/2;
}
}
};
typedef struct node
{
DataType data;
struct node *pNext;
}LLSNode;
class LinkedListStorage
{
public:
LLSNode *pHead;
LinkedListStorage()
{
pHead = NULL;
}
void insertData(DataType data)
{
LLSNode *p = (LLSNode *)malloc(sizeof(LLSNode));
p->data = data;
p->pNext = pHead;
pHead = p;
}
LLSNode *find(DataType data)
{
LLSNode *p = pHead;
while(p)
{
if(p->data == data)
return p;
p = p->pNext;
}
return NULL;
}
};
typedef struct node2
{
DataType data;
struct node2 *lchild,*rchild;
}BSTNode;
class BinarySortTree
{
public:
BSTNode *pRoot;
BinarySortTree()
{
pRoot = NULL;
}
void insertData(DataType data)
{
BSTNode *f,*p = pRoot;
while(p)
{
f = p;
if(data < p->data)
p = p->lchild;
else
p = p->rchild;
}
p = (BSTNode *)malloc(sizeof(BSTNode));
p->data = data;
p->lchild = NULL;
p->rchild = NULL;
if(pRoot == NULL)
pRoot = p;
else
if(data < f->data)
f->lchild = p;
else
f->rchild = p;
}
BSTNode *find(DataType data)
{
if(pRoot == NULL)
return NULL;
else
return recursion(data,pRoot);
}
BSTNode *recursion(DataType data,BSTNode *p)
{
if(data == p->data||p == NULL)
return p;
else if(data < p->data)
return recursion(data,p->lchild);
else
return recursion(data,p->rchild);
}
void print()
{
if(pRoot != NULL)
printR(pRoot);
}
void printR(BSTNode *p)
{
if(p->lchild != NULL)
printR(p->lchild);
printf("%d\t",p->data);
if(p->rchild != NULL)
printR(p->rchild);
}
};
class CPUTime
{
public:
_int64 getCPUCycleCount(void)
{
_asm _emit 0x0F
_asm _emit 0x31
}
long long arr[1000];
int count;
long long lastCPUCycleCount;
int randCount;
CPUTime()
{
for(int i = 0;i < 1000;i++)
arr[i] = 0;
count = -1;
lastCPUCycleCount = getCPUCycleCount();
randCount = 0;
}
void setTimePoint()
{
arr[++count] = getCPUCycleCount()-lastCPUCycleCount;
lastCPUCycleCount = getCPUCycleCount();
}
int rand()
{
randCount++;
int temp = getCPUCycleCount()%20000;
return (temp*(randCount+temp))%10007;
}
};
int main()
{
SequentialStorage ss;
OrderlySequenceStorage oss;
LinkedListStorage lls;
BinarySortTree bst;
DataType temp1;
CPUTime cpuTime;
for(int i = 0;i < 2000;i++)
{
temp1 = cpuTime.rand();
ss.insertData(temp1);
oss.insertData(temp1);
lls.insertData(temp1);
bst.insertData(temp1);
}
DataType temp[7];
for(int i = 0;i < 7;i++)
temp[i] = ss.data[cpuTime.rand()%2000];
cpuTime.setTimePoint();
for(int i = 0;i < 7;i++)
{
ss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
oss.find2(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
lls.find(temp[i]);
cpuTime.setTimePoint();
}
for(int i = 0;i < 7;i++)
{
bst.find(temp[i]);
cpuTime.setTimePoint();
}
int count = 1;
printf("各項存儲結構查找已存在數據的時間(cpu周期):\n");
printf("儲存方式\t\t數據1\t數據2\t數據3\t數據4\t數據5\t數據6\t平均\n");
int a[9];
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("順序存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序順序存儲(普通)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("有序順序存儲(二分法)\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("鏈表存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
for(int i = 1;i < 8;i++)
a[i] = (int)cpuTime.arr[count++];
a[8] = (a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7])/7;
printf("二叉排序樹存儲\t\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[8]);
system("pause");
}
//我按照課題的要求寫的c++具體實現的代碼,樓主可以編譯運行著試試,你可以參考一下
//我這搜索的是儲存結構里已存在的數據,你也可以按題目的要求用隨機生成的數據
//樓主留下qq吧,我等會把流程圖發給你
//至於其他的,樓主還是自己試著寫寫看吧
另外,站長團上有產品團購,便宜有保證
⑽ 查找演算法的二分查找
二分查找又稱折半查找,它是一種效率較高的查找方法。
【二分查找要求】:1.必須採用順序存儲結構2.必須按關鍵字大小有序排列。
【優缺點】折半查找法的優點是比較次數少,查找速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。因此,折半查找方法適用於不經常變動而查找頻繁的有序列表。【演算法思想】首先,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。重復以上過程,直到找到滿足條件的記錄,使查找成功,或直到子表不存在為止,此時查找不成功。【演算法復雜度】假設其數組長度為n,其演算法復雜度為o(log(n))
下面提供一段二分查找實現的偽代碼:
BinarySearch(max,min,des)
mid-des thenmax=mid-1elsemin=mid+1return max
折半查找法也稱為二分查找法,它充分利用了元素間的次序關系,採用分治策略,可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是,將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/2]則找到x,演算法終止。如 果xa[n/2],則我們只要在數組a的右 半部繼續搜索x。