《常用软件算法基础》课件-第章 学生基本信息管理（顺序表）

第三章学生基本信息管理教学目标：线性表的定义和性质顺序表的定义和性质顺序表的存储结构和相关操作学生基本信息管理的相关业务重点：学生基本信息管理业务实现难点：学生基本信息管理业务实现1、模块功能学生基本信息管理界面如下：2.线性表的基本概念和操作基本概念：线性表：n个数据元素的有限序列（线性表的数据元素在不同的环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）表长：线性表中数据元素的个数n（n>=0）。空表：n=0时的线性表称为空表。位序：非空表中数据元素ai是此表的第i个元素，则称i为ai在线性表中的位序。2.线性表的基本概念和操作

线性表的实例：例1英文字母表（A,B,C,…..Z)是一个线性表例数据元素例2某班学生的信息2.线性表的基本概念和操作结构特点：在数据元素的非空有限集中：存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2.线性表的基本概念和操作线性表的运算：

1.取元素：求线性表中指定数据元素的位序。2.插入：在线性表两个确定的元素之间插入一个新的数据元素。3.删除：删除表中某个数据元素。4.求表长：求线性表中数据元素的个数。5.查找：查找表中满足某种条件的数据元素。6.合并：把两个线性表合并成一个线性表。7.分拆：把一个线性表分拆成多个线性表。8.排序：按一个或多个数据项值的递增或递减次序重新排列表中数据元素。2、顺序表的基本概念和特点顺序表——线性表的顺序存储内涵：线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。特点：1.存储单元地址连续（需要一段连续空间）。2.逻辑上相邻的数据元素其物理地址也相邻。3.随机存储。4.存储密度大（100%）a1a2…aiai+1…anLOC(a1)LOC(a2)LOC(ai)LOC(ai+1)LOC(an)空闲区域LOC(a1)+(maxlen-1)*k线性表的顺序存储结构是一种随机存取的存储结构2、顺序表：存储结构示意图3、业务实现—总体描述学生基本信息管理模块，主要实现学生基本信息的增、删、改、查以及保存的功能。整个模块的设计和实现的思路如下：创建顺序表类，用以实现学生基本信息顺序表的管理。创建学生基本信息管理业务类，用以实现学生信息顺序表的增、删、改等的业务处理。具体的步骤如下：从通用模块层中，获取学生基本信息，并初始化学生基本信息顺序表。在学生信息查询方法中，给定学生的id，找到对应的学生信息进行返回。在增加学生信息方法中，在学生基本信息顺序表指定位置i，添加学生的信息elem。在删除学生信息方法中，在学生基本信息顺序表中，删除指定位置i的学生信息。在修改学生信息方法中，在学生基本信息顺序表中，修改指定学生id的信息。在保存方法中，实现对学生基本信息顺序表发生增、删、改后的信息保存。3、业务实现—顺序表类创建学生基本信息顺序表类，用以实现学生信息数据在顺序表中的增、删、改的操作。该类的主要成员包括：Student_info[]Data：一维无界数组，用以构建学生基本信息顺序表Length：用以记录顺序表中，实际的学生信息个数。

publicclassnode//创建顺序表类{ publicStudent_infoData[];//定义顺序表

publicintLength; //记录顺序表元素的个数

