nullnullnull5.1 数组的类型定义5.3 稀疏矩阵的压缩存储 5.2 数组的顺序
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示和实现5.4 广义表的类型定义5.5 广义表的表示方法5.6 广义表操作的递归函数null5.1 数组的类型定义ADT Array {
数据对象:
D={aj1,j2, ...,,ji,jn| ji =0,...,bi -1, i=1,2,..,n }
数据关系:
R={R1, R2, ..., Rn}
Ri={
| 0 jk bk -1,
1 k n 且k i, 0 ji bi -2, i=2,...,n }
} ADT Array 基本操作:null二维数组的定义:数据对象:
D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}
数据关系:
R = { ROW, COL }
COL = {| 0≤i≤b1-2, 0≤j≤b2-1}
ROW = {| 0≤i≤b1-1, 0≤ j≤b2-2}基本操作:基本操作:InitArray(&A, n, bound1, ..., boundn)DestroyArray(&A)Value(A, &e, index1, ..., indexn)Assign(&A, e, index1, ..., indexn)null InitArray(&A, n, bound1, ..., boundn)
操作结果:若维数 n 和各维长度合法,
则构造相应的数组A,并
返回OK。 DestroyArray(&A)
操作结果:销毁数组A。 DestroyArray(&A)
操作结果:销毁数组A。null Value(A, &e, index1, ..., indexn)
初始条件:A是n维数组,e为元素变量,
随后是n 个下标值。
操作结果:若各下标不超界,则e赋值为
所指定的A 的元素值,并返
回OK。null Assign(&A, e, index1, ..., indexn)
初始条件:A是n维数组,e为元素变量,
随后是n 个下标值。 操作结果:若下标不超界,则将e的值赋
给所指定的A的元素,并返回
OK。null5.2 数组的顺序表示和实现 类型特点:
1) 只有引用型操作,没有加工型操作;
2) 数组是多维的结构,而存储空间是
一个一维的结构。 有两种顺序映象的方式:
1)以行序为主序(低下标优先);
2)以列序为主序(高下标优先);null例如: 称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j 的存储位置
LOC(i,j) = LOC(0,0) + (b2×i+j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L null推广到一般情况,可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素
的存储位置是其下标的线性函数其中 cn = L,ci-1 = bi ×ci , 1 < i n。LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + ∑ ci ji i=1nnull假设 m 行 n 列的矩阵含 t 个非零元素,则称
为稀疏因子
通常认为 0.05 的矩阵为稀疏矩阵5.3 稀疏矩阵的压缩存储何谓稀疏矩阵?null 以常规方法,即以二维数组表示
高阶的稀疏矩阵时产生的问题:1) 零值元素占了很大空间;2) 计算中进行了很多和零值的运算,
遇除法,还需判别除数是否为零;null1) 尽可能少存或不存零值元素;解决问题的原则:2) 尽可能减少没有实际意义的运算;3) 操作方便; 即:
能尽可能快地找到
与下标值 (i, j) 对应的元素;
能尽可能快地找到
同一行或同一列的非零值元;null1) 特殊矩阵
非零元在矩阵中的分布有一定规则
例如: 三角矩阵
对角矩阵2) 随机稀疏矩阵
非零元在矩阵中随机出现有两类稀疏矩阵:null随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、 十字链表null #define MAXSIZE 12500
typedef struct {
int i, j; //该非零元的行下标和列下标
ElemType e; // 该非零元的值
} Triple; // 三元组类型一、三元组顺序表typedef union {
Triple data[MAXSIZE + 1];
int mu, nu, tu;
} TSMatrix; // 稀疏矩阵类型null如何求转置矩阵?null用常规的二维数组表示时的算法 其时间复杂度为: O(mu×nu) for (col=1; col<=nu; ++col)
for (row=1; row<=mu; ++row)
T[col][row] = M[row][col];null用“三元组”表示时如何实现?1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28null 首先应该确定转置矩阵中
每一行的第一个非零元在三元组中的位置。 cpot[1] = 1;
for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1];nullStatus FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if (T.tu) {
for (col=1; col<=M.nu; ++col) num[col] = 0;
for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];
cpot[1] = 1;
for (col=2; col<=M.nu; ++col)
cpot[col] = cpot[col-1] + num[col-1];
for (p=1; p<=M.tu; ++p) { }
} // if
return OK;
} // FastTransposeSMatrix 转置矩阵元素nullCol = M.data[p].j;
q = cpot[col];
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
++cpot[col]null 分析算法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=1; p<=M.tu; ++p) … …
null 三元组顺序表又称有序的双下标法,它的特点是,非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。然而,若需随机存取某一行中的非零元,则需从头开始进行查找。二、行逻辑联接的顺序表null #define MAXMN 500
typedef struct {
Triple data[MAXSIZE + 1];
int rpos[MAXMN + 1];
int mu, nu, tu;
} RLSMatrix; // 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义,增加一个数据成员rpos, 其值在稀疏矩阵的初始化函数中确定。null例如:给定一组下标,求矩阵的元素值ElemType value(RLSMatrix M, int r, int c) {
p = M.rpos[r];
while (M.data[p].i==r &&M.data[p].j < c)
p++;
if (M.data[p].i==r && M.data[p].j==c)
return M.data[p].e;
else return 0;
} // valuenull矩阵乘法的精典算法:
for (i=1; i<=m1; ++i)
for (j=1; j<=n2; ++j) {
Q[i][j] = 0;
for (k=1; k<=n1; ++k)
Q[i][j] += M[i][k] * N[k][j];
}其时间复杂度为: O(m1×n2×n1)null Q初始化;
if Q是非零矩阵 { // 逐行求积
for (arow=1; arow<=M.mu; ++arow) {
// 处理M的每一行
ctemp[] = 0; // 累加器清零
计算Q中第arow行的积并存入ctemp[] 中;
将ctemp[] 中非零元压缩存储到Q.data;
} // for arow
} // if 两个稀疏矩阵相乘(QMN)
的过程可大致描述如下:
null Status MultSMatrix
(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
if (M.nu != N.mu) return ERROR;
Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;
if (M.tu*N.tu != 0) { // Q是非零矩阵
for (arow=1; arow<=M.mu; ++arow) {
// 处理M的每一行
} // for arow
} // if
return OK;
} // MultSMatrixnull ctemp[] = 0; // 当前行各元素累加器清零
Q.rpos[arow] = Q.tu+1;
for (p=M.rpos[arow]; p MAXSIZE) return ERROR;
Q.data[Q.tu] = {arow, ccol, ctemp[ccol]};
} // if处理 的每一行Mnull分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu),
求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu),
进行压缩存储的时间复杂度为(M.muN.nu),
总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵,N是n行p列的稀疏矩阵,
则M中非零元的个数 M.tu = Mmn,
N中非零元的个数 N.tu = Nnp,
相乘算法的时间复杂度就是 (mp(1+nMN)) ,
当M<0.05 和N<0.05及 n <1000时,
相乘算法的时间复杂度就相当于 (mp)。null三、 十字链表3 0 0 5
0 -1 0 0
2 0 0 011314522-1312^^^^^^^null5.4 广义表的类型定义5.5 广义表的表示方法5.6 广义表操作的递归函数null5.4 广义表的类型定义ADT Glist {
数据对象:D={ei | i=1,2,..,n; n≥0;
ei∈AtomSet 或 ei∈GList,
AtomSet为某个数据对象 }
数据关系:
LR={| ei-1 ,ei∈D, 2≤i≤n}
} ADT Glist基本操作:null广义表是递归定义的线性结构, LS = ( 1, 2, , n )
其中:i 或为原子 或为广义表例如: A = ( )
F = (d, (e))
D = ((a,(b,c)), F)
C = (A, D, F)
B = (a, B) = (a, (a, (a, , ) ) )null广义表是一个多层次的线性结构例如:D=(E, F)其中:
E=(a, (b, c))
F=(d, (e))DEFa( )d( )bcenull广义表 LS = ( 1, 2, …, n )的结构特点:1) 广义表中的数据元素有相对次序;2) 广义表的长度定义为最外层包含元素个数;3) 广义表的深度定义为所含括弧的重数;
注意:“原子”的深度为 0 ;
“空表”的深度为 1 。4) 广义表可以共享;5) 广义表可以是一个递归的表;
递归表的深度是无穷值,长度是有限值。null6) 任何一个非空广义表 LS = ( 1, 2, …, n)
均可分解为
表头 Head(LS) = 1 和
表尾 Tail(LS) = ( 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 ) ) = ( )null 结构的创建和销毁
InitGList(&L); DestroyGList(&L);
CreateGList(&L, S); CopyGList(&T, L);基本操作 状态函数
GListLength(L); GListDepth(L);
GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作
InsertFirst_GL(&L, e);
DeleteFirst_GL(&L, &e); 遍历
Traverse_GL(L, Visit());null5.5 广义表的表示方法通常采用头、尾指针的链表结构表结点:
原子结点:null1) 表头、表尾分析法:构造存储结构的两种分析方法:若表头为原子,则为空表 ls = NIL非空表 ls指向表头的指针指向表尾的指针否则,依次类推。nullnullL = ( a, ( x, y ), ( ( x ) ) )a( x, y )( ) 1 LL = ( )0 a 1 1 1 1 1 0 x ( )xnull2) 子表分析法:若子表为原子,则为空表 ls=NIL非空表指向子表1
的指针否则,依次类推。指向子表2
的指针指向子表n
的指针null例如:((x)) LS=( a, (x,y), ((x)) ) a (x, y)null5.6 广义表操作的递归函数递归函数
一个含直接或间接调用本函数语句的函数被称之为递归函数,它必须满足以下两个条件:1)在每一次调用自己时,必须是(在某
种意义上)更接近于解;2)必须有一个终止处理或计算的准则。null例如: 梵塔的递归函数void hanoi (int n, char x, char y, char z)
{
if (n==1)
move(x, 1, z);
else {
hanoi(n-1, x, z, y);
move(x, n, z);
hanoi(n-1, y, x, z);
}
} null二叉树的遍历 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P))
{
if (T) {
Visit(T->data);
(PreOrderTraverse(T->lchild, Visit);
(PreOrderTraverse(T->rchild, Visit);
}
} // PreOrderTraversenull一、分治法 (Divide and Conquer)
(又称分割求解法)如何
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
递归函数?二、后置递归法(Postponing the work)三、回溯法(Backtracking)null 对于一个输入规模为 n 的函数或问题,
用某种方法把输入分割成 k(1
ppt
关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt
r表结点null例一 求广义表的深度例二 复制广义表例三 创建广义表的存储结构null广义表的深度=Max {子表的深度} +1例一 求广义表的深度可以直接求解的两种简单情况为:
空表的深度 = 1
原子的深度 = 0 将广义表分解成 n 个子表,分别(递归)求得每个子表的深度,null int GlistDepth(Glist L) {
// 返回指针L所指的广义表的深度
for (max=0, pp=L; pp; pp=pp->ptr.tp){
dep = GlistDepth(pp->ptr.hp);
if (dep > max) max = dep;
}
return max + 1;
} // GlistDepthif (!L) return 1;
if (L->tag == ATOM) return 0; nullfor (max=0, pp=L; pp; pp=pp->ptr.tp){
dep = GlistDepth(pp->ptr.hp);
if (dep > max) max = dep;
}例如:pppp->ptr.hppppppp->ptr.hppp->ptr.hpnull例二 复制广义表新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为:
空表复制求得的新表自然也是空表;
原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分,分别(递归)复制求得新的表头和表尾,null若 ls= NIL 则 newls = NIL
否则
构造结点 newls,
由 表头ls->ptr.hp 复制得 newhp
由 表尾 ls->ptr.tp 复制得 newtp
并使 newls->ptr.hp = newhp,
newls->ptr.tp = newtp复制求广义表的算法描述如下:nullStatus CopyGList(Glist &T, Glist L) {
if (!L) T = NULL; // 复制空表
else {
if ( !(T = new GLNode) )
exit(OVERFLOW); // 建表结点
T->tag = L->tag;
if (L->tag == ATOM)
T->atom = L->atom; // 复制单原子结点
else { }
} // else
return OK;
} // CopyGList分别复制表头和表尾nullCopyGList(T->ptr.hp, L->ptr.hp);
// 复制求得表头T->ptr.hp的一个副本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;null例三 创建广义表的存储结构 对应广义表的不同定义方法相应地有不同的创建存储结构的算法。null 假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L,建立相应的存储结构。 由于S中的每个子串i定义 L 的一个子表,从而产生 n 个子问题,即分别由这 n个子串 (递归)建立 n 个子表,再组合成一个广义表。 可以直接求解的两种简单情况为:
由串( )建立的广义表是空表;
由单字符建立的子表只是一个原子结点。null如何由子表组合成一个广义表? 首先分析广义表和子表在存储结构中的关系。先看第一个子表和广义表的关系:指向广义表
的头指针指向第一个
子表的头指针null再看相邻两个子表之间的关系:指向第i+1个
子表的头指针指向第i个
子表的头指针可见,两者之间通过表结点相链接。null若 S = ( ) 则 L = NIL否则 构造第一个表结点 *L,并从串 S 中分解出第一个子串 1, 对应 创建第一个子广义表 L->ptr.hp;若剩余串非空,则构造第二个表结点 L->ptr.tp, 并从串 S 中分解出第二个子串 2, 对应建第二个子广义表 ………;依次类推,直至剩余串为空串止。nullvoid CreateGList(Glist &L, String S) {
if (空串) L = NULL; // 创建空表
else {
L = new GLNode; // 生成表结点
L->tag=List; p=L;
sub=SubString(S,2,StrLength(S)-1);
// 脱去串 S 的外层括弧
} // else
} 由sub中所含n个子串建立n个子表;nulldo {
sever(sub, hsub); // 分离出子表串hsub=i
if (!StrEmpty(sub) {
p->ptr.tp=new(sizeof(GLNode));
// 建下一个子表的表结点*(p->ptr.tp)
p=p->ptr.tp;
}
} while (!StrEmpty(sub));
p->ptr.tp = NULL; // 表尾为空表创建由串hsub定义的广义表p->ptr.hp;nullif (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);
//递归建广义表 null后置递归的设计思想为:null 递归的终结状态是,当前的问题可以直接求解,对原问题而言,则是已走到了求解的最后一步。链表是可以如此求解的一个典型例子。
例如:编写“删除单链表中所有值为x 的数据元素”的算法。null1) 单链表是一种顺序结构,必须从第一个结点起,逐个检查每个结点的数据元素;分析:2) 从另一角度看,链表又是一个递归结构,若 L 是线性链表 (a1, a2, , an) 的头指针,则 L->next是线性链表 (a2, , an)的头指针。null a1 a2 a3 an …L例如: a1 a2 a3 an L a1 a2 a3 an L已知下列链表1) “a1=x”, 则 L 仍为删除 x 后的链表头指针2) “a1≠x”, 则余下问题是考虑以 L->next 为头指针的链表…… a1 L->nextL->next=p->nextp=L->nextnullvoid delete(LinkList &L, ElemType x) {
// 删除以L为头指针的带头结点的单链表中
// 所有值为x的数据元素
if (L->next) {
if (L->next->data==x) {
p=L->next; L->next=p->next;
free(p); delete(L, x);
}
else delete(L->next, x);
}
} // deletenull删除广义表中所有元素为x的原子结点分析:
比较广义表和线性表的结构特点:相似处:都是链表结构。不同处:1)广义表的数据元素可能还是个
广义表;
2)删除时,不仅要删除原子结点,
还需要删除相应的表结点。nullvoid Delete_GL(Glist&L, AtomType x) {
//删除广义表L中所有值为x的原子结点
if (L) {
head = L->ptr.hp; // 考察第一个子表
if ((head->tag == Atom) &&
(head->atom == x))
{ } // 删除原子项 x的情况
else
{ }// 第一项没有被删除的情况
}
} // Delete_GL… …… …nullp=L; L = L->ptr.tp; // 修改指针
free(head); // 释放原子结点
free(p); // 释放表结点
Delete_GL(L, x); // 递归处理剩余表项 1 L0 x 1 pL headnullif (head->tag == LIST) //该项为广义表
Delete_GL(head, x);
Delete_GL(L->ptr.tp, x);
// 递归处理剩余表项 1 L0 a 1 1 headL->ptr.tpnull回溯法是一种“穷举”方法。其基本思想为: 假设问题的解为 n 元组 (x1, x2, …, xn),
其中 xi 取值于集合 Si。
n 元组的子组 (x1, x2, …, xi) (in)的一个合法布局
// 时,输出之。
if (i>n) 输出棋盘的当前布局;
else for (j=1; j<=n; ++j) {
在第 i 行第 j 列放置一个棋子;
if (当前布局合法) Trial(i+1, n);
移去第 i 行第 j 列的棋子;
}
} // trial null回溯法求解的算法一般形式:void B(int i, int n) {
// 假设已求得满足约束条件的部分解(x1,..., xi-1),本函
//数从 xi 起继续搜索,直到求得整个解(x1, x2, … xn)。
if (i>n)
else while ( ! Empty(Si)) {
从 Si 中取 xi 的一个值 viSi;
if (x1, x2, …, xi) 满足约束条件
B( i+1, n); // 继续求下一个部分解
从 Si 中删除值 vi;
}
} // Bnull综合几点:
1. 对于含有递归特性的问题,最好设计递归形式的算法。但也不要单纯追求形式,应在算法设计的分析过程中“就事论事”。例如,在利用分割求解设计算法时,子问题和原问题的性质相同;或者,问题的当前一步解决之后,余下的问题和原问题性质相同,则自然导致递归求解。null2. 实现递归函数,目前必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数;反之,一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。
null3. 分析递归算法的工具是递归树,从递归树上可以得到递归函数的各种相关信息。例如:递归树的深度即为递归函数的递归深度;递归树上的结点数目恰为函数中的主要操作重复进行的次数;若递归树蜕化为单支树或者递归树中含有很多相同的结点,则表明该递归函数不适用。null 例如: n=3的梵塔算法中主要操作move的执行次数可以利用下列递归树进行分析:move(3, a, b, c)move(2, a, c, b)move(2, b, a, c)move(1, a, b, c)move(1, c, a, b)move(1, b, c, a)move(1, a, b, c)上图递归树的中序序列即为圆盘的移动操作序列。null如: 求n!的递归函数的递归树已退化为一个单枝树;nn-110。。。F5F4F3F3F2F2F1F1F0F1F0。。。而计算斐波那契递归函数的递归树中有很多重复出现的结点。null4. 递归函数中的尾递归容易消除。
例如:先序遍历二叉树可以改写为:
void PreOrderTraverse( BiTree T) {
While (T) {
Visit(T->data);
PreOrderTraverse(T->lchild);
T = T->rchild;
}
} // PreOrderTraversenullvoid delete(LinkList &L, ElemType x) {
// L为无头结点的单链表的头指针
if (L) {
if (L->data=x) {
p=L; L=L->next;
free(p); delete(L, x);
}
else delete(L->next, x);
}
}又如:nullvoid delete(LinkList &L, ElemType x) {
// L为带头结点的单链表的头指针
p=L->next; pre=L;
while (p) {
if (p->data=x) {
pre->next=p->next;
free(p); p=pre->next;
}
else { pre=p; p=p->next; }
}
}可改写为null 5. 可以用递归方程来表述递归函数的
时间性能。
例如: 假设解n个圆盘的梵塔的执行
时间为T(n)
则递归方程为: T(n) = 2T(n-1) + C,
初始条件为: T(0) = 0null1. 了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法。
2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。
3. 了解稀疏矩阵的两类压缩存储方法的特点和适用范围,领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。null4. 掌握广义表的结构特点及其存储表示方法,读者可根据自己的习惯熟练掌握任意一种结构的链表,学会对非空广义表进行分解的两种分析方法:即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。
5. 学习利用分治法的算法设计思想编制递归算法的方法。