第 17讲共用体链表
2
如何定义数据类型存储下列表格中的数据姓名
name
年龄
age
所在办公室 office工作
job （或班级 class）
struct person
{char name[10];
int age;
char job;
depa;
};
需要一个数据单元，但不同情况下存不同的数据。
李四 21 学生 0600001
张三 30 教师 计算机基础教学部
union DEPT
{ int class;
char office[10];
}
union DEPT
{ int class;
char office[10];
};/*先定义共用体类型 */
struct person
{char name[10];
int age;
char job;
union DEPT depa;
};
共用体类型
union DEPT
3
#include <stdio.h>
struct person
{ char name[10];
int age;
char job;
union DEPT
{ int class;
char office[10];
}depa;
};
void main()
{ struct person ps[4];
int n,i;
for(i=0;i<4;i++)
{scanf("%s %d %c",ps[i].name,&ps[i].age,&ps[i].job);
if(ps[i].job==?s?) /*要先判断 job是什么,然后决定存什么 */
scanf("%d",&ps[i].depa.class);
else if(ps[i].job=='t')
scanf("%s",ps[i].depa.office);
}
例 6-41
printf("\nName Age Job Class/office\n");
for(i=0;i<4;i++)
{ if(ps[i].job==?s?)/*输出的时候同样先判断，再决定输出什么 */
printf("%-10s%-6d%-3c%-10d\n",
ps[i].name,ps[i].age,ps[i].job,ps[i].depa.class);
else
printf("%-10s%-6d%-3c%-10s\n",
ps[i].name,ps[i].age,ps[i].job,ps[i].depa.office);
}
}
4
共用体类型数据的特点
union example
{ short x;
char ch[4];
}a;
a.ch[0]
a.ch[1]
a.ch[2]
a.ch[3]
a.x0F15
0F16
0F17
0F18
在内存中：
1.sizeof(union xxx)取决于 占空间最多 的那个成员变量
2.a.x和 a.ch处于 同样的地址
3.同一内存单元在每一时刻只能存放一个成员的值；
5
例 6－ 40 读取 16位整型数据的高字节数据
#include <stdio.h>
union data
{ short i;
char c[2];
};/*这种类型的变量可以看成一个整型变量,也可以看成两个字符型变量,字符型变量对应的 ASCII码即对应整型数的高,低字节 */
typedef union data DATA;
void main()
{ DATA r,*s=&r;
s->i=0x3833; /*换算成二进制为 00111000 00110011 */
printf("\n");
printf("c[0]=%d,c[1]=%d\n",r.c[0],s->c[1]);
}
00110011
00111000
r.c [0]
r.c[1]
r.i0F15
0F16
6
问题：数组有何缺点？
数组必须占据 连续 内存，在数组元素的插入或删除时，费时费力 。
数组的 长度从定义起就固定不变 。如果数据元素的个数不可预知时，就要将数组定义得足够大以备不时之需，这就会造成空间的浪费；此外，数组一经定义就占据内存，直至程序结束。
7
引入 链表 的原因
最主要的是 插入、删除操作的灵活性
能够根据需要灵活申请和释放内存空间。
缺点？
data nexthead data next data NULLdata next
data next
8
链表
一种 数据结构,用顺序,不连续 的内存空间存储数据。
链表中每个节点的数据类型（ Linked table）
struct Link
{ int data;
struct Link *next;
}
data nexthead data next data next data NULL
9
例 8-22 创建链表并存入数据
算法：
循环执行下列操作：
1、创建新节点
1、申请一个节点所用的内存；
2、向该节点存入数据；
2、将该节点链入链表尾部；
struct student
{ char num[10];
float score;
struct student *next;
};/*每个节点的数据类型 */
10
创建一个新节点
struct student *CreateNode()
{
struct student *p;
p = (struct Link *)malloc(sizeof(struct Link)); /* 动态申请一段内存 */
if(p == NULL) /* 申请失败,打印错误信息,退出程序 */
{ printf("No enough memory to alloc");
exit(0); /*结束整个程序的运行 */
}
/*为新建节点赋值 */
p->next = NULL;/* 新建的节点指针域赋空指针 */
printf(“please input number:”); /* 为新建的节点数据区赋值 */
gets(p->num);
printf(“please input score:”);
scanf(“%d”,&p->score);
printf("\n successful create a new node!");
return p;
}
11
struct student *createList( void )
{ struct student *head=NULL,*pr,p; /*开始时是空链表 */
int count=0; char c;
printf(“开始建立链表,请根据提示输入数据：,);
do/*循环实现建立链表 */
{ printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
c = getchar();
if ((c!='y'||c!='Y')&&(c!='n'||c!='N'))
{/* 如果键入既不是 ' y ',又不是 'n'则循环继续进行 */
puts("you must input 'y' or 'n'");
continue;
}
if ((c=='n'||c=='N')) /* 如果键入的是 'n'循环退出 */
break;
p= CreateNode();
if (count==0)/* 如果是第一个节点,将新节点链至头节点后 */
{ head=p;
pr = head;//使用 pr跟踪当前节点的前一个节点
}
else/* 不是第一个节点,将新建节点接到链表的结尾 pr处 */
{ pr->next = p;
pr = pr->next;//使用 pr跟踪当前节点的前一个节点
}
count++;
} while(1);
return(head); /*返回链表的头结点 */
}
创建链表
12
输出创建的链表
void PrintList(struct student *head)
{ struct student *p;
p=head;
if(head==NULL) /*判断是否为空链表 */
{ printf("List is empty! \n");
else
{ while(p!=NULL)
{ printf("%5s %4.1f\n ",p->num,p->score);
p=p->next; /*指向下一个节点 */
}
}
}
13
链表中插入节点
Head=p;
p->next=head;
Head=p;
p->next= pr ->next;
pr ->next =p;
p
p
p
pr
p
14
struct student *InsertNode(struct student *head,struct student *p,int i)
{
struct student *pr;
if(head==NULL)
{ head=p; p->next=NULL; }/*插入到空链表 */
else
if(i==0)
{ p->next=head; head=p; } /*插入到表头 */
else /*插入到第 i(!=0)个位置 */
{ pr=head;
for( ;pr!=NULL&&i>1;pr=pr->next,i--); /*找到第 i(!=0)个位置 */
if(pr==NULL)
printf("Out of the range,can?t insert p node!\n");
else
{p->next=pr->next; pr->next=p;}
}
return(head);
}
插入节点
15
链表中删除节点
(1)删除第一个结点
(2)删除中间结点
head=head->next;
pr->next =p->next;
p
pr
16
struct student *DeleteNode(struct student *head,char num[])
{struct student *pr;
struct student *p;
if(head==NULL)
{ printf("\nList is empty\n");
return(head);
}
if(strcmp(head->num,num)==0) /*删除第一个结点 */
{ p=head; head=head->next; free(p); /*不要忘了释放内存 */
}
else /*删除其它位置上满足条件的结点 */
{ pr=head; p=head->next;
while(p!=NULL&& strcmp(p->num,num)!=0)
{ pr=p;
p=p->next;
} /*找满足条件的结点 */
if(p!=NULL) /*找到，删除 */
{ pr->next=p->next; free(p); /*不要忘了释放内存 */
}
else
{ printf("%5s not been found\n",num);}
}
return(head);
}
删除节点
17
链表中的要点
用于建立更加灵活的动态数组，每个数组元素均是一个节点。因此，首先应声明每个节点的数据类型 (结构体类型的声明 )
无论是哪种操作 (建立，插入，删除 )，都是 指针的重新指向 问题，即对指针 (head或 pr,p指向的节点的 next成员 )重新赋值的过程。
18
小结
共用体
基本概念
定义、初始化、引用
链表
概念以及数据类型定义
建立、输出、插入、删除等应用。
下节课讲第七、八章剩余内容及总结
19
作业
编写程序，实现 (每一个写成一个函数 )：
创建链表，并将学生的学号、姓名和 N门课成绩写入链表，并计算每个学生的总分和平均分。
增加新节点 (增加一个学生的信息 )
查找并输出某个学生的信息 (写成两个函数，分别按学号和姓名查找 )
删除节点 (删除某个学生的记录，可以按姓名或学号查找，然后再删除 )
修改某个学生的信息
对节点进行排序 (选做 )
显示所有学生信息
释放内存
在主函数中创建一个菜单，由用户选择可进行的操作。
2
如何定义数据类型存储下列表格中的数据姓名
name
年龄
age
所在办公室 office工作
job （或班级 class）
struct person
{char name[10];
int age;
char job;
depa;
};
需要一个数据单元，但不同情况下存不同的数据。
李四 21 学生 0600001
张三 30 教师 计算机基础教学部
union DEPT
{ int class;
char office[10];
}
union DEPT
{ int class;
char office[10];
};/*先定义共用体类型 */
struct person
{char name[10];
int age;
char job;
union DEPT depa;
};
共用体类型
union DEPT
3
#include <stdio.h>
struct person
{ char name[10];
int age;
char job;
union DEPT
{ int class;
char office[10];
}depa;
};
void main()
{ struct person ps[4];
int n,i;
for(i=0;i<4;i++)
{scanf("%s %d %c",ps[i].name,&ps[i].age,&ps[i].job);
if(ps[i].job==?s?) /*要先判断 job是什么,然后决定存什么 */
scanf("%d",&ps[i].depa.class);
else if(ps[i].job=='t')
scanf("%s",ps[i].depa.office);
}
例 6-41
printf("\nName Age Job Class/office\n");
for(i=0;i<4;i++)
{ if(ps[i].job==?s?)/*输出的时候同样先判断，再决定输出什么 */
printf("%-10s%-6d%-3c%-10d\n",
ps[i].name,ps[i].age,ps[i].job,ps[i].depa.class);
else
printf("%-10s%-6d%-3c%-10s\n",
ps[i].name,ps[i].age,ps[i].job,ps[i].depa.office);
}
}
4
共用体类型数据的特点
union example
{ short x;
char ch[4];
}a;
a.ch[0]
a.ch[1]
a.ch[2]
a.ch[3]
a.x0F15
0F16
0F17
0F18
在内存中：
1.sizeof(union xxx)取决于 占空间最多 的那个成员变量
2.a.x和 a.ch处于 同样的地址
3.同一内存单元在每一时刻只能存放一个成员的值；
5
例 6－ 40 读取 16位整型数据的高字节数据
#include <stdio.h>
union data
{ short i;
char c[2];
};/*这种类型的变量可以看成一个整型变量,也可以看成两个字符型变量,字符型变量对应的 ASCII码即对应整型数的高,低字节 */
typedef union data DATA;
void main()
{ DATA r,*s=&r;
s->i=0x3833; /*换算成二进制为 00111000 00110011 */
printf("\n");
printf("c[0]=%d,c[1]=%d\n",r.c[0],s->c[1]);
}
00110011
00111000
r.c [0]
r.c[1]
r.i0F15
0F16
6
问题：数组有何缺点？
数组必须占据 连续 内存，在数组元素的插入或删除时，费时费力 。
数组的 长度从定义起就固定不变 。如果数据元素的个数不可预知时，就要将数组定义得足够大以备不时之需，这就会造成空间的浪费；此外，数组一经定义就占据内存，直至程序结束。
7
引入 链表 的原因
最主要的是 插入、删除操作的灵活性
能够根据需要灵活申请和释放内存空间。
缺点？
data nexthead data next data NULLdata next
data next
8
链表
一种 数据结构,用顺序,不连续 的内存空间存储数据。
链表中每个节点的数据类型（ Linked table）
struct Link
{ int data;
struct Link *next;
}
data nexthead data next data next data NULL
9
例 8-22 创建链表并存入数据
算法：
循环执行下列操作：
1、创建新节点
1、申请一个节点所用的内存；
2、向该节点存入数据；
2、将该节点链入链表尾部；
struct student
{ char num[10];
float score;
struct student *next;
};/*每个节点的数据类型 */
10
创建一个新节点
struct student *CreateNode()
{
struct student *p;
p = (struct Link *)malloc(sizeof(struct Link)); /* 动态申请一段内存 */
if(p == NULL) /* 申请失败,打印错误信息,退出程序 */
{ printf("No enough memory to alloc");
exit(0); /*结束整个程序的运行 */
}
/*为新建节点赋值 */
p->next = NULL;/* 新建的节点指针域赋空指针 */
printf(“please input number:”); /* 为新建的节点数据区赋值 */
gets(p->num);
printf(“please input score:”);
scanf(“%d”,&p->score);
printf("\n successful create a new node!");
return p;
}
11
struct student *createList( void )
{ struct student *head=NULL,*pr,p; /*开始时是空链表 */
int count=0; char c;
printf(“开始建立链表,请根据提示输入数据：,);
do/*循环实现建立链表 */
{ printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
c = getchar();
if ((c!='y'||c!='Y')&&(c!='n'||c!='N'))
{/* 如果键入既不是 ' y ',又不是 'n'则循环继续进行 */
puts("you must input 'y' or 'n'");
continue;
}
if ((c=='n'||c=='N')) /* 如果键入的是 'n'循环退出 */
break;
p= CreateNode();
if (count==0)/* 如果是第一个节点,将新节点链至头节点后 */
{ head=p;
pr = head;//使用 pr跟踪当前节点的前一个节点
}
else/* 不是第一个节点,将新建节点接到链表的结尾 pr处 */
{ pr->next = p;
pr = pr->next;//使用 pr跟踪当前节点的前一个节点
}
count++;
} while(1);
return(head); /*返回链表的头结点 */
}
创建链表
12
输出创建的链表
void PrintList(struct student *head)
{ struct student *p;
p=head;
if(head==NULL) /*判断是否为空链表 */
{ printf("List is empty! \n");
else
{ while(p!=NULL)
{ printf("%5s %4.1f\n ",p->num,p->score);
p=p->next; /*指向下一个节点 */
}
}
}
13
链表中插入节点
Head=p;
p->next=head;
Head=p;
p->next= pr ->next;
pr ->next =p;
p
p
p
pr
p
14
struct student *InsertNode(struct student *head,struct student *p,int i)
{
struct student *pr;
if(head==NULL)
{ head=p; p->next=NULL; }/*插入到空链表 */
else
if(i==0)
{ p->next=head; head=p; } /*插入到表头 */
else /*插入到第 i(!=0)个位置 */
{ pr=head;
for( ;pr!=NULL&&i>1;pr=pr->next,i--); /*找到第 i(!=0)个位置 */
if(pr==NULL)
printf("Out of the range,can?t insert p node!\n");
else
{p->next=pr->next; pr->next=p;}
}
return(head);
}
插入节点
15
链表中删除节点
(1)删除第一个结点
(2)删除中间结点
head=head->next;
pr->next =p->next;
p
pr
16
struct student *DeleteNode(struct student *head,char num[])
{struct student *pr;
struct student *p;
if(head==NULL)
{ printf("\nList is empty\n");
return(head);
}
if(strcmp(head->num,num)==0) /*删除第一个结点 */
{ p=head; head=head->next; free(p); /*不要忘了释放内存 */
}
else /*删除其它位置上满足条件的结点 */
{ pr=head; p=head->next;
while(p!=NULL&& strcmp(p->num,num)!=0)
{ pr=p;
p=p->next;
} /*找满足条件的结点 */
if(p!=NULL) /*找到，删除 */
{ pr->next=p->next; free(p); /*不要忘了释放内存 */
}
else
{ printf("%5s not been found\n",num);}
}
return(head);
}
删除节点
17
链表中的要点
用于建立更加灵活的动态数组，每个数组元素均是一个节点。因此，首先应声明每个节点的数据类型 (结构体类型的声明 )
无论是哪种操作 (建立，插入，删除 )，都是 指针的重新指向 问题，即对指针 (head或 pr,p指向的节点的 next成员 )重新赋值的过程。
18
小结
共用体
基本概念
定义、初始化、引用
链表
概念以及数据类型定义
建立、输出、插入、删除等应用。
下节课讲第七、八章剩余内容及总结
19
作业
编写程序，实现 (每一个写成一个函数 )：
创建链表，并将学生的学号、姓名和 N门课成绩写入链表，并计算每个学生的总分和平均分。
增加新节点 (增加一个学生的信息 )
查找并输出某个学生的信息 (写成两个函数，分别按学号和姓名查找 )
删除节点 (删除某个学生的记录，可以按姓名或学号查找，然后再删除 )
修改某个学生的信息
对节点进行排序 (选做 )
显示所有学生信息
释放内存
在主函数中创建一个菜单，由用户选择可进行的操作。
