文档介绍：第七章数据结构
导言
数据结构是计算机软件和计算机应用专业的核心课程。
对于学习计算机专业的其他课程,包括操作系统、编译原理,数据库管理系统、软件工程、人工智能等都是十分有益的。
简单说来,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系的操作等等的学科。
意义地位:数据结构+算法=程序
程序设计的基础
系统软件的核心
钱付兰 安徽大学
数据结构的概念
相关基本概念和术语:
数据--是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符号的总称。是计算机程序加工的“原料”。一般包括数值型数据(整数、实数或复数等)和非数值型数据(字符、文字、图形、图像、声音等)。
数据元素--是数据的基本单位,在不同的条件下,数据元素又可称为元素、结点、顶点、记录等等。
数据对象--是具有相同性质的数据元素的集合。
钱付兰 安徽大学
数据结构的概念
数据结构(Data Structure :DS)--是指互相之间存在着一种或多种关系的数据元素的集合。
在任何问题中,数据元素都不是孤立存在的,而是在它们之间存在某种关系,这种数据元素相互之间的关系称为结构(Structure)。
根据数据元素之间关系的不同特性,通常有下列四类基本结构(逻辑存储):
(1)集合同属于一个集合
(2)线性结构一对一的关系
(3)树形结构一对多之间的关系
(4)图形结构或网状结构多对多之间的关系
钱付兰 安徽大学
数据结构的概念
集合
线性
树
图
四类基本结构的示意图
钱付兰 安徽大学
数据结构的概念
数据结构主要研究的方面:
(或算法)
实现取决于
设计取决于
数据的存储结构可以采用顺序存储、链式存储、索引存储和散列存储等方法。
任何一个算法的设计取决于选定的逻辑结构;而算法的最
终实现依赖于采用的存储结构。
钱付兰 安徽大学
数据结构的概念
顺序存储--逻辑上相邻的元素存储在物理位置相邻的存储单元中。
链式存储--对逻辑上相邻的元素不要求其物理位置相邻,元素之间的逻辑关系通过附设的指针字段来表示。
数据域
d1 d2 …… dn
结点结构:
数据域指针域
d1
...
d2
dn NULL
结点结构:
钱付兰 安徽大学
数据结构的概念
索引存储:存储两部分内容: 数据元素序号和索引表
数据项索引顺序号
12 21 35 2 45 5 10
4 3 2 7 1 6 5
数据项
索引顺序号
序号: 1 2 3 4 5 6 7
散列存储方法:
在数据元素与存储位置之间建立一种存储关系F,根据这
种关系F,已知元素E,就可以得到它的存储地址,
即D=F(E)。
实例:哈希查找中的哈希表
索引表
钱付兰 安徽大学
几种典型的数据结构
线性表
最简单最常见的数据结构。
线性结构的特点是数据元素之间的关系为一一对应的线性关系的结构。
(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,
V,W,X,Y,Z)
字母表是一个表长为26,元素为字符的线性表。
再如,一星期七天的英文缩写表示:
(Sun,Mon,The,wed,Thu,Fri,Sat)是一个线性表,其中的元素是字符串,表的长度为7。
钱付兰 安徽大学
几种典型的数据结构
定义: 线性表是n(n0)个元素的有限序列,通常记为:
表中每个数据元素,除了第1个和最后1个外,有且仅有一个前
趋元素和后继元素。
(a1,a2,…ai-1,ai,ai+1,…,an)
(a1,a2,…ai-1,ai,ai+1,…,an)
前驱
后继
仅有前驱
仅有后继
线性表的存储方式有两种:顺序存储和链式存储
钱付兰 安徽大学