《数据结构(C语言版)整本书课件完整版电子教案(最新).ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)整本书课件完整版电子教案(最新).ppt（417页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（C语言版）第一章第一章 绪论绪论数据结构数据结构2023/3/9目录目录学生成绩管理系统简介什么是数据结构算法与算法分析1.11.1学生成绩系统简介学生成绩系统简介学生成绩管理系统是学校管理信息化的重要组成部分，该系统能大大提高学校学籍管理水平和管理效率，开发该系统必须解决以下问题：u学生成绩的信息存储u学生成绩的增加、删除、修改u学生成绩的查找u学生成绩的排序学号学号姓名姓名性别性别出生年月出生年月数学数学语文语文英语英语20120401王伟男1993/01123989020120402张译民男1993/081151088520120403陈慧女1992/1210811495201
2、20405李彩霞女1993/0510211390表表1-1 1-1 学生成绩信息表学生成绩信息表王伟张译民陈慧李彩霞最简单的线性关系C C语言中的实现方法语言中的实现方法第一步：/*用结构体类型定义学生成绩信息*/typedef struct char no10;/*学号*/char name10;/*姓名*/char sex2;/*性别*/int birthyear;/*出生年份*/int birthmonth;/*出生月份*/int Chinese;/*语文成绩*/int Mathematics;/*数学成绩*/int English;/*英语成绩*/student;/*定义学生成绩信息数
3、组*/student stu50;第二步：定义具有功能相对独立的一些函数来实现，在数据结构中称之为算法。C C语言与数据结构的关系语言与数据结构的关系C语言是一种编程的语言，编程的语言有很多种。而数据结构则是关于数据的理论知识。可以说不管什么编程语言都能用到数据结构的知识，数据结构是程序设计基础又核心的知识。如果将c语言想象为一种语言，那么数据结构就是一种说话的技巧，如何让你说话更简洁、有逻辑、容易让人听懂，这种表达技巧不管你用中文或者英文都可以。1.21.2什么是数据结构什么是数据结构用计算机解决应用问题的一般步骤用计算机解决应用问题的一般步骤数据结构基本概念和术语数据结构基本概念和术语数据
4、数据指所有能输入到计算机中并能被计算机程序处理的符号的总称。数据元素数据元素在计算机程序中通常作为一个整体进行考虑和处理的基本数据单位。一个数据元素可以由若干个数据项组成，也可以只由一个数据项组成。数据元素又被称为元素、结点或记录。数据项数据项是不可分割的、具有独立意义的最小数据单位，数据项有时也被称字段或域。结论：数据、数据元素、数据项反映了数据组织的三个层次：数据可由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。以学生成绩管理系统为例，学生成绩信息表中每一行对应为一个数据元素。这个数据元素中包含有学号、姓名、性别等若干个数据项。数据操作的基本单位是数据元素，如学生成绩的插入
5、或删除一定是对应于某个学生的全部信息，而不是对应于其中的某个数据项。1.2.3 三种数据逻辑结构数据逻辑结构是指数据元素之间的抽象关联方式，数据元素之间存在的一种或多种特定的关系被称为数据的逻辑结构，通常用二元组表示。Data structure=(D,R)Data structure=(D,R)其中D表示数据元素的集合，R表示D上数据元素间的二元关系。D=di|1in,R=rj|1jm其中rj表示数据元素之间存在关系，在关系代数中用有序偶或无序偶表示：rj=，dkDdtD【例1.1】画出数据结构DS1的逻辑结构表示图。【问题描述】有一种数据结构DS1=(D1,R1),其中D1=A,B,C,D
6、,R1=,画出其逻辑结构表示图。【分析】根据逻辑结构图的画法，经整理，DS1对应的逻辑结构图如图1-2所示，该逻辑结构图中第一个元素为A，最后一个元素为D，B、C分别有一个前驱元素和一个后继元素。1.2.3 三种数据逻辑结构ABCD图1-2 DS1对应的逻辑结构图线性结构数据元素之间存在一对一的关系，称为线性结构。该结构的特点是除第一个元素和最后一个元素外，其它元素都有且只有一个直接前趋和直接后继。如图1-2所示的线性结构是一种最常见、也是最简单的数据结构，学生成绩管理系统的数据结构是线性结构，另外仓库管理、教材管理等系统中处理的数据也是线性结构。线性结构的基本操作有插入、删除及查找等，具有线
7、性结构的数据简称为线性表。树形结构【例1.2】文件夹管理问题计算机某磁盘（以C盘为例）的目录结构如图1-3所示，Windows操作系统的文件夹之间是一种层次结构，该结构中的文件夹之间存在一对多的关系，这种结构被称为树形结构。图1-3树形结构的特点是该结构中除了有一个被称为根的结点没有前趋外，其余元素有且只有一个直接前趋，可以有多个后继。【例1.3】画出数据结构k的逻辑结构表示图。【问题描述】有一种数据结构K=（D，R）,其中D=a,b,c,d,e,f,g，R=,，画出其逻辑结构图，并指出其逻辑结构的类型。【分析】画出对应的逻辑结构图1-4所示，该数据结构为树形结构，结点a为树的根结点。abcd
8、efg图1-4图形结构【例1.4】教学计划编排问题【问题描述】一个专业教学计划包含许多课程，有些课程必须按规定的先后次序编排，如C语言程序设计必须在数据结构课程前进行，有些课程没有先后次序，如网页制作和C语言可以同时开课，表1-2反映了课程之间的先后次序，现要求根据表1.2编排出合理的教学计划。课程编号课程名称先修课程C1计算机基础无C2C语言程序设计C1C3数据结构C1，C2C4数据库应用技术C3C5网络操作系统C3C6网页制作C1C7JAVA程序设计C2C8WEB应用开发C2,C4,C7【分析】为解决教学计划编排问题，我们首先得搞清课程之间的关系，如果我们将课程作为数据元素，将课程之间先后
9、次序用有向边表示，就可以得到如图1-5所示的图形结构。图1-5图形结构是最复杂的数据结构，数据元素之间图形结构是最复杂的数据结构，数据元素之间存在多对多联系，该结构中任何元素都可以有存在多对多联系，该结构中任何元素都可以有多个直接前趋，也可以有多个后继。多个直接前趋，也可以有多个后继。全国铁路网、高速公路网等数据是图形结构。全国铁路网、高速公路网等数据是图形结构。上述示例表明，描述非数值计算问题的数学上述示例表明，描述非数值计算问题的数学模型不再是数学方程或公式，而是诸如表、模型不再是数学方程或公式，而是诸如表、树、图之类的数据结构。树、图之类的数据结构。1.2.4 数据物理结构数据在计算机存
10、储器中的存放方式称为数据的物理结构，或称存储结构。数据的存储结构是逻辑结构在计算机存储器中的实现。数据元素在计算机中主要有两种不同的存储方法：顺序存储结构和链式存储结构。例1.1学生成绩管理系统中学生成绩信息在C语言中常以数组形式定义，在高级语句中数组元素是连续存放的，这种存储方式很简单，逻辑上相邻的数据元素在物理上也相邻，这种存储方式称为顺序存储方式。1.2.4 数据物理结构顺序存储结构需要事先预估存储空间的大小。如果学生数不能确定，链式存储结构更有效。数据的逻辑结构、物理结构及数据的运算三个方面构成了数据结构的整体，数据的运算设计取决于数据的逻辑结构，而实现则依赖于指定的存储结构。VS链式
11、存储除了存储所涉及问题的相关信息外，还增加了指针域，记录下一个数据元素所对应的地址，通过指针反映数据元素之间的逻辑关系1.2.51.2.5数据类型数据类型用高级语言编写的程序中，所有的变量、常量或表达式都有一个所属的数据类型，数据类型包含了数据的取值范围及基本操作运算，因此，数据类型是程序设计语言中已经实现了的数据结构。C语言中函数strlen（）返回整型数据，它可以进行四则运算和取模运算操作，也可以通过%d格式输出该函数的值。数据类型可分为两类：一类是非结构的原子类型，C语言中的基本类型、指针类型和空类型；另一类是结构类型，它由原子类型组成，它的成分可以分解，由于数据结构中涉及到很多复杂数据
12、类型，通常用数组及结构体定义。1.3 1.3 算法和算法分析算法和算法分析算法是软件设计的精髓，一个算法实质上是针对所处理问题的需要，在数据逻辑结构和存储结构基础上实施的一种运算。由于数据的逻辑结构和物理结构不是惟一的，所以处理问题的算法也不是惟一的。即使相同逻辑结构和存储结构，由于设计思想和设计技巧不同，算法也不尽相同。根据数据结构所研究问题的范畴，可以得出如下结论。数据结构数据结构=逻辑结构逻辑结构+物理结构物理结构+算法（或操作）算法（或操作）1.3.1算法及其描述广义的算法是指完成某项工作的方法和步骤，我们做任何事情都有算法的支持，洗衣机说明书是操作洗衣机的算法，菜谱是做菜的算法等等。
13、数据结构中讨论的算法是指可以用计算机来解决某一类问题的方法和步骤，在计算机科学中排序算法、查找算法都是最常用的算法。1.3.1算法及其描述算法是指解决特定问题的一种方法或一种描述，是指令的有限序列，其中每一条指令又可以由一个或多个操作组成。有穷性有穷性 一个算法必须在有穷步骤内结束或完成。确定性确定性 算法执行的每一步和下一步必须有明确的规定，不能出现歧义。可行性可行性 算法中的所有操作都可以通过已经实现的基本运算来实现。有输入有输入 一个算法有零个或多个输入，没有输入的算法缺乏灵活。有输出有输出 一个算法有一个或多个输出，没有输出的算法没有实现的价值。算法的描述方法算法可以用自然语言描述，但
14、由于自然语言表达算法容易产生二义性，人们常使用专用的算法描述工具。图1-6传统流程图符号图1-7结构化流程图符号【例1.5】分别用传统流程图和结构化流程图描述一个算法。【问题描述】分别用传统流程图和结构化流程图描述下列问题：给定两个正整数m和n,求最大公约数。【分析】将数学中求最大公约数的辗转相除法的求解过程进行分解，用标准的流程图基本符号表示成图1-8（a）和（b）图。类语言与高级程序设计语言有些类似，有比较严格的外语法，如用ifelse表示选择结构，用while表示循环结构，对内语法如变量定义等无明确要求，这种算法不能直接在计算机上运行，但专业设计人员经常使用伪语言来描述算法，它容易编写、
15、阅读和统一格式。（2）类语言描述（3）C语言编写的程序或函数类C语言是目前应用较广的伪语言描述工具之一。这是可在计算机上运行并获得结果的算法，使给定问题能在有限时间内被求解，通常这种算法也称程序。1.3.2算法性能和复杂度分析正确性 要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。易读性 算法应易于阅读和理解，以便于调试、修改和扩充。健壮性 正确的输入能得到正确的输出这是算法必须具有的特性之一。但当遇到非法输入时，算法应能做出反应或处理(如提示信息等)，而不会产生异常中断、死机或不正确的结果。高效率 算法所需的计算机资源较低1算法设计的目标算法设计的目标由低到高分四个层次：【例1
16、.6】从算法健状性角度来分析如下问题：输入三角形的三条边，计算三角形的面积。【分析】a.合法输入当输入的三条边a,b,c满足构成三角形的条件（a+bc,a+cb,b+ca）时，算法应能得到正常的结果b.非法输入当输入的三条边a,b,c有不满足构成三角形的条件（a+bc,a+cb,b+ca）时，算法应给出相应的提示信息。注意：在算法调试过程，测试数据不仅要包括合法输入，还要尽可能多地包含各种形式的非法输入，以检验算法的健状性（或相容性）算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂度，需要的空间（即存储器）资源的量称作空间复杂度。2.2.算法的复杂性算法的复杂性分析分析运行算法所
17、需要的时间T写成输入规模n的函数，记作T(n)。“规模”一般是指输入量的数目，比如在排序问题中，问题的规模可以是定义为被排序的元素数目。在难以精确计算基本操作执行次数的情况下，只要求出它关于n的增长率即可，忽略常数项和低次项，用大O表示法来表示算法的时间复杂度。因此如果某算法T(n)=c*n+2，则其时间复杂度可简记为O(n)。各种不同的数量阶之间关系如下：O(1)O(logO(1)O(log2 2n)O(n)O(nlogn)O(n)O(nlog2 2n)O(nn)O(n2 2)O(n)O(n3 3)O(2)O(2n n)在一个没有循环的算法中基本运算次数与问题规模无关，记为O(1),也称为常
18、数阶。作为时间复杂度衡量的函数,还有平方阶n2，指数阶2n，对数阶log2n等，数量价低的算法时间效率高。一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法运行过程中临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关，后一种是较理想的情况。一个好的算法应兼顾时间效率和空间效率。【例1.7】分析以下算法的复杂度【问题描述】分析查找一维整数数组中最大元素算法的复杂度，该算法从数组中下标为0的元素开始，遍历数组中的所有元素，在遍历过程中，将当前最大元素保存在变量large中。intlar
19、gest(int*array,intn)intlarge,i;large=arra0;for(i=1;ilarge)large=arrayi;returnlarge;【分析】时间效率：数组array中存放有n个整数，显然，无论那种算法，数据n的值越大，执行的时间越长，因此可将问题的规模定为数组中数据元素的个数n。基本操作是“比较”操作，即将数组中的一个整数和现有的最大整数作比较，上述算法中比较操作的次数为n-1。算法的时间复杂度为O（n）。空间效率：由于本例中仅需临时存储空间为2个变量，与问题规模n无关，因此空间复杂度为O(1)。【例1.8】分析以下程序段的复杂度for(i=0;in;i+)f
20、or(j=0;ji;j+)aij=0;【分析】时间效率：该程序段基本语句为赋值语句：aij=0；程序段运行次数与数据n的值有关，因此可将问题的规模定为n。程序段为双重循环，外循环控制变量i的范围从0到n-1，内循环控制变量j的值为外循环有关，j的取值范围从0到i-1。也就是说当i为0时，赋值语句被执行0次，i为1时，赋值语句被执行1次，当i为n-1时，赋值语句被执行n-1次，基本操作总执行次数为0+1+2+n-1=n*(n-1)/2。算法时间复杂度只需要考虑高次项，可以忽略低次项，算法的时间复杂度为O(n2)。空间效率：上述程序段未涉及临时开辟的存储空间，因此空间复杂度为O(1)。第二章第二章
21、 线性表线性表申燕萍 2014年 2月 7日本章要点本章要点线性表的逻辑定义与结构特点。线性表的顺序存储结构和链式存储结构。顺序表上各基本操作的实现及时间复杂度的分析。链表上各基本操作的实现及时间复杂度分析。“学生成绩信息表学生成绩信息表”引例：引例：学生成绩信息表可以用来存储各班学生的基本信息以及相关科目的成绩情况。在此基础上实现对各班某个学生的各科成绩的查询，以及添加或删除一些学生的成绩信息。思考：思考：1.如何添加和删除学生成绩信息更方便，操作效率更高？2.如何存储更节省存储空间呢？2.1 2.1“学生成绩信息表学生成绩信息表”案例导入案例导入学生成绩信息表中每位学生信息是一个数据元素，
22、构成一个结点。由学号、姓名、性别、出生年月、数学、语文、英语成绩7个数据项组成。如图2-1所示。图2-1学生成绩信息表图2-1中结点之间连线表示两个结点间一对一的相邻关系。第一个结点（20120401，王伟，男，1993/01，123，98，90）无直接前驱，但有一个直接后继。最后一个结点（20120405，李彩霞，女，1993/05，102，113，90）有一个直接前驱，但无直接后继。中间每个结点都有一个直接前驱和一个直接后继。学生成绩信息表是典型的线性表。又如一个星期中的七天可放在一个线性表中：（星期一，星期二，星期三，星期四，星期五，星期六，星期日）这也是线性表的具体实例。线性表中的数据
23、元素无论是单一的数值还是具有结构的记录，它可以是各种类型，但同一表中的数据元素的类同一表中的数据元素的类型必定是相同的型必定是相同的。表中的一个数据元素可以由若干个数据项组成，也可以只由一个数据项组成。由若干数据项组成的数据元素又可称为记录记录或结点结点。线性表中数据元素之间具有一对一一对一的关系。即在数据元素的非空有限集合中，除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱；除最后一个数据元素之外，集合中的每一个数据元素都只有一个后继。分析上述两个例子，可以得出如下结论：分析上述两个例子，可以得出如下结论：数据的逻辑结构分为线性结构线性结构和非线性结构非线性结构两种。线性结构是最简
24、单的数据结构，也是十分重要的一种数据结构。因为它的应用最为广泛，同时也是学习和研究其他更为复杂的层次结构和网状结构的基础。其中线性表线性表是最简单也最常用的一种线性结构。2.2 2.2 线性表的定义及基本操作线性表的定义及基本操作线性表是由n(n0)个相同类型的数据元素组成的有序集合。通常记为L（a1，a2，ai-1,ai,ai+1,，an）。其中L为线性表名称，习惯用大写书写；a1称为起始结点起始结点，an 称为终端结点终端结点，ai为组成该线性表的数据元素，习惯用小写书写；i称为数据元素在线性表中的序号或位置。对于相邻一组关系,ai称为ai+1的前驱结点，而ai+1称为ai的后继结点。2.
25、2.1 2.2.1 线性表的定义线性表的定义表中数据元素的个数n（n0）称为线性表的长度长度。例如26个英文字母表是一个长度为26的线性表。当n=0 时，表中无元素，称为空表空表，简记为。可以表示刚开始建表尚无数据的情况，或者表中元素全部被删除的情形。线性表中每个数据元素都有一个确定的位置，这取决于它的序号。线性表：（a1,a2,a3,，an-1,an）序号：1 2 3 n-1 na1是第一个数据元素，an是最后一个数据元素。除第一个和最后一个元素以外，表中任一元素ai存在唯一的直接前驱元素ai-1和唯一的直接后继元素ai+1。线性表的特征为数据元素之间具有一对一的线性关系。归纳起来有两个要点
26、。要点要点1 1：线性表的逻辑结构可形式化表示成(D，R)，其中D=a1,a2,an,R=,，。要点要点2 2：ai为序号为i的数据元素（i=1,2,n），通常我们将它的数据类型抽象为DataType，DataType根据具体问题而定，如在学生成绩信息表中，它是用户自定义的学生结构体类型。在字符串中，它是字符型。下面给出线性表基本运算及功能描述。1InitList（L）线性表初始化操作函数。2LengthList（L）求线性表的长度。3GetList（L,i)取表中位置i处的元素。4LocateList（L,x）按值查找函数，也称定位操作。5InsertList(L,i，x)插入操作。6Del
27、ete(L,i)删除操作。7Empty(L)判空表函数。8Clear(L)表置空操作。2.2.2 2.2.2 线性表的基本操作线性表的基本操作应用上述基本运算可以实现线性表的其他运算，如将两个线性表合并，线性表逆置等。数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。对于不同的存储结构，这些基本运算的实现细节不同。下面我们将详细阐述线性表的顺序存储顺序存储和链式存储链式存储，以及在这两种存储方式下实现基本运算的算法。线性表的实现主要要解决以下两个方面的问题：选择怎样的形式来存储。用怎样的函数来实现线性表的
28、基本操作。线性表的顺序存储是实际应用中最简单、最常用的一种存储方式。顺序存储结构的线性表简称为顺序表顺序表。一般使用数组来表示顺序表。2.3 2.3 顺序表顺序表线性表顺序存储的方法是：将线性表的各元素依次存放在计算机内存中一组地址连续的存储单元中。数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。顺序表结构示意图如图2-2所示。图2-2 线性表的顺序存储结构示意图2.3.1 2.3.1 线性表的顺序存储结构线性表的顺序存储结构线性表顺序存储的特点是：表中相邻的元素ai 和 ai+1 所对应的存储地址 LOC(ai)和地址LOC(ai+1)也是
29、相邻的。也就是说表中元素的物理关系和逻辑关系是一致的物理关系和逻辑关系是一致的。我们将线性表的第一个元素记为a1,线性表的起始地址记为LOC(a1)，LOC(a1)又称为线性表的基地址。由于同一线性表中元素的类型相同，可假定每个元素占用b个存储单元，那么表中任意一个元素的存储起始地址可用公式得到：LOC(ai)=LOC(a1)+(i-1)b(1in)。【例2-1】已知顺序表L的起始地址为 1000,每个数据元素占4个字节，求数据元素a4的起始地址。分析：由公式loc(a4)=loca(a1)+(4-1)*4=1012，因此数据元素a4的起始地址是1012。说明：可以看出在访问线性表时，利用上述
30、给出的数学公式，可以快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所需花费的时间都相等。因而我们将这种存取元素的方法称为是一种随随机存取的存储结构机存取的存储结构。基于这种存储结构的线性表很容易实现读取或查找表中的某个元素的操作。具体实现时我们将存放顺序表数据元素的数组和顺序表长度进行封装，构成的通用顺序表数据类型描述如下：#define DataType int#define MAXSIZE 100typedef struct DataType dataMAXSIZE;int last;SeqList;在实际应用中首先需要定义顺序表变量：SeqList L
31、;则L的表长为L.last+1。表中元素分别存放在L.data0L.dataL.last中。也可以定义一个指向SeqList类型的指针变量：SeqList*L;则L的表长为L-last+1。存储空间为L-data0L-dataL-last。在C语言中习惯用Lmalloc(sizeof(SeqList)获得顺序表的初始存储空间，从而对线性表进行初始化。注意：注意：在本章的算法介绍中，存放线性表的数组元素下标从0开始，而顺序表元素的位置序号从1开始，因此在算法设计过程中需注意顺序表的“第i个数据元素”存放在数组下标为“i-1”的位置。2.3.2 2.3.2 顺序表基本操作的实现顺序表基本操作的实现
32、1顺序表的初始化 算法功能：构造一个空的线性表,初始化成功返回1。算法要点：掌握C语言中malloc函数的使用。【算法2.1】顺序表初始化 int InitList_SeqList(SeqList*L)L-last=-1;/长度为0 if(!(L=(SeqList*)malloc(sizeof(SeqList)exit(0);return 1;【算法分析】初始化操作就是生成一个空的顺序表L，函数中传递的是地址值。本算法的时间复杂度为O(1)。2求表长度的操作【算法2.2】顺序表表长 int LengthList_SeqList(SeqList*L)return(L-last+1);算法时间复杂
33、度为O(1)。3读取元素操作【算法2.3】读取元素值DataType GetList_SeqList(SeqList*L,int i)if(iLengthList_SeqList(L)return(NULL);else return(L-datai-1算法时间复杂度为O(1)。4顺序表定位操作【算法2.4】按值查找LocateList_SeqList(SeqList*L,DataType x)int i=0;while(idatai!=x)i+;if(ilast+1)的位置上 int j;if(iL-last+2|L-last=MAXSIZE-1)return 0;else for(j=L-l
34、ast;j=i-1;j-)L-dataj+1=L-dataj;L-datai-1=x;L-last=L-last+1;return 1;【算法分析】设表长L-last+1为n，顺序表上的插入运算时间主要消耗在数据向后移动的过程中。在第i个位置上插入x,从ai到an都要向后移动一个位置，执行元素后移的次数是n-i+1。可以看到移动元素的次数不仅和表长有关，而且还与插入元素的位置i有关。当i=n+1时，无须移动元素，当i=1时，则元素后移将执行n次，也就是说该算法在最好情况下时间复杂度是O(1)，最坏情况下时间复杂度是O(n)。进一步分析算法的平均性能：Eins=Pi(n-i+1)，在等概率的情况
35、下Pi=1/(n+1)，因此Eins=(n-i+1)/(n+1)=n/2。故在顺序表上做插入操作，平均要移动表的一半元素。就数量级而言，它是线性阶的，算法的平均时间复杂度为O O（n n）。6顺序表上元素的删除删除算法的示意图见图2-4所示。图2-4 顺序表的删除操作【算法2.6】顺序表删除操作int Delete_SeqList(SeqList*L,int i)/在顺序表L中删除第i个元素 int j;if(i L-last+1)return 0;else for(j=i;j last;j+)L-dataj-1=L-dataj;L-last-;return 1;【算法分析】与插入运算相同，该
36、删除算法的基本操作是元素向前移动操作。删除第i个元素，执行元素向前移动的次数是n-i。当i=n 时，无须移动元素，当i=1时，须依次将后面的n-1个元素逐一向前移动一个位置。进一步分析算法的平均性能：考虑在长度为n的线性表中删除一个元素，令Edel为移动元素的平均次数，在表中第i个位置上删除一个元素要移动元素的次数为n-i，故Edel=Pi(n-i),在等概率的情况下Pi=1/n,因此 Edel=(n-i)/n=(n-1)/2故在顺序表上做删除操作，平均要移动表的一半左右的元素。就数量级而言，它是线性阶的，算法的平均时间复杂度为O（n）。7判断表空的操作【算法2.7】判表空int Empty(
37、SeqList*L)if(L-last=-1)return(1);else return(0);算法的时间复杂度为O(1)。调用顺序表基本操作的主函数详见教材2.3.3 2.3.3 顺序表的应用顺序表的应用 【例2-2】将所有在顺序表Lb中存在而在顺序表La中不存在的数据元素插入到表La中（假定La有足够的容量）。【例2-3】设有递增有序的两个顺序表A和B，编写一个算法将它们合并成一个顺序表C，要求C的元素也是递增有序的。【例2-4】将顺序表（a1,a2,a3,，an-1,an）划分为以a1为界的两部分，即a1前面的值均比它小，a1后面的值均比它大。设数据元素为整型。例如操作前顺序表为（30，
38、45，25，60，10，35，15），操作后顺序表为（25，20，15，30，45，60，35）2.3.4 2.3.4“学生成绩信息表学生成绩信息表”的顺序存储实现的顺序存储实现1.问题描述采用顺序存储的成绩信息表保存各班每位学生数学、语文、英语三门功课的成绩，并按学号递增有序，如果有新同学转入该班则需要向表中插入一条记录，有同学退学则需要删除一条记录，并保持表仍递增有序。2.算法思路此时顺序表中的数据元素的类型为结构体类型，因此首先要定义这个结构体类型，再定义顺序表类型。因为采用顺序存储时，需要预先估计元素个数的最大值，以确保空间够用。3.参考源程序 详见教材2.4 2.4 链表链表链式存储
39、的线性表称为链表链表。链表是用一组任意的存储单元来存放线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的。那么如何来反映数据元素之间的逻辑关系呢？指针指针是用来映射数据元素之间的逻辑关系的途径。常见的链表形式有单链表、循环链表和双向循环链表。其中最简单的是单链表。本节首先介绍用单链表结构实现线性表的基本运算，然后介绍循环链表和双向循环链表。2.4.1 2.4.1 单链表单链表链式存储结构中，对线性表的每一个数据元素，都需要用两部分来存储：一部分用于存放数据元素的值，称为数据域数据域；另外一部分用于存放该结点的直接前驱或直接后继结点的地址（指针），称为指针域指针域。这两部分组成了链表中
40、结点的结构。倘若链表中每个结点只有一个指向直接后继结点的指针，这样的链表称为单链表。单链表的结点结构如下图2-5所示。图2-5 结点结构其中，data是数据域，用来存放结点的值；next是指针域(又称链域)，用来存放结点的直接后继结点的地址。链表正是通过每个结点的链域将线性表中n个结点按其逻辑顺序链接在一起的。对于单链表，只要已知单链表第一个结点的地址（头指针），就能通过它依次查找到链表中的每一个结点。因此，可以用可以用头指针来标识一个单链表，头指针来标识一个单链表，通常简称为单链表L或或H等。例如：线性表L=(1,3,5,7,9)采用链式存储时，其物理结构如图2-6所示。图2-6 线性表(1
41、,3,5,7,9)的物理存储事实上，作为链式存储结构，我们关心的是结点之间的逻辑结构，而不是每个结点的实际存储地址，所以通常用如图2-7所示的图示结构来表示链式存储结构。图2-7 线性表(1,3,5,7,9)的链式存储示意图带头结点的单链表表示如图2-8所示。图2-8 单链表表示的线性表结点的数据类型定义如下：typedef struct node DataType data;struct node*next;LNode,*LinkList;在上述定义中，struct node表示链表的结点，通过typedef语句把struct node类型定义为LNode,把struct node指针类型定
42、义为LinkList。LinkList的实质是链表的头指针类型，如前文所述头指针可以用来唯一确定一条单链表，因此我们常用LinkList表示一个链表类型，定义指针变量为：LNode*p;或Linklist *L;说明：p为指向结点的指针，(*p)表示p指向的结点变量，数据域为p-data,指针域为p-next。若指针变量p的值为空（NULL），表示它不指向任何结点。这样的指针称为空指针。L指向一个链表的首地址，若L的值为空，表示指向空链表。链表的操作相当灵活，它的特点是以“指针”指示数据元素之间的逻辑关系，因此链表的存储单元既可以连续也可以不连续，逻辑上相邻的数据元素在物理位置上不一定相邻。基
43、于这样的特点，在链表中插入或删除元素不需要移动大量的数据元素，只要修改指针就可以了。但是，链表中的结点除了需存储数据本身外还要有存放结点地址的链域，相对增加了空间开销2.4.2 单链单链表上的基本操作表上的基本操作1、初始化【算法2.11】单链表初始化LinkList Init_LinkList()/初始化一个空的单链表 LinkList head;head=(LNode*)malloc(sizeof(LNode);head-next=NULL;return head;此算法的时间复杂度为O(1)。2.建立单链表（1）头插入法建立单链表【算法2.12】头插入法建立单链表LinkList HCr
44、eat_LinkList()LinkList head=Init_LinkList();LNode*p;char x;while(x=getchar()!=n)p=(LNode*)malloc(sizeof(LNode);p-data=x;p-next=head-next head-next=p;return head;说明：头插入法建立单链表算法简单，但生成的链表中结点的次序和读入的数据元素的顺序相反。若希望二者顺序一致，可采用下面介绍的尾插入法建表算法。图2-9 头插入法建立单链表（2）尾插入法建立单链表【算法2.13】尾插入法建立单链表LinkList RCreat_LinkList()
45、LinkList head=NULL;LNode*p,*r=NULL;char x;p=(LNode*)malloc(sizeof(LNode);head=p;r=p;p-next=NULL;while(x=getchar()!=n)p=(LNode*)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;if(r!=NULL)r-next=NULL;return head;以上二个算法的时间复杂度均为O(n)。图2-10 尾插入法建立单链表3.查找运算（1）按序号查找【算法2.14】单链表按序号查找LNode*Get_LinkList(LinkList L,i
46、nt i)LNode*p=L;int j=0;while(p-next!=NULL&jnext;j+;if(j=i)return p;else return NULL;算法时间复杂度为O(n)。函数返回值为第i个元素的位置，若要读取第i个元素的值，只要将查找成功时的返回值改为p-data就可以了。（2）按值查找（定位操作）【算法2.15】单链表按值查找（定位）操作LNode*Locate_LinkList(LinkList L,DataType x)LNode*p=L-next;while(p!=NULL&p-data!=x)p=p-next;return p;算法时间复杂度为O(n)。4.判
47、表空的操作【算法2.16】判表空 int Empty(LinkList head)if(head-next=NULL)return 1;else return 0;算法的时间复杂度为O(1)。5.插入运算（1）在已知结点的后面插入一新结点相应的操作命令如下：s-next=p-next;/对应图中的 p-next=s;/对应图中的【注意】和的次序不能颠倒。图2-11已知结点的后面插入一新结点（2）在已知结点之前插入一个新结点 图2-12已知结点的前面插入一新结点相应的操作命令如下：q=L;while(q-next!=p)q=q-next;/寻找p的前驱结点q s-next=q-next;q-ne
48、xt=s;（3）在单链表的第i个位置上插入值为x的元素【算法2.17】单链表第i个位置上插入xint Insert_linklist(LinkList L,int i,DataType x)LNode*p,*s;p=Get_LinkList(L,i-1);/寻找位置i-1 if(p=NULL)printf(参数错);return 0;else s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;return 1;该算法的时间复杂度为O(n)。6.删除运算（1）删除已知结点的后继结点 相应的操作命令如下：s=p-next;
49、/对应图中的 p-next=s-next;/对应图中的 free(s);【注意】,次序不能颠倒。图2-13删除已知结点的后继结点（2）删除单链表L中第i个元素【算法2.18】删除单链表L中第i个元素int Del_LinkList(LinkList L,int i)LNode *p,*q;if(!Empty(L)p=Get_LinkList(L,i-1);if(p=NULL)return-1;else if(p-next=NULL)return 0;else q=p-next;p-next=q-next;free(q);return 1;该算法的基本操作是查找第i个结点，时间复杂性为O(n)。
50、7.求表长度的操作【算法2.19】求表长int Length_LinkList(LinkList head)int i;LNode*p;p=head;i=0;while(p-next!=NULL)p=p-next;i+;return i;该算法遍历单链表中的所有结点，遇到一个结点就累加，最后将结点总数返回。算法的时间复杂度为O(n)。8.单链表的输出【算法2.20】单链表的输出void Print(LinkList head)LNode *p;p=head-next;while(p)printf(%c,p-data);p=p-next;该算法是将单链表中存储的所有数据元素打印输出的过程。算法的