首页 / C语言 / 数据结构之---C语言实现广义表头尾链表存储表示

数据结构之---C语言实现广义表头尾链表存储表示

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构之---C语言实现广义表头尾链表存储表示，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5959字，纯文字阅读大概需要9分钟。

内容图文

//广义表的头尾链表存储表示
//杨鑫
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAXSTRLEN 40 ）
typedef char SString[MAXSTRLEN+1]; 
typedef char AtomType;	                   // 定义原子类型为字符型  
typedef enum{
	ATOM, LIST	                          // ATOM==0:原子 LIST==1:子表                     
} ElemTag; 

typedef struct GLNode
{
	ElemTag tag;				// 公共部分,用于区分原子结点和表结点 
	union								// 原子结点和表结点的联合部分 
	{
		AtomType atom; 						// atom是原子结点的值域, AtomType由用户定义 
		struct
		{
			struct GLNode *hp,*tp;
		}ptr;								 // ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 
	}a;
} *GList, GLNode;	


//初始化的广义表L
int InitGList(GList *L)
{ 
	*L = NULL;
	return 1;
}

//销毁广义表L
void DestroyGList(GList *L) 
{ 
	GList q1,q2;
	if(*L)
	{
		if((*L)->tag == ATOM)
		{
			free(*L);								
			*L = NULL;
		}
		else	
		{
			q1 = (*L)->a.ptr.hp;
			q2 = (*L)->a.ptr.tp;
			free(*L);
			*L = NULL;
			DestroyGList(&q1);
			DestroyGList(&q2);						// 递归删除表头和表尾结点
		
		}
	}
}


// 採用头尾链表存储结构,由广义表L复制得到广义表T。 
int CopyGList(GList *T,GList L)
{
	if(!L)
		*T = NULL;
	else
	{
		*T = (GList)malloc(sizeof(GLNode)); 
		if(!*T)
			exit(0);
		(*T)->tag = L->tag;
		if(L->tag == ATOM)
			(*T)->a.atom = L->a.atom;								// 复制单原子 
		else												// 是表结点，则依次复制表头和表尾
		{
			CopyGList(&((*T)->a.ptr.hp), L->a.ptr.hp);
			CopyGList(&((*T)->a.ptr.tp), L->a.ptr.tp);
														
			
		}
	}
	return 1;
}

// 返回广义表的长度,即元素个数
int GListLength(GList L)
{
	int len = 0;
	if(!L)
		return 0;
	if(L->tag == ATOM)
		return 1;
	while(L)
	{
		L = L->a.ptr.tp;	
		len++;
	}
	return len;
}


// 採用头尾链表存储结构,求广义表L的深度。
int GListDepth(GList L)
{
	int max, dep;
	GList pp;
	
	if(!L)
		return 1;																	// 空表深度为1
	if(L->tag == ATOM)
		return 0;																			// 原子深度为0
	for(max = 0, pp = L; pp; pp = pp->a.ptr.tp)
	{
																					// 递归求以pp->a.ptr.hp为头指针的子表深度 
		dep = GListDepth(pp->a.ptr.hp);
		if(dep > max)
			max = dep;
	}
	return max+1;															// 非空表的深度是各元素的深度的最大值加1 
}

// 判定广义表是否为空
int GListEmpty(GList L)
{
	if(!L)
		return 1;
	else
		return 0;
}

// 取广义表L的头
GList GetHead(GList L)
{
	GList h,p;

	if(!L)
	{
		printf("空表无表头!\n");
		exit(0);
	}
	p = L->a.ptr.tp;	
	L->a.ptr.tp = NULL;
	CopyGList(&h,L);
	L->a.ptr.tp = p;
	return h;
}

// 取广义表L的尾
GList GetTail(GList L)
{
	GList t;
	if(!L)
	{
		printf("空表无表尾!\n");
		exit(0);
	}
	CopyGList(&t, L->a.ptr.tp);
	return t;
}



// 插入元素e作为广义表L的第一元素(表头,也可能是子表) 
int InsertFirst_GL(GList *L,GList e)
{
	GList p = (GList)malloc(sizeof(GLNode));
	if(!p)
		exit(0);
	p->tag = LIST;
	p->a.ptr.hp = e;
	p->a.ptr.tp = *L;
	*L = p;
	return 1;
}



