数据结构Python 语言描述全套教学课件

数据结构[Python语言描述]全套可编辑PPT课件第1章绪论第2章线性表第3章栈和队列第4章串目录第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第1章绪论绪

论本章导读早期的计算机主要用于数值计算，到20世纪中叶后，逐渐扩展到对非数值的计算，它所处理的对象越来越多，包括图像、视频、表格等具有一定结构的数据。如何合理地组织这些数据，并对它们进行高效的处理，就是“数据结构”主要研究的内容。本章首先介绍数据结构的基本概念和术语，然后介绍数据的逻辑结构和存储结构，接着介绍抽象数据类型的概念，最后介绍算法和算法分析的相关知识。

第1章绪

论知识目标

第1章 熟悉数据结构的基本概念和术语。 理解数据的逻辑结构、存储结构和抽象数据类型等概念。 了解算法的定义、特性、描述方法和设计要求。 了解算法性能评价的重要指标。绪

论技能目标

第1章 能针对实际问题设计出较高质量的算法，并使用多种方法进行描述。 能分析简单算法的时间复杂度和空间复杂度。绪

论素质目标

第1章 学习楷模事迹，汲取开拓创新、无私奉献的榜样力量。 通过对算法的改进，培养科学严谨、精益求精的工匠精神。Content第1章逻辑结构和存储结构基本概念和术语抽象数据类型算法和算法分析1.1基本概念和术语第1章数据分析入门1.1基本概念和术语1．数据数据（data）是客观事物的符号表示，在计算机科学中，是指所有能被计算机程序识别、存储、加工和处理的符号的总称，它是计算机程序加工的“原料”。对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。例如，一个利用数值分析方法求解代数方程的程序，其处理的整数和实数都是数据；一个编译程序或文字处理程序，其处理的字符串也是数据。2．数据元素数据元素（dataelement）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素又称为元素或记录，如表1-1（详见教材）所示的学生基本信息表中，每个学生的信息就是一个数据元素。为便于理解数据结构中基本概念和术语的含义，下面以表1-1中的数据为例，进一步描述数据元素、数据项及数据对象之间的关系，如下图所示。高手点拨1.1基本概念和术语1.1基本概念和术语3．数据项数据项（dataitem）是组成数据元素的、有独立含义的、不可再分的最小单位，如学生基本信息表中的学号、姓名等。4．数据对象数据对象（dataobject）是性质相同的有限个数据元素的集合，是数据的一个子集。例如，集合N={2,4,6,8,10}是整数的一个数据对象，集合C={'a','b','c','d','e'}是小写字母的一个数据对象。5．数据结构数据结构（datastructure）是相互之间存在一种或多种关系的数据元素的集合。结构就是指数据元素之间的相互关系，因此，可以将数据结构看作带结构的数据元素的集合，如下图所示。1.2逻辑结构和存储结构第1章数据分析入门1.2逻辑结构和存储结构数据的逻辑结构是指数据元素之间逻辑关系的描述，它与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。根据数据元素之间关系的不同，可分为4种不同的逻辑结构，如下图所示。1.2.1逻辑结构1.2逻辑结构和存储结构（1）集合结构的数据元素之间只有属于同一个集合的关系。例如，判断一个数字是否为整数，可以将所有整数看作一个集合结构。（2）线性结构的数据元素之间是一对一的关系。此时每个数据元素都有唯一的前驱元素（第一个元素除外）和唯一的后继元素（最后一个元素除外）。例如，由多节车厢组成的列车、排队买票人员、一叠盘子等都可以看作线性结构。（3）树形结构的数据元素之间是一对多的关系。例如，学校的组织结构、家族关系等都可以看作树形结构。（4）图形结构（也称网状结构）的数据元素之间是多对多的关系。此时每个数据元素都可以有多个前驱元素或后继元素。例如，城市公共交通网、计算机网络等都可以看作图形结构。1.2逻辑结构和存储结构数据的存储结构（也称物理结构）是指数据元素在计算机中的存储表示，是逻辑结构在计算机中的实现。将数据元素存储到计算机时，通常既要存储各数据元素的数据项，又要存储数据元素之间的逻辑关系。根据数据元素之间的逻辑关系在计算机中的不同表示，可分为两种不同的存储结构，分别是顺序存储结构和链式存储结构。1.2.2存储结构1.2逻辑结构和存储结构1．顺序存储结构顺序存储结构是指逻辑上相邻的数据元素，其物理位置（内存中的位置）也相邻，数据元素间的逻辑关系由存储单元的邻接关系体现。顺序存储结构是一种最基本的存储方法，通常借助程序设计语言中的数组来实现。假设表1-1中每个学生的基本信息在内存中占用10个字节的存储单元，当数据元素从1000号存储单元开始由低地址向高地址方向依次存储时，对应的顺序存储结构如下图所示。1.2逻辑结构和存储结构2．链式存储结构链式存储结构是指在计算机中用一组任意的存储单元存储数据元素，然后再通过地址链接的形式将全部数据元素组织到一起。这组任意的存储单元既可以是连续的，也可以是不连续的。链式存储结构通常借助程序设计语言中的指针来实现，表1-1中学生基本信息的链式存储结构如下图所示。由此可以看出，在这种存储结构中，逻辑上相邻的数据元素，其物理位置不一定相邻。1.3抽象数据类型第1章数据分析入门数据类型（datatype）是一组性质相同的值的集合和定义在该集合上的一组操作的总称，它最早出现在高级程序设计语言中用于描述操作对象的特性（如取值范围、允许执行的操作等）。例如，Python中的列表数据类型（list）没有长度限制，允许执行的操作有添加元素、删除元素、分片赋值和排序等。抽象数据类型（abstractdatatype，ADT）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即无论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。1.3抽象数据类型1.3抽象数据类型抽象数据类型和数据类型实质上可看作一个概念。例如，各个计算机都拥有的“整数”类型就是抽象数据类型，尽管它们在不同处理器上实现的方法不同，但由于其定义的数学特性相同，在用户看来它们都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一个最基本的原则，即通过封装和信息隐蔽，使对象操作的具体实现方法和外部引用相分离。抽象数据类型含义更广，不仅包括各种不同的计算机处理器中已定义并实现的数据类型（又称固有数据类型），还包括设计软件系统时用户自己定义的复杂数据类型，且所定义的数据类型的抽象层次越高，含有该数据类型的软件复用程度就越高。高手点拨1.3抽象数据类型1.3抽象数据类型下面用三元组（D，S，P）来描述抽象数据类型。其中，D是数据对象，S是D上的关系集，P是对D的操作集，因此抽象数据类型的格式定义如下。ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义> }ADT抽象数据类型名1.4算法和算法分析第1章数据分析入门1.4算法和算法分析在计算机领域中，算法是指根据所要处理的问题，在数据的逻辑结构和存储结构基础上，利用有限的步骤解决这一特定问题所采用的一组有穷规则的集合。一个算法应该具有如下5个特性。1.4.1算法的定义和特性（1）有穷性。一个算法必须在有限步骤之内正常结束，不能形成无穷循环。（2）确定性。算法中的每一个步骤必须有确定含义，不能有二义性。（3）可行性。算法中的每一个步骤都可以通过已经实现的基本操作运算执行有限次来实现。（4）输入。一个算法可以有0个或多个输入。（5）输出。一个算法至少有一个或多个输出。1.4算法和算法分析高德纳·克努特被誉为现代计算机科学的鼻祖，他所著的描述基本算法与数据结构的经典著作《计算机程序设计艺术》在计算机史上的地位，堪比数学史上欧几里得所著的《几何学原理》。1973年，当这部书出版到第三卷时，已被认为是石破天惊的“神作”，高德纳·克努特也因此获得了图灵奖，而当时他才36岁。在算法方面，高德纳·克努特和他的学生共同设计了Knuth-Bendix算法和Knuth-Morris-Pratt算法，前者曾成功地解决了群论中的等式的证明问题；后者是在文本中查找字符串的简单而高效的算法。如今，高德纳·克努特已是白发苍苍的老人，这位旷世大师，用自己的才华定义了属于自己的时代。1.4算法和算法分析算法可以使用多种方法进行描述，如自然语言、流程图、伪代码和程序设计语言等，接下来分别对其进行介绍。1.4.2算法的描述方法1．自然语言使用自然语言（如汉语、英语等）描述算法的优点是简单直观且便于阅读，缺点是不够严谨，与计算机采用的程序设计语言相差很大，需要用z户自行进行转换。2．流程图流程图通过规定的图形符号（见表1-2）来描述算法。使用流程图描述算法的优点是直观、简洁、明了。3．伪代码伪代码通常用文字和符号来表示。使用伪代码描述算法的优点是忽略了程序设计语言的语法规则和描述细节，更易于用户理解。4．程序设计语言程序设计语言是用于编写计算机程序的语言。使用程序设计语言描述算法必须严格遵循所用语言的语法规则，编写的程序可直接在计算机上执行，但相对来说不易理解，有时须借助注释语句来提高程序的可读性。1.4算法和算法分析知识库流程图还包括一些特殊的图形符号，如注解符、文件符、显示符和人工输入符。其中，注解符用于标识注解内容，它不是程序流程图的必要部分，不反应流程和操作，只是为了对流程图中某些符号的操作进行必要的补充说明，以帮助读者更好地理解；文件符表示可阅读的数据，如打印输出、表格输入的数据等；显示符表示任意媒体显示的数据；人工输入符表示任意媒体以人工形式输入的数据，如通过键盘、开关装置、按钮、条形码输入器等输入的数据。1.4算法和算法分析1.4.3算法的设计要求（1）正确性。其中，“正确”的含义可以分为如下3个层次。①对于几组输入数据，能够得到满足要求的结果。②对于精心选择的典型、苛刻且带有刁难性的几组输入数据，能够得到满足要求的结果。③对于一切合法的输入数据，都能得到满足要求的结果。（2）可读性。算法主要是为了人们的阅读与交流，其次才是机器执行。因此，算法的表达应思路清晰，层次分明，易于理解，可读性强，以便于后续对算法的使用和修改。（3）健壮性。当输入数据非法时，算法也能做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。（4）高效率与低存储量。通俗地说，效率指的是算法的执行时间。对于同一个问题，若有多个算法可以解决，则执行时间越短的算法效率越高。存储量指的是算法执行过程中所需要的最大存储空间。1.4算法和算法分析要解决一个实际问题，通常可以有若干种算法，那么如何从这些算法中找出最有效的算法呢？或者对于一个解决实际问题的算法，如何来评价该算法的优劣呢？这就需要进行算法分析。算法分析是每个程序设计人员都应该掌握的技术。评价一个算法的优劣主要看执行这个算法所需的时间（时间复杂度）和存储空间（空间复杂度）。1.4.4算法分析1.4算法和算法分析1．算法的时间复杂度算法的时间复杂度（timecomplexity）是指算法的执行时间随问题规模的变化而变化的趋势，反映算法执行时间的长短，记作T(n)=O(f(n))。其中，n表示问题规模，是算法求解问题输入量的多少，也是问题大小的本质表示；T(n)表示语句的总执行次数（称为语句频度或时间频度）；f(n)是T(n)的同数量级函数，一般为问题规模n的某个函数。分析算法时间复杂度的步骤如下。（1）找出算法中语句频度最大的语句。（2）计算频度最大语句的频度与问题规模n的某个函数f(n)。（3）取f(n)数量级并用符号O表示。1.4算法和算法分析2．算法的空间复杂度一个程序在计算机上运行时，除了需要存储本身所用的指令、常数和输入数据以外，还需要一些对数据进行操作的辅助存储空间。因此，一个算法的空间复杂度（spacecomplexity）就是指程序运行所需的存储空间，记作S(n)=O(f(n))，该函数各参数的含义与时间复杂度相同，此处不再赘述。由于程序本身所用指令等所占存储空间与算法无关，因此，分析算法的空间复杂度时，只需分析算法在实现时所需要的辅助存储空间即可。同步训练将百分制成绩转换为五级制成绩【问题描述】通过键盘输入百分制成绩，设计算法将其转换为五级制成绩并输出。具体的百分制成绩占比及与五级制成绩的转换规则如表1-4（详见教材）所示。【问题分析】对于输入的百分制成绩，只需利用条件语句依次进行判断，然后根据表1-4进行转换即可。第一种算法可以根据分数从低到高依次进行判断，其流程图如下图所示。使用算法一时，70分以上的成绩（总占比80%）须进行3次或3次以上的判断才能得出结果。那么，怎样才能减少判断次数，从而提高效率呢？同步训练将百分制成绩转换为五级制成绩同步训练将百分制成绩转换为五级制成绩为此，可以将百分制成绩范围按照占比大小排序，并将具有较大占比的成绩范围排在前面，分别将输入的成绩与之进行比较。这样，大部分的成绩经过较少的比较次数就能得出其对应的等级，从而提高了效率。因此，可以将算法一进行改进得到算法二，其流程图如下图所示。同步训练将百分制成绩转换为五级制成绩【代码实现】根据算法二，写出Python源程序。var=6foriinrange(var):score=int(input('请输入成绩：'))ifscore>100orscore<0:print('输入有误。')exit()else:if70<=score<80:同步训练将百分制成绩转换为五级制成绩print('输入成绩的等级为C。'+'祝贺你通过考试！')elif80<=score<90:print('输入成绩的等级为B。'+'祝贺你通过考试！')elif60<=score<70:print('输入成绩的等级为D。'+'祝贺你通过考试！')elifscore>=90:print('输入成绩的等级为A。'+'祝贺你通过考试！')else:print('输入成绩的等级为E。'+'加油！')同步训练将百分制成绩转换为五级制成绩【程序测试】程序运行结果如下图所示。谢谢观赏第2章线性表线性表本章导读线性表是最简单、最常用的数据结构，可以将其简单理解为“线性结构的表”。本章首先介绍线性表的定义及基本操作，然后介绍线性表的顺序和链式两种存储结构及其基本操作的实现。

