《C語言程序設(shè)計(jì)教程（第3版）》課件第11章 復(fù)雜數(shù)據(jù)類型

第11章復(fù)雜數(shù)據(jù)類型制作人：sssC數(shù)據(jù)類型指針類型空類型void定義類型typedef構(gòu)造類型枚舉類型enum數(shù)組結(jié)構(gòu)體struct共用體union基本類型字符類型char實(shí)型單精度型float雙精度型double整型短整型short長整型long整型int語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C只能定義單一的數(shù)據(jù)類型，反映事物單一屬性第11章：復(fù)雜數(shù)據(jù)類型學(xué)習(xí)的意義

如定義學(xué)生成績：

floatscore;能定義復(fù)雜的數(shù)據(jù)類型，反映事物多個屬性如定義學(xué)生信息：structSTU{charno[9];//學(xué)號

charname[12];//姓名

charsex;//性別

floatscore;//成績}student;復(fù)雜數(shù)據(jù)類型豐富了C語言對數(shù)據(jù)信息的處理能力。離開了復(fù)雜數(shù)據(jù)類型，很多信息的描述是無法進(jìn)行定義，更無法進(jìn)行處理的。計(jì)算機(jī)中的信息表示更多是由復(fù)雜數(shù)據(jù)類型來定義的，象《數(shù)據(jù)結(jié)構(gòu)》課程中的鏈表、樹、圖等?？梢愿玫乩斫鈹?shù)據(jù)庫中的記錄的含義。為C++語言中類的概念的理解提供了幫助。學(xué)習(xí)目標(biāo)

熟練掌握結(jié)構(gòu)體、共用體和枚舉數(shù)據(jù)類型的定義方法；熟練掌握結(jié)構(gòu)體、共用體和枚舉變量的定義和引用方法；掌握結(jié)構(gòu)數(shù)組的定義及其應(yīng)用；掌握指向結(jié)構(gòu)的指針的概念及其應(yīng)用；了解線性鏈表的創(chuàng)建、插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)和撤銷節(jié)點(diǎn)的算法；掌握利用復(fù)雜數(shù)據(jù)類型作為函數(shù)參數(shù)和返回值的函數(shù)定義方法；語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

復(fù)雜數(shù)據(jù)類型概述結(jié)構(gòu)體結(jié)構(gòu)體類型的定義結(jié)構(gòu)體變量的定義和引用結(jié)構(gòu)體變量的賦值簡化結(jié)構(gòu)體類型名結(jié)構(gòu)體數(shù)組線性鏈表聯(lián)合體聯(lián)合體類型的定義聯(lián)合體變量的定義和引用聯(lián)合體變量的賦值位域枚舉類型變量的定義和引用復(fù)雜數(shù)據(jù)類型應(yīng)用綜合舉例本章小結(jié)學(xué)習(xí)內(nèi)容

11.1結(jié)構(gòu)體

結(jié)構(gòu)體是一種構(gòu)造數(shù)據(jù)類型

用途：把不同類型的數(shù)據(jù)組合成一個整體-------自定義數(shù)據(jù)類型

引入結(jié)構(gòu)體的好處：加強(qiáng)數(shù)據(jù)項(xiàng)之間的聯(lián)系

如學(xué)生的基本信息，包括學(xué)號、姓名、性別、年齡、班級、成績等數(shù)據(jù)項(xiàng)。這些數(shù)據(jù)項(xiàng)描述了一個學(xué)生的幾個不同側(cè)面。nonamesexageclassnograde獨(dú)立的變量表示：

數(shù)據(jù)項(xiàng)之間無關(guān)聯(lián)nonamesexageclassnograde結(jié)構(gòu)體變量表示：

數(shù)據(jù)項(xiàng)為一個整體charno[9];//學(xué)號charname[20];//姓名charsex;//性別unsignedintage;//年齡unsignedintclassno;//班級floatgrade;//成績語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C1、結(jié)構(gòu)體類型的定義struct[結(jié)構(gòu)體類型名]{

數(shù)據(jù)類型名1成員名1；數(shù)據(jù)類型名2成員名2；

……

數(shù)據(jù)類型名n成員名n；}；struct是關(guān)鍵字,不能省略合法標(biāo)識符可省:無名結(jié)構(gòu)體成員類型可以是基本型或構(gòu)造型以分號;結(jié)尾

例1：structStudent_Info{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

unsignedintage;//年齡

unsignedintclassno;//班級

floatgrade;//成績};例2：structDate{intyear;//年

intmonth;//月

intday;//日};語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

在結(jié)構(gòu)體中數(shù)據(jù)類型相同的成員，既可逐個、逐行分別定義，也可合并成一行定義，就象一次定義多個變量一樣。structStudent_Info{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

unsignedintage;//年齡

unsignedintclassno;//班級

floatgrade;//成績};structStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;};structDate{intyear;//年

intmonth;//月

intday;//日};structDate{intyear,month,day;};

注意：結(jié)構(gòu)類型只是用戶自定義的一種數(shù)據(jù)類型，用來定義描述結(jié)構(gòu)的組織形式,不分配內(nèi)存，只有用它來定義某個變量時，才會為該變量分配結(jié)構(gòu)類型所需要大小的內(nèi)存單元。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型CstructStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;};structStudent_Infostudent;例：2、結(jié)構(gòu)體變量的定義和引用struct

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

數(shù)據(jù)類型名1成員名1；

……

數(shù)據(jù)類型名n成員名n；}；struct結(jié)構(gòu)體類型名變量名列表；

