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

符号表的定义

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

用定长数组实现符号表

• 优点：结构简单，实现简单
• 缺点：
  • 所表示的集合大小受到数组大小的限制
  • 删除操作慢，在最坏情况下需要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 }