文档介绍：单片机原理与应用
2018/1/24
第4部分数据结构(压缩版)
——1
学习内容和目标
数据结构的基本知识:指出方向
线性表的概念链表
注意:
思维一定要开阔一些,多问为什么。
允许不用举手,并随时打断,向我提任何和课程相关的问题。
2018/1/24
2
本节学习目标
引论
当前看待程序和软件的主流观点:
程序= 算法(处理问题的策略) + 数据结构(问题的数学模型)
软件工程的观点:软件= 程序+文档
数据结构:由若干特性相同的数据元素构成的集合,且在集合上存在一种或多种关系。即数据的组织形式。
2018/1/24
3
1数据结构概述
数学
代数系统
硬件
计算机系统设计
软件
计算机程序设计
数据结构
编码理论
数据类型
数据表示
数据运算
数据结构
数据存取
三个内容:逻辑结构、存储结构、基本操作(运算)
数据类型:一个值的集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。
抽象数据类型(ADT)
逻辑结构:S={ D , R } ;D表示数据元素的集合,R表示元素间关系的集合
四种结构:集合、线表、树、图
R1={φ}
R2={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>}
R3={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<c,g>}
R4={<a,e>,<b,c>,<c,a>,<e,f>,<f,g>,<c,f>}
2018/1/24
4
引论(续1)
a
b
c
e
f
g
a
b
c
d
e
f
g
a
b
c
d
e
f
g
a
b
c
e
f
g
存储结构:数据元素的表示及元素之间关系的表示。顺序存储结构、链式存储结构
基本操作及其实现:对数据元素的修改、增加、删除,移动等。
本课程的讲述特点、目标、和方法:
在同学们的原有基础上,对数据结构进行概括;
由于时间有限,并且是在单片机课程中,因此将挑选几个主要的数据结构;
采用压缩的方式讲述数据结构,关键在于给出思想和方法;
通过指导培养自学能力;
掌握几种数据结构的思想,并能够处理相关问题;
2018/1/24
5
教学方法和目标
主要涉及的数据结构:
算法:排序和查找(其他略)
有穷性---执行了有限条指令后一定要终止。
确定性(无二义)---
可(能)行性---
输入数据---
输出数据---
2018/1/24
6
当前的数据结构
概念和定义
线性结构:
有且仅有一个头元素
有且仅有一个尾元素
除第一个数据元素外,其余的数据元素有且仅有一个直接前驱
除末尾数据元素外,其余的数据元素有且仅有一个直接后继
线性表的概念:
线性表是n(n>=0)个数据元素的有限序列。
记作:(a1,a2,a3,...ai,...,an) , 下标i表示数据元素在线性表中的位序。
n定义为线性表的长度;n为0表示该线性表为空表。
线性表中的数据元素可以是一个数、一个符号或由多个数据项所构成的。
2018/1/24
7
2 线性表
线性表的抽象数据类型(ADT)定义:
2018/1/24
8
线性表的概念和定义(续1)
ADT list
{
数据对象:
数据关系:
基本操作:
InitList(&L) /*初始化线性表*/
DestroyList(&L) /*销毁线性表*/
ListEmpty(L) /*判断是否为空线性表*/
......
}
例:利用线性表求集合A∪B:
集合A和B分别用线性表LA和LB表示
依次扫描LB的元素,若不存在LA中,则插入LA中
2018/1/24
9
线性表的示例
void union(List &La,List Lb)
{
La_len=ListLength(La); Lb_len=ListLength(Lb)
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,e);
if(!LocateElem(La,e,equal))
{
ListInsert(La,++La_len,e);
}
}
}
线性表的顺序表示-随机存取的存储结构
用一组连续的存储单元依次存储线性表中的数据元素。
表中第一个元素的起始位置称为顺序表的基地址。
线性表中任一数据元素的存储位置为(s表示每个数据元素所占存储空间大小。i表示数据元素的位序):
由于线性表的长度可变,因此对顺序表的定义除了需要一个存储元素的空间以外,还需要两个数据成员:其中一个指示顺序表中已有的元素个数length,另一个指示该顺序表允许存放的数据元素个数的