第七章 結(jié)構(gòu)體

1、20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 1 1 第八章 結(jié)構(gòu)體8.1 概述8.2 定義結(jié)構(gòu)體變量的方法8.3 結(jié)構(gòu)體變量的初始化8.4 結(jié)構(gòu)體變量的引用8.5 結(jié)構(gòu)體數(shù)組8.6 指向結(jié)構(gòu)體數(shù)據(jù)的指針8.7 用指針處理鏈表20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 2 2 8.1 概述 在實(shí)際問(wèn)題中我們常需要把不同類型的幾個(gè)數(shù)據(jù)組合起來(lái)在實(shí)際問(wèn)題中我們常需要把不同類型的幾個(gè)數(shù)據(jù)組合起來(lái), 構(gòu)成構(gòu)成一個(gè)整體。如一個(gè)公司職員的個(gè)人信息一個(gè)整體。如一個(gè)公司職員的個(gè)人信息, 或?qū)W校中教師和學(xué)生的信息?；?qū)W校中教師和學(xué)生的信息。以學(xué)生信息為例以學(xué)生信息為例,

2、 它可能包括學(xué)生的學(xué)號(hào)、班級(jí)、姓名、性別、年齡、它可能包括學(xué)生的學(xué)號(hào)、班級(jí)、姓名、性別、年齡、成績(jī)等。這時(shí)原有的那些數(shù)據(jù)類型就顯的有點(diǎn)無(wú)能為力了，所以引入成績(jī)等。這時(shí)原有的那些數(shù)據(jù)類型就顯的有點(diǎn)無(wú)能為力了，所以引入一種新的數(shù)據(jù)類型一種新的數(shù)據(jù)類型- 結(jié)構(gòu)體。結(jié)構(gòu)體。結(jié)構(gòu)體是由一些邏輯相關(guān)結(jié)構(gòu)體是由一些邏輯相關(guān), 但數(shù)據(jù)類型不同的分量組成的一組數(shù)據(jù)。但數(shù)據(jù)類型不同的分量組成的一組數(shù)據(jù)。注意注意: 用戶需要先定義用戶需要先定義結(jié)構(gòu)體類型結(jié)構(gòu)體類型, 之后才能之后才能定義結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量注意不要忘了分號(hào)注意不要忘了分號(hào)成員列表成員列表結(jié)構(gòu)體類型定義形式結(jié)構(gòu)體類型定義形式: struct 結(jié)構(gòu)

3、體類型名結(jié)構(gòu)體類型名 數(shù)據(jù)類型數(shù)據(jù)類型 成員名成員名1; 數(shù)據(jù)類型數(shù)據(jù)類型 成員名成員名2; : : 數(shù)據(jù)類型數(shù)據(jù)類型 成員名成員名n; ;關(guān)鍵字關(guān)鍵字用戶定義用戶定義的標(biāo)識(shí)符的標(biāo)識(shí)符20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 3 3 8.2 定義結(jié)構(gòu)體變量的方法一、一、 定義結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量1. 先定義結(jié)構(gòu)體類型先定義結(jié)構(gòu)體類型, 再定義變量再定義變量 struct student char name10 ; int age ; float s1 , s2 ; ; struct student st1 , st2 ;st1st2nameages1s2nameag

4、es1s2結(jié)構(gòu)體變量結(jié)構(gòu)體變量st1和和st2各自都各自都需要需要20個(gè)字節(jié)的存儲(chǔ)空間個(gè)字節(jié)的存儲(chǔ)空間20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 4 4 2. 定義結(jié)構(gòu)體類型同時(shí)定義變量定義結(jié)構(gòu)體類型同時(shí)定義變量 struct student char name10 ; int age ; float s1 , s2 ; st1 , st2 ;3. 直接定義結(jié)構(gòu)體變量直接定義結(jié)構(gòu)體變量 struct char name10 ; int age ; float s1 , s2 ; st1 , st2 ;4. 說(shuō)明說(shuō)明: (1) 結(jié)構(gòu)體變量具有結(jié)構(gòu)體類型的一切特征結(jié)構(gòu)體變量具

