数据结构完整版课件全套ppt教学教程汇总最新最全.ppt

《数据结构完整版课件全套ppt教学教程汇总最新最全.ppt》由会员分享，可在线阅读，更多相关《数据结构完整版课件全套ppt教学教程汇总最新最全.ppt（385页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论学习目的要求:1.理解和熟悉数据结构中的基本概念。2.理解和掌握线性结构、树形结构和图形结构的概念和二元组的表示方法。3.熟悉算法评价的一般规则，算法时间复杂度、空间复杂度的概念和数量级的表示方法。数据结构（第四版）数据结构（第四版）第第1章章 绪绪 论论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 数据的逻辑结构数据的逻辑结构1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）例1.1 电话号码自动查找问题。我们称这种数据结构为线性表。1.1

2、1.1 什么是数据结构什么是数据结构序号用户名电话号码地址01赵一12345671青年路1-1号02钱二12345672青年路1-2号03孙三12345673青年路1-3号04李四12345674青年路1-4号05周五12345675青年路1-5号06吴六12345676青年路1-6号07郑七12345677青年路1-7号08王九12345678青年路1-8号数据结构（第四版）数据结构（第四版）例1.2 计算机磁盘中文件的目录结构。文件目录结构示意图在磁盘目录中，包含一个根目录和若干个一级子目录或文件，在一级子目录中又包含若干个子目录或文件。我们称这种数据结构为树形结构。1.1 1.1 什么是

3、数据结构什么是数据结构数据结构（第四版）数据结构（第四版）网络结构示意图统。它是由各个 网站和终端用户所组成，利用网线或电话线连接到一起的。例1.3 Internet网络系统。我们称这种数据结构为图形结构。1.1 1.1 什么是数据结构什么是数据结构数据结构（第四版）数据结构（第四版）1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语1.数据（Data）数据是指能够输入到计算机中，并能被计算机处理的一切对象。对计算机科学而言，数据的含义极为广泛，如整数、实数、字符、文字、图形、图像和声音等都是数据。数据结构（第四版）数据结构（第四版）2.数据元素（Data Element）数据元

4、素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。但它还可以分割成若干个具有不同属性的项（字段）。数据元素一般由一个或多个数据项组成。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）3.数据项（Data Item）数据项是具有独立意义的最小数据单位，是对数据元素属性的描述。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）4.数据类型（Data Type）数据类型是一组性质相同的值的集合以及定义于这个值的集合上的一组操作的总称。每个数据项属于某一确定的基本数据类型。1.2 1.

5、2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）5.数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合是0，1，2，;字母字符数据对象的集合是A，B，C，Z;电话号码查找系统中，数据对象就是全体电话用户。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）6.数据结构（Data Structure）数据结构的基本含义是指数据元素之间的关系，它是按照某种关系组织起来的一批数据，以一定的存储方式把它们存储到计算机存储器中，并在这些数据上定义了一个运算

6、的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，数据元素之间的这种相互关系就称为结构，带有结构的数据对象称为数据结构。1.2 1.2 数据的逻辑结构数据的逻辑结构1.2.1 基本术语数据结构（第四版）数据结构（第四版）1.2.2 数据的逻辑结构集合：结构中各数据元素之间不存在任何关系。线性结构：在该数据结构中的数据元素存在着一对一的关系。树形结构：在该数据结构中的数据元素存在着一对多的关系。图形或网状结构：在该数据结构中的数据元素存在着多对多的关系。1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）（a）集合结构示意图（b）线性结构示

7、意图（c）树形结构示意图（d）图形结构示意图数据的逻辑结构的基本分类:1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）数据结构可用二元组S=（D，R）的形式来描述。其中，D表示数据元素的集合，R表示D上关系的集合。关于二元组S=（D，R）中前驱和后继的关系，可以描述如下，假设a1，a2是D中的两个元素，则在二元组中，a1是a2的直接前驱，a2是a1的直接后继。数据逻辑结构的数学定义方法:1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）例1.4 用上面的数学方法给出一周七天的数据逻辑结构。设a1、a2、a3、a4、a5、a6、a7分

