20182306 2018-2019-1《程序設計與數據結構》課程總結

（按順序）每周作業鏈接匯總

預備作業：

  • 安裝虛擬機過程中遇到的問題及解決過程和Linux基礎入門學習記錄

第一周作業：

  • 配置linux虛擬機、環境、學習git和單步調試

第二周作業：

  • 輸入兩個數，計算兩個數的加、減、乘、除運算結果，并輸出。

第三周作業：

  • 生成-10~10之間的隨機數（1.5分），并格式化輸出（0.###）
  • 編寫一個Book類，其實例數據分別表示書名、作者、出版社以及版權日期。定義一個Book構造方法，接收并初始化實例數據；為所有實例數據定義獲取和設置他們的方法；定義一個toString方法，返回幾行描述該圖書的字符串。創建一個Bookshelf驅動類，其main方法實例化并輸出一些Book對象。

第四周作業：

  • 接口測試（Interface）
    定義一個接口People，并定義另外一個Student類，實現該接口。
    并做簡單的測試（StudentTest）。

第五周作業：

  • 編寫支持復數和有理數（分數）的計算器
    （1）可以選擇復數或有理數的計算，也可以選擇“退出”；
    （2）復數類要求必須implements Comparable接口，并比較兩個復數的大小；
    （3）要求用WhiteStarUML畫出UML圖，加學號傳到藍墨云上；
    （4）要求使用IDEA把代碼git到碼云上；

第六周作業：

  • 參考云班課資源中的FileTest文件
    學習字節流和字符流，要求能夠實現創建文件，采用四種方法寫入和讀取文件（每種方法都要上傳結果截圖）
    采用一種方法將任意兩個復數寫入文件，再將這兩個復數讀取出來
    讀取后做加運算，將得到的結果再寫入文件
    將代碼git至碼云，附上截圖和碼云鏈接（鏈接必須必須要精確到具體文件或文件夾！！！！）

第七周作業

  • 完成課本中ArrayStack類的實現，特別是完成peek、isEmpty、size和toString方法的實現，并完成四個方法的測試。
  • 從命令行輸出一個后綴表達式：
    7 4 -3 * 1 5 + / *
    利用棧計算該表達式的值。

第八周作業：

  • 鏈表練習，要求實現下列功能：
    （1）通過鍵盤輸入一些整數，建立一個鏈表；
    （2）實現節點插入、刪除、輸出操作；
    （3）使用冒泡排序法或者選擇排序法根據數值大小對鏈表進行排序；
  • 給出size、isEmpty和toString等方法的定義，以完成LinkedStack類的實現。
    要求：1.能夠運行
    2.需要測試各個方法
    3.把代碼上傳到碼云，并將關鍵代碼和運行結果截圖加水印（學號）上傳。

第九周作業：

  • PP15.2完成CircularArrayQueue類的實現，包括所有的方法。
    注意：要求通過入隊和出隊操作，出現隊空和隊滿的情況。
  • 學習ArrayList和LinkedList類，并在Android平臺上實現添加、刪除、修改等操作（數據可以自己定義）(3分)，并實現倒置（3分）。
    倒置的意思就是：1 2 3 4 5 變為 5 4 3 2 1
  • 給定關鍵字序列19 14 23 1 68 20 84 27 55 11 10 79，試分別用順序查找、折半查找、二叉排序樹查找、散列查找(用線性探查法和鏈地址法)來實現查找。試畫出它們的對應存儲形式(順序查找的順序表，二分查找的判定樹，二叉排序樹查找的二叉排序樹，兩種散列查找的散列表)，并求出每一種查找的成功平均查找長度。其中，散列函數H(k)=k%11。
  • 給Searching類添加二分查找算法的遞歸實現方法。創建驅動程序來演示這個實現機制。
    （1）編程實現遞歸
    （2）創建一個測試類，測試遞歸實現的二分查找是否正確。

第十周作業：

  • （1）給定一個序列AB#CD###E#F##建立一顆樹，根據“二叉樹的生成”算法構造這顆樹。
    （2）使用層序遍歷方法完成遍歷并測試。

第十一周作業：

  • 建立一顆二叉排序樹，樣例如附件所示。完成：
    （1）創建二叉排序樹
    （2）查找一個元素，包含查找成功和失敗的例子；
    （3）插入2個元素，1個插入到左子樹，1個插入到右子樹；
    （4）刪除一個元素，要考慮不同情況。
  • 設有字符集：S={a,b,c,d,e，f,g,h,i,j,k,l,m,n.o.p.q,r,s,t,u,v,w,x,y,z}。
    給定一個包含26個英文字母的文件，統計每個字符出現的概率，根據計算的概率構造一顆哈夫曼樹。
    并完成對英文文件的編碼和解碼。
    要求：
    （1）準備一個包含26個英文字母的英文文件（可以不包含標點符號等），統計各個字符的概率
    （2）構造哈夫曼樹
    （3）對英文文件進行編碼，輸出一個編碼后的文件
    （4）對編碼文件進行解碼，輸出一個解碼后的文件
    （5）撰寫博客記錄實驗的設計和實現過程，并將源代碼傳到碼云
    （6）把實驗結果截圖上傳到云班課