// 删除广义表L的第一元素,并用e返回其值
int DeleteFirst_GL(GList *L,GList *e)
{ 
	GList p;
	*e = (*L)->a.ptr.hp;	
	p = *L;
	*L = (*L)->a.ptr.tp;	
	free(p);
	return 1;
}



// 利用递归算法遍历广义表L 
void Traverse_GL(GList L,void(*v)(AtomType))
{
	if(L) 
		if(L->tag == ATOM)
			v(L->a.atom);
		else
		{
			Traverse_GL(L->a.ptr.hp,v);
			Traverse_GL(L->a.ptr.tp,v);
		}
}

// 生成一个其值等于chars的串T
int StrAssign(SString T,char *chars)
{ 
	int i;
	if(strlen(chars) > MAXSTRLEN)
		return 0;
	else
	{
		T[0] = strlen(chars);
		 for(i = 1; i <= T[0]; i++)
			T[i] = *(chars + i - 1);
		return 1;
	}
}

// 由串S复制得串T
int StrCopy(SString T, SString S)
{
	int i;
	for(i = 0; i <= S[0]; i++)
		T[i] = S[i];
	return 1;
}


// 若S为空串,则返回1,否则返回0 
int StrEmpty(SString S)
{
	if(S[0] == 0)
		return 1;
	else
		return 0;
}



// 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 
int StrCompare(SString S,SString T)
{
	int i;
	for(i = 1; i <= S[0] && i <= T[0]; ++i)
		if(S[i] != T[i])
			return S[i] - T[i];
	return S[0]-T[0];
}

// 返回串的元素个数
int StrLength(SString S)
{
	return S[0];
}

// 将S清为空串
int ClearString(SString S)
{
	S[0] = 0;	// 令串长为零
	return 1;
}


// 用Sub返回串S的第pos个字符起长度为len的子串。
int SubString(SString Sub,SString S,int pos,int len)
{ 
	int i;
	if(pos < 1 || pos >S[0] || len < 0 || len > S[0]-pos+1)
		return 0;
	for(i = 1; i <= len; i++)
		Sub[i]=S[pos+i-1];
	Sub[0] = len;
	return 1;
}


// 将非空串str切割成两部分:hsub为第一个‘,‘之前的子串,str为之后的子串 
void sever(SString str,SString hstr) 
{
	int n,i, k;  
	SString ch,c1,c2,c3;
	n = StrLength(str);
	StrAssign(c1,",");
	StrAssign(c2,"(");
	StrAssign(c3,")");
	SubString(ch,str,1,1);
	for(i = 1,k = 0;i <= n && StrCompare(ch,c1) || k != 0; ++i)
	{ 
		SubString(ch, str, i, 1);
		if(!StrCompare(ch, c2))
			++k;
		else if(!StrCompare(ch,c3))
			--k;
	}
	if(i <= n)
	{
		SubString(hstr, str, 1, i-2);
		SubString(str, str, i, n - i + 1);
	}
	else
	{
		StrCopy(hstr, str);
		ClearString(str);
	}
}


// 广义表L。设emp="()" 
int CreateGList(GList *L, SString S)
{
	SString sub,hsub,emp;
	GList p,q;
	
	StrAssign(emp,"()");
	if(!StrCompare(S, emp))
		*L = NULL;	// 创建空表 
	else
	{
		*L = (GList)malloc(sizeof(GLNode));
		if(!*L)		// 建表结点 
			exit(0);
		if(StrLength(S) == 1)	// S为单原子 
		{
			(*L)->tag = ATOM;
			(*L)->a.atom = S[1]; // 创建单原子广义表 
		}
		else
		{
			(*L)->tag = LIST;
			p = *L;
			SubString(sub, S, 2, StrLength(S)-2); // 脱外层括号 
			do
			{	// 反复建n个子表 
				sever(sub, hsub); // 从sub中分离出表头串hsub 
				CreateGList(&p->a. ptr. hp, hsub);
				q = p;
				if(!StrEmpty(sub))	// 表尾不空 
				{
					p = (GLNode *)malloc(sizeof(GLNode));
					if(!p)
						exit(0);
					p->tag = LIST;
					q->a.ptr.tp = p;
				}
			}while(!StrEmpty(sub));
			q->a.ptr.tp = NULL;
		}
	}
	return 1;
}

