学生信息处理课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,学生信息处理,学生的信息包括：,学号、姓名、性别、年龄、专业等数据项。,功能要求,插入：将某学生的基本信息插入到表中；,删除：将满足条件的基本信息删除；,修改：对基本信息的数据项进行修改；,查询：查找满足条件的学生；,输出：将信息表中的全部（或满足条件）基本信息输出。,2024/10/1,1,学生信息处理学生的信息包括：2022/10/101,思考：,数据元素之间的关系是什么？数据如何表示？,数据如何存储？,数据如何处理？,2024/10/1,2,思考：数据元素之间的关系是什么？数据如何表示？数据如何存,第,2,章 线性表,本章的基本内容是：,线性表的基本概念,线性表的顺序存储及实现,线性表的链式存储及实现,顺序表和单链表的比较,2024/10/1,3,第2章 线性表本章的基本内容是：2022/10/103,2.1 线性表的基本概念,线性表的逻辑结构,线性表是具有相同数据类型的,n,（,n,0,）个数据元素组成的有限序列，通常记为,L,=(,a,1,，,a,2,，,，,a,i,1,，,a,i,，,a,i,+1,，,，,a,n,),a,1,a,3,a,4,a,n,a,2,2024/10/1,4,2.1 线性表的基本概念线性表的逻辑结构线性表是具有相同数,2.1 线性表的基本概念,非空线性表的特性,(P12),有且仅有一个表头结点,a,1,，它没有前驱，而仅有一个后继,a,2,；,有且仅有一个表尾结点,a,n,，它没有后继，而仅有一个前驱,a,n,1,；,其余的结点,a,i,（,2,i,n,1,）都有且仅有一个前驱,a,i,1,和一个后继,a,i,+1,。,线性表的存储结构,(P12),顺序存储,链式存储,2024/10/1,5,2.1 线性表的基本概念非空线性表的特性(P12)线性表,2.,2,线性表的顺序存储结构及实现,存储要点,用一段地址,连续,的存储单元,依次,存储线性表中的数据元素,0 ,i,-2,i,-1 ,n,-1 MaxSize-1,a,1,a,i,-1,a,i,a,n,空闲,2024/10/1,6,2.2 线性表的顺序存储结构及实现存储要点用一段地址连续的,如何求得任意元素的存储地址？,2.,2,线性表的顺序存储结构及实现,a,1,a,i,-1,a,i,a,n,空闲,d,Loc(,a,i,),0 ,i,-2,i,-1 ,n,-1 MaxSize-1,Loc(,a,1,),Loc(,a,i,)=Loc(,a,1,)+(,i,-,1),d,随机存取,：,在,O,(1),时间内存取数据元素,2024/10/1,7,如何求得任意元素的存储地址？2.2 线性表的顺序存储结构及,2.,2,线性表的顺序存储结构及实现,0 ,i,-2,i,-1 ,n,-1 MaxSize-1,a,1,a,i,-1,a,i,a,n,空闲,如何描述顺序表？,顺序表的内存分配：一维数组,data,顺序表的容量（最大长度）：,MaxSize,顺序表的当前长度：,length,length,data,2024/10/1,8,2.2 线性表的顺序存储结构及实现 0,2.,2,线性表的顺序存储结构及实现,顺序表的类模板,P13,template,class SeqList,T dataMaxSize;/用于存放数据元素的数组,int length;/顺序表中元素的个数,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个元素,;,2024/10/1,9,2.2 线性表的顺序存储结构及实现顺序表的类模板,2.,2,线性表的顺序存储结构及实现,顺序表的操作算法,P16-20,1、初始化操作,无参构造函数：创建空表,有参构造函数,2,、求顺序表长度,3,、按位查找,4,、按值查找,5,、遍历顺序表,6,、插入,7,、删除,2024/10/1,10,2.2 线性表的顺序存储结构及实现顺序表的操作算法,2.,2,线性表的顺序存储结构及实现,顺序表的优点：,无需为表示表中元素之间的逻辑关系而增加额外的存储空间；,随机存取：可以快速地存取表中任一位置的元素。,顺序表的缺点：,插入和删除操作需要移动大量元素；,表的容量难以确定，表的容量难以扩充；,造成存储空间的碎片。,2024/10/1,11,2.2 线性表的顺序存储结构及实现顺序表的优点：2022/,2.,3,线性表的链式存储结构及实现,存储思想：,用一组,任意,的存储单元存放线性表的元素。,静态存储分配,顺序表,事先确定容量,链式,动态存储分配,运行时分配空间,连续,不连续,零散分布,存储特点：,逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示。,2024/10/1,12,2.3 线性表的链式存储结构及实现存储思想：用一组任意的存,2.,3,线性表的链式存储结构及实现,2.3.1,单链表,P14,data next,单链表的结点结构：,数据域,指针域,template,struct Node,T data;,Node*next;,;,2024/10/1,13,2.3 线性表的链式存储结构及实现2.3.1单链表 P,head,a,1,a,2,a,n,非空表,head=NULL,空表,不带头结点的单链表,2.3.1,单链表,头指针：,指向第一个结点的地址。,2024/10/1,14,heada1a2an非空表head=NULL空表 不带头结,头结点：,在,单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,非空表,head,a,1,a,2,a,n,空表,head,2.3.1,单链表,带头结点的单链表,2024/10/1,15,头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点,2.3.1,单链表,template,class LinkList,public:,LinkList,(),；,LinkList,(,T a,int n,),;,LinkList,(),;,int Length,(),;,T Get,(,int pos,),;,int Locate,(,T x,),;,void Insert,(,int i,T item,),;,T Delete,(,int i,),;,void PrintList,(),;,private:,Node*head;,;,单链表的类模板,2024/10/1,16,2.3.1单链表template 单链表的,2.3.1,单链表,单链表的基本操作算法,P21-26,1、初始化操作,无参构造函数,有参构造函数,2,、求单链表长度,3,、按位查找,4,、按值查找,5,、遍历单链表表,6,、插入,7,、删除,2024/10/1,17,2.3.1单链表单链表的基本操作算法 P21-261,2.3.1,单链表,单链表的其他操作,P26-28,1、单链表的逆置,2,、合并有序单链表,2024/10/1,18,2.3.1单链表单链表的其他操作 P26-281、单,循环链表：,将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成,单循环链表,，简称,循环链表,。,2.3.2,线性表的其他链式存储结构,双向链表：,在,单链表的每个结点中再设置一个指向其前驱结点的指针域,。,2024/10/1,19,循环链表：将单链表的首尾相接，将终端结点的指针域由空指针改为,1,、求集合的并集,顺序表的应用,2.4,线性表的应用,2,、一元多项式相加,单链表的应用,2024/10/1,20,1、求集合的并集2.4 线性表的应用2、一元多项式相加202,2.5,顺序表和单链表的比较,存储分配方式比较,顺序表采用顺序存储结构，即用一段地址连续的存储单元,依次,存储线性表的数据元素，数据元素之间的逻辑关系通过,存储位置,来实现。,单链表采用链接存储结构，即用一组,任意,的存储单元存放线性表的元素。用,指针,来反映数据元素之间的逻辑关系。,2024/10/1,21,2.5 顺序表和单链表的比较存储分配方式比较2022/10/,2.5,顺序表和单链表的比较,时间性能比较,时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。,按位查找：,顺序表的时间为,(1),，是随机存取；,单链表的时间为,(n),，是顺序存取。,插入和删除：,顺序表需移动表长一半的元素，时间为,(n),；,单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为,(1),。,2024/10/1,22,2.5 顺序表和单链表的比较时间性能比较 2022/10/1,2.5,顺序表和单链表的比较,空间性能比较,空间性能是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度：,数据域占用的存储量,整个结点占用的存储量,存储密度,2024/10/1,23,2.5 顺序表和单链表的比较空间性能比较 数据域占用的存储,2.5,顺序表和单链表的比较,空间性能比较,结点的存储密度：,顺序表中每个结点的存储密度为,1,（只存储数据元素），没有浪费空间；,单链表的每个结点的存储密度,1,（包括数据域和指针域），有指针的结构性开销。,整体结构：,顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；,单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。,2024/10/1,24,2.5 顺序表和单链表的比较空间性能比较 2022/10/1,2.5,顺序表和单链表的比较,若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。,当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。,总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。,2024/10/1,25,2.5 顺序表和单链表的比较若线性表需频繁查找却很少进行插,