5、有結(jié)構(gòu)體類型的一切特征 在內(nèi)存中結(jié)構(gòu)體變量占有一片連續(xù)的存儲(chǔ)單元在內(nèi)存中結(jié)構(gòu)體變量占有一片連續(xù)的存儲(chǔ)單元 存儲(chǔ)單元的字節(jié)數(shù)可用存儲(chǔ)單元的字節(jié)數(shù)可用sizeof 運(yùn)算符運(yùn)算符算出算出 printf(“%dn” , sizeof(struct student) ) ; printf(“%dn” , sizeof(st1) ) ; 20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 5 5 (2) 結(jié)構(gòu)體類型可以嵌套定義結(jié)構(gòu)體類型可以嵌套定義 例例: struct date int year ; int month ; int day ; ; struct stud char name

6、10 ; struct date birthday ; float s1 , s2 ; ; 或或 : struct stud char name10 ; struct date int year ; int month ; int day ; birthday ; float s1 , s2 ; ;20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 6 6 8.3 結(jié)構(gòu)體變量的初始化struct student char name10 ; int age ; float score1 , score2 ; st1=“ Mary”, 21, 78, 86 ;struct stud

7、char name10 ; struct date birthday ; float score1 , score2 ; ;struct stud st2= “John” , 1980 , 11 , 23 , 89 , 95 ;struct student char name10 ; int age ; float score1 , score2 ; ;struct student st3; st3=“ Mary”, 21, 78, 86 ;正確初始化正確初始化錯(cuò)誤錯(cuò)誤, C不允許不允許這樣賦值這樣賦值正確初始化正確初始化20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 7 7

8、 8.4 結(jié)構(gòu)體變量的引用1. 引用結(jié)構(gòu)體變量中的成員引用結(jié)構(gòu)體變量中的成員 格式格式: 結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名. 成員名成員名struct student char name10 ; int age ; float s1 , s2 ; ;注意注意: 一般是對(duì)結(jié)構(gòu)體變量的各個(gè)成員分別進(jìn)行賦值一般是對(duì)結(jié)構(gòu)體變量的各個(gè)成員分別進(jìn)行賦值st1 = “Mary”, 21 , 78 , 86 ; 這樣的賦值是不允許的這樣的賦值是不允許的struct student st1 ;strcpy(st1. name, “Mary”) ; st1. age = 21 ;st1. s1 = 78 ; st1. s

9、2 = 86 ; struct date int year ; int month ; int day ; ;struct stud char name10 ; int age ; struct date birthday; float s1 , s2 ; ;struct stud st2 ;int age , year ;strcpy(st2. name,“John”) ; st2. age = 20 ; st2. birthday. year = 1980 ;st2. birthday. month = 11 ;st2. birthday. day = 23 ;st2. s1 = 89 ;

10、 st2. s2 = 95 ;age = 24 ; year = 2000 ;可以定義與結(jié)構(gòu)體變量可以定義與結(jié)構(gòu)體變量成員名相同名字的變量成員名相同名字的變量 它們之間不會(huì)發(fā)生混亂它們之間不會(huì)發(fā)生混亂20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 9 9 2. 相同類型的結(jié)構(gòu)體變量可以進(jìn)行相同類型的結(jié)構(gòu)體變量可以進(jìn)行整體賦值整體賦值 struct date int year ; int month ; int day ; ;struct stud char name10 ; int age ; struct date birthday; float s1 , s2 ; ;st

11、ruct stud st1, st2, st3;strcpy(st1. name, “John”) ; st1. age = 20 ; st1. birthday.year = 1980 ;st1. birthday.month = 11 ;st1. birthday.day = 23 ;st1. s1 = 89 ; st1. s2 = 95 ;st2=st1;strcpy(st3. name,“Mary”);st3. age=20;st3. birthday=st1. birthday;st3. s1 = 76;st3. s2 = 85;注意要正確賦值的條件注意要正確賦值的條件是變量是變量s

12、t1已經(jīng)有了初值已經(jīng)有了初值20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 1010 3. 結(jié)構(gòu)體變量的輸入結(jié)構(gòu)體變量的輸入 輸出輸出 C語(yǔ)言不允許結(jié)構(gòu)體變量整體進(jìn)行輸入和輸出語(yǔ)言不允許結(jié)構(gòu)體變量整體進(jìn)行輸入和輸出, 只能對(duì)結(jié)構(gòu)體變量的只能對(duì)結(jié)構(gòu)體變量的成員成員進(jìn)行輸入和輸出進(jìn)行輸入和輸出gets( st1. name ) ;scanf( “%d%d%d”, &st1. birthday. year , &st1. birthday. month , &st1. birthday. day ) ;scanf ( “%d%f%f”, &st1.

13、age , &st1. s1 , &st1. s2 ) ; puts( st1. name ) ;printf( “%4d”, st1. age );printf( “%d .%d .%d”, st1. birthday. year , st1. birthday. month , st1. birthday. day ) ;printf(“%5.2f %5.2fn”, st1. s1 , st1. s2 ) ; 20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 1111 8.5 結(jié)構(gòu)體數(shù)組 一、一、 結(jié)構(gòu)體數(shù)組的定義結(jié)構(gòu)體數(shù)組的定義 1. 先定義結(jié)構(gòu)體類型先定

