第07章C++结构体与链表

数组

。

第七章结构体与链表

7．1

结构体类型的定义、结构体变量的声明及初始化、结构体变量的访问方式

structdate //结构类型"日期"的定义{

int

year;

int

month;

int

day;};voidmain(){ dated={2000,1,1}; //结构体变量的声明及初始化 cout<<d.year<<"年"; //结构体变量的访问方式 cout<<d.month<<"月"; cout<<d.day<<"日"<<endl;}说明2：若在函数外定义结构体类型，则该结构体类型为全局类型。说明1：一般不单独对结构体变量名进行操作，除非同类型结构体变量相互间的赋值；或者结构体变量作为函数的参数（下一节介绍）。voidmain(){ dated1={2000,1,1},d2;

d2=d1;//结构体变量间的赋值 cout<<"年："<<d2.year; cout<<"\t月："<<d2.month; cout<<"\t日："<<d2.day;}

说明3：结构体变量与简单变量一样，一旦声明，系统将为之分配存储空间，其大小是其中所有成员变量所占空间之和。因此，每个结构体变量也都有自己的地址。voidmain(){ date1d1={2000,1,1},d2; cout<<"结构体变量d1的大小是："<<sizeof(d1)<<endl; cout<<"结构体变量d2的大小是："<<sizeof(d2)<<endl; cout<<"结构体变量d1的地址是："<<&d1<<endl; cout<<"结构体变量d2的地址是："<<&d2<<endl;}7．2

结构体类型的嵌套

structdate //结构类型"日期"的定义{

int

year;

int

month;

int

day;};structstudent //结构类型"学生信息"的定义{

charno[6];

charname[10];

chargender;

date

birthday; char dpt[20]; int score;};students={"091001","李四",'m',{2000,1,1},"computer",92};//结构体变量的初始化voidmain()//结构体（嵌套）变量的访问方式{ cout<<"学号："<<s.no; cout<<"\t姓名："<<; cout<<"\t性别："<<s.gender; cout<<"\t出生年月："<<s.birthday.year<<","; cout<<s.birthday.month<<","<<s.birthday.day; cout<<"\t所在系："<<s.dpt; cout<<"\t成绩："<<s.score; cout<<endl;} 说明：结构体中的成员可以是另一个结构体的变量，但后者的类型定义必须在先。7．3

结构体数组及其用法voidmain()//结构体数组的访问方式示例{ students[3]; for(inti=0;i<3;i++){ cout<<"请输入学号\t姓名\t性别\t出生年月日\t所在系\t成绩"; cin>>s[i].no>>s[i].name>>s[i].gender； cin>>s[i].birthday.year>>s[i].birthday.month>>s[i].birthday.day; cin>>s[i].dpt>>s[i].score; }cout<<"学号\t姓名\t出生年月\n";for(inti=0;i<3;i++){cout<<student[i].no<<'\t'<<student[i].name<<'\t';cout<<student[i].birthday.year<<'-'<<student[i].birthday.month<<'-'<<student[i].birthday.day; cout<<endl;}}（程序演示见.txt）7．4

结构体指针及其用法structdate {

int

year;

int

month;

int

day;};structstudnet

{

charno[6];

charname[10];

chargender;

date

birthday; char dpt[20]; int score;};students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s;voidmain()//结构体指针的访问方式{ students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s; cout<<"学号\t姓名\t性别\t出生年月日\t所在系\t成绩"<<endl; cout<<p->no<<"\t";//等价与(*p).no cout<<p->name<<"\t";//等价与(*p).name cout<<p->gender<<"\t";//等价与(*p).gender cout<<p->birthday.year<<","<<p->birthday.month<<","<<p->birthday.day;

//等价与(*p).birthday.day等等 cout<<"\t"<<p->dpt; cout<<"\t"<<p->score<<endl;} （程序演示见.txt）p7．5

结构体作为函数参数7.5.1 结构体变量为参数——值传递voidmain(){ voidmodifyStdScore(student);

students={"091001","李四",'m',{2000,1,1},"computer",92};modifyStdScore(s); cout<<"该学生现在的成绩是："<<s.score<<endl;} voidmodifyStdScore(studentstd){ std.score=100;}参数传递的结果：