// 打印原子 
void visit(AtomType e)
{
	printf("%c ", e);
}

int main()
{
	// 广义表的表示形式是，空表:(),单原子:a,表:(a,(b),c,(d,(e))) 
	char p[80] = {"(a,(b),c,(d,(e)))"};
	SString t;
	GList L,m;
	
	InitGList(&L);
	InitGList(&m);
	printf("空广义表L的深度 = %d\nL是否空？%d(1:是 0:否)\n\n",
		GListDepth(L), GListEmpty(L));
	StrAssign(t, p);
	CreateGList(&L, t);											// 创建广义表 
	printf("\n广义表L的长度 = %d\n", GListLength(L));
	printf("广义表L的深度 = %d \nL是否空？%d(1:是 0:否)\n",
		GListDepth(L), GListEmpty(L));
	printf("遍历广义表L：\n");
	Traverse_GL(L, visit);
	printf("\n\n复制广义表m = L\n");
	CopyGList(&m, L);
	printf("广义表m的长度 = %d\n", GListLength(m));
	printf("广义表m的深度 = %d\n", GListDepth(m));
	printf("遍历广义表m：\n");
	Traverse_GL(m,visit);
	DestroyGList(&m);
	m = GetHead(L);
	printf("\n\nm是L的表头，遍历广义表m：\n");
	Traverse_GL(m, visit);
	DestroyGList(&m);
	m = GetTail(L);
	printf("\n\nm是L的表尾，遍历广义表m：\n");
	Traverse_GL(m,visit);
	InsertFirst_GL(&m, L);
	printf("\n\n插入L为m的表头。遍历广义表m：\n");
	Traverse_GL(m,visit);
	printf("\n\n删除m的表头。遍历广义表m：\n");
	DestroyGList(&L);
	DeleteFirst_GL(&m, &L);
	Traverse_GL(m, visit);
	printf("\n");
	DestroyGList(&m);
	return 0;
}

原文：http://www.cnblogs.com/llguanli/p/6963191.html

内容总结

以上是互联网集市为您收集整理的数据结构之---C语言实现广义表头尾链表存储表示全部内容，希望文章能够帮你解决数据结构之---C语言实现广义表头尾链表存储表示所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1123357.html

来源：【匿名】

【上一篇】memcopy()函数c语言实现和汇编实现比较【下一篇】C语言MD5的源码实例详解

更多 ►

【数据结构之---C语言实现广义表头尾链表存储表示】教程文章相关的互联网学习教程文章

数据结构--快速、冒泡、选择排序C语言实现

#include<stdio.h> //快速排序 void quickSort(int a[],int left,int right) {int i,j,temp;i = left;j = right;temp = a[left];if(left>right)return;while(i!=j){while(a[j]>=temp &&j>i)j--;if(j>i)a[i++] = a[j];while(a[i]<=temp&&j>i)i++;if(j>i)a[j--] = a[i];}a[i] = temp;quickSort(a,left,i-1);quickSort(a,i+1,right); } //冒泡排序 void bubbleSort(int a[],int len) {int i,j,temp;for(i = 0;i<len;i++){ for(j = 0...

约瑟夫环（N个人围桌，C语言，数据结构）【图】

约瑟夫环问题（C语言、数据结构版）一、问题描述N个人围城一桌（首位相连），约定从1报数，报到数为k的人出局，然后下一位又从1开始报，以此类推。最后留下的人获胜。（有很多类似问题，如猴子选代王等等，解法都一样）二、思路分析　　　　（1）可将人的顺序简单编号，从1到N；　　　　（2）构造一个循环链表，可以解决首位相连的问题，同时如果将人的编号改为人名或者其他比较方便（3）将人的编号插入到结构体的Data域；...

