广义表存储结构|数据结构_广义表的存储结构

一、头尾链表的存储结构

由于广义表的数据元素可以分为原子和广义表，由此需要两种结构的结点，一种是表结点（广义表），一种是原子结点（原子）。

非空广义表可以分解为表头和表尾。

1、表头和表尾

表头：非空广义表的第一个元素，可以是一个单原子，也可以是一个子表
表尾：去除表头之外其余元素构成的表，表尾一定是一个广义表

2、表结点和原子结点

表结点：标志域、指示表头的指针域、指示表尾的指针域
原子结点：标志域和值域
标志域（tag）：值为1时表明结点是子表，值为0时表明结点是原子

//ATOM=0表示原子，LIST=1表示子表
typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode
{
	ElemTag tag;
	union
	{
		//Atomtype由用户自定义
		AtomType atom;
		//ptr是表结点的指针域7
		struct
		{
			struct *GLNode *hp;
			struct *GLNode *tp;
		}ptr;
	};
}*GList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、扩展线性链表的存储结构

无论是表结点还是原子结点，均由三个域组成

typedef enum{ATOM,LIST} ELemTag;
typedef struct GLNode
{
	ElemTag tag;
	struct GLNode *tp;
	union
	{
		struct GLNode *hp;
		AtomType atom;
	}
}*GList;
1
2
3
4
5
6
7
8
9
10

void Virus_detection()
{
	ifstream inFile("输入.txt");
	ofstream outFile("结果.txt");

	inFile >> num;
	while(num--)
	{
		inFile >> Virus.ch+ 1;
		inFile >> Person.ch + 1;
		
		Vir = Virus.ch;
		flag = 0;
		m = Virus.length;

		for(i=m+1,j=1;j<=m;j++) 
		{
			Virus.ch[i++] = Virus.ch[j];
		}
		Virus.ch[2*m+1] = '\0';

		for(i=0;i<m;i++)
		{
			for(j=1,j<=m;j++)
			{
				temp.ch[j] = Virus.ch[i+j];
			}
			temp.ch[j+1] = '\0';
			flag = Index_BF(Person,temp,1);
			if(flag)
				break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33