20192326 2020-2021-1 《數據結構與面向對象程序設計》課程總結

一、課程內容總結

第一章 緒論

本章介紹了Java程序設計語言和基本的程序開發過程。介紹了面向對象的開發方法,包括相關的概念和術語。

了解Java程序設計語言，了解程序編譯運行的步驟，理解問題求解的一般方法，了解軟件開發的一般過程，了解面向對象技術相關概念，面向對象的程序設計，類是對象的藍圖，虛擬機介紹與安裝，IDEA介紹與安裝。

第二章 數據和表達式

介紹了Java中使用的基本數據類型及執行計算時表達式的使用。討論了數據類型之間的轉換,以及如何借助于Scanner類交互地從用戶讀入輸入。

• 字符串
• print及println方法
• 字符串連接
• 轉義字符
• 變量和賦值
• 變量
• 賦值語句
• 常量
• 基本數據類型
• 整型和浮點型
• 字符類型
• boolean類型
• 表達式
• 算術運算符
• 運算符優先級
• 自增及自減運算符
• 賦值運算符
• 數據轉換
• 轉換技術
• 讀輸入數據
• Scanner類

第三章 使用類和對象

本章介紹了討論對象的創建及對象引用變量的使用，探討String類提供的服務，探討Random類和Math類提供的服務。

創建對象

• String類
• 包
• Random類
• Math類

第四章 條件和循環

本章主要介紹了if和switch語句執行基本的判定，分別使用while、do、和for循環重復執行語句，探討用于判定的布爾表達式，為了分析并讀入文本文件中的重復輸入,再次討論了Scanner類。

• if語句可以讓程序選擇是否執行一條特定的語句。
• 循環語句可讓程序多次執行同一條語句。
• 可用邏輯運算符構造復雜的條件。
• if-else語句可在條件為真時實現一個操作,在條件為假時實現另一個操作。
• 在嵌套的if語句中, else子句與最近尚未匹配的if相匹配

第五章 編寫類

編寫類

• 類的定義：屬性+方法；
• 類的封裝、形參實參；
• 構造方法不應該有返回值；
• 構造方法提倡封裝；
• 程序的測試；

第七章 數組

本章主要講了定義并使用數組來組織數據，討論邊界檢查及容量管理技術，討論數組作為對象及對象數組的問題。

• 數組
• 數組實例化；
• 數組越界問題排查與預防；

第八章 繼承

本章主要討論類繼承的設計機制，說明抽象類的目的及使用方法，討論與繼承有關的可見性問題

• 繼承
• 繼承是從已有類派生出新類的過程；
• 父類與子類；
• 子類可以復寫父類的方法；
• 抽象類不能實例化；

第九章 多態

探討了綁定的概念,以及它與多態的關系。之后研究了如何使用繼承或接口來完成多態引用。與多態相關的設計問題也在這一章介紹。

• 多態
• 多態引用可以在不同的時候指向不同類型的對象；
• 接口是一組抽象方法，所以不能被實例化；
• 方法的參數可以是抽象的；

第十章 異常

介紹了異常處理及不捕獲異常時的后果。探討了try-catch語句,分析了異常的傳播。本章還介紹了處理輸人/輸出時的異常使用,給出了一個編寫文本文件的例子。

• 異常
• 異常代未正確處理的對象；
• trycatch語句可以處理特定類型的異常；
• I/O異常及其處理；

第十一章 遞歸

介紹了遞歸的概念、遞歸的實現及其正確的用法。

• 遞歸
• 遞歸允許方法調用自己；
• 每次遞歸調用某一方法時，都創建了新的局部變量和參數；

第十二章 算法分析

討論了包括遞歸算法在內的算法復雜度的分析技術,介紹了大0符號。

第十三章 查找與排序

探討了線性查找和二分查找算法,還介紹了5個排序算法,其中包括平方階及O(n logn)的算法。同時還研究了這些算法的效率。
查找與排序

高效的查找可以減少查找次數與時間；
二分查找等查找算法各自適用于不同的情況；
選擇排序、插入排序等排序方法也是需要面對不同情況具體分析；

第十四章棧

介紹了集合的概念,確立了將接口與實現分開的重要意義。我們將棧作為集合的第一個例子,介紹了棧的動態及定長的兩種實現方式。

• 棧
• 后進先出；
• 集合的介紹；
• 鏈表的介紹；
• 棧、鏈表各有優劣

第十五章 隊列

介紹了隊列的概念,然后作為工具來幫助我們解決問題,最后研究所使用的數據結構。討論了基于數組和動態鏈表的兩種實現方式。

• 隊列
• 隊列的介紹
• 先進先出

第十六章 樹

介紹了樹的術語和相關概念，討論了不同的實現策略，詳細介紹了遞歸的鏈式實現方法。

第十七章 二叉排序樹

• 二叉查找樹
• 左子樹小于結點，右子樹大于結點；
• 最有效的二叉查找樹是平衡的；
• 可以對二叉樹進行旋轉使其達到平衡；

