学生信息处理课件

1、学生信息处理学生的信息包括：学号、姓名、性别、年龄、专业等数据项。功能要求 插入：将某学生的基本信息插入到表中； 删除：将满足条件的基本信息删除； 修改：对基本信息的数据项进行修改； 查询：查找满足条件的学生； 输出：将信息表中的全部（或满足条件）基本信息输出。2022/10/111学生信息处理学生的信息包括：2022/10/101思考：数据元素之间的关系是什么？数据如何表示？数据如何存储？数据如何处理？2022/10/112思考：数据元素之间的关系是什么？数据如何表示？数据如何存第2章 线性表本章的基本内容是：线性表的基本概念线性表的顺序存储及实现线性表的链式存储及实现顺序表和单链表的比较2

2、022/10/113第2章 线性表本章的基本内容是：2022/10/1032.1 线性表的基本概念线性表的逻辑结构线性表是具有相同数据类型的n（n0）个数据元素组成的有限序列，通常记为L=(a1，a2，ai1，ai，ai+1，an)a1a3a4ana22022/10/1142.1 线性表的基本概念线性表的逻辑结构线性表是具有相同数2.1 线性表的基本概念非空线性表的特性 (P12)有且仅有一个表头结点a1，它没有前驱，而仅有一个后继a2；有且仅有一个表尾结点an，它没有后继，而仅有一个前驱an1；其余的结点ai（2in1）都有且仅有一个前驱a i1和一个后继a i+1。线性表的存储结构 (P1

3、2)顺序存储链式存储2022/10/1152.1 线性表的基本概念非空线性表的特性 (P12)线性表2.2 线性表的顺序存储结构及实现存储要点用一段地址连续的存储单元依次存储线性表中的数据元素 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空闲 2022/10/1162.2 线性表的顺序存储结构及实现存储要点用一段地址连续的如何求得任意元素的存储地址？2.2 线性表的顺序存储结构及实现 a1 ai-1 ai an 空闲 dLoc(ai) 0 i-2 i-1 n-1 MaxSize-1 Loc(a1)Loc(ai)=Loc(a1) + (i -1)d随机存取：在O(

4、1)时间内存取数据元素2022/10/117如何求得任意元素的存储地址？2.2 线性表的顺序存储结构及2.2 线性表的顺序存储结构及实现 0 i-2 i-1 n-1 MaxSize-1 a1 ai-1 ai an 空闲 如何描述顺序表？顺序表的内存分配：一维数组data顺序表的容量（最大长度）：MaxSize顺序表的当前长度：lengthlengthdata2022/10/1182.2 线性表的顺序存储结构及实现 0 2.2 线性表的顺序存储结构及实现顺序表的类模板 P13template class SeqList T dataMaxSize; /用于存放数据元素的数组 int length

5、; /顺序表中元素的个数public: SeqList( ); /无参构造函数 SeqList(T a, int n); /有参构造函数 int ListLength(); /求线性表的长度 T Get(int pos); /按位查找 int Locate(T item); /按值查找 void PrintSeqList(); /遍历顺序表 void Insert(int i, T item); /在顺序表中第i个位置插入值为item的元素 T Delete(int i); /删除顺序表的第i个元素;2022/10/1192.2 线性表的顺序存储结构及实现顺序表的类模板 2.2 线性表的顺序存

6、储结构及实现顺序表的操作算法 P16-201、初始化操作 无参构造函数：创建空表 有参构造函数2、求顺序表长度3、按位查找4、按值查找5、遍历顺序表6、插入7、删除2022/10/11102.2 线性表的顺序存储结构及实现顺序表的操作算法 2.2 线性表的顺序存储结构及实现顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 随机存取：可以快速地存取表中任一位置的元素。 顺序表的缺点： 插入和删除操作需要移动大量元素； 表的容量难以确定，表的容量难以扩充； 造成存储空间的碎片。 2022/10/11112.2 线性表的顺序存储结构及实现顺序表的优点：2022/2.3 线性表的

7、链式存储结构及实现存储思想：用一组任意的存储单元存放线性表的元素。静态存储分配 顺序表事先确定容量 链式动态存储分配 运行时分配空间 连续不连续零散分布存储特点： 逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示。2022/10/11122.3 线性表的链式存储结构及实现存储思想：用一组任意的存2.3 线性表的链式存储结构及实现2.3.1单链表 P14 data next单链表的结点结构：数据域指针域template struct Node T data; Node *next; 2022/10/11132.3 线性表的链式存储结构及实现2.3.1单链表 Pheada1a2an非空表

8、head=NULL空表 不带头结点的单链表2.3.1单链表头指针：指向第一个结点的地址。2022/10/1114heada1a2an非空表head=NULL空表 不带头结头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。 非空表heada1a2an空表head2.3.1单链表带头结点的单链表2022/10/1115头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点2.3.1单链表template class LinkList public: LinkList( )； LinkList(T a , int n); LinkList( ); int

9、Length( ); T Get(int pos); int Locate(T x); void Insert(int i, T item); T Delete(int i); void PrintList( ); private: Node *head; ;单链表的类模板2022/10/11162.3.1单链表template 单链表的2.3.1单链表单链表的基本操作算法 P21-261、初始化操作 无参构造函数 有参构造函数2、求单链表长度3、按位查找4、按值查找5、遍历单链表表6、插入7、删除2022/10/11172.3.1单链表单链表的基本操作算法 P21-2612.3.1单链表单链

10、表的其他操作 P26-281、单链表的逆置2、合并有序单链表2022/10/11182.3.1单链表单链表的其他操作 P26-281、单循环链表：将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。2.3.2 线性表的其他链式存储结构双向链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。2022/10/1119循环链表：将单链表的首尾相接，将终端结点的指针域由空指针改为1、求集合的并集 顺序表的应用2.4 线性表的应用2、一元多项式相加 单链表的应用2022/10/11201、求集合的并集2.4 线性表的应用2、一元多项式相加2022.5 顺序

11、表和单链表的比较存储分配方式比较顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。2022/10/11212.5 顺序表和单链表的比较存储分配方式比较2022/10/2.5 顺序表和单链表的比较时间性能比较 时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。 按位查找：顺序表的时间为(1)，是随机存取；单链表的时间为(n)，是顺序存取。插入和删除：顺序表需移动表长一半的元素，时间为(n)；单链表不需要移动元素，在

12、给出某个合适位置的指针后，插入和删除操作所需的时间仅为(1)。2022/10/11222.5 顺序表和单链表的比较时间性能比较 2022/10/12.5 顺序表和单链表的比较空间性能比较 空间性能是指某种存储结构所占用的存储空间的大小。 定义结点的存储密度： 数据域占用的存储量整个结点占用的存储量存储密度2022/10/11232.5 顺序表和单链表的比较空间性能比较 数据域占用的存储2.5 顺序表和单链表的比较空间性能比较 结点的存储密度：顺序表中每个结点的存储密度为1（只存储数据元素），没有浪费空间；单链表的每个结点的存储密度1（包括数据域和指针域），有指针的结构性开销。整体结构：顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。2022/10/11242.5 顺序表和单链表的比较空间性能比较 2022/10/12.5 顺序表和单链表的比较若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除