11 结构.ppt

第1页：第十一讲结构封面

本页为第十一讲 结构章节封面，本讲讲解结构类型的定义、结构数组、结构指针与链表的建立及插入。

第2页：跳马问题引出结构

例：跳马。依下图将每一步跳马之后的位置 (x, y) 放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。

结构的概念与应用。

第3页：引入结构数据类型

依上图有 7 个结点：

(x1,y1) (x2,y2) …… (x6,y6) (x7,y7)

为了表示这种既有数据又有指针的情况，引入结构这种数据类型。

第4页：结构的定义格式

结构——是一种构造类型的数据类型。结构是数目固定、类型不同的若干变量的有序集合。结构与数组的区别在于结构内允许有不同类型的数据。

结构的定义，格式如下：

struct <结构名> { <成员说明> }

第5页：跳马棋局的结构定义与跳步表

例如跳马棋局可如下定义：

struct TM { int x,y; struct TM *next}

下面的表是马的跳步方案，从左下角跳到右上角：

第6页：链表的示意图

下面是形成链表的一个参考程序（分三页）。图中 head 指向 n1，n1 的 next 指向 n2，依次链接，n7 的 next 为 NULL（空地址）。

• n1 (0,0)，地址为 &n1
• n4 (4,4)，地址为 &n4
• n7 (8,4)，next 为 NULL

第7页：结构1.c的定义部分

//结构1.c #include <stdio.h>#define null 0struct TM{ int x,y; struct TM *next;}; void main(){ int i; struct TM n1,n2,n3,n4,n5,n6,n7,*head,*p;

第8页：结构1.c的赋值与链接

//分别对TM结构n1~n7中的x,y赋值 n1.x=0; n1.y=0; n2.x=1; n2.y=2; n3.x=2; n3.y=4; n4.x=4; n4.y=4; n5.x=6; n5.y=4; n6.x=7; n6.y=2; n7.x=8; n7.y=4;head=&n1;n1.next=&n2; n2.next=&n3; n3.next=&n4; n4.next=&n5; n5.next=&n6; n6.next=&n7;n7.next=null;

第9页：结构1.c的输出循环

