02线性表

第二章 线性表 课程简要说明

数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法。 通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用C语言编写质量高、风格好的应用程序及初步评价算法程序的能力；为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。 要求结合实际问题，学会分析计算机加工的数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的简单时间复杂度分析方法，训练掌握各种数据结构的表示方法和实现的算法。 (1)知识要求：学生通过学习该课程后主要应掌握以下内容：①掌握程序设计的基本原理和方法②了解对各种抽象数据类型的性质③掌握处理各种抽象数据类型的基本算法④初步掌握算法的简单时间复杂度分析方法 (2)素质要求：学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。 (3)能力要求：学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。

【第三次（2学时）】 教学主题或章、节 第二章 线性表

授课类型 理论课√ 实验课 实习或课程设计 练习课 其他□ 教学过程 前面章节复习 5 分钟，新课 93 分钟，布置作业 2 分钟 教学方式 讲授√ 讨论√ 阅读√ 示范操作 练习 提问√ 其他□ 教学资源 多媒体课件√ 演示动画√ 相关软件 音像 其他√ 教学目的及要求（分掌握、理解、了解三个层次）： 理解线性表的定义和抽象数据类型，掌握线性表的顺序存储结构，掌握线性表的顺序表示和操作实现并能灵活应用。 教学内容提要： 第一部分 前面章节简要回顾（约5分钟） 对C语言中的指针应用，指针作为参数使用的特点做简要回顾。 第二部分 新课（约93分钟） 第2章 线性表抽象数据类型及线性表的顺序表示和实现 本章内容概述（约5分钟） 简述本章基本要求、学习内容、重点、以及本章教学内容安排。 课程导入：采用任务驱动的方法，提出要建立学生成绩管理系统，如何实现？引入线性结构的特点。 线性结构的特点： – 存在唯一一个被称做“第一个”的数据元素； – 存在唯一一个被称做“最后一个”的数据元素； – 除第一个数据元素之外，每个元素都只有一个前驱； – 除最后一个数据元素之外，每个元素都只有一个后继。 §2.1 线性表的类型定义（约15分钟） （1）线性表定义：是n个数据元素的有限序列。介绍相关基本概念 结合任务学生管理系统、分析系统所涉及数据的特点。 （2）线性表的特征：有穷性、有序性、同一性。 （3）线性表的抽象数据类型定义：(略讲) 重点讲述基本操作部分，包括：结构初始化操作、结构销毁操作、引用型操作、加工型操作、复杂操作注：举算法实例讲解 举例：利用线性表实现集合的并、集合的无重复并，线性表的合并 §2.2 线性表的顺序表示和实现 ——顺序映象（约70分钟） 一、顺序表示和实现的基本概念和表示方式（约15分钟） （1）线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素。特点：是一种随即存取的存储结构，只要确定了起始位置，就可以访问表中的任何一个元素。 用物理位置来表示逻辑结构地址的计算方法。 LOC(ai+1)=LOC(ai)+l ; LOC(ai)=LOC(a1)+(i-1)*l 举例说明，其计算方式。 （2）线性表顺序存储结构的——C语言定义（动态分配方式） #define LIST_INT_SIZE 100 #define LISTINCREAMENT 10 typedef struct { ElemType *elem； /* 线性表占用的数组空间。*/ int length； /*线性表的长度*/ int listsize； /*当前分配的存储容量(以sizeof(ElemType)为单位) /* } SeqList； 同时对比其顺序存储结构的静态分配方式，二者运用的区别和不同。 二、顺序存储结构的基本操作（约55分钟） 顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。 （1）初始化操作（约10分钟） 算法思想：构造一个空表。设置表的起始位置、表长及可用空间。 重点讲解初始化的作用，以及如何进行实现。 （2）线性表的顺序表插入操作ListInsert(&L, i, e) （约17分钟） 通过提问方式引入，针对原来提出的任务，建造一个学生管理系统，在管理过程中，如果新来一位同学的话，如何更新原来的系统，引出插入，算法的基本思想：检查i值是否超出所允许的范围（1≤i≤n+1），若超出，则进行“超出范围”错误处理；将线性表的第i个元素和它后面的所有元素均向后移动一个位置；将新元素写入到空出的第i个位置上；使线性表的长度增1。 重点讲解如何插入的思想，如何把思想转化为语言进行实现，并分析插入操作的时间复杂度、以及在插入过程中平均移动元素的次数。在讲解过程中举例说明。并布置一定的任务，课下实现学生管理系统的插入算法。 （3）线性表的顺序表删除操作ListDelete(&La, i, &e) （约17分钟） 同样的方式提出，如果某个学生退学，应该如何更改原来的学生信息，简述删除算法的基本思想，检查i值是否超出所允许的范围（1≤i≤n），若超出，则进行“超出范围”错误处理；将线性表的第i个元素后面的所有元素均向前移动一个位置；使线性表的长度减1。 重点讲解如何删除的思想，如何把思想转化为语言进行实现，并分析删除操作的时间复杂度、以及在插入过程中平均移动元素的次数。在讲解过程中举例说明。并布置一定的任务，课下实现学生管理系统的删除算法。 （4）线性表的顺序表查找操作LocateElem_Sq (La, e) （约12分钟） 同样的方式提出，如果要查询学生的新题，应该如何更改原来的学生信息，简述查找算法的基本思想。举例说明。分析其时间复杂度。 三、顺序存储结构的优缺点（约3分钟） 顺序存储结构的优点：逻辑相邻，物理相邻、可随机存取任一元素、存储空间使用紧凑。缺点：插入、删除操作需要移动大量的元素、预先分配空间需按最大空间分配，利用不充分、表容量难以扩充。 §小结（约3分钟） 内容回顾、重点、难点。 第三部分 布置作业（约2分钟） 书面作业：完成学生管理系统中的查找算法、插入算法、删除算法。 重点和难点： 重点：顺序存储结构的四种基本操作实现、及其时间复杂度分析。 难点：将具体算法思想转换成语言的实现过程。 参考资料： 《数据结构题集》严蔚敏等编著，清华大学出版社 《数据结构学习指导与习题详解》张凤琴等编，清华大学出版社 《数据结构（C语言篇）习题与解析》李春葆编，清华大学出版社 注意事项及心得： 线性表的抽象数据类型的定义要简略讲，注意把握时间。

