数据结构与算法第二章清华大学出版社赵玉兰PPT课件

1、2.1 线性表ADT线性表 线性表（Linear List） 例1 26个大写英文字母组成的字母表 （A，B，C，Z） 例2 某个学生宿舍学生姓名 （“wan”，“li”，“zhao”，“ye”，“hao”，“jia”） 例3 学生信息情况登记表姓姓 名名学学 号号性性 别别年年 龄龄班班 级级家庭住址家庭住址陈陈 燕燕060001女女21计计06内蒙古内蒙古刘刘 伟伟060002男男21计计06北京北京王树林王树林060003男男22计计06山东山东第1页/共109页2.1 线性表ADT线性表 定义 由 n (n0) 个性质相同的数据元素 a1, a2, , an 组成的有限序列 数据元素的

2、个数 n (n0) 定义为表的长度，当 n=0 时称为空表 常常将非空的线性表（n0）记作： L=( a1, a2, , ai, , an ) 注意：这里的数据元素 ai ( 1i n ) 只是一个抽象的符号，其具体含义在不同的情况下可以不同。第2页/共109页2.1 线性表ADT线性表 线性表的逻辑特征 有限性：线性表中数据元素的个数是有穷的 相同性：线性表中数据元素的类型是同一的 顺序性 有且仅有一个开始结点 a1，它没有前趋，而仅有一个后继 a2 有且仅有一个终端结点 an，它没有后继，而仅有一个前趋 an-1 其余的内部结点 ai (2i n-1) 都有且仅有一个前趋 ai-1 和一个

3、后继 ai+1 线性表的逻辑结构是一种典型的线性结构第3页/共109页2.1 线性表ADT线性表 抽象数据类型线性表的定义 ADT List Data 数据元素表 size：数据元素的个数 Operation Constructor Process：创建空表 Clear Process：清空线性表IsEmpty Process：判断线性表是否为空 Output：若线性表为空，返回true，否则返回false第4页/共109页2.1 线性表ADT线性表 Length Process：求线性表中元素个数 Output：返回线性表中元素个数 GetElem Input：要取出的元素的位置 Proce

4、ss：取出指定位置上的元素 Output：返回取出的元素值 Locate Input：要定位的元素 Process：为指定元素定位 Output：若线性表中有给定元素，返回元素位置，否则 返回-1第5页/共109页2.1 线性表ADT线性表 Insert Input：被插入元素值及其位置 Process：将给定元素插入指定位置 Delete Input：被删除元素的位置 Process：若线性表中有给定元素，则删除它 Prior Input：要求前驱的元素 Process：求给定元素的直接前驱 Next Input：要求后继的元素 Process：求给定元素的直接后继 / List 第6页/共

5、109页2.1 线性表ADT线性表 例4 假设利用线性表 LA 和 LB 分别表示两个集合A 和 B（线性表中的数据元素即为集合中的成员），现求一个新的集合 AB，并用LA表示结果集合。void Intersection ( List LA, List LB ) int i=1; while ( i = LA.size ) x = LA.GetElem(i); /在LA中取一元素 k = LB.Locate(x); /在LB中搜索它 if ( k = -1 ) /在LB中未找到，则在LA中删除它 LA.Delete (i); LA.size -; else i+; / Intersection

6、第7页/共109页2.1 线性表ADT线性表 例5 假设利用线性表 LA 和 LB 分别表示两个集合A 和 B（线性表中的数据元素即为集合中的成员），现求一个新的集合 AB，并用LA表示结果集合。void Union( List LA, List LB ) int n; for ( int i=1; i=LB.size; i+ ) x = LB.GetElem(i); /在LB中取一元素 k = LA.Locate(x); /在LA中搜索它 if ( k = -1 ) /在LA中未找到，则在LA中插入它 n=LA.size; LA.Insert (n, i); LA.size +; / Int

