課堂習題參考解答
圖部分1. 以鄰接表為儲存結構，寫出圖的深度優先遍歷的非遞迴演算法。
答：補充圖的鄰接表儲存結構
void dfs(algraph g,vertexttype v)
if(top>0)
}}單鏈表部分
1.請寫乙個演算法將線性表(a1,a2,…,an)逆置為(an,an-1,….,a1)
typedef struct node
node,*linklist;
void invert(linklist head)
}2.在乙個遞增有序的線性表中，有數值相同的元素存在。若儲存方式為單鏈表，設計演算法去掉數值相同的元素，使表中不可再有重複元素。
typedef struct node
node,*linklist;
void delsame(linklist la)
else
pre->next=p;
}3.設head是帶頭結點的頭指標，試寫出演算法，按遞增次序輸出單鏈表中各結點的資料元素，並釋放結點所占用的空間。要求不允許使用陣列作為輔助空間。
typedef struct node
node,*linklist;
void minidelte(linklist head)
else
p=p->next;
printf(pre->next->data);
u=pre->next;
pre->next=u->next;
free(u);
}free(head);
}棧和佇列
1.請利用兩個棧s1和s2來模擬乙個佇列。已知棧的三種操作定義如下：
push(st,x)，元素x入棧；pop(st,x)，st棧定元素出棧並賦給變數x；sempty（st）,判斷st是否為空。那麼利用棧的操作來實現該佇列的三個操作：enqueue，插入乙個元素入隊；dequeue，刪除乙個元素出隊；queueempty，判斷隊列為空。
解：寫出佇列和棧的儲存結構。（注：假定棧s1作入隊，棧s2作出隊）
（1）入隊
int enqueue(seqstack *s1,elemtype x,seqstack *s2)
if(sempty(s2))
while(!sempty(s1))
push(s1,x);
}return 1;
}（2）出隊
void dequeue(seqstack *s2,seqstack *s1,elemtype *x)
else
if(sempty(s1))
else
while(!empty(s1))
pop(s1,x);
push(s2,*x);
pop(s2,x);
printf("出隊元素為",x);}}
（3）判隊空
int queueempty(seqstack s1,seqstack s2)
2.假設以帶頭結點的迴圈鍊錶表示佇列，並且只設乙個指標指向隊尾結點，但不設頭指標，請寫出相應的入隊和出隊演算法。
解：（1）入隊
void enqueue(linklist rear,elemtype x)
（2）出隊
void dequeue(linklist rear)
s=rear->next->next;
rear->next->next=s->next;
printf("出隊元素為：",s->data);
if(s==rear)
rear=rear->next;
free(s);}
資料結構習題解析
1.演算法的時間複雜度取決於 c a 問題的規模 b 待處理資料的初態 c a和b 2.計算機演算法指的是解決問題的步驟序列，它必須具備 b 這三個特性。a 可執行性 可移植性 可擴充性b 可執行性 確定性 有窮性c 確定性 有窮性 穩定性d 易讀性 穩定性 安全性 5 從邏輯上可以把資料結構分為 ...
複習資料結構習題解答
1 空格串是由空格組成的串，空串是不含任何字元的串，因此空格串和空串不是乙個概念。2 從整體上看，資料在儲存器內有兩種存放的方式 一是集中存放在乙個連續的記憶體儲存區中 一是利用儲存器中的零星區域，分散地存放在記憶體的各個地方。3 如果一棵滿二叉樹的深度為6，那麼它共有 63 個結點，有 32 個葉...
資料結構習題
第5章陣列和廣義表 一 選擇題 1.在以下講述中，正確的是 b a 線性表的線性儲存結構優於鍊錶儲存結構 b 二維陣列是其資料元素為線性表的線性表 c 棧的操作方式是先進先出 d 佇列的操作方式是先進後出 2.若採用三元組壓縮技術儲存稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉...