数据结构-第二章线性表

第二章

线性表

[内容提要]

1、线性表的定义、逻辑结构特点及基本运算2、线性表的顺序存储结构及基本运算3、线性表的链式存储结构及基本运算4、数组的逻辑结构定义及其存储方式5、线性表的应用示例数据结构--第二章线性表全文共96页，当前为第1页。2线性表：n(n≥0)个具有相同特性的数据元素的有限序列。其中：n表示线性表的长度，即数据元素的个数。n=0时表为空表。n>0时表通常记为:线性表的定义数据结构--第二章线性表全文共96页，当前为第2页。3线性表的特点当1<i<n时ai的直接前驱是ai-1

，

a1无直接前驱ai的直接后继是ai+1

，an无直接后继元素同构，且不能出现缺项数据结构--第二章线性表全文共96页，当前为第3页。4线性表的特点在线性表中的元素之间存在一对一的关系。所以，线性表的逻辑结构是线性结构。数据结构--第二章线性表全文共96页，当前为第4页。5线性表的元素的含义每个数据元素的具体含义，在不同线性表中各不相同，它可以是一个数、或一个符号，也可以是一个记录，甚至是其它更复杂的信息。数据结构--第二章线性表全文共96页，当前为第5页。6线性表的元素的含义（续）

如右图所示的学生成绩表也是一个线性表，其中数据元素是每一个学生所对应的一行信息，即包括学号、姓名、成绩共三个数据项。数据元素数据结构--第二章线性表全文共96页，当前为第6页。7线性表上常用的的运算⑴初始化线性表⑵判空线性表的长度，⑷读取表是否为空⑶求线性表中第i个元素⑸查找满足给定条件的数据元素⑹在线性表的第i个位置之前插入一个新的数据元素数据结构--第二章线性表全文共96页，当前为第7页。8⑺删除线性表中的第i个数据元素⑻表置空⑼查找表中第i个元素的前驱⑽查找表中第i个元素的后继⑾按一个或多个数据项值的递增或递减次序重新排列线性表中的数据元素线性表上常用的运算（续）数据结构--第二章线性表全文共96页，当前为第8页。9

利用以上的基本运算可以实现线性表的其他运算。如将两个线性表合并成一个线性表或将一个线性表拆分成多个线性表等运算，在实际应用中，可根据不同的要求选择适当的基本运算解决具体问题。线性表上常用的运算（续）数据结构--第二章线性表全文共96页，当前为第9页。10

在内存中开辟一片连续的存储空间，用一组连续的存储单元依次存放线性表的数据元素，这种存储方式叫做线性表的顺序存储结构，简称顺序表。线性表的顺序存储结构数据结构--第二章线性表全文共96页，当前为第10页。11

在逻辑上相邻的数据元素，它们的物理位置也是邻接的。即线性关系利用物理上的相邻关系来体现。顺序存储结构的特点数据结构--第二章线性表全文共96页，当前为第11页。12

线性表中第i个数据元素的存储位置是：

LOC(ai)=LOC(a1)+(i-1)*m其中，m表示每个元素占用的存储单元个数线性表的顺序存储结构是一种随机存取的存储结构（可以随机存取顺序表中任意一个元素）。顺序存储结构的特点(续)数据结构--第二章线性表全文共96页，当前为第12页。13

#defineMaxsizemaxlen;/*maxlen表示线性表可能的最大数据元素数目*/typedefintelemtype;/*elemtype表示数据元素类型，此处定义为int*/

typedefstruct

{elemtypev[Maxsize];

/*存放线性表元素的数组，关系隐含*/

intlen;

/*表示线性表的长度*/

}sqlist;/*sqlist是数据类型，此处表示线性表的顺序存储结构*/顺序表的类型定义数据结构--第二章线性表全文共96页，当前为第13页。14a1a2an01n-112n内存V数组下标元素序号Maxsize-1例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);顺序表的图示数据结构--第二章线性表全文共96页，当前为第14页。15若有下列变量定义：

sqlist*L；则：L表示指向sqlist顺序表类型的指针变量线性表的表长应表示为(*L).len或L->len第i个元素写为(*L).v[i-1]或（L->v）[i-1]

顺序表使用注意事项数据结构--第二章线性表全文共96页，当前为第15页。16顺序存储结构的优点1．随机存取元素容易实现，根据定位公式容易确定表中每个元素的存储位置，所以要指定第i个结点很方便。2．简单、直观数据结构--第二章线性表全文共96页，当前为第16页。171．插入和删除结点困难由于表中的结点是依次连续存放的，所以插入和删除一个结点时，必须将插入点和删除点以后的结点向后或向前依次移动。2．扩展不灵活建立表时，若估计不到表的最大长度，就难以确定分配的空间，影响扩展。3．容易造成浪费分配的空间过大时，会造成预留空间浪费。顺序存储结构的缺点数据结构--第二章线性表全文共96页，当前为第17页。18顺序表上的基本运算一.求线性表的长度（算法2.1）

