算法学习 之查询

 

/******************顺序查找******************/
//假设静态查找表的顺序存储结构为
typedef struct
{
ElemType *elem;   // 数据元素存储空间基址，建表时
// 按实际长度分配，0号单元留空
int length;         // 表的长度
} SSTable;

int Search_Seq(SSTable ST, KeyType key) 
{  /*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。*/
ST.elem[0] = key;      // “哨兵”
for (i=ST.length; ST.elem[i] != key; --i); // 从后往前找
return i; // 找不到时，i为0
} // Search_Seq

/****************比较无监视哨的查找算法***********/
int location (SSTable ST , ElemType& e) 
{
k = 1;
while ( k <= ST.length && ST.elem[k] !=e) 
k++;
if ( k<=ST.length) return k; 
else return 0;
} //location
//在表长>1000时，将使算法的执行时间几乎增加一倍。
//为此，改写顺序表的查找算法, 算法中附设监视哨，以避免循环时每一步都要判别是否数组出界。

/******************有序表折半查找******************/
int Search_Bin ( SSTable ST, KeyType key ) 
{  // 在有序表ST中折半查找其关键字等于key的数据元素。
// 若找到，则函数值为该元素在表中的位置，否则为0。
low = 1;    high = ST.length;  //置区间初值
while ( low <= high ) 
{
mid = (low + high) / 2;
if (ST.elem[mid] == key)   return mid;  //找到
else if ( ST.elem[mid] < key )
high = mid - 1; // 继续在前半区间进行查找
else  low = mid + 1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin

评论

1 楼 sblig 2012-05-22  

#include <stdio.h>
#include <stdlib.h>
#define  OK 1
#define  ERROR  0
#define LIST_INIT_SIZE  80
typedef struct {
  ElemType  *elem;
  int       length;
  int       listsize;
} SqList;

int ListLength_Sq(SqList L)
{
    return(L.length);
}
Status InitList_Sq(SqList &L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)) ;
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}
Status GetElem_Sq(SqList L, int i, int &e)
{
  e=L.elem[i-1];
  return OK;
}
int LocateElem_Sq(SqList L, int e)
{
    int i=0;
    while(i<L.length&&L.elem[i]!=e)
          i++;
    if(i==L.length)return 0;
    else return i;
}
Status ListInsert_Sq (SqList &L, int pos, ElemType e)
{
   ElemType *q,*p;
   if (pos<1||pos>L.length+1)  return ERROR;
   if (L.length >= L.listsize) return ERROR;

    q =&(L.elem[pos-1]);
    for (p=&(L.elem[L.length-1]); p>=q; p--)
       *(p+1) = *p;
   *q = e;
   L.length++;

  return OK;
}