8、别表示星期一至星期日，这是线性结构。图中圆框表示一个结点，圆框内的符号是该结点的值，带箭头的线段表示前驱与后继的关系。1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）例1.5 设一个数据结构的抽象描述为 S=D，R，其中:D=1，2，3，4，5，6，7，8R=，1.2 1.2 数据的逻辑结构数据的逻辑结构数据结构（第四版）数据结构（第四版）1.3 1.3 算法的描述算法的描述1.3.1 算法算法是对某一特定问题求解步骤的一种描述。在计算机系统中，算法是由若干条指令组成的有穷序列，其中每一条指令表示计算机的一个或多个操作。数据结构（第四版）数据结构（第四版）算法满

9、足以下5个性质:1.输入:一个算法可以有0个或多个输入量，在算法执行之前提供给算法。2.输出:一个算法的执行结果要有一个或多个输出量，它是算法对输入数据处理的结果。3.有穷性:一个算法必须在执行有穷步骤之后结束，并且每一步骤也都必须在有限的时间之内完成。4.确定性:算法中的每一步骤都有明确的含义，没有二义性。5.可行性:算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后来完成。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）1.3.2 算法的设计要求一般来说，算法必须具有以下几个方面的基本特征:（1）正确性 正确性是设计一个算法的首要条件，所设计的算法要

10、满足具体问题的要求。在给算法输入合理的数据后，能在有限的时间内得出正确的结果。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）（2）可读性 算法是对特定问题求解步骤的一种描述，它要转变成计算机可执行的程序，同时必须可以供他人使用。为了阅读与交流，所设计的算法要让他人能看懂，在算法或程序中可以增加一些注释来提高可读性。1.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）（3）健壮性 当输入的数据不符合要求时，算法应能判断出数据的非法性，并能进行适当的处理。比如，暂停或终止程序的执行，显示错误信息等。不允许产生不可预料的结果。1

11、.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）（4）高效性 算法的效率是指算法执行的时间和占用的存储空间。如果对于同一个问题有多个算法可供选择，应尽可能选择执行时间短、占用空间少的算法。1.3 1.3 算法的描述算法的描述1.3.2 算法的设计要求数据结构（第四版）数据结构（第四版）1.3.3 算法的评价一个好的算法首先要具备正确性，然后是可读性和健壮性。在具备了这三个条件后，就应考虑算法的效率问题，即算法的时间效率和空间效率两个方面。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）（1）时间效率 时间效率就是考虑一个算

12、法运行时所需时间的多少。一个算法运行所需要的时间与算法中语句执行的次数成正比，如果算法中语句重复执行的次数越多，所需要的时间也就越多。时间复杂度一般不是算法的精确执行次数，而是结算的数量级。它着重体现的是随着问题规模的增大，算法执行时间增长的变化趋势。1.3.3 算法的评价1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）例1.6 求下列4个程序段的语句频度。1.3 1.3 算法的描述算法的描述（a）i+;x=0;（b）for（i=1;i=n;i+）x=x+1;（c）for（i=1;i=n;i+）for（j=1;j=n;j+）x=x+1;（d）for（i=1;i=n;i+

13、）for（j=1;j=n;j+）for（k=1;k=n;k+）x=x+1;数据结构（第四版）数据结构（第四版）（a）是一个没有循环算法的基本操作，它的语句频度与问题规模没有关系，记作 T（n）=O（1），也称为常量阶。（b）是一个一重循环的算法，它的语句频度随问题规模 n的增大而呈线性增大，这种线性关系记作 T（n）=O（n），也称线性阶。（c）是一个二重循环的算法，它的语句频度为 n2，记作T（n）=O（n2），称为平方阶。（d）是一个三重循环的算法，它的语句频度为 n3，记作T（n）=O（n3），称为立方阶。1.3 1.3 算法的描述算法的描述常见的时间复杂度还有对数阶 O（log 2n）

