計算機設計語言(c語言)8

1、第第8章章 結構體結構體8.1 概述概述基本類型（簡單類型）基本類型（簡單類型） 整型、實型、字符型等。整型、實型、字符型等。構造類型構造類型 數(shù)組，數(shù)組中的各元素屬于同一類型。數(shù)組，數(shù)組中的各元素屬于同一類型。當若干個不同類型的數(shù)據(jù)項組成一個組合項時，用什么當若干個不同類型的數(shù)據(jù)項組成一個組合項時，用什么數(shù)據(jù)結構數(shù)據(jù)結構? 例如：例如：一個學生的學號，姓名，姓別，年齡，地址等。一個學生的學號，姓名，姓別，年齡，地址等。C語言中提供了一種實現(xiàn)這種組合的數(shù)據(jù)結構語言中提供了一種實現(xiàn)這種組合的數(shù)據(jù)結構 結構體類型（結構體類型（structure）.它相當于其它高級語言中的它相當于其它高級語言中的“

2、記錄記錄”。結構體類型定義的一般形式。結構體類型定義的一般形式: 第第8章章 結構體結構體 struct 結構體名結構體名 成員表列成員表列 ;結構體內的各個結構體內的各個成員成員（即（即分量分量）。）。對每個成員都應進行類型說明，成員對每個成員都應進行類型說明，成員的定名和類型說明與變量相同。的定名和類型說明與變量相同。分號不能忽略分號不能忽略結構體名的命名規(guī)則與變量名相同結構體名的命名規(guī)則與變量名相同num name sex age score addrBeijing87.518MLi Fun10010例如：例如： 將一個學生的學號、姓名、性別、年齡、成績、地址等項定義將一個學生的學號、姓

3、名、性別、年齡、成績、地址等項定義成一個結構體類型。成一個結構體類型。struct student int num; char name20; char sex ; int age; float score; char addr30; ;成員列表（稱為成員列表（稱為域表域表）分號不能漏掉分號不能漏掉 經過這樣的定義，類型名經過這樣的定義，類型名 struct student 就可以和其它類型（如就可以和其它類型（如 int 等）一樣，用來定義等）一樣，用來定義結構體類型的變量結構體類型的變量。例如例如struct student stu1, stud2; 這個定義就表示定義了一這個定義就表示定

4、義了一種種 類型名類型名為為 struct student 的的結構體類型，結構體類型，struct 是系統(tǒng)關是系統(tǒng)關鍵字，表示開始定義一個結構鍵字，表示開始定義一個結構體類型。體類型。1. 先聲明結構體類型，再定義變量名先聲明結構體類型，再定義變量名 例如例如:struct student int num; char name20; char sex ; int age; float score; char addr30;struct student student1, student2; student1 10001 Zhang Xin M 19 90.5 Shanghaistudent2

5、 10002 Wang Li F 20 98 Beijing 在定義了結構體變量后，系統(tǒng)會為之分配內存單元。例如在定義了結構體變量后，系統(tǒng)會為之分配內存單元。例如 student1 和和 student2 在內存中各占在內存中各占59個字節(jié)（個字節(jié)（2+20+1+2+4+30=59）8.2 定義結構體類型變量的方法定義結構體類型變量的方法聲明結構體類型聲明結構體類型 struct student定義了兩個類型為定義了兩個類型為struct student 的變量的變量student1和和student2為了使用方便，可以用宏定義為了使用方便，可以用宏定義 來定義一個來定義一個符號常量符號常量

6、代表一個結構體類型代表一個結構體類型.例如例如 struct student int num; char name20; char sex ; int age; float score; char addr30;#define STUD struct student STUD student1, student2; 對于較大的程序，對于較大的程序，往往將結構體類型的定義集中放到一個頭文件中往往將結構體類型的定義集中放到一個頭文件中，然后在需用到該結構體類型的源程序中用然后在需用到該結構體類型的源程序中用 #include 命令包含進來。命令包含進來。說明說明: 因為可以定義出許許多多種具體的結

7、構體類型，所以因為可以定義出許許多多種具體的結構體類型，所以定義結構體類型的定義結構體類型的變量變量時，必須時，必須指定具體的結構體類型。指定具體的結構體類型。例如例如struct student stu；struct worker w1, w2; 需要注意：需要注意：結構體類型名不是變量，結構體類型名不是變量，例如：例如：student、worker等不是變量。等不是變量。2. 在定義類型的同時定義變量在定義類型的同時定義變量 例如例如:struct student int num; char name20; char sex ; int age; float score; char add

8、r30; student1, student2; 定義了兩個類型為定義了兩個類型為struct student的變量的變量 student1 和和 student23. 直接定義結構類型的變量（無結構體名）直接定義結構類型的變量（無結構體名） 一般形式為一般形式為: struct 成員表列成員表列 變量名表列變量名表列;注意注意: 這里不出現(xiàn)結構體名這里不出現(xiàn)結構體名!一般形式為一般形式為: struct 結構體名結構體名 成員表列成員表列 變量名表列變量名表列 ;注意注意;的位置的位置關于結構體類型的說明關于結構體類型的說明: “ 類型類型”與與“ 變量變量” 是不同的概念，不能混同。只能對

