第7章 結(jié)構(gòu)體改編

第7章結(jié)構(gòu)體與鏈表7.1結(jié)構(gòu)體的引出7.2結(jié)構(gòu)體變量7.3結(jié)構(gòu)體數(shù)組7.4結(jié)構(gòu)體類型的指針變量7.5結(jié)構(gòu)體與函數(shù)7.6鏈表在實(shí)際問題中我們常需要把不同類型的幾個(gè)數(shù)據(jù)組合起來,構(gòu)成一個(gè)整體,如學(xué)校中教師和學(xué)生的信息。學(xué)號(hào)姓名性別年齡入學(xué)成績(jī)所屬學(xué)院0501李明男19610信息0502張莉女19595信息0503王濤男20580控制職工編號(hào)姓名性別民族出生日期職稱學(xué)歷單位工齡1997025孫杰男漢1974.9講師大學(xué)信息92001016趙玫女回1978.3助教大學(xué)控制51985104鄭毅男漢1964.11教授大學(xué)管理217.1結(jié)構(gòu)體的引出學(xué)號(hào)姓名性別年齡入學(xué)成績(jī)所屬學(xué)院0501李明男19610信息0502張莉女19595信息0503王濤男20580控制如何表示這樣的數(shù)據(jù)信息？結(jié)構(gòu)體是由一些邏輯相關(guān),但數(shù)據(jù)類型不同的分量組成的一組數(shù)據(jù)。學(xué)號(hào)姓名性別年齡入學(xué)成績(jī)所屬學(xué)院intnumcharname[10]charsexintageintscorecharinstitute[20]例：輸入三個(gè)學(xué)生的信息，并輸出#include<stdio.h>voidmain(){structstudent{intnum;charname[10];charsex;

intage;

intscore;charinstitute[20]};

structstudents1,s2,s3;

定義學(xué)生的結(jié)構(gòu)體類型定義3個(gè)結(jié)構(gòu)體類型的變量,用來存放3個(gè)學(xué)生的信息7.1結(jié)構(gòu)體的引出structstudent{intnum;charname[10];charsex;

intage;

intscore;charinstitute[20]};7.2.1結(jié)構(gòu)體的定義注意:定義了結(jié)構(gòu)體類型,僅僅是定義了數(shù)據(jù)的組織形式，創(chuàng)立了一種數(shù)據(jù)類型，但并不會(huì)為這種結(jié)構(gòu)體類型分配內(nèi)存空間只有定義了結(jié)構(gòu)體變量，才會(huì)為變量分配空間注意不要忘了分號(hào)成員表列struct

結(jié)構(gòu)體類型名{數(shù)據(jù)類型成員名1;

數(shù)據(jù)類型成員名2;::

數(shù)據(jù)類型成員名n;}

;關(guān)鍵字用戶定義的標(biāo)識(shí)符7.2結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量的方法(1)先定義結(jié)構(gòu)體類型,再定義變量

structstudent{charname[10];

intage;

ints1,s2;};

structstudentst1,st2;st1st2nameages1s2nameages1s2內(nèi)存中結(jié)構(gòu)體變量占有一片連續(xù)的存儲(chǔ)單元,其占用的字節(jié)數(shù)可用sizeof

運(yùn)算符算出:

printf(“%d\n”,sizeof(structstudent));

printf(“%d\n”,sizeof(st1));結(jié)構(gòu)體變量st1和st2各自都需要22個(gè)字節(jié)的存儲(chǔ)空間結(jié)構(gòu)體類型定義結(jié)構(gòu)體變量定義7.2結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量的方法(2)定義結(jié)構(gòu)體類型同時(shí)定義變量

structstudent{charname[10];

intage;

ints1,s2;}

st1,st2;(3)直接定義結(jié)構(gòu)體變量

struct

{charname[10];

intage;

ints1,s2;}

st1,st2;注意:這里沒有結(jié)構(gòu)體類型名這種方式有時(shí)使用并不方便因此不建議大家采用定義結(jié)構(gòu)體變量7.2結(jié)構(gòu)體變量例:

structdate{intyear;

intmonth;

intday;};

structstud{charname[10];

structdatebirthday;

ints1,s2;};結(jié)構(gòu)體類型可以嵌套定義

或:structstud{charname[10];

structdate{intyear;

intmonth;

intday;}birthday;

ints1,s2;};7.2結(jié)構(gòu)體變量7.2.2結(jié)構(gòu)體變量的引用和初始化格式:

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

成員名structstudent{charname[10];

intage;

ints1,s2;};structstudentst1;st1.

name

=“Mary”;st1.age

=21;st1.

s1

=78;st1.

s2