結(jié)構(gòu)體變量的定義

間接定義法：先定義結(jié)構(gòu)類型，再定義結(jié)構(gòu)變量

內(nèi)存映像語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C……9字節(jié)20字節(jié)1字節(jié)4字節(jié)4字節(jié)4字節(jié)nonamesexageclassnograde………

注意：結(jié)構(gòu)體變量student所占內(nèi)存空間的大小是否就等于各個成員所占內(nèi)存空間的大小之和與不同的編譯環(huán)境有關(guān)，詳細(xì)討論見11.2.4節(jié)。structstudent;structStudent_Infostudent1,student2;一次定義多個結(jié)構(gòu)體類型變量

定義指向結(jié)構(gòu)體類型的指針變量

structStudent_Info*pstu;

間接定義法中幾種錯誤的結(jié)構(gòu)體變量的定義方法

沒有結(jié)構(gòu)體類型名Student_Infostudent;

缺省struct關(guān)鍵字

structPointp;structPoint{intx,y;};

結(jié)構(gòu)類型Point定義在后

語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C2、結(jié)構(gòu)體變量的定義和引用struct[結(jié)構(gòu)體類型名]{

數(shù)據(jù)類型名1成員名1；

……

數(shù)據(jù)類型名n成員名n；}變量名列表；

結(jié)構(gòu)體變量的定義

直接定義法：定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量

