C语言程序设计 清华大学郑莉安颖莲 第十一讲 数据结抱基础 (一) ①《计算机程序程序设计基础》第10章 ② 《数据结构》（严蔚敏等编著）第1、2章
C语言程序设计 清华大学 郑莉 安颖莲 1 第十一讲 数据结构基础 （一） ①《计算机程序程序设计基础》第10章 ②《数据结构》（严蔚敏 等 编著）第1、2章
C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 基本概念和术语 算法和算法分析 线性表的类型定义 线性表的顺序表示和实现 ·线性表的链式表示和实现 ·单链表算法举例 Page 2
C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 基本概念和术语 • 算法和算法分析 • 线性表的类型定义 • 线性表的顺序表示和实现 • 线性表的链式表示和实现 • 单链表算法举例
C语言程序设计 清华大学郑莉安颖莲 “数据结构》的基本概念 “数据结构”在计算机科学中的地位 基本概念和术语 数据 ·对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中 并被计算机程序处理的符号的总称。 -数据元素 数据的基本单位，一个数据元素可由若干数据项组成，数据项是 数据的不可分割的最小单位。 数据对象 ·性质相同的数据元素的集合，是数据的一个子集。 - 数据结构 ·是相互之间存在一种或多种特定关系的数据元素的集合。 ·四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。 数据类型 ·是一个值的集合和定义在这个值集上的一组操作的总称。 高级语言中的数据类型可分为两类；原子类型、结构类型。P3
C语言程序设计 清华大学 郑莉 安颖莲 Page 3 “数据结构”的基本概念 • “数据结构”在计算机科学中的地位 • 基本概念和术语 - 数据 • 对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中 并被计算机程序处理的符号的总称。 - 数据元素 • 数据的基本单位，一个数据元素可由若干数据项组成，数据项是 数据的不可分割的最小单位。 - 数据对象 • 性质相同的数据元素的集合，是数据的一个子集。 - 数据结构 • 是相互之间存在一种或多种特定关系的数据元素的集合。 • 四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。 - 数据类型 • 是一个值的集合和定义在这个值集上的一组操作的总称。 • 高级语言中的数据类型可分为两类：原子类型、结构类型
C语言程序设计 清华大学郑莉安颖莲 算法和算法分析 算法 一对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。 ·算法的五个重要特征 - 有穷性、确定性、可行性、零个或多个输入、一个 或多个输出。 ·算法的设计要求 正确性、可读性、健壮性、效率与低存储量需求。 Page 4
C语言程序设计 清华大学 郑莉 安颖莲 Page 4 算法和算法分析 • 算法 - 对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。 • 算法的五个重要特征 - 有穷性、确定性、可行性、零个或多个输入、一个 或多个输出。 • 算法的设计要求 - 正确性、可读性、健壮性、效率与低存储量需求
C语言程序设计 清华大学郑莉安颖莲 线性表的定义和基本操作 ·线性表是n个数据元素的有限序列。 。 线性表的基本操作 -构造一个空线性表 一销毁一个线性表 -将一个线性表重置为空表 -判断线性表是否为空 -求线性表的元素个数 求线性表的第i个元素的值 -在线性表中查找第一个满足指定条件的元素 求指定元素的前驱 求指定元素的后继 在线性表的第i个元素之前插入一个新元素 删除线性表的第i个元素 遍历线性表 Page 5
C语言程序设计 清华大学 郑莉 安颖莲 Page 5 线性表的定义和基本操作 • 线性表是 n 个数据元素的有限序列。 • 线性表的基本操作 - 构造一个空线性表 - 销毁一个线性表 - 将一个线性表重置为空表 - 判断线性表是否为空 - 求线性表的元素个数 - 求线性表的第i个元素的值 - 在线性表中查找第一个满足指定条件的元素 - 求指定元素的前驱 - 求指定元素的后继 - 在线性表的第i个元素之前插入一个新元素 - 删除线性表的第i个元素 - 遍历线性表