=86;說明：一般情況下都是對(duì)結(jié)構(gòu)體變量的成員進(jìn)行賦值和輸入\輸出7.2結(jié)構(gòu)體變量structdate{intyear;

intmonth;

intday;};structstud{charname[10];

intage;

structdatebirthday;

ints1,s2;};structstudst2;intage,year;=“John”;st2.age=20;st2.birthday.year=1980;st2.birthday.month=11;st2.birthday.day=23;st2.s1=89;st2.s2=95;age=24;year=2000;可以定義與結(jié)構(gòu)體成員名相同名字的變量,它們之間不會(huì)發(fā)生混亂相同類型的結(jié)構(gòu)體變量可以進(jìn)行整體賦值

structdate{intyear;

intmonth;

intday;};structstud{charname[10];

intage;

structdatebirthday;

ints1,s2;};structstudst1,st2,st3;=“John”;st1.age=20;st1.birthday.year=1980;st1.birthday.month=11;st1.birthday.day=23;st1.s1=89;st1.s2=95;st2=st1;=“Mary”;st3.age=20;st3.birthday=st1.birthday;st3.s1=76;st3.s2=85;注意要正確賦值的條件是變量st1已經(jīng)有了數(shù)據(jù)7.2結(jié)構(gòu)體變量structstudent{charname[10];

intage;

ints1,s2;}

st1={“Mary”,21,78,86};structstud{charname[10];

structdatebirthday;

ints1,s2;};structstudst2={“John”,

1980,11,23

,89,95};structstudent{charname[10];

intage;

ints1,s2;};structstudentst1;

st1={“Mary”,21,78,86};初始化,正確這是賦值,錯(cuò)誤C不允許這么做初始化,正確7.2.2結(jié)構(gòu)體變量的引用和初始化結(jié)構(gòu)體變量的輸入輸出

C語言不允許結(jié)構(gòu)體變量整體進(jìn)行輸入和輸出,

只能對(duì)結(jié)構(gòu)體變量的成員進(jìn)行輸入和輸出gets(

);scanf(“%d%d%d”,

&st1.birthday.year

,

&st1.birthday.month,

&st1.birthday.day);scanf(“%d%d%d”,

&st1.age,

&st1.s1,

&st1.s2);

puts();printf(“%4d”,st1.age);printf(“%d.%d.%d”,st1.birthday.year,st1.birthday.month,st1.birthday.day);printf(“%4d%4d\n”,st1.s1,st1.s2);7.2.2結(jié)構(gòu)體變量的引用和初始化7.3結(jié)構(gòu)體數(shù)組學(xué)號(hào)姓名性別年齡入學(xué)成績(jī)所屬學(xué)院0501李明男19610信息0502張莉女19595信息0503王濤男20580控制7.3.1結(jié)構(gòu)體數(shù)組的定義一個(gè)結(jié)構(gòu)體變量只能存放一個(gè)學(xué)生的信息，對(duì)于多個(gè)學(xué)生的信息，可以使用一個(gè)結(jié)構(gòu)體數(shù)組來存放，結(jié)構(gòu)體數(shù)組的每個(gè)元素是一個(gè)結(jié)構(gòu)體類型的變量定義結(jié)構(gòu)體數(shù)組的方法與定義普通數(shù)組的方法類似:結(jié)構(gòu)體類型數(shù)組名[數(shù)組的長(zhǎng)度];例：輸入30個(gè)學(xué)生的信息，并輸出#include<stdio.h>voidmain(){structstudent{intnum;charname[10];charsex;

intage;

intscore;charinstitute[20]};

structstudents[30];

inti;

for(i=0;i<30;i++){scanf(“%c%d%d%d”,&s[i].sex,&s[i].num,&s[i].age,&s[i].score);gets(s[i].name);gets(s[i].institute);}for(i=0;i<30;i++){printf(“%6d%10s%2c%3d”,s[i].num,s[i].name,s[i].sex,s[i].age);

printf(“%5d%20s\n”,s[i].score,s[i].institue);}}7.3結(jié)構(gòu)體數(shù)組7.3.1結(jié)構(gòu)體數(shù)組的定義1、定義結(jié)構(gòu)體數(shù)組(1)先定義結(jié)構(gòu)體類型再定義結(jié)構(gòu)體數(shù)組

structstudent{charname[10];

intage;

ints1,s2;};structstudentst[6];(2)定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體數(shù)組

structstudent

{charname[10];

intage;

ints1,s2;}

st[6];(3)直接定義結(jié)構(gòu)體數(shù)組

struct

{charname[10];

intage;

ints1,s2;}

