實驗名稱： 實驗——2.1
學生姓名：
班級：班內序號：
學號：日期：
1．實驗要求
1. 實驗目的：熟悉c++語言的基本程式設計方法，掌握整合編譯環境的除錯方法；學習指標、模板類、異常處理的使用；掌握線性表的操作的實現方法；學習使用線性表解決實際問題的能力。
2. 實驗內容：完成單鏈表的基本功能，編寫測試main()函式測試線性表的正確性。
2. 程式分析
2.1 儲存結構
儲存結構：單鏈表。
2.2 關鍵演算法分析
1.關鍵演算法：
查詢：按位查詢，設工作指標p，用j作為計數器，從開頭向後面查詢，知道查詢到第i個元素返回，如果沒找到則返回0值。
插入：在單鏈表的第i個位置上插入值為x的元素，先找到i-1的元素，然後在其後插。（其中又分為前插和後插）
刪除：刪除先行表中的第i個元素，並將該元素的值返回。先進行查詢操作，找到第i-1個元素，再對第i個元素刪除。
2.**詳細分析：
1.刪除操作
圖1 刪除結點示意圖
演算法步驟：
①從第乙個結點開始，查詢第i-1個元素，設為p指向該結點；
②設q指向第i個元素：q = p->next;
③摘鏈，即將q元素從鍊錶中摘除：p->next = q->next;
④儲存q元素的資料：x = q->data;
⑤釋放q元素：delete q;
2.前插操作
圖2 前插操作示意圖
演算法步驟：
從第乙個結點開始，查詢p所指結點的前乙個結點，設為q指向該結點；
②在堆中建立新結點：node * s = new node ;
③將x寫入到新結點的資料域：s->next = p;
④修改新結點的指標域：s->next = p；
⑤修改q結點的指標域，將新結點加入到鍊錶中：q->next = s;
3.改進後的前插操作
圖3 改進後的前插操作示意圖
演算法步驟：
在堆中建立新結點：node * s = new node；
②將p結點的資料域寫到新結點的資料域：s->data = p->data；
③修改新結點的指標域：s->next = p->next；
④修改p結點的指標域，將新結點加入到鍊錶中：p->data = x；
⑤將x寫入到p結點的資料域：p->data = x；
4.查詢操作（按位查詢）
演算法步驟:
①建立乙個新的工作指標：node * p = front -> next；
②初始化計數器：int j = i；
③將指標和計數器都向後移：p = p->next j++；
④查詢完畢時返回第i個元素的位址：return p；
⑤如果沒找到元素，返回0值：return 0；
3.時間複雜度計算：
查詢：平均時間複雜度o(n)
插入：時間複雜度為o(n)
改進後的插入：時間複雜度為o(1)
刪除：時間複雜度o(1)
3. 程式執行結果
1、 測試主函式流程：流程圖如圖2所示
圖2 流程圖標意圖
2、 測試條件：在主函式中建立乙個陣列，其中有8個元素，將該陣列儲存到單鏈表中，再實現鍊錶基本運算。刪除任意乙個位置的元素（比如i=6），在第2個位置插入數88。
每次操作後都用printlist函式遍歷鍊錶已得到結果。 查詢時，用get函式按位置查詢某乙個位置（例如i=3）上的元素。
3、 測試結論：所編單鏈表正確地儲存了新建立的陣列，完成了插入、刪除、遍歷、查詢等基本功能。
4. 總結
1、除錯時出現的問題及解決的方法
1.之前沒有寫遍歷函式printlist，導致在主函式中無法在每次操作後進行遍歷。後來把遍歷函式補寫上了，問題解決了。
2通過此次實驗，綜合應用了單鏈表的性質，對單鏈表的理解更深了，也逐漸掌握。
北郵資料結構實驗報告排序
北京郵電大學 資料結構試驗報告 實驗名稱 實驗四排序 學生姓名 班級 班內序號 學號 日期 2014年1月4日 學習 實現 對比各種排序演算法，掌握各種排序演算法的優劣，以及各種演算法使用的情況。使用簡單陣列實現下面各種排序演算法，並進行比較。排序演算法 1 插入排序 2 希爾排序 3 氣泡排序 4...
北郵資料結構實驗二題目
2008級資料結構實驗報告 實驗名稱 實驗二棧和佇列 學生姓名 班級 2008211113 班內序號 學號 日期 2009年11月8日 1 實驗要求 通過選擇下面五個題目之一進行實現，掌握如下內容 進一步掌握指標 模板類 異常處理的使用 掌握棧的操作的實現方法 掌握佇列的操作的實現方法 學習使用棧解...
資料結構實驗報告
實驗報告 實驗課程 資料結構 實驗專案實驗 專業 電腦科學與技術 姓名於凡 學號 10703070328 指導教師汪林林 實驗時間 2008 12 7 重慶工學院計算機學院 實驗一線性表 1.實驗要求 掌握資料結構中線性表的基本概念。熟練掌握線性表的基本操作 建立 插入 刪除 查詢 輸出 求長度及合...