静态查找算法代码（静态查找算法代码怎么写）

今天给各位分享静态查找算法代码的知识，其中也会对静态查找算法代码怎么写进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、C语言顺序查找程序
• 2、顺序存储结构怎样构造含n个元素的静态查找表
• 3、数据结构与算法-静态最优查找树
• 4、紧急求助C语言描述的数据结构,中的有一个查找方式是用一个虚拟的哨兵元素来优化算法
• 5、顺序表的顺序查找和二分查找？
• 6、请教：用JAVA编一个基本查找算法效率比较的程序。

C语言顺序查找程序

//顺序查找

//思路:从表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

#include stdio.h

#include stdlib.h

#include math.h

#include time.h

#define N 10

typedef int DataType;//定义比较的元素类型

//静态查找表的顺序存储结构

typedef struct{

DataType * data;//数据元素存储空间基址，按实际长度分配，0号单元留空

//建表时按实际长度分配，0 号单元留空

int length;//表长度

}SSTable;

//创建一个静态表，内容为20以内的随机数

void createST(SSTable* ST,int n){

int i;

time_t t;

if(ST!=NULL){

ST-data=(DataType*)calloc(n+1,sizeof(DataType));

if(ST-data!=NULL){

srand((unsigned) time(t));

for(i=1;i=n;i++){

ST-data[i]=rand() ;//产生20以内的随机数

}

ST-length=n;

}

}

}

//创建一个静态表，内容按从小到大排列，以便折半查找

void createST_binary(SSTable* ST,int n){

int i,j=0;

time_t t;

if(ST!=NULL){

ST-data=(DataType*)calloc(n+1,sizeof(DataType));

if(ST-data!=NULL){

for(i=1;i=n;i++){

ST-data[i]=j;

j+=4;

}

ST-length=n;

}

}

}

//打印出静态表的内容

void print_SSTable(SSTable* ST){

int i,n=ST-length;

if(ST!=NULL){

for(i=1;i=n;i++){

printf("%d ",ST-data[i]);

}

printf("\n");

}

}

//顺序查找(Sequential Search)

//思路:从表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

//查找成功：返回记录所在位置

//查找失败：返回0

int search_seq(SSTable ST,DataType key){

int i;

if(ST.data==NULL)return 0;

ST.data[0]=key;//设置监视哨。目的在于免去查找过程中每一步都要检测整

//个表是否查找完毕，是一个很有效的程序设计技巧 。监视

//哨也可以设在高下标处。

for(i=ST.length;ST.data[i]!=key;i--);

return i;

}

//折半查找(Binary Search)

//当记录的key按关系有序时可以使用折半查找

//思路：对于给定key值，逐步确定待查记录所在区间，每次将搜索空间减少一半（折半），

//直到查找成功或失败为止。

int search_binary(SSTable ST,DataType key){

int low,high,mid;

low=1;

high=ST.length;

while(low=high){//当表空间存在时

mid=(low+high)/2;

if(ST.data[mid]==key){

return mid;//查找成功，返回mid

}

if(keyST.data[mid]){

high=mid-1;//继续在前半区间查找

}else{

low=mid+1;//继续在后半区间查找

}

}

return 0;//查找失败

}

//分块查找（只记录思想）

//分块查找中，设记录表长为n，将表的n个记录分成b=n/s个块，每个s个记录

//最后一个记录数可以少于s个，且表分块有序，即后一个块的所有key值大于

//前一个块的所有key值

//每块对应一个索引项，索引项记录了该块记录的最大key值和该块第一记录的指针（或序号）

//算法：

//（1）由索引表确定待查找记录所在的块；

//（2）在块内顺序查找。

int main(){

int n=20;//在20个数中查找,方便看结果，不要设置得太大

SSTable ST,ST_binary;//分别用于顺序查找和折半查找的静态表

index indtb[n+1];//索引表，用于分块查找

createST(ST,n);//创建一个随机静态表

createST_binary(ST_binary,n);//创建一个从小到大顺序排列的静态表

//采用顺序查找

printf("原始数据:");

print_SSTable(ST);

printf("顺序查找5的结果:%d\n",search_seq(ST,5));

printf("顺序查找10的结果:%d\n",search_seq(ST,10));

printf("顺序查找12的结果:%d\n",search_seq(ST,12));

printf("顺序查找15的结果:%d\n",search_seq(ST,15));

printf("顺序查找20的结果:%d\n",search_seq(ST,20));

printf("--------------------------------------------\n");

//采用折半查找

printf("原始数据:");

print_SSTable(ST_binary);

printf("折半查找5的结果:%d\n",search_binary(ST_binary,5));

printf("折半查找10的结果:%d\n",search_binary(ST_binary,10));

printf("折半查找12的结果:%d\n",search_binary(ST_binary,12));

printf("折半查找15的结果:%d\n",search_binary(ST_binary,15));

printf("折半查找20的结果:%d\n",search_binary(ST_binary,20));

system("pause");//暂停一下，看看结果

free(ST.data);//不要忘了释放堆空间

return 0;

}

