第六章

結構與鏈表第2節鏈表1程序解析2鏈表的概念3單向鏈表的常用操作1程序解析例

建立一個學生成績信息（包括學號、姓名、成績）的單向鏈表，學生記錄按學號由小到大順序排列，要求實現對成績信息的插入、修改、刪除和遍歷操作。mainCreate_Stu_DocInsertDocDeleteDocPrint_Stu_DocInsertDoc1程序解析structstud_node{/*鏈表結點類型*/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鏈表的概念鏈表是一種常見而重要的動態存儲分布的數據結構。它由若干個同一結構類型的“結點”依次串接而成。鏈表分單向鏈表和雙向鏈表。頭指針結點尾結點頭結點2鏈表的概念通常使用結構來定義單向鏈表結點的數據類型：structstud_node{intnum;charname[20];intscore;

structstud_node*next;};結構的遞歸定義

2鏈表的概念與數組比較在用數組存放數據時，一般需要事先定義好固定長度的數組，在數組元素個數不確定時，可能會發生浪費內存空間的情況。鏈表是動態存儲分布的數據結構。根據需要動態地開辟內存空間，可以比較自由方便地插入新元素（結點），故使用鏈表可以節省內存，操作效率高。2鏈表的概念動態分配相關函數void*malloc(unsignedsize)

功能：在內存的動態存貯區中分配一塊長度為size的連續空間。返回值：指針，存放被分配內存的起始地址。若未申請到空間，則返回NULL(0)。例如：(int*)malloc(sizeof(int))(structstudent*)malloc(sizeof(structstudent))voidfree(void*ptr)功能：釋放由malloc()申請的動態內存空間，ptr存放該空間的首地址。返回值：無。例如：free(p);3單向鏈表的常用操作1.鏈表的建立2.鏈表的遍歷3.插入結點4.刪除結點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.插入結點ptr2=ptr1->next;先接:ptr1->next