7.1 結(jié)構(gòu)體類型變量的定義和引用

2006-6-15 16:33:16

7.3 結(jié)構(gòu)體指針的定義和引用
7.3.1 指向結(jié)構(gòu)體類型變量的使用
7.3.2 指向結(jié)構(gòu)體類型數(shù)組的指針的使用
7.4 鏈表的建立、插入和刪除
7.4.1 單鏈表
7.4.2 單鏈表的插入與刪除

7.3 結(jié)構(gòu)體指針的定義和引用
指針變量非常靈活方便，可以指向任一類型的變量，若定義指針變量指向結(jié)構(gòu)體類型變量，則可以通過指針來引用結(jié)構(gòu)體類型變量。

7.3.1 指向結(jié)構(gòu)體類型變量的使用
首先讓我們定義結(jié)構(gòu)體：
struct stu
{
char name[20];
long number;
float score[4];
} ;
再定義指向結(jié)構(gòu)體類型變量的指針變量：
struct stu *p1, *p2 ;
定義指針變量p 1、p 2，分別指向結(jié)構(gòu)體類型變量。引用形式為：指針變量→成員；

[例7-2] 對指向結(jié)構(gòu)體類型變量的正確使用。輸入一個結(jié)構(gòu)體類型變量的成員，并輸出。
#include /*使用malloc( ) 需要*/
struct data /*定義結(jié)構(gòu)體*/
{
int day,month,year;
};
struct stu /*定義結(jié)構(gòu)體*/
{
char name[20];
long num;
struct data birthday; /* 嵌套的結(jié)構(gòu)體類型成員*/
} ;
main() /*定義main( ) 函數(shù)*/
{
struct stu *student; /* 定義結(jié)構(gòu)體類型指針*/
student=malloc(sizeof(struct stu)); /* 為指針變量分配安全的地址* /
printf("Input name,number,year,month,day:\n");
scanf("%s",student->name); /* 輸入學生姓名、學號、出生年月日*/
scanf("%ld", &student->num);
scanf("%d %d %d", &student->birthday.year,&student->birthday.month,&student->birthday.day);
printf("\nOutput name,number,year,month,day\n" );
/*打印輸出各成員項的值*/
printf("%20s%10ld%10d//%d//%d\n",student->name,student->num,student->birthday.year,student->birthday.month,student->birthday.day);
}
程序中使用結(jié)構(gòu)體類型指針引用結(jié)構(gòu)體變量的成員，需要通過C提供的函數(shù)malloc( )來為指針分配安全的地址。函數(shù)sizeof( )返回值是計算給定數(shù)據(jù)類型所占內(nèi)存的字節(jié)數(shù)。指針所指各成員形式為：
student->name
student->num
student->birthday.year
student->birthday.month
student->birthday.day
運行程序：
Input name,number,year,month,day:
Wangjian 34 1987 5 23
Wangjian 34 1987//5//23

7.3.2 指向結(jié)構(gòu)體類型數(shù)組的指針的使用
定義一個結(jié)構(gòu)體類型數(shù)組，其數(shù)組名是數(shù)組的首地址，這一點前面的課程介紹得很清楚。定義結(jié)構(gòu)體類型的指針，既可以指向數(shù)組的元素，也可以指向數(shù)組，在使用時要加以區(qū)分。

[例7-3] 在例7 - 2中定義了結(jié)構(gòu)體類型，根據(jù)此類型再定義結(jié)構(gòu)體數(shù)組及指向結(jié)構(gòu)體類型的指針。
struct data
{
int day,month,year;
} ;
struct stu /*定義結(jié)構(gòu)體*/
{
char name[20];
long num;
struct data birthday; /* 嵌套的結(jié)構(gòu)體類型成員* /
} ;
struct stu student[4],*p; /* 定義結(jié)構(gòu)體數(shù)組及指向結(jié)構(gòu)體類型的指針*/
作p = student，此時指針p就指向了結(jié)構(gòu)體數(shù)組student。
p是指向一維結(jié)構(gòu)體數(shù)組的指針，對數(shù)組元素的引用可采用三種方法。
1) 地址法
student+i和p+i均表示數(shù)組第i個元素的地址，數(shù)組元素各成員的引用形式為：
(student+i)-> name、(student+i)->num和(p+i)->name、(p+i)->num等。student+i和p+i與&student意義相同。
2) 指針法
若p指向數(shù)組的某一個元素，則p++就指向其后續(xù)元素。
3) 指針的數(shù)組表示法
若p=student，我們說指針p指向數(shù)組student，p表示數(shù)組的第i個元素，其效果與student等同。對數(shù)組成員的引用描述為: p.name、p.num等。

