第7章 結(jié)構(gòu)和鏈表

《程序設(shè)計(jì)》1第7章結(jié)構(gòu)和鏈表《程序設(shè)計(jì)》2目錄7.1結(jié)構(gòu)類型和結(jié)構(gòu)變量7.1.1結(jié)構(gòu)類型和結(jié)構(gòu)變量7.1.2結(jié)構(gòu)變量初始化7.1.3結(jié)構(gòu)指針變量7.1.4結(jié)構(gòu)變量的引用7.2結(jié)構(gòu)數(shù)組7.3結(jié)構(gòu)形參和結(jié)構(gòu)指針形參7.4鏈表及其應(yīng)用7.5聯(lián)合7.6位域7.7枚舉7.8類型定義《程序設(shè)計(jì)》37.1結(jié)構(gòu)類型和結(jié)構(gòu)變量結(jié)構(gòu)類型：自己建立數(shù)據(jù)類型一個(gè)數(shù)據(jù)實(shí)體常常包含多項(xiàng)不同屬性的數(shù)據(jù)信息一個(gè)學(xué)生的數(shù)據(jù)實(shí)體可能要包含以下多項(xiàng)數(shù)據(jù)信息:學(xué)號、姓名、性別、年齡、成績、家庭地址這類實(shí)體的數(shù)據(jù)因所包含的成分類型不同，不能用單個(gè)數(shù)組來表示，也不便將它們的成分分拆成多個(gè)獨(dú)立的單個(gè)數(shù)據(jù)項(xiàng)，因?yàn)檫@樣會失去實(shí)體的整體性C語言用結(jié)構(gòu)數(shù)據(jù)類型描述由若干獨(dú)立意義成分組成的數(shù)據(jù)實(shí)體，是允許自己建立由不同類型數(shù)據(jù)組成的組合型的數(shù)據(jù)結(jié)構(gòu)《程序設(shè)計(jì)》47.1.1結(jié)構(gòu)類型和結(jié)構(gòu)變量結(jié)構(gòu)類型的定義定義一個(gè)結(jié)構(gòu)類型的一般形式為

struct結(jié)構(gòu)類型名{

成分說明表

};其中，關(guān)鍵字“struct”引出結(jié)構(gòu)類型的定義struct之后任選的標(biāo)識符是結(jié)構(gòu)類型的名字用花括號括住的是一張?jiān)摻Y(jié)構(gòu)類型的成分說明表，指明組成此種結(jié)構(gòu)類型全部成分《程序設(shè)計(jì)》5【例】結(jié)構(gòu)類型定義示例例如，由日、月、年組成的日期結(jié)構(gòu)類型為：

structdate{intday;/*日*/intmonth;/*月*/intyear;/*年*/};某廠職工信息管理系統(tǒng)中職工信息結(jié)構(gòu)類型為：

structperson{/*職工信息結(jié)構(gòu)類型*/char*name;/*姓名*/char*address;/*地址*/floatsalary;/*基本工資*/floataddition;/*附加工資*/floatcost;/*房租水電費(fèi)*/

structdatehiredate;

/*工作日期，說明結(jié)構(gòu)類型可嵌套*/};一個(gè)結(jié)構(gòu)類型中的某些成分可以是其它結(jié)構(gòu)類型。這種嵌套不能包含自身，但允許在定義中引用自己，即可以有指針成分，該成分能指向如同定義一樣的結(jié)構(gòu)《程序設(shè)計(jì)》6結(jié)構(gòu)變量在結(jié)構(gòu)類型定義中，詳細(xì)列出了結(jié)構(gòu)類型所包含的每個(gè)成分的名及其類型。結(jié)構(gòu)類型定義只是表明一種數(shù)據(jù)類型，是定義一種數(shù)據(jù)結(jié)構(gòu)的“模式”或“樣板”，并不定義“實(shí)物”，不要求分配存儲單元。程序要使用結(jié)構(gòu)數(shù)據(jù)，必須定義結(jié)構(gòu)變量結(jié)構(gòu)變量在存在期間要占用存儲單元，它的成分個(gè)數(shù)和各成分的類型與結(jié)構(gòu)類型定義中的成分個(gè)數(shù)和各成分的類型相一致具有結(jié)構(gòu)類型的變量就是結(jié)構(gòu)變量，結(jié)構(gòu)變量也簡稱結(jié)構(gòu)《程序設(shè)計(jì)》7結(jié)構(gòu)變量的定義程序定義結(jié)構(gòu)變量有兩種不同的方法方法一：先定義結(jié)構(gòu)類型，再定義結(jié)構(gòu)變量方法二：定義結(jié)構(gòu)類型時(shí)，同時(shí)定義結(jié)構(gòu)變量方法一：先定義結(jié)構(gòu)類型，再定義結(jié)構(gòu)變量其一般形式：struct結(jié)構(gòu)類型名結(jié)構(gòu)變量標(biāo)識符表；如利用已定義的結(jié)構(gòu)類型structstdType，structstdTypest1,st2,stArray[200];定義了兩個(gè)結(jié)構(gòu)變量st1和st2，另定義數(shù)組stArray[]的元素類型為structstdType《程序設(shè)計(jì)》8結(jié)構(gòu)變量的定義（續(xù)）方法一：先定義結(jié)構(gòu)類型，再定義結(jié)構(gòu)變量定義結(jié)構(gòu)變量的寫法與定義一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)類型變量有區(qū)別在定義結(jié)構(gòu)變量的這種方法中，不僅要明確指明變量的類型為結(jié)構(gòu)(struct)，而且同時(shí)要指明某一特定的結(jié)構(gòu)類型名(如stdType)在定義標(biāo)準(zhǔn)數(shù)據(jù)類型的變量時(shí)，只需指明其類型即可，如“inti;”其它定義結(jié)構(gòu)變量的例子

structdatedate1,date2;/*定義兩個(gè)日期變量*/structpersonemployee;/*定義一個(gè)職工變量*/定義兩個(gè)structdate型變量date1和date2，一個(gè)structperson型變量employee《程序設(shè)計(jì)》9結(jié)構(gòu)變量的定義（續(xù)）方法二：定義結(jié)構(gòu)類型時(shí)，同時(shí)定義結(jié)構(gòu)變量其一般形式：

struct結(jié)構(gòu)類型名{

成分說明表

}結(jié)構(gòu)變量標(biāo)識符表;如代碼

structpoint{/*說明繪圖程序的坐標(biāo)類型*/intx;inty;}p1,p2;定義structpoint型變量p1、p2。在這種定義形式中，如某種形式的結(jié)構(gòu)類型只是一次性定義幾個(gè)變量，還可以省略結(jié)構(gòu)類型名，直接定義結(jié)構(gòu)變量《程序設(shè)計(jì)》10結(jié)構(gòu)變量的定義（續(xù)）方法二：定義結(jié)構(gòu)類型時(shí)，同時(shí)定義結(jié)構(gòu)變量如

struct{charname[20];/*產(chǎn)品名稱*/intnum;/*產(chǎn)品編號*/floatprice;/*價(jià)格*/floatquantity;/*數(shù)量*/}part;/*庫存產(chǎn)品*/《程序設(shè)計(jì)》11結(jié)構(gòu)變量的定義（續(xù)）由于結(jié)構(gòu)類型名、結(jié)構(gòu)變量名和結(jié)構(gòu)類型的成分名有不同的應(yīng)用場合，分別出現(xiàn)在不同意義的程序上下文中，即使結(jié)構(gòu)類型名、結(jié)構(gòu)變量名、結(jié)構(gòu)類型的成分名有相同的名，編譯程序也能根據(jù)它們在源程序文件中出現(xiàn)的上、下文，區(qū)別出名的不同意義如：structs{intx;ints;}s;則“structs”中的s表示結(jié)構(gòu)類型，“ints;”中的s為成分名。在語句中，對s的引用是結(jié)構(gòu)變量s。編譯程序會根據(jù)標(biāo)識符s出現(xiàn)的上、下文確定其究竟是結(jié)構(gòu)類型名，或是結(jié)構(gòu)變量名，或是結(jié)構(gòu)類型的成分名定義結(jié)構(gòu)體類型變量(1)結(jié)構(gòu)體類型與結(jié)構(gòu)體變量是不同的概念，不要混淆。只能對變量賦值、存取或運(yùn)算，而不能對一個(gè)類型賦值、存取或運(yùn)算。在編譯時(shí)，對類型是不分配空間的，只對變量分配空間。(2)結(jié)構(gòu)體類型中的成員名可以與程序中的變量名相同，但二者不代表同一對象。(3)對結(jié)構(gòu)體變量中的成員（即“域”），可以單獨(dú)使用，它的作用與地位相當(dāng)于普通變量?！冻绦蛟O(shè)計(jì)》12《程序設(shè)計(jì)》137.1.2結(jié)構(gòu)變量初始化結(jié)構(gòu)變量初始化在定義結(jié)構(gòu)變量時(shí)可同時(shí)給它置初值結(jié)構(gòu)變量初始化時(shí)，要按其結(jié)構(gòu)類型定義中的各成分順序逐一給出各成分的初值。如

