第5章 数据结构（Ｃ＋＋版）数组和广义3表

数据结构第5章数组第3讲1本章分为（2～3）讲第1讲

5.1

数组的基本概念

5.2

特殊矩阵

第2讲5.3稀疏矩阵5.3.1数组元素的三元组

5.3.2三元组顺序表供教师参考第2讲5.3.3十字链表5.5广义表

2稀疏矩阵A与它的十字链表存储图

回顾3十字链表概括如下:它有一个总表头结点，由hm指针来表示。以总表头结点为附加头结点与S个行列表头结点组成行列表头循环链表。通过S个行列表头结点，分别在m个行方向上组成以自己为附加头结点的，m个行循环链表。通过S个行列表头结点，又分别在n个列方向上组成以自己为附加头结点的，n个列循环链表。只要给定hm指针值，便可取得整个稀疏矩阵的全部信息。回顾42．十字链表的类定义

将3种不同用途的结点定义为同一种结构体Node，在它的6个子域中，其中一个子域定义为共用体。typedef

int

ElemType;structNode //定义十字链表的结点

{Introw;int

col; //行号和/列号

Node*down; //行方向指针

Node*right; //列方向指针

union //定义共用体

{Node*next;

//作表头结点，使用next

ElemType

val;//作数据结点，使用val

};};5//十字链表类定义classLinkedmat //十字链表类定义{private:Node*hm; //头指针

public:

Linkedmat(); //构造函数，初始化空十字链表

~Linkedmat(); //析构函数

voidCreat(); //创建一个十字链表

voidShow(); //输出显示十字链表};

在此，主要突出基本算法，十字链表的建立和输出。作为一个完整的链表类设计，其构造和析构函数十分重要不可或缺，它们的实现请读者自行解决。63．十字链表的主要算法介绍建立稀疏矩阵的十字链表的算法；输出十字链表的算法。

