数据结构组广义表

数据结构-⼴义表⼴义表简称表，是线性表的推⼴，表中元素可以是数据元素（原⼦），也可以是⼦表。

⼴义表的表头（head）是表中第⼀个表元素、表尾（tail）是除了表头外其它元素组成的表。

⾸先要对⼴义表结点类GenListNode和返还值的结构类Item进⾏定义。

它们都有⼀个⽤来标明结点类型的标志域utype、⼀个信息域info。

此外，⼴义表结点类还多了⼀个尾指针tlink指向下⼀个结点。

utype为0时为⼴义表专⽤的附加头结点，info存放引⽤计数refutype为1时为原⼦结点、info存放数据值valueutype为2时为⼦表结点，info存放指向⼦表表头的指针hlink这种存储表⽰中，⼴义表中的所有表，⽆论是哪⼀层的⼦表，都带有⼀个附加头结点，空表也不例外所有位于同⼀层的表元素，在其存储表⽰中也在同⼀层最⾼⼀层的表结点个数（除附加头结点外）即为表的长度#include <iostream>#include <assert.h>#include <stdlib.h>using namespace std;template <class T>struct Items{ //返回值的类结构定义int utype; //标志域union{int ref; //utype=0，存放引⽤计数T value; //utype=1，存放数值GenListNode<T> *hlink; //utype=2.存放指向⼦表的指针} info;Items():utype(0),info.ref(0){} //构造函数Items（Items<T>& RL）{utype=RL.utype;info=;} //复制构造函数}template <class T>struct GenListNode{ //⼴义表结点类定义public:GenListNode():utype(0),tlink(NULL),info.ref(0){}GenListNode(GenListNode<T>& RL){utype=RL.utype;tlink=Rl.tlink;info=;}private:int utype;GenListNode<T> *tlink; //⽐返回值的类结构多了⼀个tlink指针union{int ref;T value;GenListNode<T> *tlink;} info;}template <class T>class Genlist{public:Genlist();~Genlist();bool Head(Items& x);bool Tail(Genlist<T>& It);GenListNode<T> *First();GenListNode<T> *Next(GenListNode<T> *elem);void Copy(const Genlist<T>& R);int Length();int depth();friend istream& operator>>(istream& in,Genlist<T>& L);private:GenListNode<T> *first; //⼴义表头指针GenListNode<T> *Copy(GenListNode<T> *ls);int Length(GenListNode<T> *ls);int depth(GenListNode<T> *ls);bool equal(GenListNode<T> *s,GenListNode<T> *t); //判断s和t为表头的两个表是否相等void Remove(GenListNode<T> *ls);void Createlist(istream& in,GenListNode<T> *&ls);}template <class T>Genlist<T>::Genlist(){ //构造函数first=new GenlistNode;assert(first!=NULL);}//Head⽅法返回bool值，通过引⽤变量x返回是⼴义表第⼀个元素（Item类型的对象）；template <class T>bool Genlist<T>::Head(Items<T>& x){//若⼴义表⾮空，则通过x返回其第⼀个元素的值，否则函数没有意义if(first->tlink==NULL) return false;else{x.utype=first->tlink->utype;=first->tlink->info;return true;}}template <class T>bool Genlist<T>::Tail(Genlist<T>& It){//若⼴义表⾮空，则通过It返回⼴义表除表头元素以外其他元素组成的表，否则函数没有意义if(first->tlink==NULL) return false;else{It.first->utype=0;It.first->info.ref=0;It.first->tlink=Copy(first->tlink->tlink);return true;}}//First⽅法返回的是指向⼴义表第⼀个元素（GenlistNode类型的对象）的指针template <class T>GenlistNode<T> *Genlist<T>::First(){if(first->tlink==NULL)return NULL;else return first->tlink;}template <class T>GenlistNode<T> *Genlist<T>::Next(GenlistNode<T> *elem){ //返回表元素elem的直接后继元素if(elem->tlink==NULL) return NULL;else return elem->tlink;}⼴义表的遍历可以⽤如下⽅法：template <class T>struct Items {int mark;int utype;union{char *LName; //附加头结点的info域改为了表名T value;GenListNode<T> *hlink;}info;Items():mark(0),utype(0),info.LName('\0'){}Items(Items<T>& RL){mark=Rl.mark;utype=RL.utypr;info=;}}template <class T>struct GenListNode {public:GenListNode():mark(0),utype(0),tlink(NULL),info.LName('\0'){}GenListNode(GenListNode<T>& RL){mark=RL.mark; utype=RL.utype; tlink=RL.tlink; info=;} int getMark(GenListNode<T> *elem){return elem->mark;}int getType(GenListNode<T> *elem){return elem->utype;}int getListName(GenListNode<T> *elem){return elem->info.LName;}T getValue(GenListNode<T>* elem){return elem->info.value;}GenListNode* gettlink(GenListNode<T>* elem){return elem->tlink;}GenListNode* gethlink(GenListNode<T>* elem){return elem->info.hlink;}private:int mark;int utype;GenListNode<T> *tlink;union{char *LName;T value;GenListNode<T> *hlink;}info;}template GenList{public:GenList();~GenList(){Remove(first);}bool Head(Items& x);bool Tail(GenList<T> &lt);GenListNode<T> *First(){return first;}GenListNode<T> *Next(GenListNode<T> *elem){return elem->tlink;} void Traverse(); //⾮递归遍历private:GenListNode<T> *first;void Traverse(GenListNode<T> *ls); //递归遍历}template <class T>void GenList::Traverse(){Stack<GenListNode<T>*> st;GenListNode<T> *ls=first;while (ls!=NULL) {ls->mark=1;if (ls->utype==2){ //⼦表结点if (ls->info.hlink->mark==0){st.Push(ls->tlink;) //暂时先把⼦表结点的右结点⼊栈ls=ls->hlink;}else { //⼦表已经遍历过cout<<ls->info.hlink->info.LName;if(ls->tlink!=NULL){cout<<',';ls=ls->tlink;}}}else {if (ls->utype==0) cout<<ls->info.LName<<'('; //表头结点else if (ls->utype==1){ //原⼦结点cout<<ls->info.value;if(ls->tlink!=NULL) cout<<',';}if(ls->tlink==NULL){cout<<')';if(!st.isEmpty()){st.Pop(ls);if(ls!=NULL) cout<<',';else cout<<')';}}else ls=ls->tlink;}}}template <class T>void GenList::Traverse(GenListNode<T> *ls){if(ls!=NULL){ls->mark=1;if (ls->utype==0) cout<<ls->info.LName<<'('; //表头结点else if (ls->utype==1) { //原⼦结点cout<<ls->info.value;if (ls->tlink!=NULL) cout<<',';}else if (ls->utype==2) { //⼦表结点if (ls->info.hlink->mark==0) Traverse(ls->info.hlink);else cout<<ls->info.hlink->info.LName; //⼦表已经遍历过if (ls->tlink!=NULL) cout<<',';}Traverse(ls->tlink);}else cout<<')';}。