structpoint{/*說明繪圖程序的坐標(biāo)類型*/intx;inty;}p3={20，50};靜態(tài)結(jié)構(gòu)變量初始化如staticstructdated3={24,11,2008};《程序設(shè)計(jì)》14結(jié)構(gòu)變量初始化（續(xù)）結(jié)構(gòu)變量初始化對初值表達(dá)式的要求與數(shù)組變量初始化的要求相同，也遵守與數(shù)組變量初始化相同的規(guī)則：靜態(tài)的和全局的結(jié)構(gòu)變量初始化是在程序執(zhí)行之前完成靜態(tài)的結(jié)構(gòu)變量未指定初值的，自動(dòng)置0值局部結(jié)構(gòu)變量是每次控制進(jìn)入它所屬轄域時(shí)創(chuàng)建并初始化未指定初值的局部結(jié)構(gòu)變量其初值是不確定的《程序設(shè)計(jì)》157.1.3結(jié)構(gòu)指針變量把結(jié)構(gòu)變量s所占據(jù)的存儲段開始地址賦給能指向該結(jié)構(gòu)的指針變量p，就說指針p指向結(jié)構(gòu)變量s。指針p是一個(gè)結(jié)構(gòu)指針變量，簡稱結(jié)構(gòu)指針定義結(jié)構(gòu)指針的方法，與定義一般指針變量一樣，當(dāng)類型區(qū)分符是結(jié)構(gòu)類型時(shí)，所定義的指針變量即為結(jié)構(gòu)指針如代碼structdate*pd,date3;

定義結(jié)構(gòu)指針pd和結(jié)構(gòu)變量date3其中，指針變量pd能指向類型為structdate的結(jié)構(gòu)賦值pd=&date3，使指針pd指向結(jié)構(gòu)date3《程序設(shè)計(jì)》167.1.4結(jié)構(gòu)變量的引用程序引用結(jié)構(gòu)的方式有兩種直接用結(jié)構(gòu)變量名引用結(jié)構(gòu)變量通過指向結(jié)構(gòu)的指針間接引用結(jié)構(gòu)變量由結(jié)構(gòu)變量名引用其成分:結(jié)構(gòu)變量名.成分名例如，d1.year引用結(jié)構(gòu)變量d1的year成分。因該成分的類型為int型的，可以對它施行任何int型變量可以施行的運(yùn)算。例如賦值運(yùn)算d1.year=2008由指向結(jié)構(gòu)的指針引用結(jié)構(gòu)成分:

指針變量名->成分名《程序設(shè)計(jì)》17引用結(jié)構(gòu)成分的示例以下代碼的意義如它們的注釋所示，產(chǎn)生如圖所示的邏輯關(guān)系pt=&p;/*使pt指向結(jié)構(gòu)p*/p.pos[0]=2.2;/*結(jié)構(gòu)p的pos數(shù)組成分的首元素pos[0]置值2.2*/pt->pos[1]=2.0;/*與代碼“p.pos[1]=2.0”的作用相同*/p.next=&u;/*使結(jié)構(gòu)p的next成分指向結(jié)構(gòu)u*/p.next->pos[0]=1.2;/*與代碼“u.pos[0]=1.2”的作用相同*/u.pos[1]=1.0;u.next=NULL;ptpu2.21.22.01.0NULL引用結(jié)構(gòu)成分的效果示意圖例如：structpNode{floatpos[2];structpNode*next;}p,u,*pt;《程序設(shè)計(jì)》18引用結(jié)構(gòu)成分的示例(續(xù))上述例子說明結(jié)構(gòu)的成分可以像普通變量一樣使用。根據(jù)其類型決定其所有合法的運(yùn)算進(jìn)一步的例子

structstudent{charname[20];intage;floatscore;}stu1,stu2;stu1.age++;/*學(xué)生stu1的年齡增1*/++stu2.age;/*學(xué)生stu2的年齡增1*/sum=stu1.score+stu2.score;《程序設(shè)計(jì)》19引用結(jié)構(gòu)成分(續(xù))在結(jié)構(gòu)類型structpNode中，含有一個(gè)指向自身一樣結(jié)構(gòu)的指針成分，這是引用自身的結(jié)構(gòu)形式利用含有指針成分的結(jié)構(gòu)可以實(shí)現(xiàn)結(jié)構(gòu)的鏈接，用這樣的結(jié)構(gòu)能構(gòu)成如鏈表、樹、圖等復(fù)雜數(shù)據(jù)結(jié)構(gòu)若結(jié)構(gòu)成分本身又是結(jié)構(gòu)類型的，則可繼續(xù)使用成分運(yùn)算符‘.’引用結(jié)構(gòu)成分的結(jié)構(gòu)成分，逐級向下引用到最低一級成分例如，對employee的某些成分的訪問

employee.salary=560.00;employee.hiredate.day=24;employee.hiredate.month=11;employee.hiredate.year=2008;scanf("%f",&employee.salary)《程序設(shè)計(jì)》20引用結(jié)構(gòu)成分(續(xù))ANSIC還允許相同類型的結(jié)構(gòu)變量相互賦值表達(dá)式“*指針變量”表示指針變量所指對象，所以通過指針引用其所指結(jié)構(gòu)的成分也可寫成：

