内容简述

使用模糊编码思想使用C/C++实现广义链表基本操作以及将字符串转化为广义链表

广义链表背景

广义链表是对传统线性表的一种扩充。传统的线性表，保存的元素是同一个类型，例如都是int类型，或者某个复杂的结构体类型。而广义链表里面保存的元素既可以是某一类型元素，还可以是另外一个广义表，这样就可以得到一种表中之表的结构。

广义表在文件系统中的应用广泛。一个大的文件夹，可以看成一个广义表，里面有很多的文件以及子文件夹；而每一个子文件夹实际上又是一个新的广义表，依次类推。从这点来看，广义表和二叉树一样具有递归结构，后续操作实现，将使用这一特性。

广义链表定义

约定

广义表可以记为：
$$L=(a_1,a_2,...,a_n)$$
其中$a_i$既可以是不可细分的元素，还可以是广义表；分别称为广义表L的原子和子表

表头

对于非空广义表L，第一个元素$a_1$称作L的表头。

表尾

除了表头剩下的元素称为表尾，在上面的例子当中即为$(a_2,a_3,...,a_n)$

长度

广义链表中元素的个数，空表长度为0

深度

广义链表中括弧的最大嵌套层数，空表深度为1，原子深度为0

概念示例

广义链表存储结构

分析

广义链表的元素既可以是原子又可以是子表，因此不能用某种单一的存储结构表示。当元素是原子时，此时存储结构中应当包含原子的取值；当元素是子表时，此时存储结构应当能够表示子表，即包含表头和表尾两个部分，至于深度，长度等量可以由后续定义的表基本操作实现，因此不在包含范围内。

代码实现

typedef int AtomType;
typedef AtomType ElemType;
typedef enum {
	ATOM = 0,LIST=1
}ElemTag;
typedef struct GLNode {
	ElemTag tag;//区分表内元素是原子结点还是子表
	union {
		AtomType atom;
		struct {
			struct GLNode *hp;
			struct GLNode *tp;
		}ptr;
	}un;
}GLNode,*GList;

使用枚举类型ElemTag表示元素的种类；使用联合体实现原子和子表共用存储空间，当tag==LIST时，ptr项才有意义；当tag==ATOM时，atom才有意义。

广义表接口定义

GList.h

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//自定义宏变量
#define OK 2
#define ERROR -2
#define OVERFLOOW -1
typedef int Status; //接收函数的返回值

*
	广义表,表里面的元素除了是具体的值以外，还可以是一个广义表，是对传统线性表的一个扩展
*/
typedef int AtomType;
typedef AtomType ElemType;
typedef enum {
	ATOM = 0,LIST=1,EMPTY=-1
}ElemTag;
typedef struct GLNode {

	ElemTag tag;//区分表内元素是原子结点还是表
	union {
		AtomType atom;
		struct {
			struct GLNode *hp;
			struct GLNode *tp;
		}ptr;
	}un;
}GLNode,*GList;
GLNode* MakeAtom(AtomType e);//创建一个原子结点e
void InitGList(GList &L);//创建一个空的广义表
Status DestroyGList(GList &L);//销毁一个广义表
GLNode *GetHead(GList &L);//求广义表的表头
GList GetTail(GList &L);//求广义表的表尾
Status InsertHead(GList &L, GLNode *p);//在表头插入元素p
Status append(GList &L, GLNode *p);//在表尾插入元素p
Status DeleteHead(GList &L, GList &p);//删除表头元素，使用p返回
int GListDepth(GList L);//返回广义表的深度，特别规定空表的深度为1，原子结点的深度为0
GList CopyGList(GList L);//复制一个广义表
int GListLength(GList L);//求一个广义表的深度
Status GListEmpty(GList L);//判断广义表是否为空
Status GListTraverse(GList L, Status(*visit)(ElemType e));//遍历一个广义表
Status transform(char text[],GList &L);//将一段符合格式的字符串转化为广义表存储结构

广义表基本操作实现

实现代码

这里直接粘贴相关代码，不做特殊说明

LNode * MakeAtom(AtomType e)
{
	GList node = (GList)malloc(sizeof(GLNode));
	if (NULL == node)return NULL;
	node->tag = ATOM;
	node->un.atom = e;
	return node;
}

void InitGList(GList & L)
{
	L = NULL;
}