第十八章 堆和優先隊列

介紹了查找樹的概念，以及典型的二叉查找樹的鏈式實現。

• 堆
• 堆是一個完全二叉樹；
• 大頂堆、小頂堆；
• 堆中元素的添加、刪除；

第十九章 圖

• 圖
• 無向圖、有向圖；
• 鄰接，路徑；
• 邊的權；
• 鄰接矩陣；
• 圖的遍歷：廣度優先與深度優先；

第二十章 哈希算法

涉及創建哈希表以便于存儲及獲取對象的相關概念。本章還介紹了Java API中與哈希相關的幾種應用。

二.所做的作業

*（1）安裝虛擬機；
*（2）實踐一，虛擬機編寫簡單程序；
*（3）編寫簡單的類；
*（4）測試一
*（5）復數計算器
*（6）類的繼承
*（7）概念常識問答
*（8）測試二；
*（9）棧實踐；
*（10）二分查找實踐；
*（11）樹——計算；
*（12）二叉樹建立，層序遍歷實踐；
*（13）哈夫曼編碼實踐；
*（14）測試三；
*（15）地圖染色實踐；
*（16）迪杰斯特拉算法實踐；
*（17）拓撲排序；
*（18）最小生成樹測試；
*（19）英語打卡；

三.實驗報告鏈接匯總實驗一 Linux基礎與Java開發環境

實驗一

*（1）基于命令行和IDE進行簡單的Java程序編輯、編譯、運行和調試。
*（2）練習Linux基本命令；
*（3）學習Java程序的JDB調試技能。
*（4）編寫簡單的Java程序。
http://www.rzrgm.cn/ylk0622/p/13782103.html

實驗二

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

實驗三

下載安裝并使用IDEA，完成下面實驗。
*（1）初步掌握單元測試和TDD

• (2）理解并掌握面向對象三要素：封裝、繼承、多態
  *（3）初步掌握UML建模
  *（4）完成藍墨云上 （1）-（5）實驗。
  http://www.rzrgm.cn/ylk0622/p/13817744.html
  

實驗四

*（1）Java Socket編程
1.學習藍墨云上教材《Java和Android編程》“第16章 輸入/輸出 ”和“第22章 網絡”，學習JavaSocket編程
2.結對編程。結對伙伴A編寫客戶端SocketClient.java，結對伙伴B編寫服務器端。
3.截圖加學號水印上傳藍墨云，代碼push到碼云，并撰寫實驗報告。
*（2）Java和密碼學
以結對的方式完成Java密碼學相關內容的學習（帖子中所有代碼和相關知識點需要學習）。提交學習成果碼云鏈接和代表性成果截圖，要有學號水印。
*（3）編寫有理數/復數計算器
結對編程，結對伙伴A編寫有理數計算器。結對伙伴B編寫復數計算器。截圖加水印上傳藍墨云，代碼push碼云。
*（4）遠程有理數計算器
結對編程，結對伙伴A編程實現客戶端，結果伙伴B實現服務器端。
客戶端通過鍵盤輸入一個有理數計算的公式（例如：1/4 + 1/6 = ）,并把該公式以字符串的形式發送給伙伴B（服務器端），服務器端根據字符串計算出結果為5/12,并把結果返回給客戶端A，A收到結果后輸出結果。截圖加水印上傳藍墨云，代碼push碼云。
*（5）遠程復數計算器
結對編程，結對伙伴B編程實現客戶端，結果伙伴A實現服務器端。
客戶端通過鍵盤輸入一個有理數計算的公式（例如：1/4 + 1/6 = ）,并把該公式以字符串的形式發送給伙伴A（服務器端），服務器端根據字符串計算出結果為5/12,并把結果返回給客戶端B，B收到結果后輸出結果。截圖加水印上傳藍墨云，代碼push碼云。
注意實驗四（4）和實驗四（5），一個人不能僅實現客戶端，必須實現一個客戶端和服務器，否則兩個實驗均不得分！！！
*（6）實驗報告
在規定時間前發表博客，標題“學號 實驗四 《數據結構與面向對象程序設計》實驗報告”
http://www.rzrgm.cn/ylk0622/p/13911698.html

實驗五

*（1）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調試應用程序
*（2）Activity測試
參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十五章：
構建項目，運行教材相關代碼
創建 ThirdActivity, 在ThirdActivity中顯示自己的學號，修改代碼讓MainActivity啟動ThirdActivity
*（3）UI測試
參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十六章：
構建項目，運行教材相關代碼
修改代碼讓Toast消息中顯示自己的學號信息
*（4）布局測試：
參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十七章：
構建項目，運行教材相關代碼
修改布局讓P290頁的界面與教材不同
*（5）事件處理測試：
參考《Java和Android開發學習指南(第二版)(EPUBIT,Java for Android 2nd)》第二十八章：
構建項目，運行教材相關代碼
提交代碼運行截圖和碼云Git鏈接，截圖要有學號水印，否則會扣分
http://www.rzrgm.cn/ylk0622/p/13929361.html

實驗六

*（1）鏈表練習，要求實現下列功能：
通過鍵盤輸入一些整數，建立一個鏈表；
這些數是你學號中依次取出的兩位數。 再加上今天的時間。
例如你的學號是 20172301
今天時間是 2018/10/1， 16：23：49秒
數字就是
20， 17，23，1， 20， 18，10，1，16，23，49
打印所有鏈表元素， 并輸出元素的總數。
在你的程序中，請用一個特殊變量名來紀錄元素的總數，變量名就是你的名字。 例如你叫 張三， 那么這個變量名就是
int nZhangSan = 0; //初始化為 0.
做完這一步，把你的程序簽入源代碼控制（git push）。

• (2)鏈表練習，要求實現下列功能：
  實現節點插入、刪除、輸出操作；
  繼續你上一個程序， 擴展它的功能，每做完一個新功能，或者寫了超過10行新代碼，就簽入代碼，提交到源代碼服務器；
  從磁盤讀取一個文件， 這個文件有兩個數字。
  從文件中讀入數字1， 插入到鏈表第 5 位，并打印所有數字，和元素的總數。 保留這個鏈表，繼續下面的操作。
  從文件中讀入數字2， 插入到鏈表第 0 位，并打印所有數字，和元素的總數。 保留這個鏈表，并繼續下面的操作。
  從鏈表中刪除剛才的數字1. 并打印所有數字和元素的總數。
• (3)鏈表練習，要求實現下列功能：
  使用冒泡排序法或者選擇排序法根據數值大小對鏈表進行排序；
  如果你學號是單數， 選擇冒泡排序， 否則選擇選擇排序。
  在排序的每一個輪次中， 打印元素的總數，和目前鏈表的所有元素。
  在（2）得到的程序中繼續擴展， 用同一個程序文件，寫不同的函數來實現這個功能。 仍然用 nZhangSan （你的名字）來表示元素的總數。
• (4)在android上實現實驗（1）和（2）
• (5)在android平臺上實現實驗（3)
  http://www.rzrgm.cn/ylk0622/p/13960565.html
  