std=s运行结果

该学生现在的成绩是：927.5.2 结构体引用为参数——引用传递voidmain(){ voidmodifyStdScore(student&);

students={"091001","李四",'m',{2000,1,1},"computer",92};modifyStdScore(s); cout<<"该学生现在的成绩是："<<s.score<<endl;} voidmodifyStdScore(student&std){ std.score=100;}参数传递的结果：

&std=s运行结果

该学生现在的成绩是：1007.5.3 结构体指针为参数——地址传递voidmain(){ voidmodifyStdScore(student*);

students={"091001","李四",'m',{2000,1,1},"computer",92},*p=&s;modifyStdScore(p);//等价与&s cout<<"该学生现在的成绩是："<<s.score<<endl;} voidmodifyStdScore(student*std){

std->score=100;}参数传递的结果：

std=p即std=&s运行结果

该学生现在的成绩是：100voidmain(){

studentsetStudent();

students;

s=setStudent(); cout<<"学号："<<s.no<<"\n姓名："<<<<"\n性别："<<s.gender; cout<<"\n出生年月："; cout<<s.birthday.year<<","<<s.birthday.month<<","<<s.birthday.day; cout<<"\n所在系："<<s.dpt<<"\n成绩："<<s.score<<endl;}student setStudent(){ studentstd={"091001","李四","男",{2000,1,1},"计算机",92}; returnstd;}返回值传递：

s=std7．6

结构体作为函数返回值7.6.1 结构体变量为返回值7.6.2 结构体指针为返回值structdate//日期结构类型：由年、月、日3项组成{ intyear; intmonth; intday;};structstudent//学生信息结构类型：由姓名、生日及成绩3项组成{ charname[10]; datebirthday; intscore;};voidmain(){ student*maxScoreStudent(student*,int); students[3],*p;for(inti=0;i<3;i++){cout<<"输入姓名:";cin>>s[i].name; cout<<"输入生日的年月日:";cin>>s[i].birthday.year>>s[i].birthday.month>>s[i].birthday.day; cout<<"输入成绩:";cin>>s[i].score;}

p=maxScoreStudent(s,3); cout<<"成绩最好的学生是："<<endl;cout<<p->name<<","<<p->score<<","<<p->birthday.year<<",";cout<<p->birthday.month<<","<<p->birthday.day<<endl;}}

（程序演示见.txt）student*maxScoreStudent(student*st,intn){ studentsmax=*st,*pmax=st; for(inti=1;i<3;i++) if(st[i].score>smax.score) { smax=st[i]; pmax=st+i; } returnpmax;}返回值传递：

p=pmax7．7

结构体的应用——链表7.7.1 利用new、delete动态创建结构体变量voidmain()//动态创建结构体变量并访问之{

student*p=newstudent;//该结构体变量没有变量名，只有地址! cout<<"请输入：学号姓名性别出生年月日所在系成绩"<<endl; cin>>p->no>>p->name>>p->gender; cin>>p->birthday.year>>p->birthday.month>>p->birthday.day; cin>>p->dpt>>p->score; cout<<"该学生的信息是："endl; cout<<"学号\t姓名\t性别\t出生年月日\t所在系\t成绩"<<endl; cout<<p->no<<"\t"<<p->name<<"\t"<<p->gender; cout<<"\t"<<p->birthday.year<<","<<p->birthday.month<<","<<p->birthday.day; cout<<"\t"<<p->dpt<<"\t"<<p->score<<endl;} 每当程序需要处理的结构体变量，类型相同、数目众多且不可预知时，则可以利用动态创建的方式来实现——需要时创建之！然而，大量的指针却不便于编程。有一种叫“链表”的数据结构可以解决这个问题——将一个动态创建的结构体变量的地址保存到另一个相同类型的结构体变量中——每个结构体变量都如此！structFigure//结构类型"人物"的定义{

char

no[6];

char

name[10]; int age;

Figure*

