第二章-线性表-数据结构-教学课件.ppt

《第二章-线性表-数据结构-教学课件.ppt》由会员分享，可在线阅读，更多相关《第二章-线性表-数据结构-教学课件.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 线性表学习目的要求学习目的要求:1.线性表的定义和线性表的特征。线性表的定义和线性表的特征。2.线性表的顺序存储结构及其算法的实现。线性表的顺序存储结构及其算法的实现。3.线性链表的描述及其算法的实现。线性链表的描述及其算法的实现。4.循环链表和双向循环链表的描述。循环链表和双向循环链表的描述。5.数组的顺序存储和矩阵的压缩存储的描述。数组的顺序存储和矩阵的压缩存储的描述。2.1 线性表的基本概念2.2 线性表的顺序存储结构及其算法2.3 线性表的链式存储结构及其运算2.4 算法应用举例2.5 数组第2章 线性表第2章 线性表线性结构线性结构是一个数据的是一个数据的有序（次序）有序（次

2、序）集合集合【线性结构的【线性结构的基本特征基本特征】：】：集合中一定存在唯一的一个集合中一定存在唯一的一个“第一元素第一元素”集合中一定存在唯一的一个集合中一定存在唯一的一个“最后元素最后元素”除最后一个元素外，均有除最后一个元素外，均有“唯一后继唯一后继”除第一个元素外，均有除第一个元素外，均有“唯一前驱唯一前驱”2.1 线性表的基本概念 2.1.1 线性表的定义线性表的定义 线性表线性表（linear list）是由）是由 n个数据元素组成的个数据元素组成的有有限序列限序列,数据元素之间是一对一的关系，即数据元素之间是一对一的关系，即线性关系线性关系.线性表的二元组可以表示线性表的二元组

3、可以表示:S=（D，R）D=a1，a2，ai，an R=,称称i为线性表的位序为线性表的位序,称称n为线性表的为线性表的表长表长,n0时的线性表为时的线性表为空表空表【引用型操作】【引用型操作】1.ListEmpty（List）2.ListLength（List）3.GetElement（List，i）4.PriorElement（List，x）5.NextElement（List，x）6.LocateElement（List，x）2.1 线性表的基本概念线性表的基本概念2.1.2 线性表的基本操作线性表的基本操作【加工型操作】【加工型操作】1.ListInsert（List，i，x）2.Li

4、stDelete（List，i）2.1 线性表的基本概念线性表的基本概念2.1.2 线性表的基本操作线性表的基本操作2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法线性表的线性表的顺序存储结构顺序存储结构简称为简称为顺序表顺序表(Sequential List)在线性表中在线性表中逻辑关系相邻逻辑关系相邻的数据元素，在计算机的的数据元素，在计算机的内存中内存中物理位置也是相邻物理位置也是相邻的。的。2.2.1 线性表的顺序存储结构线性表的顺序存储结构【顺序存储结构的特点】【顺序存储结构的特点】a1a2.aian线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址

5、2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法 顺序结构的顺序结构的c语言描述：语言描述：#define MAXLEN 100typedef int elementtype;typedef struct elementtype sMAXLEN;/*线性表的最大容量线性表的最大容量*/int len;/*线性表当前的长度线性表当前的长度*/Sqlist;1.插入运算插入运算InsertsqList（i，x，&List）的实现的实现:2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法2.2.2 顺序表的运算顺序表的运算问：插入元素时，线性表的逻辑结问：插入元素时，线

6、性表的逻辑结构发生什么变化？构发生什么变化？int insertsqlist(int i,elementtype x,SqList*sql)/*在顺序表(*sql)的第i个元素之前插入一个新元素x*/int j;if(isql-len)/*i值非法，返回值为0*/return(0);else for(j=sql-len;j=i;j-)sql-sj+1=sql-sj;sql-sj+1=x;/*修正插入位置为j+1*/(sql-len)+;/*表长加1*/return(1);/*插入成功，返回值为1*/2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法判断插入得位置是否合判断插入得位