9、變量賦值、存取是不同的概念，不能混同。只能對變量賦值、存取或運算，而不能對一個類型賦值、存取或運算。在編譯時，對類型是不分配或運算，而不能對一個類型賦值、存取或運算。在編譯時，對類型是不分配空間的，只對變量分配空間?？臻g的，只對變量分配空間。 結構體中的結構體中的成員成員（即（即“域域”）可以單獨使用可以單獨使用，作用和地位相當于普通變量，作用和地位相當于普通變量。 結構體中的成員還可以是一個結構體變量。結構體中的成員還可以是一個結構體變量。 例如例如: struct date int month; int day; int year; ; struct student int num; ch

10、ar name20; int age; float score; struct date birthday; char addr30; student1, student2 ; birthday是是 struct date類型的變量類型的變量定義了兩個具有定義了兩個具有struct student類類型的變量型的變量student1和和student2 成員名可以和程序中的其它變量名相同，二者不代表同一對象。成員名可以和程序中的其它變量名相同，二者不代表同一對象。 例如，程序中可以定義一個變量例如，程序中可以定義一個變量num ，它與，它與 struct student 中的中的num是兩回事

11、，兩者互不干涉。是兩回事，兩者互不干涉。struct student 的結構：的結構： num name sex age birthdaymonth day yearaddrstruct datestudent1 0103 Li lin M 18 birthday 03 26 1983Hangzhou在定義了結構體變量以后，就可以引用這個變量以及變量中的各個成員。在定義了結構體變量以后，就可以引用這個變量以及變量中的各個成員。結構體變量中的成員的引用方式結構體變量中的成員的引用方式: 結構體變量名結構體變量名. 成員名成員名 結構體變量的成員變量的用法和一般變量一樣，如結構體變量的成員變量的用

12、法和一般變量一樣，如 被賦值、被賦值、 參與運算等參與運算等 。 如如 : student1. num=10010; 表示給變量表示給變量 student1中的成員中的成員num 賦值賦值10010。8 . 3 結構體類型變量的引用結構體類型變量的引用“.” 成員（分量）運算符，成員（分量）運算符，優(yōu)先級最高優(yōu)先級最高引用結構體變量時應遵守以下規(guī)則：引用結構體變量時應遵守以下規(guī)則： 不能將一個結構體變量作為一個整體進行輸入輸出，只能通過引用其成員不能將一個結構體變量作為一個整體進行輸入輸出，只能通過引用其成員分別輸入輸出。分別輸入輸出。 如如 ：不能用以下語句整體輸入結構體變量，：不能用以下語

13、句整體輸入結構體變量， scanf(%d, %s, %c, %d, %f, %s , &student1) ; 可用以下語句一個一個可用以下語句一個一個成員成員輸入：輸入： scanf (%d, %s, %c, %d, %f, %s, &student1.num, , ); 如果結構體變量成員本身又屬于如果結構體變量成員本身又屬于 一個結一個結構體類型，則需要用若干個成員運算符，構體類型，則需要用若干個成員運算符， 逐逐級找到最低一級的成員。級找到最低一級的成員。只能對最低級的成只能對最低級的成員進行賦值、存取以及運算。員進行賦值、存取以及運算。 如如

14、 : student1 . birthday . year注意：不能用注意：不能用 student1.birthday 來訪問來訪問student1.birthday 中的成員，因為中的成員，因為birthday本身是一個結構體變量。本身是一個結構體變量。也不能用也不能用 student1. year 來訪問來訪問birthday中的中的成員。成員。 struct date int month; int day; int year; ; struct student int num; char name20; int age; float score; struct date birthday

15、; char addr30; student1, student2 ; 但但C語言新標準允許語言新標準允許 將一個結構體變量直接賦值給另一個相同類將一個結構體變量直接賦值給另一個相同類型的結構體變量。型的結構體變量。 例如：例如： student2=student1 ;表示將表示將 student1中所有成員的值一中所有成員的值一 一賦給一賦給 student2 中相應的成員中相應的成員. 可以引用結構體變量可以引用結構體變量成員的地址成員的地址，也可以引用，也可以引用結構體變量的地址結構體變量的地址。如如 : &student1.num student1.num 的地址的地址 &am

16、p;student1 結構體變量結構體變量student1的首地址的首地址 scanf (%d , &student1 . num) ; 輸入輸入 student1.num的值的值 printf(%o , &student1) ; 以八進制以八進制 輸出輸出 student1的地址的地址結構體變量的地址主要用于作函數(shù)參數(shù)，傳遞結構體的地址。結構體變量的地址主要用于作函數(shù)參數(shù)，傳遞結構體的地址。 結構體變量的成員變量可以像普通變量一樣進行結構體變量的成員變量可以像普通變量一樣進行各種運算各種運算（根據(jù)其類型（根據(jù)其類型決定可以進行的運算），例如：決定可以進行的運算），例如：stu