Status DestroyGList(GList & L)
{
	//使用递归思想
	//释放的元素类型为原子结点
	if (L->tag == ATOM) {
		free(L);
	}
	else {
		//非原子结点继续遍历
		if (L->un.ptr.hp != NULL) {
			DestroyGList(L->un.ptr.hp);
		}
		if (L->un.ptr.tp != NULL) {
			DestroyGList(L->un.ptr.tp);
		}
		free(L);//释放空间
	}
	return OK;
}

GLNode *GetHead(GList &L)
{
	if (L == NULL)return L;
	if (L->tag == LIST) {
		return L->un.ptr.hp;
	}
	return L;
}

GList GetTail(GList & L)
{
	if (L == NULL)return L;
	if (L->tag == LIST) {
		return L->un.ptr.tp;
	}
	return L;
}

Status InsertHead(GList & L, GLNode * p)
{
	//插入的元素可能是原子结点也有可能是表结点
	//表为空时
	if (GListEmpty(L)) {
		L = (GList)malloc(sizeof(GLNode));
		if (NULL == L) {
			return ERROR;
		}
		L->tag = LIST;
		L->un.ptr.hp = p;
		L->un.ptr.tp = NULL;
	}
	else {

		//对于表L：新的表头指针指向p，新的尾指针指向L
		//需要切断练习
		GLNode *head = (GList)malloc(sizeof(GLNode));
		head->tag = LIST;
		head->un.ptr.hp = p;
		head->un.ptr.tp = L;
		L = head;
	}
	return true;
}

Status append(GList & L, GLNode * p)
{
	//在表尾插入元素，按照广义表中表尾的定义，需要进行一次封装
	//不管p的类型，将其作为一个表结点的头指针
	GList tail = (GList)malloc(sizeof(GLNode));
	if (tail == NULL)return ERROR;
	tail->tag = LIST; tail->un.ptr.hp = p; tail->un.ptr.tp = NULL;
	if (L == NULL) {
		L = tail;
	}
	else {
		GLNode *pp;//依次遍历表尾结点，在表尾结点添加元素tail
		for (pp = L; pp->un.ptr.tp != NULL; pp = pp->un.ptr.tp);
		pp->un.ptr.tp = tail;
	}
	return OK;
}

Status DeleteHead(GList & L, GList & p)
{
	if (GListEmpty(L)) {
		return ERROR;
	}
	//新的表头指向原来表尾的头指针
	//新的表尾指向原来表尾的尾指针
	GList pp = GetHead(L);
	L->un.ptr.hp = GetHead(L->un.ptr.tp);
	L->un.ptr.tp = GetTail(L->un.ptr.tp);
	if (pp) {
		free(pp);//释放空间
	}
	return OK;
}

int GListDepth(GList L)
{
	if (L == NULL)return 1;
	if (L->tag == ATOM)return 0;
	int h1 = GListDepth(L->un.ptr.hp) + 1;
	int h2 = GListDepth(L->un.ptr.tp);
	return h1 >= h2 ? h1 : h2;
}

GList CopyGList(GList L)
{
	//用递归的思想

	if (L == NULL) {
		return NULL;
	}
	GList node = (GList)malloc(sizeof(GLNode));
	if (L->tag == ATOM) {
		node->tag = ATOM;
		node->un.atom = L->un.atom;
	}
	else {
		node->tag = LIST;
		node->un.ptr.hp = CopyGList(L->un.ptr.hp);
		node->un.ptr.tp = CopyGList(L->un.ptr.tp);
	}
	return node;
}

int GListLength(GList L)
{
	if (L == NULL)return 0;
	//if (L->tag == ATOM)return 1;
	return GListLength(L->un.ptr.tp) + 1;
}

Status GListEmpty(GList L)
{
	if (L == NULL) {
		return true;
	}
	//if (L->tag == LIST && L->un.ptr.hp == NULL && L->un.ptr.tp == NULL) {
	//	return true;
	//}
	return false;
}

