01:41,概述,2.7,第二章 常用的数据结构及其运算,2.1,2.2,2.3,2.5,2.6,树与二叉树,数组,线性表栈,线性表顺序表,2.4,线性表队列,线性表链表,01:41,2.5 线性链表(Linked List),线性链表:线性表的链式存储结构，是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 结点:数据元素ai的存储映象.它包括两个域: 数据域:存储每个结点值; 指针域:存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,2.5.1线性链表定义,01:41,2.5 线性链表(Linked List),2.5.1线性链表定义,(a)线性链表的物理状态,(b)线性链表的逻辑状态,head,01:41,2.5 线性链表(Linked List),struct 结构体类型名数据成员表;结构体类型名 *指针变量名; ;,2.5.1线性链表定义,在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的。指向第一个结点的指针head称为头指针，当head=NULL(或0)时称为空表。,结点C语言描述,01:41,2.5 线性链表(Linked List),2.5.2线性链表的基本运算,由线性链表的存储结构可知，对线性链表进行插入、删除操作时，不必移动元素，而是修改指针的指向和动态生成或回收链表的结点。,01:41,2.5线性链表(Linked List),2.5.2.1插入运算 后插：当前指针指向第i个结点ai，将值为x的新结点插入到第i个结点之后。首先生成一个数据域为x的新结点*s，并令结点ai的指针域指向新结点，新结点的指针域指向结点ai1。从而实现三个结点ai，x和ai1之间的逻辑关系的变化。,01:41,2.5 线性链表(Linked List),前插：当前指针指向第i个结点ai，将值为x的新结点插入到表的第i个结点之前的位置上。首先我们必须找到ai-1的存储位置，然后生成一个数据域为x的新结点*s，并令结点ai-1的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化。,如果i1，会怎么样？,2.5.2.1插入运算,01:41,2.5线性链表(Linked List),前插：当前指针指向第i个结点ai，将值为x的新结点插入到表的第i个结点之前的位置上。 如果i1，需要修改头指针（无头结点时）。,current,2.5.2.1插入运算,01:41,2.5线性链表(Linked List),将新元素插入到链表头的C语言描述,2.5.2.1插入运算,Struct node int a;struct node *pNext; Typedef struct node NODE; NODE* InsLinkedList(NODE *pList,int x) NODE *pTemp;pTemp=new NODE;pTemp-a=x;pTemp-pNext=pList;return pTemp; ,01:41,2.5线性链表(Linked List),2.5.2.2删除运算 是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点 a i-1的指针域next中，所以我们必须首先找到 a i-1的存储位置p。然后令next（p）指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。,i-1 i i+1,01:41,2.5线性链表(Linked List),2.5.2.2删除运算,NODE * DelLinkedList(NODE *pList,int x)/删除链表中数据为x的结点 NODE * pFormer,*pCurrent;pFormer=pList;pCurrent=pList;while(pCurrent-pNext!=NULL ,01:41,2.5线性链表(Linked List),线性链表的其他形式,循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。,单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。,01:41,带表头结点的循环链表 为了使空表和非空表的处理一致，循环链表中也可设置一个 头结点（在表中第一个结点之前设立头结点，它的数据域或是空，或是按需要设定）。这样，空循环链表仅有一个自成循环的头结点表示。,(b)空表,2.5线性链表(Linked List),01:41,2.5线性链表(Linked List),双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。,结点结构,01:41,带头结点的双向循环链表结构图,由于双向链表具有对称性，从表中某一给定的结点可以随意向前或向后查找。但在做插入、删除运算时，需同时修改两个方向的指针。,2.5线性链表(Linked List),01:41,2.5.3 顺序表和链表的比较,顺序存储的三个优点： (1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。顺序存储的两个缺点： (1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 (2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。,链表的优缺点恰好与顺序表相反。,01:41,2.5.3 顺序表和链表的比较,在实际中怎样选取存储结构呢？,基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对MAXSIZE要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于的。,01:41,2.5.3 顺序表和链表的比较,基于运算的考虑 在顺序表中按序号访问ai的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。,01:41,2.5.3 顺序表和链表的比较,基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲，前者简单些，也是用户考虑的一个因素。 总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。,01:41,概述,图,查找,排序,2.7,2.9,2.8,第二章 常用的数据结构及其运算,2.1,2.2,2.3,2.5,2.6,树与二叉树,数组,线性表栈,线性表顺序表,2.4,线性表队列,线性表链表,2.10,01:41,2.6 数组,数学中的矩阵在程序设计语言中用二维数组表示。,一个mn的矩阵,主要内容： （1）一般二维数组的顺序存储结构； （2）矩阵中绝大部分元素为零的表示方法。,01:41,2.6 数组,2.6.1 二维数组的顺序存储结构,一个mn的矩阵,二维数组在计算机中顺序存储，存储方式一般有两种：以行为主的顺序存储与以列为主的顺序存储。,01:41,2.4 数组,2.6.1 数组顺序存取结构,（1）按行优先顺序存储,假设每个元素仅占L个单元地址，则元素aij的地址可由下式计算：,计算机语言中BASIC和C按行为主顺序存储,01:41,2.4 数组,2.6.1数组顺序存取结构,（2）按列优先顺序存储,元素aij的地址可由下式计算：,计算机语言FORTRAN中的多维数组在计算机中按列为主顺序存储,01:41,2.4 数组,2.6.2 规则矩阵的压缩,规则矩阵，是指矩阵中非零元素的分布有规律。,在存储一个规则矩阵时，只需存储非零元素即可，而对于大部分的零元素或者重复的非零元素（如对称矩阵）不必存储。 规则矩阵的这种存储方法称为压缩存储。 规则矩阵压缩存储的关键：方便访问矩阵中每一个元素。,上三角矩阵； 下三角矩阵； 对称矩阵； 三对角矩阵； 带型矩阵。,01:41,2.4 数组,(1)下三角矩阵的压缩存储,设n阶下三角矩阵为：,从第1行至第i-1行的非零元素个数为：,2.6.2 规则矩阵的压缩,存储原则：用一维数组以行为主顺序存放下三角矩阵中的所有下三角元素。,01:41,2.4 数组,2.6.2 规则矩阵的压缩,(1)下三角矩阵的压缩存储,将下三角矩阵A用一维数组B存储，按如下原则访问元素aij：,作业: (1)用以列为主顺序存储在一维数组中,下三角矩阵元素怎么访问? (2)上三角矩阵元素用以行为主和以列为主顺序压缩存储在一维数组中怎样访问?哪种压缩形式更方便?,01:41,2.4 数组,2.6.2 规则矩阵的压缩,(2)对称矩阵的压缩存储,对称矩阵的压缩存储与下三角矩阵完全相同.在以行为主压缩存储时,用一维数组B存储，按如下原则访问元素aij：,01:41,2.4 数组,(3)三对角矩阵的压缩存储,n阶三对角矩阵的形式为：,2.6.2 规则矩阵的压缩,共多少非零元素？,01:41,2.4 数组,将非零元素按行优先存放：,在用一维数组B以行为主存放三对角矩阵A中的元素aij时，其访问公式为：,(3)三对角矩阵的压缩存储,2.6.2 规则矩阵的压缩,01:41,2.4 数组,2.6.3一般稀疏矩阵,如果一个矩阵中绝大多数的元素值为零，只有很少的元素值非零，则称该矩阵为稀疏矩阵。,在实际存储稀疏矩阵时，可以只存储非零元素，而大量的零元素不存储，这就是稀疏矩阵的压缩存储。,01:41,2.4 数组,2.6.3一般稀疏矩阵,稀疏矩阵中非零元素的分布一般没有规律，不能用一个一维数组依次存放其中的非零元素。,常用的两种稀疏矩阵压缩存储方法是：三列二维数组和十字链表。,01:41,2.4 数组,2.6.3.1 稀疏矩阵的三列二维数组（三元组）表示,在压缩存储形式中，每一个非零元素应包括以下三个信息： 非零元素所在的行号i； 非零元素所在的列号j； 非零元素的值V。 即每一个非零元素可以用下列三元组表示：（i，j，V）,为了矩阵表示的惟一性，除了每一个非零元素用一个三元组表示外，在所有表示非零元素的三元组之前再添加一个三元组（I，J，t），I:稀疏矩阵总行数，J:稀疏矩阵总列数,t:非零元素个数。,2.6.3一般稀疏矩阵,01:41,2.4 数组,具有t个非零元素的稀疏矩阵可以用t + 1个三元组表示，其中第一个三元组用以表示稀疏矩阵的总体信息，其后的各三元组依次表示各非零元素，且按以行为主的顺序排列。 为了使各三元组的结构更紧凑，通常将这些三元组组织成三列二维表格的形式，一般又表示成三列二维数组的形式，并简称为三列二维数组。,2.6.3一般稀疏矩阵,2.6.3.1 稀疏矩阵的三列二维数组（三元组）表示,01:41,2.4 数组,具有t个非零元素的稀疏矩阵，其对应的三列二维数组为t + 1行、3列，共有3(t + 1)个元素。,