数据结构-C语言版课件（全）

1、数据结构（C语言版）鄢田云12011级工程方向与应用方向“数据结构”课程体系实行A、B班教学A班教学：由鄢田云老师承担，数据结构课程在选课系统中是工程方向。周一1-2节，在1603教室；周三1-2节，在1207教室。B班教学：由李莉丽老师承担，数据结构课程在选课系统中是应用方向。周一1-2节，在1303 教室；周三1-2节，在1604教室。 仅数据结构和本学期后续的经典算法的设计与实现按此原则选课。其余的课程按实际的工程、应用方向选课。区别：A班更多自由支配时间，完成要求教学内容；B班很多限制支配时间，要额外增加难度。2课时安排数据结构总学时： 72（学时） = 56（理论学时）+ 12（上机

2、学时）+4（实验学时）行课安排时间:第 1 14 周，上机从第4周开始。经典算法的设计与实现总学时： 24（学时） = 12（上机学时）+ 12（实验学时）行课安排时间:第 8 17 周第8、11、12 章的内容为自学内容；目录中标有 * 的内容不作要求。课程性质：核心必修考试课，4.5+1.5=6学分。考试方式：闭卷考试，平时占30，考试占70。3上机安排时间上机时间安排：应用方向周三下午7-8节，6308；计工方向周三晚上9-10节（6:30-8:00）, 6308；时间从第4周开始到期末：包括数据结构经典算法的设计与实现经典算法的设计与实现的实验部分，需要大家课外花大量时间完成，不全在机

3、房上机。云计算机房6306正在测试中，后面有可能要在云计算机房上机。4成绩计算平时成绩：30% 考勤+课堂表现+作业+上机实验报告+上机考察考试成绩：70%要求：上机不能做与该课程无关的内容。5考核资格审查第三条 考核资格审查（成都信息工程学院普通全日制学生学习成绩考核办法，成信院发2006136号）1.每学期开设的必修、选修、加修课程都必须在期末停课复习前十天或课程教学工作结束前十天，由任课教师逐个审查学生的考核资格。审查结果送学生所属系，由主管教学的系主任终审，报教务处备案。2.学生的考核资格按下述原则审查： 学生有以下情况之一者，不能参加课程成绩考核，该课程的考核成绩以零分处理。在确定学

4、籍处理、授予学士学位时，该门课程以考核不及格门次参加统计。（1）全期旷课累计达该课程教学时数五分之一（含五分之一）以上者；（2）全期缺交该课程任课教师布置作业三分之一（含三分之一）以上者；或全期所交该课程作业，虽达到任课教师布置作业三分之二以上，但所交作业的准确度、整洁度有二分之一不合格者；（3）全期缺做该课程实习、实验或缺交实习、实验报告达三分之一（含三分之一）以上者；或全期参加该课程实习、实验，所交实习、实验报告都在三分之二以上，但有二分之一不合格者；（4）未经批准或未办理选课手续，擅自修读该门课程者。 3.到课率（出勤）、作业、实习、实验等环节全部完成并合格，则取得该课程的考核资格。 4

5、.经课程承担系主任终审，未取得某门课程考核资格的学生名单，于考核前一周由系办公室报教务处并通知学生本人。擅自参加考核者，以违反考场纪律论处。6纪律要求理论课和上机课：两者无故缺席累积超过5次，平时成绩为0 。无故缺勤或上机时间玩游戏等违纪行为：第1次平时成绩扣5分，第2次扣10分，第3次扣15分，第4次扣20分，第5次扣30分，第6次平时成绩为0。7教材与参考书教材：严蔚敏，数据结构，清华大学出版社参考书：李勤，数据结构，中国电力出版社Clifford A. Shaffer，数据结构与算法分析，电子工业出版社 Sartaj Sahni, 数据结构、算法与应用, 机械工业出版社严蔚敏，数据结构题