14、義結(jié)構(gòu)體類型 再定義結(jié)構(gòu)體數(shù)組再定義結(jié)構(gòu)體數(shù)組 struct student char name10 ; int age ; float s1 , s2 ; ; struct student st6 ;2. 定義結(jié)構(gòu)體類型的同時(shí)定義數(shù)組定義結(jié)構(gòu)體類型的同時(shí)定義數(shù)組 struct student char name10 ; int age ; float s1 , s2 ; st6 ; 3. 直接定義結(jié)構(gòu)體數(shù)組直接定義結(jié)構(gòu)體數(shù)組 struct char name10 ; int age ; float s1 , s2 ; st6 ;20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室

15、 1212 二、結(jié)構(gòu)體數(shù)組的初始化二、結(jié)構(gòu)體數(shù)組的初始化 將每個(gè)數(shù)組元素的數(shù)據(jù)用花括號(hào)將每個(gè)數(shù)組元素的數(shù)據(jù)用花括號(hào) 括起來(lái)括起來(lái)struct student char name10 ; int age ; float s1 , s2 ; ;struct student st3= “Mary”, 21, 78, 86, “Alex”, 20, 90, 80 , “Mike”,19, 75, 68 ;Mary217886Alex209080Mike197568st0st1st22. 數(shù)組元素之間可以整體賦值數(shù)組元素之間可以整體賦值 也可以將一個(gè)元素賦給一個(gè)相同類型的結(jié)構(gòu)體變量也可以將一個(gè)元素賦給一

16、個(gè)相同類型的結(jié)構(gòu)體變量 struct student x , st3= “Mary”,21,78,86, “Alex”, ; st2 = st0 ; x = st1 ; 3. 只能對(duì)數(shù)組元素的只能對(duì)數(shù)組元素的成員成員進(jìn)行輸入和輸出進(jìn)行輸入和輸出gets( st2. name ) ;scanf(“%d” , &st2. age ) ;scanf(“%f%f ”, &st2. s1 , &st2. s2 );puts( st0. name );printf(“%4d%5.2f %5.2fn”, st0. age , st0. s1 , st0. s2) ;都是結(jié)構(gòu)體變量的整

17、體賦值都是結(jié)構(gòu)體變量的整體賦值三、三、 結(jié)構(gòu)體數(shù)組的引用結(jié)構(gòu)體數(shù)組的引用1. 引用某個(gè)數(shù)組元素的成員引用某個(gè)數(shù)組元素的成員 例例: puts( st0. name ) ; printf(“%d, %d”, st1. age , st1. s1 ) ;例例: 有有30名學(xué)生名學(xué)生, 輸入每個(gè)學(xué)生信息包括學(xué)號(hào)、姓名、成績(jī)，輸入每個(gè)學(xué)生信息包括學(xué)號(hào)、姓名、成績(jī)， 要求找出成績(jī)最高者，并輸出他的信息要求找出成績(jī)最高者，并輸出他的信息#include #define N 30void main( ) struct student int n ; char name10 ; int score ; ; s

18、truct student stN; int i , m ; int max ; for ( i=0 ; iN ; i+) scanf(“%d%s%d”, &sti.n , , &sti.score) ; max=st0.score;for( i=1 ; i max ) max=sti.score; m=i; printf(“%4d”, stm.n ) ; printf(“%10s ”, ); printf(“%5d ”, stm.score);例例: 按成績(jī)對(duì)學(xué)生信息進(jìn)行從高到底的排序按成績(jī)對(duì)學(xué)生信息進(jìn)行從高到底的排序#include #de