structStudent_Info{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

unsignedintage;//年齡

unsignedintclassno;//班級

floatgrade;//成績}student1,student2;struct{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

unsignedintage;//年齡

unsignedintclassno;//班級

floatgrade;//成績}student1,student2;或無名結(jié)構(gòu)體定義，變量只能一次語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C(4)結(jié)構(gòu)體類型及變量的作用域和生存期與基本類型變量相同。

(3)結(jié)構(gòu)類型中的成員名，可以與程序中的變量同名，它們代表不同的對象，互不干擾。

幾點(diǎn)說明：(1)結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同

類型:不分配內(nèi)存；

變量:分配內(nèi)存

類型:不能賦值、存取、運(yùn)算;

變量:可以(2)結(jié)構(gòu)體可以嵌套。例：

structdate{intmonth;intday;intyear;};structstudent{intnum;charname[20];

structdatebirthday;}stu;numnamebirthdaymonthdayyear例：

structstudent{intnum;charname[20];

structdate

{intmonth;intday;intyear;}

birthday;}stu;numnamebirthdaymonthdayyearstructPoint{intx,y;};structImg{inttag;structImg*pimg;//正確，可以包含自身類型的指針

structImgimg;//錯誤，不能包含自身類型的變量};structStudent_Infostudent;charname[20];語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C結(jié)構(gòu)體變量不能整體引用,只能引用變量成員可以將一個結(jié)構(gòu)體變量賦值給另一個結(jié)構(gòu)體變量結(jié)構(gòu)體嵌套時逐級引用結(jié)構(gòu)體變量名.成員名.子成員名……最低級子成員名

結(jié)構(gòu)體變量的引用

引用規(guī)則引用方式：結(jié)構(gòu)體變量名.成員名//非指針型結(jié)構(gòu)體變量的引用結(jié)構(gòu)體指針->成員名或（*結(jié)構(gòu)體指針）.成員名//指針型結(jié)構(gòu)體變量的引用成員(分量)運(yùn)算符結(jié)合性:從左向右成員(分量)運(yùn)算符結(jié)合性:從左向右語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C例

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;

stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score;stu1.age++;例

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;printf("%d,%s,%c,%d,%f,%s\n",stu1);(

)stu1={101,"WanLin",'M',19,87.5,"DaLian"};(

)例

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;if(stu1==stu2)……..(

)例

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu,*pstu=&stu;strcpy(,"zhangMing");

stu.score=80;

pstu->score+=10;

printf("%s%f",,(*pstu).score);

例

structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;stu2=stu1;(√)例

structstudent{intnum;charname[20];

structdate{intmonth;intday;intyear;}

birthday;}stu1,stu2,*pstu=&stu1;numnamebirthdaymonthdayyearstu1.birthday.month=12;pstu1->birthday.year=2008;注意：在利用指針引用結(jié)構(gòu)體成員時，-和>之間不能有空格。3、結(jié)構(gòu)體變量的賦值

結(jié)構(gòu)體變量初始化賦值先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體變量時賦初值struct

結(jié)構(gòu)體類型名初值表{……}；struct結(jié)構(gòu)體類型名變量名={成員1的值，…，成員n的值}；

注意：賦初值時，{}中間的數(shù)據(jù)順序必須與結(jié)構(gòu)體成員的定義順序一致，否則就會出現(xiàn)混亂。structStudent_Infostu={"20020306","ZhangMing",'M',18,1,90};

nonamesexageclassnograde√structStudent_Infostu={18,"ZhangMing",'M',"20020306",1,90};

×structDate{intyear;//年

intmonth;//月

intday;//日};structStu_Info{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

structDatebirthday;

//生日

unsignedintclassno;//班級

floatgrade;//成績};structStu_Infostu={"20020306","ZhangMing",'M',{1986,12,10},1,90};

語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C3、結(jié)構(gòu)體變量的賦值

結(jié)構(gòu)體變量初始化賦值定義結(jié)構(gòu)體類型的同時，定義結(jié)構(gòu)體變量并賦初值struct[結(jié)構(gòu)體類型名]{初值表

……}變量名={成員1的值，成員2的值，…，成員n的值}；structDate

{intyear,month,day;}birthday={1986,12,10};

struct

{intyear,month,day;}birthday={1986,12,10};

或語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型CstructStudent_Info{charno[9];//學(xué)號

charname[20];//姓名

charsex;//性別

unsignedintage;//年齡

unsignedintclassno;//班級

floatgrade;//成績}student={"20020306","ZhangMing",'M',18,1,90};

strcpy(stu1.no,stu.no);strcpy(,);stu1.sex=stu.sex;stu1.age=stu.age;stu1.classno=stu.classno;stu1.grade=stu.grade;structStudent_Infostu;

strcpy(stu.no,"20020306");strcpy(,"ZhangMing");stu.sex='M';stu.age=18;stu.classno=1;stu.grade=90;structStudent_Infostu1;stu1=stu;3、結(jié)構(gòu)體變量的賦值

結(jié)構(gòu)體變量在程序中賦值

如果在定義結(jié)構(gòu)體變量時并未對其賦初始值，那么在程序中要對它賦值的話，就只能一個一個地對其成員逐一賦值，或者用已賦值的同類型的結(jié)構(gòu)體變量對它賦值

逐一賦值利用已賦值的結(jié)構(gòu)體變量賦值memcpy(&stu1,&stu,sizeof(structStudent_Info));語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C#include<stdio.h>structscore{floatgrade[5];floatavegrade,maxgrade,mingrade;};intmain(){inti;structscorem;printf("inputthegradeoffivecourse:\n");for(i=0;i<5;i++)//輸入5門課的成績

scanf("%f",&m.grade[i]);m.avegrade=0;m.maxgrade=m.grade[0];m.mingrade=m.grade[0];for(i=0;i<5;i++)//求平均分、最高分、最低分

{m.avegrade+=m.grade[i];m.maxgrade=(m.grade[i]>m.maxgrade)?m.grade[i]:m.maxgrade;m.mingrade=(m.grade[i]<m.mingrade)?m.grade[i]:m.mingrade;}m.avegrade/=5;printf("avegrade=%5.1fmaxgrade=%5.1fmingrade=%5.1f\n",m.avegrade,m.maxgrade,m.mingrade);return0;}【例】計(jì)算學(xué)生5門課的平均成績，最高分和最低分。運(yùn)行結(jié)果(設(shè)5門課的成績?yōu)椋?580869068)：avegrade=79.8maxgrade=90.0mingrade=68.0&m.grade[i]的運(yùn)算順序：&m.grade[i]①②③注：

.和[]同優(yōu)先級，具有左結(jié)合性，高于&的優(yōu)先級語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C4、結(jié)構(gòu)體變量內(nèi)存分配問題透析語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

結(jié)構(gòu)體變量定義以后，系統(tǒng)會為其分配一定大小的內(nèi)存空間，但分配內(nèi)存空間的大小與C語言程序所處的編譯環(huán)境有密切的關(guān)系。

基于TC或BC環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配structMyStruct{doublex;chary;intz;}a;

內(nèi)存分配方法：在TC或BC編譯環(huán)境下，結(jié)構(gòu)體變量所占內(nèi)存空間的大小等于它所包含的每個成員所占內(nèi)存空間大小之和。sizeof(a)=sizeof(a.x)+sizeof(a.y)+sizeof(a.z)=8+1+2=11（byte）

或

sizeof(structMyStruct)=sizeof(double)+sizeof(char)+sizeof(int)=8+1+2=11（byte）語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于TC或BC環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配structMyStruct{doublex;chary;intz;}a;012345678910a.x（8byte）a.y（1byte）a.z（2byte）a（11byte）結(jié)構(gòu)體變量a的內(nèi)存分配示意圖：

語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于VC或CB環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配

在VC、CB環(huán)境下，結(jié)構(gòu)體變量分配內(nèi)存的方式與TC或BC是不同的，其所占內(nèi)存空間的大小不一定等于結(jié)構(gòu)體變量所包含的每個成員所占內(nèi)存空間大小之和。

structMyStruct{doublex;chary;intz;}a;問：sizeof(a)=?16VC、CB對變量存儲的一個特殊處理。為了提高CPU的存儲速度，VC、CB對結(jié)構(gòu)體中的成員變量的起始地址做了“對齊”處理。在默認(rèn)情況下，VC、CB規(guī)定各成員變量存放的起始地址相對于結(jié)構(gòu)的起始地址的偏移量必須為該成員變量類型所占用的字節(jié)數(shù)的倍數(shù)。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于VC或CB環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配類型對齊方式（變量存放的起始地址相對于結(jié)構(gòu)的起始地址的偏移量）

char偏移量必須為sizeof(char)即1的倍數(shù)

short偏移量必須為sizeof(short)即2的倍數(shù)

int偏移量必須為sizeof(int)即4的倍數(shù)

long偏移量必須為sizeof(long)即4的倍數(shù)

float偏移量必須為sizeof(float)即4的倍數(shù)

double偏移量必須為sizeof(double)即8的倍數(shù)VC、CB下常用數(shù)據(jù)類型的對齊方式

在VC、CB編譯環(huán)境下，結(jié)構(gòu)體變量內(nèi)存分配方式為：

(1)結(jié)構(gòu)體變量中各成員變量在存放的時候根據(jù)在結(jié)構(gòu)體中出現(xiàn)的順序依次申請空間，同時按照上表的對齊方式調(diào)整位置，空缺的字節(jié)VC、CB會自動填充。

(2)為了確保結(jié)構(gòu)體變量所占內(nèi)存空間的大小為結(jié)構(gòu)體的字節(jié)邊界數(shù)（即該結(jié)構(gòu)體中占用最大空間的類型所占用的字節(jié)數(shù)）的倍數(shù)，所以在為最后一個成員變量申請空間后，還會根據(jù)需要自動填充空缺的字節(jié)。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于VC或CB環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配structMyStruct{doublex;chary;intz;}a;

(3)再接下來為第三個成員z分配空間，這時下一個可以分配的地址對于結(jié)構(gòu)體的起始地址的偏移量為9，不是sizeof(int)=4的倍數(shù)，為了滿足對齊方式對偏移量的約束問題，VC自動填充3個字節(jié)（這三個字節(jié)沒有放什么東西），這時下一個可以分配的地址對于結(jié)構(gòu)的起始地址的偏移量為12，剛好是sizeof(int)=4的倍數(shù)，所以把z存放在偏移量為12的地方，該成員變量占用sizeof(int)=4個字節(jié)；內(nèi)存分配方法：

(1)首先為第一個成員x分配空間，其起始地址跟結(jié)構(gòu)體的起始地址相同（偏移量0，剛好為sizeof(double)的倍數(shù)），該成員變量占用sizeof(double)=8個字節(jié)；

(2)接下來為第二個成員y分配空間，這時下一個可以分配的地址對于結(jié)構(gòu)的起始地址的偏移量為8，是sizeof(char)的倍數(shù)，所以把y存放在偏移量為8的地方滿足對齊方式，該成員變量占用sizeof(char)=1個字節(jié)；這時整個結(jié)構(gòu)的成員變量已經(jīng)都分配了空間，總的占用的空間大小為：8+1+3+4=16，剛好為結(jié)構(gòu)的字節(jié)邊界數(shù)（即結(jié)構(gòu)中占用最大空間的類型所占用的字節(jié)數(shù)sizeof(double)=8）的倍數(shù)，所以沒有空缺的字節(jié)需要填充。整個結(jié)構(gòu)體變量占用內(nèi)存空間的大小為：sizeof(a)=8+1+3+4=16，其中有3個字節(jié)是VC自動填充的，沒有放任何有意義的東西。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于VC或CB環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配structMyStruct{doublex;chary;intz;}a;0123456789101112131415a.x（8byte）a.y（1byte）自動填充（3byte）a.z（4byte）a（16byte）sizeof(double)=8的倍數(shù)sizeof(char)=1的倍數(shù)sizeof(int)=4的倍數(shù)語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

基于VC或CB環(huán)境下的結(jié)構(gòu)體變量內(nèi)存分配結(jié)構(gòu)體變量定義內(nèi)存分配說明struct

MyStruct{chary;偏移量為0，滿足對齊方式，y占用1個字節(jié)；doublex;下一個可用的地址的偏移量為1，不是sizeof(double)=8的倍數(shù)，需要補(bǔ)足7個字節(jié)才能使偏移量變?yōu)?（滿足對齊方式），因此VC自動填充7個字節(jié)，x存放在偏移量為8的地址上，它占用8個字節(jié)

intz;下一個可用的地址的偏移量為16，是sizeof(int)=4的倍數(shù)，滿足int的對齊方式，所以不需要VC自動填充，z存放在偏移量為16的地址上，它占用4個字節(jié)}b;空間總的大小為1+7+8+4=20，不是結(jié)構(gòu)體的字節(jié)邊界數(shù)（即結(jié)構(gòu)體中占用最大空間的類型所占用的字節(jié)數(shù)sizeof(double)=8）的倍數(shù)，所以需要填充4個字節(jié)，以滿足結(jié)構(gòu)體變量b所占內(nèi)存空間的大小為sizeof(double)=8的倍數(shù)。變量b所占內(nèi)存空間總的大小為：sizeof(b)＝1+7+8+4+4=24（字節(jié)）

語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型CstructMyStruct{chary;doublex;intz;}b;

01234567891011121314151617181920212223b.x（8byte）自動填充（7byte）b.y（1byte）b.z（4byte）自動填充（4byte）b（24byte）sizeof(char)=1的倍數(shù)sizeof(double)=8的倍數(shù)sizeof(int)=4的倍數(shù)使總的字節(jié)數(shù)為sizeof(double)=8的倍數(shù)typedefintINTEGER;

//INTEGER是別名typedefchar*STRING

//STRING是別名structteacher_info{charname[20],charsex,unit[30];unsignedintage,workyears;floatsalary;};typedefstructteacher_infoTEACHER;

//TEACHER是別名INTEGERa;//相當(dāng)于inta;STRINGstr;//char*str;TEACHERt;//相當(dāng)于structteacher_infot;5、簡化結(jié)構(gòu)體類型名

利用typedef語句為結(jié)構(gòu)體類型起別名，這樣可使定義結(jié)構(gòu)體類型的變量顯得更為簡潔，同時也增加程序的易讀性。typedef語句的格式為：typedef

類型名類型名的別名；必須是已經(jīng)定義的數(shù)據(jù)類型名或C語言提供的基本類型名

必須是合法的標(biāo)識符，通常用大寫字母來表示必須以分號結(jié)尾

typedefcharARRAY[81];

//ARRAY是別名ARRAYstr;//相當(dāng)于charstr[81];語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C6、結(jié)構(gòu)體數(shù)組

結(jié)構(gòu)體數(shù)組的每一個元素都是具有相同結(jié)構(gòu)體類型的下標(biāo)結(jié)構(gòu)變量。

結(jié)構(gòu)體數(shù)組的定義三種形式：agenonamesexclassnogradeagenonamesexclassnograde…stu[0]stu[9]……形式一：structStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;};structStudent_Infostu[10];形式二：structStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;}stu[10];形式三：struct{charno[9],name[20],sex;unsignedintage,classno;floatgrade;}stu[10];語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

