計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)第九講結(jié)構(gòu)

結(jié)構(gòu)的概念與應(yīng)用

例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到

一個(gè)“結(jié)點(diǎn)”里，再用“鏈子穿起來”，形成一條

鏈，相鄰兩結(jié)點(diǎn)間用一個(gè)指針將兩者連到一起。

3

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

目固定、類型不同的若干變量的有序集合。結(jié)

構(gòu)與數(shù)組的區(qū)別在于結(jié)構(gòu)內(nèi)允許有不同類型的

數(shù)據(jù)。

結(jié)構(gòu)的定義，格式如下

structv結(jié)構(gòu)名〉

(

〈成員說明》

例如跳馬棋局可如下定義

structTM

(

intx,y;//結(jié)構(gòu)TM的成員，x,y為整數(shù)型

structTM*next//結(jié)構(gòu)TM的成員，屬TM型

下面的表是馬的跳步方案，從左下角跳到右上角

5

NULL為空地址

下面是形成鏈表的一個(gè)參考程序（分三頁）

6

〃結(jié)構(gòu)l.c

#include<stdio.h>〃預(yù)編譯命令

#definenull0〃定義空指針常量

structTM//定義結(jié)構(gòu)TM

{

intx,y;〃整型變量X,y

structTM*next;〃指向TM結(jié)構(gòu)的指針

}；

voidmain()〃主函數(shù)

(〃主函數(shù)開始

inti;〃聲明整型變量

〃聲明TM結(jié)構(gòu)nl?n7,結(jié)構(gòu)指針head,p

structTMnl,n2,n3,n4,n5,n6,n7/head,*p;

7

//分別對TM結(jié)構(gòu)nl?117中的x,y賦值

nl.x=O;nl.y=O;

n2.x=l;n2.y=2;

n3.x=2;n3.y=4;

n4.x=4;n4.y=4;

n5.x=6;n5.y=4;

n6.x=7;n6.y=2;

n7.x=8;n7.y=4;

//head賦值為nL即head指向nl

head=&nl;

〃nl?n7構(gòu)成鏈表

nl.next=&n2;

n2.next=&n3;

n3.next=&n4;

n4.next=&n5;

n5.next=&n6;

n6.next=&n7;

〃n7的next指針賦值為空指針8

n7.next=null;

p=head;〃p賦值為head,即p指向head所指的內(nèi)容

i=l;〃i賦值為1

do〃直到型循環(huán)

(〃循環(huán)體開始

〃輸

printf(“結(jié)點(diǎn)％(1:x=%d,y=%d\n",i,p->x,p->y);

p=p->next;〃p指向下一個(gè)結(jié)點(diǎn)

i=i+l;//計(jì)數(shù)加1

}while(p!=null);//未到達(dá)鏈表尾部，則繼續(xù)循環(huán)

〃主函數(shù)結(jié)束

9

用結(jié)構(gòu)數(shù)組，利用鍵盤輸入結(jié)點(diǎn)中的數(shù)據(jù)。

重點(diǎn)看

scanf(“％d”,&a);

n[i].x=a;

結(jié)構(gòu)數(shù)組，數(shù)組中的元素為結(jié)構(gòu)類型的數(shù)據(jù)，如n[8]

//結(jié)構(gòu)2.c

#include<stdio.h>〃預(yù)編譯命令

#definenull0〃定義空指針常量

structTM//定義TM結(jié)構(gòu)

intx,y;〃整型變量X,y

structTM*next;〃指向TM結(jié)構(gòu)的指針

｝；

10

voidmain()〃主函數(shù)

〃主函數(shù)開始

inti,a,b;〃聲明整型變量i,a,b

〃聲明TM型結(jié)構(gòu)數(shù)組n[8],TM結(jié)構(gòu)指針head,p

structTMn[8]/head/p;

for(i=l;i<=7；i=i+l)循環(huán)

{〃循環(huán)體開始

printf("輸入n[%d]的x\n",i);//提示輸入第i個(gè)結(jié)構(gòu)的x值

nn

scanf(%d9&a);//輸入a

n[i].x=a;//將a的值賦給結(jié)構(gòu)n[i]的元素x

printf("輸入n[%d]的y\n”,i);//提示輸入第i個(gè)結(jié)構(gòu)的y值

scanf(n%dlf,&b);//輸入b

n[i].y=b;//將b的值賦給結(jié)構(gòu)n[i]的元素y

)〃循環(huán)體結(jié)束

head=&n[l];〃鏈表頭部指向n[l]

for(i=l;i<=6;i=i+l)〃將結(jié)構(gòu)數(shù)組n形成鏈表

n[i].next=&n[i+1];//n[i]的next指針指向下一個(gè)結(jié)構(gòu)n[i+l]

n[7].next=null;〃鏈表尾部指向空

p=head;//p指向鏈表頭部head

i=l；〃i賦值為1

do〃直到型循環(huán)，用于輸出鏈表內(nèi)容

〃循環(huán)體開始

〃輸出結(jié)點(diǎn)內(nèi)容

printf(“結(jié)點(diǎn)%出x=%d,y=%d\n''i，p->x,p->y);

p=p->next;〃p指向相鄰的下一個(gè)結(jié)點(diǎn)

i=i+l;〃計(jì)數(shù)i加1

}while(p!=null);〃未到鏈表尾部，則繼續(xù)循環(huán)

〃主函數(shù)結(jié)束12

下面的程序與上面的程序區(qū)別僅在

scanfC6%d9\&(n[i].x));

去替換

scanf(u%d^&a);

n[i].x=a;

//結(jié)構(gòu)3.c

#include<stdio.h>〃預(yù)編譯命令

#definenull0〃定義空指針常量

structTM//定義TM結(jié)構(gòu)

intx,y;〃整型變量X,y

structTM*next;〃指向TM結(jié)構(gòu)的指針

｝；

13

voidmain()〃主函數(shù)

{〃主函數(shù)開始

inti,a,b;〃聲明整型變量i,a,b

〃聲明TM型結(jié)構(gòu)數(shù)組n[8],TM結(jié)構(gòu)指針head,p

structTMn[8],*head,*p;

for(i=l;iv=7;i=i+l)//循環(huán)

{〃循環(huán)體開始W

printf("輸入n[%d]的x\n，\i);//提示輸入第i個(gè)結(jié)構(gòu)的x值

scanfC%d!\&(n[i].x));〃輸入n[i].x

printf("輸入n[%d]的y\n”,i);//提示輸入第i個(gè)結(jié)構(gòu)的y值

scanf(M%d1\&(n[i].y));//輸入n[i].y

}〃循環(huán)體結(jié)束

14

head=&n[l];〃鏈表頭部指向n[l]

for(i=l;i<=6;i=i+l)//循環(huán)

〃循環(huán)體開始

n[i].next=&n[i+l];//11國.110/1：指向11廿+1]

}〃循環(huán)體結(jié)束

n[7].next=null;〃鏈表尾部賦值為空指針

p=head;//p指向鏈表頭部head

i=l；〃i賦值為1

do〃直到型循環(huán)

{〃循環(huán)體開始

〃提示輸入結(jié)點(diǎn)信息

printf(“結(jié)點(diǎn)％出x=%d,y=%d\n”,i,(*p).x,(*p).y);

p=(*p).next;〃p指向相鄰的下一個(gè)結(jié)點(diǎn)

i=i+l;〃功口1

}while(p!=null);〃未到達(dá)鏈表尾部，則繼續(xù)循環(huán)

〃主函數(shù)結(jié)束15

任務(wù)：

我4]要作一張登記表，登記排隊(duì)求職信息，包括：姓名、年

齡、性別、電話四個(gè)參數(shù)。希望便于管理，即可以插入和刪

B余，這時(shí)可用隊(duì)列，采用結(jié)構(gòu)類型變量。

structST

charname[20];〃字符串，姓名

intage;〃整數(shù)，年齡

charsex;〃字符，性另I

longnum;//龜話號(hào)碼

structST*next;//ST結(jié)構(gòu)的指針

｝；〃注意，這里必須有分號(hào)

聲明結(jié)構(gòu)指針變量用下列形式

structST/head,*q;

上面的head,p,q為結(jié)構(gòu)指針。

結(jié)構(gòu)的成員可以是指針，意味著這種結(jié)構(gòu)指針可以指

向結(jié)構(gòu)變量。

結(jié)構(gòu)變量和指向結(jié)構(gòu)變量的指針可以作為函數(shù)的參數(shù)

與返回值。用結(jié)構(gòu)變量作函數(shù)返回值的函數(shù)稱之為

結(jié)構(gòu)函數(shù)。structST*create(void)就是結(jié)構(gòu)函數(shù)，

為了了解結(jié)構(gòu)變量成員的地址情況，我們給出了程

序“結(jié)構(gòu)5.c”，在這個(gè)程序中我們重點(diǎn)看

1、#include<malloc.h>

這是預(yù)編譯命令，為了分配結(jié)構(gòu)變量的內(nèi)存地址用

的。

2、#definenull0

這是定義空指針變量常量，null代表0。

3、#defineLENsizeof(structST)

定義常量LEN,表示結(jié)構(gòu)ST中的變量的全部單不

的長度，分配內(nèi)存空間時(shí)需要知道這個(gè)長度信息。

4、結(jié)構(gòu)ST的定義

5、函數(shù)create的定義

6、給結(jié)構(gòu)指針p分配內(nèi)存空間。

p=(structST*)malloc(LEN);

7、查看指針p所在的地址

printf("指針p所在的地址&p=%X\n”,&p);

8、查看指針p所指向的地址\

printf(“指針p所指向的地址p=%X\n\n",p);

9、輸入姓名，查看姓名所在的地址

scanf(w%s9\&((*p).name));

10、輸入年齡，查看年齡數(shù)據(jù)所在的地址

scanf(“％d”,&((*p).age));

printf(“年齡數(shù)據(jù)所在地址％X\n\n”,&((*p).age))S

〃結(jié)構(gòu)5.c(分四頁)

#include<stdio.h>〃預(yù)編譯命令

#include<malloc.h>〃預(yù)編譯命令，內(nèi)存空間分配

#definenull0〃定義空指針常量

#defineLENsizeof(structST)〃定義常量LEN,

〃表示結(jié)構(gòu)ST的長度

structST//結(jié)構(gòu)ST定義

(

charname[20];〃字符串，表示名字

intage;〃整數(shù)類型，表示年齡

charsex;〃字符類型，表示性別

longnum;〃長整型，表示電話號(hào)碼

structST*next;〃ST結(jié)構(gòu)指針

structST*head,*p,*q;〃聲明，結(jié)構(gòu)指針變量head,p,q

voidcreate（void）//定義一個(gè)名為create的函數(shù)，無形參和返回值

{〃函數(shù)體開始

intn=0;〃整型變量n,賦初值為0

head=null;//ST結(jié)構(gòu)指針head,賦初值為null

p=（structST*）malloc（LEN）;//給結(jié)構(gòu)指針p分配內(nèi)存空間

〃輸出指針p所在地址

printf（"指針p所在地址&p=%X\nu,&p）;

〃輸出指針p所指向的地址

printf（"指針p所指向的地址p=%X\n\nn,p）;

q=p；〃q賦值為p,即q指向p所指的內(nèi)容

〃輸出指針p所在地址

printf（"旨針q所在地址&q=%X\nn,&q）;

〃輸出指針p所指向的地址

H

printf（”旨針q所指向的地址q=%X\n\n,q）;20

//提示輸入第n+1個(gè)結(jié)點(diǎn)的數(shù)據(jù)

printf("輸入第％d個(gè)結(jié)點(diǎn)的數(shù)據(jù)\n",n+1);

printf(“依次為name,age,sex,num\n’')；

〃提示輸入姓名數(shù)據(jù)，并輸出其所在地址

printf—輸入姓名數(shù)據(jù)％d\n”再+1);

scanf(t,%s,\&((*p).name));

printf("姓名數(shù)軸說在地虻%X\n\nn,&((*p).name));

〃提示輸入年齡數(shù)據(jù)，并輸出其所在地址

printf("輸入年齡數(shù)據(jù)％d\iV\n+l);

scanf(n%dn,&((*p).age));

printf,年齡數(shù)據(jù)所在血址％X\n\n”,&((*p).age));

〃提示輸入性別數(shù)據(jù)，并輸出其所在地址

printfC輸入性別數(shù)據(jù)％d\iT,n+l);

nn

scanf(%s,&((*p).sex));21

printf(“性別數(shù)據(jù)所在地址％*\11\曖,&(0^).乂));

printf("輸入電話號(hào)碼數(shù)據(jù)％(1\11111+1);〃輸出提示信息

〃從鍵盤輸入電話號(hào)碼

scanf(n%ldn,&((*p).num));

〃輸出電話號(hào)碼所在地址

printf(n電話號(hào)碼所在地址％X\n\n",&((*p).iium));

printf("輸出姓名%s\nu,p->name);〃輸出姓名

printfC輸出年齡％d\n[p->age);〃輸出年齡

n

printf("輸出性別%c\n9p->sex);//輸出性別

printf("輸出電話號(hào)碼％ld\n"?>iium);〃輸出電話號(hào)碼

}

voidmainO〃主函數(shù)

{〃主函數(shù)開始

create();〃調(diào)用函數(shù)create。，建立鏈表22

}〃主函數(shù)結(jié)束

structST*create(void)

定義p,q為ST結(jié)構(gòu)指針，定義一個(gè)tmpStr字符串

作臨時(shí)變量，讓head,p,q三個(gè)指針初始化為空。

讓n=0(初始化計(jì)數(shù)器n)

n=n+l;計(jì)數(shù)茗等力口1

do且入姓名賑^給臨時(shí).變量tmpStr

(tmpStr,".,9)==0

輸入了”產(chǎn)，結(jié)束輸入，退出

分酉己空間給p寸旨針，p=(structST*)malloc(LEN)；

u11,分配不成(功?^***^****^

給出出錯(cuò)信息，退出循環(huán)

strcpy((*p).name,tmpStr);

將1［缶日寸變J|tmpStr中存放的姓名存入結(jié)構(gòu)中

輸入，并存入年齡，

輸入，并存入件另U,

卅I入，并存入電話號(hào)碼

,是個(gè)結(jié)點(diǎn)嗎?

head=p;1匕頭c才旨車十才旨|可令拿1(女q).next=p;斗與該

個(gè)結(jié)點(diǎn)結(jié)點(diǎn)加到表尾

q=p；讓q指向新加入的結(jié)點(diǎn)p,這是表尾：3

while(l);用1表示死循環(huán)

24

〃結(jié)構(gòu)6.c(分四頁)

#include<stdio.h>〃預(yù)編譯命令

#include<malloc.h>//內(nèi)存空I司分配

#definenull0〃定義空指針常量

#defineLENsizeof(structST)〃定義常量，表示結(jié)構(gòu)長度

structST〃結(jié)構(gòu)聲明

(

charname[20];〃名字，字符串

intage;〃年齡，整型數(shù)組

charsex;〃性別，字符型變量

longnum;〃電話號(hào)碼，長整型變量

structST*next;//ST結(jié)構(gòu)指針

｝；

structST*head;〃聲明全局變量head為ST結(jié)構(gòu)指針

voidcreate(void)〃被調(diào)用函數(shù)，用于建立鏈表

〃函數(shù)體開始

structST*p,*q;//聲明ST結(jié)構(gòu)指針PM

intn=0;〃整型變量，用于由條輸入的人數(shù)

chartmpStr[20];〃字符串，作為臨時(shí)變量

head=null;〃鏈表頭部指針，初始化為空

p=null;〃鏈表當(dāng)前結(jié)構(gòu)指針，初始化為空25

q=null:〃鏈表尾部指針，初始化為空

do//直到型循環(huán)，用于循環(huán)輸入人員信息

{

n=n+l;〃人數(shù)加1

printf("輸入第％d個(gè)結(jié)點(diǎn)的數(shù)據(jù)\n“,n);〃提示信息

printf("輸入姓名數(shù)據(jù)％d\n",n);//提示輸入姓名

scanf(n%sf\tmpStr);〃輸入姓名信息，并存入臨時(shí)變量

〃判斷輸入是否結(jié)束，如果為“」，則結(jié)束

if(strcmp(tmpStr/f.n)==O)break;

p=(structST*)malloc(LEN);//為p分配空間

if(p==null)//判斷分配是否成功

(

〃如果分配出錯(cuò)，則輸出出錯(cuò)信息

printf(nInsufficientmemoryavailable\nn);

break;〃退出循環(huán)

strcpy((*p).name,tmpStr);//將名字存入p結(jié)構(gòu)中的name單元

printf(，喻入年齡數(shù)據(jù)％d\n",n);//提示輸入年齡

scanf(n%dn,&((*p).age));〃輸入年齡

printf("輸入性別數(shù)據(jù)％d\n",n);//提示輸入年齡

scanf(''%s”,&((*p).sex));〃輸入性別

printf("輸入電話號(hào)碼數(shù)據(jù)％(1\11",11);//提示輸入電話號(hào)碼

scanf(n%ldM,&((*p).num));〃輸入電話號(hào)碼

if(n==l)head=p;//如果是第一個(gè)結(jié)構(gòu)，則將head指向此結(jié)構(gòu)

else(*q).next=p;〃如果不是第一個(gè)結(jié)構(gòu)，

〃則將此結(jié)構(gòu)加到鏈表尾部

q=p；//q指針指向此結(jié)構(gòu)，表示新的鏈表尾部

}while(l);〃循環(huán)體結(jié)束，1表示死循環(huán)

if(q!=null)//鏈表尾部是否為空

q->next=null;〃如果不為空，則鏈表尾部的next指向空指針

voidprint()〃被調(diào)用函數(shù)，形參為ST結(jié)構(gòu)指針

{

intk=0;〃整型變量，用于計(jì)數(shù)

structST*r;〃聲明r為ST結(jié)構(gòu)指針

r=head;//r賦值為head,即指向head所指向的內(nèi)容

while(r!=null)//當(dāng)型循環(huán)，鏈表指針不為空

{〃循環(huán)體開始

k=k+l;//計(jì)數(shù)加1

printf("輸出排隊(duì)求職者信息％d:%s,%d,%c,%ld\iT-

,k,r->name,r->age,r->sex,r->num);〃輸出人員信息

)〃循環(huán)體結(jié)束▼

}〃被調(diào)用函數(shù)結(jié)束

voidmain()〃主函數(shù)開始

{〃函數(shù)體開始

create();//調(diào)用create函數(shù)建立鏈表

print();〃調(diào)用print函數(shù)，輸出鏈表內(nèi)容

)〃主函數(shù)結(jié)束

Z8-

字符串處理函數(shù)簡介

1、strcmp(sl,s2)

例

printf(66######%d\n”,strcmp(“b”Jb"));

輸出######0

printf("######%d\n”,strcmp(“b",”P));

輸出######-1

結(jié)論：

>當(dāng)sl>s2日寸strcmp(sl,s2)的值為1

>當(dāng)sl=s2時(shí)strcmp(sl,s2)的值為0

>當(dāng)sl〈s2時(shí)strcmp(sl,s2)的值為-1

29

字符串處理函數(shù)簡介

2、strncmp(sl,s2,n)

類似于strcmp(sl,s2,n),但只比較兩個(gè)字符串的前n

個(gè)字符。

3、strlen(s)

返回s字符串的長度(不包括結(jié)束符八(F)

例：printf("######%d\n5\strlen(uabcdefgh59));

輸出######8

4、strcpy(sl,s2)

將s2的內(nèi)容復(fù)制到si中，返回si指針。其中si和s2

為指向char的指針。

30

鏈表插入結(jié)點(diǎn)

原則:

AL插入操作不應(yīng)破壞原鏈接關(guān)系

?2、插入的結(jié)點(diǎn)應(yīng)該在它該在的位置。應(yīng)該

有一個(gè)插入位置的查找子過程。

31

先看下面一個(gè)簡單的例子：已有一個(gè)如圖所示的鏈表。

它是按結(jié)點(diǎn)中的整數(shù)域從小到大排序的?，F(xiàn)在要插

入一個(gè)結(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)為10。

head

10

此結(jié)點(diǎn)已插入鏈表32

分析：

考慮將結(jié)點(diǎn)p插入鏈表head中，分如下三種情況：

?1、第一種情況，鏈表還未建成（空鏈表），待插入結(jié)

點(diǎn)p實(shí)際上是第一個(gè)結(jié)點(diǎn)。這時(shí)必然有head==iniH。只

要讓頭指針指向p就可以了。語句為

---------------------鼠headJ"

head=p;:6

p->next=null;pnull

A2、第二種情況，鏈表已建成，待插入結(jié)點(diǎn)p的數(shù)據(jù)

要比頭結(jié)點(diǎn)的數(shù)據(jù)還要小，這時(shí)有

p->num<head->num

當(dāng)然p結(jié)點(diǎn)要插在head結(jié)點(diǎn)前。

33

34

A3、第三種情況，鏈表已建成，待插入結(jié)點(diǎn)p的數(shù)

據(jù)比頭結(jié)點(diǎn)的數(shù)據(jù)大，需要找到正確的插入位置。

這時(shí)，可以借助兩個(gè)結(jié)構(gòu)指針r和q,利用循環(huán)比

較來找到正確位置。然后將結(jié)點(diǎn)p插入到鏈表中正

確的位置。4

參見下面的圖示

35

說明：這種情況下，P結(jié)點(diǎn)已經(jīng)與鏈表的第一個(gè)結(jié)點(diǎn)

比較過了，所以從鏈表的下一個(gè)結(jié)點(diǎn)開始比較。

13>8,繼續(xù)比較。、

說明：13Vl5,找到了正確的插入位置，則插入結(jié)點(diǎn)p。

語句為：

r->next=p;

p->next=q;38

參考程序

//結(jié)構(gòu)7.c

#include<stdio.h>〃預(yù)編譯命令

#include<malloc.h>//內(nèi)在空尚分配

#definenull0//定義空指針常量

#defineLENsizeof(structnumST)〃定義常量，表示結(jié)構(gòu)長度

structnumST//結(jié)構(gòu)聲明

{..

intnum;//整型數(shù)

structnumST*next;//numST結(jié)構(gòu)指針

}；

39

〃被調(diào)用函數(shù)insert。，兩個(gè)形參分別表示鏈表和待插入的結(jié)點(diǎn)

voidinsert(structnumST**phead,structnumST*p)

〃函數(shù)體開始

structnumST*q,*r;〃定義結(jié)構(gòu)指針q,r

if((*phead)==null)〃第一種情況，鏈表為空

*phead=p;〃鏈表頭指向p

return;〃完成插入操作，返回

}

else〃鏈表不為空

//第二種情況，p結(jié)點(diǎn)num值小于鏈表頭結(jié)點(diǎn)的num值

if((*phead)->num>p->num)

{〃將p結(jié)點(diǎn)插到鏈表頭部

p->next=*phead;//將p的next指針指向鏈表頭(*口1102~)

*phead=p;〃將鏈表頭賦值為p

return;〃返回

40

)

〃第三種情況，循環(huán)查找正確位置

r=*phead;//r賦值為鏈表頭

q=(*phead)->next;〃q賦值為鏈表的下一個(gè)結(jié)點(diǎn)

while(q!