补充资料结构与自定义类型ppt课件

1、12 回想： 运用数组的益处是可以用一个变量定义逻辑上相关的一批数据，使每个分量具有一样的名字、不同的下标，但有一个限制，即一个数组变量包含的一切成分元素必需为同一类型，例如：int a3。 3学学 号号姓姓 名名性性 别别高考分数高考分数生生 源源010031010031张三张三女女567567北京北京010032010032李四李四女女539539深圳深圳010033010033王五王五男男460460上海上海4 定义构造类型student： int score; / int score; /* *高考分数高考分数* */ / char char * *place; place; / /*

2、 *生源生源* */ / ; ; 5struct datestruct date int year,month,day; int year,month,day; 【例】定义代表日期信息、药品信息的构造类型。【例】定义代表日期信息、药品信息的构造类型。 struct date struct date int year; int year; int month; int month; int day; int day; ; ; 6 struct medicine struct medicine char char * *code;code; char char * *name;name; floa

3、t price; float price; char char * *place;place; struct date validity; struct date validity; ; ;codenamepriceplacevalidityyear month day构造类型构造类型medicinemedicine：7 int score; int score; char char place12;place12; ; ;1 1先定义构造类型，再援用该类型定义的变量先定义构造类型，再援用该类型定义的变量8 2定义构造类型的同时阐明变量place12;place12; xia,ding,li;

4、xia,ding,li;9 2. 2.构造变量的援用构造变量的援用 构造变量通常都以成员的方式加以援用，构造变量成员的标构造变量通常都以成员的方式加以援用，构造变量成员的标志方式为：志方式为：成员运算符成员运算符【例】设有如下阐明：【例】设有如下阐明： struct date struct date int year,month,day; int year,month,day;构造变量名构造变量名. .成员名成员名10 以下语句序列是对药品构造变量以下语句序列是对药品构造变量drug1drug1、drug2drug2进展赋值、输入进展赋值、输入和输出运算：和输出运算： struct medic

5、ine char *code; char *name; float price; char *place; struct date validity; drug1,drug2;11 =“penicillin; drug1.price=6.38; drug1.price=6.38; =“vitamine C =“vitamine C; ; if(drug2.code if(drug2.code“99103x“99103x) ) drug2.price=drug2.price-7.5; drug2.price=drug2.price-7.

6、5; scanf(“%d%d%d scanf(“%d%d%d,&drug1.validity.year,&drug1.validity.year, &drug1.validity.month,&drug1.validity.day); &drug1.validity.month,&drug1.validity.day); puts(); puts(); puts(); puts();123.3.构造变量的初始化构造变量的初始化 【例】构造变量在定义时被赋初值。【例】构造变量在定义时被赋初值。2019,12,31;2