intlenth(sqlist*L){intlenth;lenth=(*L).len；return(lenth);/*返回线性表的长度*/}

数据结构--第二章线性表全文共96页，当前为第18页。19二、插入算法

线性表的插入运算是指在线性表的第i个数据元素之前插入一个新的数据元素，使长度为n的线性表

(a1,…,ai-1,ai,…,an)

变为长度为n＋1的线性表

(a1,…,ai-1,x,ai,…,an)

顺序表上的基本运算数据结构--第二章线性表全文共96页，当前为第19页。20顺序表上的插入运算数据结构--第二章线性表全文共96页，当前为第20页。21内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x数据结构--第二章线性表全文共96页，当前为第21页。22(1)判断线性表的存储空间是否已满，若已满，则进行“溢出”处理。(2)检查i值是否超出所允许的范围（1≤i≤n+1），若超出，则进行“超出”处理。(3)将线性表的第i个元素和它后面的所有元素均后移一个位置。(4)将新的数据元素写入到空出的下标为i-1的位置上。(5)线性表的长度增加1顺序表的插入算法数据结构--第二章线性表全文共96页，当前为第22页。23Voidinsert(sqlistl,inti,elemtypex){if(l.len==maxsize)error(“表满”);if(i<1||i>l.len)error(“i错误!”);for(j=l.len-1;j>=i-1;j--)L.v[j+1]=l.v[j];l.v[i-1]=x;L.len++;}O(n)数据结构--第二章线性表全文共96页，当前为第23页。24插入算法的算法时间复杂度假设在第i个元素之前插入一个元素的概率为Pi，所需移动数据元素的平均次数为：数据结构--第二章线性表全文共96页，当前为第24页。25插入算法主要执行时间都在移动数据元素的循环上，该语句循环执行的次数为n-i+1

当i=n+1时，移动次数为0；当i=1时,移动次数为n，该算法在最坏情况下时间复杂度为O(n)

在最好情况下时间复杂度为O(1)。

插入算法的算法时间复杂度（续）数据结构--第二章线性表全文共96页，当前为第25页。26插入算法的实现:Voidinsert(sqlistL,inti,elemtypex){if(l.len==Maxsize)error(“表满”);if(i<1||i>l.len)error(“i错误!”);for(j=l.len-1;j<=i-1;j--)L.v[j+1]=l.v[j];L.v[i-1]=x;L.len++;}O(n)数据结构--第二章线性表全文共96页，当前为第26页。27三．删除操作的实现 线性表的删除运算是指将线性表的第i个数据元素删去，使长度为n的线性表

(a1,...,ai-1,ai,ai+1,...,an)变成长度为n-1的线性表

