符号表-定长数组实现符号表

符号表的定义

以集合为基础，并且支持查询，插入，删除三种基本运算的抽象数据类型，叫做符号表。

用定长数组实现符号表

• 优点：结构简单，实现简单
• 缺点：
  • 所表示的集合大小受到数组大小的限制
  • 删除操作慢，在最坏情况下需要O(n)
  • 存储空间得不到充分利用
• 数组实现符号表的结构定义

  1 typedef short SetItem;
  2
  3 typedef struct atab
  4 {
  5     int arraysize;    //表示数组大小，即存储了几个位向量
  6     int last;    //指示集合的最后一个元素在数组中的存储位置
  7     SetItem* data;
  8 }Atab, *Table;

•  相关操作

 1 /*创建一个定长数组大小为size的空符号表*/
 2 Table TableInit(int size)
 3 {
 4     Table T = new Atab;
 5     T->arraysize = size;
 6     T->last = 0;
 7     T->data = new SetItem[size];
 8 }
 9
10 /*成员查询函数*/
11 int TableMember(SetItem x, Table T)
12 {
13     for (int i = 0; i < T->last; i++)
14     {
15         if (T->data[i] == x)
16             return 1;
17     }
18     return 0;
19 }
20
21 /*元素插入*/
22 void TableInsert(SetItem x, Table T)
23 {
24     if (!TableMember(x, T) && T->last < T->arraysize)//判断数组是否还有空间
25         T->data[T->last++] = x;
26 }
27
28 /*删除元素*/
29 void TableDelete(SetItem x, Table T)
30 {
31     int i = 0;
32     if (T->last > 0)//判断非空集合
33     {
34         while (T->data[i]!=x&&i<T->last)//遍历找到删除元素
35         {
36             i++;
37         }
38         if (i < T->last&&T->data[i] == x)
39             //以最后一个元素覆盖被删除位置，并将last--
40             T->data[i] = T->data[--T->last];
41     }
42 }