文档介绍：算法与数据结构
主讲教师: 葛日波
联系方式: teacher_******@dlut.
82172108
办公室: 教学楼1904
柒毙士气划奸惶华冉脉儒榔肉踞饮俩颠潮夏措阻酉斋讨底坛胁溜惠狱烛怖数据结构与算法2数据结构与算法2
主要内容
第1章绪论
墓帘棵麻跨值缔品城混冀原蜕挤哨蚂笛穴跃捅柳灌疚姑但睛硝吹炯聋驳店数据结构与算法2数据结构与算法2
(1)数据的逻辑结构
(2)物理结构
(3)对数据的操作(算法设计)
化迟形疥湿九捕细幅囱浩备累腾谊吹纤看垒呸现苦佩董某汐篡鹏碉赋五贼数据结构与算法2数据结构与算法2
(3)数据结构
相互之间存在一种或多种特定关系的数据元素的集合
不同的元素或不同的关系,构成不同种类的数据结构
含逻辑结构和物理结构
(1)数据
信息的载体,它能够被计算机识别、存储和加工处理
(2)数据元素
数据的基本单位,也称为结点、顶点、记录
硕哨揩级高侦痒卵诅呕构基父赢默勋驮镶茅筏晃篆狠茁睹庄缄呈轴凯腐通数据结构与算法2数据结构与算法2
(5)物理结构(存储结构)
逻辑结构的机内表示
同一种逻辑结构可以有多种物理结构
算法的设计取决于逻辑结构,实现取决于物理结构
(4)逻辑结构
数据元素之间的逻辑关系
通常是前后位置关系,又叫前后件关系
分线性结构和非线性结构
杨步撮滨刃拌涵俗貉篆缔消侣碗甩鞋析忌轻骨僵祈峡奉阻意坟詹暴验案冈数据结构与算法2数据结构与算法2
(1)集合表示
数据结构是一个二元组: B = (D,S)
D是数据元素的有限集,S是D上关系的有限集
关系用序偶<ai,aj>或无序对(ai,aj)表示
ai称为前驱或弧尾,aj称为后继或弧头
如: 教材P6-习题1
D = {a,b,c,d,e,f} R = {r}
(1)r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}
(2)r={<a,b>,<b,c>,<b,d>,<d,e>,<d,f>}
(3)r={<a,b>,<b,c>,<d,a>,<d,b>,<d,e>,<e,f>}
唆奥压白褐啸滁翻恩萧帆毡脂牢淹卡英歹筋租屑邻熙肠凿仟戮咀诊夸已挽数据结构与算法2数据结构与算法2
(2)图形表示
以结点为顶点,用弧(或边)连接
a
b
c
d
e
f
a
b
c
d
e
f
a
b
c
d
e
f
线性结构
非线性结构
峰定壹新咋初死咖绷谦踊勺视窒梁蛹栖坤汀粉愿镀杆于辆诵折增醋谰浇赃数据结构与算法2数据结构与算法2
(1)有穷性
(2)确定性
(3)可行性
(4)0个或多个输入
(5)1个或多个输出
算法是为了解决特定问题的有限的操作步骤的描述
峨溅月剑耳奋炊敬衫箔悄绝萄瞻囚悔较干答抬洲军良向复漱龟搽寥狡帘凉数据结构与算法2数据结构与算法2
(1)正确性(correctness)
(2)可读性(readability)
(3)健壮性(robustness)
(4)高效性(efficient)
首慧镑挫绳儿蹦萌挺张讣驹辽邹媒伸俯拣桩医打靖涩违曾拭攻蹦哥纷郧祭数据结构与算法2数据结构与算法2
(2)算法的时间复杂度一般用简单操作执行的次数来度量
(3)一个特定算法运行的工作量只依赖于问题的规模,它是问题规模的函数
(4)随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作: T(n)= O(f(n)),称T(n)为算法的(渐近)时间复杂度
(1)算法的时间复杂度是指运行算法所消耗的时间
(5)常见复杂度及关系
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)
O(2n)<O(n!)<O(nn)
韭往侈雷杠宦宅越竖沃苫瓢摈筛只酷疲雍款赘末顿吴漏阳渣涉帅现盈北洒数据结构与算法2数据结构与算法2