第8章-結(jié)構(gòu)體及其應(yīng)用-4學(xué)時(shí)

高級(jí)語(yǔ)言程序設(shè)計(jì)揭安全jieanquan@163.com江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院高級(jí)語(yǔ)言程序設(shè)計(jì)——基于計(jì)算思維能力培養(yǎng)高級(jí)語(yǔ)言程序設(shè)計(jì)——基于計(jì)算思維能力培養(yǎng)第8章結(jié)構(gòu)體及其應(yīng)用揭安全jieanquan@163.com江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院主要內(nèi)容結(jié)構(gòu)體類(lèi)型與結(jié)構(gòu)體變量指針結(jié)構(gòu)體的指針向函數(shù)傳遞結(jié)構(gòu)體結(jié)構(gòu)體數(shù)組動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)——單鏈表本章思維導(dǎo)圖為何要用結(jié)構(gòu)體8.18.1為何要用結(jié)構(gòu)體C語(yǔ)言中學(xué)習(xí)的基本數(shù)據(jù)類(lèi)型都不能獨(dú)立地來(lái)表示這些對(duì)象的全部屬性。結(jié)構(gòu)體類(lèi)型與

結(jié)構(gòu)體變量8.28.2.1結(jié)構(gòu)體類(lèi)型的聲明結(jié)構(gòu)體類(lèi)型定義的一般格式為： struct結(jié)構(gòu)體類(lèi)型名 {

數(shù)據(jù)類(lèi)型

屬性1;

數(shù)據(jù)類(lèi)型

屬性2; …

數(shù)據(jù)類(lèi)型

屬性n;};例如，structstudent{ charid[13]; //學(xué)號(hào) charname[9]; //姓名 intage; //年齡 charsex; //性別 charsfzh[19]; //身份證號(hào) charaddress[61]; //家庭住址 chartelNumber[12]; //電話號(hào)碼 charclassName[21]; //班級(jí)名稱(chēng)};structdate{intyear;intmonth;intday;};結(jié)構(gòu)體類(lèi)型的定義可以嵌套，即可以利用一個(gè)已定義的結(jié)構(gòu)體類(lèi)型作為別外一個(gè)結(jié)構(gòu)體類(lèi)型的屬性。structstudent{ charid[13]; //學(xué)號(hào) charname[9]; //姓名

structdatebirthday; //生日 charsex; //性別 charsfzh[19]; //身份證號(hào) charaddress[61]; //家庭住址 chartelNumber[12]; //電話號(hào)碼 charclassName[21]; //班級(jí)名稱(chēng)};8.2.2結(jié)構(gòu)體變量的定義1、結(jié)構(gòu)體變量定義的格式我們可以利用之前已定義好的structstudent結(jié)構(gòu)體類(lèi)型來(lái)聲明學(xué)生結(jié)構(gòu)體變量。structstudents1,s2;注意：結(jié)構(gòu)體類(lèi)型的完整名稱(chēng)為structstudent。為方便書(shū)寫(xiě)，我們可以用類(lèi)型定義符typedef將structstudent命名為一個(gè)新的名稱(chēng)。如：typedefstructstudentstuStru;//將structstudent命名為stuStru之后，便可在程序中使用stuStru等價(jià)地表示structstudent。例如：stuStrus1,s2;定義了兩個(gè)學(xué)生結(jié)構(gòu)體變量s1和s2。2、結(jié)構(gòu)體變量占用的字節(jié)數(shù)結(jié)構(gòu)體中的成員按定義順序占用連續(xù)的存儲(chǔ)空間。每個(gè)結(jié)構(gòu)體變量占用的字節(jié)數(shù)至少需等于所有成員（屬性）占用的內(nèi)存之和。我們可以用sizeof運(yùn)算符來(lái)獲得結(jié)構(gòu)體變量占用的字節(jié)數(shù)。 sizeof(stuStru);

或 sizeof(s1);8.2.3對(duì)結(jié)構(gòu)體變量的操作對(duì)結(jié)構(gòu)體變量的操作應(yīng)以其屬性為基本單位，具體格式如下：

結(jié)構(gòu)體變量名.成員名

其中“.”運(yùn)算符為成員運(yùn)算符。例如： stuStrus1,s2;

則s1.id表示s1的學(xué)號(hào)，表示s1的姓名等。注意事項(xiàng)：（1）在訪問(wèn)結(jié)構(gòu)體變量的成員時(shí)，要根據(jù)結(jié)構(gòu)體變量的成員類(lèi)型來(lái)進(jìn)行相應(yīng)的操作。例如：strcpy(s1.id,"201400120001");

可將"201400120001"存入s1的學(xué)號(hào)。注意：s1.id="201400120001"是錯(cuò)誤的。注意事項(xiàng)：（2）對(duì)于嵌套的結(jié)構(gòu)體變量，應(yīng)該逐級(jí)訪問(wèn)其成員，直至非結(jié)構(gòu)體成員。如：s1.birthday.year=1996;s1.birthday.month=10;s1.birthday.day=20;完成將s1的生日設(shè)置為1996年10月20日。注意事項(xiàng)：（3）不能將結(jié)構(gòu)體變量作為一個(gè)整體進(jìn)行輸入輸出，只能對(duì)變量中的各個(gè)成員輸入輸出。例如：gets(); //輸入s1的姓名printf("%s",); //輸出s1的姓名scanf("%d",&s1.birthday.year);//輸入s1的出生年份printf("%d",s1.birthday.year);//輸出s1的出生年份注意事項(xiàng)：（4）兩個(gè)同類(lèi)型的結(jié)構(gòu)體變量可以直接賦值，賦值號(hào)右邊結(jié)構(gòu)體變量的成員將依次賦值給左邊結(jié)構(gòu)體變量的各個(gè)成員。例如：s2=s1;將使s2與s1具有相同的屬性值。8.2.4結(jié)構(gòu)體變量的初始化結(jié)構(gòu)體變量可以在聲明時(shí)進(jìn)行初始化，變量后面的一組數(shù)據(jù)用“{}”括起來(lái)，其順序應(yīng)該與結(jié)構(gòu)體中的成員（屬性）順序保持一致，且對(duì)應(yīng)的類(lèi)型應(yīng)賦值相容。例如： stuStrus1={"201400120001","李明",{1996,10,20},'M',"36010119961020****","南昌市東湖區(qū)","","物聯(lián)網(wǎng)1班"};【例8.1】結(jié)構(gòu)體類(lèi)型定義及結(jié)構(gòu)體變量的定義與初始化示例。#include<stdio.h>structdate{ intyear; intmonth; intday;};【例8.1】結(jié)構(gòu)體類(lèi)型定義及結(jié)構(gòu)體變量的定義與初始化示例。structstudent{ charid[13]; //學(xué)號(hào) charname[9]; //姓名

structdatebirthday; //生日 charsex; //性別 charsfzh[19]; //身份證號(hào) charaddress[61]; //家庭住址 chartelNumber[12]; //電話號(hào)碼 charclassName[21]; //班級(jí)名稱(chēng)};typedefstructstudentstuStru;intmain(){stuStrus1={"201400120001","李明",{1996,10,20},'M',"36010119961020****","南昌市東湖區(qū)","","物聯(lián)網(wǎng)1班"};stuStrus2;

s2=s1; //結(jié)構(gòu)體變量賦值printf("學(xué)

號(hào):%s\n",s2.id);printf("姓

名:%s\n",);printf("出生日期:%d-%d-%d\n",s2.birthday.year,s2.birthday.month,s2.birthday.day);printf("性

別:%s\n",s2.sex=='M'?"男":"女");printf("身份證號(hào):%s\n",s2.sfzh);printf("家庭住址:%s\n",s2.address);printf("電話號(hào)碼:%s\n",s2.telNumber);printf("班級(jí)名稱(chēng):%s\n",s2.className);return0;}學(xué)號(hào):201400120001姓名:李明出生日期:1996-10-20性別:男身份證號(hào):36010119961020****家庭住址:南昌市東湖區(qū)電話號(hào)碼:班級(jí)名稱(chēng):物聯(lián)網(wǎng)1班程序運(yùn)行情況如下：指向結(jié)構(gòu)體的指針8.38.3指向結(jié)構(gòu)體的指針結(jié)構(gòu)體指針變量的定義格式如下：結(jié)構(gòu)體類(lèi)型名*指針變量名;例如，對(duì)例8.1定義的結(jié)構(gòu)體類(lèi)型stuStru，可以定義結(jié)構(gòu)體變量和指針變量： stuStrus,*p; p=&s;將使指針p保存s的首地址。當(dāng)結(jié)構(gòu)體指針指向某結(jié)構(gòu)體變量后，借助指針有兩種方式來(lái)訪問(wèn)該指針指向的對(duì)象屬性。（1）通過(guò)“(*指針).屬性名”來(lái)訪問(wèn)指針指向的對(duì)象的屬性。例如，若p為指向結(jié)構(gòu)體變量s的指針，則：scanf("%d",&(*p).birthday.year);printf("%s",(*p).name);分別完成p指向?qū)ο蟮某錾攴莸妮斎牒托彰妮敵觥＃?）通過(guò)“指針->屬性名”來(lái)訪問(wèn)指針指向的對(duì)象的屬性（->運(yùn)算符由減號(hào)-和大于號(hào)>組合而成）。當(dāng)p為指向結(jié)構(gòu)體變量s的指針時(shí)p->birthday.year可引用s的出生年份即s.birthday.year；p->name可引用。特別地，當(dāng)p為結(jié)構(gòu)體類(lèi)型的指針時(shí)，可以通過(guò)malloc函數(shù)來(lái)為p動(dòng)態(tài)分配結(jié)構(gòu)體空間，如： stuStru*p; p=(stuStru*)malloc(sizeof(stuStru));當(dāng)p指向的動(dòng)態(tài)結(jié)構(gòu)體使用完成后，應(yīng)采用free(p);語(yǔ)句來(lái)將該空間釋放。向函數(shù)傳遞結(jié)構(gòu)體8.48.4.1值傳遞傳值調(diào)用為單向值傳遞，函數(shù)調(diào)用發(fā)生時(shí)，系統(tǒng)將結(jié)構(gòu)體變量的值拷貝一份給形式參數(shù)，在函數(shù)中所有的操作都是針對(duì)形式參數(shù)進(jìn)行的，實(shí)際參數(shù)的值不會(huì)因形參值的改變而改變。#include<stdio.h>structdate{ intyear; intmonth; intday;};【例8.2】結(jié)構(gòu)體變量傳值調(diào)用示例。voidfun(structdated){d.year=2008;d.month=8;d.day=8;}intmain(){structdated={2014,9,1};printf("%d-%d-%d\n",d.year,d.month,d.day);fun(d); //傳值調(diào)用printf("%d-%d-%d\n",d.year,d.month,d.day);return0;}2014-9-12014-9-18.4.2地址傳遞當(dāng)函數(shù)的形參為指向結(jié)構(gòu)體變量的指針類(lèi)型時(shí)，可以將結(jié)構(gòu)體變量的地址作為函數(shù)的實(shí)參，完成結(jié)構(gòu)體變量的按地址調(diào)用。【例8.3】結(jié)構(gòu)體變量傳地址調(diào)用示例。#include<stdio.h>structdate{ intyear; intmonth; intday;};voidfun(structdate*p){

p->year=2008;p->month=8;

p->day=8;}intmain(){structdated={2014,9,1};printf("%d-%d-%d\n",d.year,d.month,d.day);fun(&d); //傳地址調(diào)用printf("%d-%d-%d\n",d.year,d.month,d.day);return0;}2014-9-12008-8-8如果結(jié)構(gòu)體變量只想被函數(shù)引用，而不想被其修改，可以用const修辭函數(shù)的形參聲明。如：voidfun(conststructdate*p)

則在程序中只能訪問(wèn)p指向的結(jié)構(gòu)體變量，而不能對(duì)它進(jìn)行修改。結(jié)構(gòu)體數(shù)組8.58.5結(jié)構(gòu)體數(shù)組序號(hào)班級(jí)名稱(chēng)姓名學(xué)號(hào)022級(jí)網(wǎng)絡(luò)工程聶加望2208066047122級(jí)網(wǎng)絡(luò)工程潘杰2208066048222級(jí)網(wǎng)絡(luò)工程秦彪2208066049322級(jí)網(wǎng)絡(luò)工程邱強(qiáng)2208066051422級(jí)網(wǎng)絡(luò)工程唐重喜22080660548.5結(jié)構(gòu)體數(shù)組8.5.1結(jié)構(gòu)體數(shù)組的定義最常用的結(jié)構(gòu)體一維數(shù)組的定義格式如下：結(jié)構(gòu)體類(lèi)型

數(shù)組名[數(shù)組大小];例如，假設(shè)stuStru是已定義好的學(xué)生結(jié)構(gòu)體類(lèi)型，則下面的語(yǔ)句定義了大小為10的學(xué)生結(jié)構(gòu)體數(shù)組s。stuStrus[10];訪問(wèn)結(jié)構(gòu)體數(shù)組的方法與普通數(shù)組類(lèi)似，通過(guò)下標(biāo)來(lái)引用數(shù)組元素。例如： printf("%s",s[2].id);當(dāng)然，我們也可以用動(dòng)態(tài)內(nèi)存分配的方法，來(lái)獲得動(dòng)態(tài)結(jié)構(gòu)體數(shù)組。例如： stuStru*s; s=(stuStru*)malloc(10*sizeof(stuStru));8.5.2結(jié)構(gòu)體數(shù)組的初始化與引用1、結(jié)構(gòu)體數(shù)組的初始化結(jié)構(gòu)體數(shù)組在定義的同時(shí)，可以進(jìn)行初始化，初始化結(jié)構(gòu)體數(shù)組的規(guī)則與初始化普通數(shù)組具有類(lèi)似的規(guī)則。8.5.2結(jié)構(gòu)體數(shù)組的初始化與引用1、結(jié)構(gòu)體數(shù)組的初始化結(jié)構(gòu)體數(shù)組的初始化列表包括在一對(duì)“{}”內(nèi)，在其內(nèi)部每個(gè)元素的成員初始化列表用“{}”括起來(lái)。若只對(duì)部分元素初始化，則其它元素將被自動(dòng)初始化為0。當(dāng)省略數(shù)組大小時(shí)，系統(tǒng)會(huì)根據(jù)初始化列表的項(xiàng)數(shù)來(lái)自動(dòng)確定數(shù)組大小?！纠?.4】結(jié)構(gòu)體數(shù)組的初始化與引用示例。#include<stdio.h>#defineN5structbook{charid[6]; //圖書(shū)編號(hào)charname[31]; //書(shū)名floatprice; //單價(jià)charauthor[13]; //作者};typedefstructbookbookStru;intmain(){bookStrub[N]={{"10001","C語(yǔ)言程序設(shè)計(jì)現(xiàn)代方法",79,"K.N.King"},{"10002","CPrimerPlus（第五版）",60,"StephenPrata"},{"10003","C語(yǔ)言程序設(shè)計(jì)",43,"蘇小紅等"},{"10004","程序設(shè)計(jì)基礎(chǔ)（第3版）",35,"吳文虎"}};inti;printf("編號(hào)

圖書(shū)名稱(chēng)

單價(jià)

作者\(yùn)n");for(i=0;i<N;i++){ printf("%-8s",b[i].id); //輸出圖書(shū)編號(hào) printf("%-30s",b[i].name); //輸出書(shū)名 printf("%-8.2f",b[i].price); //輸出單價(jià) printf("%-12s\n",b[i].author); //輸出作者}return0;}2、利用指針訪問(wèn)結(jié)構(gòu)體數(shù)組當(dāng)結(jié)構(gòu)體指針指向結(jié)構(gòu)體數(shù)組時(shí)，可以通過(guò)結(jié)構(gòu)體指針來(lái)訪問(wèn)數(shù)組各元素，對(duì)結(jié)構(gòu)體指針執(zhí)行算術(shù)運(yùn)算是以結(jié)構(gòu)體變量占用的字節(jié)數(shù)為基本單位的?！纠?.5】指針訪問(wèn)結(jié)構(gòu)體數(shù)組示例#include<stdio.h>#defineN100structbook{charid[6]; //圖書(shū)編號(hào)charname[31]; //書(shū)名floatprice; //單價(jià)charauthor[13]; //作者};typedefstructbookbookStru;intmain(){bookStrub[N],*p;intn;p=b;printf("請(qǐng)輸入圖書(shū)數(shù)量：");scanf("%d",&n);if(n<N){printf("請(qǐng)按以下格式輸入%d本圖書(shū)信息(用Tab鍵分隔):\n",n);printf("編號(hào)

圖書(shū)名稱(chēng)

單價(jià)

作者\(yùn)n");while(p<b+n){scanf("%s",p->id); //輸入圖書(shū)編號(hào)scanf("%s",p->name); //輸入圖書(shū)名稱(chēng)scanf("%f",&p->price); //輸入圖書(shū)單價(jià)scanf("%s",p->author); //輸入圖書(shū)作者p++;}

printf("編號(hào)

圖書(shū)名稱(chēng)

單價(jià)

作者\(yùn)n");printf("----------------------------------------------------\n");for(p=b;p<b+n;p++){printf("%-8s",p->id); printf("%-30s",(*p).name);printf("%-8.2f",(*p).price);printf("%-12s\n",p->author);}}return0;}請(qǐng)輸入圖書(shū)數(shù)量:3↙請(qǐng)按以下格式輸入3本圖書(shū)信息(用Tab鍵分隔):編號(hào)圖書(shū)名稱(chēng)

單價(jià)作者10001C語(yǔ)言程序設(shè)計(jì)現(xiàn)代方法79.00K.N.King↙10002CPrimerPlus（第五版）

60.00StephenPrata↙10003C語(yǔ)言程序設(shè)計(jì)

43.00蘇小紅等↙編號(hào)圖書(shū)名稱(chēng)

單價(jià)作者------------------------------------------------------------------------10001C語(yǔ)言程序設(shè)計(jì)現(xiàn)代方法79.00K.N.King10002CPrimerPlus（第五版）60.00StephenPrata10003C語(yǔ)言程序設(shè)計(jì)43.00蘇小紅等8.5.3結(jié)構(gòu)體數(shù)組的應(yīng)用準(zhǔn)考證號(hào)姓名語(yǔ)文數(shù)學(xué)英語(yǔ)綜合總分110100101張三120123110265

110100102李四96102130242

…

【例8.5】試編寫(xiě)程序，定義用于存儲(chǔ)學(xué)生信息的結(jié)構(gòu)體數(shù)組，輸入學(xué)生的準(zhǔn)考證號(hào)、姓名和成績(jī)信息，計(jì)算每位學(xué)生的總分，并按總分由高到低輸出學(xué)生信息表。成績(jī)統(tǒng)計(jì)輸入求和排序輸出#include<stdio.h>#defineN10000structstudent{charid[10]; //準(zhǔn)考證號(hào)charname[9]; //姓名floatscore[4]; //大小為4的數(shù)組，分別存儲(chǔ)4門(mén)課程分?jǐn)?shù)floattotal; //總分};typedefstructstudentstuStru;/*@函數(shù)名稱(chēng)：input入口參數(shù)：stuStrus[]@函數(shù)功能：學(xué)生信息錄入，函數(shù)返回信息輸入成功的學(xué)生人數(shù)*/intinput(stuStrus[]){intn=-1,i;printf("請(qǐng)按下列格式輸入學(xué)生信息（行首輸入q結(jié)束輸入）：\n");printf("----------------------------------------------------\n");printf("準(zhǔn)考證號(hào)\t姓名\t語(yǔ)文\t數(shù)學(xué)\t英語(yǔ)\t綜合\n");do{n++;

scanf("%s",s[n].id); //輸入準(zhǔn)考證號(hào)if(s[n].id[0]=='q'||s[n].id[0]=='Q')

break;scanf("%s",s[n].name); //輸入姓名for(i=0;i<4;i++) //輸入4門(mén)課程成績(jī)scanf("%f",&s[n].score[i]);}while(1);returnn; //返回有效學(xué)生人數(shù)}/*@函數(shù)名稱(chēng)：sum入口參數(shù)：stuStru*s,intn@函數(shù)功能：求學(xué)生的高考總分*/voidsum(stuStru*s,intn){inti,j;stuStru*p=s; //采用指針?lè)ㄔL問(wèn)數(shù)組while(p<s+n){p->total=0; //總分清0for(j=0;j<4;j++)p->total+=p->score[j];

p++;}}/*@函數(shù)名稱(chēng)：selectSort入口參數(shù)：stuStrus[],intn@函數(shù)功能：采用選擇排序法對(duì)學(xué)生信息按總分由高到低排序*/voidselectSort(stuStrus[],intn){inti,j,k,maxIndex;stuStrutemp;for(i=0;i<n-1;i++){maxIndex=i;for(j=i+1;j<n;j++) //查找最高分所在記錄if(s[j].total>s[maxIndex].total)maxIndex=j;if(i!=maxIndex){temp=s[i];s[i]=s[maxIndex];s[maxIndex]=temp;}}}/*@函數(shù)名稱(chēng)：print入口參數(shù)：stuStrus[],intn@函數(shù)功能：輸出學(xué)生信息*/voidprint(stuStru*s,intn){inti,j;if(n>0){printf("%-12s%-12s","準(zhǔn)考證號(hào)","姓名"); //輸出表頭printf("%-8s%-8s%-8s%-8s%-8s\n","語(yǔ)文","數(shù)學(xué)","英語(yǔ)","綜合","總分");printf("----------------------------------------------------\n");for(i=0;i<n;i++,s++){printf("%-12s",s->id); //輸出準(zhǔn)考證號(hào)printf("%-12s",s->name); //輸出姓名for(j=0;j<4;j++) //輸出成績(jī)printf("%-8.2f",s->score[j]);printf("%-8.2f\n",s->total); //輸出總分}}}intmain(){stuStrus[N];intn;

n=input(s); //輸入

sum(s,n); //求和selectSort(s,n); //按總分由高到低排序print(s,n); //輸出return0;}請(qǐng)按下列格式輸入學(xué)生信息（行首輸入q結(jié)束輸入）：-----------------------------------------------------------------------------準(zhǔn)考證號(hào)姓名語(yǔ)文數(shù)學(xué)英語(yǔ)綜合110100101王曉東112120121230↙110100102李科108130125241↙110100103趙國(guó)慶9998101200↙110100104鄒婕121105130250↙110100105楊婷130132128256↙q↙準(zhǔn)考證號(hào)姓名語(yǔ)文數(shù)學(xué)英語(yǔ)綜合總分-----------------------------------------------------------------------------110100105楊婷130.00132.00128.00256.00646.00110100104鄒婕121.00105.00130.00250.00606.00110100102李科108.00130.00125.00241.00604.00110100101王曉東112.00120.00121.00230.00583.00110100103趙國(guó)慶99.0098.00101.00200.00498.00動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

——單鏈表8.68.6動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)——單鏈表數(shù)組要求在內(nèi)存中占用連續(xù)的存儲(chǔ)空間。一方面，當(dāng)某程序運(yùn)行時(shí)需分配的數(shù)組規(guī)模較大時(shí)，常會(huì)出現(xiàn)內(nèi)存無(wú)法提供滿(mǎn)足程序要求的空閑區(qū)的情況發(fā)生。另一方面，由于數(shù)組在定義時(shí)大小固定，當(dāng)數(shù)據(jù)量超出數(shù)組容量時(shí)，不便動(dòng)態(tài)擴(kuò)展新的存儲(chǔ)空間。而采用鏈表可以有效解決這一問(wèn)題，鏈表是線性結(jié)構(gòu)的另一種有效存儲(chǔ)結(jié)構(gòu)。它為線性結(jié)構(gòu)中的各元素獨(dú)立地申請(qǐng)存儲(chǔ)空間，并且在每個(gè)元素內(nèi)增設(shè)指針來(lái)記錄其前驅(qū)或后續(xù)元素的位置。這種結(jié)構(gòu)不要求表中邏輯上相鄰的元素占用物理上相鄰的存儲(chǔ)空間。因此，能提高內(nèi)存空間利用率，同時(shí)便動(dòng)態(tài)擴(kuò)展。8.6動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)——單鏈表8.6.1單鏈表的定義鏈表首結(jié)點(diǎn)指針結(jié)點(diǎn)結(jié)點(diǎn)值后續(xù)結(jié)點(diǎn)地址8.6.1單鏈表的定義為建立單鏈表，首先需要一個(gè)表示表中單個(gè)結(jié)點(diǎn)的結(jié)構(gòu)體類(lèi)型。structnode{ intdata; structnode*next;

};typedefstructnodelinknode;