(*指針變量).結(jié)構(gòu)成分名這里園括號是必需的，因運(yùn)算符“*”的優(yōu)先級低于運(yùn)算符“.”*pd.day等價(jià)于*(pd.day)，在這里這樣的寫法是錯(cuò)誤的采用這種表記方法，通過pd引用date3的成分也可寫成(*pd).day、(*pd).month、(*pd).year但是很少場合采用這種表記方法，習(xí)慣都采用運(yùn)算符“->”來表記structdate*pd,date3;【】Howoldareyou?試題來源：ACMICPC::UFRNQualificationContest(FederalUniversityofRioGrandedoNorte,Brazil)，2007在線測試：UVA11219這是填好的表格。非常感謝。讓我檢查一下……嗯……好吧，好吧，等等，你多大了？20。我忘了填了嗎？不，上面寫著你下個(gè)月才出生了！你把年份填錯(cuò)了…哦…對不起！現(xiàn)在，要將上述對話的過程自動(dòng)化，以避免一些人為的錯(cuò)誤。要求根據(jù)當(dāng)前日期和給出的出生日期，計(jì)算年齡。請您編寫程序，計(jì)算年齡，或者指出是否有問題。輸入輸入的第一行給出測試用例數(shù)T（1≤T≤200）。接下來給出T個(gè)測試案例。每個(gè)測試用例先給出一個(gè)空行，然后給出兩行，分別表示當(dāng)前日期和出生日期。日期的格式為DD/MM/YYYY，其中，DD表示日期，MM表示月份，YYYY表示年份。所有日期都是有效日期。輸出對于每個(gè)輸入的測試用例，輸出一行，格式如下（引號僅用于說明）：“Case#N:AGE”，其中N是當(dāng)前測試用例的編號，AGE是以下的選項(xiàng)之一：“Invalidbirthdate”，如果無法計(jì)算年齡（還沒有出生）；“Checkbirthdate”，如果計(jì)算出的年齡超過130歲；計(jì)算得出的年齡（僅限歲）；否則，如果兩個(gè)日期相同，則輸出應(yīng)為“0”。試題解析本題要求：給出當(dāng)前日期和出生日期。日期的格式為DD/MM/YYYY，要求計(jì)算年齡，或者指出是否有問題。對于日期，用結(jié)構(gòu)類型：structDate{intday,month,year;}表示。初始時(shí)，當(dāng)前日期和出生日期是兩個(gè)結(jié)構(gòu)變量a和b；結(jié)構(gòu)變量a存儲計(jì)算結(jié)果。對于每個(gè)測試用例：輸入當(dāng)前日期和出生日期；接下來，判斷如下：如果a.day<b.day，則a.month減一；然后，如果a.month<b.month，則a.year減一；然后，根據(jù)題目描述，比較a.year和b.year：如果不是“Invalidbirthdate”，“Checkbirthdate”，則年齡為a.year-b.year。《程序設(shè)計(jì)》277.2結(jié)構(gòu)數(shù)組用結(jié)構(gòu)描述個(gè)體，用數(shù)組描述個(gè)體的集合當(dāng)數(shù)組的元素是結(jié)構(gòu)時(shí)，這種數(shù)組就稱為結(jié)構(gòu)數(shù)組如用結(jié)構(gòu)類型描述學(xué)生信息，而用結(jié)構(gòu)數(shù)組表示一個(gè)班學(xué)生。用結(jié)構(gòu)數(shù)組表示全班學(xué)生能充分反映班級整體性，程序處理也較方便在變量名之后指定元素個(gè)數(shù)，就能定義結(jié)構(gòu)數(shù)組如structstdTypestudents[30];/*結(jié)構(gòu)數(shù)組students有30個(gè)元素.元素的類型是structstdType*/structpersonemployees[200];/*結(jié)構(gòu)數(shù)組points有200個(gè)元素*/如struct{intx;inty;}points[500];/*一組坐標(biāo)點(diǎn)*/《程序設(shè)計(jì)》28訪問結(jié)構(gòu)數(shù)組元素的成分結(jié)構(gòu)數(shù)組各元素在內(nèi)存中也順序存放，也可初始化，對結(jié)構(gòu)數(shù)組元素的訪問也要利用元素的下標(biāo)訪問結(jié)構(gòu)數(shù)組元素的成分的標(biāo)記方法為：結(jié)構(gòu)數(shù)組名[元素下標(biāo)].結(jié)構(gòu)成分名即首先是指定數(shù)組的元素，再指定結(jié)構(gòu)的成分《程序設(shè)計(jì)》29訪問結(jié)構(gòu)數(shù)組元素的成分(續(xù))結(jié)構(gòu)指針變量也可指向結(jié)構(gòu)數(shù)組的某個(gè)結(jié)構(gòu)元素如有定義

structstdTypestd[50],*ps,*p;賦值運(yùn)算ps=&std[2]使指針ps指向結(jié)構(gòu)std[2]以下代碼序列實(shí)現(xiàn)在結(jié)構(gòu)數(shù)組std中找最高分的那個(gè)結(jié)構(gòu)，并由指針p指向該結(jié)構(gòu)

p=std;

/*等價(jià)于p=&std[0],使p指向結(jié)構(gòu)std[0]*/

