C语言程序设计常用数据结构

1、第九章常用数据结构【学习目标】本章将介绍在C语言中如何管理内存。学习要点包括如下几点:(1)了解内存组织方式。(2)能区分堆和栈的不同。(3)会使用动态管理内存函数。【学习导航】本章的在整个课程中的位置如图10-1所示。函数的庾用数组的使用分支结构和循环结构数据输入幅出函凝运算符与表达式常用软据类型C语言概述及开发环境搭建图 9-1 本章学习导航9.1结构体前面的课程我们学习了一些简单数据类型（整型、实型、字符型）的定义和应用，还学习了数组（一维、二维）的定义和应用，这些数据类型的特点是：当定义某一特定数据类型,就限定该类型变量的存储特性和取值范围。对简单数据类型来说，既可以定义单个的变量，也

2、可以定义数组。而数组的全部元素都具有相同的数据类型，或者说是相同数据类型的一个集合。在学生成绩管理系统中，记录一个学生会涉及到多个数据，比如学生的姓名、性别、年龄、成绩等等。下面的程序描述了一个姓名叫“罗杰”的学生的基本信息。1#include23intmain()罗杰；/姓名/性别1:男，2:女/年龄/成绩如果有多个学生的信息需要描述呢，那么就需要定义和上面代码中第5行第8行类似的很多变量，这样会出现很多变量声明；另一个问题就是这些声明的变量彼此之间看起来并无直接关联，无法从一个“整体”的角度来描述学生。 所以C语言引入一种能集中不同数据类型于一体的数据类型一结构体类型。 结构体类型的变量可

3、以拥有不同数据类型的成员，是不同数据类型成员的集合。9.1.1结构体类型定义C语言对结构体类型的定义形式：struct结构体名成员项表列;下面的程序的第511行用结构体类型对学生的描述，注意11行后需要以结束。1#include23intmain（）45structstudent45charname20=6charsex=1;7intage=20;8floatscore=85;910return0;1167charname20;/姓名8charsex;/性别1:男，2:女9intage;/年龄10floatscore;11);1213return0;14)9.1.2结构体类型变量的定义有了结构

4、体类型，我们就可以定义结构体类型变量，以对不同变量的各成员进行引用。结构体类型变量的定义与其它类型的变量的定义是一样的,事先自行定义，所以结构体类型变量的定义形式就增加了灵活性,介绍如下：1）先定义结构体类型，再定义结构体类型变量:structstudent）；structstudents1;structstudents2;用此结构体类型，可以定义更多的该结构体类型变量。2）定义结构体类型同时定义结构体类型变量:1structdate23intday;4intmonth;5intyear;6d1,d2;也可以再定义如下变量:structdatad3,d4;用此结构体类型，同样可以定义更多的该结

5、构体类型变量。但由于结构体类型需要针对问题常用的有两种形式，分别charname20;charsex;intage;floatscore;/姓名性别1:男，2:女年龄8910/定义结构体类型变量9.1.3结构体类型变量的引用及初始化员呢？C规定引用的形式为:.比如对9.1.2节中定义的结构体studentsi,访问其成员age可以这样：sl.age#includeintmain()structstudent程序第13行在定义结本体变量s1的同时，给所有成员赋值。第14行单才给s1的age成员赋值，它覆盖了第13行赋的彳1。第16行输出：Jack。第17行输出：22。覆盖了之前的20。9.1.4

6、结构体数组的定义和引用单个的结构体类型变量在解决实际问题时作用不大,现。结构体类型数组的定义形式为：structstudentstu30;学习了怎样定义结构体类型和结构体类型变量,怎样正确地引用该结构体类型变量的成对结构体变量的成员的初始化，参看下面的代码（structInit.c):1011）；1213141516171819charname20;charsex;intage;floatscore;structstudents1s1.age=22;/姓名性别1:男，2:女年龄=Jack,1,20,89.5;printf(%sn,);printf(%dn,s1.age);retu

7、rn0;般是以结构体类型数组的形式出下面通过【课堂案例9-1】来说明结构体数组的用法。【课堂案例9-1】在学生管理系统中，需要计算某组（共3人）学生的平均成绩。【案例目标】结构体的综合使用【案例知识要点】结构体的创建、定义结构体变量、结构体数组1#include2#include34structstudent56charname20;姓名7longno;/学号8floatscore3;/保存3门成绩，依次为c、oc、ios三门课程的成绩9floataverge;/保存平均分10;1112intmain()1314voidinput();/函数声明15voidaver();16voidoutpu

8、t。；1718structstudentstu3;/定义结构体数组19input(stu,3);20aver(stu,3);21output(stu,3);22return0;232425voidinput(structstudentarr,intn)2627inti,j;28chartemp30;29for(i=0;in;i+)3031printf（请输入姓名、学号、c成绩、oc成绩、ios成绩n）;32gets();33gets(temp);34arri.no=atol(temp);35for(j=0;j3;j+)3637gets(temp);38arri.scorej=

