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