[例7-4] 指向結(jié)構(gòu)體數(shù)組的指針變量的使用。
struct data /*定義結(jié)構(gòu)體類型*/
{
int day,month,year;
} ;
struct stu /*定義結(jié)構(gòu)體類型*/
{
char name[20];
long num;
struct data birthday;
} ;

main( )
{
int i;
struct stu *p,student[4]={{"liying",1,1978,5,23},{"wangping",2,1979,3,14},
{ "libo",3,1980,5,6},{"xuyan",4,1980,4,21}};
/ *定義結(jié)構(gòu)體數(shù)組并初始化* /
p=student; /*將數(shù)組的首地址賦值給指針p , p 指向了一維數(shù)組student*/
printf("\n1----Output name,number,year,month,day\n");
for(i=0;iname,(p+i)->num,(p+i)->birthday.year,(p+i)->birthday.month,(p+i)->birthday.day);
printf("\n2----Output name,number,year,month,day\n" );
for(i=0;iname,p->num,p->birthday.year,p->birthday.month,p->birthday.day);
printf("\n3-----Output name,number,year,month,day\n" );
for(i=0;iname,(student+i)->num,(student+i)->birthday.year,(student+i)->birthday.month,(student+i)->birthday.day);
p=student;
printf("\n4-----Output name,number,year,month,day\n" );
for(i=0;i





4) 將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非空表，將新
節(jié)點接到表尾。
5) 判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束。
• 單鏈表的輸出過程有以下幾步
1) 找到表頭。
2) 若是非空表，輸出節(jié)點的值成員，是空表則退出。
3) 跟蹤鏈表的增長，即找到下一個節(jié)點的地址。
4) 轉(zhuǎn)到2 )。

[例7-5] 創(chuàng)建一個存放正整數(shù)（輸入- 9 9 9做結(jié)束標志）的單鏈表，并打印輸出。
#include /* 包含malloc( ) 的頭文件*/
#include
struct node /*鏈表節(jié)點的結(jié)構(gòu)* /
{
int num;
struct node *next;
} ;
main( )
{
struct node *creat(); / *函數(shù)聲明* /
void print();
struct node *head; / * 定義頭指針* /
head=NULL; /* 建一個空表*/
head=creat(head); /* 創(chuàng)建單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************************/
struct node *creat(struct node *head) /* 函數(shù)返回的是與節(jié)點相同類型的指針*/
{
struct node *p1,*p2;
p1=p2=(struct node*) malloc(sizeof(struct node)); /* 申請新節(jié)點*/
scanf("%d", &p1->num); /* 輸入節(jié)點的值*/
p1-> next = NULL; /* 將新節(jié)點的指針置為空*/
while(p1->num>0) /* 輸入節(jié)點的數(shù)值大于0 */
{
if (head==NULL) head=p1; /* 空表，接入表頭*/
else p2->next=p1; /* 非空表，接到表尾*/
p2 = p1;
p1=(struct node *)malloc(sizeof(struct node)); /* 申請下一個新節(jié)點*/
scanf("%d", &p1->num); /*輸入節(jié)點的值*/
}
return head; /*返回鏈表的頭指針*/
}
/****************************************************/
void print(struct node *head) /* 輸出以head 為頭的鏈表各節(jié)點的值*/
{
struct node *temp;
temp=head; /*取得鏈表的頭指針*/
while (temp!=NULL) / *只要是非空表* /
{
printf("%6d", temp->num); /*輸出鏈表節(jié)點的值*/
temp=temp->next; /*跟蹤鏈表增長*/
}
}
在鏈表的創(chuàng)建過程中，鏈表的頭指針是非常重要的參數(shù)。因為對鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創(chuàng)建成功后，要返回一個鏈表頭節(jié)點的地址，即頭指針。
運行程序：
1 2 3 4 5 6 7 -999 ¿
1 2 3 4 5 6 7
鏈表的創(chuàng)建過程用圖示如下：