st[6];不提倡使用該方法7.3.2結(jié)構(gòu)體數(shù)組的初始化將每個(gè)數(shù)組元素的數(shù)據(jù)用花括號(hào){}括起來structstudent{charname[10];

intage;

ints1,s2;};structstudentst[3]={

{“Mary”,21,78,86},

{“Alex”,20,90,80},

{“Mike”,19,75,68}

};Mary217886Alex209080Mike197568st[0]st[1]st[2]7.3結(jié)構(gòu)體數(shù)組(2)數(shù)組元素之間可以整體賦值也可以將一個(gè)元素賦給一個(gè)相同類型的結(jié)構(gòu)體變量structstudent

st[3]={

{“Mary”,21,78,86},{“Alex”,…}

};structstudent

x;st[2]=st[0];x=st[1];都是結(jié)構(gòu)體變量的整體賦值形式7.3.3結(jié)構(gòu)體數(shù)組的使用(1)引用某個(gè)數(shù)組元素的成員

例:puts(

st[0].name

);

printf(“%d,%d”,

st[1].age,st[1].s1

);(3)輸入和輸出操作只能對(duì)數(shù)組元素的成員進(jìn)行7.3結(jié)構(gòu)體數(shù)組分析:假設(shè)有3個(gè)候選人,共有100個(gè)人投票定義一個(gè)結(jié)構(gòu)體數(shù)組,它有3個(gè)元素代表3個(gè)候選人,每個(gè)元素有2個(gè)成員,一個(gè)是候選人名字,一個(gè)是得票數(shù)(初始時(shí)為0)例：設(shè)計(jì)一個(gè)對(duì)候選人得票進(jìn)行統(tǒng)計(jì)的程序候選人票數(shù)Mike0John0Alex0有100張選票,輸入選票上的名字,然后判斷是誰的名字,就將誰的票數(shù)加1,重復(fù)100次最后輸出結(jié)構(gòu)體數(shù)組#include<stdio.h>#include<string.h>structperson{charname[10];

intcount;};voidmain(){structperson

cand[3]={{“Li”,0},{“Zhang”,0},{“Fun”,0}};

inti,j;charcname[20];for(i=0;i<100;i++){scanf(“%s”,cname);for(j=0;j<3;j++)if(strcmp(cname,cand[j].name)==0)cand[j].count++;

}for(i=0;i<3;i++)

printf(“%10s:%d\n”,cand[i].name,cand[i].count);}定義候選人的結(jié)構(gòu)體類型對(duì)結(jié)構(gòu)體數(shù)組進(jìn)行初始化//輸入選票上的名字//若有100人投票，則循環(huán)100次//將選票上的名字依次和候選人的名字比較//選票上名字和某個(gè)候選人名字相同時(shí),其票數(shù)加1例：按成績(jī)對(duì)學(xué)生信息進(jìn)行從高到底的排序#include<stdio.h>#defineN30structstud{intn;//學(xué)生學(xué)號(hào)charname[10];//學(xué)生姓名

ints;//學(xué)生成績(jī)};voidinput(structstud

a[]){inti;for(i=0;i<N;i++)

scanf(“%d%s%d”,&a[i].n,a[i].name,&a[i].s);

}voidoutput(structstud

a[

]){inti;for(i=0;i<N;i++)

printf(“%4d%10s%4d”,a[i].n,a[i].name,a[i].s);

}

注意a[i].name前不加&,因name是數(shù)組名，因用%s，輸入時(shí)名字不能加空格voidsort(structstud

a[]

){inti,j;

structstud

temp;

for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)

if(a[i].s<a[j].s)

{temp=a[i];a[i]=a[j];a[j]=temp;}}voidmain(){

structstud

st[N];

input(st);sort(st);output(st);}注意進(jìn)行比較的是元素a[i]和a[j]的成績(jī)成員s,但進(jìn)行交換的是元素a[i]和a[j]例:用冒泡排序法對(duì)6個(gè)數(shù)進(jìn)行排序(從小到大)

9

7

2

5

4

1a[0]a[1]a[2]a[3]a[4]a[5]

7

2

5

4

1

92775471

2

5

4

1

7

94515

2

4

1

5

7

9

2

1

4

5

7

91412冒泡排序方法:依次比較相鄰的兩個(gè)數(shù),將小數(shù)放前面,大數(shù)放后面.n個(gè)數(shù)排序需要進(jìn)行n-1輪比較,從第1輪到第n-1輪,各輪的比較次數(shù)依次為:n-1次、n-2次…1次

9

7

2

5

4

19999972541初始狀態(tài)第1輪第2輪第3輪第4輪第5輪74.1一維數(shù)組冒泡排序#include<stdio.h>#defineN6voidmain(){int

a[N],i,j,t;

for(i=0;i<N;i++)

scanf(“%d”,&a[i]);

for(i=0;i<N-1;i++)for(j=0;j<N-1-i;j++)if(a[j]>a[j+1]){t=a[j];

a[j]=a[j+1];a[j+1]=t;

}for(i=0;i<N;i++)

