第5讲数组和广义表.pptx

Section 1Array 数组的抽象数据类型定义数组的抽象数据类型定义ADT Array D=aj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n (n称数组的维数，称数组的维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维维下标下标)R=R1,R2,.,Rn Ri=|0 jk bk-1,1 k n且且k i,0 ji bi-2,i=2,.,n ADT Array 基本操作基本操作二维数组的定义二维数组的定义数据对象数据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL COL=|0ib1-2,0jb2-1 ROW=|0ib1-1,0 jb2-2基基 本本 操操 作作InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&x,index1,.,indexn)Assign(&A,x,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数若维数 n 和各维长度和各维长度 合法，则构造相应的合法，则构造相应的 数组数组A，并返回，并返回OK。DestroyArray(&A)操作结果：操作结果：销毁数组销毁数组A。Value(A,&x,index1,.,indexn)初始条件：初始条件：A是是n维数组，维数组，x为元素变为元素变 量，随后是量，随后是n 个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则x赋值赋值 为所指定的为所指定的A 的元素值，并的元素值，并 返回返回OK。Assign(&A,x,index1,.,indexn)初始条件：初始条件：A是是n维数组，维数组，x为为 元素变量，随后是元素变量，随后是n 个下标值。个下标值。操作结果：操作结果：若下标不超界，则若下标不超界，则 将将 x的值赋给所指的值赋给所指 定的定的A的元素，并的元素，并 返回返回 OK。一维数组一维数组n n定义定义 相同类型的数据元素的集合。相同类型的数据元素的集合。n n一维数组的示例一维数组的示例n n与顺序表的不同在于数组可以按与顺序表的不同在于数组可以按元素的下标直接存储和访问数组元素的下标直接存储和访问数组元素。元素。35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9一维数组一维数组(Array)类的定义类的定义template class Array Type*elements;/数组存放空间数组存放空间 int ArraySize;/当前长度当前长度 void getArray();/建立数组空间建立数组空间 public:Array(int Size=DefaultSize);Array(const Array&x);Array()delete elements;Array&operator=/数组赋值数组赋值 (const Array&A);Type&operator(int i);/取元素值取元素值 int Length()const return ArraySize;/取数组长度取数组长度 void ReSize(int sz);/扩充数组扩充数组 一维数组一维数组公共操作的实现公共操作的实现template void Array:getArray()/私有函数：创建数组存储空间私有函数：创建数组存储空间 elements=new TypeArraySize;template Array:Array(int sz)ArraySize=sz;getArray();template Array:Array(Array&x)int n=ArraySize=x.ArraySize;elements=new Typen;Type*srcptr=x.elements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;template Array:Array(Array&x)int Size=x.ArraySize;elements=new TypeSize;for(int i=0;iSize;i+)elementsi=x.elementsi;template Type&Array:operator(int i)if(i ArraySize-1)cerr “数组下标超界”endl;return NULL;return elementsi;template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=new Typesz;int n=(sz ArraySize)?sz:ArraySize;/按新的大小确定传送元素个数按新的大小确定传送元素个数 Type*srcptr=elements;Type*destptr=newarray;while(n-)*destptr+=*srcptr+;delete elements;elements=newarray;ArraySize=sz;多维数组多维数组n n多维数组是一维数组的推广多维数组是一维数组的推广n n多维数组是一种非线性结构。其特点多维数组是一种非线性结构。其特点是是每一个数据元素可以有多个直接前每一个数据元素可以有多个直接前驱和多个直接后继驱和多个直接后继。n n数组元素的下标一般具有固定的下界数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性和上界，因此它比其他复杂的非线性结构简单。结构简单。数组元素的遍历数组元素的遍历1)以行序为主序以行序为主序(按行排列按行排列):先排最右的下标先排最右的下标,依次向左依次向左,最后最后 排最左的下标排最左的下标2)以列序为主序以列序为主序(按列排列按列排列):先排最左的下标先排最左的下标,依次向右依次向右,最最 后排最右的下标后排最右的下标例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L 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 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n对于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(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)尽可能少存或不存零值元素；尽可能少存或不存零值元素；解决问题的原则解决问题的原则2)尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；3)操作方便。操作方便。即：即：1.能尽可能快地找到与下标值能尽可能快地找到与下标值 (i，j)对应的元素，对应的元素，2.能尽可能快地找到同一行或能尽可能快地找到同一行或 同一列的非零值元。同一列的非零值元。1)特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如:三角矩阵 对角矩阵2)随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则非零元在矩阵中的分布有一定规则 例如例如:对称矩阵对称矩阵 三角矩阵三角矩阵 三对角矩阵三对角矩阵 n阶对称矩阵阶对称矩阵 aij=aji 1=i,j=j j(j-1)/2+i-1 当ij K=矩阵的压缩存储对称矩阵 a11 a12 .a1n a21 a22.a2n an1 an2 .ann .a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：三角矩阵共计元素个三角矩阵共计元素个数为：数为：数为：数为：n(n+1)/2三角矩阵三角矩阵 a11 0 0.0 a21 a22 0.0 an1 an2 an3.ann .0Loc(aij)=Loc(a11)+(+(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵 a11 a12 0 .0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann.0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)|i-j|1a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：随机稀疏矩阵的顺序压缩存储随机稀疏矩阵的顺序压缩存储三元组表示法三元组表示法随机稀疏矩阵的链式压缩存储随机稀疏矩阵的链式压缩存储十字链表十字链表随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现非零元在矩阵中随机出现十字链表十字链表3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 112 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 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 SparseMatrix private:int row,col;/非零元素行号非零元素行号/列号列号 Type value;/非零元素的值非零元素的值templateclass SparseMatrixint Rows,Cols,Terms;/行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms;public:/三元组表三元组表 SparseMatrix(int Row,int Col,int Term);SparseMatrix&Transpose (SparseMatrix&);/转置转置 SparseMatrix&Add(SparseMatrix a,SparseMatrixb);/相加相加SparseMatrix&Multiply(SparseMatrix a,SparseMatrixb);/相乘相乘 稀疏矩阵的转置稀疏矩阵的转置用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;n一个一个 m n 的矩阵的矩阵 A，它的转置矩阵，它的转置矩阵 B 是一个是一个 n m 的矩阵，且的矩阵，且 Aij=Bji。即矩阵即矩阵 A 的行成为矩阵的行成为矩阵 B 的的列，矩阵列，矩阵 A 的列成为矩阵的列成为矩阵 B 的行。的行。n在稀疏矩阵的三元组表中，非零矩阵在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列元素按行存放。当行号相同时，按列号递增的顺序存放。号递增的顺序存放。n稀疏矩阵的转置运算要转化为对应三稀疏矩阵的转置运算要转化为对应三元组表的转置。元组表的转置。稀疏矩阵稀疏矩阵转置矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置稀疏矩阵转置算法思想稀疏矩阵转置算法思想n n设矩阵列数为设矩阵列数为 Cols，对矩阵三元组表对矩阵三元组表扫描扫描Cols 次。第次。第 k 次检测列号为次检测列号为 k 的的项。项。n n第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的项，的项，将其行号变列号、列号变行号，顺次将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。存于转置矩阵三元组表。template SparseMatrix&SparseMatrix:Transpose (SparseMatrix&a)SparseMatrix b(a.Cols,a.Rows,a.Terms);if(a.Terms 0)int CurrentP=0;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)按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&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素Col=M.datap.j;/p=1 col=2;p=2 col=5q=cpotcol;/p=1 q=cpot2=2;p=2 q=cpot5=5T.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=1;p0时时,表的表的第一个表元素第一个表元素称为广义表称为广义表 的的表头表头(head),除此之外除此之外,其它表元素其它表元素组组 成的表成的表称为广义表的称为广义表的表尾表尾(tail)广义表的广义表的抽象数据类型定义抽象数据类型定义ADT Glist 数据对象：数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或或 eiGList,AtomSet为某个数据对象为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2in ADT Glist基本操作基本操作:广广 义义 表表的基本操作的基本操作 结构的创建和销毁结构的创建和销毁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();广义表是广义表是递归递归定义的定义的线性结构线性结构，LS=(1,2,n)其中：其中：i 或为原子或为原子 或为广义表或为广义表例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,)广义表是一个广义表是一个多层次多层次的的线性结构线性结构例如：例如：D=(E,F)其中其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce广义表广义表 LS=(1,2,n)的结构特点的结构特点1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序2)广义表的广义表的长度长度定义为最外层包含元素定义为最外层包含元素 个数个数3)广义表的广义表的深度深度定义为所含括弧的重数定义为所含括弧的重数 “原子原子”的深度为的深度为 0 “空表空表”的深度为的深度为 1 4)广义表可以是一个广义表可以是一个递归递归的表的表5)任何一个非空广义表任何一个非空广义表 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)=()5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data广义表的头尾链表存储表示广义表的头尾链表存储表示Typedef enumATOM,LIST ElemTag;Typedef struct GLNode 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 tptag=0 atom tp5.6 广义表操作的递归函数广义表操作的递归函数递归函数递归函数 一个含直接或间接调用本函数语句含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1)在每一次调用自己时，必须是(在某 种意义上)更接近于解更接近于解;2)必须有一个终止终止处理或计算的准则准则。广义表从结构上可以分解成广义表广义表 =表头表头 +表尾表尾 或者或者广义表广义表 =子表子表1+子表子表2+子表子表n 因此常利用分治法求解之。算法设计中的关键问题是，如何将如何将 l 个子问题的解组合成原问题的解。个子问题的解组合成原问题的解。广义表的头尾链表存储表示：广义表的头尾链表存储表示：typedef enum ATOM,LIST ElemTag;/ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/标志域 union AtomType atom;/原子结点的数据域 struct struct GLNode*hp,*tp;ptr;*GListtag=1 hp tpptr表结点例一例一 求广义表的深度求广义表的深度例二例二 复制广义表复制广义表例三例三 创建广义表的存储结构创建广义表的存储结构广义表的深度广义表的深度=Max 子表的深度子表的深度+1例一例一 求广义表的深度求广义表的深度可以直接求解的两种简单情况为：空表的深度空表的深度=1 原子的深度原子的深度=0 将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，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;1 1 1 L for(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.hp例二例二 复制广义表复制广义表新的广义表由新的表头和表尾构成。新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为：空表复制求得的新表自然也是空表空表复制求得的新表自然也是空表;原子结点可以直接复制求得。原子结点可以直接复制求得。将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，若若 ls=NIL 则则 newls=NIL否则否则 构造结点构造结点 newls,由由 表头表头ls-ptr.hp 复制得复制得 newhp 由由 表尾表尾 ls-ptr.tp 复制得复制得 newtp 并使并使 newls-ptr.hp=newhp,newls-ptr.tp=newtp复制求广义表的算法描述如下复制求广义表的算法描述如下:Status CopyGList(Glist&T,Glist L)if(!L)T=NULL;/复制空表 else if(!(T=(Glist)malloc(sizeof(GLNode)exit(OVERFLOW);/建表结点 T-tag=L-tag;if(L-tag=ATOM)T-atom=L-atom;/复制单原子结点 else /else return OK;/CopyGList分别复制表头和表尾分别复制表头和表尾CopyGList(T-ptr.hp,L-ptr.hp);/复制求得表头T-ptr.hp的一个副本L-ptr.hpCopyGList(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 个子表，再组合组合成一个广义表。可以直接求解的两种简单情况为：由串由串()建立的广义表是建立的广义表是空表；空表；由单字符建立的子表只是一个原子结点。由单字符建立的子表只是一个原子结点。如何由子表组合成一个广义表？如何由子表组合成一个广义表？首先分析广义表和子表在存储结构中首先分析广义表和子表在存储结构中的关系。的关系。先看第一个子表和广义表的关系先看第一个子表和广义表的关系:1 L指向广义表指向广义表的头指针的头指针指向第一个指向第一个子表的头指针子表的头指针再看相邻两个子表之间的关系再看相邻两个子表之间的关系:1 1 指向第指向第i+1个个子表的头指针子表的头指针指向第指向第i个个子表的头指针子表的头指针可见，两者之间通过表结点相链接。可见，两者之间通过表结点相链接。若若 S=()则则 L=NIL；否则，构造第一个表结点*L，并从串S中分解出第一个子串1，对应创建第一个子广义表 L-ptr.hp；若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表；依次类推，直至剩余串为空串止。void CreateGList(Glist&L,String S)if (空串)L=NULL;/创建空表 else L=(Glist)malloc(sizeof(GLNode);L-tag=List;p=L;sub=SubString(S,2,StrLength(S)-1);/脱去串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;/表尾为空表创建由串创建由串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 x 的数据元素的数据元素”的算法。1)单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素；分析分析: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-nextL-next=p-nextp=L-nextvoid 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);/delete删除广义表中所有元素为删除广义表中所有元素为x x的原子结点的原子结点分析分析:比较广义表和线性表的结构特点结构特点：相似处：相似处：都是链表结构。不同处：不同处：1)广义表的数据元素可能还是个 广义表；2)删除时，不仅要删除原子结点，还需要删除相应的表结点。void 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 p=L;L=L-ptr.tp;/修改指针free(head);/释放原子结点free(p);/释放表结点Delete_GL(L,x);/递归处理剩余表项 1 L0 x 1 pL headif(head-tag=LIST)/该项为广义表 Delete_GL(head,x);Delete_GL(L-ptr.tp,x);/递归处理剩余表项 1 L0 a 1 1 headL-ptr.tp回溯法回溯法是一种“穷举”方法。其基本思想为：假设问题的解为 n 元组(x1,x2,xn)，其中 xi 取值于集合 Si。n 元组的子组(x1,x2,xi)(in)的一个合法布局 /时，输出之。if(in)输出棋盘的当前布局;else for(j=1;jn)else while(!Empty(Si)从 Si 中取 xi 的一个值 viSi;if (x1,x2,xi)满足约束条件 B(i+1,n);/继续求下一个部分解 从 Si 中删除值 vi;/B综合几点：综合几点：1.对于含有递归特性含有递归特性的问题，最好设计递归形式的算法。但也不要单纯追求形不要单纯追求形式式，应在算法设计的分析过程中“就事论事”。例如，在利用分割求解设计算法时，子问题和原问题的性质相同；或者，问题的当前一步解决之后，余下的问题和原问题性质相同，则自然导致递归求解。2.实现实现递归函数，目前必须利用“栈栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。3.分析分析递归算法的工具是递归树递归树，从递归树上可以得到递归函数的各种相关信息。例如：递归树的深度即为递归函数的递归深度递归深度；递归树上的结点数目恰为函数中的主要操作重复进行重复进行的次数的次数；若递归树蜕化为单支树单支树或者递归树中含有很多相同的结点含有很多相同的结点，则表明该递归函数不适用。例如例如: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)上图递归树的中序序列即为圆盘的移动操作序列。上图递归树的中序序列即为圆盘的移动操作序列。又如又如:求求n!的递归函数的递归树已退化为一个的递归函数的递归树已退化为一个单枝树单枝树;而计算斐波那契递归函数的递归树中而计算斐波那契递归函数的递归树中有很多重复出现的结点。有很多重复出现的结点。nn-110。F5F4F3F3F2F2F1F1F0F1F0。4.递归函数中的尾递归尾递归容易消除。例如：先序遍历二叉树可以改写为：void PreOrderTraverse(BiTree T)While(T)Visit(T-data);PreOrderTraverse(T-lchild);T=T-rchild;/PreOrderTraversevoid 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);又如又如:void 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;可可改改写写为为 5.可以用递归方程递归方程来表述递归函数的 时间性能时间性能。例如:假设解n个圆盘的梵塔的执行 时间为T(n)则递归方程为：T(n)=2T(n-1)+C，初始条件为：T(0)=01.1.了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组组在在以以行行为为主主的的存存储储结结构构中中的地址计算方法。的地址计算方法。2.2.掌掌握握对对特特殊殊矩矩阵阵进进行行压压缩缩存存储储时时的下标变换公式。的下标变换公式。3.3.了了解解稀稀疏疏矩矩阵阵的的两两类类压压缩缩存存储储方方法法的的特特点点和和适适用用范范围围，领领会会以以三三元元组组表表示示稀稀疏疏矩矩阵阵时时进进行行矩矩阵阵运运算算采采用用的的处理方法处理方法。4.4.掌握广义表的结构特点及其存储掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为解为表头和表尾两部分或者分解为n n个子表。个子表。5.5.学习利用分治法的算法设计思学习利用分治法的算法设计思想编制递归算法的方法。想编制递归算法的方法。