6、集，清华大学出版社8算法是计算机科学基础的重要主题 70年代前，计算机科学基础的主题没有被清楚地认识。 70年代，Knuth出版了The Art of Computer Programming(三卷）, 以各种算法研究为主线，确立了算法为计算机科学基础的重要主题，1974年获得图灵奖。 Knuth home page： :/knuth/ 70年代后，算法作为计算机科学的核心推动了计算机科学技术的飞速发展与牛顿的自然哲学的数学原理齐名 9计算机科学的体系 解决一个计算问题的过程：可计算否?能行可计算否?算法设计与分析用计算机语言实现算法软件系统定义 对于一个n元函数f(x1,.,xn)，如果存在

7、一个机械的实现过程使得对于任意赋值(a1,.,an)，该过程在有限的步骤内产生出f(a1,.,an)，那么就称f(x1,.,xn)是可计算的（或能行可计算的）。10计算机处理对象的发展数值计算问题与非数值计算问题解决一个具体问题，计算机来实现需要经过以下几个步骤： 具体问题 抽象 数学模型 设计 算法求解 编写程序 进行测试、调整至最终解答 程序=数据结构+算法11课程重要性简介是计算机相关专业考研的重点内容大公司笔试的主要内容 是计算机专业核心必修课，是其它后续计算机课程的重要基础是非计算机专业的主要选修课12 数据结构在学科中的地位 数据结构是计算机科学中一门综合性的专业基础课。数据结构的

8、研究不仅涉及计算机的硬件的研究范围，而且和计算机软件的研究有着更为密切的关系，无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。数据结构 所处的地位 13课程主要内容简介数据的逻辑结构数据的存储结构(顺序与链式)及其操作(算法)（插入、删除与遍历等）线性表、树和图查找与排序（属常用算法总结）算法的时空效率分析法14本课程章节主要内容 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：树和二叉树 第七章：图 第九章：查找 第十章：内部排序15第一章 绪 论 数据结构的引

9、论例1 图书馆的书目检索系统自动化问题 线形数据结构，1：1的关系 在书目自动检索系统中可以建立一张按登录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示： 什么是数据结构001002003004高等数学理论力学高等数学线形代数樊映川罗远祥华罗庚栾汝书S01L01S01S02书目卡片线性表16高等数学理论力学线形代数001,003, 002, 004, LS002,001, 003特点：计算机按某个特定的要求进行查询.处理对象之间存在一种简单的线形关系,这类模型可以称为简单的线形数据结构.按书名排列樊映川华罗庚栾汝书001,003,004,按作者排列按索引号排列1

10、7例2 计算机和人的对弈问题“树”形数据结构，1：N的关系 对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. *(a) 棋盘格式示例(b)井字棋对弈树的局部*树18例3 多叉路口交通灯的管理问题（ “图”形数据结构，M：N的关系 可以把这类交通,道路的问题当作一种给力的“图”的结构：一个顶点表示一条通道,而通道之间的矛盾的关系以两个顶点之间的连线表示.如下图所示:

11、AEDCB(a) 五叉路口ABACADBABCBDDADBDCEAEBECED程序=数据结构+算法图19结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构.数据结构: 数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.数据结构的发展简史（p3） 1968年美国唐欧克努特（ ）教授所著的计算机程序设计技巧第一卷基本算法中较系统地阐述了数据的逻辑结构和存储结构及其操作。不知道此人的程序员是不可原谅的 20 数据（Data) 客观事物的符号表示，能输入到计算机中并被计算机中程序处理的符号的总称。如文字、

12、声音和图像等。 数据元素 (Data element) 数据的基本单位，可由数据项组成。例如书目信息和棋盘格局。 数据项(data item)是数据不可分割的最小单位， 也称域(field)。数据对象 (Data Object) 性质相同的数据元素的集合，是数据的子集。例如整数。 基本概念21一个数据项一个数据元素学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004.整个表的记录是学生成绩数据22数据类型 是一个值的集合和定义在这个值集上一组操作总称。例如：int数据类型，取值范围为3276832767，操作运算有加、减

13、、乘、除、取模、乘方等。 数据类型分类：(按值的不同特性进行分类)原子类型 ：每一个对象仅由单值构成的类型； 值不可以分解；如：整型、字符型结构类型 ：每一个对象可由若干成分按某种 结构构成的类型。 值由若干成分按某种结构组成。 又分为固定聚合类型和可变聚合类型。 如：复数、数组数据类型 (Data Type)或抽象数据类型（ADT）23抽象数据类型（ADT）作用：抽象数据类型可以使我们更容易描述实际问题。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。 抽象数据类型与数据类型实质上是同一个概念。好处：可提高软件的复用程度。 使用它的人可以只关

14、心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。24抽象数据类型表示法：三元组表示：（D，S，P） 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型的定义格式：ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名见P9 例1-6 抽象数据类型三元组的定义。25抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注 1 ：它有些类似C语言中的结构（55）类型，但增加了相关的服务。注 2 ：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。好处：不拘泥于C语言细节，又能很