第2章线性表知识目标

第2章 理解线性表的定义和特点。 掌握线性表的基本操作。 掌握顺序表的存储结构及其基本操作的实现。 掌握单链表和双链表的结构特点及其基本操作的实现。 理解循环链表的特点。线性表技能目标

第2章 能根据线性表数据的特点选择合适的存储结构。 能使用线性表解决实际问题。线性表素质目标

第2章 增强主动思考、积极寻求问题解决方法的意识。 通过了解“二十四节气”的起源，坚定文化自信。Content第2章线性表的顺序存储线性表概述线性表的链式存储2.1线性表概述第2章线性表2.1线性表概述“春雨惊春清谷天，夏满芒夏暑相连。秋处露秋寒霜降，冬雪雪冬小大寒。”这首仅28个字的“二十四节气歌”蕴含了中华民族千百年来的智慧浓缩。2016年，“二十四节气”入选联合国教科文组织非物质文化遗产名录。在国际气象界，这一已有千年历史的时间认知体系被誉为“中国第五大发明”。“二十四节气”是中国人通过观察太阳周年运动，认知一年中时令、气候、物候等方面变化规律所形成的知识体系和社会实践。2.1线性表概述中国古人将太阳周年运动轨迹划分为24等份，每一等份为一个“节气”，统称“二十四节气”，具体包括立春、雨水、惊蛰、春分、清明、谷雨、立夏、小满、芒种、夏至、小暑、大暑、立秋、处暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒。“二十四节气”指导着传统农业生产和日常生活，是中国传统历法体系及其相关实践活动的重要组成部分，深刻影响着人们的思维方式和行为准则，是中华民族文化认同的重要载体。2.1线性表概述2.1.1线性表的定义和特点线性表是由n（n≥0）个特性相同的数据元素组成的有限序列，数据元素之间是一对一的关系。线性表可以表示为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，其逻辑结构如下图所示。由该图可以看出，线性表中的每个数据元素都有一个确定的位置，a0为首元素，ai为第i（0＜i＜n-1）个元素，an-1为尾元素。通常情况下，用线性表中数据元素的个数n表示线性表的长度。当n=0时，线性表为空表。2.1.2线性表的基本操作线性表基本操作的定义如表2-1所示。2.1线性表概述基本操作说明__init__()初始化线性表，即构造一个空的线性表createList()创建线性表，即构造一个非空的线性表getLength()线性表已存在的前提下，返回表的长度，即表中数据元素的个数insert(i,e)线性表已存在的前提下，在表中第i（0≤i≤getLength()）个位置之前插入新的数据元素e，表长加1delete(i)线性表已存在且非空的前提下，删除表中第i（0≤i≤getLength()-1）个数据元素，表长减1locate(e)线性表已存在的前提下，返回第一个与数据元素e相等的数据元素在线性表中的位置getElem(i)线性表已存在的前提下，返回表中第i（0≤i≤getLength()-1）个数据元素的值traversal()线性表已存在的前提下，对表进行遍历，在遍历过程中对表的每个数据元素均访问一次clearList()线性表已存在的前提下，将其置为空表setElem(i,e)线性表已存在的前提下，将表中第i（0≤i≤getLength()-1）个数据元素的值设置为elistEmpty()线性表已存在的前提下，判断表是否为空表2-1线性表基本操作的定义2.2线性表的顺序存储——顺序表第2章线性表2.2线性表的顺序存储——顺序表假设顺序表中有n（n≥0）个数据元素，每个数据元素占用k个存储单元，且以顺序表中第一个数据元素的存储地址Loc(a0)作为顺序表的起始地址或基地址（用d表示），则可以得到顺序表中第i个数据元素ai的存储地址为

