数据结构 2015-2016 第一学期-TSMC

o 登录URP综合教务系统，查询选课学生信息。这里有课件和VC 6.0项目工程文件。

o 课程信息

课程名: 数据结构
课程号[课序号]：13005710
考试类型：考试
学时数：72（50讲课+20上机+2考试）
学分：4
上课对象: 软件工程2014-3;软件工程2014-4 
人数：64人
上课：星期1第1-2节(1-18周);星期3第3-4节(1-18周)
上机：周一1-2, 周三3-4,扬帆楼201(6-7周、10-11周、18周)
3班 于浩明 18340829077
4班 张正义 18940925187

o 教材

工作历史

>> 教学调查 | 备忘 | 教材

31/08 1-1概论A

复习>>从计算机的角度看数据-逻辑的、存储的>>数据是有结构的>>结构上的关系及其运算>>

02/09 2-2.1线性表A

线性表的定义和特点>>线性表的顺序表示(顺序表)>>存放地址的计算>>顺序表上的插入>>顺序表上的删除>>顺序表算法效率分析>>

07/09 2-2.2线性表B p.22

链式存储>>单链表上的运算(建立）build(&L)/display(L)

09/09 2-2.2线性表B

单链表上的运算(插入、删除)>>两个单链表的归并>>P32 运算效率分析>>随堂测验

14/09 3-4串.ppt

串的定义>>串的顺序存储/链式存储>>ADT>>串的模式匹配（找子串出现的位置）

16/09 3-4串.ppt

Index(S, T, pos)>>KMP算法思路[P20演示程序]>>课内习题

21/09 4-3栈和队列A.ppt

栈的定义>>逻辑结构>>存储结构>>实现方式(顺序、链式)>>运算

23/09 4-3栈和队列A.ppt

运算>>栈应用(递归)>>应用(数制转换, 表达式求值P23)

28/09-30/09上机实习

十一放假

14/10 5-3栈和队列B.ppt

队的定义>>逻辑结构>>存储结构>>实现方式(顺序、链式)>>运算>>循环队列

17/10 6-5数组和广义表A.ppt

以教室行列为例说明数组的顺序表示及实现>>计算数组元素的地址>>运算 InitArray(Array &A,int dim,…)>>广义表的定义

备忘

[TXT131] 非递归地中序遍历--循环条件p||!StackEmpty()
[TXT159] 极大连通/强连通的含义？顶点数+边数+两两连通
[TXT175] KRUSKAL算法：实现MiniSpaneTree_KRUSKAL(*G, G->vexs[0]);

关于artc和EasyX图形库

绘图算法的开发有三种办法：(1) 使用Turbo C，(2) Windows编程；(3) 使用OpenGL。(2)和(3)都复杂，会偏离教学的重点，所以许多老师不得不用TC教学。
由于artc使用TC图形函数接口，将其移植到Windows遇到困难——如clrscr()编译出错。然后发现了EasyX图形库，它TC图形函数接口，可以在Visual C++环境下编程。

dumpbin /all cslib.lib
dumpbin /exports cslib.lib

关于nmake与Makefile

在VS环境下使用Makefile的工具是nmake，它在命令行上使用VC编译器cl和链接器link。示例如下：

starsky.obj:
    $(cc) $(cdebug) $(cflags) -MT -I".\Include\graphics.h" /Fo"$(OUTDIR)\\" /Fd"$(OUTDIR)\\" StarSky\starsky.cpp
{$(Cube_DIR)}.cpp.obj::
    @echo --- COMPILING $(Cube_DIR)\*.cpp ---
    $(cc) $(cdebug) $(cflags) -MT -I".\Include\graphics.h" /Fo"$(OUTDIR)\\" /Fd"$(OUTDIR)\\" $<
starsky.exe: starsky.obj
    @echo --- LINKING $@ ---
    $(link) $(ldebug) $(conflags) -out:$(OUTDIR)\starsky.exe $(OUTDIR)\$** /LIBPATH:$(LIBS)

[9章自测题3.] 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，
则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。
因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7  ！！！

教学调查

根据以下知识点，对自己对C语言程序设计的了解程度打分（满分100）：

1、程序语言必备知识
#define MAX 255
typedef unsigned char SString[MAX];
枚举定义enum{}
结构定义typedef struct
指针：a[i]和(a+i)是否等价？什么是函数指针？
函数调用中传值和传地址的区别？
内存分配malloc(int); realloc(&,int); sizeof(); free(&);

2、变长参数表va_start,va_arg和va_end：是否了解变长参数表va_start,va_arg和va_end的使用？了解就简单说明用法。

教材

课上用书：

《数据结构（C语言版）》,严蔚敏 吴伟民 编著，清华大学出版社
ISBN：7-302-02368-9
定价：22元
出版日期：2003年7月第22次印刷

参考书：

《数据结构题集 (C语言版) 》 严蔚敏、吴伟民著 
《数据结构题集(C语言篇)――习题与解析（修订版）》李春葆编著 清华大学出版社

Textbook in English:

Data Structures Using C
Original Publisher： McGraw-Hill
Authors： R Krishnamoorthy and G Indirani Kumaravel
ISBN：9787302207313
Pages：604
丛书名： 大学计算机教育国外著名教材系列
出版社：清华大学出版社
上架时间：2009-9-24
出版日期：2009 年9月
开本：32开

教务工作

1、《领用教材申请单》

2、URP>>教学信息>>教学日历维护>>提交《教学日历》

3、《实验课程计划表》办公邮件给实验员

4、出题/试卷

4.1 三套试卷

4.2 预定考场

登录URP>>教学信息>>考试申请，获得(考试时间、课程号、人数)

4.3 试卷、考试审批表送教务处。两三天后领取打印好的试卷（A/B卷各多2-5套）。

4.4 查询考试地点(办公邮件通知后，查询jwc.dlmu.edu.cn>>>课程考试日程查询)

4.5 安排监考人员

4.6 准备好 ...

* 考生名单安排(找教学秘书打印)
* 座位安排
* 考场记录单
* 考卷

5、成绩单2份(装订1+教学秘书1)

登录URP>>教学信息>>成绩录入，获得(课程号)

6、《考试成绩分析表》1份(装订1+教学秘书1)

7、《课程教学总结表》1份(装订1)

8、《实验教学总结》+《实验报告》+实验成绩单送实验室

9、试卷装订：

* 考场记录，
* 成绩单，
* 平时成绩依据，
*《考试成绩分析表》，
*《课程教学总结表》，
* A/B卷答案，
* A/B卷评分标准，
* A/B空白卷

教学秘书

* 成绩单（1）
* 考试成绩分析表（1）

实验报告

开头应给出题目名称、班级、姓名、学号和完成日期，具体内容包括：

一、需求分析

陈述程序设计的任务，明确规定：（1）输入和输出的形式，举例说明；（2）程序功能；（3）测试用例设计。

二、概要设计

说明主程序流程，以及在函数级上说明各程序的调用关系

三、详细设计

详细的数据类型定义；主程序和其他模块的伪代码算法

四、调试分析

包括：（1）编辑代码、编译运行所遇到的问题及其解决办法；（2）对返工的设计与实现进行讨论和分析；（3）算法的时空分析；（4）心得体会。

五、用户使用说明

主屏幕截图告诉如何使用所编写的程序

六、测试结果

根据设计的测试用例，列出详细的测试结果，包括输入、输出和是否通过。

七、附录

源程序清单

URLs

Computer Musings by Professor Donald E. Knuth
Niklaus Wirth

pronounce his name the right way ('Nick-louse Veert'), something about him on wiki and in videos, and his personality in a book

Edsger Wybe Dijkstra, and something about him on wiki

程序大赛

Also, sites like TopCoder, Google Code Jam and CodeForces have problem analyses and the code submitted during the contest available[2].

TopCoder是一个采用新颖模式的软件开发企业，通过互联网利用全球的注册用户参与开发，将原本以企业形式组织起来的软件开发工作通过众包转向了市场形式。美国在线委托TopCoder开发通信后端系统，他任命了两名职员做设计师和项目经理，他们组织了少数人员把这个系统分成52个部分，按照传统软件工程的来法要一年完成，但是TopCoder仅仅用了五个月就完成了，而且质量还很高，最终产品完全达到客户要求，并且程序中每一千行代码平均只有0.98个漏洞，低于业内要求他们每千行六个漏洞标准[3]。遵从二八律我们才认为他达到了群体参与开发的要求。比如TopCoder，它实际上是25万人，但实际开发者只有48850人，占注册用户的19.6%，来自204个国家，中国的选手为11541个人。浙江大学大概有几十个学生都从中国直接参与TopCoder的开发，而且很多同学就是因为TopCoder的开发解决了自己的学费、住宿所有的问题。说明这个群体软件适合我们中国[3]。TopCoder组件开发教程

Google从2003年起举办Google Code Jam程序设计竞赛(http://code.google.com/codejam/contest/)，用意在提升全球程序开发者交流，同时嘉奖优秀的程序设计者。Code Jam与ACM有类似之处, 但是测试的数据是开放的, 并且分为small和big两部分, small主要是用来验证程序的正确性, 而big则是考验程序的时间, 空间复杂度. 这方面与ACM相比, 更贴近实用性考量. 例1

Codeforces是一个俄国的算法竞赛网站(http://codeforces.com/), 官方语言是俄语和英语.由来自萨拉托夫州立大学Mike Mirzayanov领导的一个团队创立和维护, 是一个举办比赛、做题和交流的平台. 例2和例3

The USACO supports computing education in the USA and worldwide by identifying, motivating, and training high-school computing students at all levels. The USACO on-line training pages provide hundreds of hours of free instruction and practice problems to improve your programming and problem-solving skills. USACO真的是很不错，非常练基本功，对于代码的性能要求很苛刻。

Tutorials and Talks: Programming Contents For EveryOne and Recursive Algorithms by Jey Veerasamy. Art of Programming Contest

数据结构 2015-2016 第一学期