結(jié)構(gòu)體數(shù)組與二維表的對應(yīng)關(guān)系

結(jié)構(gòu)體數(shù)組就相當(dāng)于一張二維表，一個表的框架對應(yīng)的就是某種結(jié)構(gòu)體類型，表中的每一列對應(yīng)該結(jié)構(gòu)體的成員，表中每一行信息對應(yīng)該結(jié)構(gòu)體數(shù)組元素各成員的具體值，表中的行數(shù)對應(yīng)結(jié)構(gòu)體數(shù)組的大小。nonamesexageclassnograde………………………………結(jié)構(gòu)體類型Student_Infostu[0]stu[1]stu[9]……structStudent_Info{charno[9];charname[20];charsex;unsignedintage;unsignedintclassno;floatgrade;}stu[10];語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

結(jié)構(gòu)體數(shù)組的初始化初始化的格式為:struct

結(jié)構(gòu)體類型名{……}；struct結(jié)構(gòu)體類型名結(jié)構(gòu)體數(shù)組[size]={{初值表1}，…，{初值表n}}；struct[結(jié)構(gòu)體類型名]{……}結(jié)構(gòu)體數(shù)組[size]={{初值表1}，{初值表2}，…，{初值表n}}；或structStudent_Infostu[3]={{"20020306","ZhangMing",'M',18,1,90},{"20020307","WangHai",'M',17,1,85},{"20020308","LiHong",'F',18,2,95}};例：分行初始化語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型CstructStudent_Infostu[]={{"20020306","ZhangMing",'M',18,1,90},{"20020307","WangHai",'M',17,1,85},{"20020308","LiHong",'F',18,2,95}};例：分行初始化全部初始化時維數(shù)可省structStudent_Infostu[3]={"20020306","ZhangMing",'M',18,1,90,"20020307","WangHai",'M',17,1,85,"20020308","LiHong",'F',18,2,95};例：順序初始化例：structMan_Info

