什么是数据结构.doc

文档介绍：第一章绪论
1--1 什么是数据结构
例子
学生成绩表(线性表)
学号姓名语文数学物理化学
001 张三 76 80 90 87
002 李四 65 74 80 60
003 王五 59 70 76 60
例二对奕问题(树结构)
例三多叉路口交通灯的管理问题(图的结构)
C D
B
E
A
AC
AB
AD
BD
BC
BA
DC
DB
DA
ED
EA
EC
EB
数据结构: 带有结构的数据元素集合及其运算称为数据结构.
结构: 数据元素间的关系。
基本概念和术语
数据: 对客观对象的抽象。
数据元素: 数据的基本单位。
数据对象:
有相同性质的数据元素的集合。
数据结构:
结构: 数据间的关系。
基本结构(四类)
集合
线性结构
树形结构
图状结构(网状结构)
数据结构的形式定义:
(D,S): 其中D为数据元素有限集
S为D上关系的有限集。
逻辑结构: (逻辑关系)
物理结构: (存储结构)在计算机中的表示
数据元素间的关系在计算机中的两种表示方法
顺序映象-à顺序存储结构
非顺序映象-à链式存储结构
数据类型: 一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型(ADT): 一个数学模型以及定义在该模型上的一组操作可用(D,S,P)表示, 其中D为数据对象S为D上的关系集P为对D的基本操作。
ADT描述的一些说明及实现(P10)
算法算法的描述和算法分析
一、算法是解决某一特定问题的有限运算序列,其特性有:
有穷性
确定性
能行性
输入
输出
二、描述算法的约定
每一个算法以函数形式给出(类的概念)。
有关结点的类型定义,全局变量的说明等均在算法之前说明。
C的函数可直接调用
NULL空指针#define 预定义。
如求 10!
#define M 10
int p(int x)
{ int i,s;
for (i=1,s=1;i<=10;i++)
s=s*i;
return(s);}
三、算法分析
时间、空间复杂性(时间消耗、空间占用量)
渐近时间复杂度:T(n)=O(f(n))
线性表
线性表的特点:
存在唯一的一个被称作”第一个”的数据元素。
存在唯一的一个被称作”最后一个”的数据元素。
除第一个外,集合中的每一个数据元素均只有一个前驱。
除最后一个外,集合中的每一个数据元素一均只有一个后继。
线性表的类型定义
一、线性表
线性表: 具有上述四个特点的n个数据元素的有限序列
数据项à记录à文件
线性表的长度
注:线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短
其运算有:存取,插入,删除,查找,合并,分拆,排序,求表的长度。
二、抽象数据类型
ADT List {
数据对象:D={ai | aiÎElementSet , i=1,2,…n, n>=0}
数据关系:R1={<ai-1,ai> | ai-1,ai ÎD, i=2,3,….n}
基本操作: (略) }
三、例子
分别表示集合A和B的线性表LA和LB,现需求AÈB,即在LA中插入LB中在LA中没有的元素()
四、
已知两个数据元素已按不减有序排列的线性表LA和LB,现要它们归并为一个新的线性表LC,且LC的数据元素也是按不减有序排列。
如LA=(3,5,8,11)、LB=(2,6,8,9,11,15,20)
则 LC=(2,3,5,6,8,8,9,11,11,15,20)
()
2—2 线性表的顺序表示和实现
一、线性表的顺序表示
1)、线性表的顺序表示就是用一组地址连续的存储单元依次存储线性表的数据元素。
2)、对于线性表 a1 ,a2,…ai…,an
如果每个元素占用s个存储单元, 则ai+1的位置为:
LOC(ai+1)=LOC(ai)+s
LOC(ai+1)=LOC(a1)+(i-1)*s
(存储结构示意图P22)
二、线性表的实现
1、动态分配顺序存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem ;
int length ;
int listsize ;}SqList ;
2、基本操作
1)构造一个空表()
2)插入算法(P24)
3)删除算法(P24)
4)算法的复杂性分析(P25)
线性表的链式表示与实现
2—3--1线性链表
1、线性链表