7、置是否合法，位置得合法取值是法，位置得合法取值是1sql-len/*向后移动数向后移动数据，腾出要插据，腾出要插入的空位入的空位*/【算法】【算法】2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法2.2.2 顺序表的运算顺序表的运算问：删除元素时，线性表的逻辑结构发生什么变化？问：删除元素时，线性表的逻辑结构发生什么变化？(a1,a2,ai-1,ai,ai+1an)改变为 (a1,a2,ai-1,ai+1,an)a1a2.ai-1aiai+1ana1a2.ai-1ai+1an删除后删除后删除元素平均次数为（n-1)/2int delsqlist(int i,SqList*sql

8、)/*删除顺序表(*sql)的第i个元素*/int j;if(i sql-len)/*i值非法，返回值为0*/return(0);else for(j=i+1;jlen;j+)sql-sj-1=sql-sj;(sql-len)-;/*表长度减1*/return(1);/*删除成功，返回值为1*/2.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法【算法】【算法】/*向前移动数据，向前移动数据，覆盖前一数据覆盖前一数据*/a1a3 a2以线性表中第一个数据元素以线性表中第一个数据元素a1的存储地址的存储地址作为线性表的地址，称作线性表的作为线性表的地址，称作线性表的头指针头指针加上表

9、头指针的线性表逻辑结构如下图所示：加上表头指针的线性表逻辑结构如下图所示：当链表为空时，则表头指针为空。如图（当链表为空时，则表头指针为空。如图（b）所示。）所示。线性表的每个结点都有一个链接指针，所以不要求链表中的结点必须按照结点先后次序存储在一个地址连续的存储区中。在链式存储结构中，线性表中数据元素的逻辑关系是用指示元素存储位置的指针来表示的。下图是线性表（a1 1，a2 2，a3 3，a4 4，a5 5）的链式存储结构。为了便于实现各种运算，通常在链表的第一个结点之前设置一个附加结点，称之为表头结点。而其他结点称为表中结点。表头结点结构与表中结点结构相同，只是数据域不存放数据元素，如图2

10、.8（a）所示。图2.8（b）为带头结点的空表的情况。图图图图2.8 2.8 带表头结点的线性链表带表头结点的线性链表带表头结点的线性链表带表头结点的线性链表a1a3 a2 因此，存放数据元素的空间（称为结点）至少包括因此，存放数据元素的空间（称为结点）至少包括两个域，一个域存放该元素的值，称为数据域两个域，一个域存放该元素的值，称为数据域;另一个域另一个域存放后继结点的存储地址，称为指针域或链域。其结点存放后继结点的存储地址，称为指针域或链域。其结点结构如图所示。结构如图所示。typedef struct node int data;/*数据域数据域*/struct node*next;/*

11、指针域指针域*/NODE;/*这里以整型为例，这里以整型为例，实际上可以为任意实际上可以为任意类型数据类型数据*/*指针类型，存放指针类型，存放下一个结点的地址下一个结点的地址*/*用用NODE来替代来替代struct node型的结构类型名，以后可以用型的结构类型名，以后可以用NODE来定义来定义 struct node型的结构变量型的结构变量*/线性链表是通过结点指针域中的指针表示各结点之间的线性关系的。线性表的每个结点都有一个链接指针，所以不要求链表中的结点必须按照结点先后次序存储在一个地址连续的存储区中。在链表中插入或删除数据元素比在顺序表中要容易得多，但是链表结构需要的存储空间较大。

12、2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算【特点】【特点】1.建立带表头结点的单链表建立带表头结点的单链表建立链表时，首先要建立表头结点，此时为空链表。建立链表时，首先要建立表头结点，此时为空链表。然后将新的结点逐一插入到链表中，其过程如下然后将新的结点逐一插入到链表中，其过程如下:（1）申请存储单元，用申请存储单元，用C语言的动态分配库函数语言的动态分配库函数malloc得到。得到。malloc（sizeof（NODE）函数）函数（2）读入新结点的数据，新结点的指针域为空。读入新结点的数据，新结点的指针域为空。（3）把新结点链接到链表上去（有前插和后插两种把新结点链接到