7.4.2 單鏈表的插入與刪除
在鏈表這種特殊的數(shù)據(jù)結(jié)構(gòu)中，鏈表的長短需要根據(jù)具體情況來設定，當需要保存數(shù)據(jù)時向系統(tǒng)申請存儲空間，并將數(shù)據(jù)接入鏈表中。對鏈表而言，表中的數(shù)據(jù)可以依此接到表尾或連結(jié)到表頭，也可以視情況插入表中；對不再需要的數(shù)據(jù)，將其從表中刪除并釋放其所占空間，但不能破壞鏈表的結(jié)構(gòu)。這就是下面將介紹的鏈表的插入與刪除。

1. 鏈表的刪除
在鏈表中刪除一個節(jié)點，用圖7 - 4描述如下：





[例7-6] 創(chuàng)建一個學生學號及姓名的單鏈表，即節(jié)點包括學生學號、姓名及指向下一個
節(jié)點的指針，鏈表按學生的學號排列。再從鍵盤輸入某一學生姓名，將其從鏈表中刪除。
首先定義鏈表的結(jié)構(gòu)：
struct
{
int num;/* 學生學號*/
char str[20]; /* 姓名*/
struct node *next;
} ;
從圖7 - 4中看到，從鏈表中刪除一個節(jié)點有三種情況，即刪除鏈表頭節(jié)點、刪除鏈表的中間節(jié)點、刪除鏈表的尾節(jié)點。題目給出的是學生姓名，則應在鏈表中從頭到尾依此查找各節(jié)點，并與各節(jié)點的學生姓名比較，若相同，則查找成功，否則，找不到節(jié)點。由于刪除的節(jié)點可能在鏈表的頭，會對鏈表的頭指針造成丟失，所以定義刪除節(jié)點的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。
struct node *delet(head,pstr)/* 以head 為頭指針，刪除pstr 所在節(jié)點*/
struct node *head;
char *pstr;
{
struct node *temp,*p;
temp=head; /* 鏈表的頭指針*/
if (head==NULL) /*鏈表為空*/
printf("\nList is null!\n");
else /*非空表* /
{
temp=head;
while (strcmp(temp->str,pstr)!=0&&temp->next!=NULL)
/* 若節(jié)點的字符串與輸入字符串不同，并且未到鏈表尾*/
{
p=temp;
temp=temp->next; /* 跟蹤鏈表的增長，即指針后移*/
if(strcmp(temp->str,pstr)==0 ) /*找到字符串*/
{
if(temp==head)
{ / * 表頭節(jié)點* /
printf("delete string :%s\n",temp->str);
head=head->next;
free(temp); /*釋放被刪節(jié)點*/

}
else
{
p->next=temp->next; /* 表中節(jié)點*/
printf("delete string :%s\n",temp->str);
free(temp);
}
}
else printf("\nno find string!\n");/* 沒找到要刪除的字符串*/
}
return(head); /*返回表頭指針*/
}

2. 鏈表的插入
首先定義鏈表的結(jié)構(gòu)：
struct
{
int num; /*學生學號*/
char str[20]; /*姓名*/
struct node *next;
} ;
在建立的單鏈表中，插入節(jié)點有三種情況，如圖7 - 5所示。





插入的節(jié)點可以在表頭、表中或表尾。假定我們按照以學號為順序建立鏈表，則插入的
節(jié)點依次與表中節(jié)點相比較，找到插入位置。由于插入的節(jié)點可能在鏈表的頭，會對鏈表的
頭指針造成修改，所以定義插入節(jié)點的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。節(jié)點的
插入函數(shù)如下：
struct node *insert(head,pstr,n) /*插入學號為n、姓名為pstr的節(jié)點*/
struct node *head; /*鏈表的頭指針*/
char *pstr;
int n;
{
struct node *p1,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));/* 分配一個新節(jié)點* /
strcpy(p1->str,pstr); /* 寫入節(jié)點的姓名字串*/
p1->num=n; /* 學號*/
p2=head;
if(head==NULL) /* 空表*/
{
head=p1; p1->next=NULL;/*新節(jié)點插入表頭*/
}
else
{ /*非空表* /
while(n>p2->num&&p2->next!=NULL)
/ *輸入的學號小于節(jié)點的學號，并且未到表尾* /
{
p3=p2;
p2=p2->next; /* 跟蹤鏈表增長*/
}
if(nnum) /*找到插入位置*/
if (head==p2) / * 插入位置在表頭* /
{
head=p1;
p1->next=p2;
}
else
{ /*插入位置在表中*/
p3->next=p1;
p1->next=p2;
}
else
{ /*插入位置在表尾*/
p2->next=p1;
p1->next=NULL;
}
}
return(head);/* 返回鏈表的頭指針*/
}

