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

嵌入式C语言编程 常见数据结构及算法 GDAIB DataStructureandArithmetic 结构 联合 枚举用结构构成链表单向链表双向链表循环双向链表C语言中的常用算法 目录 Page2 一个学生的信息有学号 姓名 性别 年龄 住址 成绩等 一本图书的信息有分类编号 书名 作者 出版社 出版日期 价格 库存量等 如何描述这些类型不同的相关数据 信息管理 结构体 一种构造类型数据结构体由若干不同类型的数据项组成 构成结构体的各个数据项称为结构体成员 而数组是了相同类型数据的组合 复习 结构 联合 枚举 Page3 struct结构体名 数据类型1成员名1 数据类型2成员名2 数据类型n成员名n 结构体类型定义 struct为关键字 结构体名是用户定义的类型标识 中是组成该结构体的成员 成员的数据类型可以是C语言所允许的任何数据类型 例如 structstu longxh 学号是长整类型 charxm 20 姓名是字符数组类型 floatzf 总分是浮点类型 intmc 名次是整型类型 Page4 结构体类型变量的定义 有3种方法 1 先定义结构 再体类型定义该种类型的变量 structstus1 s2 structaccountzhang wang 定义结构体类型变量的一般形式struct结构体名结构体变量名表 2 在定义结构体类型的同时定义结构体变量 structaccount longid charname 20 structdateDate floatmoney zhang wang 一般形式为 struct结构体名 数据类型成员名1 数据类型成员名2 数据类型成员名n 结构体变量名表 Page5 3 直接定义结构体类型变量 struct longid charname 20 structdateDate floatmoney zhang wang struct 数据类型成员名1 数据类型成员名2 数据类型成员名n 结构体变量名表 说明 1 结构体变量的定义在函数的数据说明部分进行 也可以在函数的外部定义 但都必须是参照上述3种结构体变量的定义形式 类型定义在前 变量定义在后 2 结构体变量一经定义 在程序运行时 系统将按照结构体类型定义时的内存模式为结构体变量分配一定的存储单元 Page6 例structstudent intnum charname 20 structdate intmonth intday intyear birthday stu 例structdate intmonth intday intyear structstudent intnum charname 20 structdatebirthday stu 说明 结构体类型与结构体变量概念不同类型 不分配内存 变量 分配内存类型 不能赋值 存取 运算 变量 可以 sizeof求结构体类型数据的长度 printf d sizeof structstudent printf d sizeof stu Page7 结构体变量成员引用的一般形式 结构体变量名 成员名 结构体变量a的各成员可分别表示为a num a name a sex a score structdate intyear month day structstudent charnum 8 name 20 sex structdatebirthday floatscore a 是分量运算符 运算级别最高 a birthday yeara birthday montha birthday day 结构体变量的各个成员可进行何种运算 由该成员的数据类型决定 结构体变量成员引用 Page8 例 结构体变量的初始化 structdate intyear month day structstudent charnum 8 name 20 sex structdatebirthday floatscore a 9606011 Liming M 1977 12 9 83 b 9608025 Zhangliming F 1978 5 10 87 c 如果初值个数少于结构体成员个数 则将无初值对应的成员赋以0值如果初值个数多于结构体成员个数 则编译出错 结构体变量的初始化 Page9 例 结构体数组的初始化 structs charnum 8 name 20 sex floatscore stu 3 9606011 Liming M 87 5 9606012 Zhangjiangguo M 79 9606013 Wangping F 90 元素的个数可以省略 根据赋初值时结构体常量的个数确定数组元素的个数 结构体数组的初始化 Page10 补充 使用typedef定义新的类型名 structaccount longid charname 20 structdateDate floatmoney zhang wang structaccount longid charname 20 structdateDate floatmoney structaccountzhang wang structaccount longid charname 20 structdateDate floatmoney typedefstructaccountchen 等价 注意 用typedef定义的chen是类型名 而ch1和ch2是根据这个类型而定义的两个结构体变量 chench1 ch2 Page11 结构体类型解决了如何描述一个逻辑上相关 但数据类型不同的一组分量的集合 在需要节省内存储空间时 c语言还提供了一种由若干个不同类型的数据项组成 但共享同一存储空间的构造类型 共用体 一种构造类型数据共用体由若干不同类型的数据项组成 构成共用体的各个数据项称为共用体成员 由于共享的特性 只有最新存储的数据是有效的 共用体与共用体类型的定义 Page12 union共用体名 数据类型1成员名1 数据类型2成员名2 数据类型n成员名n 1 共用体类型定义的一般形式 union为关键字 共用体名是用户定义的类型标识 中是组成该共用体的成员 成员的数据类型可以是C语言所允许的任何数据类型 Page13 例如 unionutype inti charch longl charc 4 定义了一个unionutype共用体类型 共用体类型定义不分配内存空间 只是说明此类型数据的组成情况 Page14 2 共用体变量的定义 利用已定义的共用体类型名定义变量union共用体名变量名表 例如 unionutypeu1 u2 按照共用体类型的组成 系统为定义的共用体变量分配内存单元 共用体变量所占内存大小等于共用体中占用内存的长度最长的成员 printf d n sizeof unionutype printf d n sizeof u1 Page15 1 共用体类型变量在同一个内存段存放几种不同类型的成员 但在每一瞬时只能存放其中一种 而不是同时存放几种 2 共用体变量中起作用的成员是最后一次存放的成员 在存入一个新的成员后原来的成员就失去作用 u1 i 24 u1 ch a u1 f 12 45 3 共用体变量的地址和它的各成员的地址都是用一地址 例如 u1 u1 i u1 ch u1 f都是同一地址值 4 不能对共用体变量名赋值 不能企图引用变量名来得到一个值 也不能在定义共用体变量时对所有成员进行初始化 3 共用体类型数据的特点 Page16 在实际问题中 有些量的取值被限定在一个有限的范围内如 一个星期内只有七天一年只有十二个月嵌入式预科班只有2门课程 C Linux 一个班最多只能有30个学生如何为这些量定义类型 字符型或其它类型显然不妥当 枚举的概念 Page17 枚举类型定义的一般形式为 enum枚举名 枚举值表 枚举值为常量 也可以用typedef自定义类型typedefenum 枚举值表 枚举类型 枚举的定义 语言提供了一种称为 枚举 的类型 在 枚举 类型的定义中 列举出所有可能的取值 说明该 枚举 类型的变量取值不能超过定义的范围 Page18 枚举常量枚举常量是int型的常量 在使用int类型的任何地址都可以使用week tweek SUN DAY printf weekis d n week printf sizeof week t is d n sizeof week t 默认值没有特定指出常量值时 枚举列表中的常量被指定为整数值0 1 2等 依次递增 枚举的使用 Page19 sizeof week t is2如果是32位的C编译平台 则为4 weekis0 指定值可以选择常量具有的整数值 后面的常量会被赋予后续的值 Page20 结构 联合 枚举用结构构成链表单向链表双向链表循环双向链表C语言中的常用算法 目录 Page21 链表 定义 链表是一种常见的重要数据结构 它可以动态地进行存储分配 根据需要开辟内存单元 还可以方便地实现数据的增加和删除 结构 链表中的每个元素都由两部分组成 即数据域和指针域分类 单链表 又分为单向链表和双向链表 循环链表 Page22 单向链表 NULL Head structmylink inta structmylink next Head ptr 单向链表的每个节点中除信息域以外还有一个指针域 用来指向其后续节点 其最后一个节点的指针域为空 NULL Page23 双向链表 Head NULL structmylink inta structmylink next structmylink prev Head ptr NULL 双向链表与单向链表不同 它的每个节点中包括两个指针域 分别指向该节点的前一个节点和后一个节点 Page24 循环双向链表 Head structmylink inta structmylink next structmylink prev Head ptr 循环链表的组织结构与单链表非常相似 因此其操作与单链表也是一致的 惟一的差别仅在于在单链表中 算法判断到达链表尾的条件是p next是否为空 而在双链表中 则是判断p next是否等于头指针 Page25 结构 联合 枚举用结构构成链表单向链表双向链表循环双向链表C语言中的常用算法 目录 Page26 算法是问题求解过程的精确描述 一个算法由有限条可完全机械地执行的 有确定结果的指令组成 C语言中的常用算法 算法和数据结构是程序的两个重要方面 经常采用的算法主要有迭代法 穷举搜索法 递推法 贪婪法 回溯法 分治法 动态规划法等等 另外 在算法设计时又常常采用递归技术 用递归描述算法 在C语言中接确到的算法有用于排序的冒泡法和选择法 还有用于求n 的递推法 通常求解一个问题可能会有多种算法可供选择 选择的主要标准是算法的正确性和可靠性 简单性和易理解性 其次是算法所需要的存储空间少和执行更快等 定义 种类 选择标准 Page27 冒泡排序法 从小到大 两层循环结构外层循环每次把操作范围内最大的数放到最后位置内层循环每次把较大的数放到靠后的位置 先排后面 算法过程 Page28 冒泡法示例 将50个学生成绩按从低到高的顺序全部输出 defineN50main inti j t x N for i 0 ix j 1 比较相邻两数 小的调到前面 t x j x j x j 1 x j 1 t printf thesortednembers n for i 0 i N i printf 5d n x i Page29 以6个数 3 7 5 6 8 0为例 算法 第一趟 将第一个数依次和后面的数比较 如果后面的某数小于第一个数 则两个数交换 比较结束后 第一个数则是最小的数 第二趟 将第二个数依次和后面的数比较 如果后面的某数小于第二个数 则两个数交换 比较结束后 第二个数则是次小的数 选择法排序 从小到大 先排前面 Page30 defineN50main inti j t x N for i 0 i N i scanf d 选择法示例 将50个学生成绩按从低到高的顺序全部输出 Page31 1 直接或者间接调用函数本身叫递归调用 递归为函数嵌套调用过程2 经典的递归算法实例 递推法 递归调用 Page32 Page33 End