hust数据结构DS.ppt

数据结构与算法 C语言简要回顾 数据结构基本概念 算法分析 第一节 C语言回顾 C语言的成份 C语言语句 C语言变量 C语言的数据类型 函数 程序结构 结构和联合 指针 C语言成份 C语言的成份： 语句 定义 申明 注释 C语言语句 C语言的语句用“；”标记。分为以下几种： 赋值语句/表达式语句 函数调用(子程序) 流程控制语句 空语句 C语言变量的定义与申明 变量的定义 存储类型 数据类型 变量名 = 初始值; int x; int x = 3; static int x = 3; 变量的作用域：变量只在定义它的(函数)范围内起作用 在所有函数体之外定义的变量称全局变量 C语言的数据类型 数据类型 C语言基本数据类型 C语言的基本数据类型包含：字符型、整型、实型、枚举型 不同的C编译器可能对一些类型的在内存中的字节数规定不同，可以用sizeof()检测各种类型所需的存储字节数。 数组 数组的定义 存储类型 数据类型 数组名[元素个数]= {初始值表}; 数组的初值 数组在内存中的存储：顺序存储 数组的引用：以元素下标引用 下标总是从0开始，到元素个数-1 数组引用的实质：地址+偏移 数组等同于一个指针 数组的申明 字符数组与字符串 字符数组 定义：跟上面的数组一样，数据类型为char 初值：跟上面一样，但增加了一种 字符串：字符数组的最后一种形式，自动加0的字符数组 函数 函数定义 存储类型 返回类型 函数名(形参列表) {函数体语句} 返回类型：void型相当于子程序 形式参数：传值型、传址型。注意申明形式 函数调用：非void返回值可赋给变量;可直接作语句用。 函数申明 extern 返回类型 函数名(形参[类型]列表); 注意：有；符号。形参可只给类型。 通常函数申明放在头文件中。有时也叫函数原型。 程序结构 顺序结构 按照语句的顺序执行 流程控制 选择结构 if – else switch 循环结构 for while { } do { } while do { } until 跳转 goto 结构 结构定义 struct 结构名 { 结构成员类型 结构成员名; …… }; 结构使用 struct 结构名 变量名; 联合 联合定义 union联合名 { 联合成员类型 联合成员名; …… }; 联合的使用 union 联合名 变量名; 结构对齐 注意：不同的编译器使用不同的结构对齐策略，如字节对齐、字对齐、双字对齐 使用编译申明： #pragma pack(1)迫使进行字节对齐 自定义数据类型 使用typedef定义自定义的数据类型 typedef 原数据类型 用户数据类型 使用：等同于系统预定义的数据类型 自定义数据类型与宏定义不同, 宏定义只是展开，因此数据类型不变，而自定义类型则不同，是一种新的数据类型。很多编译器在编译时进行类型检查，以确定是否违例 地址指针 程序在内存中才能得以执行，数据在内存中才能被直接访问。内存单元是以地址标记的。 定义： 数据类型 * 变量名; Int *MyInt; Struct Student *lpStudentsList; 使用： *MyInt = 30; lpStudentsList-StID = 1234; 注意：指针是一种类型，指针变量也占用内存。 函数指针 每一个函数被编译成代码后，都会装入内存以执行，它们在内存中都会有一个入口地址。可以用一个变量表示这个入口地址，称为指向这个函数的指针。 使用指针时的注意事项 可以定义指针类型的变量，但使用该指针变量前，必须初始化，否则不知道该指针变量指向何处，造成结果混乱，甚于造成访问违例(Exception)。 空指针用NULL表示。指针变量的值为空(NULL)，实际上是0, 为什么可以用0代表空指针 指针变量的值存放的是地址，可以进行+,-,++,--运算。 指针分为短指针(32位)和长指针(64位)。 指针变量可以作为函数的参数进行传递。Windows API大量使用回调函数，就是将函数作为参数的。 一个指针变量可指向另一个指针变量的地址,即指针的指针 void指针类型：首先表明是一个指针，但具体未指明是那一种类型的指针。 含有指针成员的结构 既然指针是一种数据类型，当然在定义结构时可以使用指针类型的成员，包括函数指针。 在学习C语言时，曾在讲结构和指针之后，讲了如何用指针处理链表 在C++语言中，是如何实现类的 第二节 数据结构的基本概念 典型数据结构的例子 数据结构的基本概念 数据结构的表示 数据操作 数据结构的例 – 之1 数据结构的例 – 之2 a 数据结构的例 – 之3 多叉路口交通灯管理问题 数据结构的例－小结 这些例子中，描述这类问题的数学模型不再是数学方程 数