//Man_Info也可省略{charname[20];

structDate{intyear,intmonth,intday}birthday;}man[]={{"ZhangXiang",{1986,10,29}},{"WangFei",{1987,12,10}}};

結(jié)構(gòu)體數(shù)組的引用引用格式為:結(jié)構(gòu)體數(shù)組名[下標(biāo)].成員名；structStudent_Info{charno[9];charname[20];charsex;unsignedintage;unsignedintclassno;floatgrade;}stu[10];strcpy(stu[0].name,"WangFei");

stu[1].grade++;printf("%s",stu[0].name);語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C【例】統(tǒng)計(jì)侯選人選票。#include<stdio.h>#include<string.h>structperson{charname[20];//候選人姓名

intcount;//得票數(shù)}leader[3]={"Li",0,"Zhang",0,"Wang",0};語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型Cintmain(){inti,j;charleader_name[20];while(1)//統(tǒng)計(jì)候選人得票數(shù)

{scanf("%s",leader_name);//輸入候選人姓名

if(strcmp(leader_name,"0")==0)//輸入為"0"結(jié)束

break;for(j=0;j<3;j++)//比較是否為合法候選人

if(strcmp(leader_name,leader[j].name)==0)//合法

leader[j].count++;//得票數(shù)加1}for(i=0;i<3;i++)//顯示后選人得票數(shù)

printf("%5s:%d\n",leader[i].name,leader[i].count);return0;}11.3線性鏈表1、線性鏈表概述及其結(jié)構(gòu)

線性表：當(dāng)一組數(shù)據(jù)元素形成了“前后”關(guān)系時，我們稱之為線性表。