publicnode() { }

}3、业务实现—业务处理类学生基本信息业务管理类：publicclassSquential{publicintMax;//定义数组的最大长度

publicnodeL=newnode();//定义顺序表对象

StudentMangerBa=newStudentManger();//创建数据控制层对象

publicSquential(){Init();//初始化顺序表及其各个元素 }publicvoidInit(){…}//初始化顺序表及其各个元素

publicintSearch(Student_infoelem){…}//根据学生Id查找对于学生的信息publicintInsert(inti,Student_infoelem){…}//在顺序表第i个学生前插入学生信息publicStudent_infoDelete(inti){…}//删除第i个学生的信息

publicintModefy(Student_infoelem){…}//修改学生的信息

publicintsave(){…}//将增、删、改后的学生信息保存到数据库中}

3、业务实现—信息初始化学生基本信息初始化：通过学生数据控制层对象StudentManger获取学生的基本信息。初始化顺序表的空间大小，以及初始顺序表长度。从数据库中提取的学生信息，逐个初始化顺序表的元素。publicvoidInit(){//顺序表的初始化

Max=Ba.Max+100;L.Data=newStudent_info[Max];//为顺序表分配内存，多分配100用于增、删等操作

L.Length=0;for(inti=0;i<Ba.Max;i++)//为顺序表每个元素赋值

{ L.Data[i]=Ba.base_info[i]; L.Length++;}}

3、业务实现—信息查找学生基本信息查找：对顺序表中每个元素进行循环。逐个查找每个学生元素的id与给定学生的id是否相同，若相同则找到返回相关信息，否则继续循环查找。如果循环完仍然未找到，返回0。 publicintSearch(Student_infoelem) {//在学生顺序表中，对给定学生id进行元素的查找

for(inti=0;i<L.Length;i++) { if(L.Data[i].st_id==elem.st_id) { elem=L.Data[i]; returni+1; } } return0; }

3、业务实现—新增学生含义

含义：

要在学生顺序表中，进行新增学生操作，在第i个学生基本信息前插入一个学生信息，实际上是指在顺序表下标为i-1和i的结点之间插入一个学生elem的新结点，使长度为n的顺序表变成长度为n＋1的顺序表，结点和之间的逻辑关系也发生了改变，因此必须向后顺序移动结点，以便为结点elem让出位置。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x3、业务实现—新增学生流程图步骤：获取现有顺序表的长度n，判断插入位置i是否合法，不合法返回false。判断i是否超越所定义顺序表的最大值，若越界返回false。如是在顺序表末尾插入学生信息，直接将信息插入，顺序表长度自加，返回true。将……之间的所有结点依次后移，为新元素让出第i个位置。将新结点elem插入到第i个位置。表长Length自加，返回true。3、业务实现—新增学生实现 publicintInsert(inti,Student_infoelem) {//在顺序表中的第i个数据元素之前插入数据元素elem intj,n; n=L.Length; if(i<1||i>(n+1))//用以判断所插入的位置是否合法

{ return-1; } if(n>=Max)//用以判断所插入的位置是否越界

{ return-1; } if(i==n+1)//若插入的位置在顺序表末尾，直接插入

{ L.Data[i-1]=elem; L.Length++; returni; } for(j=n;j>=i;j--)//移动所要插入位置后面的元素

L.Data[j]=L.Data[j-1]; L.Data[j]=elem;//实现输入学生信息的插入

L.Length++; returni; }

3、业务实现—删除学生含义

含义：删除学生的基本信息是指，在学生基本信息顺序表结点删除下标为i学生的结点信息，使得长度为n的顺序表，变成长度为n-1的顺序表，结点和之间的逻辑关系也发生了改变，因此必须向前顺序移动结点。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+23、业务实现—删除学生流程图步骤：1、获取学生基本信息表的长度，判断所要删除结点位置是否合法，不合法，返回false。2、获取所要删除的学生基本信息。3、将第i个学生后面的学生信息……之间的结点顺序依次向上移动。并使表长length自减。3、业务实现—删除学生实现publicStudent_infoDelete(inti) {//在顺序表中，删除第i个数据元素，并返回学生信息

intj,n; Student_infoelem; n=L.Length; if(i<1||i>n)//判断所要删除的元素位置是否合法

{ returnnull; } elem=L.Data[i-1];//获取所要删除的学生信息

for(j=i-1;j<n-1;j++)//将要删除的学生后面的学生信息前移，使之构成新的顺序表

L.Data[j]=L.Data[j+1]; L.Length--;//顺序表的长度减一

returnelem; }

3、业务实现—修改学生含义

含义： 修改学生的基本信息是指：对特定学生id的基本信息发生修改，在顺序表中作相应的变化，具体的实现步骤如下：从学生顺序表中，进行循环，逐个提取学生基本信息中的学生id。判断所提取的学生id与所要修改的学生id是否一致。如果一致，进行学生信息的修改，并返回true。若不一致，继续循环，循环完毕仍未找到，返回false。3、业务实现—修改学生实现 publicintModefy(Student_infoelem) {//对指定学生id，进行学生信息修改

intj; for(j=0;j<L.Length;j++)//在顺序表中，进行循环逐个比较学生id是否存在。

{ if(L.Data[j].st_id==elem.st_id)//若学生id存在

{ L.Data[j]=elem;//实现学生信息修改

returnj;//返回修改成功

} } return-1;//返回修改失败

}

4、性能分析—顺序表插入算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：4、性能分析—顺序表插入算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低4、性能分析

顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充5、实践指导【实验内容】学生在实验1所制作的表和数据库访问层封装的基础上，用所学的顺序表的思想，完成对基本信息的增、删、改、查的实现。1．创建和实现实体基本信息顺序表节点类（如学生基本信息节点类Node）。2．创建和实现实体基本信息顺序表管理业务类（如学生基本信息顺序表管理类，Squential）。3．创建和实现实体顺序表业务管理类的界面实现（如学生基本信息管理界面）。5、实践指导【实验步骤】根据业务层的学生基本信息节点类Node，完成学生所设计实体顺序表节点类实现。根据业务层学生基本信息管理类Squential，完成学生所设计实体基本信息管理业务类的实现。参照学生信息顺序表的初始化：从数据库访问层获取信息，完成实体顺序表信息的初始化。参照学生信息顺序表的查找：依据所设计实体的主键，完成所设计实体对象查找。参照学生信息顺序表的增加：完成所设计实体对象信息的添加功能方法。参照学生信息顺序表的删除：完成所设计实体对象信息的删除功能方法。参照学生信息顺序表的修改：完成所设计实体对象信息的修改功能方法。参照学生信息顺序表的保存：完成所设计实体对象信息的保存功能方法5、实践指导【实验步骤】实体信息业务界面的实现。（以学生基本信息管理界面为例）。界面实现参考如下：界面的左半区显示数据库中所有学生的信息，右上半区显示具体所点击学生的信息，右下半区进行学生增、删、改以及保存的操作。点击左半区某一行，在顺序表中，找到对应学生对象信息，显示在右半区。执行增加学生功能时，首先获取当前所选中学生的位置，然后输入要添加的新学生的信息，点击“增加”按钮，实现在顺序表中所选中位置前添加新学生，并保存到数据库中。在执行学生信息修改时，首先选择所要进行修改的学生信息，在右半区进行修改，点击“修改”按钮，实现在顺序表中对应学生信息的修改，并保存到数据库中。在执行删除功能时，首先在左半区选中所要删除的学生信息，点击“删除”按钮，在顺序表中实现对应学生信息的删除，并在数据库中删除该学生的基本信息。在“退出”按钮中，实现本窗体的关闭。5、实践指导窗体打开时的初始化事件：publicpartialclassShunxuFrame:Form{/窗体设计涉及的控件

privateSquentialyw=newSquential();//初始化业务类对象privatevoidShunxuFrame_Load(objectsender,EventArgse){//窗体打开时触发，显示所有数据库中的学生信息

data_student.DataSource=yw.Ba.ds;data_student.DataMember="student";}}5、实践指导DataGrid控件单击查找学生信息：

privatevoiddata_student_Click(objectsender,EventArgse){//DataGridView控件单击时出发

introw=this.BindingContext[yw.Ba.ds,"student"].Position;//获取当前学生所在数据集中的位置

intid=Convert.ToInt16(yw.Ba.ds.Tables["student"].Rows[row][0]);//得到当前学生的idStudent_infotemp=newStudent_info(id);if(yw.Search(reftemp)>0)//查询获取当前学生信息，并显示出来

{txt_id.Text=temp.st_id.ToString();txt_name.Text=temp.st_name;txt_num.Text=temp.st_num;txt_sex.Text=temp.st_sex.ToString();txt_age.Text=temp.st_age.ToString();txt_phone.Text=temp.st_phone.ToString();txt_address.Text=temp.st_address;txt_banji.Text=temp.st_banji.ToString();}}5、实践指导新增学生信息单击事件：

privatevoidbnt_xz_Click(objectsender,EventArgse){//新增学生信息

introw=this.BindingContext[yw.Ba.ds,"student"].Position;//获取当前学生的位置

intid=Convert.ToInt16(yw.Ba.ds.Tables["student"].Rows[row][0]);//获取当前学生的id Student_infoa=newStudent_info(id); Student_infotemp=newStudent_info(); temp.st_id=Convert.ToInt16(txt_id.Text.ToString());//记录新增学生信息

temp.st_name=txt_name.Text.ToString();temp.st_num=txt_num.Text.ToString();temp.st_sex=Convert.ToInt16(txt_sex.Text.ToString());temp.st_age=Convert.ToInt16(txt_age.Text.ToString());temp.st_address=txt_address.Text.ToString();temp.st_phone=Convert.ToInt32(txt_phone.Text.ToString());temp.st_banji=Convert.ToInt16(txt_banji.Text.ToString());yw.Insert(yw.Search(refa),temp);//将新增学生信息插入到顺序表中

yw.Save_data(a,1);//将新增学生信息保存到数据库中

}5、实践指导学生信息删除事件：

privatevoidbnt_sc_Click(objectsender,EventArgse){//删除指定位置的学生位置

introw=this.BindingContext[yw.Ba.ds,"student"].Position;//获取要删除当前学生在数据集中位置

intid=Convert.ToInt16(yw.Ba.ds.Tables["student"].Rows[row][0]);//获取要删除学生的idStudent_infoa=newStudent_info(id);inti=yw.Search(refa);//获取所删除学生在顺序表中的位置

a=y