通信網(wǎng)理論基礎(chǔ)：碼農(nóng)的自我修養(yǎng)

1、碼農(nóng)的自我修養(yǎng)Simon編程初學(xué)者必須知道的基礎(chǔ)知識和注意事項今晚要講的內(nèi)容Part1C+簡介STL簡介Project實際要做什么書目 章節(jié)推薦今晚要講的內(nèi)容Part2編程規(guī)范編譯器/編輯器的選擇基本的調(diào)試技巧今晚要講的內(nèi)容Part3進階算法效率的重要性Windows下命令提示符的小技巧Part1C+簡介STL簡介Project實際要做什么書目 章節(jié)推薦C+簡介Why C+三大概念封裝(Encapsulation)繼承(Inheritance)重載(Overloading)OOP(面向?qū)ο缶幊?實現(xiàn)好吧，那為什么搞得這么復(fù)雜？為了看上去簡(fu)單(za)一些各種抽象C+簡介封裝封裝繼承重載C

2、+簡介Project使用C+的意義OOP？No，Object-Based Programming沒有繼承，沒有虛函數(shù)(多態(tài))泛型的使用Part1C+簡介STL簡介Project實際要做什么書目 章節(jié)推薦STL簡介Why STL標準模板庫Standard Template Library代碼重用，避免重復(fù)造輪子泛型編程的體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)結(jié)構(gòu)操作(方法)的抽象盡量減少豬隊友帶來的損失各種安全上的考慮e.g. vector的下標操作只能獲取已存在的元素各種效率上的考慮(相對)開發(fā)效率運行效率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關(guān)聯(lián)容器mapsetSTL簡介迭代器什么是迭代？迭代器 - 對i的一個抽象作用遍歷容器內(nèi)元素訪問元素兩個最重要的迭代器begin() end()注意 左閉右開example指針是一種迭代器，但迭代器不僅僅是指針Part1C+簡介STL簡介Pr

4、oject實際要做什么書目 章節(jié)推薦CGraphDesign模板介紹16 / 77 頂點數(shù)目 邊數(shù)目 邊的列表 將來的任務(wù) 給定文件 給定邊的列表 拷貝構(gòu)造 直接訪問私有成員（屬性）的各種接口函數(shù)屬性構(gòu)造函數(shù)接口其它函數(shù)CGraph設(shè)計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關(guān)于STL容器的使用別忘了頭文件和名字空間。容器中盡量裝對象指針。把容器作為參數(shù)傳遞時盡量用引用。#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);構(gòu)造拷貝構(gòu)造析構(gòu)不必拷貝構(gòu)造e的變化不會影響listEdge中的相應(yīng)元素。e的變化會反映到listEdge中的相應(yīng)元素。map x;int i=0;pair y(1,i);x.insert(y);cout x1;引用的引

7、用非法func(list x);func(list& x);要拷貝一次；而且func里對x的改變在函數(shù)外無效。2013年春季19 / 77projectsProject No.1-1求一個map，其中元素是度數(shù)和頂點編號構(gòu)成的pair。要求按照度數(shù)的降序排列。Project No.1-2構(gòu)造一個map類型，鍵值為頂點編號，每個頂點對應(yīng)的是一個list。該list中存儲了該頂點鄰接的所有其他頂點。Project No.1-3構(gòu)建鄰接矩陣。用二維的vector來表示，即vectorvector 。注意，需要構(gòu)造一個表達“空邊”的對象。Project No.1-4構(gòu)建鄰接鏈表：給定一個頂點，求一個l

8、ist，該list中存儲了與該頂點關(guān)聯(lián)的所有邊。2013年春季Project1Deadline: Apr. 07thPart1C+簡介STL簡介Project實際要做什么書目 章節(jié)推薦書目推薦算法競賽入門經(jīng)典 (零基礎(chǔ)入門)第1-4章 編程基礎(chǔ)第6章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第11章 圖論模型與算法書目推薦算法導(dǎo)論 e2/e3第3章 復(fù)雜度分析(較難)第10章 基本數(shù)據(jù)結(jié)構(gòu)第15章 動態(tài)規(guī)劃(較難)第16章 貪心算法第21章 并查集(了解)第22-26章 圖算法第29章 單純形算法(較難)書目推薦C+ Primere4 (C+零基礎(chǔ)入門)第1章 快速入門第3章 標準庫類型(string vector)第9