typedeflinknode*linklist;

屬性域后續(xù)結(jié)點(diǎn)指針結(jié)點(diǎn)類(lèi)型結(jié)點(diǎn)指針類(lèi)型可根據(jù)需要擴(kuò)展屬性域接下來(lái)，便可用linknode來(lái)聲明結(jié)構(gòu)體變量，用linklist來(lái)聲明指向結(jié)構(gòu)體的指針變量。例如：linklisthead=NULL;定義了一個(gè)結(jié)構(gòu)體指針，并將其初始化為空，表示初始鏈表head為空表。8.6.1單鏈表的定義8.6.2在單鏈表插入新結(jié)點(diǎn)要在單鏈表中插入值為x的結(jié)點(diǎn)，首先要生成結(jié)點(diǎn)結(jié)構(gòu)體，我們可以定義指針q來(lái)指向新生成的結(jié)點(diǎn)空間（q指向的結(jié)點(diǎn)可簡(jiǎn)稱(chēng)為結(jié)點(diǎn)q）。linklistq; //結(jié)點(diǎn)指針生成新結(jié)點(diǎn)，并將待插入數(shù)據(jù)存入結(jié)點(diǎn)的語(yǔ)句為：q=(linklist)malloc(sizeof(linknode)); q->data=x; //假設(shè)x為待存入的數(shù)據(jù)下面討論如何將q指向的結(jié)點(diǎn)插入到單鏈表head中。根據(jù)鏈表狀態(tài)和插入的位置，通常可以分為三種情況：8.6.2在單鏈表插入新結(jié)點(diǎn)原單鏈表head為空表（head==NULL），新加入的結(jié)點(diǎn)成為鏈表的第1個(gè)結(jié)點(diǎn)。原鏈表不為空，新結(jié)點(diǎn)q插入在單鏈表的最前面。原鏈表不為空，新結(jié)點(diǎn)q插入到鏈表中由p指向的結(jié)點(diǎn)后面。8.6.3建立單鏈表【例8.6】編寫(xiě)函數(shù)，將鍵盤(pán)輸入的整數(shù)序列依次存入初始為空的單鏈表，函數(shù)返回新建單鏈表第一個(gè)結(jié)點(diǎn)地址。尾插法建立單鏈表#include<stdio.h>#include<stdlib.h>structnode{intdata;structnode*next;};typedefstructnodelinknode;typedeflinknode*linklist;Linklist.h/*@函數(shù)名稱(chēng)：creatLink入口參數(shù)：無(wú)@函數(shù)功能：建立單鏈表，函數(shù)返回單鏈表首結(jié)點(diǎn)地址*/linklistcreatLink(){linklisthead,tail,q;intx;head=tail=NULL; //初始化空鏈表printf("請(qǐng)輸入整數(shù)序列（以空格分隔，以0作為結(jié)束）：\n");scanf("%d",&x);while(x!=0){q=(linklist)malloc(sizeof(linknode));//生成新結(jié)點(diǎn)q->data=x;if(head==NULL) //原鏈表為空head=tail=q;else //原鏈表不為空{(diào)tail->next=q;tail=q;} scanf("%d",&x);}if(tail!=NULL) tail->next=NULL;//置鏈表結(jié)束標(biāo)志returnhead;}#include"linklist.h"intmain(){linklisthead;head=creatLink();return0;}8.6.4單鏈表的遍歷所謂單鏈表的遍歷就是對(duì)單鏈表的所有結(jié)點(diǎn)進(jìn)行一遍訪問(wèn)。【例8.7】請(qǐng)?jiān)趌inklist.h中定義函數(shù)voidprint(linklisthead)，輸出單鏈表head的所有結(jié)點(diǎn)值。p=head;printf(“%5d”,p->data);p=p->next;/*@函數(shù)名稱(chēng)：print入口參數(shù)：linklisthead@函數(shù)功能：輸出單鏈表內(nèi)容*/voidprint(linklisthead){linklistp=head;printf("List:\n")while(p!=NULL)//當(dāng)p未遇到鏈表結(jié)束標(biāo)志時(shí){printf("%5d",p->data); //輸出當(dāng)前結(jié)點(diǎn)值