Loc(ai)=d+i×k（0≤i≤n-1）相邻两个数据元素ai和ai＋1的存储地址之间的关系为

Loc(ai＋1)=Loc(ai)+k（0≤i＜n-1）因此，顺序表的存储结构如下图所示。2.2.1顺序表的存储结构2.2线性表的顺序存储——顺序表由右图可以看出，在顺序表中，逻辑结构相邻的数据元素在物理存储单元中也是相邻的。只要确定顺序表的起始地址（基地址）和表中每个数据元素所占存储单元的大小，就可以计算出顺序表中任意一个数据元素的存储地址。也就是说，顺序表中任一数据元素都是可以随机存取的，这种存取元素的方法称为随机存取法。因此，线性表的顺序存储结构是一种随机存取的存储结构。2.2线性表的顺序存储——顺序表2.2.2顺序表中基本操作的实现1．初始化顺序表初始化顺序表是为顺序表动态分配存储空间，并将其长度设置为0，其具体步骤如下。（1）设置顺序表的最大容量。（2）设置顺序表的存储空间。（3）将顺序表的长度设置为0。2.2线性表的顺序存储——顺序表2．在顺序表中插入数据元素顺序表的插入操作是指在长度为n的顺序表的第i（0≤i≤n）个位置之前插入一个数据元素e。例如，顺序表为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，插入数据元素e后为(a0,a1,…,ai－1,e,ai,ai＋1,…,an-1)。此时，顺序表的长度变为n+1，如下图所示。2.2线性表的顺序存储——顺序表由上图可以看出，当在第i（0≤i≤n）个位置插入一个数据元素时，须从最后一个数据元素（an-1）开始到第i个数据元素（ai）结束，依次向后移动一个位置。当i=0时，表示在表头插入；当i=n时，表示在表尾插入，此时无须移动其他数据元素。因此，在顺序表中插入数据元素的具体步骤如下。（1）判断顺序表的存储空间是否已满，若已满，则抛出异常。（2）判断插入数据元素的位置i是否满足条件0≤i≤n，若不满足，则抛出异常。（3）将插入位置及其之后的所有数据元素依次向后移动一个位置，空出存放新数据元素的位置。（4）将新的数据元素插入到第i个位置。（5）顺序表的表长加1。2.2线性表的顺序存储——顺序表definsert(self,i,e):ifself.length==self.max: #如果表长等于最大容量，抛出异常