【C语言数据结构】静态单链表【代码】

StaticLinkLinst.h#ifndef STATIC_LINKLIST_H #define STATIC_LINKLIST_Htypedef void StaticLinkListNode; //静态单链表节点 typedef void StaticLinkList; //静态单链表/* * 创建静态单链表 * @param capacity 静态单链表的最大容量 * @return 返回静态单链表的指针 */ StaticLinkList* StaticLinkList_Create(int capacity);/* * 销毁静态单链表 * @param list 静态单链表的指针 */ void StaticLinkList_Destr...

深入浅出数据结构C语言版（8）——后缀表达式、栈与四则运算计算器【代码】【图】

在深入浅出数据结构（7）的末尾，我们提到了栈可以用于实现计算器，并且我们给出了存储表达式的数据结构（结构体及该结构体组成的数组），如下：//SIZE用于多个场合，如栈的大小、表达式数组的大小#define SIZE 1000//表达式的单个元素所使用的结构体 typedef struct elem {int num = 0; //若元素存储操作数则num为该操作数char oper = ‘=‘; //若元素存储操作符则oper为该操作符bool IsNum = false; //用于判断元素是否为操作...

数据结构之C语言模拟整数数组实现【代码】

#include <stdio.h> #include <malloc.h> #include <stdlib.h>typedef struct Arr {int *pBase; //数组第一个元素地址int len; //数组长度int cnt; //当前有效元素数量} Array;void init_array(Array *, int); //初始化数组void show_array(Array *); //遍历打印数组bool is_empty(Array *); //判断数组是否空bool insert_array(Array *, int pos, int); //插入元素 pos表示在第几个元素前面插入bool append_array(Array *...

C语言数据结构入门记——二叉排序树的建立【代码】【图】