顺序存储结构怎样构造含n个元素的静态查找表

查找表：

是由同一类型的数据元素（或记录）构成的集合。

查找表的操作：

1、查询某个“特定的”数据元素是否在查找表中。

2、检索某个“特定的”数据元素的各种属性。

3、在查找表中插入一个数据元素；

4、从查找表中删去某个数据元素。

静态查找表

对查找表只作前两种操作

动态查找表

在查找过程中查找表元素集合动态改变

关键字

是数据元素（或记录）中某个数据项的值

主关键字

可以唯一的地标识一个记录

次关键字

用以识别若干记录

查找

根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功。

一些约定：

典型的关键字类型说明：

typedef float KeyType;//实型

typedef int KeyType;//整型

typedef char *KeyType;//字符串型

数据元素类型定义为：

typedef struct{

KeyType key; // 关键字域

...

}ElemType;

对两个关键字的比较约定为如下的宏定义：

对数值型关键字

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)(b))

#define LQ(a,b) ((a)=(b))

对字符串型关键字

#define EQ(a,b) (!strcmp((a),(b)))

#define LT(a,b) (strcmp((a),(b))0)

#define LQ(a,b) (strcmp((a),(b))=0)

二、静态查找表

静态查找表的类型定义：

ADT StaticSearchTable{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：

Create(ST,n);

操作结果：构造一个含n个数据元素的静态查找表ST。

Destroy(ST);

初始条件：静态查找表ST存在。

操作结果：销毁表ST。

Search(ST,key);

初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。

操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

Traverse(ST,Visit());

初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。

操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。

}ADT StaticSearchTable

三、顺序表的查找

静态查找表的顺序存储结构

typedef struct {

ElemType *elem;

int length;

}SSTable;

顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。

int Search_Seq(SSTable ST,KeyType key){

ST.elme[0].key=key;

for(i=ST.length; !EQ(ST.elem[i].key,key); --i);

return i;

}

查找操作的性能分析：

查找算法中的基本操作是将记录的关键字和给定值进行比较，，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。

平均查找长度：

为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

其中：Pi为查找表中第i个记录的概率，且；

Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。

等概率条件下有：

假设查找成功与不成功的概率相同：

数据结构与算法-静态最优查找树

当有序表中每个记录的查询概率相同时，用折半查找性能最优。当有序表的查找概率不等时，折半查找的概率未必最优。

若只考虑查找成功的情况，则使查找性能最优的判定树其带权路径长度之和为PH值。

PH=∑wihi

hi为第i个结点在二叉树上的层次数;结点的权wi=c*pi，pi为第i个结点的查找概率，c为某个常量。

称PH值最小的二叉判定树为静态最优查找树(Static Optimal Search Tree).

构造次优查找树的方法：首先在记录序列中取第i个记录构造根结点，使得左部分序列的累计权值和与右部分序列的累计权值和差的绝对值最小;再对左右子序列分别构造次优查找树。

紧急求助C语言描述的数据结构,中的有一个查找方式是用一个虚拟的哨兵元素来优化算法

这个属于顺序表的查找

typedef int Elemtype;

//定义静态查找表的顺序存储结构

typedef struct

{

Elemtype key;

}Elem;

typedef struct

{

Elem *elem;//存储空间基址

int length;//表的长度

}SSTable;

bool EQ(Elemtype key1,Elemtype key2)

{

if(key1==key2)

{

return true;

}

return false;

}

//下面是查找函数

int Search_Seq(SSTable ST, KeyType Key)

{

ST.elem[0].key=key;

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

return i;

}

我这里是将Elemtype定义为int 的，如果要定义为char，则应相应的更改EQ函数

顺序表的顺序查找和二分查找？

顺序查找,二分查找和哈希查找算法,它们各自的特点是：

1.对比顺序查找的特点就是从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功;如果到最后一个元素仍没有目标元素，则查找失败。

2.二分查找的特点就是从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分(表是递增排列的)，反之中间元素比目标元素大，则查找表的前半部分。

3.哈希算法的特点是是使用给定数据构造哈希表，然后在哈希表上进行查找的一种算法。先给定一个值，然后根据哈希函数求得哈希地址，再根据哈希地址查找到要找的元素。是通过数据元素的存储地址进行查找的一种算法。

请教：用JAVA编一个基本查找算法效率比较的程序。

script

Array.prototype.swap = function(i, j)

{

var temp = this[i];

this[i] = this[j];

this[j] = temp;

}

Array.prototype.bubbleSort = function()

{

for (var i = this.length - 1; i 0; --i)

{

for (var j = 0; j i; ++j)

{

if (this[j] this[j + 1]) this.swap(j, j + 1);

}

}

}