第十二周作業：

  • 圖的存儲表示以及計算結點的度。
    （1）定義有向圖和無向圖（把附件圖中的箭頭去掉）的頂點矩陣和鄰接矩陣，并計算每個結點的入度和出度。（3分）
    （2）定義有向圖的帶權臨街表，并計算每個節點的出度（2分）

第十三周作業：

編程實踐：
（1）編寫代碼初始化有向無環圖和有向有環圖（見附件1和2），使用鄰接表初始化圖（3分）。
（2）使用堆棧實現拓撲排序算法，輸出附件1圖的拓撲排序序列且沒有環，檢測附件圖2存在環（4分）。

自認為寫得最好一篇博客是？為什么？

我認為是哈夫曼測試，因為這個實驗自己有充分的準備，這個實驗做完后自己收獲很大，也很開心，博客當時也是很早就完成了。

作業中閱讀量最高的一篇博客是？談談經驗

預備作業的那篇博客閱讀量最高，可能大家當時都是對新課程的好奇。

（按順序）實驗報告鏈接匯總

實驗一 實驗名稱：Linux基礎與Java開發環境

簡要內容：
基于命令行和IDE [Intellj IDEA 簡易教程](http://www.rzrgm.cn/rocedu/p/4421202.html）進行簡單的Java程序編輯、編譯、運行和調試。（本次實驗主要使用命令行的方式）
練習Linux基本命令；
學習Java程序的JDB調試技能：http://www.rzrgm.cn/rocedu/p/6371262.html
編寫簡單的Java程序。

實驗二 實驗名稱：Java基礎（數據/表達式、判定/循環語句）

簡要內容：
編寫簡單的計算器，完成加減乘除模運算。
要求從鍵盤輸入兩個數，使用判定語句選擇一種操作，計算結果后輸出，然后使用判定和循環語句選擇繼續計算還是退出。
編寫測試代碼，測試驗證。（http://www.rzrgm.cn/rocedu/p/4472842.html）

實驗三 實驗名稱：面向對象程序設計

簡要內容：
下載安裝并使用IDEA，完成下面實驗（http://www.rzrgm.cn/rocedu/p/6371315.html）。
初步掌握單元測試和TDD
理解并掌握面向對象三要素：封裝、繼承、多態（自己去學！）
初步掌握UML建模
完成藍墨云上 （1）-（5）實驗。

實驗四 實驗名稱：Java Socket編程

  • Java Socket編程
    學習藍墨云上教材《Java和Android編程》“第16章 輸入/輸出 ”和“第22章 網絡”，學習JavaSocket編程
    結對編程。結對伙伴A編寫客戶端SocketClient.java，結對伙伴B編寫服務器端。
    截圖加學號水印上傳藍墨云，代碼push到碼云，并撰寫實驗報告。
  • Java和密碼學
    以結對的方式完成Java密碼學相關內容的學習（帖子中所有代碼和相關知識點需要學習）。提交學習成果碼云鏈接和代表性成果截圖，要有學號水印。
    編寫有理數/復數計算器
    遠程有理數計算器
    遠程復數計算器

實驗五 實驗名稱：Android程序設計

  • Android Stuidio的安裝測試：
    參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十四章：
    參考http://www.rzrgm.cn/rocedu/p/6371315.html#SECANDROID,安裝 Android Stuidio
    完成Hello World, 要求修改res目錄中的內容，Hello World后要顯示自己的學號，自己學號前后一名同學的學號，提交代碼運行截圖和碼云Git鏈接，截圖沒有學號要扣分
    學習Android Stuidio調試應用程序
  • Activity測試
    參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十五章：
    構建項目，運行教材相關代碼
    創建 ThirdActivity, 在ThirdActivity中顯示自己的學號，修改代碼讓MainActivity啟動ThirdActivity
  • UI測試
    參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十六章：
    構建項目，運行教材相關代碼
    修改代碼讓Toast消息中顯示自己的學號信息
  • 布局測試：
    參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十七章：
    構建項目，運行教材相關代碼
    修改布局讓P290頁的界面與教材不同
  • 事件處理測試：
    參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十八章：
    構建項目，運行教材相關代碼
    提交代碼運行截圖和碼云Git鏈接，截圖要有學號水印，否則會扣分

實驗六 實驗名稱：線性結構之鏈表

  • 鏈表練習，要求實現下列功能：
    通過鍵盤輸入一些整數，建立一個鏈表；這些數是你學號中依次取出的兩位數，再加上今天的時間。
    打印所有鏈表元素， 并輸出元素的總數。
    在你的程序中，請用一個特殊變量名來紀錄元素的總數，變量名就是你的名字。
    做完這一步，把你的程序簽入源代碼控制（git push）。
  • 鏈表練習，要求實現下列功能：
    實現節點插入、刪除、輸出操作；
    繼續你上一個程序， 擴展它的功能，每做完一個新功能，或者寫了超過10行新代碼，就簽入代碼，提交到源代碼服務器；
    從磁盤讀取一個文件， 這個文件有兩個數字。
    從文件中讀入數字1， 插入到鏈表第 5 位，并打印所有數字，和元素的總數。 保留這個鏈表，繼續下面的操作。
    從文件中讀入數字2， 插入到鏈表第 0 位，并打印所有數字，和元素的總數。 保留這個鏈表，并繼續下面的操作。
    從鏈表中刪除剛才的數字1. 并打印所有數字和元素的總數。
  • 鏈表練習，要求實現下列功能：
    使用冒泡排序法或者選擇排序法根據數值大小對鏈表進行排序；
    如果你學號是單數， 選擇冒泡排序， 否則選擇選擇排序。
    在排序的每一個輪次中， 打印元素的總數，和目前鏈表的所有元素。
    在（2）得到的程序中繼續擴展， 用同一個程序文件，寫不同的函數來實現這個功能。
    在android上實現實驗（1）和（2）
    在android平臺上實現實驗（3)