13、链表上去（有前插和后插两种方式）。方式）。重复以上步骤，直到将所有结点都链接到链表上为止。重复以上步骤，直到将所有结点都链接到链表上为止。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.2 单链表的运算单链表的运算NODE*create()/*此函数采用后插入方式建立单链表*/NODE*head,*q,*p;/*定义指针变量*/char ch;int a;head=(NODE*)malloc(sizeof(NODE);/*申请新的存储空间，建立表头结点*/q=head;ch=*;printf(nInput the list:);2.3 线性表的链式存储结构及其运算线性表

14、的链式存储结构及其运算(Continue)【算法【算法1】while(ch!=?)/*ch为是否建立新结点的标志，若ch为?则输入结束*/scanf(%d,&a);/*输入新元素*/p=(NODE*)malloc(sizeof(NODE);p-data=a;q-next=p;q=p;ch=getchar();/*读入输入与否的标志*/q-next=NULL;return(head);/*返回表头指针head*/2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算 while(n0)scanf(%d,&a);/*输入新元素*/p=(NODE*)malloc(sizeof(NODE);

15、p-data=a;q-next=p;q=p;n-;/*读入输入与否的标志*/q-next=NULL;return(head);/*返回表头指针head*/2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.单链表中结点的查找单链表中结点的查找单链表有两种查找方法，即按单链表有两种查找方法，即按序号查找序号查找和和按按给定值查找给定值查找。在单链表中，即使知道了要查找的结点的在单链表中，即使知道了要查找的结点的序号，也只能从序号，也只能从头指针头指针开始查找。与顺序表不开始查找。与顺序表不一样，单链表一样，单链表不能实现随机查找不能实现随机查找。2.3 线性表的链式存储结构及其运

16、算线性表的链式存储结构及其运算NODE*locate(NODE*head,int x)/*在已知链表中查找给定的值在已知链表中查找给定的值x*/NODE*p;p=head-next;while(p!=NULL)&(p-data!=x)p=p-next;/*指向下一个元素指向下一个元素*/return(p);（1）按值查找按值查找 2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算/*未到表尾且未未到表尾且未找到给定数据则找到给定数据则p指向下一个元素指向下一个元素*/【算法】【算法】（2）按序号查找按序号查找2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算在单链表

17、中查找第 i 个位置上的结点，若找到，则返回它的地址，否则返回NULL。2.单链表中结点的查找单链表中结点的查找 线性表的操作：线性表的操作：GetElement（List，i）在链表中的实现：在链表中的实现：基本操作为基本操作为：使指针使指针p始终指向线性表中第始终指向线性表中第j个数据元素个数据元素(指针指针p,计数器计数器j)NODE*find(NODE*head,int i)/*在已知链表中查找给定的值在已知链表中查找给定的值x*/int j=1;NODE*p;p=head-next;/*初始化，初始化，p指向第一个结点，指向第一个结点，j为计数器为计数器*/while(p!=NULL

18、)&(jnext;/*指向下一个元素指向下一个元素*/j+;/*计数器计数器j加加1*/return(p);（2）按序号查找按序号查找2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算/*未到表尾且未找未到表尾且未找到给定数据则到给定数据则p指指向下一个元素向下一个元素*/【算法】【算法】3.单链表上的插入运算单链表上的插入运算在顺序表中，插入运算时，将会有大量元素向在顺序表中，插入运算时，将会有大量元素向后移动。而在单链表中，后移动。而在单链表中，插入一个结点不需要移动插入一个结点不需要移动元素，只需要修改指针即可元素，只需要修改指针即可。2.3 线性表的链式存储结构及其运算

19、线性表的操作：线性表的操作：InsertsqList（i，x，&List）在链表中的实现：在链表中的实现：基本操作为基本操作为：找到线性表中的第找到线性表中的第i1个结点，个结点，修改其指向后继的指针修改其指向后继的指针有序对有序对改变为改变为若将x插入到a1 和a2 之间，其过程如下:（1）建立一个新结点 q，将x值赋给q-data。（2）修改有关结点的指针域。3.单链表上的插入运算单链表上的插入运算2.3 线性表的链式存储结构及其运算p-next=q;q-data=x;q-next=p-next;void insert(NODE*p,int x)/*在链表的在链表的p结点后插入给定元素结点

20、后插入给定元素x*/NODE*q;q=(NODE*)malloc(sizeof(NODE);/*申请新的存储空间申请新的存储空间*/q-data=x;q-next=p-next;/*实现图的实现图的*/p-next=q;/*实现图的实现图的，将新结点，将新结点q链接到链接到p结点之后结点之后*/2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算3.单链表上的插入运算单链表上的插入运算【算法】【算法】4.单链表上的删除运算单链表上的删除运算2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算 线性表的操作线性表的操作:DeletesqList（x，&List）在链表上的

21、实现在链表上的实现基本操作基本操作：找到线性表中的找到线性表中的x元素，修改其指向后继的指针。元素，修改其指向后继的指针。假设元素假设元素x的位置是的位置是i则有序对则有序对改变为改变为4.单链表上的删除运算单链表上的删除运算 删除单向链表中的结点删除单向链表中的结点x，并由系统收回其占用，并由系统收回其占用的存储空间，其过程如下的存储空间，其过程如下:（1）设定两个指针设定两个指针p和和q，p指针指向被删除结点指针指向被删除结点，q为跟踪指针，为跟踪指针，指向被删除结点的直接前驱结点指向被删除结点的直接前驱结点。（2）p从表头指针从表头指针 head 指向的第一个结点开始依次指向的第一个结点

22、开始依次向后搜索。当向后搜索。当p data 等于等于x时，被删除结点找到。时，被删除结点找到。（3）修改）修改p的前驱结点的前驱结点q的指针域。使的指针域。使p结点被删除，结点被删除，然后释放存储空间。然后释放存储空间。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算q-next=p-next;free(p);2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算【算法】【算法】void delete(NODE*head,int x)/*删除链表中的给定元素x*/NODE*p,*q;q=head;/*q用来指向删除结点的前驱结点*/p=q-next;/*q用来指向删

23、除结点*/while(p!=NULL)&(p-data!=x)/*查找要删除的元素*/q=p;p=p-next;if(p=NULL)printf(%d not found.n,x);/*x结点未找到*/else q-next=p-next;/*链接x直接后继结点*/free(p);/*删除x结点，释放x结点空间*/5.输出单链表输出单链表若要将单链表按其逻辑顺序输出，就必须从若要将单链表按其逻辑顺序输出，就必须从头到尾访问单链表中的每一个结点。头到尾访问单链表中的每一个结点。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算void print(NODE*head)/*输出单向链

24、表各元素输出单向链表各元素*/NODE*p;p=head-next;printf(Output the list:);while(p!=NULL)printf(%3d,p-data);p=p-next;5.输出单链表输出单链表2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算【算法】【算法】如果将如果将单链表最后一个结点的指针指向头结点单链表最后一个结点的指针指向头结点，使链表形成一个环形，此链表就称为使链表形成一个环形，此链表就称为循环链表循环链表（Circular Link List）。）。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.3 循环链表结

25、构循环链表结构【解析书上的例子】【解析书上的例子】1.双向链表的基本概念双向链表的基本概念 在循环链表的结点中再增加一个指针域，这个在循环链表的结点中再增加一个指针域，这个指针直接指向该结点的指针直接指向该结点的 直接前驱。这样，链表中一直接前驱。这样，链表中一个结点就有了两个指针域，我们把这样的链表称个结点就有了两个指针域，我们把这样的链表称为为双向链表双向链表。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.3.4 双向链表结构双向链表结构双向链表中结点结构如图所示:双向链表的双向链表的C C语言描述如下语言描述如下:2.3 线性表的链式存储结构及其运算线性表的链式存储

26、结构及其运算typedef struct dupnode int data;/*以整型数据为例，实际可为任意允许的类型以整型数据为例，实际可为任意允许的类型*/struct dupnode*next，*prior;/*定义指向直接后继和直接前驱的指针定义指向直接后继和直接前驱的指针*/DUPNODE;如果每条链都构成一个循环链表，则称这样如果每条链都构成一个循环链表，则称这样的链表为的链表为双向循环链表双向循环链表。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.插入运算插入运算在双向链表的p结点之后插入新结点q。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其

27、运算 p-next=q;q-prior=p;q-next=p-next;（p-next）-prior=q;void insert（DUPNODE*p，DUPNODE*q）/*把把q结点插在双向链表的结点插在双向链表的p结点之后结点之后*/q-prior=p;q-next=p-next;（p-next）-prior=q;p-next=q;2.3 线性表的链式存储结构及其运算2.插入运算插入运算【算法】【算法】3.删除运算删除运算将双向链表中的将双向链表中的 p 结点删除。结点删除。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算（p-next）-prior=p-prior;（p-

28、prior）-next=p-next;void delete（DUPNODE*p）/*在双向链表中删除结点在双向链表中删除结点p*/（p-prior）-next=p-next;（p-next）-prior=p-prior;free（p）;2.3 线性表的链式存储结构及其运算3.删除运算删除运算【算法】【算法】例例2.1 有两个线性表有两个线性表A和和B，都是循环链表存储结构，都是循环链表存储结构，两个链表头指针分别为两个链表头指针分别为 head1和和head2，将，将B链表链表链接到链接到A链表的后面，链表的后面，合并成一个链表。合并成一个链表。2.4 算法应用举例算法应用举例2.4 算法应

29、用举例算法应用举例算法如下：#includetypedef struct node int data;struct node*next;NODE;NODE*connect（NODE*head1，NODE*head2）/*把循环链表把循环链表A和和B合并成一个循环链表。合并成一个循环链表。head1和和head2分别为两个循环分别为两个循环链表的头指针链表的头指针*/NODE*p，*q;p=head1-next;while（p-next!=head1）/*找找head1的最后一个结点的最后一个结点*/p=p-next;q=head2-next;while（q-next!=head2）/*找找he

30、ad2的最后一个结点的最后一个结点*/q=q-next;【算法】【算法】p-next=head2-next;q-next=head1;/*两表链接两表链接*/free(head2);free(head2);return(head1);return(head1);mainmain（）（）/*/*主程序主程序*/*/NODE*a NODE*a，*b*b，*c*c，*d*d，*e*e，*f;*f;a=create_circular();/*a=create_circular();/*调用建表函数，建立循环链表调用建表函数，建立循环链表A*/A*/b=create_circular();/*b=cre

31、ate_circular();/*调用建表函数，建立循环链表调用建表函数，建立循环链表B*/B*/c=connect(a,b);c=connect(a,b);d=c;d=c;while while（d-next!=cd-next!=c）d=d-next;d=d-next;printf printf（%3d%3d，d-datad-data）;/*/*显示链接后的整个链表显示链接后的整个链表*/*/数组是线性表的推广数组是线性表的推广，也是一种常用的数据结构。，也是一种常用的数据结构。数组是由一组数组是由一组具有相同特性的数据元素具有相同特性的数据元素组成的。组成的。数据元素在数组中的数据元素在数

32、组中的相对位置是由其下标来确定相对位置是由其下标来确定的。的。一旦定义了数组，它的维数和元素数目也就确定了，一旦定义了数组，它的维数和元素数目也就确定了，而且而且数据元素的下标具有上下界约束关系，并且是有数据元素的下标具有上下界约束关系，并且是有序的序的。2.5 数组2.5.1 数组的定义数组的定义 a a a a a a a a a a a a1112 131n2122232nm1m2m3mn2.5 数组2.5.1 数组的定义数组的定义 如果每个数组元素含有两个下标，则称该数组为如果每个数组元素含有两个下标，则称该数组为二维数组。如图，一个二维数组。如图，一个mn矩阵就是一个二维数组矩阵就是

33、一个二维数组.通常数组采用的是通常数组采用的是顺序存储结构顺序存储结构,即即把数组元素顺序把数组元素顺序地存放在一片地址连续的存储单元中。地存放在一片地址连续的存储单元中。2.5 数组2.5.2 数组的顺序存储结构数组的顺序存储结构二维数组有两种存储方式：二维数组有两种存储方式：a11a12a13a21a22a23 a11 a12 a13 a21 a22 a23 例：例：以列为主顺序以列为主顺序的存储方式的存储方式以行为主顺序以行为主顺序的存储方式的存储方式a11a21a12a22a13a23 二维数组存储地址的二维数组存储地址的计算与一维数组存储地址计算与一维数组存储地址的计算类似。的计算类

34、似。LOC(aij)=LOC(a11)+(i-1)n+j-1)L第一个元素第一个元素a11的的存储位置存储位置2.5 数组2.5.2 数组的顺序存储结构数组的顺序存储结构 a a a a a a a a a31 a32 a33 a a a a1112 131n2122232nm1m2m3mn 假设给定二维数组假设给定二维数组amn 按行为主顺序按行为主顺序存储，则存储，则数组中任一元素数组中任一元素aij 的存储地址计算公式为的存储地址计算公式为:a a a a a a a a a a a a a a a1112 13152122232551525355a53存储地存储地址为址为1044 假设

35、：假设：55的二维整型数组首地址为的二维整型数组首地址为1000，求求a53的存储地址？的存储地址？2.5 数组2.5.2 数组的顺序存储结构数组的顺序存储结构1424541000+(5-1)5(3-1)21044一般将要压缩存储的矩阵分成一般将要压缩存储的矩阵分成特殊矩阵特殊矩阵和和稀疏矩阵稀疏矩阵。具有相同值的元素和非零元素有一定分布规律的矩具有相同值的元素和非零元素有一定分布规律的矩阵，称为阵，称为特殊矩阵特殊矩阵，如三角矩阵等。，如三角矩阵等。零元素远远多于非零元素零元素远远多于非零元素，并且非零元素的分布没，并且非零元素的分布没有规律的矩阵称为有规律的矩阵称为稀疏矩阵稀疏矩阵。2.5

36、 数组数组2.5.3 矩阵的压缩存储矩阵的压缩存储1.三角矩阵三角矩阵以对角线划分，三角矩阵有以对角线划分，三角矩阵有上三角上三角和和下三角下三角两种。两种。2.5 数组数组 a 0 0 0 0 a a 0 0 0 a31 a32 a33 a a a a54 a11 212251525355 a a a a a 0 a a a a 0 0 a33 a34 a35 0 0 0 0 a1112 1315242223251455【上三角示意图】【上三角示意图】【下三角示意图】【下三角示意图】非零元素个数非零元素个数为为n(n+1)/2在下三角矩阵中，可以用一在下三角矩阵中，可以用一个一维数组个一维数

37、组An来存储矩阵中的来存储矩阵中的非零元素，非零元素，A1=a11,A2=a21,A3=a22,矩阵中的矩阵中的元素是以行为主要顺序存放在元素是以行为主要顺序存放在A数组中。数组中。a 0 0 0 0 a a 0 0 0 a31 a32 a33 a a a a54 a11 2122515253552.5 数组数组 下三角矩阵下三角矩阵下三角矩阵中任一非零元素下三角矩阵中任一非零元素aij（ij）的下标和一维数组）的下标和一维数组A的下标的下标K有一个惟一的对应关系，即有一个惟一的对应关系，即K=i*（i-1）/2+j【下三角示意图】【下三角示意图】对于对于n阶上三角矩阵，也可以阶上三角矩阵，也

38、可以用类似下三角矩阵的方法存储用类似下三角矩阵的方法存储 其非零元素和一维数组其非零元素和一维数组A的的下标下标K的对应关系为的对应关系为:K=(i-1)*n-(i-1)(i-2)/2+(j-i+1)a a a a a 0 a a a a 0 0 a33 a34 a35 0 0 0 0 a1112 1315242223251455【上三角示意图】【上三角示意图】2.5 数组数组 上三角矩阵上三角矩阵2.稀疏矩阵稀疏矩阵稀疏矩阵一般都采用压缩存储的方法来存储矩稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素。有两种常用的存储稀疏矩阵的方法阵中的元素。有两种常用的存储稀疏矩阵的方法:三元组表法三

39、元组表法和和十字链表法十字链表法。2.5 数组数组5 0 0 0 85 0 0 0 80 0 7 0 00 0 7 0 00 0 0 0 00 0 0 0 00 3 0 0 00 3 0 0 00 0 0 0 00 0 0 0 07 0 0 9 07 0 0 9 0A=1 11 15 51 15 58 82 23 37 74 42 23 36 61 17 76 64 49 9（a a）稀疏矩阵（b b）三元组表）三元组表图图2.23 2.23 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 row col val2.稀疏矩阵三元组稀疏矩阵三元组2.5 数组数组typedef struct trino

40、de int row，col;/*row为行号，为行号，col为列号为列号*/int val;/*val为结点的值，以整数为例为结点的值，以整数为例*/TRINODE;【三元组线性表中的结点定义】【三元组线性表中的结点定义】2.稀疏矩阵三元组稀疏矩阵三元组2.5 数组数组图图2.24 十字链表的结点结构十字链表的结点结构2.稀疏矩阵十字链表法稀疏矩阵十字链表法2.5 数组数组 行域行域 列域列域 值域值域 row col val down right 用十字链表作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针【结点类型用【结点类型用C C语言描述如下语

41、言描述如下】行域行域 列域列域 值域值域 row col val down right图图2.24 十字链表的结点结构十字链表的结点结构typedef struct matrixnode int row，col;int val;struct matrixnode*down，*right;MATRIXNODE;图2.23（a）中的稀疏矩阵A对应的十字链表如图2.25所示。图图2.25 稀疏矩阵稀疏矩阵的十字链表的十字链表 线性表是一种具有线性表是一种具有一对一的线性关系一对一的线性关系的特殊数的特殊数据结构。据结构。线性表有两种存储方法线性表有两种存储方法:用用顺序存储方法顺序存储方法来来表示这

42、种线性关系，得到顺序存储结构（即顺序表）表示这种线性关系，得到顺序存储结构（即顺序表）;用用链式存储方式链式存储方式来表示这种线性关系，得到线性表来表示这种线性关系，得到线性表的链式存储结构（即链表）。的链式存储结构（即链表）。本章小结1、线性表的、线性表的顺序存储结构顺序存储结构简称为简称为顺序表顺序表(Sequential List)。在线性表中在线性表中逻辑关系相邻逻辑关系相邻的数据元素，在计算机的数据元素，在计算机的内存中的内存中物理位置也是相邻物理位置也是相邻的。的。一、一、线性表的顺序存储结构线性表的顺序存储结构a1a2.aian每个元素每个元素占用占用L个个存储单元存储单元LOC

43、（ai）=LOC（a1）+（i-1）L2、线性表中第、线性表中第i个元素个元素ai的存储位置的存储位置#define MAXLEN 100typedef int elementtype;typedef struct elementtype sMAXLEN;/*线性表的最大容量线性表的最大容量*/int len;/*线性表当前的长度线性表当前的长度*/Sqlist;3、顺序结构的、顺序结构的c语言描述：语言描述：1.插入运算插入运算InsertsqList（i，x，&List）的实现的实现:a1a2.ai-1aiana1a2.ai-1aianx插入后插入后移动元素的平均次数为 n/2int in

44、sertsqlist(int i,elementtype x,SqList*sql)/*在顺序表在顺序表(*sql)的第的第i个元素之前插入一个新元素个元素之前插入一个新元素x*/int j;if(isql-len)/*i值非法，返回值为值非法，返回值为0*/return(0);else for(j=sql-len;j=i;j-)sql-sj+1=sql-sj;sql-sj+1=x;/*修正插入位置为修正插入位置为j+1*/(sql-len)+;/*表长加表长加1*/return(1);/*插入成功，返回值为插入成功，返回值为1*/2.删除运算删除运算DeletesqList（i，&List）

45、的实现）的实现:a1a2.ai-1aiai+1ana1a2.ai-1ai+1an删除后删除后删除元素平均次数为（n-1)/2int delsqlist(int i,SqList*sql)/*删除顺序表(*sql)的第i个元素*/int j;if(i sql-len)/*i值非法，返回值为0*/return(0);else for(j=i+1;jlen;j+)sql-sj-1=sql-sj;(sql-len)-;/*表长度减1*/return(1);/*删除成功，返回值为1*/【算法】【算法】二、二、线性表的链式存储结构线性表的链式存储结构a1a3 a2typedef struct node i

46、nt data;/*数据域数据域*/struct node*next;/*指针域指针域*/NODE;线性表的链式存储结构，是通过结点之间的链接线性表的链式存储结构，是通过结点之间的链接而得到的，链式存储结构有而得到的，链式存储结构有单链单链 表表、双向链表双向链表和和循环循环链表链表等。等。1、单链表、单链表 C语言描述语言描述为了处理问题方便，在链表中为了处理问题方便，在链表中增加一个头结点增加一个头结点。NODE*locate(NODE*head,int x)/*在已知链表中查找给定的值在已知链表中查找给定的值x*/NODE*p;p=head-next;while(p!=NULL)&(p-

47、data!=x)p=p-next;/*指向下一个元素指向下一个元素*/return(p);（1）按值查找按值查找 【算法】【算法】1、查找、查找NODE*find(NODE*head,int i)/*在已知链表中查找给定的值在已知链表中查找给定的值x*/int j=1;NODE*p;p=head-next;/*初始化，初始化，p指向第一个结点，指向第一个结点，j为计数器为计数器*/while(p!=NULL)&(jnext;/*指向下一个元素指向下一个元素*/j+;/*计数器计数器j加加1*/return(p);（2）按序号查找按序号查找【算法】【算法】3.单链表上的插入运算单链表上的插入运算

48、p-next=q;q-data=x;q-next=p-next;4.单链表上的删除运算单链表上的删除运算q-next=p-next;free(p);void print(NODE*head)/*输出单向链表各元素输出单向链表各元素*/NODE*p;p=head-next;printf(Output the list:);while(p!=NULL)printf(%3d,p-data);p=p-next;5.输出单链表输出单链表【算法】【算法】如果将如果将单链表最后一个结点的指针指向头结点单链表最后一个结点的指针指向头结点，使链表形成一个环形，此链表就称为使链表形成一个环形，此链表就称为循环链表

49、循环链表（Circular Link List）。）。三、循环链表结构三、循环链表结构非空单循环链表非空单循环链表head中中p所指向的结点是尾结点的所指向的结点是尾结点的判断条件是判断条件是_a a1 1headheada an na a2 2答案答案:p-next=headp-next=head双向链表的双向链表的C C语言描述如下语言描述如下:typedef struct dupnode int data;/*以整型数据为例，实际可为任意允许的类型以整型数据为例，实际可为任意允许的类型*/struct dupnode*next，*prior;/*定义指向直接后继和直接前驱的指针定义指向直

50、接后继和直接前驱的指针*/DUPNODE;1.双向链表的基本概念双向链表的基本概念四、四、双向链表结构双向链表结构如果每条链都构成一个循环链表，则称这样如果每条链都构成一个循环链表，则称这样的链表为的链表为双向循环链表双向循环链表。2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算2.插入运算插入运算在双向链表的p结点之后插入新结点q。p-next=q;q-prior=p;q-next=p-next;（p-next）-prior=q;C Cq qB BD DC Cp pq qq q B BD Dp pp pq qp-next=qp-next=qp-prior=q-priorp-p