资源描述：
《数据结构第二章 线性表-跟ppt完全对应》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构-线性表【学习目标】 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4.结合线性表类型的定义增强对抽象数据类型的理解。【重点和难点】 链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章
2、的基本要求，分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点】 线性表、顺序表、链表、有序表【学习指南】 正如课程概况中所提，学习数据结构的目标是为了编出质量更高的程序，因此重在"实践"。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。本章要求必须完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38。其中2.11和2.1
3、9可以在学完顺序表之后练习，其余都建议在学完全章的内容之后进行。【课前思考】1.抽象数据类型的定义由哪几部分组成？2.按数据元素之间的逻辑关系不同，数据结构有哪几类？3.你能举出几个你熟悉的"序列"的例子来吗？课时安排：第一课时：线性结构、线性表的逻辑结构、线性表的抽象数据类型定义第二课时：线性表的顺序存储结构结构的表示：定义、元素地址计算方法、特点、实现基本操作：插入：定义和分析、算法、算法图示、算法时间复杂度分析删除：定义和分析、算法、算法图示、算法时间复杂度分析第三四课时：顺序存储结构的优缺点线性表的链式存储结构单链表定
4、义、c语言实现、指针、头结点、基本操作查找：定义、算法描述、算法评价插入：定义、算法描述、算法评价删除：定义、算法描述、算法评价例子：动态建立单链表：算法描述、算法评价单链表的特点11数据结构-线性表第五六课时：链式存储结构的优缺点循环链表双向链表双向循环链表从第二章开始，我们将开始讨论第一章里面提到的四种数据结构。这一章我们讨论一种最简单的线性结构—线性表。l线性结构什么是线性结构？线性结构数据元素之间存在什么样的关系，简单地说，线性结构是一个数据元素的有序（次序）集合。这里的"有序"仅指在数据元素之间存在一个"领先"或"落
5、后"的次序关系，而非指数据元素"值"的大小可比性。它有四个基本特征： 1．集合中必存在唯一的一个"第一元素"；2．集合中必存在唯一的一个"最后元素"；3．除最后元素之外，其它数据元素均有唯一的"后继"；4．除第一元素之外，其它数据元素均有唯一的"前驱"。l线性表的逻辑结构线性表的类型定义线性表是一种最简单的线性结构。通常可以下列"n个数据元素的序列"表示线性表(Linear_List)通常可以这样表示 线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可。 例如，26个小写英文字母是一个线性表 (a,b,…,
6、z)同一花色的13张扑克牌 (2,3,4,5,6,7,8,9,10,J,Q,K,A)可以构成一个线性表。 例英文字母表（A,B,C,…..Z)是一个线性表学号姓名年龄001张三18002李四19………………例特征：1．序列中数据元素的个数n为线性表的一个属性，定义为线性表的表长；n=0时的线性表被称为空表。2.由于线性表是一个序列，所以每一个元素在线性表中都有一个固定的位置，称为线性表中第i个元素，称i为在线性表中的位序。11数据结构-线性表3.17、n无直接后继4.元素同构，是属于同一个对象的，也就是具有相同的特性，且不能出现缺项l线性表的抽象数据类型定义其抽象数据类型的定义如下：（ppt上没有，但书上有，可以讲）ADTList{数据对象：D＝{ai
8、ai∈ElemSet,i=1,2,...,n,n≥0}线性表由n个元素构成，其中n≥0。数据关系：R1＝{
9、,∈D,i=2,...,n}其中数据元素之间的关系表现为n个有序对。基本操作：线性表的操作有多种类型，总的来说可以归纳为四类。 {结构初始化}InitList(&L) 操作结果：构造一个空的线性表
10、L。任何数据结构在被使用之前都必须进行"初始化"，它类似于编程中使用的变量都必须先有定义。{销毁结构}DestroyList(&L) 初始条件：线性表L已存在。操作结果：销毁线性表L。任何数据结构不再使用时都必须进行"结构销毁"，其实质为"释放"它所占有的存储空间。{引用型
