文档介绍：数据结构与算法 Data Structures and Algorithms 课程安排?理论: 3课时/周+ 作业?实验:3课时/两周+ 作业?总成绩: 平时 40%( 包括听课、作业、实验、期中) + 期末 60% ?教学用书: 数据结构(C 语言版),严蔚敏、吴伟民,清华大学出版社, 1997 年?参考书: 1. 数据结构,许卓群,张乃孝,杨冬青,唐世渭, 高等教育出版社, 1987 年 2. A Practical Introduction to Data Structures and Algorithm Analysis. Clifford A. Shaffer 电子工业出版社 2002 。什么是数据结构? ?什么是数据结构? ?为什么学习数据结构?达到什么目的? ?应该掌握哪些内容?技能? ?如何学习? 从电话号码查询说起?问题:你有一叠亲友和客户等的名片,需要在其中查找某个人的卡片。?解法 1:顺序查找?卡片组织:顺序(线性逻辑结构) 如何组织数据(逻辑关系)以便实现数据上的处理从电话号码查询说起?解法 1的实现(1) : –使用数组存储卡片; 如何用 C/C++ 表示数据, 即数据的存储结构用 C++ 表示: struct Card { string name; string phone; } ; Card phones[100]; 从电话号码查询说起?解法 1的实现(1) : –算法的实现; 如何用 C/C++ 实现算法(如查找) int sequentialSearch(Card [] st, int n, string const &target) { //在查找表 st中顺序查找其关键字为 target 的记录。如果查找成功,则返回//该元素在查找表中的下标(0— n-1); 否则,返回表的长度 n,表明查找失败。 int i; for (i = 0; i<n && st[i].name != target;i ++); return i; } 用 C++ 表示: struct Card { string name; string phone; } ; 从电话号码查询说起?解法 1的实现(2) : –使用链表存储卡片; 如何设计/选择存储数据的方式(存储结构)便于数据上操作(如查找)的实现用 C++ 表示: struct Node{ Card data; Node * next; } ; Node * head; head 从电话号码查询说起?解法 1的实现(2) : –使用链表存储卡片; 如何评价以上两种实现?掌握评价算法的基本技能 struct Node{ Card data; Node * next; } ; Node * sequentialSearchLinked(Node * head, string const &target) { //在查找表 st中顺序查找其关键字为 target 的记录。如果查找成功,则返回//指向该元素的指针; 否则,返回空指针,表明查找失败。 Node * p=head; while (p!= NULL&&(p -> data).name !=target) { p=p->next }; return p; } 从电话号码查询说起?解法 2:二分查找。?条件:先把卡片按照姓名排序; ?组织结构:线性逻辑结构;?存储结构:连续结构(数组,又称随机存取结构) 从电话号码查询说起?解法 3:二叉查找树; ?数据组织(逻辑关系):二叉树型结构;