《常用软件算法基础》课件-第章 学生成绩信息管理（链表）

第三章链表教学目标：掌握链表的基本概念和存储结构掌握单向链表的概念和操作。利用单向链表实现学生成绩信息的管理。了解循环链表和双向链表的基本概念和操作。重点：学生成绩信息管理的单向链表的实现。难点：单向链表操作的实现算法和流程。1、模块功能学生成绩信息管理界面实现：2.1链表的概念线性表的链式存储结构，也称为链表。其存储方式是：在计算机内存中利用存储单元（不要求连续）来存放结点的值及它在内存中的地址，各个结点的存放顺序及位置可以以任意顺序进行，原来相邻的结点在计算机内存中的存储位置不一定相邻，从一个元素查找下一个元素必须通过地址（指针）才能实现。an^头指针a1a2头节点元素数据域指针域…尾结点2.2链表的分类：1.单链表2.循环链表3.双向链表4.双向循环链表an^a1a2…Lana1a2…La1a2a2L…a1a2a2L…2.3单链表的基本概念链表中，如果每个结点中只包含一个指针域，称这种链表为线性链表或单链表。单链表可由头指针唯一确定an^a1a2…L2.3单链表的基本概念头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^2.4单向链表概念：实例RedorangeWhiteYellowGreen例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)198NULL100120121147数据域指针域WhiteblueorangeGreenRedYellow存储地址100120121147158198158H头指针blue^2.5单链表的存储线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点

数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点3.学生信息管理问题描述： 利用单向链表的特性，实现学生信息管理系统中学生信息的管理。主要的操作包括：1、实现学生信息的初始化。2、统计学生的总人数。3、判断指定学生的信息是否录入。4、删除指定位置的学生信息。5、在已有的班级学生信息中，添加新的学生信息。3.学生成绩信息管理业务实现学生成绩信息管理模块，主要实现学生成绩信息的增、删、改、查以及保存的功能。整个模块的设计和实现的思路如下：创建学生成绩单向链表类，用以实现单个学生成绩信息的记录。创建学生成绩信息管理业务类，用以实现学生成绩信息单向链表的增、删、改等的业务处理。具体的步骤如下：从通用模块层中，获取学生成绩信息，并初始化学生成绩单向链表对象。在学生成绩查询方法中，给定学生的id，找到对应的学生成绩信息进行返回。在增加学生成绩方法中，在学生成绩单向链表中指定位置i，添加学生成绩信息elem。在删除学生成绩方法中，在学生成绩单向链表中，删除指定位置i的学生成绩信息。在修改学生成绩方法中，在学生成绩单向链表中，修改指定学生id成绩信息。在保存方法中，实现对学生成绩单向链表发生增、删、改后的信息保存。3.1业务实现---链表结点类创建学生成绩信息单向链表结点类，用以实现学生成绩信息数据在单向链表中的增、删、改的管理。该类的主要成员包括：Student_infoData：数据域，学生信息对象，用以记录学生的基本信息和成绩信息nodeNext：指针域，用以指向下一个学生的结点。

publicclassNode{//链表结点类

publicStudent_infoData;//数据域，记录学生的成绩信息

publicNodenext;//指针域，指向下一学生成绩信息

publicNode() { }}

