C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析
鏈表的概念:鏈表是一種動態(tài)存儲分布的數(shù)據(jù)結(jié)構(gòu),由若干個同一結(jié)構(gòu)類型的結(jié)點依次串連而成。
鏈表分為單向鏈表和雙向鏈表。
鏈表變量一般用指針head表示,用來存放鏈表首結(jié)點的地址。
每個結(jié)點由數(shù)據(jù)部分和下一個結(jié)點的地址部分組成,即每個結(jié)點都指向下一個結(jié)點。最后一個結(jié)點稱為表尾,其下一個結(jié)點的地址部分的值為NULL(表示為空地址)。
特別注意:鏈表中的各個結(jié)點在內(nèi)存中是可以不連續(xù)存放的,具體存放位置由系統(tǒng)分配。
例如:int *ptr ;
因此不可以用ptr++的方式來尋找下一個結(jié)點。
使用鏈表的優(yōu)點:
不需要事先定義存儲空間大小,可以實時動態(tài)分配,內(nèi)存利用效率高;
可以很方便地插入新元素(結(jié)點) ,使鏈表保持排序狀態(tài),操作效率高。
下面用課本的例子來講解:
/*用鏈表實現(xiàn)學(xué)生成績信息的管理*/ #include<stdio.h> #include<stdlib.h> #include<string.h> struct stud_node{ int num; char name[24]; int score; struct stud_node *next; }; struct stud_node *Create_Stu_Doc(); /*新建鏈表*/ struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud); /*插入*/ struct stud_node *DeleteDoc(struct stud_node *head,int num); /*刪除*/ void Print_Stu_Doc(struct stud_node *head); /*遍歷*/ int main(void) { struct stud_node *head,*p; int choice,num,score; char name[20]; int size = sizeof(struct stud_node); do{ printf("1:Create\n 2:Insert\n 3: Delete\n 4:Print\n 0:Exit\n"); scanf("%d",&choice); switch(choice){ case 1: head = Create_Stu_Doc(); break; case 2: printf("Input num,name and score:\n"); scanf("%d %s %d",&num,name,&score); p = (struct stud_node *)malloc(size); p->num = num; strcpy(p->name,name); p->score = score; head = InsertDoc(head,p); break; case 3: printf("Input num:\n"); scanf("%d",&num); head = DeleteDoc(head,num); break; case 4: Print_Stu_Doc(head); break; case 0: break; } } while(choice != 0); return 0; } /*新建鏈表*/ struct stud_node *Create_Stu_Doc(){ struct stud_node *head,*p; int num,score; char name[20]; int size = sizeof(struct stud_node); head = NULL; printf("Input num,name and score:\n"); scanf("%d %s %d",&num,name,&score); while(num != 0){ p=(struct stud_node *)malloc(size); p->num = num; strcpy(p->name,name); p->score = score; head = InsertDoc(head,p); /*調(diào)用插入函數(shù)*/ scanf("%d %s %d",&num,name,&score); } return head; } /*插入操作*/ struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud){ struct stud_node *ptr,*ptr1,*ptr2; ptr2 = head; ptr = stud; /*ptr指向待插入的新的學(xué)生記錄結(jié)點*/ /*原鏈表為空鏈表時的插入*/ if(head == NULL){ head = ptr; head->next = NULL; }else{ while((ptr->num > ptr2->num)&&(ptr2->next != NULL)){ ptr1 = ptr2; ptr2 = ptr2->next; /*ptr1,ptr2各往后移一個結(jié)點*/ } if(ptr->num <= ptr2->num){ /*在ptr1與ptr2之間插入新結(jié)點*/ if(head == ptr2){ head=ptr; } else{ ptr1->next = ptr; ptr->next = ptr2; } } else{ ptr2->next = ptr; /*新插入結(jié)點成為尾結(jié)點*/ ptr->next =NULL; } } return head; } /*刪除操作*/ struct stud_node *DeleteDoc(struct stud_node *head,int num){ struct stud_node *ptr1,*ptr2; /*要被刪除結(jié)點為表頭結(jié)點*/ while(head != NULL && head->num==num){ ptr2=head; head=head->next; free(ptr2); } if(head==NULL){ return NULL; } /*鏈表為空*/ /*要被刪除結(jié)點為非表頭結(jié)點*/ ptr1=head; ptr2=head->next; /*從表頭的下一個結(jié)點搜索所有符合刪除要求的結(jié)點*/ while(ptr2 != NULL){ if(ptr2->num == num)/*ptr2所指結(jié)點符合刪除要求*/{ ptr1->next=ptr2->next; free(ptr2); } else{ ptr1 = ptr2; /*ptr1后移一個結(jié)點*/ ptr2 = ptr1->next; /*ptr2指向ptr1的后一個結(jié)點*/ } } return head; } /*遍歷操作*/ void Print_Stu_Doc(struct stud_node *head){ struct stud_node *ptr; if(head==NULL){ printf("\nNo Records\n"); return; } printf("\nThe Students'Records Are:\n"); printf("Num\t Name\t Score\t"); for(ptr=head;ptr!=NULL;ptr=ptr->next){ printf("%d\t%s\t%d\n",ptr->num,ptr->name,ptr->score); } }
申請大小為 struct stud_node 結(jié)構(gòu)的動態(tài)內(nèi)存空間,新申請到的空間要被強制類型轉(zhuǎn)換成
struct stud_node 型的指針,并保存到指針變量p中,如下:
struct stud_node*p;
p = ( struct stud_node *)malloc(sizeof( struct stud_node ));
鏈表的建立:
上面程序中鏈表結(jié)點是按照學(xué)生學(xué)號排序的,若向根據(jù)數(shù)據(jù)輸入的順序來建立鏈表,如下:
/*按輸入順序建立單向鏈表*/ struct stud_node *Create_Stu_Doc(){ int num,score; char name[20]; int size = sizeof(struct stud_node); struct stud_node *head,*tail,*p; head=tail=NULL; printf("Input num,name and score:\n"); scanf("%d %s %d",&num,name,&score); while(num!=0){ p=(struct stud_node *)malloc(size); p->num = num; strcpy(p->name,name); p->score = score; p->next = NULL; if(head == NULL){ head = p; }else{ tail->next=p; /*把原來鏈表的尾結(jié)點的next域指向該新增的結(jié)點*/ tail=p; } scanf("%d %s %d",&num,name,&score); } return head; }
由于按數(shù)據(jù)輸入建立鏈表時,新增加的結(jié)點會加在鏈表末尾,所以該新增結(jié)點的 next 域應(yīng)置成 NULL : p->next = NULL.
鏈表的遍歷:
為了逐個顯示鏈表每個結(jié)點的數(shù)據(jù),程序要不斷從鏈表中讀取結(jié)點內(nèi)容,顯然需要用到循環(huán)。
在for語句中將ptr的初值置為表頭head,當(dāng)ptr不為NULL時循環(huán)繼續(xù),否則循環(huán)結(jié)束。不可以用ptr++來尋找下一個結(jié)點。
鏈表的插入:
插入原則:先連后斷。
首先找到正確位置,然后插入新的結(jié)點。尋找正確位置是一個循環(huán)的過程:從鏈表head開始,把要插入的結(jié)點stud的num分量值與鏈表中結(jié)點的num分量值逐一比較,直到出現(xiàn)要插入結(jié)點的值比第 i 結(jié)點的num分量值大,比第 i+1結(jié)點的分量值小。所以先與第 i+1 結(jié)點相連。再將 i 結(jié)點 與 i+1結(jié)點斷開,并讓 i 結(jié)點與 stud 結(jié)點相連。
鏈表的刪除:
刪除原則:先接后刪。
若被刪除結(jié)點是表頭則 head=head->next ;
其他內(nèi)容省略。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析的文章就介紹到這了,更多相關(guān)C語言 單向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實現(xiàn)學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)學(xué)生成績管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2020-12-12C++學(xué)習(xí)之智能指針中的unique_ptr與shared_ptr
吃獨食的unique_ptr與樂于分享的shared_ptr是C++中常見的兩個智能指針,本文主要為大家介紹了這兩個指針的使用以及智能指針使用的原因,希望對大家有所幫助2023-05-05