線性表在內(nèi)存中的兩種形式順序表：以數(shù)組的形式存放，元素在內(nèi)存中是連續(xù)存放的。線性鏈表：數(shù)據(jù)元素在內(nèi)存中不需要連續(xù)存放，而是通過指針將各數(shù)據(jù)單元鏈接起來，就象一條“鏈子”一樣將數(shù)據(jù)單元前后元素鏈接起來。特點(diǎn)：插入或刪除一個數(shù)據(jù)元素時，需要移動其它數(shù)據(jù)元素

特點(diǎn)：插入或刪除一個數(shù)據(jù)元素時，不需要移動其它數(shù)據(jù)元素

節(jié)點(diǎn)實(shí)際數(shù)據(jù)鏈表頭節(jié)點(diǎn)…h(huán)eadtail數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)n^表示NULL數(shù)據(jù)域指針域語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C線性鏈表中的節(jié)點(diǎn)可以用一個結(jié)構(gòu)體類型來定義，其形式為：

struct節(jié)點(diǎn)結(jié)構(gòu)體類型名{

數(shù)據(jù)成員定義；

struct節(jié)點(diǎn)結(jié)構(gòu)體類型名

*指針變量名；};例：structGrade_Info{intscore;structGrade_Info*next;};typedefstructGrade_Info

NODE;

語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C2、線性鏈表的基本操作基本操作有：創(chuàng)建、插入、刪除、輸出和銷毀等。

鏈表的創(chuàng)建操作

含義：從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點(diǎn)，并保持結(jié)點(diǎn)之間的前驅(qū)和后繼關(guān)系?；舅枷耄?/p>

（1）首先創(chuàng)建一個頭節(jié)點(diǎn)，讓頭指針head和尾指針tail都指向該節(jié)點(diǎn)，并設(shè)置該節(jié)點(diǎn)的指針域?yàn)镹ULL（鏈尾標(biāo)志）；

（2）然后為實(shí)際數(shù)據(jù)創(chuàng)建一個節(jié)點(diǎn)，用指針pnew指向它，并將實(shí)際數(shù)據(jù)放在該節(jié)點(diǎn)的數(shù)據(jù)域，其指針域置為NULL；

（3）最后將該節(jié)點(diǎn)插入到tail所指向節(jié)點(diǎn)的后面，同時使tail指向pnew所指向的節(jié)點(diǎn)。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C【例】鏈表創(chuàng)建操作函數(shù)Create_LinkList。head∧tailNODE*Create_LinkList()//創(chuàng)建鏈表{NODE*head,*tail,*pnew;intscor;

head=(NODE*)malloc(sizeof(NODE));

//創(chuàng)建頭節(jié)點(diǎn)

if(head==NULL)//創(chuàng)建失敗,則返回

{printf("noenoughmemory!\n");return(NULL);}head->next=NULL;//頭節(jié)點(diǎn)的指針域置NULLtail=head;//開始時尾指針指向頭節(jié)點(diǎn)語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型Cpnew->score=score;

pnew->next=NULL;

tail->next=pnew;

tail=pnew;}return(head);}【例】鏈表創(chuàng)建操作函數(shù)Create_LinkList。head∧tailinputthescoreofstudents:70↙pnew70∧tail65↙pnew65∧tail78↙pnew78∧tail90↙pnewtail90∧95↙pnewtail95∧-1↙printf("inputthescoreofstudents:\n");while(1)//創(chuàng)建學(xué)生成績線性鏈表