printf(“%3d”,a[i]);}冒泡排序的改進(jìn)方法

#include<stdio.h>voidmain(){inta[6],i,j,t,flag;for(i=0;i<6;i++)

scanf(“%d”,&a[i]);

i=0;

do{flag=0;for(j=0;j<5-i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;flag=1;

}

i++;

}while(flag);for(i=0;i<6;i++)

printf(“%3d”,a[i]);}例:用選擇排序法對(duì)6個(gè)數(shù)進(jìn)行排序(從小到大)

9

7

2

5

4

1a[0]a[1]a[2]a[3]a[4]a[5]選擇排序方法:第1輪比較時(shí),用a[0]依次與a[1]到a[5]進(jìn)行比較,如果a[0]較大則進(jìn)行交換,第1輪結(jié)束后,a[0]中為最小數(shù).以后各輪比較過程與第1論類似.

1

9

7

5

4

2

1

2

9

7

5

479574524

1

2

4

9

7

5

1

2

4

5

9

7795745

9

7

2

5

4

1729712初始狀態(tài)第1輪第2輪第3輪第4輪第5輪7957794.1一維數(shù)組選擇排序#include<stdio.h>#defineN6voidmain(){int

a[N],i,j,t;for(i=0;i<N;i++)

scanf(“%d”,&a[i]);

for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(a[i]>a[j]){t=a[i];

a[i]=a[j];

a[j]=t;

}for(i=0;i<N;i++)

printf(“%3d”,a[i]);}選擇排序改進(jìn)方法#include<stdio.h>voidmain(){inta[6],i,j,k,t;for(i=0;i<6;i++)

scanf(“%d”,&a[i]);for(i=0;i<5;i++){k=i;for(j=i+1;j<6;j++)if(a[k]>a[j])k=j;if(k!=i){t=a[i];a[i]=a[k];

a[k]=t;}//endif}//endforfor(i=0;i<6;i++)

printf(“%3d”,a[i]);}7.4結(jié)構(gòu)體類型的指針變量

7.4.1指向結(jié)構(gòu)體變量的指針

1.定義

structstudent

{charname[20];

intage;

ints1,s2;};

structstudent

stu,*p;

p=&stu;2.成員的引用格式(1)結(jié)構(gòu)體變量名.成員名

gets(

);(*p).age

=21;p->s1

=87;p->s2

=90;(2)(*指針變量名).成員名

(*p).age(3)指針變量名->成員名

p

->s1typedef

structstudent{charname[20];

intage;

ints1,s2;}SD;

SDx,stu,*p;

p=&stu;成員的引用格式(1)結(jié)構(gòu)體變量名.成員名例：scanf(“%s”,);scanf(“%d”,&x.age);x.s1=89;x.s2=78;gets();(*p).age=21;scanf(“%d”,&p->s1);p->s2=90;(2)(*指針變量名).成員名(*p).age(3)指針變量名->成員名p->s17.4結(jié)構(gòu)體與指針說明：和成員運(yùn)算符一樣,“->”為指向運(yùn)算符，是運(yùn)算優(yōu)先級(jí)最高的運(yùn)算符。由于成員運(yùn)算符“.”的運(yùn)算優(yōu)先級(jí)高于運(yùn)算符“*”,

因此(*p).成員名中()不能少。*p.成員名p=&stu.score;

不能用指向某個(gè)結(jié)構(gòu)體變量的指針指向該結(jié)構(gòu)體變量的某個(gè)成員。7.4.2指向結(jié)構(gòu)體數(shù)組的指針1.定義structstudent

a[3],*p

;2.使用for(

p=a;p<a+3;p++

){gets(

p->name);

scanf(“%d%d%d”,&p->age,&p->s1,&p->s2);}

7.4結(jié)構(gòu)體與指針例如：

struct

struct_name{charname[10];

intnum;floatscore;};/*定義結(jié)構(gòu)體類型標(biāo)識(shí)符*/

struct

struct_namestd[30],*p;900390趙明879002王建899001李紅結(jié)構(gòu)體數(shù)組stdstd[0]std[1]std[2]p賦值語句p=std;/*p指向一個(gè)結(jié)構(gòu)體數(shù)組std*//*指針變量p存放的是數(shù)組std的首地址*/引用：p->name;p->num;p->score;趙明909003879002王建899001李紅結(jié)構(gòu)體數(shù)組stdstd[0]std[1]std[2]思考：賦值語句

