C語言鏈表ppt課件

《C語言鏈表ppt課件》由會員分享，可在線閱讀，更多相關《C語言鏈表ppt課件（28頁珍藏版）》請在裝配圖網上搜索。

1、11.7 用指針處理鏈表用指針處理鏈表1.鏈表概述鏈表概述1)動態數據結構概念 數組和結構體是定長數據結構，而鏈表、堆棧、隊列、樹、圖等是執行時大小可變的動態數據結構。鏈表是連成一行連成一行的數據項集合，每一個數據項(元素)稱為節點，可以在鏈表中的任意位置進行節點插入或刪除操作，使鏈表數據項的個數隨之增加或減少。12)鏈表的構成單向鏈表圖示：單向鏈表圖示：1048 1370 1012 頭節點 表內節點 尾節點 210189.513702304901012291885NULL1048head其中：其中：各節點是相同的結構體類型，該類型有三個成員；head是指針變量，存放鏈表的頭節點指針1048；

2、各節點應包含一個指針成員存放下一節點的地址；各節點存儲有可能不連續，但各節點邏輯上連續。23)節點的構成上圖每個節點具有如下結構體類型：struct student long num;float score;structer student *next;/*鏈節成員*/其中：其中：成員num、score用于存放一個節點的具體數據；成員next是指針類型，用于存放下一節點指針，最后一個節點的next 成員存放空指針NULL；成員next是指向與自身同一類型的結構，這種結 構稱為自引用結構。(只有指針成員可自引用)節點是在運行時動態生成的。34)動態內存分配和釋放 建立和維護動態數據結構需要實現動

3、態內存分配；如在鏈表中插入節點需要先申請一段存儲區域，而刪除一個節點需要釋放該節點原先占用的存儲區域，這可由標準函數實現。內存分配函數原形：內存分配函數原形：void*malloc(unsigned size);功能：功能：申請長度為size個字節的內存空間；若申請 成功，返回存儲塊起始指針，該指針類型為 void*；否則返回空指針(NULL)。內存釋放函數原形：內存釋放函數原形：void free(void*p);功能：功能：釋放p所指向的內存塊。包含文件：包含文件：malloc.h、stdlib.h中均有其原型聲明。45)采用鏈表的意義與定長數據結構數組相比，鏈表能更好地利用內存，按需分配

4、和釋放存儲空間。在鏈表中插入或刪除一個節點，只需改變某節點“鏈節”成員的指向，而不需要移動其它節點，相對數組元素的插入和刪除效率高。即：鏈表特別適合于對大線性表頻繁插入和刪除元素、或成員數目不定的數據結構。56)鏈表的類型單鏈表：單鏈表：每個節點只有一個指向后繼節點的指針雙向鏈表：雙向鏈表：每個節點有兩個用于指向其它節點的指針；一個指向前趨節點，一個指向后繼節點循環鏈表：循環鏈表：使最后一個節點的指針指向第一個節點62.單鏈表的建立和輸出單鏈表的建立和輸出建立鏈表的準備工作建立鏈表的準備工作:1)定義鏈表的節點類型；2)定義與節點同類型的鏈表頭指針變量head并賦值0，表示鏈表在建立之前是空的

5、；3)定義與節點同類型的工作指針變量p1、p2。7建立鏈表的步驟：建立鏈表的步驟：1)開辟第一個節點的存儲區域，使head、p1、p2 指向第一個節點，并輸入第一個節點數據；210189.5headp1p2操作：操作：len=sizeof(struct student);p1=(struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);head=p2=p1;82)開辟下一節點的存儲區域，使p1指向新節點、輸入新節點數據，并將上一個節點的next成員 指向新節點；210189.5headp1p22304901048操作：操作：p1=(

6、struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);p2-next=p1;p2=p1;/*使p2也指向新節點*/13701370p2p193)重復第2步，建立并鏈接多個節點直至所需長度，將末尾節點的next成員賦值0。210189.51370headp2230490291885p2NULL1048 1370p110121012p2p1操作：操作：p1=(struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);p2-next=p1;p2=p1;/*使p2也指向新節點

7、*/p2-next=NULL;/*末尾節點next賦值0*/10【例】建立并輸出有3名學生數據的單鏈表。#include /*包含NULL的定義*/#include#define N 3struct student /*結構體類型定義*/long num;float score;struct student*next;/*自引用結構體指針*/;void main()11void main()struct student*head,*p1,*p2;int i,len;sqrt(5.5);/*TC激活浮點運算*/head=NULL;/*head不指向任何位置*/len=sizeof(struct

