商大计算机专业天津商业课件

1、第五章数组和广义表5.15.25.35.45.5数组的定义数组的顺序矩阵的压缩广义表的定义表示广义表的结构数据结构Data Structure1考核要点识记：数组和广义表的定义，数组的行主序、列主序排列顺序理解：数组和广义表的结构应用：数组和矩阵运算DataStructure2数据结构5.1 数组的定义数组概念：相同类型的数据 a00a01.a0,的集合；2) 数组类型：a10a11.a1,一维、二维、 n维； .am 1,0am 1,1am n 1 n 1 . 1, n 1数据结构Data Structure35.1 数组的定义二维数组的逻辑结构：A为mn二维数组。P91A可看成下述线性表：

2、A=(d0，d1，dn-1)dj 是列向量线性表：图5.1 (b)dj =(d0j ,d1j ,.,dm-1j )或di是行向量线性表：图5.1 (c)di =(di0 ,di1 ,.,din-1 )数据结构Data Structure45.1 数组的定义二维数组元素的逻辑关系：A中每个元素aij 均属于两个向量，第i行的向量第j列的向量。除边界外，每个元素aij 都恰好有两个直接前趋直接后继。00010203101112132021222330313233和和数据结构Data Structure55.1 数组的定义二维数组的基本运算：初始化销毁读：给定一组下标，存取相应元素的值。写：给定一组

3、下标，修改相应元素的值。数据结构Data Structure65.2数组的顺序表示1)数组的结构：P91数组一般不进行和删除操作；由于单元是一维结构，数组是结构，将数组按某种次序排成一个线性序列，然后存入内数组器。方式：顺序；图5.2FORTRAN；C、PASCAL；以列序为主序(a)：以行序为主序(b)：DataStructure7数据结构数组的顺序表示举例00102030011121310212223203132333(1)按行(2) 按列数据结构Data Structure8001020300111213102122232031323330001020310111213202122233

4、03132335.2数组的顺序表示2)二维数组mn的任一元素aij的位置：行为主序：Loc(i,j)=loc(0,0)+(ni+j)列为主序：Loc(i,j)=loc(0,0)+(mj+i)LLLoc(0 ,0)二维数组的首地址Loc（i,j），是aij 的位置每个元素占L个单元0 im-1， 0 jn-1数据结构Data Structure95.2数组的顺序表示3)数组的顺序表示：P93#define MAX_ARRAY_DIMtypedef structElemType *base ； dim；*bounds；*constants；Array；8DataStructure10数据结构5.2

5、数组的顺序表示4)数组的操作实现：P93构造数组销毁数组元素定位读元素值元素赋值数据结构Data Structure115.3矩阵的压缩1.基本概念2.对称矩阵3.三角矩阵4.稀疏矩阵数据结构Data Structure121.基本概念1)压缩基本一个：P95：在矩阵中为多个值相同的元素只分配单元，对零元不分配单元；2)特殊矩阵和稀疏矩阵：在一些阶数很高的矩阵中，同时存在许多值相同的元素或零元素的分布有一定的规律，称此矩阵为特殊矩阵，反之称为稀疏矩阵；常见特殊矩阵：对称矩阵和三角矩阵DataStructure13数据结构2.对称矩阵1)111213122212131211满足下述性质：n阶矩阵

6、a =a1i,jn下三角元素；ijji结构：2)用一维数组：san(n+1)/23)aij和位置sak的对应关系：ij：k=i(i-1)/2+j-1ij：k=j(j-1)/2+i-14)压缩： 图5.3 P96san(n+1)/2为n阶对称A的压缩；DataStructure14数据结构3.三角矩阵1)下(上)三角矩阵：矩阵的上(下)三角(不包括主对角线)的元素为常数或零的n阶矩阵；a00a0111.c.a0,n11,n1. a00c.c c. c aaaa . c1011.an1,1an1,0an1,n1an1,n1上三角矩阵下三角矩阵DataStructure15数据结构3.三角矩阵2)结