15、容易转换成C或C+语言程序。26抽象数据类型的语言的描述-P10预定义常量和类型 /函数结果状态代码 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 # define INFEASIBLE -1 # define OVERFLOW -2 typedef int Status; / Status是函数的类型，其值是函数结果状态代码 例如：P23 Status InitList_Sq(SqList &L) return OK;数据结构的表示用类型定义（typedef）描述，数据元素类型约定为ElemType，可以是C语

16、言中任何数据类型。27基本操作的算法用以下形式函数来描述函数类型函数名（函数参数表） / 算法说明 语句序列 /函数名 C语言中操作的描述（见P10-11） P12 例17赋值语句选择语句循环语句结束语句输入和输出语句注释基本函数逻辑运算约定28数据结构 (Data Structure) 相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构： （1）集合 （2）线形结构 （3）树形结构 （4）图状结构(网状结构） 集合线性树图29数据结构DS的形式定义： 数据结构是一个二元组： DS（D，S） 其中： D是数据元素的有限集 S是数据元素之间关系的有

17、限集 对于S中任意二元关系（x，yD），称x为第一元素（或y的前驱），y为第二元素（或x的后继）。 （ 注：DS Data Structure）30 数据元素之间的相互关系数据元素之间的相互关系包括三个方面：数据的逻辑结构、存储结构、操作集合。数据元素之间的逻辑关系，称为数据的逻辑结构。数据的逻辑结构分两大类： 线性结构（线性表、栈、队列、字符串、数组、广义表）； 非线性结构（树、二叉树、图）。 数据结构在计算机中的表示，称为数据的物理结构（存储结构）。位 (bit，计算机中表示信息的最小单位)元素或结点 (一个数据元素在计算机中的映象，如单字符数据元素由8位二进制数表示)数据域（数据项对应的

18、子位串，一个数据元素可以有若干数据项）31 数据元素之间的关系在计算机中的表示：有顺序映像和非顺序映像两种方法，由此得到两种存储结构：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构逻辑结构是面向用户的、是抽象的；存储结构是面向计算机的、面向实现的。32元素n元素i元素2元素1L0L0+m L0+(i-1)*m L0+(n-1)*m存储地址存储内容Loc(元素i)=L0+(i-1)*m顺序存储33 链式存储 1536元素21400元素

19、11346元素3 元素4h1345h34 数据操作描述数据的基本操作：插入：在数据结构的指定位置添加新的数据元素。删除：去掉数据结构中某个指定的数据元素。更新：改变数据结构中某个数据元素的值。查找：在数据结构中寻找某个满足特定要求的数据元素。排序：重新安排数据元素的逻辑顺序关系，使其值按从小到大或从大到小的顺序排列。从操作的特性分，所有的操作可以归结为两类：加工型操作操作改变了（操作之前的）结构的值。引用型操作不改变值，只是查询或求得结构的值。 35 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 什么是算法算法的五个特征：1、输入：可有0个或多个输入；2、输出：至少有1个或多个输出

20、；3、确定性：算法中每一步骤必须有确切含义，无二义性；4、有穷性：能够在有限步骤内结束，不能形成无限循环；5、可行性：算法可以在纸上作业方式跟踪其结果。算法设计的两个目标易读、易编码和调试（软件工程）充分利用计算机资源（算法和数据结构）36算法设计的要求：1、正确性：当输入数据合法时，能够得到满足要求的结果； 程序不含语法错误； 程序对于几组输入数据能够得出满足要求的结果； 程序对于精心选择的典型、苛刻的输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能够得出满足要求的结果。2、可读性：算法简单明了，便于别人对算法的理解和对程序的维护；3、健壮性：当输入非法时也能作出反应；4、效

21、率与低存储量要求 低存储规模：存储规模是指算法在执行过程中所需的最大存储空间，也称为算法的空间复杂性； 高效率：执行时间短的算法其效率就高，算法的执行时间也称为算法的时间复杂性。37算法与程序的区别： 计算机科学家 N.沃思 给出一个著名公式： 数据结构算法程序1、程序是在特定计算机上执行的算法，是具体的；而算法与具体计算机无关，是抽象的；2、程序可以不满足有限性要求；而算法必须满足有限性。 如：操作系统程序，除非关机，否则一直在等待循环中等待下一个工作进入系统，所以只要系统是在运作下，则操作系统程序就不会终止。解决一个具体问题，计算机来实现需要经过以下几个步骤：具体问题 抽象数学模型 设计算

22、法求解 编写程序，并进行测试、调整至最终解答38 算法效率需通过该算法编制的程序在计算机上运行所消耗的时间多少以及所需辅助空间的大小来度量。 算法效率的度量算法效率的衡量指标：时间复杂度和空间复杂度。时间复杂度：从算法中选取一个对于所研究的问题来说是基本操作的原操作（指固有数据类型的操作），以该基本操作重复执行的次数作为算法的时间量度。 计作：T（n）= O（f（n）。它表示随着n的增大，算法执行时间的增长率和 f ( n ) 的增长率相同。39空间复杂度： 一个上机执行的程序除了需要存储空间来积存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信

23、息的辅助空间。该辅助空间的大小及反映了该算法的空间复杂性。计作：S（n）= O（f（n）。频度：某语句重复执行的次数。40程序段一： +x; s=0； 该程序中“+x”是基本操作语句，其频度为1，其时间复杂度为O(1)，为常量阶。例：求下面程序的时间复杂度。41程序段二： for(i=1;i=n;+i) +x; s+=x; 该程序中“+x”是基本操作语句，其频度为n，其时间复杂度为O(n)，为线性阶。42程序段三： for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x; 该程序中“+x”是基本操作语句，其频度为n2，其时间复杂度为O(n2)，为平方阶。43程序段四：

24、 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x; 语句“+x”的执行次数关于n的增长率为n2,它是语句频度表达式(n-1)(n-2)/2中增长最快的项,时间复杂度为O(n2) 。i=2，执行0次；i=3，执行1次；i=4，执行2次；i=n，执行n-2次；总共执行次数123(n-2)=(n-2)(n-2+1)/2=(n-2)(n-1)/2=(n2 -3n+2)/244常见的几种时间复杂度数量级一般情况下，随着n的增大，T(n)增长较慢的算法为最优的算法。应该选择对数阶或多项式阶的算法，避免使用指数阶的算法。45衡量两个算法的好坏，应当是在n足够大的情形下

25、，对算法的工作量进行比较，即对算法进行渐近性态分析。n较小时难辨优劣46运行时间估计例：假设CPU每秒处理106 个指令，对于输入规模 n=108 的问题，时间代价为T(n)=2n2的算法要运行多长时间？操作次数为： T(n)=T(108)=2(108)2=21016运行时间为： 21016/106 = 21010秒每天有86,400秒，因此需要231,480 天(634年)47例：假设CPU每秒处理106 个指令，对于输入规模为n=108的问题，时间代价为T(n)=nlogn的算法要运行多长时间？操作次数为： T(n)=T(108)= 108 log108=2.66109运行时间为： 2.6

26、6109/106 = 2.66103秒，即分钟48规定时间内能解决的问题规模假设CPU每秒处理106个指令，则每小时能够解决问题的最大规模为多少？T(n)/1063600对T(n) = 2n2 而言，有： 即 2n2 3600 106 n 42 , 426对T(n) = nlogn而言，有： 即 nlogn 3600 106 n 133 , 000 , 00049算法的阶设非负函数f(n)和g(n)，nN，如果存在正常数c和正整数n0 ，使得当nn0 时，有f(n)cg(n)，则称f(n)的阶小于或等于g(n)的阶；记为 f(n)O(g(n)，读作f(n)是 g(n)的大O。一般采用求极限的方

27、法，来比较两个算法时间复杂性函数的阶： 当n时，lim f(n)/g(n)=c (1)当c0，f(n)比g(n)低阶，记为f(n) O(g(n)； (2)当c0，f(n)和g(n)同阶，记为f(n)(g(n)； (3)当c，f(n)比g(n)高阶，记为f(n)(g(n)；50算法的阶51算法的阶例如：2n-5 O(n2)，因为当n时，lim (2n -5)/n2 = 2/n - 5/n2 0-0=0；低阶例如：5n2 -3n=(n2)，因为当n时，lim (5n2 -3n)/n2 = 5 - 3/n5-0=5；同阶例如： n2 +5n=(n)，因为当n时，lim (n2 +5n)/n= n +

28、5 ；高阶注意：在求时间复杂度时，不需要严格区分同阶的情况下，把低阶或同阶的f和g统一写成 f O(g)52本章重点1.数据结构的有关基本概念2.数据结构的类型（逻辑结构）和存储方式（物理结构）3.算法及算法分析（算法评价）53作业1课件密码：y1t2y3 54第二章 线性表线性表的定义线性表的顺序表示线性表的链式表示一元多项式的运算55 线性表的基本概念线性表：是由一组数据元素组成，线性表或者是一个空表，或者 可以写成a1,a2, ai, , an，其中ai是取自某个集合S 的元素。 当1in时，数据元素ai-1称为数据元素ai的直 接前趋，而称ai+1为ai的直接后继。 若一个数据元素由若

29、干个数据项组成，则该数据元素又称为记录，含有大量记录的线性表又称为文件。 例子参见： P18 图学生健康情况登记表 线性表的定义56基本术语直接前驱： a i - 1 ，针对 a i 直接后继： a i + 1 ，针对 a i 线性表的长度：是指线性表中数据元素的个数，n = 0 时为空表。位序：下标i是数据元素ai 在线性表中的位序。57 线性结构的特点1、数据元素的数据类型一致。2、数据元素之间的相对位置呈线性关系。3、存在唯一的一个被称做“第一个”和“最后一个”的数据元素。4、除第一个和最后一个外，集合中每个数据元素均只有一个前驱和一个后继。58线性表抽象数据类型的定义(逻辑结构)ADT

30、 List 数据对象:D=ai | ai ElemSet , i = 1,2,.,n, n 0 数据关系:R1= |ai-1, ai D, i = 2,3,.,n 基本操作：/& 符号说明函数参数是引用型 InitList(&L) ListLength(L) DestroyList(&L) GetElem(L , i , &e) ClearList(&L) LocateElem(L , e ) ListEmpty(L) PriorElem(L , cur_e , &pre_e) ListInsert(&L , i , e) ListDelete(&L , i , &e) ADT List 59

31、利用ADT中的基本运算，可进行一些更复杂的操作，如线性表的合并、拆分等。例2-1 用两个线性表LA和LB分别表示两个集合A和B，现求新集合A = AB。算法如下：void union(List &La，List Lb) /在La中加入在Lb但不在La的元素 La_len = ListLength(La); Lb_len = ListLength(Lb); for(i = 1; i = Lb_len; i+) /扫描Lb中所有元素 GetElem(Lb，i，&e); /取Lb中第i个元素置于e if(!LocateElem(La，e，equal) /若在La中找不到e, ListInsert(L

32、a，+La_len，e); /则将e添加到La /end for /union60例2-2 巳知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。算法如下：void MergeList(List La，List Lb，List &Lc) /保序归并：归并非递减序列La和Lb为非递减序列Lc InitList(Lc); i = j = k = 1; /i,j,k为La,Lb,Lc的元素指针 La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_l

33、en) & (j = Lb_len) /只要i,j均指向表内便继续 GetElem(La，i，&ai); /取La中第i个元素置于ai GetElem(Lb，j，&bj); /取Lb中第j个元素置于bj if (ai = bj) /若ai小， ListInsert(Lc，k+，ai); /ai置于Lc第k位,k后移 i+; /i指针后移(j指针不动) else /否则(bj小), ListInsert(Lc，k+，bj); /bj置于Lc第k位,k后移 j+; /j指针后移(i指针不动) /end if /end while61 /上个循环结束后，La和Lb一定有一个表的元素被 /用完，而另一

34、个表的元素若未用完，处理之： while(i = La_len) /若La未用完，则将剩余元素依次加入Lc GetElem(La，i+，&ai); /取La中第i个元素置于ai,i后移 ListInsert(Lc，k+，ai); /ai置于Lc第k位,k后移 /end while while(j = Lb_len) /若Lb未用完，则将剩余元素依次加入Lc GetElem(Lb，j+，&bj); /取Lb中第j个元素置于bj,j后移 ListInsert(Lc，k+，bj); /bj置于Lc第k位,k后移 /end while/MergeList62线性表的存储结构顺序存储的线性表，叫顺序表链

35、式存储的线性表，叫链表 63线性表的顺序表示和实现顺序表的概念用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的特点：逻辑关系上相邻的两个元素在物理位置上也相邻。顺序表是随机存取的存储结构： 可以随机存取（所需时间相同）表中任一元素，因为它的存储位置可用一个简单、直观的公式（位序的线性函数）来表示。 顺序分配的存储结构采用向量结构：设线性表的长度为N，建立一向量V，用Vi表示第i个分量，第i个分量是线性表第i个元素ai在计算机存储中的映像，即Vi = ai 。64存储地址内存状态元素序号空闲aaaa12in: :bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in

36、线性表的顺序存储结构示意图 若线性表中的第一个存储元素的地址为LOC(a1)，每个元素占用L个存储单元，则表的第i个元素的存储地址（内存地址）为： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai)=LOC(ai-1)+L若每个元素仅占用1个存储单元，则表的第i个元素的存储地址为：LOC(ai)=LOC(a1)+(i-1)存储密度d：d=数据元素的值所需的存储量/该数据元素所需的存储总量在顺序分配的存储结构中，所有的存储单元空间全部被数据元素有效占用，因此，顺序分配结构的存储密度d=1。6566注意： 1）数据元素ai 的存储位置（内存地址）不同于位序 i ； 2）Loc(ai)是

37、ai在内存中的第一个字节的地址。 例如： 整型线性表存储在内存中的地址是C000，则表中的第7个元素的存储地址是多少？答：C000+2*6=C00C67顺序存储结构/定义顺序表类型SqList typedef int ElemType ; typedef Elemtype ET;typedef struct ElemType *elem ; /存储空间基址(顺序表的起址) int length ; /实际元素个数 int listsize ; /当前存储容量 /当前分配的存储容量(以sizeof(ElemType)为单位)SqList ; / SqList 是顺序表的类型名。68顺序表的基本操

38、作算法 /构造一个空的线性表 L#define List_Init_Size 100#define ListIncrement 10Status InitList_Sq( SqList &L) = (ET *) malloc(List_Init_Size*sizeof(ET); =NULL) exit(OVERFLOW); /*存储分配失败*/ =0; /* 空表的长度 */ =List_Init_Size; /* 初始存储容量 */ return OK; / InitList_Sq69顺序表的插入操作举例：例：设有长为n的线性表a1,a2, , an, 在第i位置插入新数据元素e。 顺序存储

39、结构的插入操作ea1a2a3ai-1aian:123i-1ini+1:a1a2a3ai-1an-1:123i-1ini+1n+1:aiean顺序表的插入操作算法： 1、如果1=i=n+1，则插入数据元素e。反之，则退出。 2、从第n到第i个存储单元的数据元素，依次后移，腾出空位i：第n个元素送给第n+1个存储单元，将第n-1个元素送到第n个存储单元，直到将第i个元素送给第i+1个存储单元。 3、在空位i处插入元素e，线性表长度加1。 4、返回。70顺序表的插入操作：在顺序表L中第i个位置上插入一个新的元素e。形式参数为：&L ,i , e ；算法步骤如下：对输入参数的安全性检查:插入位置i应落

40、在（表长1）范围内，即：1i L.length+1存储空间的处理：若原表的存储空间已满，应追加存储空间的分配；数据块的搬移：表中从i到位置上的所有元素往后移动一个位置；(移动 个元素)在第i个位置上存储新的元素e,表长增;注意：逻辑位置（序号）i 对应的存储下标是i-1。n-i+171重新分配动态存储空间的函数realloc(原动态区首址，字节数)原型： extern void *realloc(void *mem_address, unsigned int newsize); 功能：改变mem_address所指内存区域的大小为newsize长度。 申请新的动态存储空间(成功或失败);将原动

41、态区的数据拷贝到新动态区;释放原动态存储区;返回新存储区首地址（无类型）。用途：当原动态区不够用时，追加动态存储区；说明： 如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。当内存不再使用时，应使用free()函数将内存块释放。 注：若用C语言的数组实现顺序表，由于数组下标从“0”开始，因此属于SqList类型的表L的第i个元素是L.elemi-1而不是L.elemi。72 顺序表插入操作算法描述之一Status ListInsert_Sq (SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /若位置i非法 i

42、f (L.length = ) /若表容量不够则扩展 p=(ET*), (L.listsize+ListIncrement)*sizeof(ET); if (p= =NULL) exit(OVERFLOW); /若未分配成功，则终止程序 =p; /分配成功，新的表起址 += ListIncrement; /新容量 /追加顺序表的存储空间 for ( j=L.length ; j=i ; -j ) /用数组实现 L.elemj=L.elemj-1; /向后搬移数据块 L.elemi-1=e ; /插入元素e +L.length ; /表长增 return OK; / ListInsert_Sq7

43、3顺序表插入操作算法描述之二Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; if (L.length = ) p=(ET*), (L.listsize+ListIncrement)*sizeof(ET); if (p= =NULL) exit(OVERFLOW); =p; +=ListIncrement; q=&(L.elemi-1); / q=L.elem+(i-1) 插入位置 for (p=&(L.elemL.length-1); p=q; -p) /用指针实现 *(p+1)=*p

44、; /向后搬移数据块 *q=e ; +L.length ; return OK; /ListInsert_Sq74插入操作的算法性能分析空间复杂度：O( 1 )时间复杂度：O(n) , 其中基本操作是数据移动:最坏的情况下(在第一个位置上插入元素)，需要移动n个元素;最好的情况是不移动元素;平均情况下（等概率），需移动表中多少个元素？ 75平均情况下（等概率），需移动表中多少个元素？插入操作算法的时间复杂性： 1、假设在每个位置插入数据元素的概率相等，即概率为1/(n+1)。 2、基本操作为移动数据元素。 3、平均移动次数为 4、所以，插入操作算法的时间复杂性为O(n)。76删除操作：例：设有

45、长为n的线性表a1,a2, , an, 删除ai，并把它送入某单元e。 eaia1a2a3ai-1aian:123i-1in-1i+1n:a1a2a3ai-1an:123i-1in-1i+1n:ai+1顺序存储结构的删除操作顺序存储结构的删除操作算法： 1、如果1=i=n，则将第i个元素送给e。反之，则退出。 2、从第i个存储单元开始，依次将第i+1个元素送给第i个存储单元，将第i+2个元素送到第i+1个存储单元，直到将第n个元素送给第n-1个存储单元。 3、线性表长度减1。 4、返回。77顺序表的删除操作：在线性表L中删除ai，并把它送入某单元e形式参数为：&L , i , &e ；算法步骤

46、如下：对输入参数的安全性检查: 删除位置 i 应落在表长范围内，即：1 i L.length取出元素值赋给e：数据块的搬移：将表中从i+1到L.length位置上的所有元素往前移动一个位置；表长减：-L.length;78删除算法 /在线性表L中删除ai，并把它送入某单元eStatus ListDelete_Sq (SqList &L , int i , ET &e) if(iL.length) return ERROR; e=L.elemi-1; /被删除元素送给e for( j=i; j; j+) L.elemj-1=L.elemj; -; return OK; / ListDelete_

47、Sq问：基本操作是什么？时间复杂度是多少？79算法分析：基本操作是什么？ 时间复杂度是多少？删除操作算法的时间复杂性： 1、假设删除每个数据元素的概率相等，即概率为1/n。 2、基本操作为移动数据元素。 3、平均移动次数为 4、所以，删除操作算法的时间复杂性为O(n)。80提问顺序表中求表长的时间复杂度为（ ）顺序表中取第i元素的时间复杂度为（ ）顺序表中删除数据元素的时间复杂度为（ ）顺序表中插入数据元素的时间复杂度为（ ） A) O(n) B) O(1) C) O(logn) D) O(n2)81算法 /* 定位：在顺序表L中查找首个与给定值e满足比较关系compare()的元素并返回其位

48、序，若未找到则返回0 算法步骤： 1: 依次查访第1至n个元素 2: 返回结果 */int LocateElem_Sq (SqList *L, ElemType e, int (*compare)(ElemType, ElemType) ElemType *p; int i; p = ; /p指向首元素 for (i = 1; i = ; i+) if (compare(*p+, e) /成功找到e元素，退出for循环 break; /end for if (i = ) /成功找到e元素，返回i return i; else /没找到e元素，返回0 return 0;/LocateElem_S

49、q82/* 算法 顺序表保序归并 */ void MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc) /保序归并：归并非递减顺序表La和Lb为非递减顺序表Lc ElemType *pa, *pb, *pc, *pa_last, *pb_last; pa = ; /a表当前指针初始为指向首元素 pb = ; /b表当前指针初始为指向首元素 pa_last = + - 1; /a表尾指针 pb_last = + - 1; /b表尾指针 = = + ; /c表容量和表长 = (ElemType *)*sizeof(ElemType); pc = ; /c

50、表当前指针初始为指向首元素 if (pc= =NULL) exit(OVERFLOW); /存储分配失败83/归并：while(pa = pa_last) & (pb = pb_last) /只要pa, pb均指向表内便继续 if (*pa = *pb) /若a表当前元素小， *pc = *pa; /则置其于c表当前位置， pc+; pa+; /a和c指针后移(b指针不动)； else /否则(b表当前元素小), *pc = *pb; /则置b表当前元素于c表当前位置， pc+; pb+; /b和c指针后移(a指针不动)； /end if /end while 84 /上个循环结束后，La和L

51、b一定有一个表的元素被用完，而另一个表的元素可能未用完，处理之： while (pa = pa_last) /若La未用完，则将剩余元素依次加入Lc *pc = *pa; pc+; pa+; /end while while (pb next; while (p) printf(%c - , p-data); p = p-next; printf(NULLn);头abcd Lppppp93创建一个有N个节点的单链表void CreatList( LinkList *L, int n) int i; LinkList p, q; ET c; p=(LinkList)malloc(sizeof(L

52、Node); p-next=NULL; /生成头结点 *L = q = p; printf(Please input the data : ); for (i=n; i0; i-) /添加结点 p=(LinkList)malloc(sizeof(LNode); c = getche(); printf(nn); p-data = c; p-next =NULL; q-next = p; q=p; 头dcba Lpq头Lqp头d Lpqqd p94初始化一个单链表void Init(LinkList *L) int n; printf(Please input the number of the

53、 node : ); scanf(%d, &n); CreatList(L, n);95单链表的插入操作在单链表L中的第 i 个结点之前的插入操作步骤如下：( i 0 )寻找第 i-1个结点； /O(n)测试已知量的合法性； /O(1)申请一个结点存储空间，并给其数据域赋值； / O(1)新结点插入链表中。 /O(1)该算法的时间复杂度是：O(n)96单链表的插入操作算法Status ListInsert(LinkList *L, int i, ET e) int j=0; LinkList p, s; p=L; while ( p & jnext; +j; if ( !p | ji-1 )

54、return ERROR; s=(LinkList) malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK;97接收插入数据，调用插入操作Status Insert(LinkList L) int i, flag; ET data; printf(Please input the position : ); scanf(%d, &i); printf(Please input the data : ); data = getche(); flag = ListInsert(L, i, data); return f

55、lag;98单链表的删除操作：删除第i个结点步骤若头指针为空，则退出；否则执行下面的操作。找到要删除结点的直接前驱，将该结点的指针域指向它的直接后继。若不能找到，则返回。释放该结点所占用的内存空间。 BATCATHATWATLq第i个结点p BATHATWATLp99单链表的删除操作算法Status ListDelete (LinkList *L, int i, ET *e) /删除第i个结点 LinkList p, q; int j=0; p=L; while (p & jnext; +j; if ( !(p-next) | (ji-1) ) return ERROR; /删除位置不对 q=

56、p-next; /删除q结点，即删除p的下一个结点i p-next=q-next; *e=q-data; free(q); /释放删除的结点q return OK; 100从单链表L中，读取第i个元素的值赋给参数eStatus GetElem (LinkList L, int i, ET *e) int j=1; LinkList p; p=L-next; while (p & jnext; +j; if( !p | ji) return ERROR; *e=p-data; return OK; 时间复杂度为：O(n) 问题：在顺序表中，GetElem_Sq时间复杂度是什么？O(1)101将两

57、个有序单链表合并为一个void MergeList(LinkList L1, LinkList L2, LinkList L3) LinkList pa, pb, pc; pa = L1-next; /L1和L2含头结点(第0个结点)， pb = L2-next; /pa和pb分别指向头结点的下一个结点(第1个结点) pc = L3; while (pa & pb) if (pa-data data) /pc-next = pa; 意味着pc也含头结点 pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = p

58、b-next; pc-next = pa? pa: pb; /插入剩余部分 L1-next=NULL; L2-next=NULL; /L1和L2只保留头结点102功能控制函数void MenuSelect (LinkList La, LinkList Lb) int select, done=1; LinkList Lc; while (done) MenuList( ); printf(input the operating code : ); scanf(%d, &select); switch(select) case 1: Insert(La);break; case 2: Inser

59、t(Lb);break; case 3: Delete(La);break; case 4: Delete(Lb);break; case 5: Union(La, Lb);break; case 6: CreatList(&Lc, 0);MergeList(La, Lb, Lc); printf(LC: );printlk(Lc); break; case 7: printf(LA: );printlk(La); printf(LB: ); printlk(Lb); break; case 8: done=0;break; default: printf( ERRORn); 103主函数ma

60、in( ) LinkList La, Lb; printf(LA ); Init(&La) ; printlk(La); printf(LB ); Init(&Lb) ; printlk(Lb); MenuSelect(La, Lb);104构造一个空的单链表, 算法描述：Status InitList_L (LinkList *L) / L是双指针 *L=( LinkList ) malloc ( sizeof ( Lnode ) ); if ( *L=NULL) exit (OVERFLOW); (*L) next=NULL; (*L) data=0; return OK ; 0NULLL