通信网理论基础：码农的自我修养

1、码农的自我修养Simon编程初学者必须知道的基础知识和注意事项今晚要讲的内容Part1C+简介STL简介Project实际要做什么书目 章节推荐今晚要讲的内容Part2编程规范编译器/编辑器的选择基本的调试技巧今晚要讲的内容Part3进阶算法效率的重要性Windows下命令提示符的小技巧Part1C+简介STL简介Project实际要做什么书目 章节推荐C+简介Why C+三大概念封装(Encapsulation)继承(Inheritance)重载(Overloading)OOP(面向对象编程)实现好吧，那为什么搞得这么复杂？为了看上去简(fu)单(za)一些各种抽象C+简介封装封装继承重载C

2、+简介Project使用C+的意义OOP？No，Object-Based Programming没有继承，没有虚函数(多态)泛型的使用Part1C+简介STL简介Project实际要做什么书目 章节推荐STL简介Why STL标准模板库Standard Template Library代码重用，避免重复造轮子泛型编程的体现数据结构的抽象数据结构操作(方法)的抽象尽量减少猪队友带来的损失各种安全上的考虑e.g. vector的下标操作只能获取已存在的元素各种效率上的考虑(相对)开发效率运行效率STL简介vectorvectorvectorvectorvectorvector vector ive

3、c;ivec.push_back(42);ivec.push_back(21);ivec.push_back(14);ivec.push_front(7);b = ivec.back(); / 14f = ivec.front(); / 7s = ivec.size(); / 4STL简介Project可能用到的STL容器/算法顺序容器vectorlist关联容器mapsetSTL简介迭代器什么是迭代？迭代器 - 对i的一个抽象作用遍历容器内元素访问元素两个最重要的迭代器begin() end()注意 左闭右开example指针是一种迭代器，但迭代器不仅仅是指针Part1C+简介STL简介Pr

4、oject实际要做什么书目 章节推荐CGraphDesign模板介绍16 / 77 顶点数目 边数目 边的列表 将来的任务 给定文件 给定边的列表 拷贝构造 直接访问私有成员（属性）的各种接口函数属性构造函数接口其它函数CGraph设计2013年春季17 / 77CGraph类class CGraphprivate:int numVertex;int numEdge;list IncidentList;public:CGraph(char* inputFile);CGraph(list listEdge);CGraph(CGraph &);CGraph();int getNumVertex()

5、;int getNumEdge();2013年春季18 / 77关于STL容器的使用别忘了头文件和名字空间。容器中尽量装对象指针。把容器作为参数传递时尽量用引用。#ifndef _COMMON_H_#define _COMMON_H_#include #include #include using namespace std;#include #include “CEdge.h”typedef int VERTEXID;typedef int EDGEID;#define INFINITY 10000#endif/include “common.h”list listEdge;listEdge