link;};例如，一个由结构体Figure的变量组成的存放人物信息的链表如下所示：头指针7.7.2 链表的概念链表其实是一种“由结构变量自己来管理自己”的数据结构——每一个结构变量内部都保存着另一个结构变量的地址！而你只需要管好“头指针”即可！显然，链表是一种完全由用户自行创建并管理、处理的数据结构：链表中的结构变量的类型定义、每个结构变量的动态创建、结构变量之间的链接。注意：为便于链表的处理，通常将链表最后一个结点中的后继指针赋值为NULL！头指针链表的建立过程：NULL7.7.3 链表的基本操作（由用户定义的函数实现）（1）链表的遍历——output(L)或Traversal(L):输出链表L中每个结点的数据（2）链表的长度——Length(L):返回链表L中的结点个数（3）链表的搜索——search(L,x):若链表L中存在x结点则返回其指针;否则返回NULL（4）链表的删除——delete(L,x):删除链表L中第一个值为x的结点（5）链表的插入——insert(L,i,x):在链表L中的第i个结点前插入新结点x（6）链表的创建——creat():建立一个链表并返回其头结点指针（7）链表的撤销——destroy(L):撤销链表L中的全部结点假定，链表L的类型定义如下：structnode{ ...........//其他数据成员 node*

next;};node*L;//头指针声明L程序示例1：链表的基本操作之一(链表的创建、打印)struct

