《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第5章 数组和广义表-3》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第5章 数组和广义表-3（27页珍藏版）》请在金锄头文库上搜索。
1、1,数据结构,第5章 数组 第3讲,2,本章分为（23）讲,第1讲 5.1 数组的基本概念 5.2 特殊矩阵,第2讲 5.3 稀疏矩阵 5.3.1 数组元素的三元组 5.3.2 三元组顺序表,供教师参考,第2讲 5.3.3 十字链表 5.5 广义表,3,稀疏矩阵A 与它的十字链表存储图,回顾,4,十字链表概括如下:,它有一个总表头结点，由hm指针来表示。 以总表头结点为附加头结点与S个行列表头结点组成行列表头循环链表。 通过S个行列表头结点，分别在m个行方向上组成以自己为附加头结点的，m个行循环链表。 通过S个行列表头结点，又分别在n个列方向上组成以自己为附加头结点的，n个列循环链表。 只要给
2、定hm指针值，便可取得整个稀疏矩阵的全部信息。,回顾,5,2十字链表的类定义,将3种不同用途的结点定义为同一种结构体Node，在它的6个子域中，其中一个子域定义为共用体。 typedef int ElemType; struct Node /定义十字链表的结点 Int row; int col; /行号和/列号 Node * down; /行方向指针 Node * right; /列方向指针 union /定义共用体 Node * next; /作表头结点，使用next ElemType val; /作数据结点，使用val ; ;,6,/十字链表类定义,class Linkedmat /十字链
3、表类定义 private: Node* hm; /头指针 public: Linkedmat(); /构造函数，初始化空十字链表 Linkedmat(); /析构函数 void Creat(); /创建一个十字链表 void Show(); /输出显示十字链表 ; 在此，主要突出基本算法，十字链表的建立和输出。作为一个完整的链表类设计，其构造和析构函数十分重要不可或缺，它们的实现请读者自行解决。,7,3十字链表的主要算法,介绍建立稀疏矩阵的十字链表的算法；输出十字链表的算法。 建立稀疏矩阵的十字链表的算法，实质上是一个以插入操作为主的复杂算法。大体上分为两步。 首先建立总表头结点为主的行列表头
4、结点组成的循环链表。 然后逐一输入数据元素的三元组，将每个数据结点既要插入所在行的行循环链表，也要插入所在列的列循环链表。,8,建立十字链表 算法-5.3,void Linkedmat:Creat() int m, n, s, r, c, v; Node* p，* q，*h10; cout “ m; cout n; s = m n ? m : n; /把行数和列数较大的赋值给 s p = new Node; /动态分配Node空间 p-row = m; p-col = n; hm = p; h0 = p; /hm 和h0指向总表头结点 for ( int i = 1; i row = 0; p
5、-col = 0; hi = p; p-right = p; p-down = p; hi-1-next = p; hs-next = hm; /组成行列表头的循环链表,9,cout t; cout r c v; p = new Node; p-row = r; p-col = c; p-val = v; q = hr; /在r行上寻找插入位置 while(q-right != hr) /插入第c列 /for i /算法结束,10,输出十字链表-算法 5.4,算法 5.4包含着对十字链表的遍历和查找操作。学习十字链表可以加深对单链表的认识。 void Linkedmat:Show() Node
6、* p，* p1; int i,j; cout col; i+ ) cout “t“ i; /输出各列的标号 cout endl;,11,for ( i = 1, p = hm-next; p != hm; i+ ) /按行输出 cout right; p1 != p; j+ ) /取每列数据 if ( j- 1 = p1-col ) cout val; p1 = p1-right; else out next; /指向下一行表头结点 /fori cout endl; /算法结束,输出十字链表-算法 5.4,12,5.5 广义表,广义表不同于线性表，它的元素不仅允许为基本数据类型而且也允许为广
7、义表。 从基本数据元素的角度思考，它们之间已经不再是单纯的线性关系，而且还存在层次关系。 在人工智能领域表处理语言LISP中，就是把广义表作为基本的数据结构。 本节是从线性向非线性关系的过渡。,13,5.5.1 广义表的基本概念,广义表简称为表，是n (n0)个元素的有限序列，记作： LS = (a1,a2,an) 其中，LS是广义表的名称; 元素ai(1in)或者是基本数据元素，或者是广义表; n代表中元素的个数，称为广义表的长度。 广义表的定义是递归的，广义表中可以包含广义表。,14,广义表的基本概念,按照惯例，用英文大写字母表示广义表的名称，小写字母表示基本数据元素。 某个元素ai是一个
8、基本数据时，称其为LS的一个原子，用小写字母表示； 当ai不是一个基本数据元素时，则称它为广义表LS的子表，用大写字母表示。 当广义表LS非空时，称第一个元素a1为LS的表头（Head）；而称其余元素组成的表(a2,an)为LS的表尾（Tail）。,15,广义表举例：, 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，可以看出该
9、表定义是递归的。 广义表可以共享子表，且允许递归。广义表的元素之间存在次序关系，还存在层次关系。,16,广义表举例：,广义表中元素的最大层次数为表的深度。 元素的层次就是包含该元素的括号对的数目。 A=() 表A深度为0； B=(e) 表B深度为1； C=(a, (b,c,d) 表C深度为2； D=(A, B, C) 表D深度为3； E=(a, E) 表E深度为无穷；,17,再如广义表：F=(x, y, (z, (t) ) ,u) 数据元素x,y和u在第一层； 数据元素z在第二层；数据元素t在第三层。 广义表F深度为3。该表有4个元素，表长度为4。 A=() B=(e) C=(a, (b,c,
10、d) D=(A, B, C) E=(a, E), 又义可知，任一个非空广义表其表头可能是原子，也可能是表，而其表尾必定为表。 例如：Head(D)=A Tail(D)=(B,C) Head(C)=a Tail(C)=(b,c,d),18,5.5.2 广义表的存储结构,由于广义表（a1,a2,an）中的数据元素可以具有不同的结构(或是原子，或是表)，难以用顺序存储结构表示，通常采用链式存储结构，每个元素用一个结点表示。 广义表的存储结构主要有头尾链表存储结构和扩展线性链表结构两种表示方法。 现仅对头尾链表存储结构加以介绍,19,广义表的头尾链表存储结构：,若广义表不空，可分解成表头和表尾；一对表
11、头和表尾可唯一确定广义表。 表结点：3个域，标志域tag（1是表）、指向表头的指针hp和指示表尾的指针tp。 原子结点：两个域，标志域tag（0是原子）和数据值域atom。,20,1广义表元素结点的结构,struct glnode int tag; /标志域0/1，用来区分原子和表 union /共用体 struct ptrtp glnode *hp ,*tp; /hp指向表头元素，tp指向表尾 ptr; /对于表结点使用ptr char atom; /对于原子结点则使用atom ; ;,glnode *p;处理表结点: p-tag /值为1 p-ptr.hp /指向表头 p-ptr.tp /
12、指向表尾,glnode *q; 处理原子点结： q-tag /值为0 q-atom /数据元素值,21,2绘制广义表的结构图,对于：A=()，空表仅用A=NULL来表示，而不分配结点，也不必画图。 对于：B=(e) B指向一个表结点，B-tag=1。 B-ptr.hp应指向表头，由于表头是基本数据元素e，它指向一个原子结点e 。 B-ptr.tp应指向表尾，B表尾为空，所以B-ptr.tp为NULL。 由图可以理解，该表长度为1，深度也为1。,22,广义表：G= (b,c,d),G指向一个表结点，G-tag=1。 G-ptr.hp应指向表头，G表头是一个基本数据元素b，因此G-ptr.hp指向
13、一个值为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。,建议教师 不打字幕而对图详细讲解。,23,广义表：C=(a, (b,c,d) )
14、,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。,建议教师 不打字幕而对图详细讲解。,24,广义表：D=(A, B, C),D指向表结点，所以D-tag=1。 D-ptr.hp指向表头，即是A表，所
15、以为NULL。 D-ptr.tp指向表尾，即是（B,C），所以指向一个表结点。 D-ptr.tp-ptr.hp指向（B,C）的表头，即是B表。 D-ptr.tp-ptr.tp指向（B,C）的表尾，即是（C），所以 D-ptr.tp-ptr.tp指向一个表结点。 D-ptr.tp-ptr.tp-ptr.hp指向（C）的表头，即是C表。 D-ptr.tp-ptr.tp-ptr.tp指向（C）的表尾，即是空。 D表的长度为3，表的深度是3。,25,对于广义表：E=(a, E),E指向一个表结点，E-tag=1。D-ptr.hp指向表头，即一个值为a的原子结点。E-ptr.tp指向(a, E)的表尾，即是（E），所以指向一个表结点。 假设q=E-ptr.tp，那么q-tag=1。q-ptr.hp指向（E）的表头，即是E表（箭头向回指向）。而q-ptr.tp指向（E）的表尾，即为NULL。 E表长度为2，在层次上无穷递归所以深度为。,26,小 结,稀疏矩阵的压缩存储及其相关矩阵运算是本章的重点。应该
