數(shù)據(jù)結(jié)構(gòu)常見問(wèn)題：12單元22 迷宮問(wèn)題

數(shù)據(jù)結(jié)構(gòu)課程常見問(wèn)題 -單元22迷宮問(wèn)題1迷宮問(wèn)題如何求解？解析：在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)。計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為：Loc()= Loc()+i*d特點(diǎn)是：線性表中邏輯上相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中也相鄰2線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）單向鏈表a、初始化b、單向鏈表的插入操作c、單鏈表的刪除操作、 （2）循環(huán)鏈表（3）循環(huán)鏈表雙向鏈表3在實(shí)際應(yīng)用中順序表和鏈表，究竟選用哪一種存儲(chǔ)結(jié)構(gòu)呢？順序表和鏈表各有短長(zhǎng)。這要根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)決定。通常有以下幾方面的考慮：順序表鏈表基于空間考慮分配方式靜態(tài)分配。程序執(zhí)行之前必須明確規(guī)定存儲(chǔ)規(guī)模。若線性表長(zhǎng)度n變化較大，則存儲(chǔ)規(guī)模難于預(yù)先確定估計(jì)過(guò)大將造成空間浪費(fèi)，估計(jì)太小又將使空間溢出機(jī)會(huì)增多。動(dòng)態(tài)分配只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。因此，當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。 存儲(chǔ)密度為1。當(dāng)線性表的長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。<1 基于時(shí)間考慮存取方法隨機(jī)存取結(jié)構(gòu)，對(duì)表中任一結(jié)點(diǎn)都可在O（1）時(shí)間內(nèi)直接取得 線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜。順序存取結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)，需從頭指針起順著鏈掃描才能取得。插入刪除操作在順序表中進(jìn)行插入和刪除，平均要移動(dòng)表中近一半的結(jié)點(diǎn)，尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間開銷就相當(dāng)可觀。在鏈表中的任何位置上進(jìn)行插入和刪除，都只需要修改指針。對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。