数据结构c(11)-3.ppt

1、复 习,链 表： 链表的概念 单链表的特点 链表结构的定义 链表的基本操作 单链表的创建和输出 删除结点： 插入新的结点：,void *malloc(unsigned int size); 例如： int *p; p=(int *)malloc(8); p指示系统分配的4个整型存储单元的起始地址 也可看成包含4个数组元素的p数组：p0,p1,p2,p3,void *calloc(unsigned n,unsigned size);,void free(void *p);,例：创建一个存放正整数的单链表，并打印输出 #include stdlib.h /*包含malloc()的头文件*/ str

2、uct node /*链表节点的结构*/ int num; char str20; struct node *next; ; main() struct node *creat( ); /*函数声明*/ void print(); struct node *head; /*定义头指针*/ head=NULL;/*建一个空表*/ head=creat(head); /*创建单链表*/ print(head); /*打印单链表*/ ,struct node *creat(struct node *head) /*返回指针*/ struct node *p1,*p2; p1=p2=(struct n

3、ode*) malloc(sizeof(struct node); scanf(%d, /*返回链表的头指针*/ ,/*输出以head为头的链表各节点的值*/ void print(struct node *head) struct node *temp; temp=head; /*取得链表的头指针*/ while (temp!=NULL) printf(“%6d”,temp-num); /*输出链表节点的值*/ printf(“%s”,temp-str); temp=temp-next; ,从链表中删除一个节点有三种情况，即： 删除链表头节点 删除链表的中间节点 删除链表的尾节点 从链表中删

4、除一个节点，可用下图描述： 假定节点类型如下： struct node /*链表节点的结构*/ int num; char str20; struct node *next; ;,图7-4,对链表的插入结点操作 插入 ：链表的长短根据具体情况来设定，需要保存数据时向系统申请存储空间，并将数据（节点）接入链表中。 对链表而言，表中的数据可以依次接到表尾或连结到表头，也可以视情况插入表中； 在已建立的单链表中，插入节点有三种情况，插入的节点可以在表头、表中或表尾。 struct node /*链表节点的结构*/ int num; char str20; struct node *next; ;,在

5、第n个结点之后插入1个新结点 ,插入操作步骤： （1）q指针指向新结点，i为已访问过的结点数； （2）p=head，r指向p结点的前一个结点； （3）i+，r=p，p=p-next，p结点往前移动一个结点； （4）若inext=head，head=q; （6）若inext=q，q-next=NULL; （7）否则，将q结点插入到第n个结点之后，即插入到r结点与p结点之间：r-next=q，q-next=p; （8）返回链表头head。,例：创建节点包含学号、姓名的单链表。其节点数任意个，表以学号为序，低学号的在前，高学号的在后，以输入姓名为空作结束。在此链表中，要求删除一个给定姓名的节点，并插

6、入一个给定学号和姓名的节点。 #include stdlib.h #include “malloc.h”struct node /* 节点的数据结构*/ int num; char str20; struct node *next; ; main() struct node *creat(); /*函数声明*/ struct node *insert(); struct node *delet(); void print(); struct node *head; char str20; int n;,head=NULL; /*做空表*/ head=creat(head);/*调用函数创建以h

7、ead为头的链表*/ print(head); /*调用函数输出节点*/ printf(n input inserted num,name:n); gets(str); /*输入学号*/ n=atoi(str); gets(str); /*输入姓名*/ head=insert(head,str,n); /*将节点插入链表*/ print(head); /*调用函数输出节点*/ printf(n input deleted name:n); gets(str); /* 输入被删姓名*/ head=delet(head,str); /*调用函数删除节点*/ print(head); /*调用函数输

8、出节点*/ return; ,共用体,所谓共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。其定义形式为： union 共用体名 成员表列； 一、共用体的定义 union data /*定义了一个共用体数据类型union data */ int i; char ch; float f; obj; /*定义了共用体数据类型变量obj*/,共用体与结构体在形式上非常相似，但其表示的含义及在内存中的存储是完全不同的。,共用体变量定义分配内存, 长度=最长成员所占字节数,共用体变量任何时刻 只有一个成员存在,形式二: union data int i; char ch; fl

9、oat f; ; union data a,b,c,*p,d3;,形式三: union int i; char ch; float f; a,b,c;,二、 共用体变量的引用 可以引用共用体变量的成员，其用法与结构体完全相同： 注意: 不能同时引用四个成员，在某一时刻，只能使用其中之一的成员，因为在一个时间内只有一个成员存在。,例 a.i=1; a.ch=a; a.f=1.5; printf(“%d”,a.i); (编译通过，运行结果不对),引用规则： 不能引用共用体变量，只能引用其成员,共用体变量中起作用的成员是最后一次存放的成员,例 union int i; char ch; float

10、f; a; a=1; (),不能在定义共用体变量时初始化,例 union int i; char ch; float f; a=1,a,1.5; (),可以用一个共用体变量为另一个变量赋值,例 float x; union int i; char ch; float f; a,b; a.i=1; a.ch=a; a.f=1.5; b=a; () x=a.f; (),共用体特点： （1）系统采用覆盖技术，实现共用变量各成员的内存共享，所以在某一时刻，存放的和起作用的是最后一次存入的成员值。 例如，执行mm.a=1, mm.d=c, mm.b=3.14,mm.c=56.98后，mm.c才是有效的成

11、员。 （2）由于所有成员共享同一内存空间，故共用变量与其各成员的地址相同。 例如，mmmm.amm.dmm.c （3）不能对共用变量进行初始化（注意：结构变量可以）；也不能将共用变量作为函数参数，以及使函数返回一个共用数据，但可以使用指向共用变量的指针。 （4）共用类型可以出现在结构类型定义中，反之亦然。,struct time int year; /*年*/ int month; /*月*/ int day; /*日*/ ; union dig struct time data; /*嵌套的结构体类型*/ char byte6; ;,main() union dig unit; int i;

12、 printf(enter year:n); scanf(%d, ,运行程序，run enter year: 1976 enter month: 4 enter day: 23 year=1976 month=4 day=23 184, 7, 4, 0, 23, 0 因1976占2个字节，由第0、1字节构成 即7*256+184=1976。 4同样占两个字节，由第2、3字节构成，0*256+4=4， 23由第4、5字节构成，23=0*256+23。,枚举类型,枚举类型：将变量的可能取值一一列出，变量的取值只限于列出的值的范围。 定义枚举类型： enum ; enum weekdaysun,mo

13、n,tue,wed,thu,fri,sat; 1. 枚举元素按常量处理，枚举元素是有值的， C语言编译时按定义的顺序为：0,1,2,3,4,5,6 2. 定义枚举类型变量：enum weekday workday; 3. 给枚举变量赋值：Workday=mon; 4. 使用枚举变量的值：if(workday=mon) printf(“%d”,workday); if(workdaysun),enum ColorRed, Green, Yellow; void main(void) Color myColor; /Color是枚举类型名 myColor = Yellow; printf(“%d”

14、,myColor); ,枚举类型应用说明： 枚举元素具有缺省值，它们依次为： 0,1,2,.。 也可以在声明时另行指定枚举元素的值，如： enum Color Red=2,Green,Yellow; 使用时对枚举元素按常量处理，不能对它们赋值。例如，不能写：Red=0; 枚举值可以进行关系运算。,用typedef定义类型,除可直接使用提供的标准类型和自定义的类型（结构、共用、枚举）外，也可使用typedef定义已有类型的别名。该别名与标准类型名一样，可用来定义相应的变量。 类型定义简单形式： typedef type name; 如：typedef int INTERGER; typedef

15、float REAL; 则：int i, j; 等价于 INTERGER i，j； 作用： 1.可与别的语言的定义形式相同，方便用户使用； 2.可将某些变量按作用分类，以便编程和阅读程序一目了然。,说明: 1.typedef 没有创造新数据类型 2.typedef 是定义类型,不能定义变量 3、有时程序会依赖于硬件特性，使用 typedef有利于程序的通用与移植，如int的字节数。 4.typedef 与 define 不同,define typedef 预编译时处理 编译时处理 简单字符置换 为已有类型命名,typedef定义类型步骤： 按定义变量方法先写出定义体 如 int i; 将变量名

16、换成新类型名 如 int INTEGER; 最前面加typedef 如 typedef int INTEGER; 用新类型名定义变量 如 INTEGER i,j;,声明数组：typedef int NUM100; NUM n; 声明结构体类型： typedef struct int month; int day; int year; DATE; DATE birthday,*p; 声明字符指针类型：typedef char *STRING; STRING p, s10; p为字符指针变量，s为字符指针数组,练习,struct link int data; struck link *next;

17、a,b,c,*p,*q; 且变量a和b之间已有如下图所示的链表结构: 指针p指向变量a，q指向变量c。则能够把c插入到a和b 之间并形成新的链表的语句组是（ ）。 Aa.next=c; c.next=b; Bp.next=q; q.next=p.next; Cq-next=p-next;p-next=,以下程序的输出结果是（ ）。 union myun struct int x, y, z; u; int k; a; B5 C 6 D0,main() a.u.x=4; a.u.y=5;a.u.z=6;a.k=0;printf(%dn,a.u.x); ,#include struct NODE

18、int num; struct NODE *next; ; main() struct NONE *p,*q,*r; p=(struct NODE *)malloc(sizeof(struct NODE); q=(struct NODE *)malloc(sizeof(struct NODE); r=(struct NODE *)malloc(sizeof(struct NODE); p-num=10;q-num=20;r-num=30; p-next=q; q-next=r; printf(%dn,p-num+q-next-num); 程序运行后的输出结果是（ ）。 A）10 B） 20 C） 30 D） 40,有以下程序: struct STU char num10; float score3; ; main() struct STU s3=20021,90,95,85,20022,95,80,75, 20023,100,95,90 ,*p=s; int i; float sum=0; for(i=0;iscorei; printf(%6.2fn,sum); 程序运行后的输出结果是（ ）。 A）260.00 B） 270.00 C） 280.00 D