結(jié)構(gòu)體與共同體第1頁，課件共45頁，創(chuàng)作于2023年2月學(xué)習(xí)目標(biāo)學(xué)會建立和使用結(jié)構(gòu)體、共同體。能夠為數(shù)據(jù)對象動態(tài)分配和釋放內(nèi)存。能夠建立和操作鏈表。理解鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的應(yīng)用。第2頁，課件共45頁，創(chuàng)作于2023年2月11.1引言數(shù)組是一組同類型的數(shù)據(jù)集合。結(jié)構(gòu)體是一種構(gòu)造數(shù)據(jù)類型用途：把不同類型的數(shù)據(jù)組合成一個整體-------自定義數(shù)據(jù)類型第3頁，課件共45頁，創(chuàng)作于2023年2月11.2結(jié)構(gòu)體類型及其變量的定義和初始化11.2.1結(jié)構(gòu)體類型定義struct[結(jié)構(gòu)體名]{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；

…………….}；成員類型可以是基本型或構(gòu)造型struct是關(guān)鍵字,不能省略合法標(biāo)識符可省:無名結(jié)構(gòu)體第4頁，課件共45頁，創(chuàng)作于2023年2月例

struct

student{intnumber;charname[20];charsex;intage;

};namenumbersexage2字節(jié)2字節(jié)20字節(jié)1字節(jié)……..結(jié)構(gòu)體類型定義描述結(jié)構(gòu)的組織形式,不分配內(nèi)存第5頁，課件共45頁，創(chuàng)作于2023年2月定義結(jié)構(gòu)體類型時要注意以下幾點：1）結(jié)構(gòu)體成員可以是任何基本數(shù)據(jù)類型，也可以是數(shù)組、指針類型。如上例中的name成員為字符數(shù)組類型，sex成員為字符指針成員。2）結(jié)構(gòu)體類型可以嵌套定義，結(jié)構(gòu)體中的成員可以是其它結(jié)構(gòu)體類型。3）定義的結(jié)構(gòu)體類型，在編譯時系統(tǒng)不對類型分配內(nèi)存空間。structDATE{intyear;//年

intmonth;//月

intday;//日};structstudent{longintnumber;//學(xué)號

charname[8];//姓名

intage;//年齡

char*sex;//性別

structDATEbirthday;//出生日期結(jié)構(gòu)體嵌套定義}；第6頁，課件共45頁，創(chuàng)作于2023年2月例structstudent{intnumber;charname[8];charsex;intage;structDATEbirthday;};

structstudentstu1,stu2;11.2.2

結(jié)構(gòu)體變量的定義先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體變量一般形式：struct結(jié)構(gòu)體名{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；…………….}；struct結(jié)構(gòu)體名

變量名表列；例#defineSTUDENTstructstudent

STUDENT{intnumber;charname[8];charsex;intage;structDATEbirthday;};

STUDENTstu1,stu2;第7頁，課件共45頁，創(chuàng)作于2023年2月定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量一般形式：struct結(jié)構(gòu)體名{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；…………….}變量名表列；例structstudent{intnumber;charname[8];charsex;intage;structDATEbirthday;}stu1,stu2;第8頁，課件共45頁，創(chuàng)作于2023年2月直接定義結(jié)構(gòu)體變量一般形式：struct{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；

…………….}變量名表列；例struct{intnumber;charname[8];charsex;intage;structDATEbirthday;}stu1,stu2;用無名結(jié)構(gòu)體直接定義變量只能一次第9頁，課件共45頁，創(chuàng)作于2023年2月11.2.3

結(jié)構(gòu)體變量的引用和初始化1）對結(jié)構(gòu)體變量中成員的引用例如：stu1.numer相當(dāng)于一個長整型的變量

相當(dāng)于一個數(shù)組名如果一個結(jié)構(gòu)體類型中又嵌套一個結(jié)構(gòu)體類型，訪問該類型的變量時應(yīng)采取逐級訪問的方法，直到得到所需訪問的成員為止。例如：stu1.birthday.yearstu1.birthday.month第10頁，課件共45頁，創(chuàng)作于2023年2月2）對整個結(jié)構(gòu)體變量的引用相同類型的結(jié)構(gòu)體變量可以整體賦值例如：structstudentstu1,stu2;stu1=stu2;第11頁，課件共45頁，創(chuàng)作于2023年2月【例11-1】結(jié)構(gòu)體類型變量的引用示例。#include<stdio.h>structDATE{intyear;//年

intmonth;//月

intday;//日};structstudent{longintnumber;//學(xué)號

charname[8];//姓名

intage;//年齡

charsex[2];//性別

structDATEbirthday;//出生日期結(jié)構(gòu)體嵌套定義};第12頁，課件共45頁，創(chuàng)作于2023年2月voidmain(){structstudentst1;//聲明結(jié)構(gòu)體變量scanf("%ld",&st1.number);//輸入學(xué)號scanf("%s",);//輸入姓名scanf("%d",&st1.age);//輸入年齡scanf("%s",st1.sex);//輸入性別scanf("%d%d%d",&st1.birthday.year,&st1.birthday.month,&st1.birthday.day);//出生日期printf("學(xué)號：%ld姓名：%s年齡：%d性別：%s",st1.number,,st1.age,st1.sex);printf("出生日期：%d-%d-%d\n",st1.birthday.year,st1.birthday.month,st1.birthday.day);}第13頁，課件共45頁，創(chuàng)作于2023年2月11.2.3

結(jié)構(gòu)體變量的引用和初始化形式一：struct結(jié)構(gòu)體名{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；…………….}；struct結(jié)構(gòu)體名

結(jié)構(gòu)體變量={初始數(shù)據(jù)}；例structstudent{intnumber;charname[8];charsex;};structstudentstu1={110,“LinPing”,‘F’};第14頁，課件共45頁，創(chuàng)作于2023年2月形式二：struct結(jié)構(gòu)體名{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；…………….}結(jié)構(gòu)體變量={初始數(shù)據(jù)}；例structstudent{intnum;charname[8];charsex;}stu1={110,“LinPing”,‘F’};第15頁，課件共45頁，創(chuàng)作于2023年2月形式三：struct{

類型標(biāo)識符成員名；類型標(biāo)識符成員名；…………….}結(jié)構(gòu)體變量={初始數(shù)據(jù)}；例struct{intnum;charname[8];charsex;}stu1={112,“LinPing”,‘F’};第16頁，課件共45頁，創(chuàng)作于2023年2月11.3

結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組的定義structstudent{intnum;charname[8];charsex;intage;};structstudentstu[2];structstudent{intnum;charname[8];charsex;intage;}stu[2];第17頁，課件共45頁，創(chuàng)作于2023年2月結(jié)構(gòu)體數(shù)組初始化例struct{intnum;charname[20];charsex;intage;}stu[]={{……},{……},{……}};順序初始化:structstudent{intnum;charname[20];charsex;intage;};structstudentstu[]={100,“WangLin”,‘M’,20,101,“LiGang”,‘M’,19,110,“LiuYan”,‘F’,19};例structstudent{intnum;charname[20];charsex;intage;}stu[]={{……},{……},{……}};分行初始化:structstudent{intnum;charname[10];charsex;intage;};structstudentstu[]={{100,“Linping”,‘M’,22},{111,“Linhong”,‘M’,29},{120,“Liqiang”,‘F’,16}};全部初始化時維數(shù)可缺省結(jié)構(gòu)體數(shù)組引用引用方式：結(jié)構(gòu)體數(shù)組名[下標(biāo)].成員名

structstudent{intnum;charname[10];charsex;intage;}str[3];stu[1].age++;strcpy(stu[0].name,”LiSan”);第18頁，課件共45頁，創(chuàng)作于2023年2月11.4結(jié)構(gòu)體指針指向結(jié)構(gòu)體變量的指針定義形式：struct結(jié)構(gòu)體名*結(jié)構(gòu)體指針名;例structstudent*p;使用結(jié)構(gòu)體指針變量引用成員形式(*結(jié)構(gòu)體指針名).成員名結(jié)構(gòu)體指針名->成員名結(jié)構(gòu)體變量名.成員名第19頁，課件共45頁，創(chuàng)作于2023年2月用指向結(jié)構(gòu)體的指針作函數(shù)參數(shù)用結(jié)構(gòu)體變量的成員作參數(shù)----值傳遞用指向結(jié)構(gòu)體變量或數(shù)組的指針作參數(shù)----地址傳遞用結(jié)構(gòu)體變量作參數(shù)----多值傳遞，效率低第20頁，課件共45頁，創(chuàng)作于2023年2月11.5用結(jié)構(gòu)體變量作函數(shù)參數(shù)【例11-5】將例11-2中輸出功能用函數(shù)print實現(xiàn)。#include<stdio.h>structstudent{//定義結(jié)構(gòu)體類型

longintnumber;//學(xué)號

charname[8];//姓名

floatscore[2];//2門課程的成績};voidprint(structstudentstud)//定義輸出函數(shù)print{intj;printf("%ld%7s",stud.number,);for(j=0;j<2;j++)printf("%7.1f",stud.score[j]);printf("\n");}第21頁，課件共45頁，創(chuàng)作于2023年2月voidmain(){structstudentstud[3];//定義結(jié)構(gòu)體數(shù)組

inti,j;//輸入

for(i=0;i<2;i++){scanf("%ld",&stud[i].number);scanf("%s",stud[i].name); for(j=0;j<2;j++)scanf("%f",&stud[i].score[j]);}printf("\n學(xué)號姓名數(shù)學(xué)英語\n");for(i=0;i<3;i++)print(stud[i]);//調(diào)用輸出函數(shù)print}第22頁，課件共45頁，創(chuàng)作于2023年2月例結(jié)構(gòu)體指針變量作為函數(shù)參數(shù)

【例11-6】將例11-4中輸出功能用函數(shù)print實現(xiàn)。#include<stdio.h>structstudent{//定義結(jié)構(gòu)體類型

longintnumber;//學(xué)號

charname[8];//姓名

floatscore[2];//2門課程的成績};voidprint(structstudent*sp)//定義print函數(shù){intj;printf("%ld%7s",sp->number,sp->name);for(j=0;j<2;j++)printf("%7.1f",sp->score[j]);printf("\n");}第23頁，課件共45頁，創(chuàng)作于2023年2月voidmain(){structstudentstud[3]={{230401,“李立”,{80,89}}, {230402,"王平",{79,87}}, {230403,"趙宏",{88,86}}};inti;printf("\n學(xué)號姓名數(shù)學(xué)英語\n");for(i=0;i<3;i++)print(&stud[i]);//調(diào)print函數(shù)}第24頁，課件共45頁，創(chuàng)作于2023年2月11.7

鏈表

x1

1222頭指針1876

x2

1556

x3

1066

x4

0structnode{ intx;structnode*next};利用指針和結(jié)構(gòu)體建立鏈表

122215561066結(jié)點1結(jié)點2結(jié)點3結(jié)點4第25頁，課件共45頁，創(chuàng)作于2023年2月1．malloc函數(shù)malloc函數(shù)的原型為：void*malloc(unsignedintsize)其作用是在內(nèi)存的動態(tài)存儲區(qū)（堆）中分配一個長度為size的連續(xù)空間。2．free函數(shù)由于內(nèi)存空間總是有限的，不可能無限分配下去，而且一個程序應(yīng)該盡量節(jié)約系統(tǒng)資源，因此，用完后應(yīng)及時釋放它，以便其它的變量或者程序能夠使用。這時我們就要用到free函數(shù)。其函數(shù)原型是：voidfree(void*p)作用是釋放由指針p所指向的內(nèi)存空間。第26頁，課件共45頁，創(chuàng)作于2023年2月靜態(tài)鏈表靜態(tài)鏈表的結(jié)點不是動態(tài)開辟的動態(tài)鏈表11.7.2

鏈表的定義和特點1）不需要預(yù)先分配內(nèi)存空間；2）分配的空間可以根據(jù)程序的需要擴大或縮小。第27頁，課件共45頁，創(chuàng)作于2023年2月【例11-10】單鏈表的建立。#include<stdio.h>#include<malloc.h>/*包含動態(tài)內(nèi)存分配函數(shù)的頭文件*/#defineN10/*N為人數(shù)*/typedefstructnode{charname[20];structnode*link;}stud;第28頁，課件共45頁，創(chuàng)作于2023年2月stud*create(intn)/*建立單鏈表的函數(shù)，形參n為人數(shù)*/{stud*p,*h,*s;/**h保存表頭結(jié)點的指針，*p指向當(dāng)前結(jié)點的前一個結(jié)點，*s指向當(dāng)前結(jié)點*/inti;/*計數(shù)器*/if((h=(stud*)malloc(sizeof(stud)))==NULL)/*分配空間并檢測*/{printf("分配內(nèi)存空間失敗!");exit(0);}h->name[0]=’’;/*把表頭結(jié)點的數(shù)據(jù)域置空*/h->link=NULL;/*把表頭結(jié)點的鏈域置空*/p=h;/*p指向表頭結(jié)點*/第29頁，課件共45頁，創(chuàng)作于2023年2月for(i=0;i<n;i++){if((s=(stud*)malloc(sizeof(stud)))==NULL)/*分配空間并檢測*/{printf("分配內(nèi)存空間失敗!");exit(0);}p->link=s;/*把s的地址賦給p所指向的結(jié)點的鏈域，這樣就把p和s所指向的結(jié)點連接起來了*/printf("請輸入第%d個人的姓名",i+1);scanf("%s",s->name);/*在當(dāng)前結(jié)點s的數(shù)據(jù)域中保存姓名*/s->link=NULL;p=s;}return(h);}第30頁，課件共45頁，創(chuàng)作于2023年2月voidmain(){intnumber;/*保存人數(shù)*/stud*head;/*head是保存單鏈表表頭結(jié)點地址的指針*/number=N;head=create(number);/*把新建單鏈表表頭地址賦給head指針*/}以上為建立包含N個人姓名的單鏈表。建好一個單鏈表之后，可進行一些如插入、刪除等操作。下面先介紹查找算法，再來討論插入和刪除操作，第31頁，課件共45頁，創(chuàng)作于2023年2月stud*search(stud*h,char*x)/*查鏈表函數(shù)，其中h是鏈表頭指針，x指針是要查找人的姓名*/{stud*p;/*當(dāng)前指針，指向要與所查找的姓名進行比較的結(jié)點*/char*y;/*保存結(jié)點數(shù)據(jù)域內(nèi)姓名的指針*/p=h->link;while(p!=NULL){y=p->name;if(strcmp(y,x)==0)/*把數(shù)據(jù)域里的姓名與所要查找的姓名比較，若相同則返回0，即條件成立*/return(p);/*返回與所要查找結(jié)點的地址*/elsep=p->link;}if(p==NULL)printf("未能查找到該數(shù)據(jù)!");}第32頁，課件共45頁，創(chuàng)作于2023年2月動態(tài)鏈表的插入操作假設(shè)在一個單鏈表中存在2個連續(xù)結(jié)點p、q（其中p為q的直接前驅(qū)），現(xiàn)在需要在p、q之間插入一個新結(jié)點s，那么我們必須先為s分配空間并賦值，然后使p的指針域存儲s的地址，s的指針域存儲q的地址即可。(p->link=s;s->link=q)，這樣就完成了插入操作。第33頁，課件共45頁，創(chuàng)作于2023年2月voidinsert(stud*p)/*插入函數(shù)，在指針p后插入*/{charstuname[20];stud*s;/*指針s是保存新結(jié)點地址的*/if((s=(stud*)malloc(sizeof(stud)))==NULL){printf("不能分配內(nèi)存空間!");exit(0);}printf("請輸入你要插入的人的姓名:");scanf("%s",stuname);strcpy(s->name,stuname);/*把指針stuname所指向的數(shù)組元素拷貝給新結(jié)點的數(shù)據(jù)域*/s->link=p->link;/*把新結(jié)點的鏈域指向原來p結(jié)點的后繼結(jié)點*/p->link=s;/*p結(jié)點的鏈域指向新結(jié)點*/}第34頁，課件共45頁，創(chuàng)作于2023年2月動態(tài)鏈表的刪除操作假如我們已經(jīng)知道了要刪除的結(jié)點p的位置，那么要刪除p結(jié)點時只要令p結(jié)點的前驅(qū)結(jié)點的指針域由存儲p結(jié)點的地址改為存儲p的后繼結(jié)點的地址，并釋放p結(jié)點即可。第35頁，課件共45頁，創(chuàng)作于2023年2月voiddelete(stud*x,stud*y)/*刪除函數(shù)，其中y為要刪除的結(jié)點的指針，x為要刪除的結(jié)點的前一個結(jié)點的指針*/{stud*s;s=y;x->link=y->link;free(s);}第36頁，課件共45頁，創(chuàng)作于2023年2月11.8

共同體用戶自定義數(shù)據(jù)類型,也叫聯(lián)合體用途：將不同類型的數(shù)據(jù)項組織為一個整體，占有同一段內(nèi)存共用體類型定義定義形式：union共同體名{

成員表；};

例