p=std+1;和p++;分別代表指針p指向哪里？p->name;p->num;p->score;代表的信息發(fā)生了什么變化？pp注意：以下賦值語句都是錯(cuò)誤的:p=&std[1].score;(不能指向數(shù)組元素的成員變量)p=&std;(數(shù)組名本身就代表該數(shù)組的首地址,因此不能使用地址運(yùn)算符&)7.5.1結(jié)構(gòu)體變量作為函數(shù)參數(shù)1.函數(shù)實(shí)參和形參都用結(jié)構(gòu)體變量,參數(shù)之間為值傳遞，實(shí)參結(jié)構(gòu)體變量各成員的值依次傳給形參結(jié)構(gòu)體變量2.返回結(jié)構(gòu)體類型值的函數(shù)定義格式:結(jié)構(gòu)體類型名函數(shù)名(形參表){函數(shù)體;}

例:structstudentfunct(intx,floaty){函數(shù)體;}注意：結(jié)構(gòu)體類型是已經(jīng)定義好的7.5結(jié)構(gòu)體與函數(shù)#include<stdio.h>#defineN5structstud{charname[10];

ints[3];

intsum,ave;};structstud

count(structstudx){intj;

x.sum=0;for(j=0;j<3;j++)

x.sum=x.sum+x.s[j];

x.ave=x.sum/3;

return(x);}例:求學(xué)生成績(jī)的總分和平均分(結(jié)構(gòu)體變量作參數(shù))//定義學(xué)生的結(jié)構(gòu)體類型//計(jì)算學(xué)生三門課的總分//返回學(xué)生的全部信息//結(jié)構(gòu)體變量作參數(shù)返回結(jié)構(gòu)體類型的值voidmain(){structstuda[N];

intj;for(j=0;j<N;j++)

scanf(“%s%d%d%d”,a[j].name,&a[j].s[0],

&a[j].s[1],&a[j].s[2]);

for(j=0;j<N;j++)

a[j]=count(a[j]);

for(j=0;j<N;j++)printf(“%10s%4d%4d%4d%6d%4d\n”,a[j].name,a[j].s[0],a[j].s[1],a[j].s[2],a[j].sum,a[j].ave);}//函數(shù)調(diào)用,將a[j]的值傳給count函數(shù)的參數(shù)x,并將返回值賦給a[j]//輸入N個(gè)學(xué)生的信息//定義結(jié)構(gòu)體數(shù)組a,存放N個(gè)學(xué)生的信息void

count(structstud*p){intj;p->sum=0;for(j=0;j<3;j++)p->sum=p->sum+p->s[j];p->ave=p->sum/3;}例:求學(xué)生成績(jī)的總分和平均分(指向結(jié)構(gòu)體的指針作參數(shù))#include<stdio.h>#defineN5structstud{charname[10];

ints[3];

intsum,ave;};//指向結(jié)構(gòu)體的指針作參數(shù)返回結(jié)構(gòu)體類型的值voidmain(){structstuda[N];

intj;for(j=0;j<N;j++)

scanf(“%s%d%d%d”,a[j].name,&a[j].s[0],

&a[j].s[1],&a[j].s[2]);

for(j=0;j<N;j++)

count(&a[j]);

for(j=0;j<N;j++)printf(“%10s%4d%4d%4d%6d%4d\n”,a[j].name,a[j].s[0],a[j].s[1],a[j].s[2],a[j].sum,a[j].ave);}voidmain(){structstuda[N],*q;

intj;

q=a;for(j=0;j<N;j++)

scanf(“%s%d%d%d”,q->name,&a[j].s[0],

&a[j].s[1],&a[j].s[2]);

for(j=0;q<a+N;q++)

count(q);

for(j=0;j<N;j++)printf(“%10s%4d%4d%4d%6d%4d\n”,a[j].name,a[j].s[0],a[j].s[1],a[j].s[2],a[j].sum,a[j].ave);}7.6鏈表鏈表:是可以動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種數(shù)據(jù)結(jié)構(gòu)它是由一組動(dòng)態(tài)數(shù)據(jù)鏈接而成的序列結(jié)點(diǎn):鏈表中的每一個(gè)動(dòng)態(tài)數(shù)據(jù)稱為一個(gè)結(jié)點(diǎn)表頭結(jié)點(diǎn)表尾結(jié)點(diǎn)NULL為空地址

表示鏈表到此結(jié)束2010142815709514281861570282NULL3中間結(jié)點(diǎn)一.、基本概念1.動(dòng)態(tài)存儲(chǔ)分配:根據(jù)需要臨時(shí)分配內(nèi)存單元用以存放數(shù)據(jù),

當(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)數(shù)據(jù)鏈接而成的序列3.結(jié)點(diǎn):鏈表中的每一個(gè)動(dòng)態(tài)數(shù)據(jù)稱為一個(gè)結(jié)點(diǎn)4.結(jié)點(diǎn)類型:是一個(gè)包含指針項(xiàng)的結(jié)構(gòu)體類型一般由兩部分組成:(1)數(shù)據(jù)成員:存放數(shù)據(jù)(2)指針成員:存放下一個(gè)結(jié)點(diǎn)的地址struct

