符號表的定義
以集合為基礎，并且支持查詢，插入，洗掉三種基本運算的抽象資料型別，叫做符號表，
用定長陣列實作符號表
- 優點：結構簡單，實作簡單
- 缺點：
- 所表示的集合大小受到陣列大小的限制
- 洗掉操作慢，在最壞情況下需要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 = https://www.cnblogs.com/KBryant/p/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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/102060.html
標籤：C++
上一篇：集合-用鏈表實作集合
下一篇：繼承（一）