[實驗目的]
本次實驗的主要目的在於熟悉線性表的基本運算在兩種儲存結構上的實現,其中以熟悉鍊錶的各種操作為側重點。通過本次實習還可幫助讀者複習高階語言的使用方法。
[問題描述]
試設計乙個非遞迴演算法在o(n)時間內,將乙個含有n個元素的單鏈表實現就地逆置,要求其輔助空間為常量。
[基本要求]
利用單鏈表儲存結構模擬就地逆置過程,輸出單鏈表的初始順序和逆置後順序。
[測試資料]
n 的初值為5;元素:29,76,18,45,25(正確的結果應為25,45,18,76,29)。也可以自選元素值。
[實現提示]
程式執行後首先要求使用者指定元素個數值,然後分別讀取元素,輸出單鏈表的初始順序和逆置後順序。
[思考]
(1) 描述你所設計的演算法思路。
用p指標掃瞄原單鏈表,先將頭節點l的next域置為null而變成乙個空鍊錶,然後用*p結點採用頭插法插入到l中由前往後將每個結點依次從頭結點鍊錶中摘下,作為第乙個結點插入到帶頭結點鍊錶中。
(2) 分析你所設計的演算法的時間複雜度。
時間複雜度為 o(1)
[源程式**]:
#include
using namespace std;
typedef struct list
list;
list * creat()//建立鍊錶
else flag = 0;
} p->next = null;
return head;
}list *reverse(list *head)//鍊錶逆置
head->next = null;
head = p1;
return head;
}void delete(list *h)//銷毀鍊錶
}void show(list *head)//列印鍊錶
cout<}
int main()
[選作內容]
利用順序儲存結構模擬實現逆置過程的演算法描述及**。
解:演算法如下:
#define listsize 100 // 假定表空間大小為100
typedef int datatype;//假定datatype的型別為int型
typedef struct}
資料結構實驗線性表
實驗報告 電腦科學與技術學院 2015 年 10 月 8 日 實驗專案名稱線性表的基本操作 1 實驗目的 1 掌握上機除錯線性表的基本方法 2 掌握線性表的一些基本操作 二 實驗內容 問題描述 實現線性表的建立 修改元素 插入 刪除等線性表的基本操作。基本要求 1 依次從鍵盤讀入資料,建立線性表 3...
實驗1線性表的應用 選做 一元多項式相加
1.實驗題目 鍊錶的應用 2.實驗內容 一元多項式相加 3.實驗目的 掌握鍊錶的概念與原理,運用其原理設計並完成實驗題目中的內容。4.實驗要求 實驗課前認真做好相關內容的預習及偽碼的編寫 寫在紙上及盤中均可 在實驗課中除錯並執行,並驗證其正確性。5.概要設計原理 6.詳細程式清單及注釋說明 incl...
實驗4線性表的順序表示和實現
浙江大學城市學院實驗報告 課程名稱資料結構 實驗專案名稱實驗四線性表的順序表示和實現 學生姓名孫臻傑專業班級軟體1403學號 31401375 實驗成績指導老師 簽名日期 一.實驗目的和要求 1 掌握線性表的順序儲存結構 2 掌握線性表的動態分配順序儲存結構及基本操作的實現函式 3 進一步熟悉資料結...