17、dent1 . score=student2 . score ;sum=student1 . score+student2 . score ;student1 . age+ ;+student1 . age ;注意：注意： 成員運算符成員運算符“.” 優(yōu)先級最高優(yōu)先級最高和其它類型變量一樣，對結構體變量也可以和其它類型變量一樣，對結構體變量也可以在定義時初始化。在定義時初始化。例例8.1 對結構體變量初始化。對結構體變量初始化。main( ) struct student long int num; char name20; char sex ; char addr20; a=89031,”L

18、i Lin“, M , 123 Beijing Road; printf(No. :%ldn, a . num) ; printf(name : %sn, a . name) ; printf(sex :%cn, a . sex) ; printf(address :%sn, a . addr) ;運行結果：運行結果：No. : 89031name : Li linsex : Maddress : 123 Beijing Road8.4 結構體變量的初始化結構體變量的初始化一個結構體變量中可以存放一組數(shù)據(jù)，如果有多組結構體數(shù)據(jù)參與一個結構體變量中可以存放一組數(shù)據(jù)，如果有多組結構體數(shù)據(jù)參與運算，

19、則應該用數(shù)組，這就是運算，則應該用數(shù)組，這就是結構體數(shù)組結構體數(shù)組。結構體數(shù)組中的每個元素都是一。結構體數(shù)組中的每個元素都是一個結構體類型的數(shù)據(jù)，而且都分別包括各個成員項。個結構體類型的數(shù)據(jù)，而且都分別包括各個成員項。8.5.1 定義結構體數(shù)組定義結構體數(shù)組 與結構體變量的定義類似，只需將變量與結構體變量的定義類似，只需將變量 說明為數(shù)組即可。說明為數(shù)組即可。 例如例如:struct student int num; char name20; char sex ; int age; float score; char addr30;struct student stu3;8.5 結構體數(shù)組結構

20、體數(shù)組定義了一個數(shù)組定義了一個數(shù)組stu3，其各元，其各元素為素為 struct student 類型的數(shù)據(jù)類型的數(shù)據(jù)定義結構體類型定義結構體類型 struct studentnumnamesexagescoreaddress10101Li LinM1887.5103 Beijing Road 10102Zhang FunM1999130 Shanghai Road10104Wang MinF2078.51010 Zhongshan Roadstu0stu1stu2也可以直接定義也可以直接定義:struct student. stu3;或或: struct. stu3;見下圖所示。見下圖所示。

21、stu0 10101 2B Li Lin 20B M 1B 18 2B 87.5 4B 103 Beijing Road 30B59 個字節(jié)個字節(jié)stu1stu2。數(shù)組中各元素在內存中是連續(xù)存放的：數(shù)組中各元素在內存中是連續(xù)存放的：說明：說明：1. 元素內部按成員元素內部按成員順序初始化；順序初始化；2. 按數(shù)組元素順序，每個元素可用按數(shù)組元素順序，每個元素可用 括起來；括起來；3. 元素個數(shù)如果缺省，則按初值個數(shù)來確定，例如：元素個數(shù)如果缺省，則按初值個數(shù)來確定，例如：struct student int num ; char name20 ;stu = 97001,Zhang,97002,

22、Li,97003,Wang ; 也可以先聲明結構體類型，然后定義結構體數(shù)組及初始化。例如也可以先聲明結構體類型，然后定義結構體數(shù)組及初始化。例如struct student int num ; char name20 ; ；struct student stu =97001,Zhang,97002,Li,97003,Wang ;8.5.2 結構體數(shù)組的初始化結構體數(shù)組的初始化只需在定義數(shù)組時在數(shù)組名后面加上只需在定義數(shù)組時在數(shù)組名后面加上 =初值表列初值表列;例如例如: struct student int num; char name20; stu3= 97001,Zhang,97002,L

23、i,97003,Wang ;#include struct person char name20; int count; leader3= Li,0,Zhang,0,Wang,0 ;main( ) int i , j; char leader_name20; /* 被選人的名字被選人的名字*/ for (i=1; i=10 ; i+) scanf(%s, leader_name); for (j=0 ; j3 ; j+) if (strcmp(leader_name , )=0) leaderj . count+ ; printf(n); for (i=0 ; i3 ;

24、 i+) printf(%s : %dn,leaderi . name , leaderi . count); 例例8.2 有三個候選人，統(tǒng)計得票次數(shù)。（有有三個候選人，統(tǒng)計得票次數(shù)。（有10個選民）個選民） 執(zhí)行執(zhí)行10次次leader 3 name count Li 0 Zhang 0 Wang 08.5.3 結構體數(shù)組應用舉例結構體數(shù)組應用舉例“.” 比比+ 優(yōu)先級高優(yōu)先級高一個一個結構體變量的指針結構體變量的指針就是指向一個結構變量所占據(jù)的內存段的起始地址。就是指向一個結構變量所占據(jù)的內存段的起始地址。 8.6.1 指向結構體變量的指針指向結構體變量的指針 例例8.3 指向結構體變量的

