6.2.5鏈表 - 鏈表-教學(xué)課件

第六章

結(jié)構(gòu)與鏈表第2節(jié)鏈表1程序解析2鏈表的概念3單向鏈表的常用操作1程序解析例

建立一個(gè)學(xué)生成績信息（包括學(xué)號(hào)、姓名、成績）的單向鏈表，學(xué)生記錄按學(xué)號(hào)由小到大順序排列，要求實(shí)現(xiàn)對(duì)成績信息的插入、修改、刪除和遍歷操作。mainCreate_Stu_DocInsertDocDeleteDocPrint_Stu_DocInsertDoc1程序解析structstud_node{/*鏈表結(jié)點(diǎn)類型*/intnum;charname[20];intscore;structstud_node*next;};structstud_node*Create_Stu_Doc();/*新建鏈表*/structstud_node*InsertDoc(structstud_node*head,structstud_node*stud);/*插入*/structstud_node*DeleteDoc(structstud_node*head,intnum);/*刪除*/voidPrint_Stu_Doc(structstud_node*head);/*遍歷*/2鏈表的概念鏈表是一種常見而重要的動(dòng)態(tài)存儲(chǔ)分布的數(shù)據(jù)結(jié)構(gòu)。它由若干個(gè)同一結(jié)構(gòu)類型的“結(jié)點(diǎn)”依次串接而成。鏈表分單向鏈表和雙向鏈表。頭指針結(jié)點(diǎn)尾結(jié)點(diǎn)頭結(jié)點(diǎn)2鏈表的概念通常使用結(jié)構(gòu)來定義單向鏈表結(jié)點(diǎn)的數(shù)據(jù)類型：structstud_node{intnum;charname[20];intscore;

structstud_node*next;};結(jié)構(gòu)的遞歸定義

2鏈表的概念與數(shù)組比較在用數(shù)組存放數(shù)據(jù)時(shí)，一般需要事先定義好固定長度的數(shù)組，在數(shù)組元素個(gè)數(shù)不確定時(shí)，可能會(huì)發(fā)生浪費(fèi)內(nèi)存空間的情況。鏈表是動(dòng)態(tài)存儲(chǔ)分布的數(shù)據(jù)結(jié)構(gòu)。根據(jù)需要?jiǎng)討B(tài)地開辟內(nèi)存空間，可以比較自由方便地插入新元素（結(jié)點(diǎn)），故使用鏈表可以節(jié)省內(nèi)存，操作效率高。2鏈表的概念動(dòng)態(tài)分配相關(guān)函數(shù)void*malloc(unsignedsize)

功能：在內(nèi)存的動(dòng)態(tài)存貯區(qū)中分配一塊長度為size的連續(xù)空間。返回值：指針，存放被分配內(nèi)存的起始地址。若未申請(qǐng)到空間，則返回NULL(0)。例如：(int*)malloc(sizeof(int))(structstudent*)malloc(sizeof(structstudent))voidfree(void*ptr)功能：釋放由malloc()申請(qǐng)的動(dòng)態(tài)內(nèi)存空間，ptr存放該空間的首地址。返回值：無。例如：free(p);3單向鏈表的常用操作1.鏈表的建立2.鏈表的遍歷3.插入結(jié)點(diǎn)4.刪除結(jié)點(diǎn)3單向鏈表的常用操作1.鏈表的建立3單向鏈表的常用操作1.鏈表的建立head=tail=NULL;scanf("%d%s%d",&num,name,&score);while(num!=0){

p=(structstud_node*)malloc(size);p->num=num;strcpy(p->name,name);p->score=score;

p->next=NULL;if(head==NULL)head=p;elsetail->next=p;tail=p;scanf("%d%s%d",&num,name,&score);}頭部插入法：p->next=head;head=p;尾部插入3單向鏈表的常用操作2.鏈表的遍歷for(ptr=head;ptr!=NULL;ptr=ptr->next)printf("%d\t%s\t%d\n",ptr->num,ptr->name,ptr->score);先連:s->next=ptr->next;后斷:ptr->next=s;headptrs3單向鏈表的常用操作3.插入結(jié)點(diǎn)ptr2=ptr1->next;先接:ptr1->next