C/C++泛型编程实现数据结构之广义表
广义表是线性表的推广，又称列表。线性表的元素只限于原子项，即每个数据元素只能是一个数或一个记录，如果放松对线性表元素的这种限制，允许他们自身具有结构，那么就产生了广义表。
广义表是一种多层次的线性结构，像是一颗倒扣的树，实际上，这也算是一种树形结构。广义表不仅是线性表的推广，也算是树结构的推广。
广义表的存储结构
广义表的元素本身可以具有结构，这是一种带有层次性的线性结构。这里我们定义了三个域。一个为tag标志位，指示了当前元素是原子还是子表。广义表规定了当tag为0时，当前原子项为原子（data），当tag为1时，当前原子项指向下一个原子子表的地址。（slink），即当广义表中的某个节点出现了data时，不可能出现节点slink。这个我们可以通过union联合体来实现。
另一个节点是link。link指向了同一层次的下一个元素的地址。类似于链表中得到next，link把每一个节点都窜通在了一起，不同于slink的是，link指向下一个节点，slink指向子表，当slink存在是，link一定为NULL。
广义表的基本操作
-
- 建立广义表
- 输出广义表
- 查找广义表中元素
- 获取广义表中的tail尾表
- 获取广义表深度
广义表理论存储形式直观表述
代码实现广义表结构
其中tag为标志位，data和slink在联合体中，link指向下一个节点，当节点是本层次最后一个元素时，link为NULL
typedef enum { atom, list }NodeTag;
template <typename DataType>
typedef struct GLNode{
NodeTag tag;
union {
DataType data;
GLNode* slink;
};
GLNode* link;
}*Glist;
代码实现广义表建立
用户输入字符。若当前字符为左括号，则设当前tag为1（list），否则当前tag为0（atom），若用户输入为空格，则广义表为空表。由上图可知，广义表创建是一个递归的过程，所以这里使用递归来实现。当然如果表特别大对内存空间有很大压力，则我们可以使用栈来模拟递归操作。最后本函数结尾返回广义表头
Glist CreateGList(Glist GL) {
char ch;
ch = getchar();
if (ch != ' ') {
GL = (GLNode *)malloc(sizeof(GLNode));
if (ch == '(') {
GL->tag = list;
GL->slink = CreateGList(GL->slink);
}
else {
GL->tag = atom;
GL->data = ch;
}
}
else GL = NULL;
ch = getchar();
if (GL != NULL) {
if (ch == ',')
GL->link = CreateGList(GL->link);
else
GL->link = NULL;
return GL;
}
}
代码实现广义表输出操作
广义表输出也是一个递归的操作。这里我们先判断广义表的标志位tag。如果tag为list，则暗示当前节点指向了下一个子表的地址。那么我们使用递归来访问当前节点的子表的地址slink。当然如果slink为空，那么子表就是空表，自然就需要输出空格了。当前子表判断后，我们可以继而判断当前层次的下一个元素。如果link为空，则当前表结束。否则我们每当访问一个link，输出一个逗号，并递归的访问下一个元素的地址。输出。
void PrintGlist(Glist GL = this.GL) {
if (GL != NULL) {
if (GL->tag == list) {
cout << "(";
if (GL -> slink == NULL)cout << " ";
else PrintGlist(GL->slink);
}
else {
cout << GL->data;
}
if (GL->tag == list)cout << ")";
if (GL->link != NULL) {
cout << ",";
PrintGlist(GL->link);
}
}
}
广义表的查找操作
这段函数的作用时在广义表GL中查找值为X的原子，并且如果查找成功就令mark的值为1，很容易得出。这也是一个递归的过程。
void FindGlistX(GList GL,DataType x,int * mark) {
if (GL != NULL) {
if (GL->tag == 0 && GL->data == x) {
p = GL;
*mark = 1;
}
else {
if (GL->tag == 1)FindGlistX(GL->slink, x, mark);
FindGlistX(gl->link, x, mark);
}
}
}
判断广义表深度
void depth(Glist GL, int * maxdh) {
int h;
if (GL->tag == 0)*maxdh = 0;
else {
if (GL->tag == 1 && GL->slink == NULL) {
*maxdh = 1;
}
else {
GL = GL->slink;
*maxdh = 0;
do {
depth(GL, &h);
if (h > *maxdh) {
maxdh = h;
}
} while (GL != NULL);
(*maxdh)++;
}
}
}
完整代码
#include <iostream>
#include <string>
using namespace std;
typedef enum { atom, list }NodeTag;
template <typename DataType>
class GLIST {
private:
typedef struct GLNode{
NodeTag tag;
union {
DataType data;
GLNode* slink;
};
GLNode* link;
}*Glist;
public:
Glist _GL;
Glist p;
public:
//建立广义表的存储结构
Glist CreateGList(Glist GL) {
char ch;
ch = getchar();
if (ch != ' ') {
GL = (GLNode *)malloc(sizeof(GLNode));
if (ch == '(') {
GL->tag = list;
GL->slink = CreateGList(GL->slink);
}
else {
GL->tag = atom;
GL->data = ch;
}
}
else GL = NULL;
ch = getchar();
if (GL != NULL) {
if (ch == ',')
GL->link = CreateGList(GL->link);
else
GL->link = NULL;
return GL;
}
}
void PrintGlist(Glist GL = this.GL) {
if (GL != NULL) {
if (GL->tag == list) {
cout << "(";
if (GL -> slink == NULL)cout << " ";
else PrintGlist(GL->slink);
}
else {
cout << GL->data;
}
if (GL->tag == list)cout << ")";
if (GL->link != NULL) {
cout << ",";
PrintGlist(GL->link);
}
}
}
void FindGlistX(GList GL,DataType x,int * mark) {
if (GL != NULL) {
if (GL->tag == 0 && GL->data == x) {
p = GL;
*mark = 1;
}
else {
if (GL->tag == 1)FindGlistX(GL->slink, x, mark);
FindGlistX(gl->link, x, mark);
}
}
}
Glist tail() {
Glist p;
if (GL != NULL && GL->tag != 0) {
p = GL->slink;
p->link = NULL;
return p;
}
else return NULL;
}
void depth(Glist GL, int * maxdh) {
int h;
if (GL->tag == 0)*maxdh = 0;
else {
if (GL->tag == 1 && GL->slink == NULL) {
*maxdh = 1;
}
else {
GL = GL->slink;
*maxdh = 0;
do {
depth(GL, &h);
if (h > *maxdh) {
maxdh = h;
}
} while (GL != NULL);
(*maxdh)++;
}
}
}
};
int main()
{
GLIST<char>* gl = new GLIST<char>();
//自己定义操作。
return 0;
}
以上即为利用C/C++泛型编程实现数据结构之广义表。类模板可复用。