25、指針的應用。指向結構體變量的指針的應用。#include main( ) struct student long int num; char name20; float score; ; struct student stu; /* 定義結構體變量定義結構體變量 stu */ struct student *p; /* 定義指向定義指向 struct student 型數(shù)據(jù)的指針變量型數(shù)據(jù)的指針變量 p */ p=&stu; /* p指向指向str的起始地址的起始地址 */ stu. num=89101;/* 變量成員賦值變量成員賦值 */ strcpy(stu . name,Li);

26、 stu . score=89. 5; printf(No.%ld name %s score %6.2fn, stu.num, , stu.score); printf(No.%ld name %s score %6.2f, (*p).num , (*p).name, (*p).score); 8.6 指向結構體類型數(shù)據(jù)的指針指向結構體類型數(shù)據(jù)的指針注意：注意： (*p ) . num中的中的 ( ) 不可省，因為不可省，因為 “ .” 的優(yōu)先級最高，的優(yōu)先級最高，(*p) 表示表示 p 所指向的所指向的結構體變量，而結構體變量，而*p.num 等價于等價于*(p.num)。

27、 C語言中，為了使用方便和使之直觀，可以語言中，為了使用方便和使之直觀，可以 將指針將指針p 所指向的結所指向的結構體變量中的成員構體變量中的成員 表示為表示為: p-成員名成員名，它等價于，它等價于: (*p). 成員名。成員名。其中其中 “ ” 稱為稱為指向運算符。指向運算符。由由“-”和和“”構構成成也就是說，若也就是說，若 p=&stu ，以下三種形式等價：以下三種形式等價： （1）結構體變量名）結構體變量名. 成員名成員名 stu . num （2） ( * p ) . 成員名成員名 (*p) . num （3） p- 成員名成員名 p-num 象一般數(shù)組一樣，對于結構體數(shù)組

28、和數(shù)組元素，也可以使用指針或象一般數(shù)組一樣，對于結構體數(shù)組和數(shù)組元素，也可以使用指針或指針變量來指向。指針變量來指向。例：若有如下的定義例：若有如下的定義: struct student long int num; . ; struct student stu3; struct student *p;則則: p=stu; 表示令表示令 p 指向數(shù)組指向數(shù)組 stu 的首地址。的首地址。 p+1 表示數(shù)組中下一個元素的起始地址，即表示數(shù)組中下一個元素的起始地址，即 &stu1。 (+p)-num 表示先使表示先使 p 指向下一個元素，然后得到該元素中的指向下一個元素，然后得到該元素中的n

29、um值，值， 即即stu1. num。 (p+)-num 表示先得到當前元素的表示先得到當前元素的num值，值，,然后使然后使 p 指向下一指向下一個元素，即取出個元素，即取出stu0. num 成員，然后使指針成員，然后使指針 p + ，指向結構元素，指向結構元素 stu1 。 8.6.2 指向結構體數(shù)組的指針指向結構體數(shù)組的指針例例8.4 指向結構體數(shù)組的指針的應用。指向結構體數(shù)組的指針的應用。struct student int num; char name20; char sex ; int age ; ;struct student stu3=10101, Li Lin,M,18 ,

30、 10102, Zhang Fun, M,19, 10104, Wang Min , F , 20 ;main( ) struct student *p ; printf( No. name sex agen ) ; for( p=stu ; pnum , p-name , p-sex , p-age) ;運行結果：運行結果：No. Name sex age10101 Li Lin M 1810102 Zhang Fun F 1910104 Wang Min F 2020FWang Min1010419FZhang Fun1010218MLi Lin10101stu0stu1stu2p=stu

31、stu+38.6.3 用結構體變量和指向結構體的指針作函數(shù)參數(shù)用結構體變量和指向結構體的指針作函數(shù)參數(shù)將一個結構體變量的值傳遞給另一個函數(shù)時，有三種方法將一個結構體變量的值傳遞給另一個函數(shù)時，有三種方法:1.用結構體變量的用結構體變量的成員成員作為實參，將實參的值傳遞給形參作為實參，將實參的值傳遞給形參 ( 值傳遞值傳遞 )。用法。用法和普通變量作實參一樣，但應當注意實參與形參的類型必須保持一致。和普通變量作實參一樣，但應當注意實參與形參的類型必須保持一致。2.用結構體變量作實參（用結構體變量作實參（值傳遞值傳遞）。函數(shù)調用期間，形參也要占用內存單）。函數(shù)調用期間，形參也要占用內存單元，在時間