7、ersection第8页/共109页2.1 线性表线性表的顺序存储顺序表 定义 顺序存储的线性表 把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里存储要点用一段地址连续的存储单元依次存储线性表中的数据元素a1a2ai-1aian第9页/共109页2.1 线性表线性表的顺序存储 例：（34, 23, 67, 82）34236782存储空间的起始地址基地址用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度 4第10页/共109页2.1 线性表线性表的顺序存储 存储结构与逻辑结构的关系 存储地址存储地址 内存状态内存状态线性表中线性表中的位序的位序LOC(a1)a11LOC(

8、a1)+ma22LOC(a1)+(i-1) maiiLOC(a1)+(n-1) mann 空闲空闲 顺序表存储结构示意图顺序表存储结构示意图LOC(ai) = LOC(a1) + (i-1)m基地址LOC(ai) = LOC(ai-1) + m一个数据元素所占存储量顺序表是一种随机存取的存储结构第11页/共109页2.1 线性表线性表的顺序存储u注意线性表的第 i 个元素 ai 存储在数组下标为 i-1 的位置线性表的长度 size 与数组的长度 MaxListSize 是不同的lsize=n，大小可变lMaxListSize 是数组的长度，大小不变lsizeMaxListSize表的长度空闲

9、anaiai-1a2a1datan-1 MaxListSize-1sizeMaxListSizei-1i-210下标如何实现顺序表的内存分配？顺序表一维数组第12页/共109页2.1 线性表线性表的顺序存储const int MaxListSize=100;class SeqList DataType dataMaxListSize; int size; /元素的个数 public: List( )size = 0; /构造一个空线性表 void Clear( ); /清空顺序表 bool IsEmpty( ); /判断如果为空表，返回true，否则 返回false DataType GetE

10、lem(int k)return datak-1; /返回第k个元素 int Locate(DataType e); /返回第一个与元素e匹配的元素 位序 DataType Prior ( DataType e); /返回元素e 的前驱 DataType Next (DataType e); /返回元素e 的后继 void Insert (DataType e, int i ); /在表中第 i 个位置插入e DataType Delete ( int i ); /删除第i个元素，并返回其值；/SeqList第13页/共109页2.1 线性表线性表的顺序存储基本操作在顺序表中的实现 定位操作算

