《數(shù)據(jù)結構常見問題：12單元22 迷宮問題》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構常見問題：12單元22 迷宮問題（2頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構課程常見問題 -單元22迷宮問題1迷宮問題如何求解？解析：在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結構。計算機存儲空間中的存儲地址為：Loc()= Loc()+i*d特點是：線性表中邏輯上相鄰的結點在存儲結構中也相鄰2線性表的鏈式存儲結構（1）單向鏈表a、初始化b、單向鏈表的插入操作c、單鏈表的刪除操作、 （2）循環(huán)鏈表（3）循環(huán)鏈表雙向鏈表3在實際應用中順序表和鏈表，究竟選用哪一種存儲結構呢？順序表和鏈表各有短長。這要根據(jù)具體問題的要求和性質來決定。通常有以下幾方面的考慮：順序表鏈表基于空間考慮分配方式靜態(tài)分配。程序執(zhí)行之前必須明確規(guī)定存儲

2、規(guī)模。若線性表長度n變化較大，則存儲規(guī)模難于預先確定估計過大將造成空間浪費，估計太小又將使空間溢出機會增多。動態(tài)分配只要內存空間尚有空閑，就不會產(chǎn)生溢出。因此，當線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結構為好。存儲密度為1。當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結構。1基于時間考慮存取方法隨機存取結構，對表中任一結點都可在O（1）時間內直接取得線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜。順序存取結構，鏈表中的結點，需從頭指針起順著鏈掃描才能取得。插入刪除操作在順序表中進行插入和刪除，平均要移動表中近一半的結點，尤其是當每個結點的信息量較大時，移動結點的時間開銷就相當可觀。在鏈表中的任何位置上進行插入和刪除，都只需要修改指針。對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲結構。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。