raiseException('顺序表已满，无法插入数据！')ifi<0ori>self.length: #如果插入位置不合理，抛出异常

raiseException('插入位置不合理！')forjinrange(self.length,i-1,-1): #移动数据元素

self.data[j]=self.data[j-1]self.data[i]=e #插入数据元素

self.length+=1 #表长加1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表提示最坏时间复杂度是算法在最坏情况下的时间复杂度，表示算法的计算量可能达到的最大值。最好时间复杂度是算法在最好情况下的时间复杂度，表示算法的计算量可能达到的最小值。平均时间复杂度是算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值，一般用于表示该算法的时间复杂度。2.2线性表的顺序存储——顺序表3．在顺序表中删除数据元素顺序表的删除操作是指将顺序表中第i（0≤i≤n-1）个数据元素从顺序表中删除。例如，顺序表为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，删除数据元素ai后为(a0,a1,…,ai－1,ai＋1,…,an-1)。此时，顺序表的长度变为n-1，如下图所示。2.2线性表的顺序存储——顺序表由上图可以看出，删除顺序表中第i（0≤i≤n-1）个数据元素，须从第i+1个数据元素（ai＋1）开始到第n-1个数据元素（an-1）结束，依次向前移动一个位置。当i=0时，表示删除表头的数据元素；当i=n-1时，表示删除表尾的数据元素，此时无须移动其他数据元素。因此，在顺序表中删除数据元素的具体步骤如下。（1）判断删除数据元素的位置i是否满足条件0≤i≤n-1，若不满足，则抛出异常。（2）将第i个数据元素之后的数据元素都向前移动一个位置。（3）顺序表的表长减1。2.2线性表的顺序存储——顺序表defdelete(self,i):ifi<0ori>self.length-1:#如果删除位置不合理，抛出异常