9、-11章 STL第2章 第4-8章 適當(dāng)翻閱書目推薦*C+程序設(shè)計語言 特別版 (進階)更加深入、透徹講解C+標準庫的函數(shù)、模板原型工具書Part1C+簡介STL簡介Project實際要做什么書目 章節(jié)推薦Part2編程規(guī)范編譯器/編輯器的選擇基本的調(diào)試技巧編程規(guī)范Make it work, make it right, make it fast. Kent Beck前提：make it readable程序首先是人讀的，規(guī)范的格式利人利己規(guī)范的格式是對程序閱讀者的尊重編程規(guī)范具體要求代碼縮行 (tab, )屬于同一個作用域內(nèi)的代碼位于同一列花括號對齊空格= = != (大于) + - *(乘

10、法) / % | & 前后加空格,(逗號) ;(分號) 后面加空格. -(域作用符) &(引用) *(指針) !(非) 后面不加空格編程規(guī)范具體要求變量/函數(shù)命名規(guī)范少取/不取沒有意義的名字目的：讓人一目了然變量/函數(shù)的作用而不需另加注釋匈牙利命名法？駝峰式命名法？不拘一格參考算法競賽入門經(jīng)典 C+ PrimerPart2編程規(guī)范編譯器/編輯器的選擇基本的調(diào)試技巧編譯器/編輯器的選擇編譯器：把.cpp文件變成.exe文件的工具編輯器：編寫代碼的地方IDE：Integrated-Development-Environment把編輯器、編譯器、調(diào)試器集中到一個軟件里Visual Studiocod

11、e:blocks eclipse dev-C+ etc.編譯器的選擇不推薦使用IDE體積巨大，過多用不上的模塊(90%+)工程文件龐雜*編譯失敗有可能因為是編譯器的原因不要用VC 6.0 ！不解釋編譯器推薦gccGCC（GNU Compiler Collection，GNU編譯器套裝），是一套由GNU開發(fā)的編程語言編譯器。它是一套以GPL及LGPL許可證所發(fā)布的自由軟件，也是GNU計劃的關(guān)鍵部分，亦是自由的類Unix及蘋果計算機Mac OS X操作系統(tǒng)的標準編譯器。GCC（特別是其中的C語言編譯器）也常被認為是跨平臺編譯器的事實標準。編譯器推薦gcc開源，跨平臺，操作簡單，功能強大編譯信息簡單

12、明確，編譯結(jié)果只有一個.exe文件過渡到Linux下編程更加自然在一個控制臺下完成編譯、運行操作，結(jié)束后不關(guān)閉窗口No need for system(”pause”);*對了解編譯鏈接過程更有幫助-S 輸出編譯產(chǎn)生的匯編代碼-c 輸出編譯匯編后產(chǎn)生的目標代碼-O1 O2 編譯優(yōu)化參數(shù)編譯器推薦gcc用法編譯: g+ *.cpp運行: a enterThats all!要求：學(xué)會看編譯信息，不懂的地方google/baidu/翻書編輯器推薦for WinNotepad+Evereditfor LinuxgeditvimnanoPart2編程規(guī)范編譯器/編輯器的選擇基本的調(diào)試技巧基本的調(diào)試技巧什

13、么時候需要調(diào)試(debug)？程序出錯的三個過程編譯錯誤（不需要調(diào)試）運行時錯誤（很多原因，最常見：段錯誤）結(jié)果錯誤實際上，調(diào)試可能占去寫代碼的一大半時間要求：遇到錯誤，先自己嘗試調(diào)試程序基本的調(diào)試技巧盡量不用調(diào)試器(VS/gdb/ddd)不利于提高編程水平 在調(diào)試中學(xué)習(xí)編程增加學(xué)習(xí)成本(gdb)我有特別的調(diào)試技巧。printf/cout需要對程序的運行過程非常了解格式規(guī)范、結(jié)構(gòu)清晰的重要性手動添加運行位置標志（代替斷點）手動添加中間變量輸出（代替變量觀察窗口）Part2編程規(guī)范編譯器/編輯器的選擇基本的調(diào)試技巧Part3算法效率的重要性Windows下命令提示符的小技巧算法效率的重要性算法復(fù)雜度與輸入規(guī)模相比較的運行時間數(shù)量級一個簡單的問題Part3算法效率的重要性