32、上和空間上開銷較大，此方法較少用。元，在時間上和空間上開銷較大，此方法較少用。3.用指向結構體變量用指向結構體變量(或數(shù)組或數(shù)組)的的指針指針作實參作實參,將地址傳遞給形參將地址傳遞給形參 ( 地址傳遞地址傳遞 ) 注意注意: 如果指針如果指針 p 已定義為指向結構體類型數(shù)據(jù)的變量（如已定義為指向結構體類型數(shù)據(jù)的變量（如struct student 類型），則它類型），則它只能指向結構體變量或結構體數(shù)組的一個元素（只能指向結構體變量或結構體數(shù)組的一個元素（p 的值是的值是stu 數(shù)組的一個元素的起始地址）數(shù)組的一個元素的起始地址），而不能指向某個成員。，而不能指向某個成員。若若 p=stu ;

33、 /* 指向結構體數(shù)組指向結構體數(shù)組 stu */則則 p=&stu1. name ; 編譯時出錯，編譯時出錯， p不能指向結構體元素不能指向結構體元素 stu1的成員的成員如果地址類型不同，可以使用強制類型轉換，例如如果地址類型不同，可以使用強制類型轉換，例如p=(struct student *)&;例例 8.5 有一個結構體變量，包含學生學號、姓名、和三門課成績。要求在有一個結構體變量，包含學生學號、姓名、和三門課成績。要求在main( ) 函數(shù)中賦以值，在另一個函數(shù)函數(shù)中賦以值，在另一個函數(shù)print( ) 中將它們打印輸出。中將它們打印輸出。#incl

34、ude #define FORMAT %dn%sn%fn%fn%fnstruct student int num ;char name20 ;float score3 ; ;main( ) void print(struct student ) ; struct student stu1 ; stu1.num=12345 ; strcpy( , Li Li ) ; stu1.score0=67.5 ; stu1.score1=89 ; stu1.score2=78.6 ; print(stu1) ; /* 結構體變量為形參結構體變量為形參 */void print(stuct

35、 student stu) printf(FORMAT , stu.num , , stu.score0, stu.score1, stu.score2) ; printf(n) ;運行結果：運行結果：12345Li Li67.50000089.00000078.599998實參數(shù)組實參數(shù)組 stu1 形參數(shù)組形參數(shù)組 stu例例8.6 上例改為指針方式。上例改為指針方式。#define FORMAT %dn%sn%fn%fn%fnstruct student int num ;char name20 ;float score3 ; stu1=12345 , Li Li , 6

36、7.5 , 89 , 78.6 ;main( ) void print(struct student *) ; print(&stu1) ;void print(stuct student *p) /* 結構指針變量為形參結構指針變量為形參 */ printf(FORMAT , p-num , p-name , p-score0, p-score1, p-score2) ; printf(n) ;指針作參數(shù)能提高運行效率。指針作參數(shù)能提高運行效率。score0score1score2namenumstupmain 函數(shù)中對各成員的賦值，也可以改用函數(shù)中對各成員的賦值，也可以改用scan

37、f 函數(shù)輸入，即函數(shù)輸入，即scanf(%d%s%f%f%f,&stu.num, ,&stu.score0,&stu.score1,&stu,score2); 前沒有前沒有&main( ) struct student int num; char name8; float score; stu4=10,A1,78,15,A2,89,20,B1,90,25,B2,70; struct student *p; float max ; int temp , i ; max=stu0.score; for (i=1 ; imax)

38、 max=stui . score; temp=i ; /* temp 成績最高者下標成績最高者下標 */ p=stu+temp ; /* 使使 p 指向指向 stu成績最高者成績最高者 */ printf(No.%d , name %s , %dn, p-num , p-name , p-score) ;例、已知例、已知 學生的學生的 學號、姓名、成績，找出成績最高者的學號、姓名、成學號、姓名、成績，找出成績最高者的學號、姓名、成績績8.7.1 鏈表概述鏈表概述 鏈表是一種鏈表是一種動態(tài)動態(tài)地進行存儲分配的地進行存儲分配的數(shù)據(jù)結構數(shù)據(jù)結構，用數(shù)組存放數(shù)據(jù)時，必須，用數(shù)組存放數(shù)據(jù)時，必須申請一

39、塊申請一塊連續(xù)空間連續(xù)空間，若元素有，若元素有100個，則必須申請長度為個，則必須申請長度為100個元素的數(shù)組，個元素的數(shù)組，若數(shù)組元素個數(shù)不定，則需要定義足夠大的數(shù)組長度，這勢必浪費內存。而若數(shù)組元素個數(shù)不定，則需要定義足夠大的數(shù)組長度，這勢必浪費內存。而 用鏈表可以根據(jù)需要來開辟內存單元。用鏈表可以根據(jù)需要來開辟內存單元。 一種簡單的鏈表結構圖示如下一種簡單的鏈表結構圖示如下 : 鏈表有一個鏈表有一個頭指針變量頭指針變量head，指向第一個元素指向第一個元素(表頭表頭)。 鏈表中的每一個元素稱為鏈表中的每一個元素稱為結點。結點。 一個結點包括兩個部分一個結點包括兩個部分: 實際數(shù)據(jù)實際數(shù)據(jù)