for(ps=p+1;ps<=std+sizeofstd/sizeofstd[0];ps++)if(ps->score>p->score)p=ps;指針加n的意義是指針值增加n個(gè)單位，ps++使程序在循環(huán)執(zhí)行過程中，指針ps順序指向結(jié)構(gòu)std[1]、std[2]、…《程序設(shè)計(jì)》30【例7.2.4】結(jié)構(gòu)數(shù)組程序示例-1根據(jù)輸入的年份、月份和日期，輸出相應(yīng)的月份英文名稱和該日是該年份中的第幾天采用常用方法，嚴(yán)格檢查輸入數(shù)據(jù)合理性，發(fā)現(xiàn)不合理時(shí)，輸出警告信息，并要求重新輸入。程序框架如下{提示程序開始工作;for(;;){

輸入年份;for(;;){/*月份輸入不正確，繼續(xù)循環(huán)*/

輸入月份;if(月份合理)break;

輸出警告信息;}

輸出月份英文名稱;《程序設(shè)計(jì)》31結(jié)構(gòu)數(shù)組程序示例-1(續(xù))算法(續(xù))for(;;){/*日期輸入不正確，繼續(xù)循環(huán)*/

輸入日期;if(日期合理)break;

輸出警告信息;}

計(jì)算日期是該年中的第幾天;

輸出結(jié)果;

輸出是否繼續(xù)的提示;

輸入用戶回答;if(!繼續(xù))break;/*結(jié)束程序*/}}《程序設(shè)計(jì)》32結(jié)構(gòu)數(shù)組程序示例-1(續(xù))有關(guān)的數(shù)據(jù)結(jié)構(gòu)主要有日期結(jié)構(gòu)變量：設(shè)日期變量包含有日、月、年、年中的天和月份名稱字符串的首字符指針等成分月份與月份名稱對照表。設(shè)它是一個(gè)結(jié)構(gòu)數(shù)組，數(shù)組的每個(gè)元素是月份和月份英文名稱組成的結(jié)構(gòu)。因該對照表是固定不變的，可在定義它時(shí)初始化月份天數(shù)表。因月份天數(shù)有閏年和平年之分，將該數(shù)組設(shè)計(jì)成一個(gè)二維數(shù)組，其中第1行存儲平年各月份的天數(shù)；第2行存儲閏年各月份的天數(shù)。對它也在定義時(shí)初始化《程序設(shè)計(jì)》33結(jié)構(gòu)數(shù)組程序示例-1(續(xù))最后是設(shè)計(jì)有關(guān)函數(shù)：將有關(guān)功能獨(dú)立的程序段用函數(shù)來實(shí)現(xiàn)例如，確定日期是年中第幾天的計(jì)算可編寫成函數(shù)。為使該函數(shù)邏輯上獨(dú)立于主函數(shù)，函數(shù)設(shè)有日期、月份、年份三個(gè)形參，返回日期是年中第幾天的結(jié)果函數(shù)模型為intdayofYear(int,int,int)《程序設(shè)計(jì)》34結(jié)構(gòu)數(shù)組程序示例程序1-P1#include<stdio.h>intdayTbl[][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};structdate{intday;intmonth;intyear;intyearDay;char*monthName;}date;struct{intmon;char*name;}month[]={{1,"January"},{2,"February"},{3,"March"},{4,"April"},{5,"May"},{6,"June"},{7,"July"},{8,"August"},{9,"September"},{10,"October"},{11,"November"},{12,"December"},{-1,""}};《程序設(shè)計(jì)》35結(jié)構(gòu)數(shù)組程序示例程序1-P2char*monthName(intmon)/*尋找月份名稱*/{intm;for(m=0;month[m].mon>0;m++)if(month[m].mon==mon)returnmonth[m].name;returnNULL;}intdayofYear(intd,intm,inty)/*計(jì)算年中第幾天*/{inti,leap,day=d;leap=(y%4==0&&y%100)||(y%400==0);for(i=0;i<m-1;i++)day+=dayTbl[leap][i];returnday;}《程序設(shè)計(jì)》36結(jié)構(gòu)數(shù)組程序示例程序1-P3voidmain(){intleap,days;charans;printf("\n\t\tDateConversionProgram\n");for(;;){printf("Year=");scanf("%d",&date.year);for(;;){/*輸入月份*/printf("Month=");scanf("%d",&date.month);if(date.month>=1&&date.month<=12)break;printf("\tMonthmustbebetween1to12.\n");}date.monthName=monthName(date.month);printf("Thenameofthe%d(th)monthis%s.\n",date.month,date.monthName);leap=(date.year%4==0&&date.year%100)||date.year%400==0;days=dayTbl[leap][date.month-1];《程序設(shè)計(jì)》37結(jié)構(gòu)數(shù)組程序示例程序1-P4for(;;){/*輸入日*/printf("Day=");scanf("%d",&date.day);if(date.day>=1&&date.day<=days)break;printf("\tDaymustbebetween1to%d.\n",days);}date.yearDay=dayofYear(date.day,date.month,date.year);printf("\tThedaysoftheyearare%d.\n",date.yearDay);printf("\tContinue?(y/n)");doscanf("%c",&ans);while(!((ans>='A'&&ans<='Z')||(ans>='a'&&ans<='z')));if(ans!='y'&&ans!='Y')break;}}《程序設(shè)計(jì)》38【例7.2.5】結(jié)構(gòu)數(shù)組程序示例-2設(shè)程序中有三個(gè)表示坐標(biāo)點(diǎn)的變量，用戶分別用1、2、3來稱呼它們。程序給出以下命令供用戶選擇1.為某坐標(biāo)點(diǎn)輸入坐標(biāo)值2.顯示某點(diǎn)的坐標(biāo)值3.指定兩個(gè)點(diǎn),讓另外一個(gè)點(diǎn)成為它們的中點(diǎn)4.顯示兩點(diǎn)之間的矩離5.指定兩點(diǎn)，判另一點(diǎn)是否在兩點(diǎn)的連線上6.結(jié)束程序遵照編程習(xí)慣，將完成指定功能的代碼、供用戶指定坐標(biāo)點(diǎn)序號的代碼，及顯示菜單并接受用戶選擇的代碼分別編寫成函數(shù)《程序設(shè)計(jì)》39結(jié)構(gòu)數(shù)組程序示例2-P1#include<stdio.h>#include<math.h>structpoint{intx;inty;}p[3];/*結(jié)構(gòu)數(shù)組，存儲三個(gè)坐標(biāo)點(diǎn)*/intmenu()/*菜單函數(shù)*/{intchoice;do{printf("\n\n\n");printf("1.指定點(diǎn)，并為它輸入坐標(biāo)值\n");printf("2.指定點(diǎn)，顯示它的坐標(biāo)值\n");printf("3.指定兩點(diǎn),求出它們的中點(diǎn)坐標(biāo)給另外一個(gè)點(diǎn)\n");printf("4.指定兩點(diǎn)，顯示兩點(diǎn)間的矩離\n");printf("5.指定兩點(diǎn)，判另一點(diǎn)是否在兩點(diǎn)的連線上\n");printf("6.結(jié)束程序\n");《程序設(shè)計(jì)》40結(jié)構(gòu)數(shù)組程序示例2-P2printf("\t輸入你的選擇!\n");scanf("%d",&choice);if(choice>=1&&choice<=6)returnchoice;/*返回選擇*/printf("選擇出錯(cuò)！重新選擇。\n");}while(1);}intpointNo()/*接受用戶指定的點(diǎn)的代號*/{intpno;while(1){printf("指定點(diǎn)的代號:\n");scanf("%d",&pno);if(pno>=1&&pno<=3)returnpno-1;printf("點(diǎn)的代號指定不正確,請重新");}}《程序設(shè)計(jì)》41結(jié)構(gòu)數(shù)組程序示例2-P3voidinputPoint(intpno)/*輸入指定點(diǎn)的坐標(biāo)*/{printf("輸入第%d點(diǎn)的X坐標(biāo)和Y坐標(biāo)\n",pno+1);scanf("%d%d",&p[pno].x,&p[pno].y);}voiddisplayPoint(intpno)/*顯示指定點(diǎn)的坐標(biāo)*/{printf("第%d點(diǎn)的X坐標(biāo)=%d,它的Y坐標(biāo)=%d\n",pno+1,p[pno].x,p[pno].y);}voidmidPoint()/*求指定兩點(diǎn)的連線中點(diǎn)為另一點(diǎn)*/{intpno1,pno2,pno3;pno1=pointNo();pno2=pointNo();pno3=3-pno1-pno2;p[pno3].x=(p[pno1].x+p[pno2].x)/2;p[pno3].y=(p[pno1].y+p[pno2].y)/2;}《程序設(shè)計(jì)》42結(jié)構(gòu)數(shù)組程序示例2-P4voiddistance()/*指定兩點(diǎn)，顯示兩點(diǎn)間的矩離*/{intpno1,pno2;pno1=pointNo();pno2=pointNo();printf("兩點(diǎn)間矩離=%f\n",sqrt((double)(p[pno1].x-p[pno2].x)*(p[pno1].x-p[pno2].x)+(double)(p[pno1].y-p[pno2].y)*(p[pno1].y-p[pno2].y)));}voidisInLine()/*判另一點(diǎn)是否在指定兩點(diǎn)的連線上*/{intpno1,pno2,pno3;doublet;pno1=pointNo();pno2=pointNo();pno3=3-pno1-pno2;t=(double)(p[pno2].y-p[pno1].y)*(double)(p[pno3].x-p[pno1].x)–

(double)(p[pno3].y-p[pno1].y)*(double)(p[pno2].x-p[pno1].x);if(fabs(t)<1.0e-5)printf("Insameline\n");elseprintf("Notinsameline\n");}《程序設(shè)計(jì)》43結(jié)構(gòu)數(shù)組程序示例2-P5voidmain(){intchoice;while(1){choice=menu();switch(choice){case1:inputPoint(pointNo());break;case2:displayPoint(pointNo());break;case3:midPoint();break;case4:distance();break;case5:isInLine();break;case6:return;}}}【例7.2.5】GoogleisFeelingLucky試題來源：Celebrationforthe106thAnniversaryofFudanUniversity(1905-2011)&WarmupforACM/ICPC2011WorldFinals在線測試：UVA12015Google是最著名的互聯(lián)網(wǎng)搜索引擎之一，它托管和開發(fā)了許多基于互聯(lián)網(wǎng)的服務(wù)和產(chǎn)品。在其搜索引擎網(wǎng)站上，一個(gè)有趣的按鈕“I’mfeelinglucky（我感到幸運(yùn)）”非常吸引大家的眼球。該功能可以允許用戶跳過搜索結(jié)果頁面，直接進(jìn)入排名第一的頁面，節(jié)省了用戶很多時(shí)間。問題是，當(dāng)一個(gè)用戶鍵入一些關(guān)鍵詞并按下“我感覺幸運(yùn)”按鈕時(shí)，會出現(xiàn)哪個(gè)網(wǎng)頁？Google做了很多工作，并提出了很好的方法來處理它。本題是解決這一問題的簡化版方案，Google為每個(gè)網(wǎng)頁賦一個(gè)整數(shù)值，表示其相關(guān)數(shù)；Google選擇最相關(guān)的頁面。如果相關(guān)數(shù)的值相同，則選擇相關(guān)數(shù)最高的所有頁面。本題給出10個(gè)網(wǎng)頁及其相關(guān)數(shù)。請您挑選出在按下“我感覺幸運(yùn)”按鈕時(shí)，所有可能的候選網(wǎng)頁，以提供給用戶。輸入輸入包含多個(gè)測試用例。輸入的第一行給出測試用例的數(shù)量T。對于每個(gè)測試用例，有10行描述網(wǎng)頁和相關(guān)數(shù)。每一行給出一個(gè)字符串，字符串沒有空格字符，表示一個(gè)網(wǎng)頁的URL；以及一個(gè)整數(shù)Vi表示該網(wǎng)頁相關(guān)數(shù)。URL的長度在1和100之間（包括1和100），1≤Vi≤100。輸出對于每個(gè)測試用例，輸出若干行可以選擇的網(wǎng)頁URL，URL的順序與輸入的順序相同。有關(guān)輸出格式的更多信息，請看樣例輸出。試題解析本題給出若干測試用例，每個(gè)測試用例10個(gè)網(wǎng)址及其相關(guān)數(shù)，輸出相關(guān)數(shù)最多的網(wǎng)頁網(wǎng)址（可能有多個(gè)）。網(wǎng)址及其相關(guān)數(shù)用結(jié)構(gòu)類型表示，每個(gè)測試用例則用結(jié)構(gòu)數(shù)組表示。每個(gè)測試用例輸入后，按相關(guān)數(shù)從大到小進(jìn)行排序，然后輸出相關(guān)數(shù)最高的網(wǎng)址。在參考程序中，使用在C++STL中algorithm里的sort函數(shù)，對相關(guān)數(shù)遞減排序?！冻绦蛟O(shè)計(jì)》497.3結(jié)構(gòu)形參和結(jié)構(gòu)指針形參結(jié)構(gòu)形參結(jié)構(gòu)指針形參《程序設(shè)計(jì)》50結(jié)構(gòu)形參以函數(shù)dayofYear()為例，若以結(jié)構(gòu)為形參，改寫該函數(shù)有