中序遍历二叉排序树输入一整数序列，建立二叉排序树，然后中序遍历。输入第一行为整数的个数n，第二行是具体的n个整数。建立二叉排序树，然后输出中序遍历的结果。输入示例：5 1 6 5 9 8输出：1 5 6 8 9 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct stu{int data;struct stu *lc,*rc; }bitree; bitree *creat(int n){int ch;bitree *q[100];//设置指针型数组构建队列 int front,rear;int num=0,i;b...

C语言数据结构-线性链表LinkList【代码】

1. 头结点表示链表中第一个结点的存储位置2. 最后一个结点的存储位置为空(NULL);#ifndef __LINKLLIST_H__ #define __LINKLLIST_H__#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLF -1 #define OVERFLOW -2#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10typedef int Status;typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next; }LNode, *LinkList;#endif #inclu...

数据结构之---C语言实现广义表头尾链表存储表示

//广义表的头尾链表存储表示 //杨鑫 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> #define MAXSTRLEN 40 ） typedef char SString[MAXSTRLEN+1]; typedef char AtomType; // 定义原子类型为字符型 typedef enum{ATOM, LIST // ATOM==0:原子 LIST==1:子表 } ElemTag; typedef struct GLNode {ElemTag tag; // 公共部...

数据结构之---C语言实现链式队列【图】

//链式队列的存储 //杨鑫 #include <stdio.h> #include <stdlib.h> typedef int QElemType;//定义节点 typedef struct QNode {QElemType data;struct QNode *next; }QNode, *QueuePtr;//定义指针 typedef struct {QueuePtr front;QueuePtr rear; }LinkQueue;//插入元素e进入队列 void en_Queue(LinkQueue *q, QElemType e) {QueuePtr temp = (QueuePtr)malloc(sizeof(QNode));if(temp){temp->data = e;temp->next = NULL;q->rear->...

数据结构之---C语言实现线索二叉树【图】

//线索二叉树，这里在二叉树的基础上添加了线索化 //杨鑫 #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef enum {Link,Thread} childTag; //Link表示结点，Thread表示线索 typedef struct bitNode {ElemType data;struct bitNode *lchild, *rchild;int ltag, rtag; } bitNode, *bitTree;bitTree pre; //创建全局变量，表示刚刚访问过的结点/* 创建二叉树，其输入必须按照前序遍历的次序。 T...

数据结构C语言循环链表练习之俄罗斯轮盘赌【代码】【图】

编译器：/******************************project :数据结构*function :循环链表之俄罗斯赌盘*Author :Rookie Uzz******************************copyright:2019.2.27 by UZT****************************/ 1 #include <stdio.h>2 #include <stdlib.h>3 #include "CListTest.h" 4 #include <time.h>5#define MAX_NUM 1000 //最大容量 6 7int Bet();8 9int main() 10{ 11 Bet(); 12return0; 13} 1415int Bet() 16{ 1...

数据结构之---C语言实现稀疏矩阵【图】

//稀疏矩阵三元组顺序表存储表示 //杨鑫 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef int ElemType; typedef struct {int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple;typedef struct {Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix;// 创建稀疏矩阵M int CreateSMatrix(TSMatrix *M) {int i,m,n;ElemType ...

C语言从入门到精通到实战学习路线图（指针/函数/数组/文件/标准库/接口/单片机/数据结构/算法/面试）

C语言是一门永不过时的编程开发语言，到处都离不开它，学好这门编程语言，用处极大。但是如何学好学精它，却让人很头疼，在学习过程中总会遇到各种各样的疑难杂症。收集整理了一些C语言编程学习必备的资料，涵盖：C语言学习路线图，编程工具，编程思维，指针，函数，数组，文件，标准库，常见问题解惑，数据结构，常用算法，算法分析，接口实现，单片机开发，程序实例，名题范例，面试宝典等等。认真看完这些，估计都能成为大神。...

仅用C语言可以构造出Python中Dict那种数据结构吗？

查找，插入，删除的时间复杂度能一样不？回复内容： CPython的dict就是用纯C实现的嗯：cpython/dict-common.h at master · python/cpython · GitHubcpython/dictobject.c at master · python/cpython · GitHubPython就是用c实现的，你说可以不可以？另外，c实现的这种哈希表+链表的二维数据结构，其实也有实例：memcached中的缓存就是同一种数据结构。只不过，在python里面，链表用于维持有序性（foreach/push/pop的时候用到），而...

数据结构——c语言寻找鞍点【代码】

设计并验证以下算法：若矩阵采用三元组顺序表表示，设计并验证找出矩阵所有马鞍点的算法。直接上代码： #include <stdio.h> #include <stdlib.h> #include <time.h>#define MAX 500 #define M 100 #define N 100typedef int arr_type;//储存行列值 typedef struct {int row;//从1 开始 int col;//从1 开始 arr_type value; }array;//储存三元组顺序表+总行数，总列数，总非零元素个数 typedef struct {array arr[MAX];//从0...

首页 / C语言 / 数据结构之---C语言实现广义表头尾链表存储表示

数据结构之---C语言实现广义表头尾链表存储表示

内容导读

内容图文

内容总结

内容备注

内容手机端

【数据结构之---C语言实现广义表头尾链表存储表示】教程文章相关的互联网学习教程文章

数据结构--快速、冒泡、选择排序C语言实现

约瑟夫环（N个人围桌，C语言，数据结构）【图】

【C语言数据结构】静态单链表【代码】

深入浅出数据结构C语言版（8）——后缀表达式、栈与四则运算计算器【代码】【图】

数据结构之C语言模拟整数数组实现【代码】

C语言数据结构入门记——二叉排序树的建立【代码】【图】

C语言数据结构-线性链表LinkList【代码】

数据结构之---C语言实现广义表头尾链表存储表示

数据结构之---C语言实现链式队列【图】

数据结构之---C语言实现线索二叉树【图】

数据结构C语言循环链表练习之俄罗斯轮盘赌【代码】【图】

数据结构之---C语言实现稀疏矩阵【图】

C语言从入门到精通到实战学习路线图（指针/函数/数组/文件/标准库/接口/单片机/数据结构/算法/面试）

仅用C语言可以构造出Python中Dict那种数据结构吗？

数据结构——c语言寻找鞍点【代码】

数据结构 - 相关标签

C语言 - 相关标签

链表 - 相关标签

C语言 - 技术教程分类

C语言 - 最新教程

C语言 - 最热教程