raiseException('删除位置不合理！')forjinrange(i,self.length): #移动数据元素

self.data[j]=self.data[j+1]self.length-=1 #表长减1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表4．在顺序表中查找数据元素在顺序表中查找数据元素的过程是从第一个数据元素（a0）开始，依次将表中的数据元素与要查找的数据元素进行比较，若相等，则返回该数据元素在表中的位置；否则，查找失败，过程如下图所示。2.2线性表的顺序存储——顺序表在顺序表中查找数据元素的具体步骤如下。（1）从顺序表中第一个数据元素（a0）开始，依次和要查找的数据元素e比较，若找到与e相等的数据元素ai，则查找成功，并返回该数据元素的位置i。（2）若顺序表查找完成后依然没有找到数据元素e，则查找失败，返回-1。deflocate(self,e):foriinrange(self.length):ifself.data[i]==e:returnireturn-1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表5．在顺序表中取指定数据元素由于顺序表具有随机存取的特点，因此可以通过数据元素的下标直接获取数据元素，如下图所示。在顺序表中取指定数据元素的具体步骤如下。（1）判断指定的位置i是否满足条件0≤i≤n-1，若不满足，则返回-1。（2）若i满足条件，将直接返回第i个数据元素。2.2线性表的顺序存储——顺序表defgetElem(self,i):ifi<0ori>self.length-1:return-1returnself.data[i]【算法描述】【算法分析】该算法的时间复杂度为O(1)。2.2线性表的顺序存储——顺序表6．求顺序表的长度defgetLength(self):returnself.length【算法描述】【算法分析】该算法的时间复杂度为O(1)。求顺序表的长度就是返回顺序表中数据元素的个数。2.2线性表的顺序存储——顺序表7．遍历顺序表deftraversal(self):foriinrange(self.length):returnself.data[i]【算法描述】【算法分析】该算法的时间复杂度为O(n)。遍历顺序表就是依次访问顺序表中的各个数据元素。当线性表的长度变化不大，且易于事先确定其大小时，为了节省存储空间，应使用顺序存储结构。此外，若线性表的主要操作是查找数据元素，且很少插入或删除数据元素，也应使用顺序存储结构。高手点拨2.2线性表的顺序存储——顺序表同步训练利用顺序表存储学生成绩【问题描述】设计算法创建一个学生成绩表（其中每个学生的成绩信息包括学号、姓名、《语文》成绩、《数学》成绩、《英语》成绩、总成绩），实现学生成绩的录入、总成绩的计算，以及学生成绩的查询和删除。【问题分析】创建一个顺序表存储学生的成绩信息，首先输入学生人数确定要创建的顺序表长度，然后依次录入每个学生的成绩信息并提示“成绩录入成功！”，最后计算学生个人总成绩。查询学生的成绩信息时，首先输入要查询学生的学号，然后将顺序表中每个学生的学号与给定学号进行比较，若相等则提示“成绩查询成功！”并输出该学生的成绩信息，否则提示“无此学生！”。同步训练利用顺序表存储学生成绩删除学生的成绩信息时，首先输入要删除学生的学号，然后将顺序表中每个学生的学号与给定学号进行比较，若相等则删除该学生的成绩信息并提示“成绩删除成功！”，否则提示“无此学生！”。【代码实现】L=[]defadd(): #录入学生的成绩信息

j=eval(input('输入学生人数:'))foriinrange(0,j): #按输入的学生人数遍历顺序表

print('----输入第%d个学生的成绩信息----'%(i+1))sNumber=eval(input('学号：')) #定义学生学号同步训练利用顺序表存储学生成绩sName=input('姓名：') #定义学生姓名

chinese=eval(input('请输入《语文》成绩：'))

#定义《语文》成绩

math=eval(input('请输入《数学》成绩：'))

#定义《数学》成绩

english=eval(input('请输入《英语》成绩：'))

#定义《英语》成绩

dict1={} #定义一个字典存储学生的成绩信息

dict1['sNumber']=sNumber #存储学生学号

dict1['name']=sName #存储学生姓名

dict1['chinese']=chinese #存储《语文》成绩同步训练利用顺序表存储学生成绩dict1['math']=math #存储《数学》成绩

dict1['english']=english #存储《英语》成绩

dict1['sum']=(math+chinese+english)#存储总成绩

L.append(dict1) #将学生的成绩信息加入列表中

print('成绩录入成功！')defsearch(): #查询学生的成绩信息

num=eval(input('请输入要查询学生的学号：'))index1=-1fori,dictinenumerate(L): #将顺序表组成索引序列进行遍历

#如果顺序表中存储的学号与输入的学号相等

ifdict.get('sNumber')==num:

同步训练利用顺序表存储学生成绩index1=i #index1重新赋值

breakifindex1!=-1: #如果index1不等于-1，输出学生信息

print('成绩查询成功！')print('学号：%d，姓名：%s，《语文》成绩：%d，《数学》成绩：%d，《英语》成绩：%d，总成绩：%d'%(L[index1]['sNumber'],L[index1]['name'],L[index1]['chinese'],L[index1]['math'],L[index1]['english'],L[index1]['sum']))else:print('无此学生！')

同步训练利用顺序表存储学生成绩defdelete(): #删除学生的成绩信息

num=eval(input('请输入要删除学生的学号：'))index1=-1fori,dictinenumerate(L): #将顺序表组成索引序列进行遍历

#如果顺序表中存储的学号与输入的学号相等

