高级语言程序设计第6讲数据的组织结构ppt课件.pptVIP

1 第6讲数据的组织结构 二 一 结构体二 指针和引用三 动态申请存储空间四 不同类型的函数参数总结五 链表六 文件七 联合体与枚举类型 2 一 结构体 如何表示多个不同类型的数据项 这些数据项逻辑上构成一个数据元素 如 每个学生都有学号 姓名每本书都有书号 书名 作者 出版社用结构体类型来表示 3 struct structpoint intx inty structstudent intsNum charname 10 结构体类型声明 声明的是数据类型 不是变量 4 pointp1 p2 对比 inti j studentzhang wang 定义时初始化pointp1 1 1 studentzhang 1 张一 结构体类型变量定义 p1 p1 p1 1 1 zhang 1 张一 整型大小 10个字符大小 5 结构体类型变量的成员变量的引用 p1 xp1 yzhang sNumzhang name即看成普通变量使用scanf d d 6 同一结构体类型变量可以赋值pointp1 1 2 p2 p2 p1 等同于 p2 x p1 x p2 y p1 y 7 例 学生基本信息的组织 学生信息 学号 姓名 出生日期 所属院系 专业完成任务键盘输入30个学生的信息 并屏幕输出 键盘输入月份和日期 查找并输出本年度在给定日期之后过生日的学生信息 8 例 学生基本信息的组织 设计数据结构 每个学生基本信息用结构体描述 9 structDate 日期结构 intyear intmonth intday structStudentInfo 学生信息结构 intnum charname 24 Datebirthday chardepartment 48 charmajor 32 10 数据类型的别名 用户可以为已有的数据类型起别名语法 typedef原数据类型新的数据类型名例如 typedefintxuehao 思考这样做的好处 程序更加清晰易懂日期Date和学生信息StudentInfo结构的另一种定义方式 11 typedefstruct 日期结构 intyear intmonth intday Date typedefstruct 学生信息结构 intnum charname 24 Datebirthday chardepartment 48 charmajor 32 StudentInfo 12 30名学生用数组表示 defineNUM30StudentInfos NUM 13 程序结构设计给出每个函数的定义 包括 功能说明 入口参数 出口参数等 主模块main 输入模块inputIofo 查询处理模块searchInfo 输出模块outputInfo 14 输入模块voidinputInfo StudentInfo 功能 将全部学生信息通过键盘输入到StudentInfo 数组 参数 学生信息数组 返回值 没有 输出模块voidoutputInfo StudentInfo 功能 格式化输出StudentInfo 数组中的全部学生信息 参数 学生信息数组 返回值 没有 查询处理模块voidsearchInfo StudentInfo DATE 功能 查找并输出StudentInfo 数组中 DATE之后过生日的学生信息 参数 学生信息数组 查找关键字 Date返回值 没有 15 依据定义设计函数的流程 编写代码 编写主模块函数的代码 看书P170 程序代码 分析书中设计的优缺点 16 结构体应用例题 P172 键盘输入10个整数 将它们从小到大重新排序 要求输出排序后的结果和排序前的位置数据结构用结构体类型将整数和原始位置绑在一起typedefstruct intdata 整型数值 intpos 原始位置 DATATYPE 算法输入 针对本次任务修改输出 针对本次任务修改排序 用以前的函数 17 例 模拟发扑克牌 数据结构一张扑克牌的表示一副扑克牌的表示算法初始化一副扑克牌洗牌发牌P175 18 二 指针 指针类型变量的定义 int intptr char chptr intptr 0 x0012ff78 一个地址大小 chptr 0 x0012ff70 一个地址大小 指针是变量是地址变量 19 指针类型变量的引用int intptr char chptr inti 0 charc a intptr c的地址赋给chptr 20 intptr 0 x0012ff78 0 x0012ff78 chptr 0 x0012ff70 0 x0012ff70 0 a int intptr char chptr inti 0 charc a intptr c i 21 指针变量所指的值 intptr 30 在格式化输入输出中的应用printf d c intptr chptr scanf d c intptr chptr intptr 30 22 intptr1 intptr2 NULL 指针变量可初始化为空指针int intptr1 i 23 指针比较if intptr2 intptr1 if intptr2 NULL if intptr2 24 指针加减int p data p指向data 0 即 0123456789 data intdata 10 25 例 char strchr char s charc 函数确定某个字符在字符串中出现的位置s是字符串 c要找的字符strchr函数返回指向找到的字符的指针用此函数获取指定字符在字符串中的位置数目chars 1236 87 intp p strchr s s 1 printf 位置在 d n p strchr函数返回指针 指针相减定位位置 26 例 include stdio h include string h intmain intargc char argv charb Goodbye char pb 逆序 27 为什么指针变量也要有类型 指针变量所存地址没有区别但对指针变量所存地址指向的数据的操作不同 不同数据集合上定义的操作不同 如 指针加1的操作 指针可指向各种数据类型 如基本类型 数组 函数 对象 指针等 28 指针与数组 数组名是指向数组第1个元素的指针 但这个指针是常量 charstr program printf c n str 打印pprintf c n str 错printf c n 1 str 对char p p str printf c n p 打印r 29 指针与数组 数组名定位数组元素P184图6 14指针定位数组元素P184图6 15 30 利用指针对数组元素进行操作 intiarray 20 int ptr 方法一for ptr iarray i 0 i 20 i printf d ptr i 方法二for ptr iarray ptr iarray 20 ptr printf d ptr 例6 4P185 31 指针数组例子 打印整型数组指定的行 j 行号 0开始 rowD 行长度 p 指向数组第一个元素的指针voidpr row intj introwD int p inti p p j rowD for i 0 i rowD i printf d p i 32 二维数组与一维指针数组 inta 3 2 a 0 a 0 a 1 a 2 33 二维数组与一维指针数组 inta 3 2 a 0 a 1 a 2 a 0 a 1 a 2 一维数组的首地址 是指针 用指针定位二维数组元素 i代表行 j代表列int ptr a 0 元素 ptr i 列数 j 34 例 P187 defineROWNUM5 defineCOLNUM4inta ROWNUM COLNUM int ptr1 ptr1 a 0 for i 0 i ROWNUM i for j 0 j COLNUM j printf 3d ptr1 i COLNUM j printf n 可替换 ptr1 35 例 P187 int ptr2 COLNUM ptr2 书错 int ptr2 COLNUM 与int ptr2 COLNUM 区别int ptr2 COLNUM 是整型指针的数组int ptr2 COLNUM 指向整型指针的指针数组 36 指针数组 inta 10 int b 3 b 0 b是一个指向指针的指针 0123456789 a b 书学习书P188 例6 5 37 指向指针的指针变量 float p 地址 p 地址 值 main intx p q x 0 p 打印x的值 38 指针与字符串 字符数组名是字符数组首地址 字符串需要有字符串结束符 charname 10 zhang char chptr name printf s name printf s chptr 39 指针与字符串例子 库函数strcmp intstrcmp char s1 char s2 while s1 直到s1字符串结尾才falseif s1 s2 return s1 s2 else s1 s2 return0 40 例子 找出程序的错误 main char p s 80 p s do gets s while p printf c p while strcmp s done 41 例子 正确答案 main char p s 80 do p s gets s while p printf c p while strcmp s done 42 指向结构体变量的指针 定义structStudent intnumber char next 使用Studentzhang p zhang 1 zhangbo p 43 例 选举问题 选举问题 某部门 需要由全体员工推选一名办公室主任 假设有10名候选人 编程序依据每个候选人的得票数量 得票最多当选 给出选举结果包括候选人编号和得票数 定义结构体 structCandidate intnumber 候选人号码intvote 候选人得票数 44 intmain Candidatedata NUM CandidateMySelected input data NUM MySelected max data NUM output MySelected return0 45 查找得票最多的候选人 参数 返回值 Candidatemax Candidatevalue intn inti Candidateselected selected vote value 0 vote selected number value 0 number for i 1 iselected vote selected vote value i vote selected number value i number returnselected 46 voidoutput Candidateselected printf 当选者是 d候选人 得票数 d n selected number selected vote return voidinput Candidatevalue intn inti printf 请输入 d个候选人的号码 n for i 0 i n i scanf d 47 结构体成员是结构体变量的指针 structnode intdata node next nodea p a 1 NULL p 48 三 动态申请存储空间 库函数中动态申请和释放存储空间的函数 包含 stdlib hvoid malloc intsize 申请voidfree void p 释放例 int ptr int malloc sizeof int 20 free ptr 为什么叫动态内存分配 49 数组 inta 10 静态内存分配动态申请内存空间存储数组int ptr int malloc sizeof int 10 比较 程序运行到此语句才分配内存空间必须释放 注意内存泄漏 50 例6 6 P190 构造杨辉三角形 a 分析题目 设计数据结构 一维整型指针数组 动态生成整型数组空间 51 四 引用 引用类型变量定义 int 52 与地址相关的运算符 int p 声明p是一个int型指针inti 0 int 53 五 再谈函数和函数参数 值传递 变量值做函数参数 voidexchang1 intx inty ints s x x y y s main intt1 1 t2 2 exchange1 t1 t2 Exchange1中对x y的改变不影响t1 t2的值 实际没有完成交换功能 结论 值传递时 被调用函数中对参数值的改变 不影响调用它的函数实参的值 54 地址传递 指针变量做函数参数 voidexchang3 int x int y ints s x x y y s main intt1 1 t2 2 exchange3 Exchange3中对x y所指值的改变使t1 t2的值发生改变 完成了交换功能 结论 地址传递时 被调用函数中对参数值的改变 将影响调用它的函数实参的值 55 引用变量做函数参数 voidexchang2 int Exchange2中对x y的改变使t1 t2的值发生改变 完成了交换功能 结论 地址传递时 被调用函数中对参数值的改变 将影响调用它的函数实参的值 56 数组做函数参数 voidexchang4 char a char b chars 5 strcpy s a strcpy a b strcpy b s main chart3 5 aaa chart4 5 bbb exchang4 t3 t4 Exchange4中对a b的值改变使t3 t4的值发生改变 完成了交换功能 57 利用函数返回值例题 intmain chara while 1 scanf c intfun char 58 指针型函数 函数的返回值为指针 P199代码 char strsub char str intstart intlen inti num char p if strlen str start returnNULL if strlen str start len num strlen str start elsenum len p char malloc sizeof char num 1 for i 0 i num i p i str start i p i 0 returnp 59 选举的例子 教育在线课件资料中有完整的例子 intmain intn NUM int data intMySelected input intinput int value inti value int malloc sizeof int NUM if value return 1 1代表申请存储空间失败printf 请输入 d个整型数 NUM for i 0 i NUM i scanf d value i return0 函数成功返回 60 错误例子 错在哪里 intmain intn NUM int data intMySelected input data MySelected max data n output MySelected return0 intinput int value inti value int malloc sizeof int NUM if value return 1 1代表申请存储空间失败printf 请输入 d个整型数 NUM for i 0 i NUM i scanf d value i return0 函数成功返回 61 六 链表 目的 练习指针 初识数据结构 需要存储数据 a1 a2 an 使用怎样的数据结构 答案 数组 intdata N 如果元素的个数在 1 n 之间动态变化 甚至可能超过n 使用怎样的数据结构 答案 动态生成数组 p int malloc sizeof int N 仍然要确定存储空间大小 使用链表结构 62 单链表 链表特点 不必预知元素多少相邻元素存储空间不必连续数组特点 预知元素多少 且变化不大的连续的存储空间 a1 L a2 an 63 构建单链表分析必须有L 称之为头指针链表中每个元素 称之为结点 每个结点必须存储数据和指向下一个结点的指针最后一个结点 没有后继 为空指针空的单链表暂时没有元素构建单链表基础 a1 L a2 an L NULL 64 结点的定义 例如元素为整型数据structnode intdata node next 由此联想数据处理操作 循环开始 头指针指向第一个元素循环中 前驱指向后继循环结束 空指针 a1 L a2 an 65 构建单链表 方法一 尾插法总是插入到当前链表的表尾 直到读入结束标志为止 正序输入数据 L 在此插入 思路 定义头指针 建立a1结点 赋头指针 建立后面结点插入链表尾 66 voidCreateList E node L 正序输入元素的值 建立单链表L node p s L node malloc sizeof node scanf d CreateList E 67 带头结点的单链表 为了使所有元素统一处理方式 专门加一个头结点带头结点的空链表 L L 68 voidCreateList E node L 正序输入元素的值 建立带头结点的单链表L node p s L node malloc sizeof node L next NULL 先建立一个带头结点的单链表p L while 结束条件表达式 s node malloc sizeof node scanf d CreateList E 69 构建单链表 方法二 头插法该方法从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的头指针上 直到读入结束标志为止 L 在此插入 应逆序插入 头结点 70 voidCreateList L node L 逆序输入n个元素的值 建立带头结点的单链表L node p L node malloc sizeof node L next NULL 先建立一个带头结点的空的单链表for i n i 0 i p node malloc sizeof node 生成新结点scanf d createList L 体会有头结点的好处 71 例 计算链表结点的个数 intListLength node L 带头结点 node p p L intlen 0 for p NULL p p next len returnlen L 72 插入链表结点 在第i个元素前插入一个新元素x首先找到ai 1的存储位置p生成一个数据域为x的新结点 s插入过程先做 s next p next再做 p next s P P S ai 1 ai 1 2 73 intListInsert L node L inti intx node s p L intj 0 while p L 74 删除链表结点 删除运算是将表的第i个结点删去 思路首先找到ai 1的存储位置pq p next 为处理被删除结点做准备删除操作 p next q next处理q所指结点 L p q 75 intListDelete L node L inti int 76 例6 9 P203 约瑟夫环 数据使用没有头结点的循环单链表每个结点数据 每个人的序号 当然有指向下一个结点的指针 功能建造循环链表游戏的过程打印输出序列 一边游戏一边打印 将结果保存之后一起打印 77 例6 10 P206 学生考试成绩处理 数据学生信息采用数组 是结构体数组 每个数组元素有数据 学生姓名 指向成绩链的指针 学生选修每门课程和成绩 一个学生一个单链表 链表结点数据有 课程名 成绩 单链表指针 功能见P206图6 31定义每个模块中函数 函数功能 函数名 参数 返回值 78 例 有序数组插入元素 在第i个元素之前插入元素x a为整型数组首地址 length为当前数组元素个数 x为元素值 intinsertSq int a int 79 例 有序数组删除元素 删除第i个元素 指放入参数x a为整型数组首地址 length为当前数组元素个数 intdelSq int a int 80 数组与单链表的优缺点总结 数组预知数据多少必须用连续存储空间支持随机存取插入删除操作需要移动大量元素 单链表不需预知数据量不需连续存储空间不支持随机存取插入删除操作不需移动大量元素 81 不用指针实现单链表 有些语言没有提供指针类型 82 七 文件 持久化存储数据外存数据以文件形式组织依组织形式不同 分为两类 文本文件二进制文件 83 文本文件 以字符为单位 每个字符一个字节 存放ASCII码例如 00111000001101110011011000110101存放8765有若干文本行 每行以换行符 n 结束文本文件结束标志是EOF 它的值为 1 84 二进制文件 以二进制形式存储数据例如 数值8765存放 0010001000111101需要两个字节存储这个数值所以 二进制文件也可以看成字节序列 称为字节流 有了这一特征 也将文件称为流式文件 85 文件指针 FILE结构 一个内存中的FILE结构对应一个磁盘文件 FILE结构声明在stdio h中 见P211页定义 使用想文件 先定义文件指针FILE FILE fp 86 打开文件 打开文件 系统自动创建一个FILE结构 并将提供指向此结构的指针 完成库函数 FILE fopen char fname char mode FILE fp if fp fopen c file dat r NULL printf n不能打开文件 87 文件操作模式 mode参数的值 见P212表 88 关闭文件 打开文件后必须关闭文件 否则可能造成文件指针泄漏或文件数据丢失 完成库函数 成功返回0 否则为非0值intfclose FILE fp if fclose fp printf n文件关闭有错误 89 文件读写 打开文件后可对文件进行读写操作 库函数中有若干文件读写函数 字符读写操作字符串读写操作数据块读写操作格式化读写操作 90 字符读写操作 intfgetc FILF fp 在stdio h中从fp所指文件的当前位置读取一个字符 并将文件位置指示器增大 返回值为字符转换的整数 到达文件尾时返回值为EOFintfputc intc FILF fp 在stdio h中将字符c写到fp所指的文件的当前位置 并将文件位置指示器增大 返回值为所写的字符的值 91 字符读写操作 例题 读取一个文本文件 并将内容显示 includeintmain FILE fp intch if fp fopen e a txt r NULL printf 打不开文件 return 1 92 ch fgetc fp while ch EOF putchar ch ch fgetc fp fclose fp return0 93 字符读写操作 例题 文本文件拷贝 includeintmain FILE fp1 fp2 intch if fp1 fopen e a txt r NULL printf 打不开旧文件 return 1 94 if fp2 fopen e b txt w NULL printf 打不开新文件 return 1 while ch fgetc fp1 EOF fputc ch fp2 fclose fp1 fclose fp2 95 字符串读写操作 char fgets char str intnum FILF fp 在stdio h中从fp中读取至多num 1个字符 放入str指向的字符数组 并在最后一个字符位置加上 0 遇到换行符或EOF时读取也停止 操作成功 返回str 失败时返回空指针 intfputs char str FILF fp 在stdio h中把str所指的字符串的内容写入fp文件流 但不写 0 操作成功 返回0 失败时为非0值 96 字符串读写操作 例题 读取一个文本文件 并将内容显示 includeintmain inti charlines 1024 80 FILE fp intch if fp fopen e a txt r NULL printf 打不开文件 return 1 97 for i 0 feof fp i fgets 98 字符串读写操作 例题 文本文件拷贝 includeintmain inti charlines 1024 80 FILE fp1 fp2 intch if fp1 fopen e a txt r NULL printf 打不开旧文件 return 1 99 if fp2 fopen e b txt w NULL printf 打不开新文件 return 1 for i 0 feof fp1 i fgets 100 数据块读写操作 intfread void buffer intsize intcount FILE fp intfwri