intdayofYear(structdated){inti,leap,day=d.day;leap=(d.year%4==0&&d.year%100)||d.year%400==0;for(i=0;i<d.month-1;i++)day+=dayTbl[leap][i];returnday;}調(diào)用帶結(jié)構(gòu)形參的函數(shù)，必須提供與形參相同類型的結(jié)構(gòu)變量實(shí)參。所以主函數(shù)中對函數(shù)dayofYear()的調(diào)用應(yīng)改寫成：date.yearDay=dayofYear(date);函數(shù)設(shè)置結(jié)構(gòu)形參，雖能向函數(shù)直接傳遞結(jié)構(gòu)信息，但函數(shù)調(diào)用時(shí)，系統(tǒng)要為結(jié)構(gòu)形參分配存儲單元，并要完成實(shí)參結(jié)構(gòu)向形參結(jié)構(gòu)傳遞值的工作等《程序設(shè)計(jì)》51結(jié)構(gòu)指針形參函數(shù)設(shè)置結(jié)構(gòu)指針形參：再改寫函數(shù)dayofYear()，使其以日期結(jié)構(gòu)指針為形參，并以此說明結(jié)構(gòu)指針形參的用法

voiddayofYear(structdate*dp){inti,leap,day=dp->day;leap=(dp->year%4==0&&dp->year%100)||dp->year%400==0;for(i=0;i<dp->month-1;i++)day+=dayTbl[leap][i];dp->yearDay=day;}改寫后的函數(shù)通過指針形參引用結(jié)構(gòu)成分，并將計(jì)算結(jié)果存放在結(jié)構(gòu)的相應(yīng)成分中，不再返回結(jié)果對該函數(shù)的調(diào)用方式也需相應(yīng)地改寫成dayofYear(&date);調(diào)用函數(shù)dayofYear()時(shí)，必須提供結(jié)構(gòu)變量date的地址【例7.3.3】Electricity在線測試：UVA12148Martin和Isa終于結(jié)婚了。他們搬到一個(gè)在偏遠(yuǎn)地方的新房子里住，這是他們用他們的大部分積蓄買的。在那里，他們過著幸福的新生活。在這個(gè)新地方的生活有些不一樣，電特別昂貴，Martin提議每天記錄新居的用電量。他們有一個(gè)電表，它顯示一個(gè)數(shù)字，是從他們住進(jìn)新居到現(xiàn)在的總共的用電量，以度（千瓦時(shí)）為單位。剛開始時(shí)，每天早上，他們查看電表，并記下用電量。有時(shí)Martin做，有時(shí)Isa做。這樣，他們就能夠通過計(jì)算連續(xù)的兩天的用電量的差，知道上一天用了多少電。但有時(shí)他們會忘記做，所以，時(shí)間一長，他們的記錄也就不完整了。他們有一個(gè)日期和用電量的列表，但并非所有日期都是連續(xù)的。本題要求計(jì)算可以精確地確定單日用電量的天數(shù)，以及在這些天里總共用了多少電。輸入輸入包含若干個(gè)測試用例。每個(gè)測試用例的第一行給出一個(gè)整數(shù)n，表示用電的記錄數(shù)量（2≤n≤103）。接下來的n行每行表示一個(gè)記錄，給出4個(gè)用單空格分隔的整數(shù)d、m、y和c，分別表示記錄的當(dāng)天是哪一天（1≤d≤31）、月份（1≤m≤12）、年份（1900≤y≤2100），以及從他們住進(jìn)新居到這一天的用電量（0≤c≤106）。這n行按日期升序排序，其中有閏年。用電量按升序增加，沒有兩個(gè)不同日期的用電量會是相同的數(shù)字。本題設(shè)定d、m和y代表的是有效的日期。如果年份可以被4整除，而不是被100整除，那么它就是閏年；或者，如果年份可以被400整除，那么它也是閏年。輸入以僅包含一個(gè)零的一行結(jié)束。輸出對于輸入中的每個(gè)測試用例，輸出一行，給出一個(gè)空格分隔的兩個(gè)整數(shù)：可以精確確定單日用電量的天數(shù)，以及在這些天里的用電量的總和。試題解析每個(gè)測試用例有n條記錄，每條記錄是4個(gè)用單空格分隔的整數(shù)d、m、y和c。用一個(gè)結(jié)構(gòu)數(shù)組表示一個(gè)測試用例，每個(gè)結(jié)構(gòu)表示一條記錄，結(jié)構(gòu)包含的成分為4個(gè)整數(shù)變量d,m,y,c，分別表示記錄的當(dāng)天是哪一天d、月份m、年份y，以及從他們住進(jìn)新居到這一天的用電量c。如果第i-1條記錄表示的日期的后一天是第i條記錄表示的日期，那么第i條記錄的用電量和第i-1條記錄的用電量的差是第i-1條記錄表示的日期的單日用電量。也就是說，第i-1條記錄表示的日期是可以精確地確定單日用電量日期。函數(shù)day(structDate*d)用于計(jì)算結(jié)構(gòu)指針形參d所指向的結(jié)構(gòu)的下一天，結(jié)果保存在d所指向的結(jié)構(gòu)中。在主函數(shù)中，輸入n條記錄后，對前n-1條記錄，逐條判斷：如果對當(dāng)前記錄調(diào)用函數(shù)day()后，日期和下一條記錄的日期相同，則當(dāng)前記錄對應(yīng)的那一天可以精確確定單日用電量，所以，對可以精確確定單日用電量的天數(shù)，以及在這些天里的用電量的總和進(jìn)行累加。《程序設(shè)計(jì)》60結(jié)構(gòu)形參vs結(jié)構(gòu)指針形參以結(jié)構(gòu)為形參，函數(shù)dayofYear()必須用return語句返回結(jié)果。函數(shù)的形參是函數(shù)的局部變量，函數(shù)調(diào)用時(shí)，將結(jié)構(gòu)date的各成分值拷貝到形參d的各成分中，以后函數(shù)對d的改變與date無關(guān)以結(jié)構(gòu)指針為形參，函數(shù)調(diào)用時(shí)，雖只傳遞某結(jié)構(gòu)的地址值，但函數(shù)能通過該指針間接引用外面實(shí)在的結(jié)構(gòu)變量。函數(shù)可引用形參所指結(jié)構(gòu)，也可把計(jì)算結(jié)果存儲于形參所指的結(jié)構(gòu)中《程序設(shè)計(jì)》61結(jié)構(gòu)形參和結(jié)構(gòu)指針形參C語言還允許函數(shù)返回結(jié)構(gòu)類型值，如將函數(shù)dayofYear()改為設(shè)置structdate類型的形參，并返回structdate類型的值。對函數(shù)dayofYear()的新的改寫如下structdatedayofYear(structdated){inti,leap;d.yearDay=d.day;leap=(d.year%4==0&&d.year%100)||d.year%400==0;for(i=0;i<d.month-1;i++)d.yearDay+=day_tbl[leap][i];returnd;}《程序設(shè)計(jì)》62結(jié)構(gòu)形參和結(jié)構(gòu)指針形參主函數(shù)調(diào)用函數(shù)dayofYear()把返回的結(jié)構(gòu)值賦給結(jié)構(gòu)變量date，即date=dayofYear(date);調(diào)用有結(jié)構(gòu)類型形參的函數(shù)時(shí)，實(shí)參結(jié)構(gòu)的各成分值要全部拷貝給形參結(jié)構(gòu)的相應(yīng)成分，費(fèi)時(shí)間又費(fèi)空間一般情況下，以傳遞結(jié)構(gòu)指針為好。僅當(dāng)為了程序的安全性，確保函數(shù)不修改實(shí)參結(jié)構(gòu)成分的值等情況下，可使用結(jié)構(gòu)作為形參函數(shù)返回結(jié)構(gòu)值時(shí)，常需要將函數(shù)的返回值賦給結(jié)構(gòu)變量，對于復(fù)雜的結(jié)構(gòu)類型，需要執(zhí)行一長串的傳送指令才能實(shí)現(xiàn)這一要求從程序執(zhí)行效率和實(shí)用性說，以函數(shù)返回結(jié)構(gòu)的指針更簡便《程序設(shè)計(jì)》637.4鏈表及其應(yīng)用程序用變量表示問題中的數(shù)據(jù)對象，變量通過變量定義引入。程序執(zhí)行時(shí)，不能顯式地用語句隨意生成變量和消去變量，并且變量之間的關(guān)系也不能由變量本身的成分來表達(dá)。但在現(xiàn)實(shí)問題中，問題所包含的數(shù)據(jù)對象的個(gè)數(shù)是變化著的，數(shù)據(jù)對象之間的關(guān)系也在不斷地變化著的按數(shù)據(jù)對象可能最多情況來設(shè)定變量，習(xí)慣稱這種實(shí)現(xiàn)方法為靜態(tài)方法按需要用語句顯式地生成和消去數(shù)據(jù)對象，數(shù)據(jù)之間的關(guān)系也能由程序隨時(shí)設(shè)定和改變，稱這種實(shí)現(xiàn)方法為動(dòng)態(tài)方法《程序設(shè)計(jì)》64動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)采用動(dòng)態(tài)方法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)被稱為動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對象是一種結(jié)構(gòu)變量，除有一些數(shù)據(jù)信息成分，還有指針類型成分，并且這些指針成分能指向與自身同樣類型的結(jié)構(gòu)例如下面的結(jié)構(gòu)類型定義：

