数据结构第三章栈、队列、数组

1、第三课 栈、队列和数组第一节 栈栈顶栈顶栈底栈底一、基本术语限定仅在表尾进行F栈顶和栈底F栈能进行插入和删除一端称栈底。插入、删除的线性表。操作的一端称栈顶，另anai+1aiai-1a1一、基本术语F入栈和出栈先进后出一、基本术语栈中元素个数。F空栈F栈的长度长度为0的栈。二、抽象数据类型定义P45F栈三、顺序栈F存储结构设计【例】设栈S=(34,28,76,53,99)9934762853#define MAXSIZE 10040213MAXSIZE-15typedef struct ElemType elemMAXSIZE;int length;SqStack;SqStack S;S.e

2、lemS.length三、顺序栈F入栈【例】设栈S=(34,28,76,53,99)，5993476285340213MAXSIZE-1S.elemS.length待入栈元素e=82，执行push(&S,e)e82826三、顺序栈F出栈【例】设栈S=(34,28,76,53,99)，5993476285340213MAXSIZE-1S.elemS.length执行pop(&S,&e)e4四、链栈F存储结构设计head99 34287653【例】设栈S=(34,28,76,53,99)四、链栈F入栈head9934287653【例】设栈S=(34,28,76,53,99)

3、待入栈元素e=82，执行push(S,e)e8282ps四、链栈F出栈head9934287653【例】设栈S=(34,28,76,53,99)执行pop(S,e)ep99q四、链栈F存储结构设计head34 99537628【例】设栈S=(34,28,76,53,99)四、链栈F入栈head3499537628【例】设栈S=(34,28,76,53,99)待入栈元素e=82，执行push(S,e)e8282s四、链栈F出栈head3499537628【例】设栈S=(34,28,76,53,99)执行pop(S,e)e99p问题：设表达式中可含算符 +、-、*、/、( )及操作数，并设表达式无