p=p->next; //指向下一個(gè)結(jié)點(diǎn)}printf("\n");}#include"linklist.h"intmain(){linklisthead;head=creatLink(); //建立單鏈表print(head); //輸出單鏈表return0;}請(qǐng)輸入整數(shù)序列（以空格分隔，以0作為結(jié)束）：1020304050600List:1020304050608.6.5在單鏈表中查找結(jié)點(diǎn)在單鏈表中查找結(jié)點(diǎn)可采用順序查找的方法，其查找過(guò)程可借助于對(duì)單鏈表的遍歷來(lái)完成。【例8.8】編寫(xiě)函數(shù)linklistsearchLink(linklisthead,intx)，在單鏈表head中查找值為x的結(jié)點(diǎn)，若查找成功返回該結(jié)點(diǎn)地址，否則返回NULL?！痉治觥坑靡粋€(gè)指針p，從單鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，依次向后查找。linklistsearchLink(linklisthead,intx){linklistp=head;while(p!=NULL&&p->data!=x)p=p->next;returnp;}intmain(){linklisthead,p;intx;head=creatLink(); //建立單鏈表print(head); //輸出單鏈表printf("請(qǐng)輸入要查找的結(jié)點(diǎn)值：");scanf("%d",&x);p=searchLink(head,x);if(p!=NULL)printf("查找成功！");elseprintf("查找失??！\n");return0;}8.6.6在單鏈表中刪除結(jié)點(diǎn)在單鏈表中刪除結(jié)點(diǎn)需要知道被刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的位置。假設(shè)p指向被刪除結(jié)點(diǎn)，pre指向p的前驅(qū)結(jié)點(diǎn)，則刪除操作分兩種情況：（1）被刪除結(jié)點(diǎn)是單鏈表的第一個(gè)結(jié)點(diǎn)（2）被刪除結(jié)點(diǎn)不是單鏈表的第一個(gè)結(jié)點(diǎn)（1）被刪除結(jié)點(diǎn)是單鏈表的第一個(gè)結(jié)點(diǎn)（2）被刪除結(jié)點(diǎn)不是單鏈表的第一個(gè)結(jié)點(diǎn)【例8.9】編寫(xiě)一個(gè)函數(shù)linklistdeleteList(linklisthead,intx)，刪除單鏈表head中值為x的結(jié)點(diǎn)。#include"linklist.h"/*@函數(shù)名稱(chēng)deleteList入口參數(shù)：linklisthead,intx@函數(shù)功能：在鏈表head中刪除第一個(gè)值為x的結(jié)點(diǎn)@出口參數(shù)：返回刪除后的鏈表首結(jié)點(diǎn)地址*/linklistdeleteList(linklisthead,intx){ linklistpre,p; pre=NULL; p=head; while(p!=NULL&&p->data!=x) { pre=p; p=p->next; }if(p) //查找成功{if(pre==NULL) //情況（1）：被刪除結(jié)點(diǎn)是鏈表的第一個(gè)結(jié)點(diǎn)head=head->next;else//情況（2）：被刪除結(jié)點(diǎn)不是鏈表的第一