




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Chapter 5Array /数组存放空间 int ArraySize; /当前长度 void getArray ( ); /建立数组空间 public: Array( int Size=DefaultSize ); Array( const Array,Array( ) delete elements; Array /扩充数组 ,一维数组公共操作的实现,template void Array : getArray ( ) /私有函数:创建数组存储空间 elements = new TypeArraySize; ,template Array : Array ( int sz ) Array
2、Size = sz; getArray ( ); ,template Array:Array(Array ,template Array:Array(Array ,template Type ,template void Array : Resize ( int sz ) if ( sz = 0 /按新的大小确定传送元素个数,Type *srcptr=elements; Type *destptr=newarray; while (n-)*destptr+=*srcptr+; delete elements; elements = newarray; ArraySize = sz; ,多维数组
3、,多维数组是一维数组的推广 多维数组是一种非线性结构。其特点是每一个数据元素可以有多个直接前驱和多个直接后继。 数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简单。,数组元素的遍历 1)以行序为主序(按行排列): 先排最右的下标,依次向左,最后 排最左的下标 2)以列序为主序(按列排列): 先排最左的下标,依次向右,最 后排最右的下标,例如:,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0
4、,2,a1,0,a1,1,a1,2,L,L,对于一般意义二维数组Ac1:d1,c2:d2,设每个元素占用1个存储单元,LOC(c1,c2)是第一个元素ac1c2的存储位置,则按行存放时,aij的存储位置为: LOC(i,j)=LOC(c1,c2)+(d2-c2+1)(i-c1)+(j-c2) 则列行存放时,aij的存储位置为: LOC(i,j)=LOC(c1,c2)+(d1-c1+1)(j-c2)+(i-c1),推广到一般情况,可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。,其中 cn = L,ci-1 = bi ci , 1
5、 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,对于n维数组的一般情况Ac1:d1,c2:d2,cn:dn,设每个元素占用个存储单元,LOC(c1,c2, cn)是第一个元素ac1c2cn的存储位置,则按行存放时,aj1j2jn的存储位置如下: LOC(j1j2jn)=LOC(c1,c2, ,cn)+(j1-c1)(d2-c2+1)(dn-cn+1) +( j2-c2)(d3-c3+1)(dn-cn+1) +( jn-1-c n-1)(dn-cn+1) +( jn-c n)l,则列行存放时,aj1j2jn的存储位置如下: LOC(
6、j1j2jn)=LOC(c1,c2, , cn)+(j1-c1) +(d1-c1+1) ( j2-c2) +(d1-c1+1)(dn-2-cn-2+1) (jn-1-cn-1) +(d1-c1+1)(dn-1-cn-1+1) (jn-cn)l,稀疏矩阵(Sparse Matrix),非零元素个数远远少于矩阵元素个数,假设 m 行 n 列的矩阵含 t 个非零元素,则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,以常规方法,即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算, 遇除法,还需判别除数是否为零。,1) 尽可能少存
7、或不存零值元素;,解决问题的原则,2) 尽可能减少没有实际意义的运算;,3) 操作方便。 即: 1. 能尽可能快地找到与下标值 (i,j)对应的元素, 2. 能尽可能快地找到同一行或 同一列的非零值元。,1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵,2) 随机稀疏矩阵 非零元在矩阵中随机出现,有两类稀疏矩阵:,特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 对称矩阵 三角矩阵 三对角矩阵,n阶对称矩阵 aij=aji 1=j j(j-1)/2+i-1 当ij,K=,矩阵的压缩存储 对称矩阵,三角矩阵共计元素个数为: n(n+1)/2,三角矩阵,对角矩阵,Loc(
8、aij)=Loc(a11)+2(i-1)+(j-1) |i-j|1,随机稀疏矩阵的顺序压缩存储,三元组表示法,随机稀疏矩阵的链式压缩存储,十字链表,随机稀疏矩阵 非零元在矩阵中随机出现,十字链表,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,11,2,1,Typedef struct OLNode int i, j; ElemType e; struct OLNode *right, *right; Typedef struct OLink * rhead, *lhead; int mu, nu,tu; ,#define MAXSIZE 12500
9、 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,三元组顺序表(C语言版),typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,已知稀疏矩阵,三元组顺序表示例,三元组表示为,稀疏矩阵三元组表的抽象数据类型 (C+版) const int MaxTerms=1000; template class SparseMatrix; template class Trituple friend class S
10、parseMatrix private: int row, col; /非零元素行号/列号 Type value; /非零元素的值 ,templateclass SparseMatrix int Rows,Cols,Terms;/行/列/非零元素数 Trituple smArrayMaxTerms; public: /三元组表 SparseMatrix (int Row, int Col,int Term); SparseMatrix /转置,SparseMatrix /相乘 ,稀疏矩阵的转置,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (col=1; col=nu
11、; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,一个 mn 的矩阵 A,它的转置矩阵 B 是一个 nm 的矩阵,且 Aij = Bji。即矩阵 A 的行成为矩阵 B 的列,矩阵 A 的列成为矩阵 B 的行。 在稀疏矩阵的三元组表中,非零矩阵元素按行存放。当行号相同时,按列号递增的顺序存放。 稀疏矩阵的转置运算要转化为对应三元组表的转置。,稀疏矩阵,转置矩阵,用三元组表表示的稀疏矩阵及其转置,稀疏矩阵转置算法思想,设矩阵列数为 Cols,对矩阵三元组表扫描Cols 次。第 k 次检测列号为 k 的项。 第 k 次扫描找寻所有列号为 k 的
12、项,将其行号变列号、列号变行号,顺次存于转置矩阵三元组表。,template SparseMatrix,for ( int k = 0; k a.Cols; k+ ) for ( int i = 0; i a.Terms; i+ ) if ( a.smArrayi.col = k ) b.smArrayCurrentP.row = a.smArrayi.col; b.smArrayCurrentP.col = a.smArrayi.row; b.smArrayCurrentP.value= a.smArrayi.value;,CurrentP+; return b; ,时间复杂度O(nu*tu
13、),按a.data中三元组的次序进行转换,如果能预先确定矩阵M中的每一列(即T中 每一行)的第一个非零元在b.data中应有置, 则在对a.data中的三元组依次转置时,便可直接放到b.data中恰当的位置上去。 (先求M中每一列非零元素的个数。),首先应该确定每一列的第一个非零元在三元组中的位置。,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / FastTransposeSMatrix,转置矩阵元素
14、,Col = M.datap.j; / p=1 col=2; p=2 col=5 q = cpotcol; / p=1 q=cpot2=2; p=2 q=cpot5=5 T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol,分析算法FastTransposeSMatrix的时间复杂度:,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p
15、=1; p=M.tu; +p) ,Section 2 General List,1.广义表的概念 n(0)个表元素组成的 有限序列,记作 LS = (a0, a1, a2, , an-1) LS是表名,ai是表元素,它可以是表(称为 子表),可以是数据元素(称为原子) 2.n为表的长度。n=0的广义表为空表 3.n0时,表的第一个表元素称为广义表 的表头(head),除此之外,其它表元素组 成的表称为广义表的表尾(tail),广义表的 抽象数据类型定义,ADT Glist 数据对象:Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象
16、 数据关系: LR| ei-1 ,eiD, 2in ADT Glist,基本操作:,广 义 表 的基本操作,结构的创建和销毁 InitGList(,状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);,插入和删除操作 InsertFirst_GL(,遍历 Traverse_GL(L, Visit();,广义表是递归定义的线性结构,,LS = ( 1, 2, , n ) 其中:i 或为原子 或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D
17、, F) B = (a, B) = (a, (a, (a, , ) ) ),广义表是一个多层次的线性结构,例如:,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,广义表 LS = ( 1, 2, , n ) 的结构特点,1)广义表中的数据元素有相对次序,广义表的长度定义为最外层包含元素 个数,广义表的深度定义为所含括弧的重数 “原子”的深度为 0 “空表”的深度为 1,4)广义表可以是一个递归的表,5)任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(L
18、S) = ( 2, , n) 两部分,例如: D=(E, F)=(a,(b, c),F),Head(D)=E Tail(D)=(F),Head(E)=a Tail(E)=(b, c),Head(b, c)=(b, c) Tail(b, c)=( ),Head(b, c)=b Tail(b, c)=(c),Head(c)=c Tail(c)=( ),5.5 广义表的表示方法,通常采用头、尾指针的链表结构,表结点: 原子结点:,tag=1 hp tp,tag=0 data,广义表的头尾链表存储表示,Typedef enumATOM, LIST ElemTag; Typedef struct GLN
19、ode ElemTag tag; union AtomType atom; struct struct GLNode *hp, *tpptr; ; *glist,若子表为原子,则为,空表 ls=NIL,非空表,1,指向子表1 的指针,tag=0 data,否则,依次类推。,1,指向子表2 的指针,1,指向子表n 的指针,ls,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,第二种链表表示方法,表结点: 原子结点:,tag=1 hp tp,tag=0 atom tp,5.6 广义表操作的递归函数,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数,它
20、必须满足以下两个条件:,1)在每一次调用自己时,必须是(在某 种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,广义表从结构上可以分解成,广义表 = 表头 + 表尾,或者,广义表 = 子表1 + 子表2 + + 子表n,因此常利用分治法求解之。 算法设计中的关键问题是,如何将 l 个子问题的解组合成原问题的解。,广义表的头尾链表存储表示:,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结
21、点的数据域 struct struct GLNode *hp, *tp; ptr; ; *GList,tag=1,hp tp,ptr,表结点,例一 求广义表的深度,例二 复制广义表,例三 创建广义表的存储结构,广义表的深度=Max 子表的深度 +1,例一 求广义表的深度,可以直接求解的两种简单情况为: 空表的深度 = 1 原子的深度 = 0,将广义表分解成 n 个子表,分别(递归)求得每个子表的深度,,int GlistDepth(Glist L) / 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-
22、ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth,if (!L) return 1; if (L-tag = ATOM) return 0;,1,1,1,L,for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; ,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,例二 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为: 空表复制求得的新表
23、自然也是空表; 原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分,分别(递归)复制求得新的表头和表尾,,若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp,复制求广义表的算法描述如下:,Status CopyGList(Glist / CopyGList,分别复制表头和表尾,CopyGList(T-ptr.hp, L-ptr.hp); / 复制求得表头T-ptr.hp的一
24、个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); / 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp,语句 CopyGList(T-ptr.hp, L-ptr.hp); 等价于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp;,例三 创建广义表的存储结构,对应广义表的不同定义方法相应地有不同的创建存储结构的算法。,假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L,建立相应的存储结构。,由于S中的每个子串i定义 L 的一个子表,从而产生 n 个子问题,即分别由这 n个子串 (递归)建立 n
25、 个子表,再组合成一个广义表。,可以直接求解的两种简单情况为: 由串( )建立的广义表是空表; 由单字符建立的子表只是一个原子结点。,如何由子表组合成一个广义表?,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表 的头指针,指向第一个 子表的头指针,再看相邻两个子表之间的关系:,1,1,指向第i+1个 子表的头指针,指向第i个 子表的头指针,可见,两者之间通过表结点相链接。,若 S = ( ) 则 L = NIL; 否则,构造第一个表结点 *L, 并从串S中分解出第一个子串1,对应创建第一个子广义表 L-ptr.hp; 若剩余串非空,则构造第二个表结
26、点 L-ptr.tp,并从串S中分解出第二个子串 2,对应创建第二个子广义表 ; 依次类推,直至剩余串为空串止。,void CreateGList(Glist /脱去串S的外层括弧 / else ,由sub中所含n个子串建立n个子表;,do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一个子表的表结点*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾为空表,创建由串
27、hsub定义的广义表p-ptr.hp;,if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 创建单原子结点 else CreateGList(p-ptr.hp, hsub); /递归建广义表,后置递归的设计思想为:,递归的终结状态是,当前的问题可以直接求解,对原问题而言,则是已走到了求解的最后一步。,链表是可以如此求解的一个典型例子。 例如:编写“删除单链表中所有值为x 的数据元素”的算法。,1) 单链表是一种顺序结构,必须从第一个结点起,逐
28、个检查每个结点的数据元素;,分析:,2) 从另一角度看,链表又是一个递归结构,若 L 是线性链表 (a1, a2, , an) 的头指针,则 L-next是线性链表 (a2, , an)的头指针。,a1,a2,a3,an,L,例如:,a1,a2,a3,an,L,a1,a2,a3,an,L,已知下列链表,1) “a1=x”,则 L 仍为删除 x 后的链表头指针,2) “a1x”,则余下问题是考虑以 L-next 为头指针的链表,a1,L-next,L-next=p-next,p=L-next,void delete(LinkList / delete,删除广义表中所有元素为x的原子结点,分析:
29、比较广义表和线性表的结构特点:,相似处:都是链表结构。,不同处:1)广义表的数据元素可能还是个 广义表; 2)删除时,不仅要删除原子结点, 还需要删除相应的表结点。,void Delete_GL(Glist / 考察第一个子表 if (head-tag = Atom) L = L-ptr.tp; / 修改指针 free(head); / 释放原子结点 free(p); / 释放表结点 Delete_GL(L, x); / 递归处理剩余表项,1,L,0 x,1,p,L,head,if (head-tag = LIST) /该项为广义表 Delete_GL(head, x); Delete_GL(
30、L-ptr.tp, x); / 递归处理剩余表项,1,L,0 a,1,1,head,L-ptr.tp,回溯法是一种“穷举”方法。其基本思想为:,假设问题的解为 n 元组 (x1, x2, , xn), 其中 xi 取值于集合 Si。 n 元组的子组 (x1, x2, , xi) (in) 称为部分解,应满足一定的约束条件。 对于已求得的部分解 (x1, x2, , xi) , 若在添加 xi+1Si+1 之后仍然满足约束条件, 则得到一个新的部分解 (x1, x2, , xi+1) , 之后继续添加 xi+2Si+2 并检查之。,例一、皇后问题求解,设四皇后问题的解为 (x1, x2, x3,
31、 x4), 其中: xi (i=1,2,3,4) Si=1, 2, 3, 4 约束条件为:其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。,按回溯法的定义,皇后问题求解过程为: 解的初始值为空;首先添加 x1=1, 之后添加满足条件的 x2=3,由于对所有的 x31,2, 3, 4都不能找到满足约束条件的部分解(x1, x2, x3), 则回溯到部分解(x1), 重新添加满足约束条件的x2=4, 依次类推。,void Trial(int i, int n) / 进入本函数时,在nn棋盘前i-1行已放置了互不攻 / 击的i-1个棋子。现从第 i 行起继续为后续棋子选择 / 满足约束条
32、件的位置。当求得(in)的一个合法布局 / 时,输出之。 if (in) 输出棋盘的当前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一个棋子; if (当前布局合法) Trial(i+1, n); 移去第 i 行第 j 列的棋子; / trial,回溯法求解的算法一般形式:,void B(int i, int n) / 假设已求得满足约束条件的部分解(x1,., xi-1),本函 /数从 xi 起继续搜索,直到求得整个解(x1, x2, xn)。 if (in) else while ( ! Empty(Si) 从 Si 中取 xi 的一个值 viSi; if (x1, x2, , xi) 满足约束条件 B( i+1, n); / 继续求下一个部分解 从 Si 中删除值 vi; / B,综合几点: 1. 对于含有递归特性的问题,最好设计递归形式的算法。但也不要单纯追求形式,应在算法设计的分析过程中“就事论事”。例如,在利用分割求解设计算法时,子问题和原问题的性质相同;或者,问题的当前一步解决之
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《李凭箜篌引》(李贺)测试题带答案
- 《后汉书关羽传》测试题带答案
- 2024年干部休养所服务项目资金筹措计划书代可行性研究报告
- 2024年磁卡宽片资金筹措计划书代可行性研究报告
- 蓝色红色新中式部门年中工作总结
- 睡眠宣传班会课件
- 湘夫人课件讲课件
- 生命安全与健康教育主题班会讲课件
- 围棋趣味入门题目及答案
- 抽样技术课件
- 2024年凉山州木里县选聘社区工作者真题
- 保险公司攒钱活动方案
- 九师联盟2024-2025学年高二下学期6月摸底联考英语试题(含答案)
- 2024智联招聘人社局解决就业大型招聘会活动方案
- 医院护理岗位笔试题目及答案
- 芯核半导体科技有限公司年产2400套半导体零部件项目环评资料环境影响
- 供水行业安全培训课件
- 2025家常保姆雇佣合同协议书
- 中小学校长管理能力测试题及答案
- 妇科腔镜试题及答案
- DZ/T 0276.27-2015岩石物理力学性质试验规程第27部分:岩体变形试验(钻孔变形法)
评论
0/150
提交评论