7、构：下/上三角元素；用一维数组：Mn(n+1)/2+13)下三角aij和位置Mk的对应关系：(0in-1)ij：k=i(i+1)/2+jij：k=n(n+1)/2(常数C的位置)4)上三角aij和位置Mk的对应关系：(0in-1)ij：k=i(2n-i+1)/2+j-iij：k=n(n+1)/2(常数C的位置)DataStructure16数据结构4.稀疏矩阵稀疏矩阵：P96含义：非零元素较零元素少，且分布没有一定规律；稀疏因子：=t/(mn)稀疏矩阵： 0.05数据结构Data Structure174.稀疏矩阵2)稀疏矩阵压缩方法：三元组顺序表：顺序结构不仅位置；非0元素，还要它所在行和列

8、的行逻辑的顺序表：顺序结构，P100；链表：链式结构，P103；DataStructure18数据结构4.稀疏矩阵3)三元组结点： (i, j, aij)稀疏矩阵零元的三元组及其行列数唯一确定；i：为v所在的行数；j：为v所在的列数；aij：为非0元素；举例：三元组表(1,2,12),(1,3,9),(3,1,-3), (3,6,14), (4,3,24),(5,2,18), (6,1,15), (6,4,-7),(6,7,8)123 90000000000M 00240000 00DataStructure19数据结构ijaij4.稀疏矩阵5)三元组顺序表表示：#define MAXSIZE

9、typedef struct12500i,j；ElemType e；Triple；/*定义结点*/typedef struct Triple dataMAXSIZE+1；/ mu,nu,tu；TSMatrix； /*定义三元组*/data0不用DataStructure20数据结构5.4 广义表的定义广义表的定义和基本概念：P106含义： lists，也称列表，线性表的推广；应用：AI的LISP语言；表示：LS=(a1，a2，an)LS：表名,用大写字母表示；n：表的长度；术语： ai(1in)原子(小写)(线性表为单个元素)子表表头表尾；数据结构Data Structure215.4广义表的

10、定义2)广义表的基本运算：创建一个空表；判断表空；表；元素删除元素取广义表的表头；取广义表的表尾；DataStructure22数据结构5.4 广义表的定义广义表举例：A =（）：空表，n=0；B =（e）：1个原子，n=1；C =（a,(a,b,c,d)）：1个原子和1个子表，n=2D =（A,B,C）：3个列表，n=3；E =（a,E）：递归表，n=2；数据结构Data Structure235.4 广义表的定义广义表的特点：广义表是一个多层次的数据结构，可以用图形象表示，图5.7；广义表可以为其它列表所共享，通过子表的名称用；广义表可以是一个递归的表；任何一个非空列表，表头可能是原子，也

11、可能是表，而其表尾必定为列表。地引子数据结构Data Structure245.4 广义表的定义广义表运算举例：GetHead(B) = eGetTail(B) = ( )GetHead(D) = AGetTail(D) = (B,C)GetHead(GetTail(D) = BGetTail(B,C) = (C)数据结构Data Structure255.4广义表的定义6)注意：不能对空表求表头和表尾运算；表尾用( )扩起来；列表LS=()和LS=()的区别：LS=()：为空表，n=0；LS=()：n=1,表头和为空表()；数据结构Data Structure265.5广义表的结构1)广义表

12、的采用链式结构：结构头尾链表表示扩展线性链表表示每个数据元素用一个结点表示结点如何表示？DataStructure27数据结构5.5广义表的结构2)头尾链表结点结构：需要两种结构；P109表结点：表示列表,3个指针域标志域表头表尾原子结点：表示原子,2个指针域值域标志域数据结构Data Structure28tag=0atomtag=1hptp5.5 广义表的结构3)头尾链表的表示：typedef enumATOM，LISTtypedef struct GLNode ElemTag tag； unionAtomType atom ；ElemTag；struct； *Glist；GLNode *hp,*tp；ptr；DataStructure29数据结构广义表结构示例A=NILCB11DE图 5