2.2.2 运算的实现
1. 创建一个空顺序表 PSeqList createNullList_seq(int m ) 首先需要调用函数malloc(sizeof(struct SeqList))， 首先需要调用函数malloc(sizeof(struct SeqList))， 得到一 个 struct SeqList 的 空 间 ， 然 后 再 按 参 数 m 的 大 小 调 用 malloc(sizeof(DataType)*m)， malloc(sizeof(DataType)*m) ， 得到为顺序表分配的一个由参 数m指定大小的数组空间，并将顺序表的MAXNUM字段置 指定大小的数组空间，并将顺序表的MAXNUM字段置 为m， n字段置为0。 字段置为0 程序实现 2. 判断线性表是否为空 int isNullList_seq( PSeqList palist ) 判断palist的 字段是否为0 判断palist的n字段是否为0即可 程序实现
2.1基本概念与抽象数据类型 2.1基本概念与抽象数据类型
2.1.1 基本概念
线性表（ 线性表（简称为表）是零个或多个元素的有穷序列。 L=（ k0，k1,…，kn-1） L=（ 线性表的逻辑结构：L=<K， 线性表的逻辑结构：L=<K，R> 其中K={ 其中K={ k0，k1,…，kn-1}， R={<ki, ki+1>|0≤i≤n-2 }， >|0≤i≤科学学院 生命科学学院
生物技术学系 生物技术学系 细胞及遗传学系 细胞及遗传学系
2.1.2 抽象数据类型
假设用List表示一个线性表类型，用DataType来 假设用List表示一个线性表类型，用DataType来 表示其元素的类型 ，元素的下标用Position类 ，元素的下标用Position类 型的量表示， 则可以说明如下: 则可以说明如下: List list; DataType x; Position p;

即：LOC(ai) = LOC(ai-1) + C
一个数据元素所占存储量↑
所有数据元素的存储位置均取决于
第一个数据元素的存储位置
LOC(ai) = LOC(a1) + (i-1)×C
↑基地址
SIE. BIT
数据结构与算法设计
线性表的顺序存储结构示意图
逻辑地址
0
数据元素
k0
存储地址 数据元素
Loc(k0) k0
SIE. BIT
数据结构与算法设计
链表的常用操作

获取表头指针；
求链表的长度；



寻找第i个数据元素；
根据关键字值求数据元素在链表中的位 置； 插入数据元素； 修改数据元素的值； 删除数据元素。
SIE. BIT

数据结构与算法设计
2.2 抽象链表类的定义
线性链表有3种：单链表、循环链表与双向链表； 抽象出上述三种线性链表的相同点（结点、指针和 相同操作），建立一个抽象链表类，再由此抽象链 表类派生出新的链表类（单链表和循环链表）； 采用类模板机制； 增加表头结点，统一空表和非空表的操作，方便算 法设计。
010501
010502
令狐冲
王重阳
17
18
男
男
010503
010504 010505
曲洋
何铁手 李莫愁
17
19 16
男
女 女
SIE. BIT
数据结构与算法设计
1.2 线性表的顺序存储方式
在计算机内部可以采用两种不同方法来表示
一个线性表，它们分别是顺序表表示法和链
表表示法。
顺序表示法的定义； 元素的地址表示； 顺序表示法的优、缺点。

5. 单链表类
public class SinglyLinkedList<E> implements LList<E> { //单链表类，实现线性表接口 protected Node<E> head; //头指针 public SinglyLinkedList() { //构造空单链表 this.head = null; } }（P59） • 单链表操作的效率分析
2.3.1 线性表的链式存储结构
2.3.2 单链表
•单链表结点类 public class Node<E> { //单链表结点类 public E data; //数据域，保存数据元素 public Node<E> next; //地址域，引用后继结点 }
Node<String> p,q; p=new Node<String>("A"); q=new Node<String>("B"); p.next=q;
*2.4 迭代器（略）
【例2.2】 采用单链表求解约瑟夫环问题。
7. 单链表是递归结构
public String toString() { return "(" + this.toString(this.head) + ")"; } public String toString(Node<E> p) { //递归算法 if (p!=null) return p.data.toString() + ", " + this.toString(p.next); return ""; }