数据结构C语言版顺序查找
P216
编译环境：Dev-C++ 4.9.9.2
日期：2011年2月15日
*/
#include
#include
#define N 5 // 数据元素个数
typedef int KeyType; // 设关键字域为整型
typedef struct // 数据元素类型(以教科书P215图9.1高考成绩为例) {
long number; // 准考证号
char name[9]; // 姓名(4个汉字加1个串结束标志)
int politics; // 政治
int Chinese; // 语文
int English; // 英语
int math; // 数学
int physics; // 物理
int chemistry; // 化学
int biology; // 生物
KeyType key; // 关键字类型应为KeyType,域名应为key
} ElemType;
typedef struct
{
// 数据元素存储空间基址，建表时按实际长度分配，0号单元留空ElemType *elem;
int length; // 表长度
}SSTable;
ElemType r[N] = {
{179324, "何芳芳", 85, 89, 98, 100, 93, 80, 47},
{179325, "陈红", 85, 86, 88, 100, 92, 90, 45},
{179326, "陆华", 78, 75, 90, 80, 95, 88, 37},
{179327, "张平", 82, 80, 78, 98, 84, 96, 40},
{179328, "赵小怡", 76, 85, 94, 57, 77, 69, 44}
}; // 全局变量
#define total key // 定义总分(total)为关键字
// 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r)。
int Creat_Seq(SSTable *ST,int n)
{
int i;
(*ST).elem = (ElemType *)calloc(n+1,sizeof(ElemType));
// 动态生成n+1个数据元素空间(0号单元不用)
if(!(*ST).elem)
return 0;
for(i=1;i<=n;i++)
*((*ST).elem+i)=r[i-1]; // 将全局数组r的值依次赋给ST (*ST).length=n;
return 1;
}
// 重建静态查找表为按关键字非降序排序。
void Ascend(SSTable *ST)
{
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];
}
if(k != i) // 有更小的值则交换
{
(*ST).elem[k] = (*ST).elem[i];
(*ST).elem[i] = (*ST).elem[0];
}
}
}
// 构造一个含n个数据元素的静态按关键字非降序查找表ST。
// 数据来自全局数组r。
int Creat_Ord(SSTable *ST,int n)
{
int f;
f = Creat_Seq(ST,n);
if( f )
Ascend( ST );
return f;
}
// 销毁表ST。
int Destroy(SSTable *ST)
{
free((*ST).elem);
(*ST).elem = NULL;
(*ST).length = 0;
return 1;
}
// 按顺序对ST的每个元素调用函数Visit()一次且仅一次。
int Traverse(SSTable ST, void (* Visit)(ElemType))
{
ElemType *p;
int i;
p = ++ST.elem; // p指向第一个元素,第0个元素没有用
for(i = 1;i <= ST.length; i++)
Visit(*p++);
return 1;
}
// 算法9.1 P217
// 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数// 值为该元素在表中的位置，否则为0。
int Search_Seq(SSTable ST,KeyType key)
{
int i;
ST.elem[0].key = key; // 哨兵
for(i = ST.length; !(ST.elem[i].key == key); --i)
; // 从后往前找
return i; // 找不到时，i为0
}
void print(ElemType c) // Traverse()调用的函数
{
printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5d\n",
c.number, , c.politics, c.Chinese,c.English,