Array.prototype.selectionSort = function()

{

for (var i = 0; i this.length; ++i)

{

var index = i;

for (var j = i + 1; j this.length; ++j)

{

if (this[j] this[index]) index = j;

}

this.swap(i, index);

}

}

Array.prototype.insertionSort = function()

{

for (var i = 1; i this.length; ++i)

{

var j = i, value = this[i];

while (j 0 this[j - 1] value)

{

this[j] = this[j - 1];

--j;

}

this[j] = value;

}

}

Array.prototype.shellSort = function()

{

for (var step = this.length 1; step 0; step = 1)

{

for (var i = 0; i step; ++i)

{

for (var j = i + step; j this.length; j += step)

{

var k = j, value = this[j];

while (k = step this[k - step] value)

{

this[k] = this[k - step];

k -= step;

}

this[k] = value;

}

}

}

}

Array.prototype.quickSort = function(s, e)

{

if (s == null) s = 0;

if (e == null) e = this.length - 1;

if (s = e) return;

this.swap((s + e) 1, e);

var index = s - 1;

for (var i = s; i = e; ++i)

{

if (this[i] = this[e]) this.swap(i, ++index);

}

this.quickSort(s, index - 1);

this.quickSort(index + 1, e);

}

Array.prototype.stackQuickSort = function()

{

var stack = [0, this.length - 1];

while (stack.length 0)

{

var e = stack.pop(), s = stack.pop();

if (s = e) continue;

this.swap((s + e) 1, e);

var index = s - 1;

for (var i = s; i = e; ++i)

{

if (this[i] = this[e]) this.swap(i, ++index);

}

stack.push(s, index - 1, index + 1, e);

}

}

Array.prototype.mergeSort = function(s, e, b)

{

if (s == null) s = 0;

if (e == null) e = this.length - 1;

if (b == null) b = new Array(this.length);

if (s = e) return;

var m = (s + e) 1;

this.mergeSort(s, m, b);

this.mergeSort(m + 1, e, b);

for (var i = s, j = s, k = m + 1; i = e; ++i)

{

b[i] = this[(k e || j = m this[j] this[k]) ? j++ : k++];

}

for (var i = s; i = e; ++i) this[i] = b[i];

}

Array.prototype.heapSort = function()

{

for (var i = 1; i this.length; ++i)

{

for (var j = i, k = (j - 1) 1; k = 0; j = k, k = (k - 1) 1)

{

if (this[k] = this[j]) break;

this.swap(j, k);

}

}

for (var i = this.length - 1; i 0; --i)

{

this.swap(0, i);

for (var j = 0, k = (j + 1) 1; k = i; j = k, k = (k + 1) 1)

{

if (k == i || this[k] this[k - 1]) --k;

if (this[k] = this[j]) break;

this.swap(j, k);

}

}

}

function generate()

{

var max = parseInt(txtMax.value), count = parseInt(txtCount.value);

if (isNaN(max) || isNaN(count))

{

alert("个数和最大值必须是一个整数");

return;

}

var array = [];

for (var i = 0; i count; ++i) array.push(Math.round(Math.random() * max));

txtInput.value = array.join("\n");

txtOutput.value = "";

}

function demo(type)

{

var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n");

for (var i = 0; i array.length; ++i) array[i] = parseInt(array[i]);

var t1 = new Date();

eval("array." + type + "Sort()");

var t2 = new Date();

lblTime.innerText = t2.valueOf() - t1.valueOf();

txtOutput.value = array.join("\n");

}

/script

body onload=generate()

table style="width:100%;height:100%;font-size:12px;font-family:宋体"

tr

td align=right

textarea id=txtInput readonly style="width:100px;height:100%"/textarea

/td

td width=150 align=center

随机数个数input id=txtCount value=500 style="width:50px"brbr

最大随机数input id=txtMax value=1000 style="width:50px"brbr

button onclick=generate()重新生成/buttonbrbrbrbr

耗时(毫秒)：label id=lblTime/labelbrbrbrbr

button onclick=demo("bubble")冒泡排序/buttonbrbr

button onclick=demo("selection")选择排序/buttonbrbr

button onclick=demo("insertion")插入排序/buttonbrbr

button onclick=demo("shell")谢尔排序/buttonbrbr

button onclick=demo("quick")快速排序(递归)/buttonbrbr

button onclick=demo("stackQuick")快速排序(堆栈)/buttonbrbr

button onclick=demo("merge")归并排序/buttonbrbr

button onclick=demo("heap")堆排序/buttonbrbr

/td

td align=left

textarea id=txtOutput readonly style="width:100px;height:100%"/textarea

/td

/tr

/table

/body

这个代码是放在DREAMWEAVER head/head标签里面

静态查找算法代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于静态查找算法代码怎么写、静态查找算法代码的信息别忘了在本站进行查找喔。