4、语法错误，试设计算法求其值。五、应用：表达式求值表达式的表示方法u中缀表达式u前缀表达式u后缀表达式5+6+5656+(1+2*(3+4)/5*(7-6)*/+1*2+345761234+*+5/76-*定义：calc(exp)操作结果：输出表达式求值结果原型：int calc(char *exp);五、应用：表达式求值F中缀表达式F前缀表达式F后缀表达式1+3*4/2-5#运算数栈运算符栈#i1+3*4=12/26-57 2exp【例】F中缀表达式1+2*3/(5-4)#运算数栈运算符栈#i+2*3=6/(51-41 6 7【例】expF中缀表达式思路：表达式起始符入运算符栈；读表达式中字符

5、；若当前字符为，且运算符栈中栈顶元素也是，则表达式计算结束，返回运算结果，否则执行；五、应用：表达式求值若当前字符不是运算符，则入运算数栈，并读下一字符；否则与运算符栈中栈顶元素进行优先级比较：设表达式中算符出现在算符前，则两者优先关系：=无无)无=/*-+#)(/*-+12五、应用：表达式求值当前运算符入栈，并读下一字符；Y栈顶优先级低Y两者优先级同Y栈顶优先级高必为左右括号相遇，令栈顶元素出栈，读下一字符；完成栈顶运算，结果入运算数栈；反复执行、，直至计算完成。-+1/*3425#Y前缀表达式1+3*4/2-5#【例】-+1/*3425expnewexp12 6 7 2思路：取最后面的运算

6、符为当前运算符；取当前运算符后面的两个数为运算数；运算结果替换当前算式；重复执行直至所有运算符都运算完毕。五、应用：表达式求值第二节 队列一、基本术语队列是限定在一端进行插入，而在另一端进行删除的线F入队和出队F队列、队头和队尾性表，能插入的一端称为队尾，能删除的一端称为队头。队头队尾先进先出一、基本术语队列中元素个数。F空队F队列的长度长度为0的队列。二、抽象数据类型定义F队列P59三、链队列F存储结构设计head99 34287653【例】设队列Q=(34,28,76,53,99)tailtypedef struct QNodeElemType data;/数据域struct QNode

7、*next;/指针域QNode;三、链队列F存储结构设计head99 34287653【例】设队列Q=(34,28,76,53,99)tailtypedef struct QNode *head;QNode *tail; LinkQueue;LinkQueue Q;Q.headQ.tailQ.head三、链队列F入队9934287653【例】设队列Q=(34,28,76,53,99)Q.tail待入队元素e=82，执行enqueue(Q,e)e8282sF出队【例】设队列Q=(34,28,76,53,99)执行dequeue(Q,e)ep三、链队列Q.head99 34287653Q.tail

8、34F出队【例】设队列Q=(99)执行dequeue(Q,e)ep三、链队列Q.head99 Q.tail99四、顺序队列F存储结构设计【例】设队列Q=(34,28,76,53,99)9934762853#define MAXSIZE 10040213MAXSIZE-15typedef struct ElemType elemMAXSIZE;int head;int tail;SqQueue Q;Q.elemQ.tail0Q.headSqQueue;四、顺序队列F入队【例】设队列Q=(34,28,76,53,99)993476285340213MAXSIZE-15Q.elemQ.tail0Q.

9、head待入队元素e=82，执行enqueue(Q,e)56e82826Q.elemQ.tail=e;Q.tail+;四、顺序队列F出队【例】设队列Q=(34,28,76,53,99)9934762853402135Q.elemQ.tail0Q.head执行dequeue(Q,e)56e1e=Q.elemQ.head;Q.head+;82四、顺序队列F可能的问题【例】设队列Q=(34,28,76,53,99)9934762853402135Q.elemQ.tail0Q.head执行dequeue(Q,e)56e1执行dequeue(Q,e)执行dequeue(Q,e)2 3执行enqueue(

10、Q,e) e=82826执行enqueue(Q,e) e=4747477执行enqueue(Q,e) e=151547四、顺序队列F循环队列【例】设队列Q如图，9953402136Q.elemQ.tail3Q.head执行enqueue(Q,e) e=4756e8247Q.elemQ.tail=e;Q.tail+;Q.tail=(Q.tail+1)%7;0执行enqueue(Q,e) e=1515151入队四、顺序队列F循环队列【例】设队列Q如图，402133Q.elemQ.tail6Q.head执行dequeue(Q,e)56e91e=Q.elemQ.head;Q.head+;471566Q

11、.head=(Q.head+1)%7;0出队四、顺序队列F循环队列【例】设队列Q如图，执行length(Q)求队长9953402136Q.elemQ.tail3Q.head5682Q.tail-Q.head四、顺序队列F循环队列【例】设队列Q如图，402133Q.elemQ.tail6Q.head执行length(Q)5691471566求队长MAXSIZE-(Q.head-Q.tail)四、顺序队列F循环队列求队长Q.tailQ.head时：Q.tailQ.head时：Q.tail-Q.headMAXSIZE-(Q.head-Q.tail)MAXSIZE+Q.tail-Q.headMAXSI

12、ZE+Q.tail-Q.head(MAXSIZE+Q.tail-Q.head)%MAXSIZE(MAXSIZE+Q.tail-Q.head)%MAXSIZE五、应用：离散事件模拟问题：设某银行有四个窗口对外接待客户，每个窗口在一个时刻只能接待一个客户，客户较多时需排队。客户业务处理完毕后离开银行，与他同处一队的下一客户的业务得以处理。要求编程模拟银行的业务活动，计算一天内客户在银行逗留的平均时间。五、应用：离散事件模拟分析：一天内客户在银行逗留的平均时间从银行开门至关门时间内所有客户逗留时间之和客户数客户逗留时间客户离开时间客户到达时间五、应用：离散事件模拟分析：客户到达时间是随机的，不妨设第

13、一个客户的到达时间为 0 ，即银行开门时间，下一客户的到达时间为前一客户到达时间加一随机数。客户到达时间不能超过银行关门时间。客户到达后排入长度最短的队列。若该队为空，则客户离开时间客户到达时间客户业务处理时间，否则客户离开时间该队前一客户离开时间客户业务处理时间。其中客户业务处理时间亦为随机数。五、应用：离散事件模拟分析：待处理事件有两类，即客户到达事件和客户离开事件。对客户到达事件的处理为：累计客户数；产生下一客户到达事件；当前客户入长度最短的队；若该队原为空，则产生客户离开事件。对客户离开事件的处理为：从队列中删除当前客户；累计客户逗留时间；若该队非空，则产生下一客户离开事件。事件应按其

14、发生的先后次序得以处理。五、应用：离散事件模拟数据对象：Y客户信息数据项逻辑结构存储结构Y事件信息数据项逻辑结构存储结构客户到达时间、业务处理时间队列链队事件类型、事件发生时间线性表单链表（按事件发生时间有序）五、应用：离散事件模拟思路：银行开门：列、事件表，产生第一个客户到达事件；业务活动：银行关门：初始化客户数、客户逗留时间、4个客户队依次处理事件表中事件，直至事件表为空；求得一天内客户在银行逗留的平均时间。五、应用：离散事件模拟类型定义：typedef structint ArrivalTime;/客户到达时间int Duration;/业务处理时间Custom;/客户typedef C

15、ustom QElemType;五、应用：离散事件模拟类型定义：typedef struct QNodeQElemType data;struct QNode *next;QNode;typedef structQNode *head;QNode *tail;LinkQueue;/客户队列类型五、应用：离散事件模拟类型定义：typedef structint OccurTime;/事件发生时间int NType;/事件类型，0表示客户到达事件，/1,2,3,4分别表示队列1,2,3,4中队头客户离开事件Event;/事件typedef Event LElemType;五、应用：离散事件模拟类型

16、定义：typedef struct LNodeLElemType data;struct LNode *next;LNode,*EventList;/事件链表类型全局变量：int TotalTime,CustomerNum;/客户逗留时间、客户数五、应用：离散事件模拟算法：void Bank_Simulation( )/银行开门/初始化客户数、客户逗留时间CustomerNum=0;TotalTime=0;/初始化4个客户队列for(i=1;i=4;+i) InitQueue(qi);五、应用：离散事件模拟/初始化事件表InitList(ev);/产生第一个客户到达事件enen.OccurTi

17、me=0;/事件发生时间en.NType=0;/事件类型OrderInsert(ev,en);/将事件en按发生时间有序插入事件表ev五、应用：离散事件模拟/业务活动/依次处理事件表中事件，直至事件表为空；while(!ListEmpty(ev)/若事件表非空ListDelete(ev,1,en);/en为当前待处理事件if (en.NType=0) CustomerArrived( en );else CustomerDeparture( en );/while五、应用：离散事件模拟/银行关门printf(“The Average Time: %fn,TotalTime/CustomerNu

18、m);/Bank_Simulation五、应用：离散事件模拟客户到达事件处理算法：void CustomerArrived(LElemType en)/累计客户数+CustomerNum;/产生下一客户到达事件e，并按时间有序入事件表evRandom(intertime);/下一客户间隔多久后到达e.OccurTime=en.OccurTime+intertime;if (e.OccurTime0ji为数据元素第 i 维的下标，0jibi-1，bi是数组第 i 维的长度，即维界，一、抽象数据类型定义ADT Array一、抽象数据类型定义数据对象：D=aj1j2jn |其中：aj1j2jnEle

19、mSet，i=1,2,n，n为数组的维数，也即每个数据元素对应的下标的个数，n0ji为数据元素第 i 维的下标，0jibi-1，bi是数组第 i 维的长度，即维界，【例】二维数组，记： B=(1,2,3),(4,5,6)；或： B=(1,4),(2,5),(3,6)。654321数据关系：R=R1,R2,RnRi=，0jibi-2，0jkbk-1，1kn，kininijjjjjjaa.1.11,Daaninijjjjjj .1.11,|一、抽象数据类型定义设二维数组B=，则b1=2，b2=3，R=R1,R2。654321【例】关系R1有：0j1b1-2=0，0j2b2-1=2，即R1= , =

20、,关系R2有：0j1b1-1=1，0j2b2-2=1，即R2= ,=,一、抽象数据类型定义基本操作：InitArray(&A,n,bound1,boundn)操作结果：若给定的维数和各维长度值合法，则构造数组ADestroyArray(&A)操作结果：销毁数组A一、抽象数据类型定义Value(A,&e,index1,indexn)操作结果：若各给定下标值不越界，则由 e 返回相应元素值Assign(&A,e,index1,indexn)操作结果：若各给定下标值不越界，则将 e 值赋给指定元素/ADT Array一、抽象数据类型定义51324用一组地址连续的存储单

21、元依次存储数组中数据元素，存储时需考虑各维的主次问题。1、存储结构设计【例】设数组A=200820002004200220062 byte65432162010行主序二、顺序存储结构31245用一组地址连续的存储单元依次存储数组中数据元素，存储时需考虑各维的主次问题。1、存储结构设计【例】设数组A=200820002004200220062 byte65432162010列主序问题：如何按给定的下标，计算对应数组元素的存储地址。二、顺序存储结构设二维数组Ams以行序为主序存储，存储空间首地址为LOC(0,0)，每个数组元素占用L个存储单元，求LOC(i,j)。【例】0,00,j0,s-11,0

22、1,j1,s-1i,0i,ji,s-1m-1,0m-1,jm-1,s-10,00,s-11,01,s-1i,0i,ji,s-1.LOC(0,0)LOC(0,0)s s* *L L i行i i* *s s* *L Lj j* *L L设二维数组Ams以行序为主序存储，存储空间首地址为LOC(0,0)，每个数组元素占用L个存储单元。【例】0,00,s-11,01,s-1i,0i,ji,s-1.LOC(0,0)LOC(0,0)i i* *s s* *L Lj j* *L LLOC(i,j)=LOC(0,0)+i*s*L+j*L解：LOC(j1,j2)=LOC(0,0)+(j1*b2+j2)*L设三维

23、数组Amst以行序为主序存储，存储空间首地址为LOC(0,0,0)，每个数组元素占L个存储单元，求LOC(i,j,k)。【例】0,0,00,0,k0,0,t-10,1,00,1,k0,1,t-10,j,00,j,k0,j,t-10,s-1,00,s-1,k0,s-1,t-10,0,00,s-1,t-11,0,01,s-1,t-1i,0,0i,j,ki,s-1,t-1.LOC(0,0,0)LOC(0,0,0)s s* *t t* *L L i片i i* *s s* *t t* *L L(j(j* *t+k)t+k)* *L L【例】LOC(i,j,k)解：=LOC(0,0,0)+i*s*t*L+

24、j*t*L+k*L设三维数组Amst以行序为主序存储，存储空间首地址为LOC(0,0,0)，每个数组元素占L个存储单元，求LOC(i,j,k)。0,0,00,s-1,t-11,0,01,s-1,t-1i,0,0i,j,ki,s-1,t-1.LOC(0,0,0)LOC(0,0,0)LOC(j1,j2,j3)=LOC(0,0,0)+(j1*b2*b3+j2*b3+j3)*Li i* *s s* *t t* *L L(j(j* *t+k)t+k)* *L L设维数组Ab1b2bn，则：niiijc1*LOC(j1,j2,jn)j j1 1*b b2 2* * *b bn n* *L L+j j2 2

25、*b b3 3* * *b bn n* *L L+j jn-1n-1*b bn n* *L L+j jn n*L L其中，cn=L，ci-1=ci*bi，1in，称求址常量。LOC(0,0,0)+LOC(0,0,0)+二、顺序存储结构对n维数组，除需长为b1*b2*bn的连续空间存储数据元素外，还需记录数组的维数n和各维的维界bi，为提高存取效率，可将求址常量ci也保存下来，此时可令cn=1。二、顺序存储结构【例】设三维数组A=(1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16),(17,18,19,20),(21,22,23,24)按行序存放。1224

26、A.base234A.bounds1241A.constants3A.dim0123二、顺序存储结构#define MAX_ARRAY_DIM 8/定义最大维数typedef structElemType *base;/保存数组元素存储空间首地址int dim;/保存数组维数int *bounds;/指向保存各维维界的存储空间int *constants;/指向保存求址常量的存储空间Array;二、顺序存储结构编程时通常用二维数组保存矩阵，但有时会浪费空间。【例】A=B=【问题】对值相同的元素或零元素分布有规律的矩阵，如何存储才既能节省空间，又能保证矩阵运算的正常进行。587658230373

27、64760492537210004000803030006000209000三、矩阵的压缩存储F定义若n阶矩阵A有aij=aji i,j0,n-1，则称A为n阶对称阵。【例】A=58765823037364760492537211、对称阵F存储结构设计用一组地址连续的存储单元按行或列序保存其上/下三角（含对角线）中的数据元素，共n(n+1)/2个。【例】A=58765823037364760492537211、对称阵F存储结构设计【例】行主序：列主序：A=1297465127359558765823037364760492537211、对称阵F存储地址计算【问题】设以行序将对称矩阵的下三角元素

28、（含对角线）保存在一维数组san(n+1)/2中。若aij保存在sak中，则如何由i,j求k值？【分析】下三角中元素行下标列下标，因此若ij，则应求aji的存储位置；1、对称阵若ij，则aij在存储空间中的相对位置为k=i(i+1)/2+j。1, 11 , 101, 10, 1111000.nnniiijiiiiaaaaaaaaaa1、对称阵F定义若矩阵的上下三角（不含对角线）中元素为一常数，则称该矩阵为下上三角阵。【例】A=B=431962740322058222602222170000860009230060420837252、三角阵F存储结构设计用一组地址连续的存储单元按行或列序存储其上

29、下三角（含对角线）中数据元素，再加常数，共n(n+1)/2+1个。【例】A=43196274032205822260222212、三角阵F存储结构设计【例】行主序列主序A=106854106854210836410836422243196274032205822260222212、三角阵F定义若矩阵中除主对角线及其上下若干条对角线上的元素之外，其余元素均为0，则称对角阵。【例】A=43000132000975000386000213、对角阵F存储结构设计将矩阵中的非零元按某种次序（行序、对角线顺序等）存储于一组地址连续的存储单元。【例】A=43000132000975000386000213、

30、对角阵F存储结构设计【例】行主序对角线顺序A=268334239121343000132000975000386000213、对角阵F定义设在mn矩阵中，有t个数据元素不为零。当稀疏因子时，称该矩阵为稀疏矩阵。【例】A=05. 0nmt000700150000018000002400014000030000000000091204、稀疏阵F三元组表示法对稀疏矩阵进行压缩存储时，可只保存其中非零元，同时还需指明非零元所处的行列位置及总的行数、列数。【例】 A=000700150000018000002400014000030000000000091204、稀疏阵记：(1,2,12)，(1,3,9

31、)，(3,1,-3)，(3,6,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7)，(6,7,8)F存储结构设计顺序表存储结构用一组地址连续的存储单元按行序保存各三元组，另设变量保存稀疏矩阵的行数、列数和非零元数。4、稀疏阵【例】A=786A.tu-7461516182524341463-3139311221A.dataA.muA.nuije76543201000700150000018000002400014000030000000000091204、稀疏阵#define MAXSIZE 1000/非零元最大个数typedef structint i;/行下标in

32、t j;/列下标ElemType e;/非零元值Triple;/三元组类型4、稀疏阵typedef struct Triple dataMAXSIZE;/三元组表int mu;/行数int nu;/列数int tu;/非零元个数TSMatrix;4、稀疏阵F矩阵转置基于顺序表存储结构实现【定义】TransposeSMatrix(M,&T)操作结果：求稀疏矩阵M的转置矩阵T【原型】void TransposeSMatrix(TSMatrix M,TSMatrix &T);4、稀疏阵【经典算法】将mu行nu列的矩阵M转置为矩阵T的经典算法为：for(i=1;i=mu;+i)for(

33、j=1;j=nu;+j)Tji=Mij;算法的时间复杂度为O(mu*nu)。4、稀疏阵设稀疏矩阵M：则其转置矩阵T：00070015000001800000240001400003000000000009120000000000140000000070000000240090180001215003004、稀疏阵三元组表M：三元组表T：(1,2,12),(1,3,9),(3,1,-3)(1,3,-3),(1,6,15),(2,1,12)(3,6,14),(4,3,24),(5,2,18)(2,5,18),(3,1,9),(3,4,24)(6,1,15),(6,4,-7),(6,7,8)(4,6

34、,-7),(6,3,14),(7,6,8)4、稀疏阵【思路】交换矩阵行列数；交换每个三元组中的行列下标：重排三元组，使之按行序排列。Y重排方案一按T中三元组的次序依次在M中找到相应的三元组进行转置，即按M的列序进行转置。4、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tuT.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tuT.dataT.muT.nu765432017654

35、32014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tuT.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tuT.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-331T.dataT.muT.nu76543201765432014

36、、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-331T.dataT.muT.nu76543201765432

37、014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1561-331T.dataT.muT.nu765

38、43201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu12121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu121215

39、61-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu12121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu12121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221

40、M.dataM.muM.nu687T.tu12121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu12121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu

41、-7461516182524341463-3139311221M.dataM.muM.nu687T.tu185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu185212121561-331T.data

42、T.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M

43、.dataM.muM.nu687T.tu913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu913185212121561-331T.dataT.muT.nu765432017654320

44、14、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.n

45、u687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu765432017654320

46、14、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.n

47、u687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu765432017654320

48、14、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.n

49、u687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu765

50、43201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-313

51、9311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-

52、331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-746

53、1516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu-764

54、2443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu7654320

55、1765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463

56、-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443

57、913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765

58、432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-313

59、9311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【例】786M.tu-7461516182524341463-3139311221M.dataM.muM.nu687T.tu1436-7642443913185212121561-331T.dataT.muT.nu76543201765432014、稀疏阵【算法分析】此时对M中每一列的处理均需扫描整个三元组表，时间复杂度为O(nu*tu)，当tu与mu*nu等数量级时，时间复杂度达O(nu2*mu)，高于经典

60、算法的O(mu*nu)。4、稀疏阵Y重排方案二按M中三元组的次序进行转置，将转置所得三元组存放到T中恰当位置。此时需记录T中每一行（即M中每一列）的当前三元组应存放的位置。该位置初始时为每一行的第一个非零元所在位置，然后每放一个三元组就加1。4、稀疏阵【例】000000num0-7461516182524341463-3139311221M.data786M.tuM.muM.nuT.data687T.tuT.muT.nu76543201765432016543201注：num中保存M中各列(即T中各行)的非零元数4、稀疏阵【例】000000num0-7461516182524341463-3139311221M.data786M.tuM.muM.nu7654