實驗七

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

實驗八

• (1)參考教材PP16.1,完成鏈樹LinkedBinaryTree的實現（getRight,contains,toString,preorder,postorder）
  用JUnit或自己編寫驅動類對自己實現的LinkedBinaryTree進行測試，提交測試代碼運行截圖，要全屏，包含自己的學號信息
  課下把代碼推送到代碼托管平臺
• (2)基于LinkedBinaryTree，實現基于（中序，先序）序列構造唯一一棵二?樹的功能，比如給出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,構造出附圖中的樹
  用JUnit或自己編寫驅動類對自己實現的功能進行測試，提交測試代碼運行截圖，要全屏，包含自己的學號信息
  課下把代碼推送到代碼托管平臺
• (3)自己設計并實現一顆決策樹
  提交測試代碼運行截圖，要全屏，包含自己的學號信息
  課下把代碼推送到代碼托管平臺
• (4)輸入中綴表達式，使用樹將中綴表達式轉換為后綴表達式，并輸出后綴表達式和計算結果（如果沒有用樹，正常評分。如果用到了樹，即使有小的問題，也酌情給滿分）
  提交測試代碼運行截圖，要全屏，包含自己的學號信息
  http://www.rzrgm.cn/ylk0622/p/14110987.html
  

實驗九

圖的綜合實踐

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

四、代碼托管鏈接

https://gitee.com/besti1923/yang-likai-20192326

• 給出statistic.sh的運行結果，說明本學期的代碼量目標達到沒有？
  
  原定5000行代碼，可是只完成了3382行，沒有達到目標感覺有一點遺憾
• 加點代碼，改點代碼是理解的最好方式，參考編程的智慧，談談你的心得
  代碼很難，我覺得很難一個人獨立完成，這時就需要參考很多的資料，并且需要請教同學。一步一步慢慢理解代碼的含義，多練習，熟能生巧。
• 積極主動敲代碼做到沒？教材實踐上有什么經驗教訓？
  能沒做到隨時都在敲代碼，原因應該是自己不夠熟練。
• 課程收獲與不足
  收獲：認識了一門新的計算機語言，并且應用廣泛。
  不足：沒有好好掌握！！！

五. 問卷調查

• 你平均每周投入到本課程有效學習時間有多少？
  5個小時左右
• 每周的學習效率有提高嗎？你是怎么衡量的？
  每周實驗的多少決定了我學習的效率，實驗越多越難，我就會提高效率，害怕超時提交作業。
• 藍墨云班課的使用對你的學習有促進嗎？有什么建議和意見嗎？
  有，云班課功能很齊全，很實用。
• 你覺得這門課老師應該繼續做哪一件事情？
  繼續給我們帶了新知識。
• 你覺得這門課老師應該停止做哪一件事情？
  無