{scanf("%d",&score);//輸入成績

if(score<0)//成績?yōu)樨?fù),循環(huán)退出

break;

//創(chuàng)建一新結(jié)點(diǎn)

pnew=(NODE*)malloc(sizeof(NODE));

if(pnew==NULL)//創(chuàng)建新結(jié)點(diǎn)失敗，則返回

{printf("noenoughmemory!\n");return(NULL);}語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C2、線性鏈表的基本操作

鏈表的插入操作

含義：在第i個結(jié)點(diǎn)Ni與第i+1節(jié)點(diǎn)Ni+1之間插入一個新的結(jié)點(diǎn)N，使線性表的長度增1，且Ni與Ni+1的邏輯關(guān)系發(fā)生如下變化：插入前，Ni是Ni+1的前驅(qū)，Ni+1是Ni的后繼；插入后，新插入的結(jié)點(diǎn)N成為Ni的后繼、Ni+1的前驅(qū)。

基本思想：

（1）通過單鏈表的頭指針head，找到鏈表的第一個結(jié)點(diǎn)；

（2）順著結(jié)點(diǎn)的指針域找到第i個結(jié)點(diǎn)；

（3）將pnew指向的新結(jié)點(diǎn)插入到第i個結(jié)點(diǎn)之后。

插入時首先將新節(jié)點(diǎn)的指針域指向第i個結(jié)點(diǎn)的后繼節(jié)點(diǎn)，然后再將第i個結(jié)點(diǎn)的指針域指向新節(jié)點(diǎn)。注意順序不可顛倒。當(dāng)i=0時，表示頭節(jié)點(diǎn)。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C【例】鏈表插入操作函數(shù)Insert_LinkList

。voidInsert_LinkList(NODE*head,NODE*pnew,inti){NODE*p;intj;p=head;for(j=0;j<i&&p!=NULL;j++)//將p指向要插入的第i個節(jié)點(diǎn)

p=p->next;if(p==NULL)//表明鏈表中第i個節(jié)點(diǎn)不存在

{printf("the%dnodenotfoundt!\n",i);return;}

pnew->next=p->next;

//將插入節(jié)點(diǎn)的指針域指向第i個節(jié)點(diǎn)的后繼節(jié)點(diǎn)

p->next=pnew;

//將第i個節(jié)點(diǎn)的指針域指向插入節(jié)點(diǎn)}

head70657890∧0123465pnew假設(shè)i=2ppp語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C2、線性鏈表的基本操作

鏈表的刪除操作

含義：刪除鏈表中的第i個結(jié)點(diǎn)Ni，使線性表的長度減1。刪除前，節(jié)點(diǎn)Ni-1是Ni的前驅(qū)，Ni+1是Ni的后繼；刪除后，結(jié)點(diǎn)Ni+1成為Ni-1的后繼。

基本思想：

（1）通過單鏈表的頭指針head，首先找到鏈表中指向第i個結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針p和指向第i個節(jié)點(diǎn)的指針q；

（2）然后刪除第i個結(jié)點(diǎn)。

刪除時只需執(zhí)行p->next=q->next即可，當(dāng)然不要忘了釋放節(jié)點(diǎn)i的內(nèi)存單元。注意當(dāng)i=0時，表示頭節(jié)點(diǎn)，是不可刪除的。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C【例】鏈表刪除操作函數(shù)Delete_LinkList

。voidDelete_LinkList(NODE*head,inti){NODE*p,*q;intj;if(i==0)//刪除的是頭指針，則返回return;

p=head;//將p指向要刪除的第i個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

for(j=1;j<i&&p->next!=NULL;j++)p=p->next;

if(p->next==NULL)//表明鏈表中第i個節(jié)點(diǎn)不存在

{printf("the%dnodenotfoundt!\n",i);return;}head70657890∧01234假設(shè)i=2ppq語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C

q=p->next;

//q指向待刪除的節(jié)點(diǎn)ip->next=q->next;

//刪除節(jié)點(diǎn)i

free(q);

//釋放節(jié)點(diǎn)i的內(nèi)存單元}

2、線性鏈表的基本操作

鏈表的輸出操作

含義：將鏈表中節(jié)點(diǎn)的數(shù)據(jù)域的值顯示出來。如果在輸出過程中，對數(shù)據(jù)進(jìn)行相應(yīng)的比較，則可實(shí)現(xiàn)對鏈表的檢索操作。

基本思想：通過單鏈表的頭指針head，使指針p指向?qū)嶋H數(shù)據(jù)鏈表的第一個節(jié)點(diǎn)，輸出其數(shù)據(jù)值，接著p又指向下一個節(jié)點(diǎn)，輸出其數(shù)據(jù)值，如此進(jìn)行下去，直到尾節(jié)點(diǎn)的數(shù)據(jù)項(xiàng)輸出完為止，即p為NULL為止。voidDisplay_LinkList(NODE*head){NODE*p;for(p=head->next;p!=NULL;p=p->next)printf("%d",p->score);printf("\n");}【例】鏈表輸出操作函數(shù)Display_LinkList

。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C2、線性鏈表的基本操作

鏈表的銷毀操作

含義：將創(chuàng)建的鏈表從內(nèi)存中釋放掉，達(dá)到銷毀的目的。

基本思想：每次刪除頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)，最后刪除頭節(jié)點(diǎn)。注意，不要以為只要刪除了頭節(jié)點(diǎn)就可以刪除整個鏈表,要知道鏈表是一個節(jié)點(diǎn)一個節(jié)點(diǎn)建立起來的，所以銷毀它也必須一個一個節(jié)點(diǎn)的刪除才行。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型CvoidFree_LinkList(NODE*head)

{NODE*p,*q;p=head;while(p->next!=NULL){q=p->next;p->next=q->next;free(q);}free(head);}【例】鏈表銷毀操作函數(shù)Free_LinkList

。head70657890∧01234pqqqq∧語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C#include<stdio.h>#include<stdlib.h>structGrade_Info{intscore;structGrade_Info*next;}typedefstructGrade_InfoNODE;NODE*Create_LinkList();voidInsert_LinkList(NODE*head,NODE*pnew,inti);voidDelete_LinkList(NODE*head,inti);voidDisplay_LinkList(NODE*head);voidFree_LinkList(NODE*head);3、線性鏈表應(yīng)用舉例【例1】建立一個學(xué)生成績的線性鏈表，然后對其進(jìn)行插入、刪除、顯示，最后銷毀該鏈表。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型Cintmain(){NODE*head,*pnew;head=Create_LinkList();//創(chuàng)建鏈表

if(head==NULL)//創(chuàng)建失敗

return;printf("aftercreate:");Display_LinkList(head);//輸出鏈表中的值

//新建一插入的節(jié)點(diǎn)

pnew=(NODE*)malloc(sizeof(NODE));if(pnew==NULL)//創(chuàng)建失敗,則返回

{printf("noenoughmemory!\n");return;}pnew->score=88;

//將新節(jié)點(diǎn)插入節(jié)點(diǎn)3的后面

Insert_LinkList(head,pnew,3);printf("afterinsert:");Display_LinkList(head);//輸出鏈表中的值

Delete_LinkList(head,3);//刪除鏈表中節(jié)點(diǎn)3printf("afterdelete:");Display_LinkList(head);//輸出鏈表中的值

Free_LinkList(head);//銷毀鏈表return0;}運(yùn)行結(jié)果(假設(shè)輸入為：706578909585-1)：aftercreate：706578909585afterinsert：70657888909585afterdelete：706588909585【例2】用線性鏈表來存儲從鍵盤輸入的num個整數(shù)，要求降序排列。然后刪除重復(fù)的整數(shù)使其只保留一個。

例如：輸入八個整數(shù)：96897659，則降序排列為：99987665，刪除重復(fù)整數(shù)后：98765。語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C設(shè)計(jì)思想：根據(jù)題目要求，關(guān)鍵問題有兩個：1、建立含有num個數(shù)據(jù)結(jié)點(diǎn)的有序鏈表。可以借鑒插入排序的思想，將每次輸入的整數(shù)插入到鏈表正確的位置，以保持降序排列。這里的關(guān)鍵就是如何找到插入的正確位置，我們知道如果在鏈表中某個結(jié)點(diǎn)Ni的后面插入一個新的結(jié)點(diǎn)，那么就必須找到指向結(jié)點(diǎn)Ni的指針。

其具體方法就是：8^pnewhead96p^pf=head;p=head->next;while(p!=NULL&&p->data>8){pf=p;p=p->next;}pnew->next=p;pf->next=pnew;pfpfp語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C設(shè)計(jì)思想：根據(jù)題目要求，關(guān)鍵問題有兩個：

2、刪除鏈表中重復(fù)結(jié)點(diǎn)。因?yàn)槭怯行蜴湵?，值相同的?shù)據(jù)結(jié)點(diǎn)一定是連續(xù)的，因此可以定義兩個指針p和q，p指向值相同的第一個數(shù)據(jù)結(jié)點(diǎn)，q指向p的后繼節(jié)點(diǎn)，反復(fù)比較q所指結(jié)點(diǎn)的值與p所指結(jié)點(diǎn)值是否相等，如果相等，則刪除q所指的數(shù)據(jù)結(jié)點(diǎn)，然后q指向下一個結(jié)點(diǎn)，繼續(xù)與p所指結(jié)點(diǎn)的值比較，直到q為空或q所指結(jié)點(diǎn)的值不等于ｐ所指結(jié)點(diǎn)的值為止。接下來ｐ指向下一個數(shù)據(jù)結(jié)點(diǎn)，重復(fù)上述操作，直到p為空為止。下圖給出了在有序鏈表中刪除值為9的重復(fù)結(jié)點(diǎn)的過程。p=head->next;while(p!=NULL){q=p->next;

while(q!=NULL&&q->data==p->data){r=q;

q=q->next;

free(r);

}p->next=q;

p=q;

}head9996^pqrqrqp#include<stdio.h>#include<malloc.h>structLNode{intdata;structLNode*next;};typedefstructLNodeNODE;NODE*Create_LinkList_Order();voidDelete_LinkList_Order(NODE*head);voidDisplay_LinkList_Order(NODE*head);voidFree_LinkList_Order(NODE*head);語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型Cintmain(){NODE*head;head=Create_LinkList_Order();//創(chuàng)建有序鏈表