structintNode{/*整數(shù)鏈表表元類型*/intvalue;/*存放整數(shù)*/structintNode*next;/*存放后繼表元的指針*/};類型structintNode有兩個(gè)成分，int類型的value和指針next。其中指針next能指向的結(jié)構(gòu)的類型正是定義中的structintNode這種結(jié)構(gòu)又稱為自引用結(jié)構(gòu)。利用成分next可把一個(gè)structintNode類型的結(jié)構(gòu)與另一個(gè)同類型的結(jié)構(gòu)鏈在一起，用于描述動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中兩數(shù)據(jù)對象之間的關(guān)系。在這種有成分引用自身結(jié)構(gòu)類型的定義中，要求那些引用自身成分的類型只能是指針類型《程序設(shè)計(jì)》65內(nèi)存動(dòng)態(tài)分配和釋放庫函數(shù)因動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對象可按需要由程序語句動(dòng)態(tài)生成和消去，所以建立和維護(hù)動(dòng)態(tài)數(shù)據(jù)需要內(nèi)存動(dòng)態(tài)分配和釋放Ｃ系統(tǒng)的函數(shù)庫提供了供程序動(dòng)態(tài)申請和釋放存儲單元的庫函數(shù)。其中最經(jīng)常使用的是下面介紹的三個(gè)庫函數(shù)void*malloc(unsignedsize)void*calloc(unsignednelm,unsignedelsize)voidfree(void*ptr)《程序設(shè)計(jì)》66內(nèi)存動(dòng)態(tài)分配和釋放庫函數(shù)void*malloc(unsignedsize)函數(shù)調(diào)用malloc(size)向系統(tǒng)申請內(nèi)存，從系統(tǒng)提供的動(dòng)態(tài)存儲區(qū)域中分配至少size個(gè)字節(jié)的連續(xù)空間，函數(shù)返回該連續(xù)空間的開始地址如果因動(dòng)態(tài)存儲區(qū)域已分配完，而不能滿足這次申請要求，函數(shù)將返回0(NULL)值因函數(shù)malloc()的返回值是無類型指針值，程序可將該返回值強(qiáng)制轉(zhuǎn)換成某種特定的指針類型如有變量定義structintNode*p;p=(structintNode*)malloc(sizeof(structintNode));實(shí)現(xiàn)向系統(tǒng)申請能存儲類型為structintNode的一個(gè)結(jié)構(gòu)，并將該結(jié)構(gòu)的指針存于指針變量p中《程序設(shè)計(jì)》67內(nèi)存動(dòng)態(tài)分配和釋放庫函數(shù)void*calloc(unsignednelm,unsignedelsize)函數(shù)調(diào)用calloc(nelm,elsize)也可用來向系統(tǒng)申請內(nèi)存單元，在動(dòng)態(tài)存儲區(qū)中分配nelm*elsize個(gè)字節(jié)的連續(xù)空間，并將該空間的內(nèi)容清0。函數(shù)返回該連續(xù)空間的開始地址；如果分配不成功，則返回0如以下函數(shù)調(diào)用都返回能存儲100個(gè)整數(shù)的存儲塊，利用函數(shù)返回的存儲塊的首地址，可象數(shù)組一樣訪問這存儲塊中的100個(gè)元素p=(int*)malloc(100*sizeof(int));q=(int*)calloc(100,sizeof(int));《程序設(shè)計(jì)》68內(nèi)存動(dòng)態(tài)分配和釋放庫函數(shù)voidfree(void*ptr)函數(shù)調(diào)用free(ptr)釋放由ptr所指向的存儲塊。要求ptr的值是調(diào)用函數(shù)malloc()或calloc()申請到的連續(xù)存儲空間中的地址以上三個(gè)函數(shù)中，形參size、nelm和elsize為unsigned類型，ptr為某種指針類型函數(shù)malloc()和calloc()返回的是系統(tǒng)分配的連續(xù)存儲空間的首地址，其類型為void*的，程序?qū)⑦@返回值賦給某個(gè)指針變量，然后用該指針變量間接引用存儲空間的相應(yīng)成分《程序設(shè)計(jì)》69用鏈表實(shí)現(xiàn)的線性表（續(xù)）線性表是最簡單又是最常使用的一種數(shù)據(jù)結(jié)構(gòu)線性表是由相同類型的結(jié)點(diǎn)組成的有限序列，線性表中的結(jié)點(diǎn)習(xí)慣稱為元素或表元一個(gè)有n個(gè)表元e0、e1、…、en-1組成的線性表記為(e0、e1、…、en-1)線性表的表元個(gè)數(shù)稱為線性表的長度，長度為0的線性表稱為空表線性表中表元之間的關(guān)系由表元在線性表中的位置所確定，用相鄰表元構(gòu)成的偶(ei,ei+1)（0<=i<=n-2）表示線性表上存在的線性關(guān)系《程序設(shè)計(jì)》70用鏈表實(shí)現(xiàn)的線性表（續(xù)）如果兩個(gè)線性表有相同的表元集合，但它們的表元在線性表中出現(xiàn)的順序不同，則它們是兩個(gè)不相同的線性表線性表的表元可以由多個(gè)成分組成，如線性表有能唯一確定一個(gè)表元的成分或成分組存在，則該成分或成分組稱為該線性表的關(guān)鍵字，簡稱鍵為了一般性地討論線性表，也為了簡便，往往只考慮表元的關(guān)鍵字，而忽略表元的其它成分線性表可以用順序存儲的數(shù)組實(shí)現(xiàn)，也可采用鏈接存儲的鏈表實(shí)現(xiàn)《程序設(shè)計(jì)》71用鏈表實(shí)現(xiàn)的線性表（續(xù)）鏈表概述（下圖表示最簡單的一種鏈表結(jié)構(gòu)）有一個(gè)指針指向鏈表的第一個(gè)表元，習(xí)慣稱其為“頭指針”或“鏈表頭”鏈表中的每個(gè)表元都包含兩部分內(nèi)容，它們是表元的實(shí)際數(shù)據(jù)信息和后繼表元指針圖中，頭指針head指向第一個(gè)表元，第一個(gè)表元又指向第二個(gè)表元，…，直到最后一個(gè)表元，該表元不再指向其他表元，習(xí)慣稱鏈表的最后一個(gè)表元為“表尾”。121620HeadNULLHeadNULL(a)一個(gè)非空鏈表(b)一個(gè)空鏈表《程序設(shè)計(jì)》72用鏈表實(shí)現(xiàn)的線性表（續(xù)）表元的后繼表元位置由表元所包含的指針?biāo)该?，鏈表中各表元在?nèi)存中的存放位置是可以任意的。如要尋找鏈表中某表元，必須由鏈表頭指針?biāo)傅牡谝粋€(gè)表元開始、順序查找前面圖中所示的鏈表結(jié)構(gòu)是單向的，即每個(gè)表元只知道它的后繼表元位置，而不能知道它的前驅(qū)表元在某些應(yīng)用中，要求鏈表的每個(gè)表元都能方便地知道它的前驅(qū)表元和后繼表元，這種鏈表的表元應(yīng)設(shè)有兩個(gè)指針成分，分別指向它的前驅(qū)和后繼表元，這種鏈表稱為雙向鏈表為適應(yīng)不同問題的特定要求，鏈表結(jié)構(gòu)也有多種變形形式《程序設(shè)計(jì)》73鏈表與數(shù)組的主要區(qū)別數(shù)組的元素個(gè)數(shù)是固定的，而組成鏈表的表元個(gè)數(shù)可按需要增減數(shù)組元素的存儲單元在數(shù)組定義時(shí)分配，鏈表表元的存儲單元在程序執(zhí)行時(shí)動(dòng)態(tài)向系統(tǒng)申請數(shù)組元素的順序關(guān)系由元素在數(shù)組中的位置或下標(biāo)確定，鏈表中的表元順序關(guān)系由表元所包含的指針來體現(xiàn)長度不固定的列表，用可能最大長度的數(shù)組來描述，會浪費(fèi)許多內(nèi)存空間；用鏈表實(shí)現(xiàn)可按需要?jiǎng)討B(tài)改變用數(shù)組實(shí)現(xiàn)列表，當(dāng)有表元插入或刪除時(shí)，要移動(dòng)部分表元的存儲位置；用鏈表實(shí)現(xiàn)不需要移動(dòng)表元《程序設(shè)計(jì)》74用鏈表實(shí)現(xiàn)的線性表（續(xù)）前圖中的(a)是一個(gè)有三個(gè)表元的整數(shù)鏈表，該鏈表的表元類型就可用前述的類型structintNode來描述結(jié)構(gòu)類型structintNode中有成分next是指針類型的，它能指向類型structintNode的結(jié)構(gòu)。在結(jié)構(gòu)類型structintNode的定義中，為定義成分next類型，使用了還未完全定義的類型，并且正是自已要定義的類型在有成分引用自身結(jié)構(gòu)類型的定義中，限制此成分的類型只能是指針類型如類型T1中有成分t1引用類型T2，T2類型中有成分t2引用類型T1，其中t1和t2都是指針類型《程序設(shè)計(jì)》75用鏈表實(shí)現(xiàn)的線性表（續(xù)）為了定義類型T1和T2，需要引入不完整的結(jié)構(gòu)類型說明