9、(float)atof(temp);3940414243voidaver(structstudentarr,intn)44(45inti,j;46for(i=0;in;i+)47(48arri.averge=0;49for(j=0;j3;j+)50(51arri.averge+=arri.scorej;525354arri.averge=arri.averge/3;55565758voidoutput(structstudentarr,intn)59(60inti,j;61printf(n);62printf(%10s%8s%10s%10s%10s%10sn,63姓名,学号,c成绩,oc成绩,

10、ios成绩,”平均分）64for(i=0;in;i+)65(66printf(%10s|%8ld,,arri.no);67for(j=0;j3;j+)68(69printf(%7.2f|,arri.scorej);707172printf(%7.2f,arri.averge);73printf(nn);7475【程序输入】请输入姓名、学号、心成绩,建成绩、i i”成绩TonTon11011101606070708080请输入姓名、学号、心成绩,口。成绩、士”成绩JackJack11021102请输入姓名、学号、c c成绩，加成绩、“自成绩SmithSmith110311037

11、07080809090图10-2averge.c程序的输入【程序说明】第410行定义了结构体student。第1416行分别声明了函数input、aver、output,input函数用于输入，aver函数用于求平均分、output用于输出。第2940行定义了一个循环，用来接收三个学生信息的输入。第4655行使用循环来求每个学生的平均分。其中第49第52行求出每个学生的总分，第54行求出平均分，并保存到结构体student的averge成员中。【程序输出】姓名学号心成绩口心成绩ss成绩平均分TomTom：11011101皿孙70.0070.00；80.0080.00；70.0070.00Jac

12、kJack1 11182118265.00!65.00!75.00!75.00!8585.哂75-0075-00Smith1Smith11103110370.00170.00180.00180.00190.0090.00：图10-3averge.c程序的输出9.1.5结构体指针的定义和引用指针变量非常灵活方便，可以指向任一类型的变量，若定义指针变量指向结构体类型变量，则可以通过指针来引用结构体类型变量。structstudent*s1;定义指针变量s1,指向结构体类型变量。引用形式为：指针变量一成员。下面的代码(structPoint.c)说明如何使用指针变量访问结构体的成员。1#includ

13、e1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numb1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numbstructstudent1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numb(1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numbcharname20;/姓名1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679

14、614f-Numblongno;/学号1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numbfloatscore3;1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numb;1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numb1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numbintmain()1462c-Numbered_b97998f1-2f1b-4065-a

15、3b4-d282b679614f-Numb1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numbstructstudent*stu;1462c-Numbered_b97998f1-2f1b-4065-a3b4-d282b679614f-Numb14stu=malloc(sizeof(structstudent);15scanf(%s,stu-name);16scanf(%ld,&stu-no);17printf(%sn,stu-name);18printf(%ldn,stu-no);return0;【程序说明】第12行定义了结构

16、体类型指针变量stu。第14行，使用结构体类型指针引用结构体变量的成员，需要通过函数malloc()来为指针分配安全的地址。第15行，接收键盘车入给成员name赋值，第16行接收键盘输入给成员no赋值。第1718行，输出结构体成员。2链表数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要30个大小的数组，有时需要50个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。我们希望构造动态的数组，随时可以调整数组

17、的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表。下面介绍最简单的单链表，其结构如图10-4。图10-4单链表结构图单链表有一个头节点head,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地

18、址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。链表节点的数据结构定义：structstudent（intno;floatscore;structstudent*nextStu;前两个成员项组成数据域，后一个成员项nextStu构成指针域，它是一个指向stu类型结构的指针变量。在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成

19、功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。链表的基本操作对链表的主要操作有以下几种：建立链表；结构的查找与输出；插入一个结点；删除一个结点；单链表的创建过程有以下几步：）定义链表的数据结构。）创建一个空表。）利用malloc（）函数向系统申请分配一个节点。）将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾。）判断一下是否有后续节点要接入链表，若有转到3）,否则结束。单链表的输出过程有以下几步：1）找到表头。2）若是非空表，输出节点的值成员，是空表则退出。3）跟踪链表的增长，即找到下一个节点的地址。4）转到2）。下面通过【课堂案例9-2】来

20、说明这些操作。【课堂案例9-2】在学生管理系统中，用单链表实现学生的添加和输出。【案例目标】单链表的运用。【案例知识要点】单链表的创建、单链表节点的插入。【案例程序代码】singleList.c#include#includestructstudentlongno;/学号floatscore;/成绩structstudent*nextStu;intmain()structstudent*creat();/函数声明voidprint();structstudent*head;head=NULL;head=creat(head);print(head);/打印单链表return0;structst

21、udent*creat(structstudent*head)structstudent*s1,*s2;s1=s2=(structstudent*)malloc(sizeof(structstudent);scanf(%d,&s1-no);/输入节点的值s1-nextStu=NULL;/将新节点的指针置为空while(s1-no0)/输入节点的数值大于0if(head=NULL)head=s1;/空表，接入表头elses2-nextStu=s1;/非空表，接到表尾s2=s1;s1=(structstudent*)malloc(sizeof(structstudent);scanf(%d,&s1-no);/输入节点的值returnhead;/返回链表的头指针123456789101112131415161718192021222324252