if(head==NULL)//創(chuàng)建失敗，則返回

return-1;printf("Createdorderedlinkedlist:");Display_LinkList_order(head);//輸出鏈表中的值

Delete_LinkList_Order(head);//刪除有序鏈表中重復(fù)結(jié)點(diǎn)

printf("Afterdeletingduplicatenodes:");Display_LinkList_order(head);//輸出鏈表中的值

Free_LinkList_order(head);//銷毀鏈表

return0;}語言程序設(shè)計(jì)教程第三版第十一章復(fù)雜數(shù)據(jù)類型C//創(chuàng)建降序排列的有序鏈表NODE*Create_LinkList_Order(){NODE*head,*pf,*p,*pnew;inti,num,data;//創(chuàng)建頭結(jié)點(diǎn)

head=(NODE*)malloc(sizeof(NODE));if(head==NULL)//創(chuàng)建失敗,則返回

{printf("noenoughmemory!\n");return(NULL);}head->next=NULL;//頭結(jié)點(diǎn)的指針域置NULLprintf("inputthenumberofintegers:");scanf("%d",&num);//輸入整數(shù)個數(shù)

printf("input%dintegers:",num);//將每次輸入的數(shù)據(jù)插入的有序鏈表中

for(i=0;i<num;i++){

//為輸入的整數(shù)創(chuàng)建一個由pnew指向的新數(shù)據(jù)結(jié)點(diǎn)

scanf("%d",&data);//輸入整數(shù)

//創(chuàng)建一新結(jié)點(diǎn)

pnew=(NODE*)malloc(sizeof(NODE));

if(pnew==NULL)//創(chuàng)建新結(jié)點(diǎn)失敗,則返回

{printf("noenoughmemory!\n");return(NULL);}pnew->data=data;pnew->next=NULL;

//找新數(shù)據(jù)結(jié)點(diǎn)要插入的位置（即前驅(qū)結(jié)點(diǎn)的指針pf）

pf=head;//pf為前驅(qū)結(jié)點(diǎn)指針

p=head->next;//p為當(dāng)