8、student);/*求類型長*/for(i=1;inum,&p1-score);if(i=1)head=p2=p1;/*指向首節點*/else p2-next=p1;p2=p1;/*節點鏈接*/if(i=N)p2-next=NULL;/*標記末尾節點*/12 void main()for(i=1;i=N;i+)/*建立鏈表*/for(i=1;inext;/*p1指向下一節點*/printf(%d:num=%ld,score=%5.2fn,i,p1-num,p1-score);/*main*/13【例】將上題利用函數實現，并求平均成績。定義如下函數：定義如下函數：建立鏈表函數:struct s

9、tudent*create(void);輸出鏈表函數:void plink(struct student*head);求平均值函數:float averf(struct student*head);函數間信息傳遞：函數間信息傳遞：主函數createplinkaverf無參頭指針頭指針無返回值平均值頭指針14#include#include#define N 3struct student /*全局結構類型*/long num;float score;struct student*next;void main()15void main()struct student*head,*create(v

10、oid);void plink(struct student*head);float averf(struct student*head);int i,len;float aver;sqrt(5.5);clrscr();/*TC中使用 head=NULL;head=create();/*返回鏈表頭指針*/plink(head);aver=averf(head);/*返回平均值*/printf(Average=%5.2fn,aver);16struct student *create()struct student*head,*p1,*p2;int i,len;len=sizeof(struct

11、 student);for(i=1;inum,&p1-score);if(i=1)head=p2=p1;/頭節點 else p2-next=p1;p2=p1;/中間節點 if(i=N)p2-next=NULL;/尾節點 return(head);/返回鏈表頭指針 17void plink(struct student*head)/*輸出各節點*/struct stduent*p;int i;for(i=1;inext;printf(%d:num=%ld,score=%5.2fn,i,p-num,p-score);return;PP18float averf(struct student*hea

12、d)struct student*p;float sum=0;int c=0;p=head;/*使p指向首節點*/while(p!=NULL)c+;/*c統計節點數*/sum=sum+p-score;p=p-next;return(sum/c);/*返回平均值*/1913703.節點的刪除節點的刪除步驟：步驟：1)從頭節點開始按查找關鍵字查找要刪除的節點；2)找到，則將要刪除節點的“鏈節”成員賦給前一節點的“鏈節”成員，使刪除的節點脫離鏈表。若：要刪除節點為首節點，則將首節點“鏈節”成 員賦給鏈頭指針變量。3)釋放已被刪除節點占用的空間。1048 1012210189.51370head230

13、4901012pNULL1048291885101220【例】按上例刪除指定學號的節點struct student*del(struct student*head,long n)struct student*p1,*p2;/*n：要刪除學號*/p1=head;if(p1-num=n)head=p1-next;/*刪除首節點*/else do p2=p1;p1=p1-next;/*繼續找*/while(p1!=NULL&p1-num!=n);if(p1-num=n)p2-next=p1-next;/*找到*/else printf(Not be found!n);/*未找到*/free(p1);

14、/*釋放被刪除節點的存儲區*/return(head);/*返回頭指針*/21void plink(struct student*head)/*更具通用性*/struct student*p;p=head;while(p!=NULL)printf(num=%ld,score=%5.2fn,p-num,p-score);p=p-next;return;注：注：本形式的鏈表輸出函數具有通用性，可適應由于刪除或插入節點引起的鏈表長度的變化。224.節點的插入節點的插入 插入可分為隨意插入和按順序插入，隨意插隨意插入入包括插入到頭部、尾部或中間指定位置；按順按順序插入序插入是指按某關鍵字的順序插入，而

15、在插入前鏈表必須已按該關鍵字進行了排序。按順序插入的步驟：按順序插入的步驟：1)開辟待插入節點的存儲區域并輸入數據；2)查找插入位置：從鏈表首節點開始按關鍵字成 員與待插入節點相同成員進行比較，直到確定了插入位置；233)將插入位置前一節點的“鏈節”成員賦給待插入節 點的“鏈節”成員；若：插入點在鏈頭，則將頭指針賦給待插入節點的 “鏈節”成員；4)將待插入節點的指針賦給前一節點“鏈節”成員；若：插入點在鏈頭，先將頭指針賦給插入節點的指針域，再將待插入節點的指針賦給頭指針變量。210189.51370head 10482304901012241478 1048 1370 101210122680

16、2680291885NULL24【例】按上例在鏈表中按學號順序插入節點插入函數：插入函數：struct student*insert(struct student*head)struct student*p0,*p1,*p2;long n;int len;len=sizeof(struct student);p0=(struct student*)malloc(len);/*申請新節點*/printf(Enter num,score to insert:);scanf(%ld,%f,&p0-num,&p0-score);n=p0-num;/*產生學號副本n*/p1=head;/*從首節點開始查

17、找*/25 p1=head;/*插入在頭部*/if(nnum)p0-next=head;head=p0;else do /*查找插入位置*/p2=p1;p1=p1-next;while(p1!=NULL&np1-num);p0-next=p2-next;/*插入在其余位置*/p2-next=p0;return(head);/*insert*/26【例】編寫一個通用的函數，可根據需要建立任意節點數的鏈表。struct student *creat()/*無參有返回值*/struct student*head=NULL,*p1,*p2;int len;long n;float s;len=size

18、of(struct student);while(1)/*循環次數不確定*/printf(Enter number,score:);scanf(%ld,%f,&n,&s);if(n=0)break;/*輸入0表示數據結束*/p1=(struct student*)malloc(len);return(head);27 while(1)printf(Enter number,score:);scanf(%ld,%f,&n,&s);if(n=0)break;/*以0表示數據結束*/p1=(struct student*)malloc(len);p1-num=n;p1-score=s;/*轉存入節點*/if(head=NULL)head=p2=p1;else p2-next=p1;p2=p1;p2-next=NULL;/*末尾鏈節成員賦空*/return(head);/*返回鏈表頭指針*/*creat*/28