(a1,...,ai-1,ai+1,...,an)顺序表上的基本运算数据结构--第二章线性表全文共96页，当前为第27页。28顺序表上的删除运算数据结构--第二章线性表全文共96页，当前为第28页。29内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2数据结构--第二章线性表全文共96页，当前为第29页。30算法思路：(1)判断i值是否超出所允许的范围(1≤i≤n），若是，则进行“超出范围”处理；(2)把第I个元素赋给y;(3)把第i个元素后的所有元素依次向前移动一个位置；(4)线性表长度减1。顺序表的删除算法数据结构--第二章线性表全文共96页，当前为第30页。31删除算法的算法时间复杂度假设删除第i个元素的概率为qi，所需移动数据元素的平均次数为：数据结构--第二章线性表全文共96页，当前为第31页。32删除算法主要执行时间都在移动数据元素的循环上，该语句循环执行的次数为n-i

当i=1时，移动n-1个，当i=n时，不需移动，该算法在最坏情况下时间复杂度为O(n)

在最好情况下时间复杂度为O(1)。删除算法的算法时间复杂度（续）数据结构--第二章线性表全文共96页，当前为第32页。33删除算法的实现voiddelete(sqlistl,inti){if(i<1||i>l.len)error(“错误!”);for(j=i;j<=l.len-1;j++)L.v[j-1]=l.v[j];L.len--;}O(n)数据结构--第二章线性表全文共96页，当前为第33页。34四．查找 线性表的查找是指找出数据元素x在表中的位序号，若v[i]==x,则算法返回值为i+1，若不存在数据元素x则返回0顺序表上的基本运算数据结构--第二章线性表全文共96页，当前为第34页。线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），数据元素之间的逻辑关系借助指示元素存储位置的指针来表示，这种存储方式叫做线性表的链式存储结构，简称链表。数据结构--第二章线性表全文共96页，当前为第35页。36ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针数据结构--第二章线性表全文共96页，当前为第36页。37用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置链式存储结构的特点数据域指针域数据结构--第二章线性表全文共96页，当前为第37页。单链表链表中，每个结点只包含一个指针域，则称此链表为线性链表或单链表。数据结构--第二章线性表全文共96页，当前为第38页。39

有时为了操作方便，在单链表的第一个结点之前添加一个结点，称头结点或伪结点，头结点的数据域可以不存放任何信息，也可以存放其他特殊信息，头结点的指针域存放第一个元素结点的存储地址，即指向第一个结点的指针值。此时，单链表的头指针指向头结点，称其为带头结点的单链表。带头结点的单链表数据结构--第二章线性表全文共96页，当前为第39页。40typedefstructnode{elemtypedata;structnode*next;}Lnode,*linklist;/*Lnode为结点类型，linklist为指向结点的指针类型*/单链表的类型定义数据结构--第二章线性表全文共96页，当前为第40页。41若:LNode*h,*p;或linklisth,p;//p,h为变量p=(LNode*)malloc(sizeof(Lnode));//P有操作对象此时,P和对象之间的关系:datanextp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).nextp->next表示p指向结点的指针域单链表的使用注意事项数据结构--第二章线性表全文共96页，当前为第41页。421、建立单链表（头插法）单链表的基本运算h头结点an^0han-10an^a2…...han-10an^ha1a2an^…...0h0^数据结构--第二章线性表全文共96页，当前为第42页。43算法思路：1)首先建立一个头结点，并使头结点的指针域为空；2)读入值ch；3)建立一个新结点p；4)将ch赋给p的数据域；5)改变指针p的值，使p成为h的直接后继；6)重复（2）到（5），直到不满足循环条件为止。头插法建立单链表算法数据结构--第二章线性表全文共96页，当前为第43页。44Linklistcreate(){head=(lnode*)malloc(sizeof(lnode));Head->next=NULL;for(i=0;i<5;i++){p==(lnode*)malloc(sizeof(lnode));输入一个结点值;p->next=head->next;Head->next=p;}Retunhead;}数据结构--第二章线性表全文共96页，当前为第44页。45Linklistcreate(){head=(lnode*)malloc(sizeof(lnode));head->next=NULL;p=NULL;for(i=0;i<5;i++){q=(lnode*)malloc(sizeof(lnode));q->next=p;输入节点值;head->next=q;p=q;}returnhead;}数据结构--第二章线性表全文共96页，当前为第45页。46typedefcharelemtype;Lnode*creat()/*表尾插入法，建立单链表*/{lnode*h,*p，*t;elemtypex;h=(lnode*)mallod(sizeof(lnode));h->next=NULL;t=h;while(ch=getchar())!=’\n’){p=(lnode*)mallod(sizeof(lnode));p->data=ch;p->next=NULL;t->next=p;t=p;/*t始终指向最后一个元素*/}return(h);}尾插法建立单链表算法数据结构--第二章线性表全文共96页，当前为第46页。47

算法思路：

1）设置一个工作指针变量p，再设置一个整型变量i作计数器; 2）让p指向第一个结点，置i为0; 3）指针p在单链表中后移并且i值加1; 4）当p=NULL时说明单链表结束，计数完毕，这时i的值正好是表长。求单链表的长度的算法数据结构--第二章线性表全文共96页，当前为第47页。48Intlength(linklisth){i=0;p=h;While(p->next!=NULL){i++;p=p->next;}Returni;}数据结构--第二章线性表全文共96页，当前为第48页。49

在单链表中p结点之后插入值为x的新结点s插入算法1①s->next=p->next;②p->next=s;数据结构--第二章线性表全文共96页，当前为第49页。50算法思路：(1)生成一个新结点s；(2)将x赋给将新结s的数据域；(3)新结点链入单链表中；插入算法1（续）数据结构--第二章线性表全文共96页，当前为第50页。51在单链表中第i个元素之前插入一个元素x该如何实现。1、定位：使p指向第i-1号结点2、新产生一个结点，存放元素x3、插入：在p之后插入s所指向的新结点插入算法２数据结构--第二章线性表全文共96页，当前为第51页。52删除单链表中p的后继结点q删除算法

pabcq=p->next;p->next=q->next;数据结构--第二章线性表全文共96页，当前为第52页。53

算法思路：

1）将q指向p结点的直接后继；

2）改变指针链接，把q结点的直接后继作为p结点的直接后继；

3）从单链表中删除q结点；

4）释放q结点空间。删除算法(续)

数据结构--第二章线性表全文共96页，当前为第53页。54

查找单链表中是否存在数据域为x的结点。若有该结点，则返回指向该结点的指针，否则返回空。 算法思路：

1）从第一个结点开始扫描整个单链表，逐个比较数据域值和x；

2）找到该结点后返回指向该结点的指针。按值查找算法数据结构--第二章线性表全文共96页，当前为第54页。55Linklistget(linklisthead,elemtypex){p=head->next;While(p->data!=x&&p!=null)p=p->next;If(p->data==x)returnp;ElsereturnNULL;}数据结构--第二章线性表全文共96页，当前为第55页。56lnode*get(linklisth,elemtypex){p=h->next;While(p->data!=x&&p->next!=NULL)p=p->next;If(p>data==x)returnp;ElsereturnNULL;}数据结构--第二章线性表全文共96页，当前为第56页。57ha1a2an^…...pj=1pj=2

读取单链表中的第i个元素。如果找到，则返回第i个结点的存储地址，否则返回空。

算法思路：1）p从单链表的第一个结点出发，并定义j=1；2）在单链表中移动指针p，同时累计j;3）通过j的累计查找j=i的结点；4）重复2）、3）直到p为空或p指向第i个元素。读取元素算法数据结构--第二章线性表全文共96页，当前为第57页。58它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢单链表特点数据结构--第二章线性表全文共96页，当前为第58页。59循环链表循环链表是指在单链表中最后一个结点的链域值不是NULL，而是指向头结点，整个表形成一环。特点:是从表中任意结点出发均可以找到表中其它的结点.操作与单链表基本一致,循环条件不同单链表p或p->next=NULL循环链表p或p->next=H数据结构--第二章线性表全文共96页，当前为第59页。60循环链表按值查找算法Lnode*get(Lnode*h,elemtypex){Lnode*p;p=h->next;while(p!=h&&x!=p->data)/*循环扫描查找，直到p指向头结点h或找到x结束*/p=p->next;return(P);}数据结构--第二章线性表全文共96页，当前为第60页。61双向链表每一个结点中有两个指针域，其一指向直接后继，另一指向直接前趋的链表叫双向链表。双向链表的结点描述为：typedefstructdulnode{elemtypedata;structdulnode*next,*prior;}dulnode;priorelementnext数据结构--第二章线性表全文共96页，当前为第61页。62L空双向循环链表：双向链表(续)非空双向循环链表：LABbcap具有恒等关系:p->prior->nextpp->next->proir;数据结构--第二章线性表全文共96页，当前为第62页。63在双向循环链表结点p之前插入结点s双向循环链表的插入算法1数据结构--第二章线性表全文共96页，当前为第63页。64

可见，改变指针链接的语句有： ①s->prior=p->prior; ②p->prior->next=s; ③s->next=p; ④p->prior=s;数据结构--第二章线性表全文共96页，当前为第64页。65

含义:在双向环形链表的第i个结点之前插入值为x的新结点。如果成功，返回1，否则，返回0。

算法思路：

1）通过p的移动在双向链表中依次查找第i个元素；

2）如果找到，则建立一个新结点s; 3）将s和p以及p的前驱链接起来，即使s的前驱是p原来的前驱，s和后继是p；双向循环链表的插入算法2数据结构--第二章线性表全文共96页，当前为第65页。66删除双向环形链表的结点p

双向循环链表的删除算法1改变指针链接的语句有：

p->prior->next=p->next;p->next->prior=p->prior;数据结构--第二章线性表全文共96页，当前为第66页。67含义:删除双向环形链表的第i个结点p。如果成功，返回1，否则，返回0。算法思路：

1）通过p的移动在双向链表中依次查找第i个元素；

2）如果找到，改变指针链接，即使p的前驱指向p的后继，p的后继结点的前驱指针指向p原来的前驱；

3）释放p；

双向循环链表的删除算法2数据结构--第二章线性表全文共96页，当前为第67页。68线性表的顺序存储和链式存储在操作上的比较：顺序存储链式存储循环控制变量下标变量i指针变量P初始化i=0；P=head;或：P=head->next;处理对象a[i]*p下一对象i++;P=p->next;循环条件i<n(长度)P!=NULL数据结构--第二章线性表全文共96页，当前为第68页。69本节学习要点1.了解顺序表、链表的概念、含义、区别。2.熟练掌握这两类存储结构的描述方法。3.熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4.熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。5.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。数据结构--第二章线性表全文共96页，当前为第69页。70第2章复习1.带头结点的单链表head为空的条件是_head->next=null__2.单链表中,q是p的前趋结点,在p和q之间插入一个结点s,应选择____操作A.s->next=p->next;p->next=sB.q->next=s;s->next=p;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;数据结构--第二章线性表全文共96页，当前为第70页。713.下面的算法判断带头结点的循环双链表是否对称,填空__intdlink(dlinklisth){j=1;p=h->next;q=h->prior;while(p!=q&&(p->prior!=q||q->next!=p)){{if(p->data==q->data){p=p->next;q=q>prior;}Elsej=0;}Returnj;}数据结构--第二章线性表全文共96页，当前为第71页。724.编写算法删除按值递增有序排列的顺序表中多余的值相同的元素Voiddelete(sqlistL){i=0;While(i<=l.len-1){if(l.v[i]!=l.v[i+1]i++;else{for(j=i+2;j<=l.len-1;j++)L.v[j-1]=L.v[j];L.len--;}}数据结构--第二章线性表全文共96页，当前为第72页。735.编写算法实现将两个递增单链表合并为一个递增的单链表的运算linklistlink(linklistA,linklistB){C=(linklist)malloc(sizeof(lnode));C->next=null;r=c;While(a->next!=null&&b->next!=null){p=a->next;q=b->next;If(p->data<q->data){a->next=p->next;r->next=p;r=p;}Else{b->next=q->next;r->next=q;r=q;}If(a->next!=null)r->next=a->next;Elser->next=b->next;ReturnC;}数据结构--第二章线性表全文共96页，当前为第73页。746.设有一个不带头结点循环单链表head,设计算法实现结点指针域指向其直接前趋的操作.Voidinvert(linklisthead){p=head;q=head->next;r=q->next;While(r!=head){q->next=p;p=q;q=r;r=r->next;}q->next=p;r->next=q;}数据结构--第二章线性表全文共96页，当前为第74页。757.设有一循环双链表,初始化时每个结点的前趋域prior是空的,编写算法,使每个结点的前趋域指向其前趋.数据结构--第二章线性表全文共96页，当前为第75页。数组

在数据结构中，数组是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。数据结构--第二章线性表全文共96页，当前为第76页。77数组的定义

数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。数据结构--第二章线性表全文共96页，当前为第77页。78()()()()()()()()()二维数组数组A可以看成一个线性表：

A=(α0，α1，...，αk)（k=m-1或n-1）其中每一个数据元素αi是由第i行元素组成的一维数组，即一个行向量的线性表。αi=(ai0，ai1，...，ai,n-1)0≤i≤m-1或αj是由第j列元素组成的一维数组，即一个列向量的线性表。数据结构--第二章线性表全文共96页，当前为第78页。79数组的特点及运算数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值数组一般不做插入或删除操作数据结构--第二章线性表全文共96页，当前为第79页。80次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n数组的顺序存储结构

按列序为主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

数据结构--第二章线性表全文共96页，当前为第80页。81矩阵的压缩存储方法

压缩存储是指为多个值相同的元素只分配一个存储空间；对零元素不分配空间。数据结构--第二章线性表全文共96页，当前为第81页。82

a11

a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对称矩阵的压缩存储方法数据结构--第二章线性表全文共96页，当前为第82页。83

a11

00

……..0

a21

a22

0

……..0

an1

an2

an3……..ann

….

0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：三角矩阵的压缩存储方法数据结构--第二章线性表全文共96页，当前为第83页。84

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)+3*(i-1)-1+j-i+1=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角矩阵的压缩存储方法数据结构--第二章线性表全文共96页，当前为第84页。85M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩阵维数（6,7）唯一确定定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵数据结构--第二章线性表全文共96页，当前为第85页。86三元组表所需存储单元个数为3(t+1)其中t为非零元个数6

7

8

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值稀疏矩阵的三元组

表示法#defineMAX10typedefstruct{inti,j;elemtypev;}node;

typedefstruct{intmu,nu,tu;nodedata[MAX];}mat;mu,nu,tu分别存放矩阵行列维数和非零元个数数据结构--第二章线性表全文共96页，当前为第86页。87

算法思路：⑴将两个矩阵的行数和列数相互交换；⑵将每个三元组中的i和j相互调换；⑶重排三元组之间的次序便可实现矩阵的转置，即使b.data中的三元组以B的行（即A的列）为主序依次排列。稀疏矩阵的转置运算数据结构--第二章线性表全文共96页，当前为第87页。88

算法实现思想（算法2.16）：按照矩阵A的列序来进行转置运算。也就是首先寻找a.data中的第１列的所有