Status GTraverse(GList L, Status(*visit)(ElemType e), int flag) {
	//flag变量为标志变量
	//值为1时，需要打印左右括号
	//值为0时，不需要
	if (L == NULL) {
		return OK;
	}
	if (L->tag == ATOM) {
		visit(L->un.atom);
	}
	else {
		if (flag == 1) {
			printf("(");
		}
		GLNode *head = L->un.ptr.hp;
		if (head != NULL)GTraverse(head, visit, 1);
		GLNode *tail = L->un.ptr.tp;
		if (tail != NULL)printf(",");
		if (GListDepth(head) < GListDepth(tail)) {
			//两者深度相同
			GTraverse(tail, visit, 0);
		}
		else {
			GTraverse(tail, visit, 1);
		}
		if (flag == 1) {
			printf(")");
		}
	}
	return OK;
}

Status GListTraverse(GList L, Status(*visit)(ElemType e))
{
	if (L == NULL) {
		printf("()n");
	}
	else {
		GTraverse(L, visit, 1);
		printf("n");
	}
	return OK;
}

测试代码

Status visitGList(ElemType e) {
	if (typeid(e) == typeid(char)) {
		printf("%c", e );
	}
	if (typeid(e) == typeid(int)) {
		printf("%d", e );
	}
	return OK;
}

void testGList() {
	GList list;
	InitGList(list);
	printf("测试InsertHead函数n");
	for (int j = 0; j < 4; j++) {
		GList l;
		InitGList(l);
		for (int i = 0 + j; i < 3 + j; i++) {
			InsertHead(l, MakeAtom(i));
		}
		InsertHead(list, l);
		GListTraverse(list, visitGList);
	}
	printf("n表的深度为%dn", GListDepth(list));
	printf("尾指针的长度为%dn", GListDepth(GetTail(list)));
	printf("表的长度为%dn", GListLength(list));

	GLNode *temp;
	for (int i = 0; i < 4; i++) {
		DeleteHead(list, temp);
		GListTraverse(list, visitGList);
	}
	DestroyGList(list);
	InitGList(list);
	//测试append函数
	printf("n测试append函数n");
	for (int j = 0; j < 4; j++) {
		GList l;
		InitGList(l);
		for (int i = 0 + j; i < 3 + j; i++) {
			InsertHead(l, MakeAtom(i));
		}
		append(list, l);
		GListTraverse(list, visitGList);
	}
	printf("n复制一个广义表n");
	GList copyL = CopyGList(list);
	printf("删除并且摧毁复制的广义表n");
	for (int j = 0; j < 4; j++) {
		GLNode *temp;
		DeleteHead(copyL, temp);
		GListTraverse(copyL, visitGList);
	}
	printf("n打印原来的list表n");
	GListTraverse(list, visitGList);
}

测试结果

核心部分：将字符串转化为广义链表

背景

在广义链表接口中定义了基本操作，通过里面的INsertHead函数和Append函数理论上可以构建出我们想要的任何符合我们预期的广义表，但是那样比较麻烦，如下举例所示：
为了构建广义表：
$$L=((),(a),(c,(d),e))$$
需要如下步骤：

1. 创建广义表L
2. 在表头插入空链表
3. 在表尾插入$((a),(c,(d),e))$，为了实现这一目标，需要对其进行如下分解：
   3.1 创建广义表L1，在L1表头插入（a）
   3.2 在表尾插入$((c,(d),e))$，为了实现这一目标，又需要进行分解
   （1）创建链表L2，在表头插入$(c,(d),e)$，在表尾插入空链表
   ……………………

经过上面分析，发现这样很麻烦。但是上面分析的思路却给了我们另外一个思路，那就是广义链表具有递归结构，而所给的字符串似乎也具有一定的递归结构

分析合法字符串的组成

并不是所有的字符串都可以转化成一个广义链表，只有那些符合一定格式的才能进行转化。进一步需要满足如下的规则：