19、fine N 30void main( ) struct stud int n ; char name10 ; int s ; ; struct stud aN, temp; int i ,j,k; for ( i=0 ; iN ; i+) scanf(“%d%s%d”, &ai.n, , &ai.s) ; for ( i=0 ; iN-1 ; i+) for ( j=i+1 ; jN ; j+) if ( ai.saj.s ) k=j; temp=ak ; ak=ai ; ai=temp ; for ( i=0 ; i s1 = 87 ;p - s2 = 90

20、;(2) (*指針變量名指針變量名) . 成員名成員名 (*p) . age(3) 指針變量名指針變量名 - 成員名成員名 p - s1up只能指向一個(gè)結(jié)構(gòu)體變量，如：只能指向一個(gè)結(jié)構(gòu)體變量，如：p=&stu；而不能指向結(jié)；而不能指向結(jié)構(gòu)體變量的一個(gè)成員。如：構(gòu)體變量的一個(gè)成員。如：p=&stu.age；是非法的；是非法的。u -運(yùn)算符的優(yōu)先級(jí)最高。運(yùn)算符的優(yōu)先級(jí)最高。例如：例如：struct char name20 ; int age ; *p ;則表達(dá)式：則表達(dá)式： +p-age： 表示表示age的值增加的值增加1。 等價(jià)于等價(jià)于+(p-age) u使用結(jié)構(gòu)體指針變量應(yīng)注意

21、以下幾點(diǎn)：使用結(jié)構(gòu)體指針變量應(yīng)注意以下幾點(diǎn)：u p不是結(jié)構(gòu)體變量不是結(jié)構(gòu)體變量(是指向結(jié)構(gòu)體變量的指針是指向結(jié)構(gòu)體變量的指針)，因此，因此不能寫成不能寫成成員引用方式成員引用方式p.age的形式的形式。二、二、 指向結(jié)構(gòu)體數(shù)組的指針指向結(jié)構(gòu)體數(shù)組的指針1. 定義定義 struct student st3 , *p ;2. 使用使用 for ( p=st ; pname ) ; scanf( “%d%d %d ”,&p-age,&p-s1,&p-s2) ; 對(duì)于指向結(jié)構(gòu)體數(shù)組的指針：對(duì)于指向結(jié)構(gòu)體數(shù)組的指針：pp只能指向只能指向一個(gè)結(jié)構(gòu)體一個(gè)結(jié)構(gòu)體數(shù)組的一個(gè)元素?cái)?shù)組的一個(gè)

22、元素（相當(dāng)于變量），然（相當(dāng)于變量），然后后用用-指向運(yùn)算符指向運(yùn)算符取其成員的值取其成員的值，而不能直接指向一個(gè)數(shù)組，而不能直接指向一個(gè)數(shù)組元素的成員。元素的成員。p(+p)-age：p表示表示p指針指向下一個(gè)數(shù)組元素后，再訪問(wèn)其成員指針指向下一個(gè)數(shù)組元素后，再訪問(wèn)其成員age。p(p+)-age：p先訪問(wèn)先訪問(wèn)age操作，再對(duì)指針操作，再對(duì)指針p加加1，使其指向下一個(gè)數(shù)組，使其指向下一個(gè)數(shù)組元素。元素。結(jié)構(gòu)體變量作為函數(shù)參數(shù)結(jié)構(gòu)體變量作為函數(shù)參數(shù)1. 函數(shù)的實(shí)參和形參都用結(jié)構(gòu)體變量函數(shù)的實(shí)參和形參都用結(jié)構(gòu)體變量 , 參數(shù)之間為參數(shù)之間為值傳遞值傳遞即即:實(shí)參實(shí)參 結(jié)構(gòu)體變量結(jié)構(gòu)體變量各成員

23、的值依次傳給各成員的值依次傳給形參結(jié)構(gòu)體變量形參結(jié)構(gòu)體變量2. 返回結(jié)構(gòu)體類型值的函數(shù)返回結(jié)構(gòu)體類型值的函數(shù) 函數(shù)定義格式函數(shù)定義格式 : 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名 函數(shù)名函數(shù)名 ( 形參表列形參表列) 函數(shù)體函數(shù)體 ; 例例 : struct student funct ( int x , float y ) 函數(shù)體函數(shù)體 ; 注意注意 結(jié)構(gòu)體類型是已經(jīng)定義好的結(jié)構(gòu)體類型是已經(jīng)定義好的20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 2020 三、結(jié)構(gòu)體與函數(shù)三、結(jié)構(gòu)體與函數(shù) 注意注意 結(jié)構(gòu)變量作為參數(shù)傳遞時(shí)，其實(shí)參與形參的結(jié)構(gòu)類型必結(jié)構(gòu)變量作為參數(shù)傳遞時(shí)，其實(shí)參與形參的結(jié)構(gòu)

