Data Structure and Algorithm (in Chinese)
数据结构及其算法 (2017~2018学年秋季学期)

教师:刘东 (dongeliu AT ustc.edu.cn)
助教:陈康(2261842955@qq.com)、丁浩帅(dhsls211@mail.ustc.edu.cn)


教学进度与通知

课堂时间:每周一下午14:00~15:35,每周四上午7:50~9:25,地点:3A310
实验时间:每周六晚上18:30~21:30,地点:西区机房

课件下载

第一章
第二章
第三章

补充作业

4.16 写一个递归算法,对不带头结点的单链表进行逆序,要求输入参数是单链表的头指针,返回逆序之后的头指针。
6.26 写一个递归算法,求二叉链表表示的二叉树的先序遍历序列的第k个元素(1<=k<=n)的值。
9.14 (荷兰国旗问题) 假设输入序列中仅有三种颜色:R(红), W(白), B(蓝),写一个算法将序列按照R,W,B的顺序排好。例如输入序列是RWBBWWRRW,输出应为RRRWWWWBB。

课本与参考书

课本:
袁平波等,《数据结构及应用算法(第2版)》,中国科学技术大学出版社
参考书:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C. 《数据结构与算法分析:C语言描述》,机械工业出版社
Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language. 《C程序设计语言》,机械工业出版社
李春葆编著,《数据结构习题与解析》,清华大学出版社
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms. 《算法导论》,机械工业出版社

编程工具

Visual Studio: 官方主页
微软公司出品的集成开发环境,可用于C/C++、C#、Visual Basic、JavaScript等语言的开发。功能强大、图形界面友好、调试非常方便。Windows操作系统首选。建议下载最新的社区版即Visual Studio Community 2017(免费供学生使用)。
Code::Blocks: 官方主页
开源、跨平台、免费的C/C++和Fortran集成开发环境。功能丰富、图形界面简洁、可使用gdb调试。Windows、Linux、Mac OS X操作系统均可使用。建议下载codeblocks-16.01mingw-setup.exe。
Xcode: 官方主页
苹果公司出品的集成开发环境,特别适合Mac OS X及iOS系统的应用程序开发。功能强大、图形界面友好、调试方便。Mac OS X操作系统首选。建议从Mac App Store中免费下载最新版。

上机实验

C++语言参考手册:在线下载
实验说明
实验一:一元多项式的运算
实验二:表达式求值或银行排队系统仿真
实验三:关键词检索
实验四:Huffman编码和解码
实验五:最短路径
实验六:排序算法的计算复杂度
实验七(选做):旅行商问题
实验八(选做):统计话费