ifdict.get('sNumber')==num:index1=i #index1重新赋值

breakifindex1!=-1: #如果index1不等于-1，删除学生的成绩信息

delL[index1]print('成绩删除成功！')同步训练利用顺序表存储学生成绩

else:print('无此学生！')defdisplay(): #显示学生的成绩信息

iflen(L)==0: #确认存储学生成绩信息的顺序表是否为空

print('无学生！')else:fordict1inL: #遍历存储学生信息的顺序表并输出学生的成绩信息

print('学号：%d，姓名：%s，《语文》成绩：%d，《数学》成绩：%d，《英语》成绩：%d，总成绩：%d'%(dict1['sNumber'],dict1['name'],dict1['chinese'],dict1['math'],dict1['english'],dict1['sum']))同步训练利用顺序表存储学生成绩defmain(): #定义main()函数并调用定义的方法

add() #调用add()函数录入学生的成绩信息

display() #调用display()函数显示学生的成绩信息

search() #调用search()函数查询学生的成绩信息

delete() #调用delete()函数删除学生的成绩信息

display() #调用display()函数显示学生的成绩信息

main() 同步训练利用顺序表存储学生成绩【程序测试】程序运行结果如右图所示。2.3线性表的链式存储——链表第2章线性表2.3线性表的链式存储——链表2.3.1单链表1．单链表的结构特点在线性表的链式存储结构中，为了表示每个元素与其后继元素之间的逻辑关系，除了需要存储元素本身的数据信息外，还要存储一个指示其后继元素地址的信息，这两部分信息共同构成了一个数据元素的存储结构，称为结点（node），如下图所示。2.3线性表的链式存储——链表其中，存储元素本身数据信息的部分称为数据域（data），存储其后继元素地址信息的部分称为指针域（next）。单链表（也称线性链表）是指将n个数据元素通过其对应结点的指针域按其逻辑关系链接成的链表，其中每个结点只包含一个数据域和一个指针域，一般形式如下图所示。其中，head称为头指针，用于指向单链表的第一个结点（也称首元结点）。由于单链表的最后一个结点没有后继元素，所以其指针域为“空”（None），用符号“^”表示。2.3线性表的链式存储——链表提示在Python中并不存在指针的概念，此处的指针属性实际上存放的是后继结点的引用，但为了表述方便仍然采用“指针”一词。为避免读者对首元结点、头结点和头指针的概念产生混淆，下面分别对其进行解释说明。（1）首元结点是指链表中存储第一个数据元素的结点。（2）头结点是在首元结点之前增加的一个结点，其指针域指向首元结点。增加头结点是为了便于处理首元结点，即对链表的首元结点的操作与其他结点相同，无须做特殊处理。（3）头指针是指向链表中第一个结点的指针。若单链表中增加了头结点，则头指针指向头结点；若单链表中没有增加头结点，则头指针指向首元结点。高手点拨2.3线性表的链式存储——链表2.3线性表的链式存储——链表2．单链表中基本操作的实现1）初始化单链表初始化单链表就是构造一个空表，如右图所示。classSLinkList:def__init__(self):self.head=Node(None)self.head.next=None【算法描述】2.3线性表的链式存储——链表2）建立单链表建立单链表是在一个空表中一次性创建多个结点。建立单链表的常用方法有头插法和尾插法两种，下面分别介绍。（1）头插法是通过将新结点逐个插入单链表中的头结点之后来建立单链表，具体过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，使用头插法建立单链表可分为如下6步。①建立只有头结点的空表。②生成第一个结点s。其中，新结点的数据域存储数据元素的数据信息，指针域为None。③将第一个结点插入头结点之后。④生成新结点s。⑤将新结点的指针指向第一个结点（s.next=head.next），然后将头结点的指针指向新结点s（head.next=s）。⑥重复步骤④和⑤，直到单链表生成完毕。2.3线性表的链式存储——链表defcreateList_head(self,a):self.head=Node(None) #生成头结点

foriinrange(len(a)):s=Node(a[i]) #生成一个新结点ss.next=self.head.next #修改新结点的指针域

self.head.next=s #将新结点s插入头结点之后【算法描述】2.3线性表的链式存储——链表提示上述算法中的语句s.next=head.next和head.next=s的顺序不能颠倒。若先执行语句head.next=s，再执行语句s.next=head.next，会找不到结点a0，此时相当于执行语句s.next=s，插入操作将出现错误。2.3线性表的链式存储——链表（2）尾插法是通过将新结点逐个插入单链表的尾部来建立单链表，具体过程如下图所示。由上图看出，使用尾插法建立单链表可分为如下3步。①建立只有头结点的空表，并增加指针t，使其指向头结点。②从线性表的第一个数据元素开始依次获取表中数据元素，并生成一个新结点s。其中，新结点的数据域存储数据元素的数据信息，指针域为None。③将新结点插入当前链表的表尾，并使指针t始终指向当前链表的尾结点。2.3线性表的链式存储——链表defcreateList_tail(self,a):self.head=Node(None) #生成头结点

t=self.head #创建一个尾指针t指向头结点

foriinrange(len(a)):s=Node(a[i]) #生成一个新结点ss.next=None #将新结点的指针域置为空

t.next=s #将新结点s插入尾结点t之后

