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

文章目录一、头尾链表的存储结构1、表头和表尾2、表结点和原子结点二、扩展线性链表的存储结构一、头尾链表的存储结构由于广义表的数据元素可以分为原子和广义表，由此需要两种结构的结点，一种是表结点（广义表），一种是原子结点（原子）。非空广义表可以分解为表头和表尾。1、表头和表尾表头：非空广义表的第一个元素，可以是一个单原子，也可以是一个子表表尾：去除表头之外其余元素构成的表，表尾一定是一个广...

写代码的资资

8010人浏览 · 2019-10-27 13:18:24

写代码的资资 · 2019-10-27 13:18:24 发布

文章目录

一、头尾链表的存储结构

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

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

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;

在这里插入图片描述

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

无论是表结点还是原子结点，均由三个域组成
在这里插入图片描述

typedef enum{ATOM,LIST} ELemTag;
typedef struct GLNode
{
	ElemTag tag;
	struct GLNode *tp;
	union
	{
		struct GLNode *hp;
		AtomType atom;
	}
}*GList;

在这里插入图片描述

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;
		}
	}
}