stu{ char name[20];

//注意：结构体中的字符串成员不便声明为“char*name;” stu *next;};voidmain(){ stu

*head,

*tail,

*p;

//头结点指针haed、尾结点指针tail、工作指针p int

i; head

=

tail

=

NULL; for(

i

=

1;

i

<=

3;

i++

){ //建立一个包含3个节点的链表 p

=

new

stu;

//让p指向一个新创建的结点 cout<<"请输入姓名："<<endl; cin>>p->name;

//若name为字符指针，则不能这样赋值! p->next

=

NULL;

//让p的后继为空（即p将作为链表中的最后一个结点） if(

head

==

NULL)

//若头指针head为空，则让head指向新创建的结点

head

=

p; else

//若头指针不空，则让p所指结点为尾结点

tail->next

=

p; tail

=

p;

//让tail指向尾结点 }

cout<<"链表中的结点是："<<endl; p

=

head;

//使指针p指向链表的头结点

while(

p

!=

NULL

){ //若p不空(即p所指结点存在),则打印该节点中数据

cout<<p->name<<","; p

=

p->next;

//注意此句p的作用：使p指向下一个结点！ } cout<<endl;}值得注意的是：链表的头指针（保存着表头结点的地址）是用户掌控及访问链表的唯一信息——一旦丢失，无处复得！因此，在链表的操作过程中，通常需要一些工作指针（如指针p、tail等）。而头指针（如head）在建表后，一般将不再被改变——以免丢失头结点的地址——丢失链表!!程序示例2：链表的基本操作之二(链表的创建、打印分别由函数实现)#include"stdafx.h"#include"iostream"usingnamespacestd;structstu{ char name[20]; int age; stu *next;};voidmain()//主函数{ stu*create(int); //声明“创建链表”的函数create原型 voidoutput(stu*); //声明“打印链表”的函数output原型 stu*head; //声明链表的头指针 head=create(5); //调用create函数来创建链表(长度为5) cout<<"链表中的信息是:"<<endl; output(head); //调用output函数来打印链表}

stu*create(intn)//创建长度为n的链表：返回链表的头指针{ stu*head,*tail,*p;//head指向表头、tail指向表尾、 //p指向动态申请的新结点。 inti; for(i=0;i<n;i++){ p=newstu; cout<<"inputNumberandAge"<<endl; cin>>p->name>>p->age;

p->next=NULL;//使pb所指结点没有后继——尾结点 if(i==0)//等价与“head==NULL” head=p; elsetail->next=p; tail=p; } returnhead;//返回链表头指针的值（表头结点的地址）}voidoutput(stu*head)//打印链表（头指针为head）{ stu*p; //声明工作指针p p=head; //开始时，让p指向链表头结点 while(p!=NULL) { cout<<"姓名是:"<<p->name<<",年龄是"<<p->age<<endl; p=p->next;//注意此句的作用——指向链表中的下一个结点!! }}（程序演示见.txt）说明：“链表打印”函数output(head)也叫做“链表遍历”函数showList(head)。（请参见《易学C++》P.101）让“打印函数”output()输出的链表结果更直观、形象：voidoutput(stu*head)//2.打印链表{ stu*p;

cout<<"head"; p=head; while(p!=NULL) { cout<<"→（"<<p->num<<"、"<<p->name<<"、"<<p->score<<"）"; p=p->next; } cout<<endl;}

程序示例3：链表创建函数的另一种算法、打印函数的递归算法#include"stdafx.h"#include"iostream"usingnamespacestd;structstu{ char name[20]; int age; stu *next;};voidmain()//主函数{ stu*create(int); //声明“创建链表”的函数create原型 voidoutput(stu*); //声明“打印链表”的函数output原型 stu*head; //声明链表的头指针 head=create(3); //调用create函数来创建链表(长度为5) cout<<"链表中的信息是:"<<endl; output(head); //调用output函数来打印链表}

stu*create(intn)//（逆向）创建链表：返回链表的头指针{ node*head=NULL,*p; inti; for(i=0;i<n;i++) { p=newnode; cout<<"inputNmaeandAge"<<endl; cin>>p->name>>p->age; p->next=head; head=p; } returnhead;}voidoutput1(stu*head)//递归算法{ if(head!=NULL) { cout<<"姓名是:"<<head->name<<",年龄是"<<head->age<<endl;

output1(head->next); }}程序示例4：求链表的长度（自行实现）程序示例5：链表的查询（参见讲义P.104）程序示例6：链表的删除（参见讲义P.105）程序示例7：链表的插入（参见讲义P.104）关于“链表的基本操作函数”的一些说明：（1）由于结点类型的不同(比如，结点类型为figure、node、student等)，其链表的基本操作函数的具体实现就会不同！（2）在一般教材中，每种链表的“基本操作函数”通常只定义有6、7个(比如，creat()、output()、insert()、delete()、search()、length()、DestroyList()

等）。而在实际应用中，则可根据实际需要来定义（比如有，获取第i个结点元素getElem(L，i)、修改第i个结点元素putElem(L，i，x)、两个链表的合并merger(La，Lb)、链表的初始化init(L)等等）。a0a1an-1

head…a0a1an-1

head…通常在链表的第一结点之前增设一个称为“头结点”的结点——也叫做“哨兵结点”，其数据域一般不存放任何数据。此举仅出于简化程序设计的考虑。关于链表结构的一个约定head空链表的情形：“哨兵(Sentinel)”结点程序示例8：带哨兵链表的初始化函数、插入函数、打印函数structnode{ char name[20]; int age; node *next;};voidmain(){ boolinsert(node*,int,node*); //链表的插入函数 voidoutput(node*); //链表的打印函数 node*init(); //链表的初始化函数 node*head=init(),*p;//初始化表头指针head（指向带哨兵的空链表） intn; cout<<"请输入链表的长度:"<<endl; cin>>n; for(inti=1;i<=n;i++)//建立长度为n的链表head（功能相当于函数create） { p=newnode; cout<<"请输入链表中的第"<<i<<"个数据（姓名、年龄）:"<<endl; cin>>p->name>>p->age; insert(head,i,p); //在链表head中的第i个结点前插入新结点p } output(head);}

voidoutput(node*head)

//链表的输出{ node*p=head->next;

//让p指向第一个元素结点a1 while(p!=NULL) { cout<<"姓名是:"<<p->name<<",年龄是"<<p->age<<endl; p=p->next; }}node*init()//链表的初始化：创建一个空表（带哨兵结点）{ node*head=newnode; //创建哨兵结点 head->next=NULL; returnhead;}

boolinsert(node*head,inti,node*newnode){//在链表head中的第i(1~n+1)个结点前插入新结点newnode node*p=head; intn=0; while(p!=NULL&&n<i-1)//定位第i-1个结点 { p=p->next; n++; }

if(p!=NULL&&n==i-1)

//等价与if(i<=n+1&&i>=1) {//将指针newnode所指结点插入到p所指结点的后边 newnode->next=p->next; p->next=newnode; return1; } else //i>表长+1或i<1——插入位置不存在 return0;}程序示例9：带哨兵结点链表的删除函数（课堂讨论） delete(head,no) //删除链表head中学号为no的结点及 delete(head,i) //删除链表head中第i个结点注意： 为便于日后《数据结构》的学习，从现在开始，凡是有关链表的程序设计，建议使用带哨兵结点的链表结构！ 除特别说明外，以后的链表均指带哨兵结点。delete(head,no)//删除链表head中学号为no的结点voiddelete(

stu*head,

intno

)

//删除链表中学号等于no的节点。

{ stu*p=head->next,q=head; while(p!=NULL

&&

p->num!=no

){ q=p; p=p->next; } if(p==NULL){ cout<<"不存在学号为"<<no<<"的学生\n"; return; } else{ q->next=p->next; deletep; }}

delete(head,i) //删除链表head中第i个结点voiddelete(stu*head,

inti)//删除链表head中第i个结点(i的范围为：1~n){ stu*

p

=

head,q; intn=0; while((p->next!=

NULL)&&(n<i-1)) {

n++; p=p->next; } if((p->next!=

NULL)&&(n==i-1)

) { q=

p->next;

p->next

=

p->next->next; deleteq; } else

cout<<"不存在学号为"<<no<<"的学生\n";}程序示例10： 建立一个链表，每个节点包括：学号、姓名、成绩；编程：测试该链表的各基本操作函数。structstu{ intnum; charname[10]; intscore; structstu*next;};voidmain(

)