14、、O（n log 2n），指数阶O（2n）等。数据结构（第四版）数据结构（第四版）（2）空间效率 一个算法在执行过程中所占用的存储空间大小，称为空间效率或空间频度。与时间复杂度类似，空间复杂度是指算法在计算机内执行时临时占用的存储空间大小。算法的空间复杂度一般以数量级形式给出。1.3 1.3 算法的描述算法的描述数据结构（第四版）数据结构（第四版）1.数据结构研究的是数据的表示形式和数据之间的相互关系。数据的逻辑结构有四种:集合、线性结构、树形结构和图形结构。2.集合的数据元素之间不存在任何关系;线性结构的数据元素之间存在一对一的线性关系;树形结构的数据元素之间存在一对多的非线性关系;图形结构

15、的数据元素之间存在多对多的非线性关系。3.算法的评价指标主要为正确性、可读性、健壮性和高效性四个方面。在高效性中又包括算法执行的时间效率和所占用的空间效率。4.通常用数量级的形式来表示算法的时间复杂度和空间复杂度。数量级的形式有常量阶、线性阶、平方阶、立方阶、对数阶和指数阶等。一个算法的时间复杂度和空间复杂 度越低，算法的执行效率就会越高。本章小结本章小结数据结构（第四版）数据结构（第四版）谢谢观看！谢谢观看！谢谢观看！谢谢观看！数据结构（第四版）数据结构（第四版）第第2章章 线性表线性表数据结构（第四版）数据结构（第四版）第2章 线性表学习目的要求:1.线性表的定义和线性表的特征。2.线性表

16、的顺序存储结构及其算法的实现。3.线性链表的描述及其算法的实现。循环链表和双向循环链表的描述。数组的顺序存储和矩阵的压缩存储的描述。数据结构（第四版）数据结构（第四版）2.1 线性表的基本概念2.2 线性表的顺序存储结构及其算法2.3 线性表的链式存储结构及其运算2.4 算法应用举例2.5 数组第2章 线性表数据结构（第四版）数据结构（第四版）2.1.1 线性表的定义2.1 线性表的基本概念线性表（linear list）是由 n个数据元素组成的有限序列。线性表可以用一个标识符来命名，如果用A来表示线性表，则:A=（a1 ，a2 ，ai ，an ）线性表是一种非常典型的线性结构，用二元组可以表

17、示成:S=（D，R）D=a1，a2，ai，an R=，数据结构（第四版）数据结构（第四版）2.1.2 线性表的基本操作（1）InitList（List）:初始化操作，建立一个空的线性表List;（2）ListLength（List）:求线性表的长度;（3）GetElement（List，i）:取线性表中的第 i 个元素（1 i n，n为线性表长度）;（4）PriorElement（List，x）:若 x 不是第一个数据元素，则取 x 的直接前驱;（5）NextElement（List，x）:若 x 不是最后一个元素，则取 x 的直接后继;（6）LocateElement（List，x）:若 x

18、 存在于表中，则取得 x 的位置（位序）;（7）ListInsert（List，i，x）:在线性表第 i 个元素之前插入一个数据元素x;（8）ListDelete（List，i）:删除线性表中第 i 个元素（1 i n，n为线性表长度）。2.1 线性表的基本概念数据结构（第四版）数据结构（第四版）2.2 线性表的顺序存储结构及其算法2.2.1 线性表的顺序存储结构线性表的顺序存储结构简称为顺序表（Sequential List）。顺序存储结构的特点是:在线性表中逻辑关系相邻的数据元素，在计算机的内存中物理位置也是相邻的。线性表中第i个元素ai的存储位置为:LOC（ai）=LOC（a1）+（i-

19、1）L数据结构（第四版）数据结构（第四版）2.2.2 顺序表的运算1.插入运算插入运算是指在具有n个元素的线性表的第i（1in）个元素之前插入一个新元素x。2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）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-s

