第三章鏈表教學目標：掌握鏈表的基本概念和存儲結構掌握單向鏈表的概念和操作。利用單向鏈表實現學生成績信息的管理。了解循環鏈表和雙向鏈表的基本概念和操作。重點：學生成績信息管理的單向鏈表的實現。難點：單向鏈表操作的實現算法和流程。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