11、法2.4 定位int Locate (DataType e) int i = 0; while ( i =size ) return -1;/没有找到 else return i; /找到此元素，返回其下标/ Locate 注意序号和下标之间的关系！第14页/共109页2.1 线性表线性表的顺序存储定位成功定位不成功e48e50第15页/共109页2.1 线性表线性表的顺序存储 定位算法的时间复杂度 基本操作：比较 成功时 最好情况： 最坏情况：)( nO22)(1*n1)2(111)(1=10101nnnnnincpEniiniilo不成功时：比较 n 次第16页/共109页2.1 线性表线

12、性表的顺序存储在在 i=4 处插入处插入 下标下标数据数据元素元素012 113 221 324 4 5 6 7 82528304277插入u在顺序表中的第 i 个位置上插入 eai和ai+1之间的逻辑关系发生了变化存储位置要反映这个变化第17页/共109页2.1 线性表线性表的顺序存储算法2.2 插入void Insert (DataType e, int i ) if ( i size | size = = MaxListSize -1 ) exit; else for (j=size; ji; j- ) dataj = dataj-1; datai = e; /插入成功 size+; /

13、 Insert什么时候不能插入？注意边界条件第18页/共109页2.1 线性表线性表的顺序存储 插入算法的时间复杂度 基本语句：移动元素 最好情况：不移动（i=n），时间复杂度为O(1) 最坏情况：移动 n 个元素（i=0），时间复杂度为O(n) 平均情况：设插入每个数据元素的概率相等，则)(nO221)(1)(1 0)1(11)(11=E0isnnnnnninnni第19页/共109页2.1 线性表线性表的顺序存储 删除 删除顺序表中第 i 个位置上的元素DataType Delete ( int i ) if (i= size) return nulldata; /被删除的元素下标错 el

14、se size-; e=datai; for ( int j=i; jnext=NULL); /判断是否为空链表 DataType Prior ( DataType e); /返回e 的前驱结点元素 DataType Next (DataType e); /返回e 的后继结点元素 void Insert (DataType x, int i); /在第i个结点之前插入元素值为x的结点 Datatype Delete (int i); /删除第i个结点，并返回其元素值 void Clear( ); /清空链表;/ nextList第29页/共109页2.1 线性表线性表的链式存储 取元素Data

15、Type GetElem (int i) if (head-next=NULL) /空链表，返回空值 return nulldata; else p=head; k=0; while (p & knext; k+; if (!p | k=0) return nulldata; / i超出链表元素的范围 else return p-data;/ GetElem第30页/共109页2.1 线性表线性表的链式存储 插入操作 将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间 插入过程：1）定位；2）插入。pai-1headaixa1newnode new

16、nodenext = pnext; pnext = newnode;第31页/共109页2.1 线性表线性表的链式存储void Insert ( DataType x, int i ) /在第i个结点位置上插入元素值为x的结点 Node* p = head; int k = 0; if (isize) return nulldata; / 插入位置错误 while ( p & knext; k+; /找到插入位置 if (!p) exit; Node* newnode= new Node(); newnode-data=x; newnode-next=p-next; p-next=ne

17、wnode; size+;/ Insert第32页/共109页2.1 线性表线性表的链式存储 删除操作 将表的第 i 个结点，即 ai 删去 删除过程：1）定位；2）删除。pai-1headaia1ai+1q q = pnext; pnext = qnext; delete q;第33页/共109页2.1 线性表线性表的链式存储DataType Delete (int i) /删除第i个结点 Node* p = head; int k=0; if (isize) / 结点序号i超出链表结点范围，返回空值 return nulldata; while ( p & knext; k+; i

18、f ( p=NULL ) cout next; p-next = q-next; e= q-data; delete q; size-; return e; / Delete第34页/共109页2.1 线性表线性表的链式存储 建立单链表 头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。第35页/共109页2.1 线性表线性表的链式存储头插法建表void Create (i

19、nt n) head=new Node( ); /创建头结点 head-next=NULL; for ( i=n; i0; i-) p=new Node( ); if (p=NULL) exit; cinp-data; p-next=head-next; head-next=p; size=n;第36页/共109页2.1 线性表线性表的链式存储 尾插法建表 该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。 （1）创建头结点 head，使尾结点 r 为NULL； （2）新建结点 p，如果 head- next = NULL，则 head- next

20、 =p；r=p； （3）否则，r- next =p；r=p；重复（2），（3） （4）如果r!= NULL；则r- next =NULL第37页/共109页2.1 线性表线性表的链式存储尾插法建表void Create (int n) head=new Node( ); head-next=NULL; r=head; for ( i=n; i0; i-) p=new Node( ); if (p=NULL) exit; cinp-data; rnext=p; r=p; size=n;第38页/共109页2.1 线性表线性表的链式存储 双向链表（Double nexted list） 每个结点中

21、有两个指针域 指向其直接前趋结点 指向其直接后继结点 每个结点结构第39页/共109页2.1 线性表线性表的链式存储 带头结点的双向链表 heada1a2anheadu结点指针的指向p = p - prior - next = p - next - prior空表非空表p-priorp-nextp第40页/共109页2.1 线性表线性表的链式存储 带头结点的双向链表类的定义class DNode DataType data; DNode *prior; /指向前驱的指针 DNode *next; /指向后继的指针 public: DNode(DataType d=nulldata) data=

22、d; prior=next=NULL; friend class DBList; / DNode第41页/共109页2.1 线性表线性表的链式存储class DBList DNode *head; int size; public: DBList()head=new DNode(); size=0; /构造函数，创建空链表 void Create (int n); /创建长度为n的双链表 DataType GetElem (int i); /取得第i个元素 Dnode* Locate (DataType e); /返回第一个与e匹配的结点指针 bool IsEmpty ( ); /判断是否为空

23、链表 void Insert (DataType e, int i ); /在第i个结点前插入值为e的结点 DataType Delete ( int i ); /删除第i个结点，并返回其元素值 void Clear ( ); /清空链表;/ DBList第42页/共109页2.1 线性表线性表的链式存储 定位定位成功head定位不成功head第43页/共109页2.1 线性表线性表的链式存储 插入操作（在结点 p 之前插入结点 s） s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s;考虑：哪些语句可以交换位置？哪些不能交

24、换？esabp s = new DNode (e);第44页/共109页2.1 线性表线性表的链式存储 删除操作（删除结点 p）p-next-prior = p-prior; aiai+1ai-1pp-prior-next = p-next;delete p;第45页/共109页2.1 线性表线性表的链式存储 注意 与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针。第46页/共109页2.1 线性表线性表的链式存储 循环链表 是线性链表的变形 表尾结点的 next 指针不为 NULL，而是指向了链表的头结点 特点 从表中任一结点出发，均可访问表中其他任一结点

25、headhead第47页/共109页2.1 线性表线性表的链式存储 循环链表基本操作的实现 基本操作与单链表类似 在循环链表中遍历的终止条件是什么？ 终止 p-next = NULL;或 p = NULL; 终止应该是 p-next = head ; 或 p = head ; 开始 p = head-next ; 或 p = head ; 第48页/共109页2.1 线性表线性表的链式存储 单链表的应用：一元多项式求和 一元多项式nnnxpxpxppxP.)(2210在计算机中，可以用一个线性表来表示 P = ( p0 , p1 , , pn )但是对于下述多项式，该表示方法并不合适 P(x)

26、 = 1 + 3x10000 2x20000第49页/共109页2.1 线性表线性表的链式存储 一般情况下，一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为ei 项的非零系数， 0e1 e2 term.expn; b=pb-term.expn; /指数 if (anext=pa; pc=pa; pa=pa-next; /pa指针后移 else if (ab) /多项式bh中当前结点的指数值小 pc-next=pb; pc=pb; pb=pb-next; /pb指针后移 else if ( pa.coef+pb.coefnext; del

27、ete p; p=pb; pb=pb-next; delete p; else /将pb结点的系数加入pa结点 pa-coef=pa.coef+pb.coef; pc-next=pa; pc=pa; pa=pa-next; p=pb; pb=pb-next; delete p; / while if ( pa ) pc-next=pa; else pc-next=pb; return ah;第54页/共109页2.1 线性表线性表的链式存储 例2 非递减有序线性表的归并 已知线性表LA和线性表LB中的数据元素按值非递减有序排列， 现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值

28、非递减有序排列。 如 LA=（3, 5, 8, 11） LB=（2, 6, 8, 9, 11, 15, 20） 则LC=（2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) 第55页/共109页2.1 线性表线性表的链式存储 归并算法void MergeList(LinkList&La,LinkList &Lb,LinkList &Lc) pa=La.head-next; pb=Lb.head-next; Lc=La; pc=Lc.head; while(pa & pb) if(pa-datadata) pc-next=pa; pc=pa;

29、 pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; delete Lb.head;/end MergeList第56页/共109页2.1 线性表线性表的链式存储 例3 约瑟夫环问题 n (n0) 个人围成一个圆圈，从第1个人开始顺时针报数，报到第m个人，令其出列。然后再从其下一个人开始重新报数，报到第m个人再令其出列，如此下去, 直到圆圈中只剩一个人为止。 例n=8 m=3第57页/共109页2.1 线性表顺序表和链表的比较 顺序表 没有附加存储空间开销 随机取得任一元素 预先申请固定长度的数组 插入、删除需要移

30、动元素，运算时间代价O(n) 链表 插入、删除运算时间代价O(1) ，但找第 i 个元素个元素时间代价O(n) 在运行时动态为表中新的元素分配存储空间 顺序取得某一元素 每个元素都有附加存储空间开销第58页/共109页2.1 线性表顺序表和链表的比较 根据应用选择顺序表和链表 顺序表 结点总数目大概可以估计 表中结点比较稳定（插入、删除操作少） 链表 结点数目无法预知 线性表中结点动态变化（插入、删除操作多） 第59页/共109页2.2 数组数组 数组的定义 是由一组具有相同类型的数据元素构成的有限序列，且存储在一块地址连续的内存单元中 数据元素可以是简单类型，也可以是构造类型 数据元素在数组

31、中的相对位置由其下标确定第60页/共109页2.2 数组数组 一维数组 只有一个下标的数组 特点 连续存储（别名 向量） 除第一个元素外，其它每一个元素有且仅有一个直接前驱 除最后一个元素外，其它每一个元素有且仅有一个直接后继第61页/共109页2.2 数组数组 存储时时0,) 1(0,)(iliLOCiaiLOClia第62页/共109页2.2 数组数组 二维数组 Anm 每个数据元素都有两个下标 行下标 列下标 二维数组是一个数据元素值为一维数组的一维数组n=4 m=6mn第63页/共109页2.2 数组数组 二维数组中的元素 aij可以看成属于两个向量：即第 i 行的向量Ai 和第 j

32、列的向量Bja00没有前驱结点，称之为开始结点； an-1,m-1没有后继结点，称之为终端结点aij （1 i n-2, 1 j m-2）有两个前驱结点 ai,j-1 , ai-1,j 两个后继结点 ai,j+1 , ai+1,j第0行的元素 a0j ( j=1,m-1) 只有一个前驱 a0,j-1 第0列的元素 ai0 ( i=1,n-1) 只有一个前驱 ai-1,0 第n-1行的元素an-1,j (j=0,m-2) 只有一个后继 an-1,j+1 第m-1列的元素ai,m-1 (i=0,n-2)只有一个后继 ai+1,m-1第64页/共109页2.2 数组数组 存储 0 00 10 201

33、1 01 11 2112 02 12 2211 01 11 211aaaamaaaamaaaama na na na nmA 有次序问题 约定的次序不同，则计算元素地址的公式也有所不同 C和PASCAL中采用行优先顺序；FORTRAN中采用列优先顺序第65页/共109页2.2 数组数组 a00 a01 . a0m-1 a10 a11 . a1m-1 an-10 an-11 an-1m-1 . 以行序为主序 an-1m-1 an-11 an-10 a1m-1 a11 a10 a0m-1 a01 a00n*m-1(n-1)*m1*mm-110以行序为主序存储的地址公式为：LOC(aij )=LOC

34、(a00) + ( im+j )l第66页/共109页2.2 数组数组 以列序为主序 a00 a01 . a0m-1 a10 a11 . a1m-1 an-10 an-11 an-1m-1 . an-1m-1 a1m-1 a0m-1 an-11 a11 a01 an-10 a10 a00n*m-1(m-1)*n1*nn-110以列序为主序存储的地址公式为：LOC(aij )=LOC(a00) + ( jn+i )l第67页/共109页2.2 数组数组n 维数组 各维元素个数为 b1, b2, b3, , bn 下标为（j1, j2, j3, , jn）的数组元素的存储地址ljbjLOCljbj

35、bbjbbbjLOCjjjLOCnninikkinnnnnn11113232121)0 ,0 ,0()()0 ,0 ,0(),(第68页/共109页2.2 数组特殊矩阵 矩阵 在科学与工程计算问题中，矩阵是一种常用的数学对象 在高级语言编制程序时，将一个矩阵描述为一个二维数组 特殊矩阵 具有许多相同值的元素或者零元素，并且这些元素在矩阵中的分步有一定规律的矩阵。 压缩存储 为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间。第69页/共109页2.2 数组特殊矩阵 对称矩阵的压缩存储 若一个 n 阶方阵 A 中的元素满足下述关系：aij=aji ( 0=i, j=n-1 )，则 A

36、 为对称矩阵 a00 a10 a11 a20 a21 a22 . an-1,0 an-1,1 an-1,2 an-1,n-1以行序为主序存储其下三角 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 对称矩阵第70页/共109页2.2 数组特殊矩阵 在下三角（包括对角线）中，元素总数为： 102/ ) 1() 1(ninniu将这些元素存放在一维数组 M0.n(n+1)/2-1中a00a10a11a20an-1,0an-1,n-1k=0123n(n-1)/2n(n+1)/2-1)(nnk(jii)(jjjij)(iik2102121当当uM k

37、和矩阵中的元素 aij 之间存在着一一对应关系第71页/共109页2.2 数组特殊矩阵 三角矩阵的压缩存储 以主对角线划分，三角矩阵有两种 上三角矩阵：其主对角线下方元素均为常数 下三角矩阵：其主对角线上方元素均为常数 大多数情况下，三角矩阵中的常数为零 a00 a01 a0,n-1 c a11 a1,n-1 . c c an-1,n-1 上三角矩阵 a00 c c a10 a11 c . an-1,0 an-1,1 an-1,n-1 下三角矩阵第72页/共109页2.2 数组特殊矩阵 可以用数组 M0.n(n+1)/2存储，其中常量c存入最后一个单元)n(nk(ji)n(njij)i(ik2

38、102121当当u下三角矩阵的元素 aij 和 Mk 之间的对应关系)n(nk(ji)n(njiij)ini(k21021212当当u上三角矩阵中的元素 aij 和 Mk 之间的对应关系第73页/共109页2.2 数组特殊矩阵 对角矩阵（或带宽矩阵）的压缩存储 a00 a01 a10 a11 a12 a21 a22 a23 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1带宽d=3的对角矩阵带宽d=3的对角矩阵中非零元素 aij 的地址公式为：LOC(aij)LOC(a00)3i1( ji1 )LOC(a00)2ija00 a01 a10 a11 a12

39、 an-1n-2 an-1n-1 .k=0 1 2 3 4 3(n-1) 以行序为主序第74页/共109页2.2 数组稀疏矩阵 定义 设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数（即snm），则称A为稀疏矩阵。0000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022000A6776 第75页/共109页2.2 数组稀疏矩阵 三元组顺序表稀疏矩阵的压缩存储方法之一 把稀疏矩阵的每个非零元素表示为三元组，并按行号的递增顺序（同一行按列的递增顺

40、序）排列行下标行下标 i列下标列下标 j元素值元素值 vu三元组顺序表的存储结构定义 const int SMax=1024; struct SPNode /三元组类 int i,j; /非零元素的行、列 DataType v; /非零元素值 ;第76页/共109页2.2 数组稀疏矩阵class SPMatrix /三元组表类 int rn,cn,en; /矩阵的行、列及非零元素的个数 SPNode dataSMax; /三元组表 public: SPMatrix(); SPMatrix(int m,int n,int s); /构造m行n列，元素个数 为s的稀疏矩阵 SPMatrix Tra

41、nspose(); /求转置矩阵 SPMatrix Add(SPMatrix&); /求矩阵的和 SPMatrix Multiply(SPMatrix&); /求矩阵的乘积 ;/ SPMatrix第77页/共109页2.2 数组稀疏矩阵 例011202920-3241432244118501553-7rn6cn6en8ijv三元组顺序表的缺点失去随机存取功能012345670 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0第78页/共109页2.2 数组稀疏矩阵 稀疏矩阵的转置转置

42、 其时间复杂度为： O(nm)用常规的二维数组表示时的转置算法for ( i=0; in; i+ ) for ( j=0; jm; j+ ) Tji = Mij;005280000007143600矩阵 T（53）028003600070500140矩阵 M（35）第79页/共109页2.2 数组稀疏矩阵(0, 1, 12)(0, 2, 9 )(2, 0, -3)(2, 4, 14)(3, 2, 24)(4, 1, 18)(5, 0, 15)(5, 3, -7)(0, 2, -3)(0, 5, 15)(1, 0, 12)(1, 4, 18)(2, 0, 9)(2, 3, 24)(3, 5, -

43、7)(4, 2, 14)M的三元组表示T的三元组表示0 12 9 0 00 0 0 0 0-3 0 0 0 140 0 24 0 00 18 0 0 015 0 0 -7 0M0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 0T转置第80页/共109页2.2 数组稀疏矩阵 问题：若采用三元组顺序表存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？u思路总行数 rn 和总列数 cn 互换；每个元素的行下标 i 和列下标 j 互换；按以行为主序的结构重新排列三元组内元素的顺序。上述

44、（1）和（2）容易实现，难点在（3）。第81页/共109页2.2 数组稀疏矩阵 方法1：转置 反复扫描 M.data 中的列序，从小到大依次进行转置5 6 8 0 2 -3 0 5 15 1 0 12 1 4 18 2 0 9 2 3 24 3 5 -7 4 2 14 qppcol=0col=1 6 5 8 0 1 12 0 2 9 2 0 -3 2 4 14 3 2 24 4 1 18 5 0 15 5 3 -7 i j vM76543210i j vT76543210第82页/共109页2.2 数组稀疏矩阵SPMatrix Transpose() SPMatrix T; T.rn=cn;

45、T.cn=rn; T.en=en; if (en) q=0; for (col=0; colcn; +col) for (p=0; pen; +p) if (datap.j=col) T.dataq.i= datap.j; T.dataq.j= datap.i; T.dataq.v=datap.v; +q; return T; / Transpose第83页/共109页2.2 数组稀疏矩阵 转置算法思想 设矩阵 M 列数为 cn，对其三元组表扫描 cn 次。 第 k 次扫描寻找所有列号为 k 的项，将其行号变列号、列号变行号，依次存放于转置矩阵 T 的三元组表中。第84页/共109页2.2 数

46、组稀疏矩阵 时间复杂度分析v主要时间消耗在查找 datap.j=col 上，由两重循环完成： for ( col=0; colcn; +col ) 循环次数cn for ( p=0; p0) /有非0元素 for ( i=0; icn; i+) /给数组num赋初值 numi=0; for (i=0; ien; i+) /求原矩阵中每一列非0元的个数 j= datai.j; numj+; 第90页/共109页2.2 数组稀疏矩阵 cpot0=0; /求原矩阵中每一列第一个元素在转置矩阵中的位置 for (i=1;icn;i+) cpoti= cpoti-1+numi-1; for(i=0; i

47、en; i+) /扫描原矩阵三元表进行转置 j=datai.j; k=cpotj; / 取到当前三元组在转置矩阵三元组表中的位置 T.datak.i= datai.j; T.datak.j= datai.i; T.datak.v= datai.v; cpotj+; /for i /if return T; / FastTranspose第91页/共109页2.2 数组稀疏矩阵 快速转置算法的效率分析v在空间上，附加了生成辅助向量表的工作。增开了2个长度为列长 cn 的数组 num 和 cpot。v在时间上，此算法用了4个并列的单循环，其中前3个单循环都是用来产生辅助向量表的。 for ( i=

48、0; icn; i+ ) 循环次数cn; for ( i=0; ien; i+ ) 循环次数en; for ( i=1; icn; i+ ) 循环次数cn; for ( i=0; ien; i+ ) 循环次数en; 时间复杂度(cn2)(en2)O( cnen )v最恶劣情况：enrncn（即矩阵中全部是非零元素），而此时的时间复杂度也只是O( rncn )，并未超过传统转置算法的时间复杂度。第92页/共109页2.2 数组稀疏矩阵 转置算法小结 传统转置：O( rncn ) 采用压缩存储 转置：O( cnen ) 快速转置：O( cnen ) 牺牲空间效率换时间效率第93页/共109页2.3

49、 字符串（String） 字符串的基本概念 字符串是 n ( n0 ) 个字符的有限序列，记为： s = a1 , a2 , . , an 串名串值（用 括起来）隐含结束符0 ，即ASCII码NUL第94页/共109页2.3 字符串（String）u串长：字符串中的字符个数（n0）。n=0 时称为空串。u空白串：由一个或多个空格符组成的串。u子串：串S中任意个连续的字符序列叫 S 的子串；S 叫主串。u子串位置：子串的第0个字符在主串中的位置。u字符位置：字符在串中的序号。u串相等：串长度相等，且对应位置上字符相等。 第95页/共109页2.3 字符串（String） 示例 设 A 和 B 分

50、别为：A=“This is a string” B=“is”，则B是 A 的子串，A 为主串。B 在 A 中首次出现所对应的主串位置是2。因此，称 B 在 A 中的位置为2。 空串是任意串的子串，任意串是其自身的子串。 空串和空白串有无区别？ 有区别。空串（Null String）是指长度为零的串；而空白串（Blank String），是指包含一个或多个空格的字符串。 现有以下4个字符串：a =BEI b =JING c = BEIJING d = BEI JING，问： 他们各自的长度？ b是哪个串的子串？在主串中的位置是多少？第96页/共109页2.3 字符串（String） 串的抽象数据

51、类型定义ADT String Data：零个或多个字符组成的字符序列 Operation Constructor Process：构造空串 Assign Input：被复制的字符串 Process：串赋值 Output：复制成功，返回true；否则，返回false 第97页/共109页2.3 字符串（String） Compare Input：用以比较的串 Process：串比较 Output：若大于，返回值大于0；若小于，返回值小于 0；若等于，返回值等于0 Length Process：求串长 Output：返回串中字符个数 Concat Input：串S1和S2 Process：串S1和

52、S2连接成新串 Output：连接成功，返回true；否则返回false第98页/共109页2.3 字符串（String） SubString Input：子串的位置和长度 Process：求子串 Output：返回子串 Index Input：子串以及开始匹配的位置 Process：子串匹配 Output：返回子串在开始位置之后的匹配位置 Replace Input：子串T和子串V Process：用子串V替换子串T / Sting第99页/共109页2.3 字符串（String） C+中有关字符串的库函数 头文件 #include int strcpy (char *str1, char *str2