t=s #尾指针t指向尾结点【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表3）在单链表中取指定结点的值若要在单链表中取指定结点的值，须从单链表的首元结点出发，然后顺着指针域向后依次访问各个结点，其具体步骤如下。（1）使用指针p指向首元结点，使用变量j做计时器并赋初值0。（2）从首元结点开始依次向后访问，只要当前结点的指针p不为空，且没有到达第i（0≤i≤n-1）个结点，就循环执行p指向下一个结点及j+1的操作。（3）退出循环后，判断指定结点的位置i是否满足条件0≤i≤n-1，若满足，则取值成功，此时j=i，即p所指的结点就是要取出的第i个结点，最后保存该结点的数据域。若不满足，则返回-1。2.3线性表的链式存储——链表deflistGetElem(self,i):p=self.head.next #p指向首元结点

j=0 #查找第i个结点并由p指向该结点

whilepisnotNoneandj<i:p=p.nextj+=1ifpisNoneorj>i: #判断指定结点的位置是否满足条件

return-1e=p.data #保存结点的数据域

returne【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表4）在单链表中插入结点单链表的插入操作是指在长度为n的单链表的第i（0≤i≤n）个位置插入一个值为e的结点，因此，须首先找到插入位置的前驱结点，然后修改该结点的指针域，具体过程如下图所示。当i=0时，表示在链表头部插入；当i=n时，表示在链表尾部插入。2.3线性表的链式存储——链表由上图可以看出，在单链表中插入结点可分为如下4步。（1）找到单链表的第i-1个结点，并增加一个指针p指向该结点。（2）生成一个新结点s，并设置其数据域为e。（3）使新结点s的指针域指向第i个结点。（4）修改第i-1个结点的指针域，使其指向新结点。deflistInsert(self,i,e):p=self.head #p指向头结点

j=-1 #查找第i-1个结点并由p指向该结点

whilepisnotNoneandj<i-1:【算法描述】2.3线性表的链式存储——链表p=p.nextj+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1s=Node(e) #生成新结点

s.next=p.next #修改指针域

p.next=s【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表5）在单链表中删除结点删除单链表中的结点与插入结点类似，也须首先找到删除结点的前驱结点，然后修改该结点的指针域，具体过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，在单链表中删除结点可分为如下两步。（1）找到单链表中ai的前驱结点，并增加一个指针p指向该结点。（2）修改ai的前驱结点的指针域，使其指向ai的后继结点。deflistDelete(self,i):p=self.head #p指向头结点

j=-1

#查找第i-1个结点并由p指向该结点【算法描述】2.3线性表的链式存储——链表whilepisnotNoneandj<i-1:p=p.nextj+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1p.next=p.next.next

#修改指针域【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表6）在单链表中查找结点要查找单链表中值为e的结点，需从单链表的首元结点开始，逐个将结点的值与e进行比较。当两者相等时，则当前指针指向的就是要查找的结点，其具体步骤如下。（1）使用指针p指向首元结点。（2）从首元结点开始顺着指针域依次向后查找，只要当前结点的指针p不为空，且p所指结点的数据域与要查找的值e不相等，就循环执行p指向下一个结点的操作。（3）查找成功后，返回p。2.3线性表的链式存储——链表deflistLocate(self,e):p=self.head.next #p指向首元结点

#查找值为e的结点并由p指向该结点

whilepisnotNoneandp.data!=e:p=p.nextreturnp【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表7）遍历单链表遍历单链表就是依次访问单链表中的各个结点，并输出各个结点的值。deftraversal(self):p=self.head.next #p指向首元结点

whilepisnotNone: #判断当前指针是否指向尾结点

print(p.data,end='')p=p.next【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表2.3.2双链表1．双链表的结构特点在单链表中，每个结点只设置了一个指针域用于指示该结点的后继结点。因此，从单链表的任意结点出发，都只能顺着指针方向向后查找其他结点。若要查找其前驱结点，必须从单链表的头结点出发，从前向后依次查找。为此，在单链表的每个结点中增加一个指向其前驱结点的指针域，这样的链表称为双链表。双链表中的每个结点有一个数据域（data）和两个指针域（prior和next），一个指针域（prior）指向该结点的前驱结点，另一个指针域（next）指向该结点的后继结点，如下图所示。2.3线性表的链式存储——链表双链表的一般形式如下图所示。在双链表中，假设每个结点为DNode类对象，则结点的定义如下。classDNode: #双链表结点类

def__init__(self,data): #构造方法

self.data=data #data属性

self.next=None #next属性

self.prior=None #prior属性2.3线性表的链式存储——链表2．双链表中基本操作的实现1）初始化双链表初始化双链表就是构造一个空表，如右图所示。classDLinkList:def__init__(self):self.head=DNode(None)self.head.next=None

self.head.prior=None【算法描述】2.3线性表的链式存储——链表2）在双链表中插入结点在长度为n的双链表的第i（0≤i≤n）个位置插入一个值为e的结点，首先需要找到第i-1个结点，然后修改4个指针属性，其实现过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，在双链表中插入结点可分为如下3步。（1）找到双链表的第i-1个结点，并增加一个指针p指向该结点。（2）生成一个新结点s，并令其数据域为e。（3）修改第i-1个结点、第i个结点和新结点s的next和prior属性（共4个指针属性）。defdlistInsert(self,i,e):p=self.head #p指向头结点

j=-1 #查找第i-1个结点，并由p指向该结点

whilepisnotNoneandj<i-1: p=p.next【算法描述】2.3线性表的链式存储——链表 j+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1s=DNode(e) #生成新结点

s.next=p.nextifp.next!=None: #判断p是否为尾结点