建立稀疏矩阵的十字链表的算法，实质上是一个以插入操作为主的复杂算法。大体上分为两步。首先建立总表头结点为主的行列表头结点组成的循环链表。然后逐一输入数据元素的三元组，将每个数据结点既要插入所在行的行循环链表，也要插入所在列的列循环链表。7建立十字链表算法-5.3voidLinkedmat::Creat(){ intm,n,s,r,c,v;Node*p，*q，*h[10];

cout<<"请输入要创建的矩阵维数->"<<endl<<endl;

cout<<"行数:";cin>>m;cout<<"列数:";cin>>n;s=m>n?m:n;//把行数和列数较大的赋值给sp=newNode;//动态分配Node空间

p->row=m;p->col=n;

hm=p;h[0]=p;//hm

和h[0]指向总表头结点

for(inti=1;i<=s;i++)//创建s个行列表头结点

{

p=newNode;p->row=0;p->col=0;

h[i]=p;p->right=p;p->down=p;h[i-1]->next=p;}

h[s]->next=hm; //组成行列表头的循环链表8

cout<<"三元组最多个数:"<<m*n<<endl;

intt;

cout<<"输入非零元素的个数t=?";

cin>>t;

cout<<"输入三元组格式(以空格分开):rcv(回车)"<<endl;

for(inti=0;i<t;i++) {cout<<"输入三元组:";cin>>r>>c>>v;p=newNode;p->row=r;p->col=c;p->val=v;q=h[r]; //在r行上寻找插入位置

while((q->right!=h[r])&&(q->right->col<c))q=q->right;p->right=q->right;q->right=p;

//插入第r行

q=h[c];//在c列上寻找插入位置

while((q->down!=cp[c])&&(q->down->row<r))q=q->down;p->down=q->down; q->down=p;

//插入第c列

}//fori}//算法结束9输出十字链表-算法5.4

算法5.4包含着对十字链表的遍历和查找操作。学习十字链表可以加深对单链表的认识。voidLinkedmat::Show(){Node*p，*p1;

int

i,j;

cout<<endl<<"十字链表的矩阵为:“<<endl;for(i=0;i<=hm->col;i++){cout<<"\t"<<i;}//输出各列的标号

cout<<endl;10for(i=1,p=hm->next;p!=hm;i++)//按行输出

{cout<<"\t"<<i; //输出每行的标号

for(j=1,p1=p->right;p1!=p;j++)//取每列数据

{if(j-1==p1->col){cout<<p1->val;p1=p1->right;}else{out<<"\t";}//不存在的元素，输出跳格

}//forj

cout<<endl;p=p->next;//指向下一行表头结点

}//foricout<<endl;}//算法结束输出十字链表-算法5.4115.5广义表

广义表不同于线性表，它的元素不仅允许为基本数据类型而且也允许为广义表。从基本数据元素的角度思考，它们之间已经不再是单纯的线性关系，而且还存在层次关系。在人工智能领域表处理语言LISP中，就是把广义表作为基本的数据结构。本节是从线性向非线性关系的过渡。125.5.1广义表的基本概念广义表简称为表，是n(n≥0)个元素的有限序列，记作：LS

=

(a1,a2,…,an)

其中，LS是广义表的名称;

元素ai(1≤i≤n)或者是基本数据元素，或者是广义表;n代表中元素的个数，称为广义表的长度。广义表的定义是递归的，广义表中可以包含广义表。

13广义表的基本概念按照惯例，用英文大写字母表示广义表的名称，小写字母表示基本数据元素。某个元素ai是一个基本数据时，称其为LS的一个原子，用小写字母表示；当ai不是一个基本数据元素时，则称它为广义表LS的子表，用大写字母表示。当广义表LS非空时，称第一个元素a1为LS的表头（Head）；而称其余元素组成的表(a2,…,an)为LS的表尾（Tail）。14广义表举例：①A=(),A是空表；表长度n为零。②B=(e),B有一个元素e，为原子；表长度为1。③C=(a,(b,c,d)),C有两个元素，分别为原子a和子表(b,c,d)；表长度为2。④D=(A,B,C),D有三个元素都是子表；表长度3。⑤E=(a,E),E有两个元素，一个是原子a，一个是表E；表长度为2，可以看出该表定义是递归的。广义表可以共享子表，且允许递归。广义表的元素之间存在次序关系，还存在层次关系。15广义表举例：

广义表中元素的最大层次数为表的深度。

元素的层次就是包含该元素的括号对的数目。

A=()表A深度为0；

B=(e)表B深度为1；

C=(a,(b,c,d))表C深度为2；

D=(A,B,C)表D深度为3；

E=(a,E)

表E深度为无穷∞；16再如广义表：F=(x,y,(z,(t)),u)

数据元素x,y和u在第一层；数据元素z在第二层；数据元素t在第三层。广义表F深度为3。该表有4个元素，表长度为4。

A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E),

又义可知，任一个非空广义表其表头可能是原子，也可能是表，而其表尾必定为表。例如：Head(D)=ATail(D)=(B,C)

Head(C)=aTail(C)=((b,c,d))175.5.2广义表的存储结构由于广义表（a1,a2,…,an）中的数据元素可以具有不同的结构(或是原子，或是表)，难以用顺序存储结构表示，通常采用链式存储结构，每个元素用一个结点表示。广义表的存储结构主要有头尾链表存储结构和扩展线性链表结构两种表示方法。现仅对头尾链表存储结构加以介绍

18广义表的头尾链表存储结构：若广义表不空，可分解成表头和表尾；一对表头和表尾可唯一确定广义表。①表结点：3个域，标志域tag（1是表）、指向表头的指针hp和指示表尾的指针tp。②原子结点：两个域，标志域tag（0是原子）和数据值域atom。191．广义表元素结点的结构struct

glnode{inttag; //标志域0/1，用来区分原子和表

union //共用体

{struct

ptrtp{glnode*hp,*tp;//hp指向表头元素，tp指向表尾

}

ptr;//对于表结点使用ptrcharatom;//对于原子结点则使用atom};};glnode*p;处理表结点:p->tag//值为1p->ptr.hp//指向表头p->ptr.tp//指向表尾glnode*q;处理原子点结：q->tag //值为0q->atom//数据元素值202．绘制广义表的结构图

对于：A=()，空表仅用A=NULL来表示，而不分配结点，也不必画图。

对于：B=(e)

B指向一个表结点，B->tag=1。

B->ptr.hp应指向表头，由于表头是基本数据元素e，它指向一个原子结点e。

B->ptr.tp应指向表尾，B表尾为空，所以B->ptr.tp为NULL。由图可以理解，该表长度为1，深度也为1。21广义表：G=(b,c,d)

G指向一个表结点，G->tag=1。

G->ptr.hp应指向表头，G表头是一个基本数据元素b，因此G->ptr.hp指向一个值为b的原子结点。

G->ptr.tp应指向表尾，G表的表尾是除去a之外剩余元素构成的表（b,c），所以G->ptr.tp指向一个表结点。设q=G->ptr.tp，因为(c,d)的表头是c，所以q->ptr.hp指向值为c的原子结点。同理，q->ptr.tp应指向（c,d）的表尾，即（d），所以q->ptr.tp也指向一个表结点。设p=q->ptr.tp，因为(d)的表头是d，所以p->ptr.hp指向值为d的原子结点。又因为（d）的表尾是空，所以p->ptr.tp为空NULL。由图可直观地看出，该表长度为3，深度为1。建议教师不打字幕而对图详细讲解。22广义表：C=(a,(b,c,d))

C指向一个表结点，所以C->tag=1。

C->ptr.hp指向表头，是一个值为a的原子结点。

C->ptr.tp指向表尾，即剩余元素(b,c,d)构成的表((b,c,d))，因此C->ptr.tp指向一个表结点。因为表((b,c,d))的表头素是(b,c,d)，也是G表，所以C->ptr.tp->ptr.hp指向G表。又因为表((b,c,d))的表尾是空，所以C->ptr.tp->ptr.tp为NULL。

C表的长度为2。表的深度为2。建议教师不打字幕而对图详细讲解。23广义表：D=(A,B,C)

D指向表结点，所以D->tag=1。

D->ptr.hp指向表头，即是A表，所以为NULL。D->ptr.tp指向表尾，即是（B,C），所以指向一个表结点。

D->ptr.t