sd{intnum;

intscore;

struct

sd*next;};

數(shù)據(jù)成員指針成員鏈表的基本概念2010142815709514281861570282NULL3鏈表的基本概念2010head2010142815709514281861570282NULL3鏈表的每個(gè)結(jié)點(diǎn)存放在內(nèi)存中的不同位置，只有找到第1個(gè)結(jié)點(diǎn),才能通過第1個(gè)結(jié)點(diǎn)的指針成員找到第2個(gè)結(jié)點(diǎn)…因此我們將第1個(gè)結(jié)點(diǎn)的地址存放在頭指針中頭指針鏈表的長(zhǎng)度是不固定的，可以隨時(shí)添加結(jié)點(diǎn)，如果將一個(gè)結(jié)點(diǎn)添加到鏈表的尾部，則新結(jié)點(diǎn)成為表尾結(jié)點(diǎn)，它的指針成員必須賦為NULL，而原來的表尾結(jié)點(diǎn)則成為中間結(jié)點(diǎn)75NULL436923692靜態(tài)簡(jiǎn)單鏈表#include<stdio.h>typedef

structstud{intnum,score;

structstud*next;}SD;head2010142815702010abc19514282861570382NULLp201014281570NULLvoidmain(){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%4d\n”,p->num,p->score);

p=p->next;}}靜態(tài)簡(jiǎn)單鏈表#include<stdio.h>typedef

structstud{intnum,score;

structstud*next;}SD;voidmain(){SDa,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;

while(head!=NULL){printf("%3d%4d\n",head->num,head->score);head=head->next;}}//也可以實(shí)現(xiàn)上一頁(yè)的功能動(dòng)態(tài)鏈表的建立建立鏈表的方法表尾添加法：新結(jié)點(diǎn)作為表尾結(jié)點(diǎn)表首添加法：新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)95NULL1201086NULL21428201082NULL3157095NULL1201086NULL2142882NULL31570head201014281570head20101428處理動(dòng)態(tài)鏈表所需的函數(shù)(需用頭文件<stdlib.h>)1.malloc

函數(shù)原型:void*malloc(unsignedintsize)

作用:在內(nèi)存中開辟一個(gè)長(zhǎng)度為size的連續(xù)存儲(chǔ)空間,

并將此存儲(chǔ)空間的起始地址帶回注意:(1)函數(shù)返回值是指針,但該指針是指向void類型的,因此在使用時(shí)希望這個(gè)指針指向其他類型需要用強(qiáng)制類型轉(zhuǎn)換(2)如果內(nèi)存缺少足夠大的空間進(jìn)行分配,則malloc

函數(shù)返回值為“空指針”(即NULL)例:struct

sd*p;p=

(struct

sd*)

malloc(

sizeof(struct

sd)

);強(qiáng)制類型轉(zhuǎn)換結(jié)構(gòu)體類型占用的字節(jié)長(zhǎng)度2.free函數(shù)原型:voidfree(void*ptr)

作用:將指針變量ptr指向的存儲(chǔ)空間釋放注意:ptr的值不是任意的地址,必須是程序中執(zhí)行malloc

函數(shù)所返回的地址(2)模型中ptr是void型,但調(diào)用free函數(shù)時(shí),參數(shù)可能是其他類型,計(jì)算機(jī)系統(tǒng)會(huì)自動(dòng)進(jìn)行轉(zhuǎn)換

例:struct

sd*p;p=(struct

sd*)malloc(sizeof(struct

sd));free(p);p42004200動(dòng)態(tài)鏈表的建立表尾添加法建立鏈表#include<stdio.h>#include<stdlib.h>typedef

structstudent{intnum;

intscore;

structstudent*next;}ST;#defineLENsizeof(ST)intn;定義ST,以后書寫簡(jiǎn)單求出結(jié)構(gòu)體類型占用的字節(jié)數(shù)全局量n表示結(jié)點(diǎn)的個(gè)數(shù)ST*creat(void){ST*p1,*p2,*head=NULL;n=0;

p1=(ST*)malloc(LEN);if(p1==NULL){printf("\nNoenoughmemory!\n");exit(0);}

scanf("%d%d",&p1->num,&p1->score);while(p1->num!=0){n=n+1;if(n==1)head=p1;elsep2->next=p1;p2=p1;

p1=(ST*)malloc(LEN);if(p1==NULL){printf("\nNoenoughmemory!\n");exit(0);}

scanf("%d%d",&p1->num,&p1->score);}p2->next=NULL;

