数据结构-预备知识.ppt

第0章 预备知识 Thursday August27 2009nysfxy 1 第0章预备知识 Thursday August27 2009nysfxy 1 数据结构与算法应用教程 主要内容 1输入与输出2预定义常量3函数4结构体5引用6指针7内存动态分配与释放8枚举9类型定义 typedef 1输入与输出输入与输出流对象 cout和cin iostream h 1 用cout进行输出格式 cout 变量1 变量2 将提取符 作用在流类对象cin上实现输入如 inta b cin a b 例1 cin与cout的使用 includevoidmain cout name cin age cout Yournameis name endl cout Yourageis age endl 运行情况如下 Pleaseenteryournameandage Wang li 19 yournameisWang liyourageis19 2预定义常量和类型符号常量定义 用一个标识符来表示一个常量 注意 符号常量在使用之前一应要首先声明 符号常量声明语句的格式为 const数据类型说明符常量名 常量值 或数据类型说明符const常量名 常量值 例如 constfloatpi 3 14159265 函数结果主要状态代码 typedefintstatus status是函数的类型 其值是函数结果状态代码 consttrue 1 constfalse 0 constOK 1constERROR 0constINFEASIBLE 1constOVERFLOW 2注意 符号常量在声明时必须要赋初值 而在程序中不能改变其值 符号常量的优点 有利于提高程序的可读性和方便修改 3函数3 1函数的定义 用于完成特定功能或操作的程序模块 一般格式 函数类型函数名 参数表 算法说明语句序列 函数名如 intmax int int 定义有参函数max int return 3 2函数参数形式参数 定义函数时函数名后面括号中的变量名称实际参数 主调函数中调用一个函数时 函数名后面括号中的参数 可以是一个表达式 函数调用时实参与形参应一一对应 参数结合有两种方式 值传递与地址传递 3 3函数的返回值通过语句return 表达式 获得 返回值的类型应与函数类型一致 若无返回值 函数类型应定义为void 3 4函数调用格式 函数名 实参表列 说明 有语句 表达式 函数参数三种调用方式 3 5函数声明如果使用库函数 还应该在本文件开头用 include命令将调用有关库函数时所需用到的信息 包含 到本文件中来 如果使用自定义的函数 而该函数的位置在调用它的函数 即主调函数 的后面 应该在主调函数中对被调用的函数作声明 函数原型的一般形式为 函数类型函数名 参数类型1 参数类型2 3 6函数的递归调用在调用一个函数的过程中又出现直接或间接地调用该函数本身 递归问题的关键 递推公式 递归条件 边界 如 已知Fibonacci数列的第n项为 编写求第n项的递归函数longfib intn n的合法性在主调函数中检测 longf if n 1 n 2 f 1 elsef fib n 1 fib n 2 return f 3 7带缺省参数的函数一般情况下 实参个数应与形参个数相同 C 允许实参个数与形参个数不同 办法是在形参表列中对一个或几形参指定缺省值 或称默认值 格式 函数类型函数名 类型1参数1 类型2参数2 表达式 如 某函数首部 voidfun inta intb intc 100 在调用此函数时如写成fun 2 4 6 则形参a b c的值分别为2 4 6 如果写成fun 2 4 即少写了最后一个参数 由于在函数定义时已指定了c的缺省值为100 因此a b c的值分别为2 4 100 注意 赋予缺省值的参数必须放在形参表列中的最右端 4结构体结构体 不同类型相互关联的数据的有序集合 4 1声明一个结构体类型的一般形式为 struct结构体名 成员表列 如 structstudent intnum charname 20 charsex intage floatscore charaddr 30 结构体名 成员类型名 成员名 域名 说明 1 不要忽略最后的分号 2 structstudent是一个类型名 它和系统提供的标准类型 如int char float等 一样具有同样的地位和作用 都可以用来定义变量的类型 只不过结构体类型需要由用户自己指定而已 3 成员表列 称为 域表 每一个成员也称为结构体中的一个域 成员名命名规则与变量名相同 4 2定义结构体类型变量的方法先定义结构体类型再定义变量如 structstudentstudent1 student2 在声明类型的同时定义变量一般形式为 struct结构体名 成员表列 变量名表列 直接定义结构体类型变量一般形式为 struct 成员表列 变量名表列 4 3结构体变量的引用不能将一个结构体变量作为一个整体进行输入和输出 引用结构体变量中成员的方式 结构体变量名 成员名说明 是成员 分量 运算符 它在所有的运算符中优先级最高 student1 num表示student1变量中的num成员 可以对变量的成员赋值 例如 student1 num 10010 将整数10010赋给student1变量中的成员numstudent1 age 使student1 age中的成员age进行自加运算 4 4结构体变量的初始化与其他类型变量一样 对结构体变量可以在定义时指定初始值 例 对结构体变量初始化 structstudent longintnum charname 20 charsex charaddr 20 a 89031 LiLin M 123BeijingRoad 5引用 1 引用的概念 引用 reference 是C 的一种新的变量类型 它的作用是为一个变量起一个别名 并没有开辟新的存储区 定义方法 类型名不可建立对不同类型变量的引用 例2 了解引用和变量的关系 include includevoidmain inta 10 int 运行结果如下 1001002020 3 引用作为函数参数有了变量名 为什么还需要一个别名呢 C 之所以增加 引用 主要是把它作为函数参数 以扩充函数传递数据的功能 函数调用参数传递方式 值传递与地址传递 C 提供了向函数传递数据的第三种方法 即传送变量的别名 例3 利用 引用形参 实现两个变量的值互换 includevoidswap int 输出结果为i 5j 3 说明 实参传给形参的是变量的地址 也就是使形参a具有变量i的地址 从而使a和i共享同一单元 为便于理解 我们说把变量i的名字传给引用变量a 使a成为i的别名 系统传送的是实参的地址而不是实参的值 这种用法比使用指针变量简单 直观 方便 注 当读者看到 a这样的形式时 怎样区别是声明引用变量还是取地址的操作呢 请记住 当 a的前面有类型符时 如int a 它必然是对引用的声明 如果前面无类型符 如 a 则是取变量的地址 6指针6 1变量的指针 变量在内存中的地址指针变量的定义 基类型 指针变量名 如 int p i 3 p 指针法 a i or p i 2020 1 7 23 2 二维数组指针定义格式 指针类型名 指针名 常数 如 inta 3 4 p 4 a 对数组元素的引用 下标法 a i j orp i j 指针法 a i j or p i j 6 3字符串指针定义格式 char 指针名 如 charstr C Program char p p str 例4 将两个字符串合并为一个字符串 include includevoidmain charstr 100 Welcometo char ps C inti len len strlen str for i 0 ps i i str len i ps i cout Theresult str endl 6 4指针数组定义格式 类型名 数组名 数组长度 如 int p 4 b 10 inta 5 c p 0 例5 使用指针数组对若干个字符串按从小到大排序输出 include include voidmain char p 5 C C JAVA Delpha ASP inti j k char ch for i 0 i0 k j if k i ch p k p k p i p i ch for i 0 i 5 i cout p i endl 6 5函数指针函数是一段程序 运行时与变量一样占用内存空间 有一个起始地址 即指向此函数的指针 定义格式 类型名 函数名 形参表 函数名 如 若有函数 intfun int char 则 int p int char p fun orint p int char fun p为指向函数fun的指针注 函数名为指针常量 不可改变 函数指针一般用于作函数参数 用来简化有规律的函数调用 例6 使用函数名作函数参数 include intminus inta intb returna b intplus inta intb returna b intmultiply inta intb returna b intdivide inta intb returna b intop inta intb int p int int voidmain cout 5 3 op 5 3 plus endl cout 5 3 op 5 3 minus endl cout 5 3 op 5 3 multiply endl cout 5 3 op 5 3 6 6返回指针的函数函数的返回值可以是指针 称为指针函数 定义格式 类型名 函数名 形参表 函数体 例7 有若干学生成绩 要求输入学生的序号 输出学生的全部成绩 使用指针函数 includevoidmain floatscore 4 60 70 80 90 56 66 87 77 65 99 75 68 float search float p 4 intn float q inti m cout m cout ThescoresofNO m are endl q search score m for i 0 i 4 i cout q i cout endl float search float p 4 intn return p n 1 6 7结构体指针结构体指针指结构体变量所占据的内存段的起始地址 例8 结构体指针应用示例 include include includestructstudent longnum charname 20 charsex floatscore voidmain studentstu 1 stu 2 student p p 通过指针访问结构体成员 p 成员名p 成员名 指向运算符 7内存动态分配与释放 运算符new和delete C 提供了较简便而功能较强的运算符new和delete来取代malloc calloc和free函数 1 new运算符简单变量动态存储格式为 指针变量 new类型名 初值表列 例如 int p newint 开辟一个存放整数的空间 返回一个指向整型数据的指针int p newint 100 开辟一个存放整数的空间 并指定该整数的初值为100float p newfloat 3 14159 开辟一个存放浮点数的空间 并指定该浮点数的初值为3 14159 将返回的指向实型数据的指针赋给指针变量p 数组动态存储格式 指针变量 new类型名 元素个数 如 intn 5 p newint n char ps newchar 10 开辟一个存放字符数组的空间 该数组有10个元素 返回一个指向字符数据首字符的指针float q 4 newfloat 5 4 申请可存放5行4列浮点数的空间注 用new分配数组空间时不能指定初值 2 delete运算符格式 delete 指针变量作用 释放由new申请到的内存空间 如 deletep delete ps q 加方括号 表示对数组空间的操作 例9 动态开辟空间以存放一个结构体变量 include includestructstudent charname 10 intnum charsex voidmain student p newstudent strcpy p name WangFun p num 10123 p sex M coutnamenum coutsex endl deletep 例10 链表创建与遍历 include includestructstudent longnum floatscore student next intn 0 统计结点个数voidmain voidprint student head 函数声明student creat student head head creat print head student creat 创建链表 student head p1 p2 p1 p2 newstudent cout p1 num p1 score head NULL while p1 num 0 n if n 1 head p1 elsep2 next p1 p2 p1 p1 newstudent cin p1 num p1 score p2 next NULL returnhead voidprint student head 遍历链表 student p coutnumscorenext while p NULL 8枚举定义枚举类型的一般格式 enum枚举类型名 枚举元素表 例如 enumbool true false 说明 1 枚举元素为符号常量 不能改变其值 2 枚举常量的值为整数 按定义时的顺序依次为 0 1 2 enumweekday Sun Mon Tue Wed Thu Fri Sat enumweekday Sun 7 Mon 1 Tue Wed Thu Fri Sat 3 枚举常量可赋给枚举变量 但不可将一整数赋给枚举变量weekdayday day Mon cout day 结果为14 枚举值可以比较大小 例11 由序号求枚举值 include 演示voidmain inti typedefenum a 1 b c d character charactergc cout i gc character i switch gc c