//主函数:用于调试各函数{ stu*

create();

//create函数：创建链表 stu*

search(stu*,int);//search函数：搜索链表中学号为no的结点 void

output(stu*);

//output函数：遍历打印链表 void

delete(stu*,int);

//delete函数：删除学号为no的结点 stu*

locate(stu*,int);//locate函数：搜索链表中第i个结点 stu*

prior(stu*,int);

//prior函数：搜索链表中学号为no的前一个结点 int

length(stu*);

//length函数：求链表的长度 stu

*L,

*p; int

no,i; char

choice;

L=

create(); //调用creat函数创建链表并将头指针返回给指针L cout<<"链表中的信息是:\n";

output(L); //调用output函数打印链表L程序示例10： 建立一个链表，每个节点包括：学号、姓名、成绩；编程：测试该链表的各基本操作函数。

do{

cout<<"\n请输入你要找的学号：";

cin>>no; if(

p

=

search(L,no)

)

//调用search函数搜索链表L中学号为no的结点 cout<<"-->（"<<p->num<<","<<p->name<<","<<p->score<<"）\n"; else cout<<"学号为"<<no<<"的学生不存在！\n"; cout<<"\n你要找几号的前一位学生？";

cin>>no; if(

p

=

prior(L,no)

) //调用prior函数搜索链表L中学号为no的前一个结点 cout<<no<<"号的前一个学生是:（"<<p->name<<","<<p->score<<"）\n"; else cout<<no<<"号的前一个学生不存在！\n"; cout<<"你想删除的学号是：\t";

cin>>no;

delete(L,

no

);

//调用delete函数删除链表L中学号为no的节点 cout<<"\n删除学号"<<no<<"后，链表中的信息是:\n"; cout<<"当前链表的长度是："<<length(L)<<endl;

//调用函数length获取链表L的长度 cout<<"当前链表中的数据有："<<endl;

output(L); cout<<"你想找链表中第几个结点？\t";

cin>>i; if(

p

=

locate(L,i)

)

//调用locate函数搜索链表L中第i个结点 cout<<"\n该结点是：("<<p->num<<","<<p->name<<","<<p->score<<")\n"; else cout<<"第"<<no<<"个结点不存在！\n"; cout<<"\n您还想继续吗？(

Y

/

N

)";

cin>>choice;

}while(

choice

==

'Y'

||

choice

==

'y');

cout<<"谢谢您的使用！******再见！\n";}

//其中各基本操作函数的实现及其测试程序请见.txt课堂练习：假设链表的结点类型定义为：structnode{ char name[20]; int num; node *next;};1、编写链表的“创建”函数ordList_create(head)——输入若干结点数据并按学号递增序存入链表head中——创建一个有序链表L。2、编写链表的“合并”函数union(La，Lb)——将存在于线性表

LB

中而不存在于线性表LA中的学号并入到线性表LA中去课堂练习1分析：链表的“创建”函数or