p=head;i=1;do{ printf("结点%d: x=%d, y=%d\n",i,p->x,p->y); p=p->next; i=i+1;} while(p!=null);} 
第10页：结构数组的定义
用结构数组，利用键盘输入结点中的数据。重点看：
scanf("%d",&a); n[i].x=a;
结构数组——数组中的元素为结构类型的数据，如 n[8]。
//结构2.c #include <stdio.h>#define null 0struct TM{ int x,y; struct TM *next;};
第11页：结构2.c的输入循环
void main(){ int i,a,b; struct TM n[8],*head,*p; for(i=1;i<=7;i=i+1) { printf("输入n[%d]的x\n",i); scanf("%d",&a); n[i].x=a; printf("输入n[%d]的y\n",i); scanf("%d",&b); n[i].y=b; } 
第12页：结构2.c的链表输出
head=&n[1];for(i=1;i<=6;i=i+1){ n[i].next=&n[i+1]; }n[7].next=null;p=head;i=1;do{ printf("结点%d: x=%d, y=%d\n",i,p->x,p->y); p=p->next; i=i+1;} while(p!=null);} 
第13页：结构3.c的改写说明
下面的程序与上面的程序区别仅在：
scanf("%d",&(n[i].x));
去替换
scanf("%d",&a); n[i].x=a;
//结构3.c #include <stdio.h>#define null 0struct TM{ int x,y; struct TM *next;};
第14页：结构3.c的输入循环
void main(){ int i,a,b; struct TM n[8],*head,*p; for(i=1;i<=7;i=i+1) { printf("输入n[%d]的x\n",i); scanf("%d",&(n[i].x)); printf("输入n[%d]的y\n",i); scanf("%d",&(n[i].y)); } 
第15页：结构3.c的另一种访问写法
head=&n[1];for(i=1;i<=6;i=i+1){ n[i].next=&n[i+1]; }n[7].next=null;p=head;i=1;do{ printf("结点%d: x=%d, y=%d\n",i,(*p).x,(*p).y); p=(*p).next; i=i+1;} while(p!=null);} 
第16页：求职登记表与ST结构
任务：我们要作一张登记表，登记排队求职信息，包括：姓名、年龄、性别、电话四个参数。希望便于管理，即可以插入和删除，这时可用队列，采用结构类型变量。
struct ST { char name[20]; int age; char sex; long num; struct ST *next;}; 
第17页：结构函数与内存分配
结构的成员可以是指针，意味着这种结构指针可以指向结构变量。结构变量和指向结构变量的指针可以作为函数的参数与返回值。用结构变量作函数返回值的函数称之为结构函数，struct ST *create(void) 就是结构函数。
为了了解结构变量成员的地址情况，我们给出了程序“结构5.c”，在这个程序中我们重点看：
#include <malloc.h> 这是预编译命令，为了分配结构变量的内存地址用的
#define null 0 这是定义空指针变量常量，null 代表 0
#define LEN sizeof(struct ST) 定义常量 LEN，表示结构 ST 中的变量的全部单元的长度，分配内存空间时需要知道这个长度信息
第18页：结构5.c的阅读要点
继续“结构5.c”的阅读要点：
结构 ST 的定义
函数 create 的定义
给结构指针 p 分配内存空间：p=(struct ST *) malloc (LEN);
查看指针 p 所在的地址：printf("指针p所在的地址&p=%X\n",&p);
查看指针 p 所指向的地址：printf("指针p所指向的地址p=%X\n\n",p);
输入姓名，查看姓名所在的地址：scanf("%s",&((*p).name));
输入年龄，查看年龄数据所在的地址：scanf("%d",&((*p).age));
printf("年龄数据所在地址%X\n\n",&((*p).age));
第19页：结构5.c的定义部分
//结构5.c（分四页） #include <stdio.h>#include <malloc.h>#define null 0#define LEN sizeof(struct ST)struct ST{ char name[20]; int age; char sex; long num; struct ST *next;}; struct ST *head,*p,*q; 
第20页：结构5.c的create函数前段
void create(void){ int n=0; head=null; p=(struct ST *) malloc(LEN); printf("指针p所在地址&p=%X\n",&p); printf("指针p所指向的地址p=%X\n\n",p); q=p; printf("指针q所在地址&q=%X\n",&q); printf("指针q所指向的地址q=%X\n\n",q);
第21页：结构5.c的输入与地址查看
printf("输入第%d个结点的数据\n",n+1); printf("依次为name,age,sex,num\n"); printf("输入姓名数据%d\n",n+1); scanf("%s",&((*p).name)); printf("姓名数据所在地址%X\n\n",&((*p).name)); printf("输入年龄数据%d\n",n+1); scanf("%d",&((*p).age)); printf("年龄数据所在地址%X\n\n",&((*p).age)); printf("输入性别数据%d\n",n+1); scanf("%s",&((*p).sex)); printf("性别数据所在地址%X\n\n",&((*p).sex));
第22页：结构5.c的输出与主函数
printf("输入电话号码数据%d\n",n+1);scanf("%ld",&((*p).num));printf("电话号码所在地址%X\n\n",&((*p).num)); printf("输出姓名%s\n",p->name);printf("输出年龄%d\n",p->age);printf("输出性别%c\n",p->sex);printf("输出电话号码%ld\n",p->num);} void main(){ create();} 
第23页：结构函数的声明形式
struct ST * create(void)
这就是结构函数的声明形式：函数名 create，无形参，返回值为指向 ST 结构的指针。
第24页：结构6.c的总说明
下面给出用结构数组（动态分配）建立求职登记链表的完整参考程序 结构6.c，该程序由 create 与 print 两个函数构成，读者可对照前面各页的要点阅读。
第25页：结构6.c的定义部分
//结构6.c（分四页） #include <stdio.h>#include <malloc.h>#define null 0#define LEN sizeof(struct ST)struct ST{ char name[20]; int age; char sex; long num; struct ST *next;}; struct ST *head;void create(void){ struct ST *p,*q; int n=0; char tmpStr[20]; head=null; p = null; q = null; 
第26页：结构6.c的输入循环
do{ n=n+1; printf("输入第%d个结点的数据\n",n); printf("输入姓名数据%d\n",n); scanf("%s",tmpStr); if (strcmp(tmpStr,".")==0) break; p=(struct ST *) malloc(LEN); if (p == null) { printf("Insufficient memory available\n" ); break; }
第27页：结构6.c的链接处理
strcpy((*p).name,tmpStr);printf("输入年龄数据%d\n",n); scanf("%d",&((*p).age));printf("输入性别数据%d\n",n); scanf("%s",&((*p).sex));printf("输入电话号码数据%d\n",n); scanf("%ld",&((*p).num));if(n==1) head=p;else (*q).next=p;q=p;}while(1);if (q!=null) q->next = null;}
第28页：结构6.c的输出与主函数
void print(){ int k=0; struct ST * r; r=head; while(r != null) { k=k+1; printf("输出排队求职者信息%d:%s,%d,%c,%ld\n", k,r->name,r->age,r->sex,r->num); r=r->next; } } void main(){ create(); print();}
第29页：字符串处理函数strcmp
字符串处理函数简介
1、strcmp(s1,s2)，例：
printf("###### %d\n",strcmp("b","b"));printf("######%d\n",strcmp("b","f")); 
第30页：字符串处理函数
字符串处理函数简介
2、strncmp(s1,s2,n)：类似于 strcmp(s1,s2)，但只比较两个字符串的前 n 个字符。
3、strlen(s)：返回 s 字符串的长度（不包括结束符 '\0'），例：
printf("###### %d\n",strlen("abcdefgh")); 
第31页：链表插入结点的原则
链表插入结点原则：
插入操作不应破坏原链接关系
插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程
第32页：插入结点的示例
先看下面一个简单的例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该结点中的数为 10。
原链表：head → 5 → 6 → 10 → 15 → null（图中还标出待插入值 12 与 8 的位置示意）
插入后：待插入结点被插入到链表中合适的位置
说明：源文件该页以图形为主，结点数值呈粘连状态，上表文字为依据前后页（结点值 5、6、10、15 与待插入值 10、12、8）整理，建议对照原图核对。
第33页：插入结点的第一种与第二种情况
分析：考虑将结点 p 插入链表 head 中，分如下三种情况：
1、第一种情况，链表还未建成（空链表），待插入结点 p 实际上是第一个结点。这时必然有 head==null。只要让头指针指向 p 就可以了。语句为：
head = p; p->next = null;
2、第二种情况，链表已建成，待插入结点 p 的数据要比头结点的数据还要小，这时有 p->num < head->num，当然 p 结点要插在 head 结点前。
第34页：插到链表头的语句
第二种情况的图示：head 原指向 6，待插入结点 p 的值为 5（小于头结点 6），插入后 p 成为新的头结点。
p->next=head; head=p;
第35页：插入结点的第三种情况
3、第三种情况，链表已建成，待插入结点 p 的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针 r 和 q，利用循环比较来找到正确位置。然后将结点 p 插入到链表中正确的位置。参见下面的图示。
第36页：查找插入位置第一步
图示：head → 6 → 8 → 12 → 13 → null，待插入结点 p 的值为 15，指针 r 指向 6，指针 q 指向 8。
说明：这种情况下，p 结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。13>8，继续比较。
第37页：查找插入位置第二步
图示：r 前进到 8，q 前进到 12。
说明：13>12，继续比较。
第38页：找到位置并插入
图示：r 前进到 12，q 前进到 15。
说明：13<15，找到了正确的插入位置，则插入结点 p。语句为：
r->next = p; p->next = q;
第39页：结构7.c的定义部分
//结构7.c #include <stdio.h>#include <malloc.h>#define null 0#define LEN sizeof(struct numST)struct numST{ int num; struct numST *next;};
参考程序。
第40页：insert函数的前两种情况
//被调用函数insert()，两个形参分别表示链表和待插入的结点 void insert (struct numST **phead, struct numST *p) { struct numST *q,*r; if ((*phead)==null) { *phead = p; return; } else { if ( (*phead)->num > p->num) { p->next = *phead; *phead = p; return; }
第41页：insert函数的第三种情况
 r = *phead; q = (*phead)->next; while (q!=null) { if (q->num < p->num) { r = q; q = q->next; } else break; } r->next = p; p->next = q; } }
第42页：结构7.c的print函数
//被调用函数，形参为ST结构指针，用于输出链表内容 void print(struct numST *head) { int k=0; struct numST * r; r=head; while(r != null) { k=k+1; printf("%d %d\n",k,r->num); r=r->next; }}
第43页：结构7.c的主函数
void main(){ struct numST *head, *p; head = null; head = (struct numST *) malloc(LEN); head->next = (struct numST *) malloc(LEN); head->num = 5; head->next->num = 10; head->next->next = null; p = (struct numST *) malloc(LEN); p->num = 8; p->next = null; insert(&head, p); print(head);} 
第44页：指向指针的形参说明
说明：函数 insert() 的第一个形参为 struct numST** 类型，即“指针的指针”。调用时送入的实参是链表头指针的地址，即程序中的 &head。这样对 head 的修改才会在函数返回后仍有效。如果形参为 struct numST*，则传入的为指针，当函数返回后，head 无法改变。
第45页：第十一讲结束页
本页为第十一讲 结构的结束页，本讲内容至此结束。