structT1{intival;structT2*t1;};structT2{charcval;structT1*t2;};其中類型structT1定義中的成分structT2*t1就包含不完整的結(jié)構(gòu)類型structT2《程序設(shè)計(jì)》76用鏈表實(shí)現(xiàn)的線性表（續(xù)）對于不完整的結(jié)構(gòu)類型定義，可以在其轄域之內(nèi)稍后給出它的完整的結(jié)構(gòu)類型定義，如上面示例但是，如果在上述定義的前面某處另外還有一個(gè)結(jié)構(gòu)類型T2的定義，則類型T1中對T2的引用指的是前面的那個(gè)類型T2，而不是其后定義的類型T2在這種情況下，如要在T1中引用其后定義的類型T2，可在T1類型定義之前加一個(gè)空的結(jié)構(gòu)類型說明structT2;該空的類型說明的作用是屏蔽前面關(guān)于T2的定義《程序設(shè)計(jì)》77鏈表的基本操作鏈表的基本操作主要包括建立空鏈表、生成指定值的新表元、插入一個(gè)表元、遍歷、查找和刪除一個(gè)表元等這些操作都有固定的模式，利用它們，并結(jié)合循環(huán)等控制能實(shí)現(xiàn)各種有關(guān)鏈表的復(fù)雜操作下面以整數(shù)單向鏈表為例，說明各種操作的實(shí)現(xiàn)假定鏈表表元類型是前面定義的structintNode類型，并另有以下變量說明

structintNode*head,*p,*q,*u,*v,*w;其中變量head是整數(shù)鏈表頭指針，其余變量是工作指針《程序設(shè)計(jì)》78鏈表的基本操作（續(xù)）建立空鏈表鏈表的建立過程是從空鏈表(沒有鏈表表元)出發(fā)，逐漸插入鏈表新表元的過程要使以變量head為頭指針的鏈表為空鏈表，讓head取NULL值即可語句：head=NULL;就建立以head為鏈表頭指針的空鏈表《程序設(shè)計(jì)》79鏈表的基本操作（續(xù)）生成指定值的新表元要生成值為kx的新表元，先向系統(tǒng)申請一個(gè)表元大小的存儲塊，然后將指定值填入即可。如代碼

p=(structintNode*)malloc(sizeof(structintNode));p->value=kx;上述代碼有對函數(shù)malloc()的調(diào)用，實(shí)參sizeof(structintNode)是一個(gè)表達(dá)式，sizeof運(yùn)算的結(jié)果是運(yùn)算分量所需(或占用)的字節(jié)數(shù)。這里是存儲鏈表表元數(shù)據(jù)所需的字節(jié)數(shù)。函數(shù)調(diào)用malloc()返回分配給新表元的存儲空間的開始地址《程序設(shè)計(jì)》80鏈表的基本操作（續(xù)）生成指定值的新表元(續(xù))申請獲得的存儲空間開始地址需轉(zhuǎn)換成存儲對象類型的指針類型，然后再對該存儲空間以數(shù)據(jù)類型所具有的成分進(jìn)行存儲例如，對函數(shù)malloc()調(diào)用的返回值作強(qiáng)制類型轉(zhuǎn)換(structintNode*)，使函數(shù)調(diào)用返回的(void*)類型值轉(zhuǎn)換成structintNode*類型的值，以便通過轉(zhuǎn)換后的指針值引用成分value或next《程序設(shè)計(jì)》81鏈表的基本操作（續(xù)）向鏈表插入一個(gè)新表元向鏈表插入一個(gè)新表元是建立鏈表的主要操作之一，按新表元要插入位置不同有：在首表元之前插入新表元在某指針?biāo)傅谋碓蟛迦胄卤碓谑妆碓安迦胄卤碓谑妆碓安迦胄卤碓?，插入后將使新表元成為新的首表元。這個(gè)工作包括將原鏈表的首表元接在新表元的后面，和修改鏈表首指針，使鏈表的首指針指向新表元。設(shè)新表元由指針p所指，下面是實(shí)現(xiàn)這個(gè)功能的代碼p->next=head;head=p;《程序設(shè)計(jì)》82鏈表的基本操作（續(xù)）向鏈表插入一個(gè)新表元(續(xù))在某指針?biāo)傅谋碓蟛迦胄卤碓獙τ趩蜗蜴湵?，因?yàn)橐粋€(gè)表元的前驅(qū)表元不是直接可引用的，所以新表元一般要求插在某已知表元之后。設(shè)已知表元由指針w所指，且w的值不是NULL，而待插入的新表元由指針p所指，插入前、后的狀態(tài)變化如圖7-6所示（見教材）插入工作包含兩個(gè)基本動(dòng)作首先，將w所指表元的后繼表元指針復(fù)制給p所指表元的后繼指針域，即原先w所指表元的后繼表元成為p所指表元的后繼表元，這可用代碼p->next=w->next實(shí)現(xiàn)然后，是將p的值復(fù)制給w所指表元的后繼指針域，即讓p所指表元成為w所指表元的后繼表元，這可用代碼w->next=p實(shí)現(xiàn)《程序設(shè)計(jì)》83鏈表的基本操作（續(xù)）向鏈表插入一個(gè)新表元(續(xù))在某指針?biāo)傅谋碓蟛迦胄卤碓?續(xù))以下代碼就能實(shí)現(xiàn)在w所指表元之后插入p所指表元