24、類型必須一致，傳遞時(shí)其實(shí)參只需指定其結(jié)構(gòu)變量名即可。當(dāng)實(shí)參須一致，傳遞時(shí)其實(shí)參只需指定其結(jié)構(gòu)變量名即可。當(dāng)實(shí)參為數(shù)組時(shí)，其形參可以定義為同類型結(jié)構(gòu)的結(jié)構(gòu)數(shù)組或結(jié)構(gòu)為數(shù)組時(shí)，其形參可以定義為同類型結(jié)構(gòu)的結(jié)構(gòu)數(shù)組或結(jié)構(gòu)指針。指針。與普通變量一樣，結(jié)構(gòu)變量在函數(shù)內(nèi)部定義時(shí)為局部的，其值與普通變量一樣，結(jié)構(gòu)變量在函數(shù)內(nèi)部定義時(shí)為局部的，其值只在本函數(shù)范圍內(nèi)有效，不會(huì)影響其它函數(shù)只在本函數(shù)范圍內(nèi)有效，不會(huì)影響其它函數(shù) 將結(jié)構(gòu)傳遞給函數(shù)的方式有三種將結(jié)構(gòu)傳遞給函數(shù)的方式有三種p傳遞單個(gè)成員傳遞單個(gè)成員p傳遞整個(gè)結(jié)構(gòu)傳遞整個(gè)結(jié)構(gòu)p傳遞指向結(jié)構(gòu)的指針傳遞指向結(jié)構(gòu)的指針傳遞結(jié)構(gòu)變量的地址可以實(shí)現(xiàn)結(jié)構(gòu)的傳址調(diào)用。

25、傳遞結(jié)構(gòu)變量的地址可以實(shí)現(xiàn)結(jié)構(gòu)的傳址調(diào)用。結(jié)構(gòu)數(shù)組也可作為函數(shù)參數(shù)傳遞。結(jié)構(gòu)數(shù)組也可作為函數(shù)參數(shù)傳遞。在調(diào)用在調(diào)用print時(shí)，時(shí)， &stud做實(shí)參，將做實(shí)參，將stud的地址的地址傳遞給函數(shù)的傳遞給函數(shù)的形參形參p，這時(shí)這時(shí)p指向了結(jié)構(gòu)變量指向了結(jié)構(gòu)變量 stud的成員值。的成員值。#include #define FORMAT “%dn%sn%6.2fn” struct student int num; char name20; float score; ; main() void print (); struct student stud; stud.num=1001; str

26、cpy(,”michell”); stud.score=90.9; print(&stud); void print(struct student *p) printf(FORMAT,p-num,p-name,p-score); printf(“n”); 例例: 求學(xué)生成績(jī)的總分和平均分求學(xué)生成績(jī)的總分和平均分 #include #define N 5struct stud char name10 ; int s3 ; float sum , ave ; ; struct stud comp (struct stud x) int j ; x.sum = 0 ; fo

27、r ( j = 0; j3 ; j+ ) x.sum = x.sum + x.sj ; x.ave = x.sum / 3 ; return(x); void main ( ) struct stud aN ; int j ; for ( j=0; jN; j+ ) scanf(“%s%d%d%d ”, , &aj.s0, &aj.s1 , &aj.s2 ); for ( j=0; jN; j+) aj=comp ( aj ) ; for ( j=0; jN; j+) printf(“%10s%4d”, , aj.s0 ); printf(“

28、%4d%4d”, aj.s1, aj.s2 ); printf(“%8.2f %6.2fn”, aj.sum , aj.ave ); 例例: 按成績(jī)對(duì)學(xué)生信息進(jìn)行從高到底的排序按成績(jī)對(duì)學(xué)生信息進(jìn)行從高到底的排序#include #define N 30struct stud int n ; char name10 ; int s ; ;void input(struct stud a ) int i ; for ( i=0 ; iN ; i+) scanf(“%d%s%d”, &ai.n, , &ai.s) ; void output(struct stud a