40、 下一個下一個同類型同類型結點的地址結點的地址。 鏈表有一個鏈表有一個表尾表尾，該元素不再指向其它元素，它的地址部分存放一，該元素不再指向其它元素，它的地址部分存放一個個空地址空地址(NULL)， ( NULL 是一個符號常量，是一個符號常量，代表整數(shù)代表整數(shù) 0， 指針變量指針變量等于等于0(NULL) 表示一個表示一個空指針空指針 )。 A1356headB1475C1021DNULL1249 1356 1475 102112498.7 用指針處理鏈表用指針處理鏈表可見可見: 1.鏈表中的各元素鏈表中的各元素 在內存中可以在內存中可以不連續(xù)存放。不連續(xù)存放。2.整個鏈表的訪問，整個鏈表的訪

41、問，必須從表頭指針開始必須從表頭指針開始，根據(jù)上一個元素所提供的，根據(jù)上一個元素所提供的地址找到下一個元素。地址找到下一個元素。3.鏈表的數(shù)據(jù)結構鏈表的數(shù)據(jù)結構必須利用指針變量必須利用指針變量才能實現(xiàn)，一個結點中除了包含才能實現(xiàn)，一個結點中除了包含 數(shù)據(jù)變量外，還應包含一個指針變量，用來存放下一結點的地址。數(shù)據(jù)變量外，還應包含一個指針變量，用來存放下一結點的地址。因此，前面介紹的因此，前面介紹的結構體類型用作鏈表中的結點結構體類型用作鏈表中的結點是最合適的：是最合適的： 例如，例如， 要建立一個鏈表，首先要定義結點的類型要建立一個鏈表，首先要定義結點的類型 ：struct student in

42、t num; float score ; struct student *next; /* next 是指針變量，指向下一個結點是指針變量，指向下一個結點*/ ；數(shù)據(jù)數(shù)據(jù)指針指針指向下一個結點指向下一個結點89.59910190991038599107nextscorenum#define NULL 0struct student long int num ;float score ;struct student *next ; ;/* 聲明一個結構體聲明一個結構體 */ 建立鏈表是指從無到有地建立起一個鏈表建立鏈表是指從無到有地建立起一個鏈表，包括一個一個地輸入各，包括一個一個地輸入各結點數(shù)

43、據(jù)結點數(shù)據(jù), 并建立起前后相鏈的關系。并建立起前后相鏈的關系。例例11.7 建立如下圖所示的鏈表，它由建立如下圖所示的鏈表，它由3各學生數(shù)據(jù)的結點組成。各學生數(shù)據(jù)的結點組成。8.7.2 建立簡單鏈表建立簡單鏈表 a b cnumnextscore &b &c NULL 89.5 90.0 85.0 99101 99103 99107main( ) /* a,b,c 是結構變量，是結構變量，head 和和 p是指針是指針 */ struct student a, b, c , *head , *p ; a. num=99101 ; a. score=89.5 ; b. num=9

44、9103 ; b. score=90.0 ; c. num=99107 ; c . score=85.0 ; a. next=&b ; b. next=&c ; c. next=NULL ; p=head=&a ; while( p !=NULL) printf(%ld %5.1f n , p-num , p-score) ; p=p-next ; /* 建立鏈表建立鏈表 */* 輸出各結點內容輸出各結點內容 */ a b cnumnextscore &b &c NULL 89.5 90.0 85.0 99101 99103 99107/* 結點賦值結點

45、賦值 */ 鏈表是動態(tài)地分配存儲的，鏈表是動態(tài)地分配存儲的，C語言中提供了語言中提供了動態(tài)地開辟和釋放存儲單動態(tài)地開辟和釋放存儲單元的庫函數(shù)元的庫函數(shù)（其信息包含在（其信息包含在 malloc.h 文件中）。文件中）。1. malloc 函數(shù)函數(shù) 函數(shù)原型為：函數(shù)原型為： void *malloc(unsigned int size) ; 其作用是：在內存的動態(tài)存儲區(qū)中分配一個長度為其作用是：在內存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。的連續(xù)空間。此此 函數(shù)的值（即返回值）是一個指向函數(shù)的值（即返回值）是一個指向該分配域起始地址該分配域起始地址的指針（基類型為的指針（基類型為 voi

46、d）。如果函數(shù)未能成功地執(zhí)行，則返回值為）。如果函數(shù)未能成功地執(zhí)行，則返回值為NULL。8.7.3 處理處理動態(tài)鏈表動態(tài)鏈表所需的函數(shù)所需的函數(shù)2. calloc函數(shù)函數(shù) 函數(shù)原型為：函數(shù)原型為： void * calloc(unsigned n, unsigned size) ; 其作用是：在內存的動態(tài)存儲區(qū)中分配其作用是：在內存的動態(tài)存儲區(qū)中分配 n 個長度為個長度為 size 的連續(xù)空間。的連續(xù)空間。 函數(shù)返回一個函數(shù)返回一個 指向該分配指向該分配空間的起始地址的指針；空間的起始地址的指針； 如果函數(shù)不能成功執(zhí)如果函數(shù)不能成功執(zhí)行行,則返回值為則返回值為NULL。鏈表的操作包括：鏈表的操

