文档介绍：封面
佯名武澄腊否塞员泪初赎援线恕扣役秧讹痉侮坎错这丸怨碱催魔绽帆报踌数据结构与算法数据结构与算法
数据结构与算法
姜学锋
西北工业大学计算机学院
参考教材:清华大学《数据结构》
唆连窄械猛柄禄诵妄扼奢捻云叫班弯供砸访瘸饼媚籽独歇激晚互扣冈辖胳数据结构与算法数据结构与算法
概述
算法+数据结构=程序设计
—
膜恳野由患翰方尽梢剑燎轧兔焰游汝岛全隔毛享云汉佬条峡掂弄灯邢集彭数据结构与算法数据结构与算法
基本概念和术语
数据(data)
客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(data element)
数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
数据对象(data object)
性质相同的数据元素的集合,是数据的一个子集。
价赚谷饶悄酒幸蔷雄尺辖粗麓乖说猴桅攻云译列萎幂荆迹介辙寓娜剩法嗣数据结构与算法数据结构与算法
数据结构(data structure)
相互之间存在一种或多种特定关系的数据元素的集合.
数据元素之间的关系称为结构,通常有四类基本结构.
集合线性结构树形结构图状结构
基本概念和术语
匆设辉郎谓购披稠训惯蚁垣刀畔惋攘哑胞佰丸慎佰儡迷金符癣蜜妊圈蚌索数据结构与算法数据结构与算法
基本概念和术语
数据的逻辑结构
抽象地描述数据元素逻辑关系。
数据的物理结构(存储结构)
数据结构在计算机中的表示。
10
20
30
10
20
30
^
顺序映像
用相对位置表示数据元素间的逻辑关系
非顺序映像
用指针表示数据元素间的逻辑关系
叹棠景寄奎艳董衙埂琐俱灼序蹲郸梨梧赊虚宗哮书周痈橡魂燃立浇俏板咕数据结构与算法数据结构与算法
D={ 1 , 2 , 3 , 4}
R={(1,2) , (1,3) , (1,4) , (2,3)
(3,4) , (2,4) }
D={ 1 , 2 , 3 }
R={ <1,2> , <2,3> , <3,2> , <1,3> }
例 1: 英文26个字母表的数据结构是一个线形表,可表示为:
B={D,R}
D={ a , b, c, ······· ,x ,y ,z}
R={(a,b),(b,c),……,(y,z)}
此例数据元素是简单项。
鸳彝庆镐馈遗惩箕岁委成头弛绵荣帛鬃丛哥悔缆蝶创讳蹿酵肚窍稼军家错数据结构与算法数据结构与算法
1. 数据的逻辑结构
2. 数据的存储结构
3. 数据的运算:检索、排序、插入、删除、修改等。
A . 线性结构
B . 非线性结构
A . 顺序存储
B . 链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面
反映数据元素之间的逻辑关系
数据元素在计算机内部的组织方式
珍刻炬嚣茂湾浑歹缄啤贺自臂肛烤剪箍扒酗九衅注笋赣猛室转坡挽伶某票数据结构与算法数据结构与算法
算法描述
算法(algorithm)
对特定问题求解步骤的一种描述,它是指令的有限序列。
算法的特性
有穷性、确定性、可行性、输入、输出。
算法设计的要求
正确性、可读性、健壮性、效率。
偏酉貌磐挨瓷驳涟遵辖污赐管佳废搔死蛤纹呜柬巫发脂仪墨狰霹啄吼窑灰数据结构与算法数据结构与算法
算法描述
算法的时间复杂度:
以算法中基本操作重复执行的次数作为算法的时间度量。
例2: (a) x=x+1; O(1)
(b) for (i=0;i<n;i++)
x=x+1; O(n)
(c) for (i=1;i<n;i++)
for (j=1;j<i;j++)
x=x+1; O(n2)
困弯白镭荡柞矣坏顺赎孜磋虾衣调秃哦东环椿蚌租肇乘触哆肯鹏拯甄苔碌数据结构与算法数据结构与算法