1. 左右括弧匹配：出现一个左括弧，需要有一个右括弧与之匹配
   eg1：正确格式$(a,(a),((b)))$
   eg2：错误格式$(a,(a),((b)$
2. 使用逗号对不同的元素进行区分，出现一个逗号，表明该字符串对应的广义链表里面至少有两个元素

算法目标

给定一段合法的字符串，对其进行分析，将其转化为相应的广义链表，并且使用基本操作中打印广义链表的函数GListTraverse打印输出该链表，检查是否和所给字符串一致。

方法论：模糊编码

代码编写过程并不总是一帆风顺，往往会遇到各种各样的问题，这些问题可以将我们代码编写过程划分为几个不同的阶段，从而对应不同的状态

几种编码状态

1. 模糊状态
   通常对于给定的问题，很难立马想出对应的求解思路，有些时候可能想出来了，但是很模糊，甚至存在一些逻辑上的错误，这种状态我愿意称为模糊状态
2. 顿悟状态
   当我们认真分析问题的时候，会抓住问题的关键点，也可以成为破绽，根据关键点，我们可以得到一些常用的处理方法，这个过程我愿意称为顿悟状态
3. 分析状态
   这种状态才是我们想要的。经过上面顿悟状态，我们已经有了一些常规思路，接下来，要做的就是根据常规思路进一步细化，分析，使用符合逻辑的语言也就是伪代码进行描述
4. 困难状态
   在分析状态中，即使不上机编写代码，我们还是会事先遇到很多的困难，这些困难使我们不得不又转入到顿悟状态甚至是模糊状态
5. 完善状态
   当我们解决困难状态中各种各样的问题的时候，我们此时可能觉得大功告成；但在更多的时候，我们需要考虑一些比较细节的问题：例如非空判断，下标越界检查，数据格式之间转化等等
6. 编码阶段
   经过上面的努力，终于要手动实现了，成败在此一举
7. 测试阶段
   代码编写完成，当然要测试一下时候正确，最好的办法就是测试。需要准备好测试用例，测试用例需要具有代表性，特别应该考虑到一些特殊的情况
8. 成功状态
   这个状态不用多说，是我们所期望的状态
9. 怀疑人生阶段
   这个状态更不用多说，是我们不想碰到的状态。除非在这个状态有精神损失费

状态转换

优点

1. 模糊编码从思路形成过程上看，是由模糊逐渐变得清晰，思维跨度小
2. 从编码角度来看，不强调编码，强掉伪代码，强掉伪代码能不能正确表达出期望的逻辑
3. 从人文世界解决问题的角度来看，是符合我们人知，容易被接受

缺点

1. 强掉个人和问题进行的斗争，忽视了团队的力量
2. 需要进行详细的伪代码描述工作，在有些场景下不适合，浪费时间
3. 由于过程曲折，容易打击自身编码积极性，造成主观上不想编码，甚至患有代码恐惧症

编写思路

正如算法目标里面描述的那样，所给的字符串具有递归结构，还是上面的例子，如下：
$$L=((),(a),(c,(d),e))$$
现在把它看成是一道算法题，很显然，其表头部分为：
$$GetHead(L)=()$$
表尾部分为：
$$GetTail(L)=((a),(c,(d),e))$$
其中注意到表尾部分和L在结构上很相似。为了将L对应的字符串转化为对应的广义表，那么首先需要将表尾部分字符串转化为广义表；进一步而言后者是前者的子问题。基于上述分析，我们就可以从模糊阶段进入到顿悟阶段——即使用递归的策略，将问题规模缩减，直至为可以直接解决的问题。

第一版伪代码

1. 定义用户调用函数Status transform(char text[], GList &L)
2. 定义递归函数GList TransformTextToGList(char text[], int l, int r)，其语义为将text[l,r]对应的字符串转化为一个广义链表
   接下来重点实现TransformTextToGList函数的逻辑
   （1） 递归结束条件
   text[l,r]对应的是空链表或者是原子结点时，直接创建广义链表元素结点，对元素结点里面的属性进行赋值，返回元素结点
   （2）主体逻辑
   进入到这里，表明text[l,r]对应的是一个链表，有表头和表尾两个部分。
   创建元素结点node，类型为LIST
   将字符串分割成表头和表尾两个部分，其中表头对应的范围为$[h_1,h_2]$；表尾为$[t_1,t_2]$
   开始递归
   node的表头指针为TransformTextToGList(text,$h_1$,$h_2$)
   node的表尾指针为TransformTextToGList(text,$t_1$,$t_2$)
   将node结点返回即可
3. 在transform函数里面的逻辑直接调用函数即可
   TransformTextToGList(text,0,text的长度)

第二版伪代码

在上面关键点在于对字符串进行分割为表头和表尾两部分，直觉告诉我通过O(N)时间复杂度就可以完成，因此代码逻辑里面应该包括遍历字符串；但是循环内部该如何处理？

第三版伪代码

循环内部通过找逗号的方式，这里我采用的方法为由特殊到一般再到特殊

从上面可以看出表头部分后面为逗号，表尾部分前面为逗号，因此可以通过定位逗号的方式来进行分割。
但此时又有问题出现了，并不是所有的逗号都是分割符，分割符只有一个，且在它前面左括弧的个数比右括弧的个数多1，满足这个条件才是我们想找的分割符。
于是可以使用flag变量来记录左右括弧之差，初始值为0
在遍历text过程中，遇到左括弧时，flag++；遇到右括弧时，flag–；当遇到逗号时，如果flag的值为1，就结束循环，此时遍历到的位置 i 即是我们想要的分隔符
于是表头部分为[l,i-1]；表尾部分为[i+1,r]

第一次上机

打印出奇怪的东西，失败

第四版伪代码

关键点在于表尾部分出错，其范围应当是[i,r]，但是text[i]为逗号，需要手动改为左括弧，待逻辑处理完以后再改为逗号

第二次上机

报错，无法处理((a))和（（a，d））的情况

第五版伪代码

当遍历完text[l,r]还是没有找到分隔符时，此时说明text对应的表尾部分为空，里面只有一个表头元素，而表头对应的部分为
[l+1,r-1]，表尾直接为空即可

第三次上机

成功

完整代码

//返回text的长度
int GeTTextLength(char text[]) {

	char *p = text;
	int length = 0;
	while (p != NULL && (*p) != '') {
		p++;
		length++;
	}
	return length;
}

GList TransformTextToGList(char text[], int l, int r) {
	GLNode *node = NULL;
	if (l == r) {
		//原子结点
		node = (GLNode*)malloc(sizeof(GLNode));
		node->tag = ATOM;
		node->un.atom = text[l];
		return node;
	}
	if (l > r) {
		//空结点
		return node;
	}
	//将字符串分为表头和表尾两个部分
	int i = l;
	int flag = 0;
	for (; i <= r; i++) {
		if (text[i] == '(') {
			flag++;
		}
		if (text[i] == ')') {
			flag--;
		}
		if (text[i] == ','&&flag == 1) {
			//可以进行分割
			node = (GLNode*)malloc(sizeof(GLNode));
			node->tag = LIST;
			node->un.ptr.hp = TransformTextToGList(text, l + 1, i - 1);
			char temp = text[i];
			text[i] = '(';
			node->un.ptr.tp = TransformTextToGList(text, i, r);
			text[i] = temp;
			break;
		}
	}
	if (i > r) {
		//没有找到分割点
		node = (GLNode*)malloc(sizeof(GLNode));
		node->tag = LIST;
		node->un.ptr.hp = TransformTextToGList(text, l + 1, r - 1);
		node->un.ptr.tp = NULL;
	}
	return node;
}


Status transform(char text[], GList &L) {
	int length = GeTTextLength(text);
	if (length == 2 && text[0] == '('&&text[1] == ')') {
		L = NULL;
	}
	else {
		L = TransformTextToGList(text, 0, length - 1);
	}
	return OK;
}

测试代码

void testTransformTextToGList() {
	char text[100];
	printf("输入测试字符串，下面是通过的测试，当然也可以自定义，前提是符合格式（括号匹配以及英文逗号）:n");
	printf("()n");
	printf("(a)n");
	printf("((),(a),(b,(c,(d),e)))n");
	printf("((),((a),((b,((c,((d),e)))))))n");
	printf("(f,(g),h)n");
	scanf("%s", text);
	GList L;
	InitGList(L);
	transform(text, L);
	printf("打印广义链表：n");
	GListTraverse(L, visitGList);
	printf("n表的深度为%dn", GListDepth(L));
	printf("尾指针的长度为%dn", GListDepth(GetTail(L)));
}

测试结果

最后

以上就是认真黑米为你收集整理的模糊编码实践：C/C++实现广义链表基本操作以及将字符串转化为广义链表内容简述广义链表背景广义链表定义广义链表存储结构广义表接口定义广义表基本操作实现核心部分：将字符串转化为广义链表的全部内容，希望文章能够帮你解决模糊编码实践：C/C++实现广义链表基本操作以及将字符串转化为广义链表内容简述广义链表背景广义链表定义广义链表存储结构广义表接口定义广义表基本操作实现核心部分：将字符串转化为广义链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。