20、j+1=x;/*修正插入位置为j+1*/(sql-len)+;/*表长加1*/return(1);/*插入成功，返回值为1*/2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）2.删除运算删除运算是指从具有n个元素的线性表中，删除其中的第i（1in）个元素，使表的长度减1。2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）int delsqlist(int i,SqList*sql)/*删除顺序表(*sql)的第i个元素*/int j;if(isql-len)/*i值非法，返回值为0*/return(0);else for(j=i+1;jlen;j+

21、)sql-sj-1=sql-sj;/*向前移动数据，覆盖前一数据*/(sql-len)-;/*表长度减1*/return(1);/*删除成功，返回值为1*/2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）2.3.1 线性表的链式存储结构 为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。typedef struct node int data;struct node*next;NODE;2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）线性链表是通过结点指针域中的指针表示各结点之间的线

22、性关系的。线性表的每个结点都有一个链接指针，所以不要求链表中的结点必须按照结点先后次序存储在一个地址连续的存储区中。在链表中插入或删除数据元素比在顺序表中要容易得多，但是链表结构需要的存储空间较大。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.3.2 单链表的运算若线性链表的每个结点只含有一个指针域，则称这样的线性链表为单链表。1.建立带表头结点的单链表建立链表时，首先要建立表头结点，此时为空链表。然后将新的结点逐一插入到链表中，其过程如下:（1）申请存储单元，用C语言的动态分配库函数malloc得到。（2）读入新结点的数据，新结点的指针域为空。（3）把新结点链接

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

24、为是否建立新结点的标志，若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 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.单链表中结点的查找单链表有两种查找方法，即按序号查找和按给定值查找。在单链表中，即使知道了要查找的结点的序号，也只能从头指针开始查找。与顺序表不一样，单链表不能实现随机查找。2.3 线性表的链式存储结

25、构及其运算数据结构（第四版）数据结构（第四版）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 线性表的链式存储结构及其运算按值查找，就是在单链表中查找是否存在数据域值为给定的值（如整数x）的结点。数据结构（第四版）数据结构（第四版）NODE*find(NODE*head,int i)/*在已知链表中查找给定的值x*/int j=1;NODE*p;p=

