7.3 結構體指針的定義和引用
7.3.1 指向結構體類(lèi)型變量的使用
7.3.2 指向結構體類(lèi)型數組的指針的使用
7.4 鏈表的建立、插入和刪除
7.4.1 單鏈表
7.4.2 單鏈表的插入與刪除

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

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

[例7-2] 對指向結構體類(lèi)型變量的正確使用。輸入一個(gè)結構體類(lèi)型變量的成員，并輸出。
#include /*使用malloc( ) 需要*/
struct data /*定義結構體*/
{
int day,month,year;
};
struct stu /*定義結構體*/
{
char name[20];
long num;
struct data birthday; /* 嵌套的結構體類(lèi)型成員*/
} ;
main() /*定義main( ) 函數*/
{
struct stu *student; /* 定義結構體類(lèi)型指針*/
student=malloc(sizeof(struct stu)); /* 為指針變量分配安全的地址* /
printf("Input name,number,year,month,day:\n");
scanf("%s",student->name); /* 輸入學(xué)生姓名、學(xué)號、出生年月日*/
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);
}
程序中使用結構體類(lèi)型指針引用結構體變量的成員，需要通過(guò)C提供的函數malloc( )來(lái)為指針?lè )峙浒踩牡刂?。函數sizeof( )返回值是計算給定數據類(lèi)型所占內存的字節數。指針所指各成員形式為：
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 指向結構體類(lèi)型數組的指針的使用
定義一個(gè)結構體類(lèi)型數組，其數組名是數組的首地址，這一點(diǎn)前面的課程介紹得很清楚。定義結構體類(lèi)型的指針，既可以指向數組的元素，也可以指向數組，在使用時(shí)要加以區分。

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

[例7-4] 指向結構體數組的指針變量的使用。
struct data /*定義結構體類(lèi)型*/
{
int day,month,year;
} ;
struct stu /*定義結構體類(lèi)型*/
{
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}};
/ *定義結構體數組并初始化* /
p=student; /*將數組的首地址賦值給指針p , p 指向了一維數組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) 將新節點(diǎn)的指針成員賦值為空。若是空表，將新節點(diǎn)連接到表頭；若是非空表，將新
節點(diǎn)接到表尾。
5) 判斷一下是否有后續節點(diǎn)要接入鏈表，若有轉到3 )，否則結束。
• 單鏈表的輸出過(guò)程有以下幾步
1) 找到表頭。
2) 若是非空表，輸出節點(diǎn)的值成員，是空表則退出。
3) 跟蹤鏈表的增長(cháng)，即找到下一個(gè)節點(diǎn)的地址。
4) 轉到2 )。

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




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

1. 鏈表的刪除
在鏈表中刪除一個(gè)節點(diǎn)，用圖7 - 4描述如下：





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

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

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





插入的節點(diǎn)可以在表頭、表中或表尾。假定我們按照以學(xué)號為順序建立鏈表，則插入的
節點(diǎn)依次與表中節點(diǎn)相比較，找到插入位置。由于插入的節點(diǎn)可能在鏈表的頭，會(huì )對鏈表的
頭指針造成修改，所以定義插入節點(diǎn)的函數的返回值定義為返回結構體類(lèi)型的指針。節點(diǎn)的
插入函數如下：
struct node *insert(head,pstr,n) /*插入學(xué)號為n、姓名為pstr的節點(diǎn)*/
struct node *head; /*鏈表的頭指針*/
char *pstr;
int n;
{
struct node *p1,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));/* 分配一個(gè)新節點(diǎn)* /
strcpy(p1->str,pstr); /* 寫(xiě)入節點(diǎn)的姓名字串*/
p1->num=n; /* 學(xué)號*/
p2=head;
if(head==NULL) /* 空表*/
{
head=p1; p1->next=NULL;/*新節點(diǎn)插入表頭*/
}
else
{ /*非空表* /
while(n>p2->num&&p2->next!=NULL)
/ *輸入的學(xué)號小于節點(diǎn)的學(xué)號，并且未到表尾* /
{
p3=p2;
p2=p2->next; /* 跟蹤鏈表增長(cháng)*/
}
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. 實(shí)例[例7 - 7 ]
創(chuàng )建包含學(xué)號、姓名節點(diǎn)的單鏈表。其節點(diǎn)數任意個(gè)，表以學(xué)號為序，低學(xué)號的在前，高學(xué)號的在后，以輸入姓名為空作結束。在此鏈表中，要求刪除一個(gè)給定姓名的節點(diǎn)，并插入一個(gè)給定學(xué)號和姓名的節點(diǎn)。
#include "stdlib.h"
#include "malloc. h"
struct node /*節點(diǎn)的數據結構*/
{
int num;
char str[20];
struct node *next;
};
/*******************************************************/
main( )
{
/*函數聲明*/
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表*/
head=creat (head); /*調用函數創(chuàng )建以head 為頭的鏈表*/
print(head);/*調用函數輸出節點(diǎn)*/
printf("\n input inserted num,name:\n");
gets(str); /*輸入學(xué)號*/
n=atoi (str);
gets(str); /*輸入姓名* /
head=insert (head, str, n); /* 將節點(diǎn)插入鏈表*/
print (head)； / *調用函數輸出節點(diǎn)*/
printf("\n input deleted name:\n");
gets(str); /*輸入被刪姓名*/
head=delet(head,str); /* 調用函數刪除節點(diǎn)*/
print (head); /*調用函數輸出節點(diǎn)*/
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;
}

/********** 插入節點(diǎn)**********/
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);
}

/***** 刪除節點(diǎn)*************/
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);
}

/**********鏈表各節點(diǎn)的輸出**********/
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