6、.push_back(CEdge(1,2,3);list listEdge;listEdge.push_back(new CEdge(1,2,3);list listEdge;CEdge e(1,2,3);listEdge.push_back(e);list listEdge;CEdge* pe= new CEdge(1,2,3);listEdge.push_back(pe);构造拷贝构造析构不必拷贝构造e的变化不会影响listEdge中的相应元素。e的变化会反映到listEdge中的相应元素。map x;int i=0;pair y(1,i);x.insert(y);cout x1;引用的引

7、用非法func(list x);func(list& x);要拷贝一次；而且func里对x的改变在函数外无效。2013年春季19 / 77projectsProject No.1-1求一个map，其中元素是度数和顶点编号构成的pair。要求按照度数的降序排列。Project No.1-2构造一个map类型，键值为顶点编号，每个顶点对应的是一个list。该list中存储了该顶点邻接的所有其他顶点。Project No.1-3构建邻接矩阵。用二维的vector来表示，即vectorvector 。注意，需要构造一个表达“空边”的对象。Project No.1-4构建邻接链表：给定一个顶点，求一个l

8、ist，该list中存储了与该顶点关联的所有边。2013年春季Project1Deadline: Apr. 07thPart1C+简介STL简介Project实际要做什么书目 章节推荐书目推荐算法竞赛入门经典 (零基础入门)第1-4章 编程基础第6章 数据结构基础第11章 图论模型与算法书目推荐算法导论 e2/e3第3章 复杂度分析(较难)第10章 基本数据结构第15章 动态规划(较难)第16章 贪心算法第21章 并查集(了解)第22-26章 图算法第29章 单纯形算法(较难)书目推荐C+ Primere4 (C+零基础入门)第1章 快速入门第3章 标准库类型(string vector)第9

9、-11章 STL第2章 第4-8章 适当翻阅书目推荐*C+程序设计语言 特别版 (进阶)更加深入、透彻讲解C+标准库的函数、模板原型工具书Part1C+简介STL简介Project实际要做什么书目 章节推荐Part2编程规范编译器/编辑器的选择基本的调试技巧编程规范Make it work, make it right, make it fast. Kent Beck前提：make it readable程序首先是人读的，规范的格式利人利己规范的格式是对程序阅读者的尊重编程规范具体要求代码缩行 (tab, )属于同一个作用域内的代码位于同一列花括号对齐空格= = != (大于) + - *(乘

10、法) / % | & 前后加空格,(逗号) ;(分号) 后面加空格. -(域作用符) &(引用) *(指针) !(非) 后面不加空格编程规范具体要求变量/函数命名规范少取/不取没有意义的名字目的：让人一目了然变量/函数的作用而不需另加注释匈牙利命名法？驼峰式命名法？不拘一格参考算法竞赛入门经典 C+ PrimerPart2编程规范编译器/编辑器的选择基本的调试技巧编译器/编辑器的选择编译器：把.cpp文件变成.exe文件的工具编辑器：编写代码的地方IDE：Integrated-Development-Environment把编辑器、编译器、调试器集中到一个软件里Visual Studiocod

11、e:blocks eclipse dev-C+ etc.编译器的选择不推荐使用IDE体积巨大，过多用不上的模块(90%+)工程文件庞杂*编译失败有可能因为是编译器的原因不要用VC 6.0 ！不解释编译器推荐gccGCC（GNU Compiler Collection，GNU编译器套装），是一套由GNU开发的编程语言编译器。它是一套以GPL及LGPL许可证所发布的自由软件，也是GNU计划的关键部分，亦是自由的类Unix及苹果计算机Mac OS X操作系统的标准编译器。GCC（特别是其中的C语言编译器）也常被认为是跨平台编译器的事实标准。编译器推荐gcc开源，跨平台，操作简单，功能强大编译信息简单

12、明确，编译结果只有一个.exe文件过渡到Linux下编程更加自然在一个控制台下完成编译、运行操作，结束后不关闭窗口No need for system(”pause”);*对了解编译链接过程更有帮助-S 输出编译产生的汇编代码-c 输出编译汇编后产生的目标代码-O1 O2 编译优化参数编译器推荐gcc用法编译: g+ *.cpp运行: a enterThats all!要求：学会看编译信息，不懂的地方google/baidu/翻书编辑器推荐for WinNotepad+Evereditfor LinuxgeditvimnanoPart2编程规范编译器/编辑器的选择基本的调试技巧基本的调试技巧什

13、么时候需要调试(debug)？程序出错的三个过程编译错误（不需要调试）运行时错误（很多原因，最常见：段错误）结果错误实际上，调试可能占去写代码的一大半时间要求：遇到错误，先自己尝试调试程序基本的调试技巧尽量不用调试器(VS/gdb/ddd)不利于提高编程水平 在调试中学习编程增加学习成本(gdb)我有特别的调试技巧。printf/cout需要对程序的运行过程非常了解格式规范、结构清晰的重要性手动添加运行位置标志（代替断点）手动添加中间变量输出（代替变量观察窗口）Part2编程规范编译器/编辑器的选择基本的调试技巧Part3算法效率的重要性Windows下命令提示符的小技巧算法效率的重要性算法复杂度与输入规模相比较的运行时间数量级一个简单的问题Part3算法效率的重要性