3. 實例[例7 - 7 ]
創(chuàng)建包含學號、姓名節(jié)點的單鏈表。其節(jié)點數(shù)任意個，表以學號為序，低學號的在前，高學號的在后，以輸入姓名為空作結(jié)束。在此鏈表中，要求刪除一個給定姓名的節(jié)點，并插入一個給定學號和姓名的節(jié)點。
#include "stdlib.h"
#include "malloc. h"
struct node /*節(jié)點的數(shù)據(jù)結(jié)構(gòu)*/
{
int num;
char str[20];
struct node *next;
};
/*******************************************************/
main( )
{
/*函數(shù)聲明*/
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表*/
head=creat (head); /*調(diào)用函數(shù)創(chuàng)建以head 為頭的鏈表*/
print(head);/*調(diào)用函數(shù)輸出節(jié)點*/
printf("\n input inserted num,name:\n");
gets(str); /*輸入學號*/
n=atoi (str);
gets(str); /*輸入姓名* /
head=insert (head, str, n); /* 將節(jié)點插入鏈表*/
print (head)； / *調(diào)用函數(shù)輸出節(jié)點*/
printf("\n input deleted name:\n");
gets(str); /*輸入被刪姓名*/
head=delet(head,str); /* 調(diào)用函數(shù)刪除節(jié)點*/
print (head); /*調(diào)用函數(shù)輸出節(jié)點*/
return;
}

/****************創(chuàng)建鏈表******************/
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf ("input num, name: \n") ;
printf("exit:double times Enter!\n");
g e t s ( t e m p ) ;
gets (p1->str);
pl->num=atoi (temp);
pl->next=NULL;
while (strlen (pl->str)>0
{
if(head==NULL) head=pl;
else p2->next=p1;
P2=pl;
pl=(struct node *)malloc(sizeof(struct node));
printf ("input num, name: \n");
printf("exit:double times Enter!\n");
gets(temp);
gets(pl ->str);
p1->num=atoi (temp);
P1->next=NULL;
}
return head;
}

/********** 插入節(jié)點**********/
struct node *insert (head, pstr,n);
struct node *head;
char *pstr;
int n;
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1->str, pstr);
p1->num=n;
p2=head;
if(head==NULL)
{
head=pl;pl->next=NULL;
}
else
{
while (n>p2->num&&p2->next!=NULL)
{
p3=P2
p2=p2->next;
}
if (nnum)
if (head==p2)
{
head=pl;
pl->next=p2;
}
else
{
p3->next=pl;
pl->next=p2;
}
else
{
p2->next=pl;
pl->next=NULL;
}
}
return(head);
}

/***** 刪除節(jié)點*************/
struct node *delet (head, pstr)
struct node *head;
char *pstr;
{
struct node *temp,*p;
temp=head;
if (head==NULL)
printf("\nList is null!\n");
else
{
temp=head;
while (strcmp(temp->str,pstr)!=O&&temp->next!=NULL)
{
p=temp;
temp=temp->next,
}
if(strcmp(temp->str,pstr)==0)
{
if(temp== head)
{
head=head->next;
free(temp);
}
else
{
p->next =temp->next;
printf("delete string :%s\n",temp->str);
free(temp);
}
}
else printf("\nno find string!\n");
}
return(head);
}

/**********鏈表各節(jié)點的輸出**********/
void print (struct node *head)
{
struct node *temp;
t e m p = h e a d ;
printf("\n output strings:\n");
while (temp!=NULL)
{
printf("\n%d----%s\n",temp->num,temp->str);
temp=temp->next;
}
return;
}
運行程序：
input num,name:
exit:double times Enter!
1
Huangping
input num,name:
exit:double times Enter!
3
Lixiaobo
input num,name:
exit:double times Enter!
4
Yangjinhua
input num,name:
exit:double times Enter!
7
xuehong
input num,name:
exit:double times Enter!

output strings:
1------- Huangping
3--------Lixiaobo
4--------Yangjinhua
7--------xuehong
input inserted num,name:
5
Liling
output strings:
1------- Huangping
3--------Lixiaobo
4--------Yangjinhua
5--------Liling
7--------xuehong
input deleted name:
Lixiaobo
delete string : Lixiaobo
1------- Huangping
4--------Yangjinhua
5--------Liling
7--------xuehong