47、作包括： 建立鏈表、插入或建立鏈表、插入或 刪除鏈表中的一個結點等。刪除鏈表中的一個結點等。8.7.4 建立動態(tài)鏈表建立動態(tài)鏈表例例 11.8 寫一個函數(shù)，建立有三個學生數(shù)據(jù)的單向動態(tài)鏈表。寫一個函數(shù)，建立有三個學生數(shù)據(jù)的單向動態(tài)鏈表。head num score *next 1 2 3 NULL3. free 函數(shù)函數(shù) 函數(shù)原型為：函數(shù)原型為：void free(void *ptr) 作用是：釋放由作用是：釋放由 ptr 所指向的內存區(qū)，所指向的內存區(qū)， ptr 是最近一次調用是最近一次調用malloc 或或 calloc 函數(shù)函數(shù) 時返回的地址。時返回的地址。free 函數(shù)無返回值。函數(shù)無

48、返回值。注意：以前注意：以前C版本提供的版本提供的malloc 和和 calloc 函數(shù)得到的是指向字符型函數(shù)得到的是指向字符型數(shù)據(jù)的指針。數(shù)據(jù)的指針。ANSI C 規(guī)定為規(guī)定為 void * 類型。類型。步驟步驟:1. 定義結點類型（結構體類型）：定義結點類型（結構體類型）： struct student2. 定義指向結點的指針變量定義指向結點的指針變量 head, p1, p2： head 指向表頭，指向表頭，p1 指向指向當前當前新建立的結點新建立的結點， p2 指向鏈表中最后一個結點指向鏈表中最后一個結點；3. 新建一個結點新建一個結點 （開辟內存單元，（開辟內存單元， 輸入學號和成績

49、輸入學號和成績 數(shù)據(jù)）；數(shù)據(jù)）；4. 建立表頭建立表頭5. 建立鏈表建立鏈表 如果新結點是第一個結點，如果新結點是第一個結點，則表頭則表頭 head 指向該結點指向該結點， 否則該結點鏈否則該結點鏈入鏈表，并讓入鏈表，并讓 p2 指向新鏈入的這個結點，重復指向新鏈入的這個結點，重復3、 5； 如果是第如果是第3個結點，則個結點，則讓讓 p1 所指的結點中的指向下一個結點的指針為所指的結點中的指向下一個結點的指針為空指針空指針NULL，鏈表建立結束。，鏈表建立結束。head num score *next 1 p1 1 23head num score *nextp2p1*nextNULL#in

50、clude #define NULL 0struct student long num; float score; struct student *next; ; void main( ) struct student *head , *p1 , *p2 ; int n ; head=NULL ; for(n=1 ; n num , &p1 - score) ;if(head = NULL) head=p1 ;else p2-next=p1 ;p2=p1 ; p1-next=NULL ; free(p1) ; /* 釋放結點空間釋放結點空間*/ return ;三次動態(tài)三次動態(tài)申請空間

51、申請空間定義結點的數(shù)據(jù)結構定義結點的數(shù)據(jù)結構 現(xiàn)在，我們用一個現(xiàn)在，我們用一個函數(shù)函數(shù)來建立一個有來建立一個有若干若干個學生的學號和成績數(shù)據(jù)的個學生的學號和成績數(shù)據(jù)的單向鏈表（假設輸入學號為單向鏈表（假設輸入學號為 0 時結束）。時結束）。步驟步驟:1. 定義結點類型（結構體類型）：定義結點類型（結構體類型）： struct student2. 定義指向結點的指針變量定義指向結點的指針變量 head, p1, p2； head 指向表頭，指向表頭，p1 指向指向當前當前新建立的結點新建立的結點，p2 指向表中最后一個結點指向表中最后一個結點。 把把p1所指的結點連接在所指的結點連接在p2所指的

52、結點后面，用所指的結點后面，用“p2-next=p1; ”來實現(xiàn)來實現(xiàn)。3. 新建一個結點新建一個結點 （開辟內存單元、輸入學號、成績等數(shù)據(jù)）；（開辟內存單元、輸入學號、成績等數(shù)據(jù)）；4. 建立表頭建立表頭 （head=NULL;）5. 建立鏈表建立鏈表 如果新結點是第一個結點，如果新結點是第一個結點，則表頭則表頭 head 指向該結點指向該結點， 否則該結點否則該結點鏈入鏈表，并讓鏈入鏈表，并讓 p2 指向新鏈入的這個結點，重復指向新鏈入的這個結點，重復 3、5； 如果輸入學號為如果輸入學號為0，則該結點不鏈入鏈表，前一個結點是表尾，即，則該結點不鏈入鏈表，前一個結點是表尾，即讓讓 p2 所