29、) int i ; for ( i=0 ; iN ; i+) printf(“%4d%10s%4d”, ai.n, , ai.s) ; void sort(struct stud a ) int i , j ，k; struct stud temp; for ( i=0 ; iN-1 ; i+) k=i; for ( j=i+1 ; jN ; j+) if ( ai.saj.s ) k=j; if(k!=i)temp=ak ; ak=ai ; ai=temp ; void main( ) struct stud stN; input(st); sort(st); output(s

30、t); 20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 2424 8.7 利用結(jié)構(gòu)體組織鏈表一、基本概念一、基本概念1. 動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配: 根據(jù)需要臨時(shí)分配內(nèi)存單元用以存放數(shù)據(jù)根據(jù)需要臨時(shí)分配內(nèi)存單元用以存放數(shù)據(jù), 當(dāng)數(shù)據(jù)不用時(shí)可以隨時(shí)釋放內(nèi)存單元當(dāng)數(shù)據(jù)不用時(shí)可以隨時(shí)釋放內(nèi)存單元2. 鏈表鏈表: 是可以動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種數(shù)據(jù)結(jié)構(gòu)是可以動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種數(shù)據(jù)結(jié)構(gòu) 它是由一組動(dòng)態(tài)數(shù)據(jù)鏈接而成的序列它是由一組動(dòng)態(tài)數(shù)據(jù)鏈接而成的序列3. 結(jié)點(diǎn)結(jié)點(diǎn): 鏈表中的每一個(gè)動(dòng)態(tài)數(shù)據(jù)稱為一個(gè)結(jié)點(diǎn)鏈表中的每一個(gè)動(dòng)態(tài)數(shù)據(jù)稱為一個(gè)結(jié)點(diǎn)4. 結(jié)點(diǎn)類型結(jié)點(diǎn)類型: 是一個(gè)包含指針項(xiàng)的結(jié)

31、構(gòu)體類型是一個(gè)包含指針項(xiàng)的結(jié)構(gòu)體類型 一般由兩部分組成一般由兩部分組成:(1) 數(shù)據(jù)成員數(shù)據(jù)成員: 存放數(shù)據(jù)存放數(shù)據(jù)(2) 指針成員指針成員: 存放下一個(gè)結(jié)點(diǎn)的地址存放下一個(gè)結(jié)點(diǎn)的地址struct sd int num; int score; struct sd *next ; ; 數(shù)據(jù)成員數(shù)據(jù)成員指針成員指針成員20082008東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室東北大學(xué)計(jì)算機(jī)基礎(chǔ)教研室 2525 頭指針頭指針表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)表尾結(jié)點(diǎn)表尾結(jié)點(diǎn)2010head 2010 1428 15709514281861570282NULL3NULL為空地址為空地址, 表示鏈表到此結(jié)束表示鏈表到此結(jié)束二、簡(jiǎn)單鏈表二、

32、簡(jiǎn)單鏈表#include struct sd int num; int score; struct sd *next ; ; void main( ) struct sd a,b,c,*head,*p; head=&a; a.num=1; a.score=95; a.next=&b; b.num=2; b.score=86; b.next=&c; c.num=3; c.score=82; c.next=NULL; p=head; while(p!=NULL) printf(“%3d%4dn”,p-num,p-score); p=p-next; head201014281

33、5702010abc19514282861570382NULLp201014281570NULL說(shuō)明說(shuō)明: 該程序雖然建立了一個(gè)鏈表該程序雖然建立了一個(gè)鏈表, 但這個(gè)鏈表是靜態(tài)的但這個(gè)鏈表是靜態(tài)的, 因?yàn)樗驗(yàn)樗慕Y(jié)點(diǎn)個(gè)數(shù)是固定的的結(jié)點(diǎn)個(gè)數(shù)是固定的, 不能按需要增加新的結(jié)點(diǎn)不能按需要增加新的結(jié)點(diǎn),也不能按需要?jiǎng)h也不能按需要?jiǎng)h除結(jié)點(diǎn)除結(jié)點(diǎn). 這樣的鏈表并不實(shí)用這樣的鏈表并不實(shí)用, 我們需要的是我們需要的是“動(dòng)態(tài)鏈表動(dòng)態(tài)鏈表”三、三、 處理動(dòng)態(tài)鏈表所需的函數(shù)處理動(dòng)態(tài)鏈表所需的函數(shù) ( 需用頭文件需用頭文件 )1. malloc 函數(shù)函數(shù) 原型原型 : void *malloc( unsigned

34、int size ) 作用作用 : 在內(nèi)存中開(kāi)辟一個(gè)長(zhǎng)度為在內(nèi)存中開(kāi)辟一個(gè)長(zhǎng)度為 size 的連續(xù)存儲(chǔ)空間的連續(xù)存儲(chǔ)空間 , 并將此存儲(chǔ)并將此存儲(chǔ) 空間的起始地址帶回空間的起始地址帶回注意注意 : (1) 函數(shù)返回值是指針函數(shù)返回值是指針, 但該指針是指向但該指針是指向void類型的類型的 , 因此在因此在 使用時(shí)希望這個(gè)指針指向其他類型需要用強(qiáng)制類型轉(zhuǎn)換使用時(shí)希望這個(gè)指針指向其他類型需要用強(qiáng)制類型轉(zhuǎn)換(2) 如果內(nèi)存缺少足夠大的空間進(jìn)行分配如果內(nèi)存缺少足夠大的空間進(jìn)行分配 , 則則 malloc 函數(shù)函數(shù) 返回值為返回值為“空指針空指針” (即即NULL)例例: struct sd *p;