7、019,12,31;139.3.2 9.3.2 构造数组构造数组 1. 1. 构造数组的定义构造数组的定义 float price; float price; char char * *place;place; struct date struct date validity;validity;14 2. 2.构造数组的援用构造数组的援用 构造数组是以下标变量的成员名方式加以援用的。其标志方式构造数组是以下标变量的成员名方式加以援用的。其标志方式为：为：for(i=0;iN;i+)for(i=0;iprice-=200; price-=200; (+py) (+py)stock+=10;sto

8、ck+=10;18501850/ /* *电冰箱降价电冰箱降价200200元元* */ /*洗衣机库存加洗衣机库存加10*/10310322 构造指针作为函数的参数使得构造变量也能像普通变量一样实构造指针作为函数的参数使得构造变量也能像普通变量一样实现现“传地址调用。调用发生时，实参传送给形参的是本身构造的传地址调用。调用发生时，实参传送给形参的是本身构造的存储地址，使方式参数直接指向了真实实参，形参不再另占内存单存储地址，使方式参数直接指向了真实实参，形参不再另占内存单元，从而使函数体中对方式参数所作的改动就是对真实参数所作。元，从而使函数体中对方式参数所作的改动就是对真实参数所作。 3.

9、3.构造指针作为函数的参数构造指针作为函数的参数23 【例】知10名学生的三门单科考试成果，求每一门课程的总平均分。242526运转结果为：运转结果为：2728【例【例1】运转结果为：运转结果为：29【例【例2】运转结果为：运转结果为：30【例【例3】31【例【例4】见实验教程】见实验教程P66-程序改错。程序改错。【例【例5】见实验教程】见实验教程P66-程序填空。程序填空。【例【例6】见实验教程】见实验教程P59-程序填空。程序填空。32 9.4.1 9.4.1 链表概述链表概述 1. 1.什么是链表什么是链表 顺序存储顺序存储将逻辑上相邻的数据分配在物理上相邻的存储单将逻辑上相邻的数据分

10、配在物理上相邻的存储单元中，数据之间的逻辑关系经过存储单元的邻接关系来表达；元中，数据之间的逻辑关系经过存储单元的邻接关系来表达； 链接存储链接存储将逻辑上相邻的数据分配在物理上离散的存储单将逻辑上相邻的数据分配在物理上离散的存储单元中，然后在每一个存储单元中粘贴一张标有相邻者存储地址的标元中，然后在每一个存储单元中粘贴一张标有相邻者存储地址的标签，使数据之间的逻辑关系经过地址的链接关系来表达。签，使数据之间的逻辑关系经过地址的链接关系来表达。33 2.链表实例 以下图表示存放整数11，13，17，19的链表：head1079115312860头结点头结点末结点末结点头指针头指针数据域数据域指

11、针域指针域1079115312860NUL4.2 9.4.2 单链表结点的类型定义单链表结点的类型定义111153数据域：存储数据数据域：存储数据指针域：存储后续结点的地址指针域：存储后续结点的地址35 单链表结点的类型定义： struct struct 构造名构造名 数据成员表列；数据成员表列； struct struct 构造名构造名 * *指针名；指针名； ; ; head1079115312860107911115313128617139019NULL36【例】定义素数链表的结点类型【例】定义素数链表的结点类型struct primestruct prime。

12、素数链表：素数链表：headhead1111131317171919NULLNULL 要求素数链表结点只包含一个数据成员，因此结点类型可要求素数链表结点只包含一个数据成员，因此结点类型可定义为：定义为： struct prime struct prime int data int data； struct prime struct prime * *next; ;next; ;37 【例】定义学生链表的结点类型【例】定义学生链表的结点类型struct studentstruct student。 假设一个学生记录包括学号、姓名、性别和高考成果，那么假设一个学生记录包括学号、姓名、性别和高考成果

13、，那么学生链表的结点类型可定义为：学生链表的结点类型可定义为： struct student struct student long num; long num; char char * *name;name; char sex; char sex; int score; int score; struct student struct student * *next; next; ; ;struct student struct student * *p,p,* *q;q;38 struct student struct student long num; long num; char ch

14、ar * *name;name; char sex; char sex; int score; int score; struct student struct student * *next; next; ; ;010201010201倪桂兰倪桂兰女女568568struct student struct student * *p,p,* *q;q;p-num=010201;p-name=“p-num=010201;p-name=“倪桂兰；倪桂兰；p-sex=p-sex=女女;p-score=568;p-score=568;010202010202刘宁宁刘宁宁女女544544p pq-num

15、=010202;q-name=“q-num=010202;q-name=“刘宁宁；刘宁宁；q-sex=q-sex=女女;q-score=544;q-score=544;q qp-next=q;p-next=q;399.4.3 9.4.3 动态存储分配函数动态存储分配函数 2.calloc 2.calloc函数函数 函数原型：函数原型：void void * *calloc(unsigned n,unsigned size)calloc(unsigned n,unsigned size) 1.malloc 1.malloc函数函数 函数原型：函数原型：void void * *malloc(un

16、signed size)malloc(unsigned size) 函数功能：在内存的动态存储区中分配一块长度为函数功能：在内存的动态存储区中分配一块长度为sizesize字节的字节的延续空间，并前往该存储区域的首地址；假设函数调用失败，前往延续空间，并前往该存储区域的首地址；假设函数调用失败，前往空指针空指针NULLNULL。40 3.free 3.free函数函数 函数原型：函数原型：void free(void void free(void * *p)p) 函数功能：释放当前正被指针函数功能：释放当前正被指针p p所指向的内存区域，将它归所指向的内存区域，将它归还给系统以作它用。还给系统

17、以作它用。41 9.4.4 9.4.4 创建链表创建链表 创建链表从空表开场，循环地将新结点逐一产生出来，并按预定创建链表从空表开场，循环地将新结点逐一产生出来，并按预定的链接关系插入到链表中去的过程。的链接关系插入到链表中去的过程。010201010201倪桂兰倪桂兰女女568568010202010202刘宁宁刘宁宁女女544544010230010230潘俊潘俊男男626626NULLNULLhead42 结点插入通常有两种预定关系：结点插入通常有两种预定关系： “ “栈式构造栈式构造新结点总是从表首插入，使得最先插入到新结点总是从表首插入，使得最先插入到 链表中去的结点被挤压到链尾，成

18、为末结点，而最后插入链表中去的结点被挤压到链尾，成为末结点，而最后插入 的结点成为链表的头结点；的结点成为链表的头结点； “队列式构造新结点总是从表尾插入； 1创建“栈式链表43p 3 设设headhead为链表头指针，为链表头指针，p p为创建动态结点的任务指针，那么：为创建动态结点的任务指针，那么： 建空表：建空表： head headNULLNULL； 创建新结点，创建新结点， p=( p=(结点类型结点类型* *)malloc()malloc(结点长度结点长度) ) 并对结点的数据域赋值：并对结点的数据域赋值： 新结点进栈：新结点进栈： p-next=head;head=p; p-ne

19、xt=head;head=p; 反复、步骤假设干次；反复、步骤假设干次；head NULLheadp 3NULLheadp 3 NULLhead 44【例】用上述步骤往链表中插入两个结点：【例】用上述步骤往链表中插入两个结点：head p 3headp 3 NULL 3 NULLheadp 5 5 3 NULLheadp45 【例】编写程序，建立一个存储字符及其ASCII码的链表，规定ASCII码的范围为m，n32mnnext=plast-next=p； 3 headlast 5p 3 head 5plast last last指针后移至末结点：指针后移至末结点：lastlastlast-ne

20、xtlast-next；52 反复、步骤假设干次，如下所示；反复、步骤假设干次，如下所示；p 7 开辟后续新结点：开辟后续新结点：p=(p=(结点类型结点类型* *) malloc() malloc(结点长度结点长度) )； 新结点插入表尾：新结点插入表尾：last-next=plast-next=p； 3 head 5plastp753 终止链表的延伸：终止链表的延伸：last-nextlast-nextNULLNULL； last last指针后移至末结点：指针后移至末结点：lastlastlast-nextlast-next； 3 head 5lastp7lasthead357NUlll

21、ast549.4.5 9.4.5 结点的删除与插入结点的删除与插入 1. 1.删除结点删除结点 删除结点删除结点解除该结点的链接关系，使之与链表脱钩，再调用解除该结点的链接关系，使之与链表脱钩，再调用freefree函数收回它的存储空间。函数收回它的存储空间。 1 1被删结点被删结点p p为链表首结点为链表首结点 p=head; / p=head; /* *使使p p指针指向首结点指针指向首结点* */ / head=head-next; / head=head-next; /* *头指针后移一个结点头指针后移一个结点* */ / free(p); / free(p); /* *收回首结点的存

22、储空间收回首结点的存储空间* */ /55删除学生链表的首结点删除学生链表的首结点1001倪兰女5681002王 田女5371003刘宁女5441004应 浩男4991005潘 俊男626NULLheadpheadheadheadnextfree(p)56 2被删结点为链表的中间结点或末结点1113171997NULLheadprep prenext=pnext; 借助两个任务指针借助两个任务指针p p和和prepre，寻觅被删结点的过程如下：，寻觅被删结点的过程如下： p p指针从头至尾对链表的结点逐一扫描，而指针从头至尾对链表的结点逐一扫描，而prepre指针总是跟踪指针总是跟踪p p当当

23、前所指结点的前驱结点，与前所指结点的前驱结点，与p p指针坚持同步挪动，指针坚持同步挪动，p p指针一旦找到了被指针一旦找到了被删结点，执行下面的语句即可实现删除：删结点，执行下面的语句即可实现删除：free(p);free(p);57 【例】结点删除的例子见书【例】结点删除的例子见书P171P171页。页。 【例】创建偶数【例】创建偶数2 21010之间链表，并删除指定偶数，之间链表，并删除指定偶数，要求输出创建的链表以及删除后的结果。要求输出创建的链表以及删除后的结果。58 2.结点的插入+=?&NULLheadpinsert* 【例】将以下图中的【例】将以下图中的insertinsert

24、指针指向的结点插入到头指针为指针指向的结点插入到头指针为headhead的链表中，且指针的链表中，且指针p p曾经指向插入点。曾经指向插入点。59 1在知结点之后插入+=?&NULLheadpinsert*p pnext=insert;next=insert;insertinsertnext=pnext=pnext;next;60 2在知结点之前插入+=?&NULLheadinsert*insertinsertnext=p;next=p;preppreprenext=insert;next=insert;思索：上述两个拉链语句的次序能颠倒吗？思索：上述两个拉链语句的次序能颠倒吗？【例】结点插入

25、的例子见书【例】结点插入的例子见书P173P173页例页例9.119.11。61 共用体共用体同一块内存区域在不同时辰存储不同类型的数据，同一块内存区域在不同时辰存储不同类型的数据，是一种内存覆盖技术。共用体能使多个类型不同的变量共享一块内是一种内存覆盖技术。共用体能使多个类型不同的变量共享一块内存区域，这些变量在不同的时间去占用这一片内存。存区域，这些变量在不同的时间去占用这一片内存。 9.5.1 9.5.1 共用体类型的定义共用体类型的定义 方式：方式： union union 共用体名共用体名 成员表列成员表列 ; ;关键字，代表共用体类型关键字，代表共用体类型有时也会省略有时也会省略6

26、2 【例】 union student long num; char name10; int score; zhang , lin; 这种类型使长度为这种类型使长度为1010个字节的内存区域最长成员所占的字节数个字节的内存区域最长成员所占的字节数既能存储既能存储longlong型数据，又能存储字符串和型数据，又能存储字符串和intint型数据，并在定义类型型数据，并在定义类型的同时也定义了两个的同时也定义了两个union studentunion student类型的变量类型的变量zhangzhang和和linlin。 【思索题】【思索题】zhangzhang和和linlin所占据的存储字节均

27、为多少？假设将上所占据的存储字节均为多少？假设将上述类型改为述类型改为struct studentstruct student，那么变量，那么变量zhangzhang和和linlin又占据多少字节？又占据多少字节？63 9.5.2 9.5.2 共用体变量的援用共用体变量的援用 方式：方式： 共用体变量名共用体变量名. .成员名成员名 【例】【例】=“=“wangfen; ; lin.score=83; lin.score=83; 【例】 union student long num; char name10; int score; zhan

28、g , lin;64 1 1任何时辰，只需一个成员的值被存储：任何时辰，只需一个成员的值被存储：lin.num=990011; lin.score=83; lin.num=990011; lin.score=83; 2 2共用体变量和各成员具有一样的存储地址，即共用体变量和各成员具有一样的存储地址，即&zhang&zhang与与&zhang.num&zhang.num、&&、&zhang.score&zhang.score为同一个地址值；为同一个地址值； 3 3不能对共用体变量以整体方式援用，下面语句均错：不能对共用体变量以整体方式援用，下面语句均错：s

29、canf(“%ld%s%dscanf(“%ld%s%d,&lin); zhang=lin;,&lin); zhang=lin; 共用体变量的一切成员共享一段内存，长度为最长成员的字节数，运用时要留意以下一些问题：65 方式： enum 枚举名 枚举值表列 ;enumenum为关键字，代表枚举类型为关键字，代表枚举类型花括号中列出的枚举值均为常花括号中列出的枚举值均为常量标识符，代表具有该枚举类量标识符，代表具有该枚举类型的变量可以取的全部值。型的变量可以取的全部值。66 【例】【例】enum weekday enum weekday Sunday,Monday,Tueday,Wedday,Thrday,Friday,Satday; Sunday,Monday,Tueday,Wedday,Thrday,Friday,Satday; 【例】【