53、指的結點中的指向下一個結點的指針為空指針所指的結點中的指向下一個結點的指針為空指針NULL（p2 - next=NULL;），鏈表建立結束。），鏈表建立結束。int n; /* 全局變量全局變量 n 統(tǒng)計結點數(shù)統(tǒng)計結點數(shù) ，本模塊中各函數(shù)，本模塊中各函數(shù) 均可使用它均可使用它*/struct student * creat (void) /* 定義函數(shù)定義函數(shù) 。此函數(shù)帶回一個。此函數(shù)帶回一個指向鏈表頭的指針指向鏈表頭的指針*/ struct student *head, *p1 , *p2 ; head=NULL; n=0; p1= (struct student *) malloc (si

54、zeof (struct student) ; /* 開辟內存單元準備建立第一個結點開辟內存單元準備建立第一個結點 */ scanf(%ld , %f, &p1-num , &p1-score) ; while ( p1-num != 0) n+; if (head= NULL) head=p1; /* head 指向第一個結點指向第一個結點 */ else p2-next=p1 ; /* 將新結點將新結點 p1 鏈入鏈表鏈入鏈表 */ p2=p1 ; /* 保留當前保留當前結點的地址結點的地址 */ p1=(struct student *) malloc(sizeof (s

55、truct student) ; scanf(%ld,%f, &p1-num , &p1-score) ; p2 - next=NULL ; free(p1) ; return (head);p2p18.7.5 輸出鏈表輸出鏈表 將鏈表中各個結點的數(shù)據(jù)依次輸出。將鏈表中各個結點的數(shù)據(jù)依次輸出。 首先要知道鏈表表頭首先要知道鏈表表頭head的地的地址，再定義一個指向結點的指針變量址，再定義一個指向結點的指針變量 p ，使，使p先指向第一個結點，輸出先指向第一個結點，輸出該該 結點的數(shù)據(jù)，然后讓結點的數(shù)據(jù)，然后讓 p 指向下一個結點，再輸出，直到表尾為止。指向下一個結點，再輸出，直

56、到表尾為止。 例例11.9 編寫一個輸出鏈表的函數(shù)編寫一個輸出鏈表的函數(shù)print。void print(struct student *head) struct student *p; printf(n輸出輸出結點結點數(shù)據(jù)數(shù)據(jù) :n) ; p=head; if(head!=NULL) /* 如果不是空鏈表，則輸出如果不是空鏈表，則輸出 */ do printf(%ld %fn, p-num , p-score) ; p=p-next ; /* 使使 p 指向下一個結點指向下一個結點 */ while( p!=NULL) ;可以在可以在main 函數(shù)中調用函數(shù)中調用 creat 函數(shù)：函數(shù)：m

57、ain( ) creat( ); 調用調用creat 函數(shù)后建立函數(shù)后建立一個單向動態(tài)鏈表一個單向動態(tài)鏈表 從一個動態(tài)鏈表中刪除一個結點，并不是真正從內存中把它抹掉，而是從一個動態(tài)鏈表中刪除一個結點，并不是真正從內存中把它抹掉，而是把它從鏈表中分離出來，只要改變原來的連接關系即可，即讓該結點的前一把它從鏈表中分離出來，只要改變原來的連接關系即可，即讓該結點的前一個結點直接指向該結點的下一個結點。個結點直接指向該結點的下一個結點。注意注意: 如果如果刪除的是第一個結點刪除的是第一個結點，則要修改表頭，則要修改表頭 head。 如果鏈表是空表（無結點）或表中找不到要刪除的結點如果鏈表是空表（無結點

58、）或表中找不到要刪除的結點 , 不刪除。不刪除。p2. . .p1 刪除刪除headp18.7.6 刪除一個結點刪除一個結點進行操作：進行操作：head = p1-next ;用函數(shù)來刪除一個指定的結點，方法如下：用函數(shù)來刪除一個指定的結點，方法如下：1. 用一個指向結點的指針變量，從表頭開始用一個指向結點的指針變量，從表頭開始查找查找需要刪除的結點。需要刪除的結點。2. 定義兩個指針變量定義兩個指針變量 p1 和和 p2 ，其中：，其中： p1 指向要刪除的結點，指向要刪除的結點，p2 是指向是指向 p1前面的一個結點。前面的一個結點。要刪除要刪除 p1，使，使p2-next = p1-ne

59、xt ; 就從鏈表中刪除了就從鏈表中刪除了p1 所指的結點。所指的結點。struct student *del (struct student *head, long num) struct student *p1,*p2; if (head = NULL) printf(空鏈表空鏈表n) ; goto end; p1=head; while( p1 - num != num & p1-next != NULL) p2=p1; p1=p1-next ; /* 后移一個結點后移一個結點, 繼續(xù)查找繼續(xù)查找 */ if( p1 - num = num) /* 找到找到 */ if ( p1 = head) /* 如果刪除第一個結點如果刪除第一