free(p1);return(head);}//產(chǎn)生一個(gè)新結(jié)點(diǎn)//輸入新結(jié)點(diǎn)的數(shù)據(jù)成員//結(jié)點(diǎn)個(gè)數(shù)加1//讓指針p2指向p1所指向的結(jié)點(diǎn)//表尾結(jié)點(diǎn)的指針成員賦為空//釋放p1所指向的結(jié)點(diǎn)空間//p1指向新產(chǎn)生的結(jié)點(diǎn)//若n等于1，則p1當(dāng)前所指向的是表頭結(jié)點(diǎn)由于head頭指針不變，所以讓下一個(gè)結(jié)點(diǎn)p2記錄表頭結(jié)點(diǎn)的地址，讓表頭結(jié)點(diǎn)去產(chǎn)生一個(gè)新結(jié)點(diǎn)，這樣再讓p2->next指向新結(jié)點(diǎn)，即可產(chǎn)生鏈接表尾添加法建立鏈表的過程演示ST*creat(void){ST*p1,*p2,

*head;head=NULL;n=0;p1=(ST*)malloc(LEN);

scanf("%d%d",&p1->num,&p1->score);while(p1->num!=0){n=n+1;if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(ST*)malloc(LEN);

scanf("%d%d",&p1->num,&p1->score);}p2->next=NULL;free(p1);return(head);}head201014281570NULLp1p23264201020101951428n201014282863820014281570NULL1570157032640123動(dòng)態(tài)鏈表的遍歷(輸出)輸出鏈表voidlist(ST*head){ST*p;

p=head;while(p!=NULL){printf(“%d,%d\n”,p->num,p->score);

p=p->next;

}}head201014281570201019514282861570382NULLp201014281570NULL輸出：1,952,863,82voidmain(){ST*h=NULL;

h=creat();list(h);}951428120108615702142882NULL315702010head鏈表的刪除結(jié)點(diǎn)操作刪除表頭結(jié)點(diǎn)讓頭指針指向鏈表的第2個(gè)結(jié)點(diǎn)1428step1：讓指針變量p指向要?jiǎng)h除的結(jié)點(diǎn)即表頭結(jié)點(diǎn)step2：重新給頭指針賦值，使它指向第2個(gè)結(jié)點(diǎn)head=p->next;step3：釋放刪除的結(jié)點(diǎn)空間free(p);p=head;2010p應(yīng)為要釋放刪除的結(jié)點(diǎn)，所以必須在知道此結(jié)點(diǎn)的地址的情況下，才能進(jìn)行空間釋放，所以讓p記錄此結(jié)點(diǎn)的地址。951428120108615702142882NULL315702010head鏈表的刪除結(jié)點(diǎn)操作刪除表尾結(jié)點(diǎn)將鏈表的倒數(shù)第2個(gè)結(jié)點(diǎn)的指針成員賦為NULLstep1：讓指針變量p指向要?jiǎng)h除的結(jié)點(diǎn)即表尾結(jié)點(diǎn)

讓指針變量q指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)1570p1428qstep2：將刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針成員賦空值step3：釋放刪除的結(jié)點(diǎn)空間free(p);q->next=NULL;NULL951428120108615702142882NULL315702010head鏈表的刪除結(jié)點(diǎn)操作刪除中間結(jié)點(diǎn)step1：讓p指向要?jiǎng)h除的結(jié)點(diǎn),

讓q指向要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)1428p2010qstep2：前驅(qū)結(jié)點(diǎn)的指針成員賦為要?jiǎng)h除結(jié)點(diǎn)的指針成員值step3：釋放刪除的結(jié)點(diǎn)空間free(p);q->next=p->next;讓要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后繼結(jié)點(diǎn)1570ST*del(ST*head,intnum){ST*p,*q=NULL;p=head;

while((num!=p->num)&&(p->next!=NULL)){q=p;p=p->next;}if(num==p->num){if(p==head)head=p->next;elseq->next=p->next;

free(p);

n=n-1;

printf(“deleted!\n”);}elseprintf(“cannotdelete!\n”);

return(head);}typedef

structstudent{intnum;

intscore;

structstudent*next;}ST;鏈表的刪除結(jié)點(diǎn)操作刪除結(jié)點(diǎn)函數(shù)令p指向要?jiǎng)h除的結(jié)點(diǎn)，q指向其前驅(qū)結(jié)點(diǎn)（方法）//刪除結(jié)點(diǎn)為表頭結(jié)點(diǎn)//刪除結(jié)點(diǎn)為表尾結(jié)點(diǎn)或中間結(jié)點(diǎn)//釋放已刪除的結(jié)點(diǎn)空間//鏈表的結(jié)點(diǎn)個(gè)數(shù)減1//返回鏈表的頭指針要求：刪除與num相等的結(jié)點(diǎn)ST*p,*q=NULL;