p->next=w->next;

w->next=p;

《程序設(shè)計(jì)》84鏈表的基本操作（續(xù)）向鏈表插入一個(gè)新表元(續(xù))WP465上圖在w所指表元之后插入p所指表元的插入之前狀態(tài)WP465下圖在w所指表元之后插入p所指表元的插入之后狀態(tài)《程序設(shè)計(jì)》85鏈表的基本操作（續(xù)）遍歷鏈表從鏈表的首表元開始，沿著鏈表表元的鏈接順序逐一考察每個(gè)表元，直至鏈表結(jié)束用工作指針p遍歷整個(gè)鏈表，訪問表元只做輸出表元值的工作。p的初值為鏈表頭指針，在p不等于NULL值時(shí)循環(huán)，輸出p所指表元的值，并準(zhǔn)備考察下一個(gè)表元(即p=p->next)。能實(shí)現(xiàn)遍歷鏈表功能的函數(shù)定義如下voidtravelLink(structintNode*h){structintNode*p=h;while(p!=NULL){printf(”%4d”,p->value);/*輸出表元的值*/p=p->next;/*準(zhǔn)備訪問下一個(gè)表元*/}printf(”\n”);}《程序設(shè)計(jì)》86鏈表的基本操作（續(xù)）在鏈表中查找指定值的表元在鏈表中查找指定值表元可能有不同目的找到后以獲取該表元的詳細(xì)信息，稱為簡單查找為了進(jìn)一步對鏈表的修改，或?qū)⒉榈降谋碓獎(jiǎng)h除，或在查到的表元之前插入一個(gè)新表元等，稱為動(dòng)態(tài)查找另外，查找過程的實(shí)現(xiàn)又可分兩種情況一是無序鏈表上的查找二是有序鏈表上的查找《程序設(shè)計(jì)》87鏈表的基本操作（續(xù)）在鏈表中查找指定值的表元無序鏈表上的簡單查找：從鏈表頭指針?biāo)傅谝粋€(gè)表元出發(fā)，順序查找?；虬l(fā)現(xiàn)有指定值的表元，以指向該表元的指針值為查找結(jié)果；或查找至鏈表末尾，未發(fā)現(xiàn)指定值的表元，查找結(jié)果為NULL，表示鏈表中沒有指定值的表元structintNode*searchSLink(structintNode*h,intkey){structintNode*v=h;while((v!=NULL)&&(v->value!=key))v=v->next;returnv;}形參h是已知鏈表的頭指針，形參key是要找表元的值。函數(shù)使用指向鏈表表元的工作指針變量v，它的初值為鏈表頭指針。在v不等于NULL值，且v所指表元的值不等于指定值情況下，考察下一個(gè)表元(即v=v->next)《程序設(shè)計(jì)》88鏈表的基本操作（續(xù)）在鏈表中查找指定值的表元有序鏈表上的簡單查找如鏈表的表元是按值從小到大順序鏈接的，則在順序考察鏈表表元的查找循環(huán)中，當(dāng)發(fā)現(xiàn)還有表元，并且該表元的值比key小時(shí)，應(yīng)繼續(xù)查找。反之，若不再有表元，或當(dāng)前表元值不比key值小，則應(yīng)結(jié)束查找。查找循環(huán)結(jié)束后，僅當(dāng)還有表元，且表元的值與key值相同情況下，才找到，函數(shù)返回當(dāng)前表元的指針。否則，鏈表中沒有值為key的表元，函數(shù)返回NULL值。

structintNode*searchSOLink(structintNode*h,intkey){structintNode*v=h;while((v!=NULL)&&(v->value<key))v=v->next;returnv!=NULL&&v->value==key?v:NULL;}《程序設(shè)計(jì)》89鏈表的基本操作（續(xù)）無序鏈表上的動(dòng)態(tài)查找動(dòng)態(tài)查找為插入或刪除做好必要的準(zhǔn)備工作。由于是單向鏈表，函數(shù)除要回答查找結(jié)束時(shí)的當(dāng)前表元的指針外，還應(yīng)回答該表元的前驅(qū)表元指針。令函數(shù)的返回值是查找結(jié)束時(shí)的當(dāng)前表元的指針，函數(shù)另設(shè)一個(gè)指針形參，將找到的前驅(qū)表元的指針存于環(huán)境中的某指針變量中，所以該形參的類型是intNode**的。

structintNode*searchDSLink(structintNode*h,intkey，

structintNode**pp){structintNode*v=h,*u=NULL;while((v!=NULL)&&(v->value!=key)){u=v;v=v->next;/*后繼表元成為當(dāng)前表元*/}*pp=u;returnv;}《程序設(shè)計(jì)》90鏈表的基本操作（續(xù)）有序鏈表上的動(dòng)態(tài)查找

設(shè)鏈表的表元按值從小到大順序鏈接，與無序鏈表上的動(dòng)態(tài)查找類似，但查找循環(huán)當(dāng)發(fā)現(xiàn)查找值不比鏈表當(dāng)前表元的值小時(shí)，就應(yīng)提早結(jié)束查找循環(huán)。

structintNode*searchDOLink(structintNode*h,intkey，structintNode**pp){structintNode*v=h,*u=NULL;while((v!=NULL)&&(v->value<key)){u=v;v=v->next;}*pp=u;returnv;}《程序設(shè)計(jì)》91鏈表的基本操作（續(xù)）如在頭指針為head的有序鏈表上找值為5的表元，并要求找到時(shí)，值為5表元的指針存于指針變量p，而前驅(qū)表元的指針存于指針變量q，則函數(shù)的調(diào)用形式為

p=searchDOLink(head,5,&q);函數(shù)返回后，根據(jù)p和q的值，可分出以下多種不同情況：A.若q==NULL且p==NULL，則鏈表是空鏈表；B.若q==NULL，且p!=NULL，則在考察鏈表的首表元時(shí)，就結(jié)束查找，是否找到由表達(dá)式p->value==key為真確定。C．若q!=NULL，且p==NULL，則鏈表中沒有要找的表元，q指向鏈表的末表元；D．若q!=NULL，且p!=NULL，則在考察鏈表的中間表元時(shí)，就結(jié)束查找，是否找到也由表達(dá)式

p->value==key為真確定?！冻绦蛟O(shè)計(jì)》92鏈表的基本操作（續(xù)）從鏈表刪除指定表元的后繼表元在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，除產(chǎn)生新表元和插入到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的操作以外，還有改變動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中表元之間的關(guān)系、刪除原動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的表元等基本操作。設(shè)要?jiǎng)h除鏈表中由指針變量w所指表元的后繼表元。如后圖所示，欲刪去值為5的表元。經(jīng)刪除后，w所指表元的后繼表元變?yōu)橹禐?的表元。完成這樣的刪除操作，可用以下語句實(shí)現(xiàn)：

p=w->next;w->next=p->next;p->next=NULL;《程序設(shè)計(jì)》93456w

46w

p=w->next;w->next=p->next;p->next=NULL

5pNULL從鏈表刪除的表元可有兩種不同的處理；或可調(diào)用函數(shù)free()回收刪除表元所占的存儲單元；或?qū)h除表元插入到其他鏈表等(b)刪除后(a)刪除前《程序設(shè)計(jì)》94鏈表的基本操作（續(xù)）從鏈表刪除指定值的表元為能刪除指定值的表元，首先要查找指定值的表元。若未找到，則不做刪除工作；若找到，則將它從鏈表中刪除。刪除時(shí)還要考慮兩種不同情況，如刪的是首表元，要更改鏈表頭指