35、p = (struct sd * ) malloc ( sizeof(struct sd) ) ;強(qiáng)制類型轉(zhuǎn)換強(qiáng)制類型轉(zhuǎn)換結(jié)構(gòu)體類型占用的字節(jié)長(zhǎng)度結(jié)構(gòu)體類型占用的字節(jié)長(zhǎng)度2. free函數(shù)函數(shù) 原型原型 : void free( void *ptr ) 作用作用 : 將指針變量將指針變量ptr指向的存儲(chǔ)空間釋放指向的存儲(chǔ)空間釋放 注意注意: (1) ptr的值不是任意的地址的值不是任意的地址, 必須是程序中執(zhí)行必須是程序中執(zhí)行malloc或或 calloc函數(shù)所返回的地址函數(shù)所返回的地址(2) 模型中模型中ptr是是void型型, 但調(diào)用但調(diào)用free函數(shù)時(shí)函數(shù)時(shí), 參數(shù)可能是參數(shù)可能是 其他

36、類型其他類型, 計(jì)算機(jī)系統(tǒng)會(huì)自動(dòng)進(jìn)行轉(zhuǎn)換計(jì)算機(jī)系統(tǒng)會(huì)自動(dòng)進(jìn)行轉(zhuǎn)換 例例: struct sd *p; p=(struct sd *) malloc (sizeof(struct sd) ; free(p);p42004200 四、四、 鏈表應(yīng)用舉例鏈表應(yīng)用舉例 1. 建立鏈表建立鏈表(表尾添加法表尾添加法) #include #include #define ST struct student ST int num ; int score ; ST *next ; ; #define LEN sizeof(ST) int n ; 宏定義宏定義ST , 以后書寫簡(jiǎn)單以后書寫簡(jiǎn)單求出結(jié)構(gòu)體類型占用

37、的字節(jié)數(shù)求出結(jié)構(gòu)體類型占用的字節(jié)數(shù)全局量全局量 , n 表示結(jié)點(diǎn)的個(gè)數(shù)表示結(jié)點(diǎn)的個(gè)數(shù)ST * creat(void) ST *head , *p1 , *p2 ; n=0 ; head=NULL ; p1=(ST *) malloc ( LEN ) ; scanf( “%d %d ”, &p1-num, &p1-score ) ; while ( p1-num!=0 ) n=n+1; if (n= =1) head=p1 ; else p2-next=p1 ; p2 = p1 ; p1 = (ST *) malloc (LEN) ; scanf( “%d %d ”, &

38、p1-num, &p1-score ) ; p2-next = NULL ; return( head ) ; headhead201020101428142815701570NULLp1p2326432642010201010951428n0 1 2 320101428208630820014281570NULL1570157032642. 輸出鏈表輸出鏈表void list ( ST *head ) ST *p ; p = head ; while ( p!=NULL ) printf(“%3d %4dn”, p-num, p-score ) ; p = p-next ; headhead2010201014281428157015702010201010951428208615703082NULLp201014281570NULLp120101428num20p22010headhead201020101428142815701570201020101095142828615703082NULL1570n3 23. 鏈表的刪除鏈表的刪除ST *del ( ST *head , int num ) ST *p1 , *p2 ; p1 = h