3.2业务实现---学生成绩业务类学生成绩信息业务类，是应用单向链表的思想，用以实现学生成绩信息的增、删、改、查等操作，主要的成员和方法如下所示：publicclassLink{publicNodeL;//定义链表对象publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicLink(){ Init(); }publicvoidInit(){…}//单向链表的初始化

publicStudent_infoSearch(Student_infoelem){…}//指定学生id，查找对应学生的成绩信息publicintmodify(Student_infoelem){…}//修改指定学生id的成绩信息publicintInsert(inti,Student_infoelem){…}//在指定位置增加学生成绩信息

publicintdelete(inti,Student_infoelem){…}//实现指定位置的学生成绩信息的删除

publicintSave(Student_infoelem，intflag){…}//保存学生成绩信息，在链表中发生增、删、改后进行调用

publicintGet_length(){…}//获取链表的总的结点个数}

3.2.1业务类---链表初始化单向链表创建示意图：^La^pbp3.2.1业务类---链表初始化具体步骤如下：为链表对象L，分配内存空间，并使指针域为空，带头结点的空单向链表创建好。定义局部单向链表对象p，用以创建链表其他学生成绩信息结点。利用数据控制层对象的学生信息数组，逐个读取，初始化单向链表结点，并添加到单向链表中，具体作法如下：逐个循环，为局部学生成绩链表对象p，分配新空间。从数据控制层学生信息数组获取信息，为对象p的数据域赋值。修改局部对象p和成员单向链表对象L的指针域。3.2.1业务类---链表初始化实现流程图：3.2.1业务类---链表初始化代码实现： publicvoidInit() {//单向链表的初始化

Nodep; L=newNode(); //初始化链表对象

L.next=null; for(inti=0;i<Ba.Max;i++)//利用数据库数据对链表进行初始化

{ p=newNode(); //为新结点分配空间

p.Data=newStudent_info();//为结点数据域分配空间

p.Data=Ba.base_info[i]; //为每个结点数据域赋值

p.next=L.next; //修改指针域

L.next=p; } }

3.2.2业务类---学生成绩信息查询该方法是根据所输入的学生id信息，在单向链表中进行查找，返回学生在链表中的位置和该学生的所有信息。具体思路如下：调用该方法之前，先创建学生信息对象elem，并把所要查找的学生id赋值到elem对象的学生id属性st_id。（在C#中应用引用传值，在Java中用对象传值）。声明局部变量intplace=0；用以记录所找id在链表中的位置。声明局部学生成绩信息链表结点p=L；通过p=p.next操作，来实现从链表头到链表尾的搜索。对链表的各个结点进行搜索，判断各个结点的学生id与输入对象elem的学生id是否相等，若相等，表示找到。返回所找学生信息和所在的位置。若循环完毕仍未找到，返回位置null。3.2.2业务类---学生成绩信息查询代码实现：

publicStudent_infoSearch(Student_infoelem) {//指定学生id，查找对应学生的成绩信息

intplace=0; Nodep; p=L; while(p.next!=null)//循环查找

{ p=p.next; place++; if(p.Data.st_id==elem.st_id)//所查找结点学生id与链表结点学生id是否一致

{ elem=p.Data; returnelem;//返回学生成绩对象

} } returnnull; }

3.2.3业务类---学生成绩信息新增新增学生成绩信息的操作示意图：pai-1aixss.next=p.next;p.next=s;3.2.3业务类---学生成绩信息新增具体步骤：将新学生信息x插入到第i个位置上，先找到第ai-1的位置P。将位置P的下一结指针指向插入元素X。让X的下一结点指针指向位置P结点的下一结点。返回。3.2.3业务类---学生成绩信息新增代码实现：

publicintInsert(inti,Student_infoelem){Nodep; //用以记录要进行插入位置的前一个学生的成绩信息结点Nodes; //要进行学生成绩信息插入的结点intj;p=L; j=0;while(p!=null&&j<i-1)//用以寻找指定i位置的学生成绩信息结点

{ p=p.next; j++; }if(p==null)return0;//如插入的位置在表尾之后，插入不成功

s=newNode(); //创建新的学生成绩信息结点

s.Data=elem; //将学生信息载入结点中

s.next=p.next; //实现新学生成绩信息结点的插入

p.next=s; return1;}

3.2.4业务类---学生成绩信息删除删除学生成绩信息操作示意图：pabcp.next=p.next.next;3.2.4业务类---学生成绩信息删除具体步骤：输入所要进行删除的学生成绩信息、和所要删除元素的位置i，以及所要进行返回的元素指针。通过链表循环，找到所要删除结点的前一个结点用指针P来表示。所要删除节点用指针Q来表示。具体操作如下：Q＝P.next;P.next=Q.next;获取所删除结点值，返回结果。3.2.4业务类---学生成绩信息删除流程图：3.2.4业务类---学生成绩信息删除代码实现：

publicStudent_infodelete(inti){//实现指定位置的学生成绩信息的删除Nodep;//用以记录要进行删除位置的前一个学生成绩信息结点Nodeq;//用以记录要进行删除位置的学生成绩信息结点Student_infoelem=newStudent_info();intj=0;p=L;while(p!=null&&j<i-1)//用以寻找要进行删除第i个位置的前一个学生成绩信息结点

{ p=p.next; j++; }if(p.next==null)returnnull; //如果所要删除的位置在表尾之后，删除不成功

q=p.next; //实现指定位置的学生成绩信息从链表中删除

p.next=q.next; elem=q.Data; //用以返回所要删除的学生成绩信息

returnelem; }

3.2.5业务类---学生成绩信息修改该方法用以修改指定学生id的学生成绩信息，实现的思想与学生成绩信息查找相似，其具体实现的代码如下：publicintmodify(Student_infoelem){//对指定学生id的成绩信息，来修改链表中对应结点学生成绩信息

Nodep; p=L; while(p.next!=null) { p=p.next; if(p.Data.st_id==elem.st_id)//所查找结点学生id与链表结点学生id是否一致

{ p.Data=elem; return1; } } return0;}

3.2.6业务类---学生成绩信息保存学生成绩信息的保存是指：在单向链表中进行了增、删、改后，要将学生成绩信息保存到数据库中。在这里我们通过调用数据控制层的save_info（）来实现，具体的代码如下：

publicintSave(Student_infoelem,intflag) {//保存学生成绩信息，在链表中发生增、删、改后进行调用

returnBa.Save_Data(elem,flag); }

4、单向链表特点单向链表特点：它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢5.1知识扩展---单向循环链表循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p.next=NULL循环链表p或p.next=Hhh空表5.1知识扩展---单向循环链表实例计算一个循环链表中结点的个数。算法只需扫描一次链表，同时设立一个计数变量用来计数即可。publicintStudent_all(){//统计学生单向链表总的学生数：即表长

Nodep; //定义局部变量，依次记录学生信息的结点

inti=0; p=L.next; //指向单向链表中第一个学生的结点

while(p!=L)//如果未到单向链表末尾，继续循环

{ i++; //进行累加统计

p=p.next;//指向当前学生的下一个学生

} returni;}

5.2知识扩展---双向链表双向链表（doublelinkedlist）：prior域指向其前驱结点，next指向其后继结点，data域存放结点本身的信息

priorelementnextL空双向循环链表：bcapp.prior.next=p=ir;classNode{publicStudent_infoData;publicNodenext，prior;};5.2知识扩展---双向链表增加结点xSbaP插入：在双向链表L中第i个数据元素前插入元素X算法描述找到第i个元素结点的位置，用指针p表示。插入元素x的位置，用指针s表示。进行插入操作作如下动作：

1、s.prior=p.prior; 2、p.prior.next=s; 3、s.next=p;4、p.prior=s;双向循环链表插入元素的流程图：

开始输入所要插入双向循环链表结构指针L、位置i和插入元素x声明局部单链表指针p和s；赋初值p＝L为指针s分配内存空间；并赋值：s.data=x;返回结果查找单链表中位置i的元素结构指针p？p==L进行元素插入操作：s.prior=p.prior;p.prior.next=s;s.next=p;p.prior=s;5.2知识扩展---双向链表增加结点代码实现：publicintStudent_insert(inti,Student_infoelem){//在学生单向链表中，指定位置插入学生信息

Nodep; //用以记录要进行插入位置的前一个学生的信息结点

Nodes; //要进行学生信息插入的结点

intj;p=L; j=0;while(p!=Link&&j<i-1)//用以寻找指定i位置的学生信息结点

{p=p.next; j++; }if((i>0)&&(j==i-1)) {s=newNode(); //创建新的学生信息结点

s.Data=elem; //将学生信息载入结点中

s.prior=p.prior; //实现新学生信息结点的插入

p.prior=s.prior; s.next=p; p.prior=s; return1; } elsereturn0;//如插入的位置在表尾之后，插入不成功}

5.2知识扩展---双向链表增删除结点bcaPp.prior.next=p.next;p.next.prior=p.prior;删除：删除双向链表中第i个元素。算法描述查找双向链表第i个元素的位置，用指针p表示。判断指针p的位置是否正确。作如下操作：

1、p.prior.next=p.next2、p.next.prior=p.prior3、获取所要删除元素的值，返回结果。5.2知识扩展---双向链表增删除结点的流程图：

开始输入所要删除双向循环链表结构指针L、位置i和返回元素元素指针s声明局部单链表指针p；并初值p＝L进行元素删除操作：p.prior.next=p.next; p.next.prior=p.prior;返回结果查找单链表中位置i的元素结构指针p？p==L获取所删除元素值：s=p.data；5.2知识扩展---双向链表删除结点代码实现：publicStudent_infoStudent_delete(inti){//实现指定位置的学生信息的删除

Nodep;//用以记录要进行删除位置的前一个学生的信息结点

Nodeq;//用以记录要进行删除位置的学生的信息结点

Student_infoelem=newStudent_info（）; intj=0; p=Link; while(p!=null&&j<i-1)//用以寻找要进行删除第i个位置的前一个学生信息结点

{ p=p.next; j++; } if((i>0)&&(j==i-1)) {q=p.next; elem=q.Data; //用以返回所要删除的学生信息

p.prior.next=p.next;//实现指定位置的学生信息从链表中删除

p.next.prior=p.prior; returnelem; } elsereturnnull;//如果所要删除的位置在表尾之后，删除不成功}

6、实践指导【实验内容】学生在实验1所制作的实体表和数据库访问层封装的基础上，用所学的单向链表的思想，完成学生所设计实体对象的管理（如学生成绩基本信息的增、删、改、查的实现）。1．创建和实现实体对象信息单向链表节点类（如学生成绩信息节点类Node）。2．创建和实现实体对象信息单向链表管理业务类（如学生成绩信息链表管理类，Link）。3．创建和实现实体链表业务管理类的界面实现（如学生成绩信息管理界面）。6、实践指导【实验步骤】根据业务层的学生成绩信息节点类Node，完成学生所设计实体对象单向链表节点类的实现。根据业务层学生成绩信息管理类Link，完成学生所设计实体对象信息链表管理业务类的实现。1）、参照学生成绩信息链表的初始化：从数据库访问层获取信息，完成实体链表信息的初始化。2）、参照学生成绩信息单向链表的查找：依据所设计实体的主键，完成所设计实体的单向链表查找。3）、参照学生成绩信息单向链表的增加：完成所设计实体信息单向链表添加功能方法。4）、参照学生成绩信息单向链表的删除：完成所设计实体信息单向链表的删除功能方法。5）、参照学生成绩信息单向链表的修改：完成所设计实体信息单向链表修改功能方法。6）、参照学生成绩信息单向链表的保存：完成所设计实体信息单向链表保存功能方法6、实践指导【实验步骤】

实体信息业务界面的实现。（以学生成绩信息管理界面为例）。界面实现参考如下：界面的左半区显示数据库中所有学生的信息，右上半区显示具体所点击学生成绩信息，右下半区进行学生增、删、改以及保存的操作。点击左半区某一行，在单向链表中，找到对应学生的成绩信息，显示在右半区。执行增加学生成绩功能时，首先获取当前所选中学生的位置，然后输入要添加的新学生的成绩信息，点击“增加”按钮，实现在单向链表中所选中位置前添加新学生成绩信息，并保存到数据库中。执行学生信息修改时，首先在左半区选择所要进行修改的学生成绩信息，在右半区进行学生成绩信息的修改，点击“修改”按钮，实现在单向链表中对应学生成绩信息的修改，并保存到数据库中。在执行删除功能时，首先在左半区选中所要删除的学生信息，点击“删除”按钮，在单向链表中实现对应学生成绩信息的删除，并在数据库中删除该学生的基本信息。在“退出”按钮中，实现本窗体的关闭。6、实践指导窗体打开时的初始化事件：publicpartialclasscjgl

:Form{/窗体设计涉及的控件

Linkyw=newLink();//初始化业务类对象

privatevoidcjgl_Load(objectsender,EventArgse){//窗体打开时，提取所有学生信息显示

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

privatevoiddata_student_Click(objectsender,EventArgse){//当点击datagrideview，控件某行，显示对应的学生成绩信息

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

intid=Convert.ToInt16(yw.Ba.ds.Tables["student"].Rows[row][0]);//获取当前学生的idStudent_infotemp=yw.Search(newStudent_info(id));//查询获取学生成绩信息

if(temp!=null)//将学生成绩信息进行显示

{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();txt_yw.Text=temp.st_yw.ToString();txt_sx.Text=temp.st_sx.ToString();txt_yy.Text=temp.st_yy.ToString();txt_ty.Text=temp.st_ty.ToString();txt_zz.Text=temp.st_zz.ToString();}}6、实践指导新增学生成绩信息按钮单击事件：

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

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

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());temp.st_yw=Convert.ToInt16(txt_yw.Text.ToString());temp.st_sx=Convert.ToInt16(txt_sx.Text.ToString());temp.st_ty=Convert.ToInt16(txt_ty.Text.ToString());temp.st_yy=Convert.ToInt16(txt_yy.Text.ToString());temp.st_zz=Convert.ToInt16(txt_zz.Text.ToString());yw.Insert(row+1,temp);//在单向链表中增加学生成绩信息

yw.Save(temp,1);//新增学生成绩信息保存到数据库中

}6、实践指导学生成绩信息删除事件：

privatevoidbnt_sc_Click(objectsender,EventArgse){introw=this.BindingContext[yw.Ba.ds,"student"].Posit