資料結構第三章
t1223-3-28朱俊傑
1、原理討論題：
1、順序儲存的三個優點：
1思路和實現都比較簡單，容易理解。
2不用為表示結點間的邏輯關係而增加額外的儲存空間。
3順序表具有按元素序號隨機訪問的特點。
順序比鏈式節約空間。是因為鏈式結構每乙個節點都有乙個指標儲存域。
順序支援隨機訪問，方便操作
鏈式的要比順序的方便
2、線性結構
3、順序儲存和鏈式儲存
4、判斷是否為空、求順序表長度、遍歷順序表所有元素、讀取乙個結點、修改乙個結點、插入乙個結點、刪除乙個結點、順序表所有元素反轉。
2、理論基本題：
線性鍊錶
線性鍊錶是具有鏈結儲存結構的線性表，它用一組位址任意的儲存單元存放線性表中的資料元素，邏輯上相鄰的元素在物理上不要求也相鄰，不能隨機訪問。一般用結點描述：結點（表示資料元素） =資料域（資料元素的映象） + 指標域（指示後繼元素儲存位置）。
概念在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。鏈式儲存方式即可以用於表示線性結構，也可用於表示非線性結構。
一般來說，**性表的鏈式儲存結構中，各資料結點的儲存符號是不連續的，並且各結點在儲存空間中的位置關係與邏輯關係也不一致。對於線性鍊錶，可以從頭指標開始，沿各結點的指標掃瞄到鍊錶中的所有結點。
線性表的查詢操作在鍊錶中的實現:
基本操作為: 使指標p始終指向線性表中第j個資料元素
status getelem_l(linklist l, int i, elemtype &e)// l為帶頭結點的單鏈表的頭指標。當線性表中存在第i個元素時，則將第i個資料元素的值賦給e並返回ok，否則返回error
直到第i個資料，才退出continue迴圈，並得到e=p->data，放回ok。
線性表的插入操作在鍊錶中的實現:
基本操作為: 找到線性表中第i-1個結點，修改其指向後繼的指標
有序對 改變為 和
statuslistinsert_l(linklist l, int i, elemtype e) // 尋找第i-1個結點
s = (linklist)malloc(sizeof(lnode)); // 生成新結點
s->data = e; s->next = p->next; // 插入l中
p->next = s;
returnok;
} // linstinsert_l演算法的時間複雜度為:o(listlength(l))
插入到1-2之間
**性表的鏈結儲存中，為了方便在表頭插入和刪除結點的操作，經常在表頭結點（儲存第乙個元素的結點）的前面增加乙個結點，稱之為頭結點或表頭附加結點。這樣原來的表頭指標由指向第乙個元素的結點改為指向頭結點，頭結點的資料域為空，頭結點的指標域指向第乙個元素的結點。
定義乙個帶頭結點的線性鍊錶型別：
typedefstruct lnode // 結點型別
*link,*position;
typedef struct// 鍊錶型別
linklist；
statu**akenode( link&p, elemtype e );
// 分配由p指向的值為e的結點，並返回ok；若分配失敗，則返回error
voidfreenode( link&p ); // 釋放p所指結點
建立帶頭結點的單鏈線性表：
voidcreatelist_l(linklist&l, int n) // 逆位序輸入n個元素的值，建立帶表頭結點的、//單鏈線性表l。
}本章的收穫、體會:
malloc函式其作用是在動態儲存區中分配乙個長度為size的連續空間。此函式返回值是乙個指向分配域起始位址的指標（基型別為void).如果此函式未能分配成功地執行（例如記憶體空間不足）則返回空指標（null)。
calloc函式其作用是在記憶體的動態區儲存中分配n個長度為size的連續空間，函式返回乙個指向分配起始域位址的指標;如果分配不成功，返回null
free函式其作用是釋放由p指向的記憶體區，使這部分記憶體區能被其它變數使用。p是最近一次呼叫的calloc或malloc函式時返回的值。free無返回值。
define巨集定義
線性表的兩類不同的儲存結構，不受空間限制，在節點的插入、刪除方便，不用大量移動資料，資料結構中的線性表、順序表和煉表之間的特點和區別，陣列就是順序表，
單鏈表就是鍊錶，可以線性的存貯資料，順序表中的元素是按其物理位置排列的，鍊錶是通過指標來描述其邏輯位置的，鍊錶是指標與型結構體型別的一種結合體，鍊錶的每乙個節點都應該包含兩個部分：節點資料和指向下一節點的指標。因為下一節點具有與該節點相同的結構，所以鍊錶節點的型別定義時，需要引用正在定義的型別的本身，與陣列相比，鍊錶在插入和刪除節點時比的插入和刪除要簡單，開銷更小，但鍊錶不可隨機訪問它的節點，只能通過指向煉表表頭的指標順序訪問相應的節點。
資料結構課後習題第三章
1.對於棧，運算元據的原則是 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.一般情況下，將遞迴演算法轉換成非遞迴應通過設定 實現。a.陣列 b.線性表 c.佇列d.棧 3.棧和佇列的共同點是 a.都是先進後出b.都是先進先出 c.只允許在端點處插入和刪除元素 d.沒有共同點 4.若元素...
資料結構課後習題及解析第三章
第三章習題 1.按圖3.1 b 所示鐵道 兩側鐵道均為單向行駛道 進行車廂排程，回答 如進站的車廂序列為123，則可能得到的出站車廂序列是什麼？如進站的車廂序列為123456，能否得到435612和135426的出站序列，並說明原因。即寫出以 s 表示進棧 以 x 表示出棧的棧操作序列 2.設佇列中...
資料結構1800題第三章
第3章棧和佇列 一選擇題 1.對於棧運算元據的原則是 青島大學 2001 五 2 2分 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.在作進棧運算時,應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為 為了增加記憶體空間的利用率...