
数据结构袁平波2025.2课程主页:http://staff.ustc.edu.cn/~ypbhttps://git.ustc.edu.cn/ypb/course中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 数据结构 袁平波 2025.2 课程主页:http://staff.ustc.edu.cn/~ypb https://git.ustc.edu.cn/ypb/course

课程概况50理论课时一作业一章提交一次20实验课时-5次一第5/6周开始·课程考核一考试60-70%,平时(作业/出勤)10%,实验30-20%一6个实验(必做:2,选做:1)一提交1份实验报告,实验随堂检查·课堂要求一缺勤要请假中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 课程概况 • 50理论课时 – 作业一章提交一次 • 20实验课时 – 5次 – 第5/6周开始 • 课程考核 – 考试60-70%,平时(作业/出勤)10%,实验30-20% – 6个实验(必做:2,选做:1) – 提交1份实验报告,实验随堂检查 • 课堂要求 – 缺勤要请假

参考教材实验指导教材DATASTRUCTUREANDAPNRHALGORITHMmES数据结构实验指导数据结构及ShupuJiegou Shiyan Zhidau应用算法定干洗特餐第3版东度刻车小三周国3中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 参考教材 实验指导教材

第1章数据结构导论1.1数据结构的基本概念1.2数据结构类型1.3抽象数据类型1.4数据与数据结构1.5算法1.6算法分析中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 1.1数据结构的基本概念 1.2数据结构类型 1.3抽象数据类型 1.4数据与数据结构 1.5算法 1.6算法分析 第1章 数据结构导论

数据结构研究什么?数据结构的历史·1968美国唐·欧·克努特设立《数据结构》课程·1976瑞士NiklausWirth提出程序设计=算法+数据结构数据结构是研究:非数值类问题的对象描述、信息组织方法及其相应的操作,即逻辑结构及其编程表示方法。·(1)加工对象逻辑组织(2)存储到计算机(3)数据运算5中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 5 中国科学技术大学 数据结构的历史 • 1968 美国唐·欧·克努特设立《数据结构》课程 • 1976 瑞士 Niklaus Wirth 提出程序设计=算法+数据结构 数据结构是研究 • 非数值类问题的对象描述、信息组织方法及其相应的操作 , 即逻辑结构及其编程表示方法。 • (1) 加工对象逻辑组织(2)存储到计算机 (3)数据运算 数据结构研究什么?

「例]、设有一个电话号码薄,有N个人的姓名和电话号码。要求设计一个程序,按人名查找号码,若不存在则给出查找失败的信息。姓名namename,name:nametehtelz电话号码tel.o.e+tel(a)联序存储Lhead-3namesname;name;name2namesteltelstelteletel5216421345(b)链式存储6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 [例]、设有一个电话号码薄,有N个人的姓名和电话号码。 要求设计一个程序,按人名查找号码,若不存在则给出查找 失败的信息

「例井子棋、非线性数据结构-树Xxo(b)(a)井字棋对穿“树”(a)棋盘格局示例,(b)对奔树的局部中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 • [例] 井子棋、非线性数据结构-树

[例】交叉口交通灯设置(顶点着色问题T一图非线性-ACABADT-DBDCBA221BDADBDC313EBECEDEA4(a)(b)五叉路口交通管理示意图(a)五叉路口:(b)表示通路的图8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 [例] 交叉口交通灯设置(顶点着色问题) 非线性——图

1.1数据结构的基本概念·集合和关系一集合是若于具有共同可辨特征的事物的“聚合”,每个事物称该集合的元素或成员。一集合元素之间一般都具有某种“关系”。·数据和信息一数据是指描述客观事物且能由计算机处理的数值、字符符号的总称一信息是包含在数据中符号的含义。数据是信息的符号表示形式。9中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 • 集合和关系 – 集合是若干具有共同可辨特征的事物的“聚合” , 每个事物称该集合的元素或成员。 – 集合元素之间一般都具有某种“关系” 。 • 数据和信息 –数据是指描述客观事物且能由计算机处理的数值、 字符符号的总称 – 信息是包含在数据中符号的含义。数据是信息的符 号表示形式。 1.1数据结构的基本概念

·数据元素一是数据的基本单位,有时称记录、结点、顶点。其包括数据项(DataItem),数据项可以是原子项(性别)或组合项 (出生日期)·数据对象一是性质相同的数据元素的集合,是数据的一个子集。·关键码(key)一数据元素中起识别作用的数据项。有主次之分,能唯一识别的称主码,否则称次码。10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 • 数据元素 –是数据的基本单位,有时称记录、结点、顶点。其包 括数据项(Data Item),数据项可以是原子项(性别) 或组合项(出生日期) • 数据对象 – 是性质相同的数据元素的集合,是数据的一个子集 。 • 关键码(key) – 数据元素中起识别作用的数据项。有主次之分,能唯 一识别的称主码,否则称次码