Download presentation
Presentation is loading. Please wait.
1
陈海明 副教授 信息学院 计算机系 http://www.chenhaiming.cn
电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
2
数据类型 整型(short,int,long,unsigned) 数值类型 单精度型(float) 实型 双精度型(double) 基本类型
字符型(char) 枚举类型(enum) 数组类型([ ]) 数据类型 构造类型 结构体类型(struct) 共用体类型(union) 指针类型() 空类型(void)
3
数据结构 计算机内部数据的组织形式和存储方法 逻辑结构：数据元素的逻辑关系 物理结构：在计算机中的存储方法 1001 Ningbo
Zhejiang China …… 1004 Hangzhou 1001 Ningbo Zhejiang China 1002 Hangzhou 1004 Nanjing Jiangsu 1005 Chicago IL USA
4
数据结构 线性表 顺序表 链表 线性结构 栈 队列 树结构 图结构 操作系统->进程管理 服务器->进程线程管理
线性表 顺序表 链表 栈 队列 线性结构 操作系统->进程管理 服务器->进程线程管理 人工智能->博弈树 数据挖掘->决策树 多媒体技术->哈夫曼树 树结构 图结构 人工智能->神经网络，贝叶斯网络
5
线性表的特点 1、同一性 2、有穷性 3、有序性 数组、字符串、矩阵、堆栈、队列、… 满足线性条件 同类数据元素 有限个数据元素
相邻元素存在序偶关系<ai,ai+1> 数组、字符串、矩阵、堆栈、队列、… 满足线性条件
6
以一维数组为基础建立，数组元素可以是任何类型
线性表的顺序存储（顺序表） 以一维数组为基础建立，数组元素可以是任何类型 创建：申请固定或指定长度的存储空间 输入：依次输入每个元素的内容 长度：顺序表中元素的个数 查找：按序号/内容查找 插入：位置向后移动 删除：位置向前移 输出：依次输出每个元素的内容 销毁：释放存储空间 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 );
7
线性表的抽象数据类型定义 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. }
8
实例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 084111 Sample Output 98
9
线性表的顺序存储（顺序表） 优点： 缺点： 1、不需要额外空间来表示结点的逻辑关系 2、随机存储方便 1、插入/删除效率低
2、需事先确定存储规模
10
改进的顺序表
11
实例2.2 用改进的顺序表完成实例2.1
12
作业 1201 1347
Similar presentations
