嵌入式C语言常见数据结构及算法.ppt

嵌入式C语言编程常见数据结构及算法,GDAIB,Data Structure and Arithmetic,结构、联合、枚举 用结构构成链表 单向链表 双向链表 循环双向链表 C语言中的常用算法,目 录,Page 2,一个学生的信息有学号、姓名、性别、年龄、住址、成绩等。 一本图书的信息有分类编号、书名、作者、出版社、出版日期、价格、库存量等。 如何描述这些类型不同的相关数据？,?,信息管理,结构体一种构造类型数据 结构体由若干不同类型的数据项组成， 构成结构体的各个数据项称为结构体成员。,而数组是了相同类型数据的组合,复习结构、联合、枚举,Page 3,struct 结构体名 数据类型1 成员名1; 数据类型2 成员名2; 数据类型n 成员名n; ;,结构体类型定义,struct为关键字； 结构体名是用户定义的类型标识。 中是组成该结构体的成员。成员的数据类型可以是C语言所允许的任何数据类型。,例如：struct stu long xh； /* 学号是长整类型 */ char xm20；/* 姓名是字符数组类型 */ float zf； /* 总分是浮点类型 */ int mc； ； /* 名次是整型类型 */,Page 4,结构体类型变量的定义,有3种方法：,1先定义结构，再体类型定义该种类型的变量,struct stu s1 , s2； struct account zhang, wang；,定义结构体类型变量的一般形式 struct 结构体名 结构体变量名表；,2在定义结构体类型的同时定义结构体变量。,struct account long id； char name20； struct date Date； float money； zhang,wang；,一般形式为：,struct 结构体名 数据类型 成员名1； 数据类型 成员名2； 数据类型 成员名n； 结构体变量名表；,Page 5,3直接定义结构体类型变量,struct long id； char name20； struct date Date； float money； zhang, wang；,struct 数据类型 成员名1； 数据类型 成员名2； 数据类型 成员名n； 结构体变量名表；,说明：,（1）结构体变量的定义在函数的数据说明部分进行，也可以在函数的外部定义。但都必须是参照上述3种结构体变量的定义形式，类型定义在前，变量定义在后。,（2）结构体变量一经定义，在程序运行时，系统将按照结构体类型定义时的内存模式为结构体变量分配一定的存储单元。,Page 6,例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu;,例 struct date int month; int day; int year; ; struct student int num; char name20; struct date birthday; stu;,说明 ：结构体类型与结构体变量概念不同 类型:不分配内存； 变量:分配内存 类型:不能赋值、存取、运算; 变量:可以,sizeof求结构体类型数据的长度:,printf(“d”,sizeof(struct student)； printf(“%d”,sizeof(stu)；,Page 7,结构体变量成员引用的一般形式： 结构体变量名.成员名,结构体变量a的各成员可分别表示为a.num、、a.sex、a.score,struct date int year, month, day; struct student char num8, name20, sex; struct date birthday; float score; a;,“.”是分量运算符，运算级别最高。,a.birthday.year a.birthday.month a.birthday.day,结构体变量的各个成员可进行何种运算，由该成员的数据类型决定,结构体变量成员引用,Page 8,【例】结构体变量的初始化。 struct date int year, month, day; struct student char num8, name20, sex; struct date birthday; float score; a=“9606011“,“Li ming“,M,1977,12,9,83, b=“9608025“,“Zhang liming“,F,1978,5,10,87,c;,如果初值个数少于结构体成员个数,则将无初值对应的成员赋以0值 如果初值个数多于结构体成员个数,则编译出错,结构体变量的初始化,Page 9,【例】结构体数组的初始化。 struct s char num8,name20,sex; float score; stu3=“9606011“,“Li ming“,M,87.5, “9606012“,“Zhang jiangguo“,M,79, “9606013“,“Wang ping“,F,90;,元素的个数可以省略，根据赋初值时 结构体常量的个数确定数组元素的个数,结构体数组的初始化,Page 10,补充：使用typedef定义新的类型名,struct account long id； char name20； struct date Date； float money； zhang,wang；,struct account long id； char name20； struct date Date； float money； struct account zhang, wang；,struct account long id； char name20； struct date Date； float money； typedef struct account chen;,等价,注意：用typedef定义的chen是类型名，而ch1和ch2是根据这个类型而定义的两个结构体变量,chen ch1,ch2;,Page 11,结构体类型解决了如何描述一个逻辑上相关，但数据类型不同的一组分量的集合。 在需要节省内存储空间时，c语言还提供了一种由若干个不同类型的数据项组成，但共享同一存储空间的构造类型。,共用体一种构造类型数据 共用体由若干不同类型的数据项组成， 构成共用体的各个数据项称为共用体成员。,由于共享的特性，只有最新存储的数据是有效的。,共用体与共用体类型的定义,Page 12,union 共用体名 数据类型1 成员名1; 数据类型2 成员名2; 数据类型n 成员名n; ;,1、共用体类型定义的一般形式：,union为关键字； 共用体名是用户定义的类型标识。 中是组成该共用体的成员。成员的数据类型可以是C语言所允许的任何数据类型。,Page 13,例如： union utype int i; char ch; long l; char c4; ;,定义了一个union utype共用体 类型，共用体类型定义不分配内存 空间，只是说明此类型数据的组成 情况。,Page 14,2、共用体变量的定义,利用已定义的共用体类型名定义变量 union 共用体名 变量名表； 例如： union utype u1,u2;,按照共用体类型的组成，系统为定义的共用体变量分配内存单元。共用体变量所占内存大小等于共用体中占用内存的长度最长的成员。,printf(“%dn”,sizeof(union utype)； printf(“%dn”，sizeof(u1)；,Page 15,(1)共用体类型变量在同一个内存段存放几种不同类型的成员，但在每一瞬时只能存放其中一种，而不是同时存放几种,(2)共用体变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后原来的成员就失去作用,u1.i=24； u1.ch=a； u1.f=12.45；,(3)共用体变量的地址和它的各成员的地址都是用一地址,例如：&u1、&u1.i、&u1.ch、&u1.f都是同一地址值。,(4)不能对共用体变量名赋值，不能企图引用变量名来得到一个值，也不能在定义共用体变量时对所有成员进行初始化。,3、共用体类型数据的特点,Page 16,在实际问题中，有些量的取值被限定在一个有限的范围内 如： 一个星期内只有七天 一年只有十二个月 嵌入式预科班只有2门课程（C、Linux） 一个班最多只能有30个学生 如何为这些量定义类型？ 字符型或其它类型显然不妥当,枚举的概念,Page 17,枚举类型定义的一般形式为： enum 枚举名 枚举值表 /枚举值为常量 ; 也可以用typedef自定义类型 typedef enum 枚举值表 枚举类型;,枚举的定义,语言提供了一种称为“枚举”的类型，在“枚举”类型的定义中“列举出所有可能的取值”，说明该“枚举”类型的变量取值不能超过定义的范围。,Page 18,枚举常量 枚举常量是int型的常量，在使用int类型的任何地址都可以使用 week_t week = SUN_DAY; printf(“week is %dn”, week ); printf(“sizeof(week_t) is %dn”, sizeof(week_t); 默认值 没有特定指出常量值时，枚举列表中的常量被指定为整数值0、1、2等，依次递增,枚举的使用,Page 19,sizeof(week_t) is 2 如果是32位的C编译平台，则为4,week is 0,指定值 可以选择常量具有的整数值，后面的常量会被赋予后续的值,Page 20,结构、联合、枚举 用结构构成链表 单向链表 双向链表 循环双向链表 C语言中的常用算法,目 录,Page 21,链 表,定义：链表是一种常见的重要数据结构，它可以动态地进行存储分配，根据需要开辟内存单元，还可以方便地实现数据的增加和删除。 结构：链表中的每个元素都由两部分组成，即 数据域和指针域 分类：单链表（又分为单向链表和双向链表） 循环链表,Page 22,单向链表,NULL,Head,struct mylink int a; struct mylink *next; *Head, ptr;,单向链表的每个节点中除信息域以外还有一个指针域，用来指向其后续节点，其最后一个节点的指针域为空（NULL）,Page 23,双向链表,Head,NULL,struct mylink int a; struct mylink *next; struct mylink *prev; *Head, ptr;,NULL,双向链表与单向链表不同，它的每个节点中包括两个指针域，分别指向该节点的前一个节点和后一个节点,Page 24,循环双向链表,Head,struct mylink int a; struct mylink *next; struct mylink *prev; *Head, ptr;,循环链表的组织结构与单链表非常相似，因此其操作与单链表也是一致的，惟一的差别仅在于在单链表中，算法判断到达链表尾的条件是pnext是否为空，而在双链表中，则是判断pnext是否等于头指针,Page 25,结构、联合、枚举 用结构构成链表 单向链表 双向链表 循环双向链表 C语言中的常用算法,目 录,Page 26,算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成,C语言中的常用算法,算法和数据结构是程序的两个重要方面,经常采用的算法主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，在算法设计时又常常采用递归技术，用递归描述算法。在C语言中接确到的算法有用于排序的冒泡法和选择法，还有用于求n！的递推法。,通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。,定义：,种类：,选择标准：,Page 27,冒泡排序法（从小到大）,两层循环结构 外层循环每次把操作范围内最大的数放到最后位置 内层循环每次把较大的数放到靠后的位置,先排后面,算法过程,Page 28,【冒泡法示例】将50个学生成绩按从低到高的顺序全部输出,#define N 50 main() int i,j, t, xN; for( i=0; ixj+1) /*比较相邻两数,小的调到前面*/ t=xj;xj=xj+1;xj+1=t; printf(“the sorted nembers:n”); for( i=0; iN; i+) printf(“%5dn”, xi); ,Page 29,以6个数：3、7、5、6、8、0为例。 算法： 第一趟：将第一个数依次和后面的数比较，如果后面的某数小于第一个数，则两个