数据结构之用C++实现广义表

内容导读

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

内容图文

　　广义表,相对于链表较复杂,相对于树又较简单....用来过渡顺序表和树是非常好的选择.

　　废话不多说,一言不合就贴代码.

/*
*文件说明:广义表相关声明及定义
*作者:高小调
*日期:2016-12-12
*集成开发环境:Microsoft Visual Studio 2010 
*/
#ifndef __GENERALLIST_H__
#define __GENERALLIST_H__
#include<assert.h>
enum Type{
	HEAD,
	SUB,
	VALUE
};
struct GeneralListNode{
	Type type;
	union{
		char value;
		GeneralListNode *sublink;
	};
	GeneralListNode *next;
	GeneralListNode(Type t,const char v = 0)
		:type(t)
		,next(0){
			if(t == HEAD || t ==VALUE){
				value = v;
			}else if(t == SUB){
				sublink = 0;
			}else {
				assert(false);	
			}
	}
};

class GeneralList{
typedef GeneralListNode Node;
public:
	//构造函数
	GeneralList(const char *s){
		_head = _CreateList(s);
	}
	//拷贝构造
	GeneralList(const GeneralList &g){
		_head = _Copy(g._head);
	}
	//赋值运算符重载
	GeneralList &operator=(const GeneralList &g){
		if(_head!=g._head){		//不是自己给自己赋值
			GeneralList temp(g);
			swap(_head,temp._head);
		}
	}
	//析构函数
	~GeneralList(){
		if(_head!=NULL){
			_Destory(_head);
			_head = NULL;
		}
	}
public:
	//打印广义表
	void Print(){
		_Print(_head);
		cout<<endl;
	}
	//广义表数据个数
	size_t Size(){
		return _Size(_head);
	}
	//广义表深度
	size_t Depth(){
		return _Depth(_head);
	}
protected:
	//拷贝广义表
	Node * _Copy(Node* head){
		Node *NewHead = new Node(HEAD);
		Node *Tail = NewHead;
		Node *cur = head;
		while(cur){
			if(cur->type == VALUE){							//数据节点
				Tail->next = new Node(VALUE,cur->value);	//创建新节点,添加至尾节点
				Tail = Tail->next;							//尾节点后移
				cur = cur->next;							//被拷贝节点后移
			}else if(cur->type == SUB){						//子表节点
				Node *NewSub = new Node(SUB);				//创建新子表节点
				Tail->next = NewSub;						//添加至尾节点
				Tail = Tail->next;							//尾节点后移
				NewSub->sublink = _Copy(cur->sublink);		//递归拷贝子节点
				cur = cur->next;							//被拷贝节点后移
			}else if(cur->type == HEAD){					//头节点
				cur = cur->next;							//被拷贝节点后移
			}else{
				assert(false);			//出错!
			}
		}
		return NewHead;
	}
	//交换
	void _Swap(Node* &l,Node *&r){
		Node *tmp = l;
		l = r;
		r = tmp;
	}
	//销毁
	void _Destory(Node *head){
		Node *cur = head;
		while(cur){
			if((cur->type == VALUE)	
				||(cur->type == HEAD)){		//当前节点为头节点或数据节点
				Node *del = cur;			//保存当前节点
				cur = cur->next;			//当前节点后移
				delete del;					//删除节点
			}else if(cur->type == SUB){		//当前节点为子表
				Node * del = cur;			//保存当前节点
				cur = cur->next;			//当前节点后移
				_Destory(del->sublink);		//递归销毁子表里的数据	
				delete del;					//销毁子表
			}else{
				assert(false);				//程序运行出错!
			}
			
		}
	}
	//判断是否为数据
	bool _IsValue(const char s){
		if((s>=‘0‘&&s<=‘9‘)
			||(s>=‘a‘&&s<=‘z‘)
			||(s>=‘A‘&&s<=‘Z‘)){
			return true;
		}
		return false;
	}
	//递归创建广义表
	Node *_CreateList(const char * &s){
		assert(*s==‘(‘);						//断言字符串s第一个字符是(
		++s;									//跳过(进入数据部分
		Node *head = new Node(HEAD);			//创建头节点
		Node *Tail = head;						//作为尾节点,来插入新数据
		while(*s){
			if(_IsValue(*s)){						//数据项
				Tail->next = new Node(VALUE,*s);	//创建数据节点
				Tail = Tail->next;					//尾节点后移
				++s;
			}else if(*s == ‘(‘){				//子表项
				Node *NewNode = new Node(SUB);	//创建子表节点
				Tail->next = NewNode;			//插入尾部
				Tail = Tail->next;				//尾部后移
				NewNode->sublink = _CreateList(s);	//递归创建子表数据节点
			}else if(*s ==‘)‘){						//数据结束
				++s;
				return head;						//返回头节点
			}else{
				++s;								//遇到逗号跳过
			}
		}
		return head;
	}
	//递归打印广义表
	void _Print(Node *head){
		Node * cur = head;
		while(cur){
			if(cur->type == HEAD){			//头节点
				cout<<"(";
			}else if(cur->type == VALUE){	//值节点
				cout<<cur->value;
				if(cur->next!=NULL){		//不是最后一个元素
					cout<<",";				//以逗号分隔
				}
			}else if(cur->type == SUB){		//子表项
				_Print(cur->sublink);		//递归打印子表
				if(cur->next!=NULL){		//不是最后一项数据
					cout<<",";				//以逗号分隔
				}
			}else{
				assert(false);
			}
			cur = cur->next;
		}
		cout<<")";
	}
	//递归获取广义表数据个数
	size_t _Size(Node *head){
		Node *cur = head;
		size_t ret = 0;
		while(cur){
			if(cur->type ==VALUE){			//当前为值节点
				++ret;						//数据个数+1
			}else if(cur->type ==SUB){
				ret += _Size(cur->sublink);	//递归求取子表数据个数
			}else{
				//头节点
			}
			cur = cur->next;
		}
		return ret;
	}
	//递归求广义表深度
	size_t _Depth(Node *head){
		Node *cur = head;
		size_t MaxDepth = 1;						//当前深度为1
		while(cur){
			if(cur->type == SUB){					//遇到子表
				size_t Depth = _Depth(cur->sublink);//递归求子表深度
				if(MaxDepth<Depth+1){				//如果子表深入大于当前值
					MaxDepth = Depth+1;				//更新最大深入
				}
			}
			cur = cur->next;
		}
		return MaxDepth;							//返回最大深度
	}
private:
	Node * _head;
};
#endif

/*
*文件说明:测试文件
*作者:高小调
*日期:2016-12-12
*集成开发环境:Microsoft Visual Studio 2010 
*/
#include<iostream>
using namespace std;
#include"GeneralList.h"
void GeneralListTest(){
	const char * const str1 = "(a)"; 
	GeneralList g1(str1);
	g1.Print();
	cout<<"Size = "<<g1.Size()<<endl;
	cout<<"Depth = "<<g1.Depth()<<endl;

	const char * const str2 = "(a,b)"; 
	GeneralList g2(str2);
	g2.Print();
	cout<<"Size = "<<g2.Size()<<endl;
	cout<<"Depth = "<<g2.Depth()<<endl;

	const char * const str3 = "(a,b,(c,d))"; 
	GeneralList g3(str3);
	g3.Print();
	cout<<"Size = "<<g3.Size()<<endl;
	cout<<"Depth = "<<g3.Depth()<<endl;
	
	const char * const str4 = "((e,(f),h))"; 
	GeneralList g4(str4);
	g4.Print();
	cout<<"Size = "<<g4.Size()<<endl;
	cout<<"Depth = "<<g4.Depth()<<endl;

	const char * const str5 = "(((1,2)),((3,4)))";
	GeneralList g5(str5);
	g5.Print();
	cout<<"Size = "<<g5.Size()<<endl;
	cout<<"Depth = "<<g5.Depth()<<endl;

	cout<<"////////拷贝构造//////"<<endl<<endl;
	//(a)
	GeneralList g6(g1);
	g6.Print();
	cout<<"Size = "<<g6.Size()<<endl;
	cout<<"Depth = "<<g6.Depth()<<endl;
	//(a,b)
	GeneralList g7(g2);
	g7.Print();
	cout<<"Size = "<<g7.Size()<<endl;
	cout<<"Depth = "<<g7.Depth()<<endl;

	//(a,b,(c,d))
	GeneralList g8(g3);
	g8.Print();
	cout<<"Size = "<<g8.Size()<<endl;
	cout<<"Depth = "<<g8.Depth()<<endl;

	GeneralList g9(g4);
	g9.Print();
	cout<<"Size = "<<g9.Size()<<endl;
	cout<<"Depth = "<<g9.Depth()<<endl;

	GeneralList g10(g5);
	g10.Print();
	cout<<"Size = "<<g10.Size()<<endl;
	cout<<"Depth = "<<g10.Depth()<<endl;
}
int main(){
	GeneralListTest();
	return 0;
}

　　总结:

　　第一次接触这个,还确实有点难办,写得我脑袋都透支了,还专门打了几把LOL休息了一下....

　　这个东西并不是有多难,仅仅是因为递归程序,极其难于调试.当程序出问题时,调试比较让人抓狂!

　　还有一点就是,个人太钻牛角尖.有时候及时接受别人的知识,然后纳入自己的知识体系,比自己死磕要快得多....

原文：http://www.cnblogs.com/shujujiegou/p/6165401.html

内容总结

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

内容备注

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

内容手机端

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

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

来源：【匿名】

【下一篇】c++有个库什么的吗?

更多 ►

【数据结构之用C++实现广义表】教程文章相关的互联网学习教程文章

广义表,相对于链表较复杂,相对于树又较简单....用来过渡顺序表和树是非常好的选择.　　废话不多说,一言不合就贴代码./* *文件说明:广义表相关声明及定义 *作者:高小调 *日期:2016-12-12 *集成开发环境:Microsoft Visual Studio 2010 */ #ifndef __GENERALLIST_H__ #define __GENERALLIST_H__ #include<assert.h> enum Type{HEAD,SUB,VALUE }; struct GeneralListNode{Type type;union{char value;GeneralListNode *sublink;};Gene...

C++ _数据结构 _线性表的顺序存储【代码】【图】

#ifndef __MY_SEQLIST_H__ #define __MY_SEQLIST_H__typedef void SeqList; typedef void SeqListNode;//链表创建 SeqList* SeqList_Create(int capacity);//链表销毁void SeqList_Destroy(SeqList* list);////链表清空void SeqList_Clear(SeqList* list);//链表长度int SeqList_Length(SeqList* list);//链表容量 int SeqList_Capacity(SeqList* list);//链表在某一个位置插入元素int SeqList_Insert(SeqList* list, Seq...

数据结构(c++)写法【代码】【图】

单链表的建立本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。输入以-1 作为结束 1 #include<bits/stdc++.h>2usingnamespace std;3 4 typedef struct LNode *List;5struct LNode6{7int data;8 LNode *next; 9 }; 1011void InitList(List &L) 12{ 13 L = new LNode; 14 L->next = NULL; 15} 1617void CreatList(List &L) 18{ 19 List r,s; 20 s = L; 21int a; 22while(1...

c++数据结构 --unorder_map【代码】【图】

#include <iostream> #include <unordered_map> usingnamespace std; class Book { private:string num;string name; public:Book() {};Book(string num,string name) { this ->name = name;this ->num = num;};string getNum() { return num;};string getName() { return name;}; }; int main() {unordered_map<string,Book>lib;Book b("001","高级语言程序设计") ;lib[b.getNum()] = b;unordered_map<string,Book>::iterator it;...

noi题库（noi.openjudge.cn） 3.9数据结构之C++STL T1——T2【代码】【图】

T1 1806:词典描述你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是，你有一本词典可以帮助你。输入首先输入一个词典，词典中包含不超过100000个词条，每个词条占据一行。每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，然后给出一个由外语单词组成的文档，文档不超过100000行，而且每行只包括一个外语单词。...

【C/C++】实现数据结构广义表【代码】

1. 广义表的定义每个元素可以为Atom，原子，也可以为线性表。线性表的推广。线性表元素有唯一的前驱和后继，为线性表，而广义表是多层次的线性表表头：第一个元素，可能是原子，可能是广义表表尾：除了第一个元素，剩余的元素，所构成的广义表举例： A = (a,b,(c,d),e) head(A) = a tail(A) = (b,(c,d),e) 遍历操作：取表头，取表尾，取表头.. 长度：最外层的...

字符串数据结构算法题-C++【代码】

1）最长不重复子串使用string和vector<string>string FindLongestNonRepeatSubstring(string str) {if (str.empty()) return"";string tmp;//存放临时不重复的子串vector<string> svec;//存放所有不重复的子串int start = 0;//标记每次开始查找子串的下标int pos = -1; //查找当前字符在子串中的位置下标tmp.push_back(str[0]);for (unsigned int i = 1; i < str.size(); ++i){pos = tmp.find(str[i]);if (pos == -1){tmp.push_bac...

C++数据结构知识点【代码】【图】

数据结构(data stucture)的定义：数据结构由数据元素的集合和该集合中数据元素之间的关系组成。即{D,R}。线性结构，即线性表(linearlist). ---数组(array)，文件，栈(stack)，队列(queue)，优先级队列非线性结构 ---集合，图C++类默认访问级别是privatestruct默认访问级别是 public 这可以说是他们的惟一区别。union默认访问级别也是 public流是个简单的字符序列cout<<endl; 输出一个换行符，并清空流。C++的输入输出：void main...

【数据结构】3、模拟银行窗口排队叫号系统——C++【图】

这里我们模拟一下银行排队叫号系统的实现：假设一个银行有4个窗口对外接待客户。由于每个窗口在某一时刻只能接待一个客户，在客户众多的时候需要排队，对于刚进入银行的客户，如果某个窗口正空闲，则可上前办理业务，如果所有窗口都不空闲则排在人数最少的窗口。现在要求模拟银行的某一时间段内的4个窗口的客户排队情况。这里客户到达的时刻和办理业务的时间都是随机的。首先我们银行发生事件，我们得有一个类表示事件对象/* *功...

【C++/数据结构】单链表的基本操作【图】

#pragma once #ifndef _CLIST_H_ #define _CLIST_H_#include <iostream> #include <assert.h> using namespace std;template<class Type> class List;typedef enum { FALSE, TRUE }Status;template<class Type> class ListNode {friend class List<Type>; public:ListNode() :data(Type()), next(NULL){}ListNode(Type d, ListNode<Type> *n = NULL): data(d), next(n){}~ListNode(){}void setData(const Type &d){data = d;}Type ...

C++数据结构——队列【代码】【图】

C++数据结构——队列目录 1、简介 2、基本结构 3、基本操作简介像栈一样，队列也是一种线性表。它允许在表的一端插入数据，在另一端删除元素。插入元素的这一端称之为队尾。删除元素的这一端我们称之为队头，它的特点是先进先出。首先我们来思考一下队列这种数据结构使用什么表的创建方式比较好，是头插法？尾插法？之前我们有提到，队列在队头删除元素，在队尾插入元素，如果是头插法，那么在头结点这边进行插入，在另一边进行删除...

数据结构C++版-线性表【代码】【图】

PS：资料来源慕课网视频。一、什么是线性表线性表是n个数据元素的有限序列。分类：二、补充知识点1、栈和队列有出操作、入操作，对应线性表（数组）为插入元素和删除元素，而线性表中要获取指定元素值可直接使用getelem()函数，获取后并不删除元素，可重复获取。【与只能使用一次的栈、队列有区别】 2、顺序表：遍历和寻址非常快，插入、删除效率低。 3、《链表算法说明》课程评论：静态链表基于数组，动态链表基于结构体，所...

【C/C++】c/c++基础加进阶视频教程（含数据结构和设计模式）【图】

收集整理了c和c++从基础到进阶的视频教程，共26.4G，欢迎下载。至于学习c++要不要先学c的问题也是见仁见智，个人觉得在c语言的基础上学c++会更有效率一些。这套视频教程包含了c语言课程，麻油们可以根据自己的需要选择是否要先学c。创一个小群，供大家学习交流聊天如果有对学C++方面有什么疑惑问题的，或者有什么想说的想聊的大家可以一起交流学习一起进步呀。也希望大家对学C++能够持之以恒C++爱好群，如果你想要学好C++最好加入一...

C++八股文分享---数据结构其二---哈希表【代码】

C++八股文分享—数据结构其二—哈希表前言什么是哈希表？搜索二叉树对值的查找是通过从根节点开始，逐个节点与目标值做比较，向下查找，直至找到目标值或是到达根节点未查找到，时间复杂度为O(logn)。而哈希表，则是通过将value与key成对绑定，将key带入哈希函数，即可得到目标值的存放地址，从而得到目标值，在不考虑哈希冲突的情况下，时间复杂度为O(1)。哈希表其实可以理解为一个特殊的数组。我们通常使用的数组，通过下标0...

队列的C++数组实现方法(队列--数据结构)【代码】

队列的C++实现方法(队列–数据结构) 1.队列结构 #define MaxSize //储存数据元素的最大个数 struct QNode {ElementType Data[MaxSize];int rear;int front; }; typedef struct QNode *Queue; 2.入队列 void AddQ(Queue PtrQ, ElementType item) {if((PtrQ->rear+1)%MaxSize==Ptr->front){printf("队列满")；return;}PtrQ->rear=(PtrQ->rear+1)%MaxSize;PtrQ->Data[Ptr->rear]=item; } 3.出队列 ElementType DeleteQ(Queue PtrQ) {i...