26、head-next;while(p!=NULL)&(jnext;/*指向下一个元素*/j+;return(p);（2）按序号查找2.3 线性表的链式存储结构及其运算在单链表中查找第 i 个位置上的结点，若找到，则返回它的地址，否则返回NULL。数据结构（第四版）数据结构（第四版）3.单链表上的插入运算在顺序表中，插入运算时，将会有大量元素向后移动。而在单链表中，插入一个结点不需要移动元素，只需要修改指针即可。若将x插入到a1 和a2 之间，其过程如下:（1）建立一个新结点 q，将x值赋给q-data。（2）修改有关结点的指针域。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第

27、四版）void insert(NODE*p,int x)/*在链表的p结点后插入给定元素x*/NODE*q;q=(NODE*)malloc(sizeof(NODE);/*申请新的存储空间*/q-data=x;q-next=p-next;/*实现图的*/p-next=q;/*实现图的，将新结点q链接到p结点之后*/2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）4.单链表上的删除运算删除单向链表中的结点x，并由系统收回其占用的存储空间，其过程如下:（1）设定两个指针p和q，p指针指向被删除结点，q为跟踪指针，指向被删除结点的直接前驱结点。（2）p从表头指针 head 指向

28、的第一个结点开始依次向后搜索。当p data 等于x时，被删除结点找到。（3）修改p的前驱结点q的指针域。使p结点被删除，然后释放存储空间。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）void delete(NODE*head,int x)/*删除链表中的给定元素x*/NODE*p,*q;q=head;p=q-next;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直接后继结

29、点*/free(p);/*删除x结点，释放x结点空间*/2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）5.输出单链表若要将单链表按其逻辑顺序输出，就必须从头到尾访问单链表中的每一个结点。void print(NODE*head)/*输出单向链表各元素*/NODE*p;p=head-next;printf(Output the list:);while(p!=NULL)printf(%3d,p-data);p=p-next;2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.3.3 循环链表结构如果将单链表最后一个结点的指针指向头结点，使链表形成

30、一个环形，此链表就称为循环链表（Circular Link List）。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.3.4 双向链表结构1.双向链表的基本概念在循环链表的结点中再增加一个指针域，这个指针直接指向该结点的 直接前驱。这样，链表中一个结点就有了两个指针域，我们把这样的链表称为双向链表。2.3 线性表的链式存储结构及其运算如果每条链都构成一个循环链表，则称这样的链表为双向循环链表。数据结构（第四版）数据结构（第四版）2.插入运算在双向链表的p结点之后插入新结点q。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）void inse

31、rt（DUPNODE*p，DUPNODE*q）/*把q结点插在双向链表的p结点之后*/q-prior=p;q-next=p-next;（p-next）-prior=q;p-next=q;2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）3.删除运算将双向链表中的 p 结点删除。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）void delete（DUPNODE*p）/*在双向链表中删除结点p*/（p-prior）-next=p-next;（p-next）-prior=p-prior;free（p）;2.3 线性表的链式存储结构及其运算数据结构（第

32、四版）数据结构（第四版）例2.1 有两个线性表A和B，都是循环链表存储结构，两个链表头指针分别为 head1和head2，将B链表链接到A链表的后面，合并成一个链表。2.4 算法应用举例数据结构（第四版）数据结构（第四版）例2.2 一元多项式的加法运算。设有两个一元多项式分别为:An（x）=a0+a1x+a2x2+anxn Bm（x）=b0+b1x+b2x2+bm x m多项式中每个非零项的系数用一个结点来表示，结点中含有两个数据域和一个指针域，两个数据域分别存放非零项的系数和指数。typedef struct pnode int coef;/*系数以整型为例*/int exp;/*指数*/s

33、truct pnode*next;PNODE;2.4 算法应用举例数据结构（第四版）数据结构（第四版）设有多项式 A（x）=1+2x+4x3 （1）B（x）=2-2x+3x2 （2）2.4 算法应用举例多项式（1）加多项式（2）的和为多项式（3）:R（x）=3+3x2+4x3 （3）数据结构（第四版）数据结构（第四版）数组是线性表的推广，也是一种常用的数据结构。2.5.1 数组的定义 数组是由一组具有相同特性的数据元素组成的。数据元素在数组中的相对位置是由其下标来确定的。一旦定义了数组，它的维数和元素数目也就确定了，而且数据元素的下标具有上下界约束关系，并且是有序的。2.5 数组数据结构（第四

34、版）数据结构（第四版）2.5.2 数组的顺序存储结构通常数组采用的是顺序存储结构，即把数组元素顺序地存放在一片地址连续的存储单元中。二维数组存储地址的计算与一维数组存储地址的计算类似。假设给定二维数组 按行为主顺序存储，则数组中任一元素aij 的存储地址计算公式为 2.5 数组LOC（aij）=LOC（a 11）+（i-1）n+j-1）L数据结构（第四版）数据结构（第四版）2.5.3 矩阵的压缩存储一般将要压缩存储的矩阵分成特殊矩阵和稀疏矩阵。具有相同值的元素和非零元素有一定分布规律的矩阵，称为特殊矩阵，如三角矩阵带状矩阵等。零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵称为稀疏矩阵

35、。2.5 数组数据结构（第四版）数据结构（第四版）1.三角矩阵以对角线划分，三角矩阵有上三角和下三角两种。下三角矩阵中的任一非零元素aij（ij）的下标和一维数组A的下标K有一个惟一的对应关系，即K=i*（i-1）/2+j对于n阶上三角矩阵，也可以用类似下三角矩阵的方法存储，其非零元素和一维数组A的下标K的对应关系为:K=（i-1）*n-（i-1）（i-2）/2+（j-i+1）2.5 数组数据结构（第四版）数据结构（第四版）2.稀疏矩阵稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素。有两种常用的存储稀疏矩阵的方法:三元组表法和十字链表法。在压缩存放稀疏矩阵的非零元素时，还要存放此非零元素所

36、在的行号和列号，这种存储方法称为三元组表法。2.5 数组数据结构（第四版）数据结构（第四版）在链表中，每个非零元素可用一个含5个域的结点表示，其中row、col和val分别表示该非零元素所在行、列和值，向右域right用以链接稀疏矩阵同一行中的非零元素，向下域down用以链接稀疏矩阵同一列中下一个非零元素。同一行的非零元素通过right域链接成一个线性链表，同一列的非零元素通过down域链成一个线性链表，每个非零元素既是某个行链表中的 一个结点，又是某个列链表中的一个结点。整个稀疏矩阵构成一个十字交叉链表，故称这样的存储结构为十字链表。2.5 数组数据结构（第四版）数据结构（第四版）用十字链表

37、作稀疏矩阵存储结构时，每个结点除了存储元素值外，还要存储该非零元素的行、列的下标和两个指针。另外还要增设行、列链表表头指针数组。只有在矩阵中非零元素少于一定数量时采用十字链表才可能节约存储空间。2.5 数组数据结构（第四版）数据结构（第四版）线性表是一种具有一对一的线性关系的特殊数据结构。线性表有两种存储方法:用顺序存储方法来表示这种线性关系，得到顺序存储结构（即顺序表）;用链式存储方式来表示这种线性关系，得到线性表的链式存储结构（即链表）。线性表的链式存储结构，是通过结点之间的链接而得到的，链式存储结构有单链 表、双向链表和循环链表等。单链表结点至少有两个域:一个数据域和一个指针域。双向链表

38、结点至少含有三个域:一个数据域和两个指针域。本章小结数据结构（第四版）数据结构（第四版）4.循环链表不存在空指针，最后一个结点的指针指向表头，形成一个首尾相接的环。5.为了处理问题方便，在链表中增加一个头结点。6.顺序存储可以提高存储单元的利用率，不便于插入和删除运算。链式存储会占用较多的存储空间，可以使用不连续的存储单元，插入、删除运算较方便。本章小结数据结构（第四版）数据结构（第四版）谢谢观看！谢谢观看！谢谢观看！谢谢观看！数据结构（第四版）数据结构（第四版）第第2章章 线性表线性表数据结构（第四版）数据结构（第四版）第2章 线性表学习目的要求:1.线性表的定义和线性表的特征。2.线性表的

39、顺序存储结构及其算法的实现。3.线性链表的描述及其算法的实现。循环链表和双向循环链表的描述。数组的顺序存储和矩阵的压缩存储的描述。数据结构（第四版）数据结构（第四版）2.1 线性表的基本概念2.2 线性表的顺序存储结构及其算法2.3 线性表的链式存储结构及其运算2.4 算法应用举例2.5 数组第2章 线性表数据结构（第四版）数据结构（第四版）2.1.1 线性表的定义2.1 线性表的基本概念线性表（linear list）是由 n个数据元素组成的有限序列。线性表可以用一个标识符来命名，如果用A来表示线性表，则:A=（a1 ，a2 ，ai ，an ）线性表是一种非常典型的线性结构，用二元组可以表示

40、成:S=（D，R）D=a1，a2，ai，an R=，数据结构（第四版）数据结构（第四版）2.1.2 线性表的基本操作（1）InitList（List）:初始化操作，建立一个空的线性表List;（2）ListLength（List）:求线性表的长度;（3）GetElement（List，i）:取线性表中的第 i 个元素（1 i n，n为线性表长度）;（4）PriorElement（List，x）:若 x 不是第一个数据元素，则取 x 的直接前驱;（5）NextElement（List，x）:若 x 不是最后一个元素，则取 x 的直接后继;（6）LocateElement（List，x）:若 x

41、存在于表中，则取得 x 的位置（位序）;（7）ListInsert（List，i，x）:在线性表第 i 个元素之前插入一个数据元素x;（8）ListDelete（List，i）:删除线性表中第 i 个元素（1 i n，n为线性表长度）。2.1 线性表的基本概念数据结构（第四版）数据结构（第四版）2.2 线性表的顺序存储结构及其算法2.2.1 线性表的顺序存储结构线性表的顺序存储结构简称为顺序表（Sequential List）。顺序存储结构的特点是:在线性表中逻辑关系相邻的数据元素，在计算机的内存中物理位置也是相邻的。线性表中第i个元素ai的存储位置为:LOC（ai）=LOC（a1）+（i-1

42、）L数据结构（第四版）数据结构（第四版）2.2.2 顺序表的运算1.插入运算插入运算是指在具有n个元素的线性表的第i（1in）个元素之前插入一个新元素x。2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）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

43、+1=x;/*修正插入位置为j+1*/(sql-len)+;/*表长加1*/return(1);/*插入成功，返回值为1*/2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）2.删除运算删除运算是指从具有n个元素的线性表中，删除其中的第i（1in）个元素，使表的长度减1。2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）int delsqlist(int i,SqList*sql)/*删除顺序表(*sql)的第i个元素*/int j;if(isql-len)/*i值非法，返回值为0*/return(0);else for(j=i+1;jlen;j+)

44、sql-sj-1=sql-sj;/*向前移动数据，覆盖前一数据*/(sql-len)-;/*表长度减1*/return(1);/*删除成功，返回值为1*/2.2 线性表的顺序存储结构及其算法数据结构（第四版）数据结构（第四版）2.3.1 线性表的链式存储结构 为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。typedef struct node int data;struct node*next;NODE;2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）线性链表是通过结点指针域中的指针表示各结点之间的线性

45、关系的。线性表的每个结点都有一个链接指针，所以不要求链表中的结点必须按照结点先后次序存储在一个地址连续的存储区中。在链表中插入或删除数据元素比在顺序表中要容易得多，但是链表结构需要的存储空间较大。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.3.2 单链表的运算若线性链表的每个结点只含有一个指针域，则称这样的线性链表为单链表。1.建立带表头结点的单链表建立链表时，首先要建立表头结点，此时为空链表。然后将新的结点逐一插入到链表中，其过程如下:（1）申请存储单元，用C语言的动态分配库函数malloc得到。（2）读入新结点的数据，新结点的指针域为空。（3）把新结点链接到

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

47、是否建立新结点的标志，若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 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）2.单链表中结点的查找单链表有两种查找方法，即按序号查找和按给定值查找。在单链表中，即使知道了要查找的结点的序号，也只能从头指针开始查找。与顺序表不一样，单链表不能实现随机查找。2.3 线性表的链式存储结构

48、及其运算数据结构（第四版）数据结构（第四版）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 线性表的链式存储结构及其运算按值查找，就是在单链表中查找是否存在数据域值为给定的值（如整数x）的结点。数据结构（第四版）数据结构（第四版）NODE*find(NODE*head,int i)/*在已知链表中查找给定的值x*/int j=1;NODE*p;p=h

49、ead-next;while(p!=NULL)&(jnext;/*指向下一个元素*/j+;return(p);（2）按序号查找2.3 线性表的链式存储结构及其运算在单链表中查找第 i 个位置上的结点，若找到，则返回它的地址，否则返回NULL。数据结构（第四版）数据结构（第四版）3.单链表上的插入运算在顺序表中，插入运算时，将会有大量元素向后移动。而在单链表中，插入一个结点不需要移动元素，只需要修改指针即可。若将x插入到a1 和a2 之间，其过程如下:（1）建立一个新结点 q，将x值赋给q-data。（2）修改有关结点的指针域。2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四

50、版）void insert(NODE*p,int x)/*在链表的p结点后插入给定元素x*/NODE*q;q=(NODE*)malloc(sizeof(NODE);/*申请新的存储空间*/q-data=x;q-next=p-next;/*实现图的*/p-next=q;/*实现图的，将新结点q链接到p结点之后*/2.3 线性表的链式存储结构及其运算数据结构（第四版）数据结构（第四版）4.单链表上的删除运算删除单向链表中的结点x，并由系统收回其占用的存储空间，其过程如下:（1）设定两个指针p和q，p指针指向被删除结点，q为跟踪指针，指向被删除结点的直接前驱结点。（2）p从表头指针 head 指向的