软件设计师2005年11月试题4(C语言 散列文件存储)

简介: 散列文件的存储单位称为桶(BUCKET) 。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1 个同义词会发生"溢出"。此时需要将第m+1 个同义词存放到另一个称为"溢出桶"的桶中。

     散列文件的存储单位称为桶(BUCKET) 。假如一个桶能存放m个记录,当桶中已有m个同义词(散列函数值相同)的记录时,存放第m+1 个同义词会发生"溢出"。此时需要将第m+1 个同义词存放到另一个称为"溢出桶"的桶中。相对地,称存放前m个同义词的桶为"基桶"。溢出桶和基桶大小相同,用指针链接。查找指定元素记录时,首先在基桶中查找。若找到,则成功返回,否则沿指针到溢出桶中进行查找。
  例如:设散列函数为Hash(Key)=Key mod 7 ,记录的关键字序列为15,14,21,87,96,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453 ,建立的散列文件内容如图4-1 所示。
[图4-1] 

 

 

为简化起见,散列文件的存储单位以内存单元表示。
  函数InsertToHashTable(int NewElemKey )的功能是:若新元素NewElemKey 正确插入散列文件中,则返回值1;否则返回值0。
  采用的散列函数为Hash(NewElemKey)=NewElemKey % P ,其中P设定的基桶数目。
  函数中使用的预定义符号如下:
  #define NULLKey -1   /*散列桶的空闲单元标识*/
  #define P 7   /*散列文件中基桶的数目*/
  #define ITEMS 3  /*基桶和溢出桶的容量*/
  typedef struct BucketNode {   /*基桶和溢出桶的类型定义*/
   int KeyData[ITEMS];
   struct BucketNode *Link;
  }BUCKET;BUCKET Bucket[P];  /*基桶空间定义*/
[函数]
  int InsertToHashTable(int NewElemKey){
   /*将元素NewElemKey 插入散列桶中,若插入成功则返回0,否则返回-1*/
   /*设插入第一个元素前基桶的所有KeyData[] 、Link 域已分别初始化为NULLKEY 、NULL*/
   int Index;  /*基桶编号*/
   int i,k; BUCKET *s,*front,*t;
   Index=NewElemKey % P;
   for(i=0;i<ITEMS; i++)  /* 在基桶查找空闲单元,若找到则将元素存入*/
    if (Bucket[Index].KeyData[i] == NULLKEY) {
     Bucket[Index].KeyData[i] = NewElemKey;
     break;
    }
    if (i<ITEMS)return 0;
    /* 若基桶已满,则在溢出桶中查找空闲单元,若找不到则申请新的溢出桶*/
    front=Bucket+Index;
    t = Bucket[Index].Link;
    if (t != NULL) {   /* 有溢出桶*/
     while (t != NULL) {
      for(k = 0;k < ITEMS; k++)
       if (t -> KeyData[k] == NULLKEY) { /* 在溢出桶链表中找到空闲单元*/
        t -> KeyData[k] = NewElemKey;
        break;
       }  /*if*/
       if (k==ITEMS) t = t-> Link;   /*指向下一个溢出桶*/
       else break;
     }  /*while*/
    }  /*if*/
    if (t==NULL) {  /* 申请新溢出桶并将元素存入*/
     s = (BUCKET *)malloc(sizeof(BUCKET));
     if (!s) return -1;
     s->Link = NULL;
     for(k = 0; k < ITEMS; k++)
      s->KeyData[k] = NULLKEY;
      s->KeyData[0] = NewElemKey;
      front->Link=s;
    }  /*if*/
    return 0;
   }  /*InsertToHashTable*/ 

相关文章
|
2月前
|
存储 数据可视化 Serverless
【C语言】C语言-学籍管理系统(源码+文件存储)【独一无二】
【C语言】C语言-学籍管理系统(源码+文件存储)【独一无二】
|
存储 文件存储 C语言
【C语言】通讯录3.0 (文件存储版)
通讯录是一种记录联系人信息的工具,包括姓名、电话号码、电子邮件地址、住址等。 文章的一二三章均于上一篇相同,可以直接看第四章改造内容。 此通讯录是基于通讯录2.0(动态增长版)的基础上进行增加文件操作功能,请先看系列文章第二篇,再看本篇博客。
48 1
|
存储 编译器 C语言
C语言进阶——指针进阶试题讲解(万字长文详解)
C语言进阶——指针进阶试题讲解(万字长文详解
55065 7
C语言进阶——指针进阶试题讲解(万字长文详解)
|
存储 编译器 C语言
C语言进阶——指针进阶试题讲解(万字长文详解)
指针,一块存储其他内存块地址的空间,不仅能监管别人的地址信息,还拥有属于自己的地址。在取地址操作符(&)与解引用操作符(*)的“双重折磨”下,很多人对指针望而生畏,常常会掉进不规范使用指针而引发错误的大坑中。本文旨在通过众多例子来带大家理解指针(主要包含sizeof、strlen和多道指针笔试题),本文篇幅可能较长,请系好安全带,跟我走!
66 0
C语言进阶——指针进阶试题讲解(万字长文详解)
|
存储 C语言
软件评测师2020年考试上午C语言试题解析
软件评测师2020年考试上午C语言试题解析
134 0
|
算法 数据安全/隐私保护 C语言
【C 语言】文件操作 ( 文件加密解密 | 加密解密原理 | 对称加密 | 非对称加密 | 散列函数 )
【C 语言】文件操作 ( 文件加密解密 | 加密解密原理 | 对称加密 | 非对称加密 | 散列函数 )
211 0
|
程序员 编译器 C语言
[软考考点解析]软件设计师--C语言存储空间
1. 题目 C程序中全局变量存储空间在____分配。 A 代码区 B 静态数据区 C 栈区 D 堆区
130 0
|
C语言 人工智能 存储
软件设计师2006年5月试题5(C语言 多叉平衡查找树)
B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树:  ①树中每个结点至多有m棵子树;  ②若根结点不是叶子结点,则它至少有两棵子树;  ③除根之外的所有非叶子结点至少有「m/2]棵子树;  ④所有的非叶子结点中包含卞列数据信息   (n,A0,K1,A1,K2,...
673 0
|
C语言 存储
软件设计师2006年11月下午试题5(C语言 树及其孩子-兄弟表示)
[说明]  一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图 5-1(a) 所示的树的孩子-兄弟表示如图 5-1(b)所示。
944 0
|
2天前
|
算法 搜索推荐 C语言
【C语言篇】深入理解指针4(模拟实现qsort函数)
【C语言篇】深入理解指针4(模拟实现qsort函数)
10 2