實驗七 實驗名稱：查找與排序

  • 定義一個Searching和Sorting類，并在類中實現linearSearch,SelectionSort方法，最后完成測試。
    要求不少于10個測試用例，提交測試用例設計情況（正常，異常，邊界，正序，逆序），用例數據中要包含自己學號的后四位
    提交運行結果圖。
  • 重構你的代碼，把Sorting.java Searching.java放入 cn.edu.besti.cs1823.（姓名首字母+四位學號） 包中（例如：cn.edu.besti.cs1823.G2301）
    把測試代碼放test包中
  • 重新編譯，運行代碼，提交編譯，運行的截圖（IDEA，命令行兩種）
  • 參考http://www.rzrgm.cn/maybe2030/p/4715035.html ，學習各種查找算法并在Searching中補充查找算法并測試，提交運行結果截圖
    • 補充實現課上講過的排序方法
    • 希爾排序，堆排序，二叉樹排序等(至少3個)
    • 測試實現的算法（正常，異常，邊界）
    • 提交運行結果截圖（如果編寫多個排序算法，即使其中三個排序程序有瑕疵，也可以酌情得滿分）

實驗八 實驗名稱：樹

  • 參考教材PP16.1,完成鏈樹LinkedBinaryTree的實現（getRight,contains,toString,preorder,postorder）
    • 用JUnit或自己編寫驅動類對自己實現的LinkedBinaryTree進行測試
    • 提交測試代碼運行截圖，要全屏，包含自己的學號信息
    • 課下把代碼推送到代碼托管平臺
  • 基于LinkedBinaryTree，實現基于（中序，先序）序列構造唯一一棵二?樹的功能，比如給出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,構造出附圖中的樹
    • 用JUnit或自己編寫驅動類對自己實現的功能進行測試，提交測試代碼運行截圖，要全屏，包含自己的學號信息
    • 課下把代碼推送到代碼托管平臺
  • 自己設計并實現一顆決策樹;提交測試代碼運行截圖，要全屏，包含自己的學號信息
    課下把代碼推送到代碼托管平臺
  • 輸入中綴表達式，使用樹將中綴表達式轉換為后綴表達式，并輸出后綴表達式和計算結果
    提交測試代碼運行截圖，要全屏，包含自己的學號信息

實驗九 實驗名稱：圖

  • 初始化：根據屏幕提示（例如：輸入1為無向圖，輸入2為有向圖）初始化無向圖和有向圖（可用鄰接矩陣，也可用鄰接表），圖需要自己定義（頂點個數、邊個數，建議先在草稿紙上畫出圖，然后再輸入頂點和邊數）（2分）
  • 圖的遍歷：完成有向圖和無向圖的遍歷（深度和廣度優先遍歷）（4分）
  • 完成有向圖的拓撲排序，并輸出拓撲排序序列或者輸出該圖存在環（3分）
  • 完成無向圖的最小生成樹（Prim算法或Kruscal算法均可），并輸出（3分）
  • 完成有向圖的單源最短路徑求解（迪杰斯特拉算法）（3分）