p=head;while((num!=p->num)&&(p->next!=NULL)){q=p;p=p->next;}951428120108615702142882NULL315702010head2010pNULLq設(shè)num=32010142814281570讓p指向要?jiǎng)h除的結(jié)點(diǎn)，讓q指向其前驅(qū)結(jié)點(diǎn)鏈表的刪除結(jié)點(diǎn)操作鏈表的插入結(jié)點(diǎn)操作插入的結(jié)點(diǎn)作表頭結(jié)點(diǎn)951428220108615705142882NULL815702010head75121062106p02010p12010讓p0指向新結(jié)點(diǎn)即要插入的結(jié)點(diǎn)，讓p1指向插入位置上的結(jié)點(diǎn)即表頭結(jié)點(diǎn)head=p0;p0->next=p1;2106插入的結(jié)點(diǎn)作表尾結(jié)點(diǎn)9693652951428220108615705142882NULL815702010head讓p0指向新結(jié)點(diǎn)即要插入的結(jié)點(diǎn)，讓p1指向插入位置上的結(jié)點(diǎn)即表尾結(jié)點(diǎn)3652p01570p1NULL3652鏈表的插入結(jié)點(diǎn)操作p1->next=p0;p0->next=NULL;插入的結(jié)點(diǎn)作中間結(jié)點(diǎn)9262374951428220108615705142882NULL815702010head鏈表的插入結(jié)點(diǎn)操作讓p0指向新結(jié)點(diǎn)即要插入的結(jié)點(diǎn)，讓p1指向插入位置上的結(jié)點(diǎn)，p2指向p1的前驅(qū)結(jié)點(diǎn)2374p01570p11428p223741570p2->next=p0;p0->next=p1;鏈表的插入結(jié)點(diǎn)操作插入結(jié)點(diǎn)函數(shù)ST*insert(ST*head){ST*p0,*p1,*p2;p1=head;p0=(ST*)malloc(LEN);

scanf(“%d%d”,&p0->num,&p0->score);if(head==NULL){head=p0;p0->next=NULL;}else{while((p0->num>p1->num)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->num<=p1->num){if(head==p1)head=p0;elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}}n++;return(head);}//如果是空鏈表，則新結(jié)點(diǎn)是鏈表的表頭結(jié)點(diǎn)//找到要插入結(jié)點(diǎn)的位置//插入結(jié)點(diǎn)作表頭結(jié)點(diǎn)//插入結(jié)點(diǎn)作中間結(jié)點(diǎn)//插入結(jié)點(diǎn)作表尾結(jié)點(diǎn)//鏈表的結(jié)點(diǎn)個(gè)數(shù)加1鏈表的插入結(jié)點(diǎn)操作(1)插入鏈表的第一個(gè)結(jié)點(diǎn)ST*insert(ST*head){ST*p0,*p1,*p2;p1=head;p0=(ST*)malloc(LEN);

scanf(“%d%d”,&p0->num,&p0->score);

if(head==NULL){head=p0;p0->next=NULL;}

else{…}

n++;return(head);}headNULL1428p1p2p03861428NULL1428NULLn0

1鏈表的插入結(jié)點(diǎn)操作ST*insert(ST*head){ST*p0,*p1,*p2;p1=head;p0=(ST*)malloc(LEN);

scanf(“%d%d”,&p0->num,&p0->score);

if(head==NULL){…}

else{while((p0->num>p1->num)&&(p1->next!=NULL))

{…}

if(p0->num<=p1->num){if(head==p1)head=p0;

else…

p0->next=p1;}

else{…}}n++;return(head);}1428head1428386NULLn12p1p2p0

201020101428195(2)插入結(jié)點(diǎn)作表頭結(jié)點(diǎn)14282010鏈表的插入結(jié)點(diǎn)操作ST*insert(ST*head){ST*p0,*p1,*p2;p1=head;p0=(ST*)malloc(LEN);

scanf(“%d%d”,&p0->num,&p0->score);

if(head==NULL){…}else{while((p0->num>p1->num)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}

if(p0->num<=p1->num){…}

else{p1->next=p0;p0->next=NULL;}}n++;return(head);}1570(3)插入結(jié)點(diǎn)作表尾結(jié)點(diǎn)20101428head20101951428386NULLp2p0n2p1582NULL201020101428315707.8類型定義符typedef的用法

當(dāng)用戶定義一種結(jié)構(gòu)體類型后，每次都需要用“struct

結(jié)構(gòu)體類型名”來定義相應(yīng)變量，稍顯麻煩。Ｃ語言不僅提供了豐富的數(shù)據(jù)類型，而且還允許由用戶自己定義類型說明符，也就是說允許由用戶為數(shù)據(jù)類型取“別名”。類型定義符ty