第6章广义表z6.1 广义表的基本概念z6.2 广义表的存储结构z6.3 广义表的操作算法16.1 广义表的基本概念广义表（列表）的概念-n( ≥0 )个表元素组成的有限序列，记作LS= ( a1, a1, a2, …, a n)LS是表名，a i是表元素，它可以是单个元素(称为原子) ，可以是表(称为子表) 。

n为表的长度。

n= 0 的广义表为空表。

n> 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。

2广义表举例：（1）A=（）（2）B=（e）（3）C=（a, (b, c, d) )（4）D=（A，B，C）（5）E= (a , E）9任意一个非空广义表，均可分解为表头和表尾。

9对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。

3广义表的基本操作：•结构的创建和销毁InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);•状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);•插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);•遍历Traverse_GL(L, Visit());66. 2 广义表的存储结构z由于广义表中的元素不是同一类型，因此难以用顺序结构表示，通常采用链接存储方法存储广义表，并称之为广义链表。

z由于广义表中有两种数据元素，原子或子表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。

z下面介绍一种广义表的链式存储结构。

78扩展的线性链表表示法：-子表结点由三个域组成：标志域、表头指针域和指向下一个元素的指针域；-原子结点的三个域为：标志域、值域和指向下一个元素的指针域。

数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。

5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。

其数据元素通常也称为数组元素。

数组地每个数据元素都有一个序号,称为下标。

可以通过数组下标访问数据元素。

数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。

如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。

如aij表示第i行j列地数据元素。

数组也是一种线性数据结构,它可以看成是线性表地一种扩充。

一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。

如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。