(按順序）團隊項目報告鏈接匯總

代碼托管

  • 代碼托管
  • 給出statistic.sh的運行結果，說明本學期的代碼量目標達到沒有？

原計劃代碼量為6000行，經過一個學期的努力，我的代碼量達到目標，并突破10000行。

  • 加點代碼，改點代碼是理解的最好方式，參考編程的智慧，談談你的心得
    所有的代碼不可能靠一個人完完全全的來完成，但是在借用代碼的時候理解好代碼的含義，就是收獲。
  • 積極主動敲代碼做到沒？教材實踐上有什么經驗教訓？
    會主動完成作業，并不能稱作為積極主動敲代碼，很多的代碼本源就來自書上的代碼，從百度上搜索好久的代碼一翻書，代碼就在書上。

課堂項目實踐

  • 課堂實踐鏈接（沒有的可以不列）
    • 課堂實踐-Scanner&JDB練習
    • 類的編寫實踐
    • Random和NumberFormat測試
    • Interface實踐
    • 復數/有理數計算器（接口）
    • 文件讀寫
    • 期中測試
    • 時間復雜度分析
    • ArrayStack類的實現和測試
    • 后綴表達式求值
    • 出門條-棧-數組實現棧
    • 鏈棧補全（LinkedStack補全）size\isEmpty\toString\Push
    • 鏈表插入
    • 鏈表實踐
    • CircularArrayQueue方法補全
    • 線性表實踐（ArrayList、LinkedList）
    • 查找及ASL作業（編程+計算）
    • 二分查找（折半查找）實踐
    • 快速排序測試(必須有中間過程)
    • 選擇排序最壞情況
    • 樹-計算題
    • 中序和先序計算二叉樹結構
    • 二叉樹的建立和層序遍歷法實踐
    • 遞歸前中后序和非遞歸前中序遍歷實踐
    • 堆排序過程測試
    • 二叉排序樹實踐
    • 哈夫曼編碼實踐
    • 哈夫曼編碼測試
    • 圖實踐
    • 十字鏈表練習
    • 圖的DFS和BFS測試
    • 考試安排沖突問題（畫圖）
    • 最小生成樹測試
    • Dijkstra(迪杰斯特拉)算法測試
    • AOE/AOV練習
    • 拓撲排序實踐測試

課程收獲與不足

  • 自己的收獲（投入，效率，效果等）
    自己投入的時間還是很多的，畢竟這個學科的任務量大，講課快，好多知識點要自學；
    效率我認為自己并不高，因為很多時候自己的學習沒有方法，導致很多時間白白的浪費了。
    效果來說可能沒有自己最開始預期的那種感覺，但是有所收獲。
  • 自己需要改進的地方
    我認為自己需要改進學習效率，畢竟這么課任務量大，花了很多時間，但是結果沒有達到自己的要求。
  • 結對學習是不是真正貫徹了？寫一下你提供的幫助或接受了什么幫助，并對老師提供參考建議
    這門課雖然結課了，但是我并沒有真正的貫徹，只是簡簡單單的懂懂皮毛，也接受了來自同學，學長學姐們和老師的各種各樣的幫助。
    建議老師呢可以拆開這兩門課，信息量實在太大了，我這1KB的大腦接收不了1G的APP啊！！！
  • 問卷調查
    • 你平均每周投入到本課程有效學習時間有多少？
      一般來說，應該可以維持20個小時左右。
    • 每周的學習效率有提高嗎？你是怎么衡量的？
      emmmm這個嘛，學習效率時好時壞，也要和整體課業的任務與壓力有關，列如有的科目要考試了，精力就會放到那邊，學習的效率就會下降；有的時候心血來潮，學習效率就會提高。
    • 藍墨云班課的使用對你的學習有促進嗎？有什么建議和意見嗎？
      還是有幫助的，畢竟自己還可以找到提交的作業，日后可以看。對于藍墨云班課的看法我比較佛系，沒啥建議.....
    • 你覺得這門課老師應該繼續做哪一件事情？
      多帶著大家在實驗課一起敲一些代碼，可以更好的理解。
    • 你覺得這門課老師應該停止做哪一件事情？
      少布置一點作業吧，我們壓力也很大，救救孩子吧！

出你的總結中涉及到的鏈接的二維碼

  • 第一周

  • 第二周

  • 第三周

  • 第四周

  • 第五周

  • 第六周

  • 第七周

  • 第八周

  • 第九周

  • 第十周