数据结构C语言版 顺序查找

*




*

#include
#include

#define N 5 数据元素个数

typedef int KeyType; 设关键字域为整型

typedef struct 数据元素类型(以教科书P215图9.1高考成绩为例)
{









long number;
char name[9];
int politics;
int Chinese;
int English;
int math;
int physics;
int chemistry;
int biology;
准考证号
姓名(4个汉字加1个串结束标志)
政治
语文
英语
数学
物理
化学
生物
关键字类型应为KeyType,域名应为key
数据结构C语言版 顺序查找
P216
编译环境：Dev-C++ 4.9.9.2
日期：2011年2月15日
KeyType key;
} ElemType;

typedef struct
{


数据元素存储空间基址，建表时按实际长度分配，0号单元留空
ElemType *elem;
表长度 int length;
}SSTable;

ElemType r[N] = {
{179324, 何芳芳
{179325, 陈红
{179326, 陆华
{179327, 张平
{179328, 赵小怡
}; 全局变量

#define total key 定义总分(total)为关键字

构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r)。

int Creat_Seq(SSTable *ST,int n)
{









}

重建静态查找表为按关键字非降序排序。
void Ascend(SSTable *ST)
{

















}

构造一个含n个数据元素的静态按关键字非降序查找表ST。
数据来自全局数组r。
int Creat_Ord(SSTable *ST,int n)
{
int f;
f = Creat_Seq(ST,n);
int i,j,k;
for(i=1;i<(*ST).length;i++)
{













}
k=i;
(*ST).elem[0] = (*ST).elem[i]; 待比较值存[0]单元
for(j = i + 1; j <= (*ST).length; j++)





if((*ST).elem[j].key < (*ST).elem[0].key)
{


}
k = j;
(*ST).elem[0] = (*ST).elem[j];
int i;
(*ST).elem = (ElemType *)calloc(n+1,sizeof(ElemType));
动态生成n+1个数据元素空间(0号单元不用)
if(!(*ST).elem)


return 0;
*((*ST).elem+i)=r[i-1]; 将全局数组r的值依次赋给ST
for(i=1;i<=n;i++)
(*ST).length=n;
return 1;
if(k != i) 有更小的值则交换
{


}
(*ST).elem[k] = (*ST).elem[i];
(*ST).elem[i] = (*ST).elem[0];

if( f )
Ascend( ST );

return f;
}

销毁表ST。
int Destroy(SSTable *ST)
{





}

按顺序对ST的每个元素调用函数Visit()一次且仅一次。
int Traverse(SSTable ST, void (* Visit)(ElemType))
{






}

算法9.1 P217
在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数
值为该元素在表中的位置，否则为0。
int Search_Seq(SSTable ST,KeyType key)
{





}


void print(ElemType c) Traverse()调用的函数
{
printf(
, , cs, e,h,
int i;
[0].key = key; 哨兵
for(i = !([i].key == key); --i)
从后往前找
return i; 找不到时，i为0
ElemType *p;
int i;
p = ++; p指向第一个元素,第0个元素没有用
for(i = 1;i <= i++)
Visit(*p++);
return 1;
free((*ST).elem);
(*ST).elem = NULL;
(*ST).length = 0;

return 1;

,s,try,y,);
}

int main()
{






















SSTable st;
int i,s;
for(i=0;i r[i].total = r[i].politics + r[i].Chinese +



Creat_Seq(&st, N); 由全局数组产生静态查找表st
printf(准考证号 姓名 政治 语文 外语 数学 物理 化学 生物 总分n
Traverse(st,print); 按顺序输出静态查找表st

printf(请输入待查找人的总分:
scanf(
i = Search_Seq(st,s); 顺序查找
if( i )
print( *( + i) );
else
printf(没找到n

Destroy(&st);

system(
r[i].English + r[i].math
+ r[i].physics + r[i].chemistry + r[i].biology;
return 0;
}

*
输出效果：

准考证号 姓名 政治 语文 外语 数学 物理 化学 生物 总分
179324 何芳芳 85 89 98 100 93 80 47 592
179325 陈红 85 86 88 100 92 90 45 586
179326 陆华 78 75 90 80 95 88 37 543
179327 张平 82 80 78 98 84 96 40 558
179328 赵小怡 76 85 94 57 77 69 44 502
请输入待查找人的总分: 543
179326 陆华 78 75 90 80 95 88 37 543
请按任意键继续. . .

*