陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn
数据类型 整型(short,int,long,unsigned) 数值类型 单精度型(float) 实型 双精度型(double) 基本类型 字符型(char) 枚举类型(enum) 数组类型([ ]) 数据类型 构造类型 结构体类型(struct) 共用体类型(union) 指针类型() 空类型(void)
数据结构 计算机内部数据的组织形式和存储方法 逻辑结构：数据元素的逻辑关系 物理结构：在计算机中的存储方法 1001 Ningbo Zhejiang China …… 1004 Hangzhou 1001 Ningbo Zhejiang China 1002 Hangzhou 1004 Nanjing Jiangsu 1005 Chicago IL USA
数据结构 线性表 顺序表 链表 线性结构 栈 队列 树结构 图结构 操作系统->进程管理 服务器->进程线程管理 线性表 顺序表 链表 栈 队列 线性结构 操作系统->进程管理 服务器->进程线程管理 人工智能->博弈树 数据挖掘->决策树 多媒体技术->哈夫曼树 树结构 图结构 人工智能->神经网络，贝叶斯网络
线性表的特点 1、同一性 2、有穷性 3、有序性 数组、字符串、矩阵、堆栈、队列、… 满足线性条件 同类数据元素 有限个数据元素 相邻元素存在序偶关系<ai,ai+1> 数组、字符串、矩阵、堆栈、队列、… 满足线性条件
以一维数组为基础建立，数组元素可以是任何类型 线性表的顺序存储（顺序表） 以一维数组为基础建立，数组元素可以是任何类型 创建：申请固定或指定长度的存储空间 输入：依次输入每个元素的内容 长度：顺序表中元素的个数 查找：按序号/内容查找 插入：位置向后移动 删除：位置向前移 输出：依次输出每个元素的内容 销毁：释放存储空间 include <string.h> char * strcpy ( char * dest, const char * src ); size_t strlen ( const char * str ); const char * strchr ( char * str, int character ); char * strstr ( char * str1, const char * str2 );
线性表的抽象数据类型定义 ADT LinearList{ } 数据元素：D={ai|ai∈T，i=1,2,…,n,n≥0,T为某一数据类型} 结构关系：R={<ai,ai+1>|ai,ai+1 ∈T, i=1,2,…,n-1} 基本操作： ①InitList(L)：操作前提：L为未初始化线性表。操作结果：将L初始化为空表。 ②ListLength(L)：操作前提：线性表L已存在。操作结果：返回表中元素个数。 ③GetData(L,i)：操作前提：表L存在，且i有效。操作结果：返回L中第i个元素的值。 ④InsList(L,i,e)：操作前提：表L存在，e合法，i有效。操作结果：在L中第i个位置前插入新元素e，L长度加1. ⑤DellList(L,i,e)：操作前提：表L存在且非空。操作结果：删除L中第i个元素，并用e返回其值，L的长度减1. ⑥Locate(L,e):操作前提：表L已存在，e合法。操作结果：若L中存在e,则将当前指针指向元素e所在位置且返回TRUE，否则返回FALSE. }
实例2.1 1168 查找学生信息 Description Input Output Sample Input Sample Output 1168 查找学生信息 Description 将n个学生信息录入到数组中，包括学生的学号和期末考试总成绩，查找某学号学生的相应信息。 Input 第一行输入n(n<100)，表示有n个学生; 后面n行输入这n个学生的信息，内容分别为学号和分数，接下来一行输入所要查询的学生学号。 Output 输出该学号学生的成绩，如无匹配学号，则输出“No found!”。（输出不包含引号） Sample Input 4 084110 100 084111 98 084112 97 084113 99 084111 Sample Output 98
线性表的顺序存储（顺序表） 优点： 缺点： 1、不需要额外空间来表示结点的逻辑关系 2、随机存储方便 1、插入/删除效率低 2、需事先确定存储规模
改进的顺序表
实例2.2 用改进的顺序表完成实例2.1
作业 1201 1347