p.next.prior=ss.prior=pp.next=s【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表提示以上算法是在双链表中先找到第i-1个结点，然后在该结点之后插入新结点，还可以在双链表中先找到第i个结点，然后在该结点之前插入新结点。2.3线性表的链式存储——链表3）在双链表中删除结点删除长度为n的双链表的第i（0≤i≤n-1）个结点，首先需要找到该结点，然后修改其前驱结点和后继结点的指针属性，具体过程如下图所示。defdlistDelete(self,i):p=self.head #p指向头结点

j=-1 #查找第i个结点并由p指向该结点【算法描述】2.3线性表的链式存储——链表whilepisnotNoneandj<i:p=p.nextj+=1ifpisNoneorj>i: #判断删除的位置是否满足条件

return-1ifp.prior!=None: #不是第一个结点时执行的操作

p.prior.next=p.nextifp.next!=None: #不是最后一个结点时执行的操作

p.next.prior=p.prior【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表提示以上算法是在双链表中先找到第i个结点，然后通过其前驱结点和后继结点删除该结点，还可以在双链表中先找到第i1个结点，然后再删除其后继结点。2.3线性表的链式存储——链表2.3.3循环链表将链表中最后一个结点的指针域指向头结点，从而形成一个首尾相接的链表，这样的链表称为循环链表。在循环链表中，所有结点链接在环上，从循环链表中任一结点出发均可找到其他结点。循环链表又可以分为循环单链表和循环双链表。带头结点的循环单链表和循环双链表分别如下图所示。2.3线性表的链式存储——链表循环链表的操作与普通链表基本一致，不同的是，在循环链表中判断某个结点为尾结点的条件不是其后继结点为空，而是其后继结点为头结点。在循环单链表中，找到第一个结点a0只需要一步操作，即a0=head.next，其时间复杂度为O(1)；然而要找到最后一个结点an-1则要遍历整个链表，其时间复杂度为O(n)。为使操作简化，通常在循环单链表中设立尾指针rear，如下图所示。这样，当查找第一个结点和最后一个结点时，都只需一步操作就可以完成，即a0=rear.next.next，an-1=rear，其时间复杂度均为O(1)。当线性表的长度变化较大，难以事先确定其大小时，应使用链式存储结构。此外，若线性表的主要操作是插入或删除，也应使用链式存储结构。高手点拨2.3线性表的链式存储——链表同步训练利用单链表实现多项式相加【问题描述】已知有两个一元n阶多项式a(x)=a0+a1x+a2x2+a3x3+…+anxn和b(x)=b0+b1x+b2x2+b3x3+…+bnxn，设计算法求它们的和c(x)。【问题分析】多项式中的每一项由其系数和指数来确定，

如a2x2中的a2是系数，x2中的2是指数。多项式相加的规则是指数相同的项，指数不变，系数相加；指数不同的项，指数小的项在前，指数大的项在后，最后合并两项即可。由一元n阶多项式的表示形式可以看出，它由n+1个系数唯一确定。因此，为节省存储空间，通常采用链式存储结构来存储多项式。多项式中的每个系数非零项对应着链表中的一个结点，其存储结构如下图所示。同步训练利用单链表实现多项式相加其中，coef域用于存放多项式某一项的系数；index域用于存放该项的指数；next域用于存放指向下一个系数非零项结点的指针。【代码实现】'''结点为Node类对象，结点的定义'''classNode:def__init__(self,coef,index):self.coef=coef #多项式的系数

self.index=index #多项式的指数

self.next=None #指向后继元素的指针同步训练利用单链表实现多项式相加

'''单链表为polyLinkList类对象，单链表的定义'''classpolyLinkList():def__init__(self,items):self.head=Noneself.items=items #存放系数和指数的数组

foriteminself.items:coef,index=item[0],item[1]node=Node(coef,index)self.insertSort(node)同步训练利用单链表实现多项式相加 '''将结点插入单链表中，并按指数大小升序排列'''definsertSort(self,node): pre=Nonecur=self.head #指针cur指向头结点

whilecurisnotNoneandcur.index<=node.index:ifcur.index==node.index:cur.coef+=node.coefreturnpre=curcur=cur.next #移动指针cur同步训练利用单链表实现多项式相加node.next=curifpreisnotNone:pre.next=nodeelse:self.head=nodedefdisplay(self): #打印多项式

cur=self.headwhilecurisnotNone:ifcur.coef!=0:print('%d%s%d'%(cur.coef,'x^',cur.index),end='')cur=cur.next同步训练利用单链表实现多项式相加'''多项式相加类polynomialAdd的定义'''classpolynomialAdd:def__init__(self,p1,p2):self.p1=p1 #第一个多项式

self.p2=p2 #第二个多项式

self.sum=[] #存储两个多项式相加得到的系数和指数的数组

self.__polynomialAdd() #两个多项式相加

p3=polyLinkList(self.sum) #创建存储两个多项式的和同步训练利用单链表实现多项式相加

p3.display()

def__polynomialAdd(self):l1=self.p1.head #第一个多项式的表头

l2=self.p2.head #第二个多项式的表头

'''两个多项式都不为空时，将其合并'''whilel1isnotNoneandl2isnotNone:ifl1.index>l2.index:self.sum.append([l2.coef,l2.index])l2=l2.nextelifl1.index<l2.index:同步训练利用单链表实现多项式相加self.sum.append([l1.coef,l1.index])

l1=l1.nextelse:self.sum.append([l1.coef+l2.coef,l2.index])l1=l1.nextl2=l2.next '''如果第一个多项式为空，但第二个多项式不为空，则将第二个