計算機(jī)問題求解：基本的數(shù)據(jù)結(jié)構(gòu)

計算機(jī)問題求解

–

論題2-8

基本的數(shù)據(jù)結(jié)構(gòu)問題1:全校學(xué)生分布在整個操場上,怎么樣就算是有“結(jié)構(gòu)”了？問題2：你能夠說說在你用過的程序設(shè)計語言中有什么東西體現(xiàn)了數(shù)據(jù)的結(jié)構(gòu)？問題3：仍然以全校的學(xué)生為例，你能夠討論一下“結(jié)構(gòu)”和物理位置是什么關(guān)系？問題4：你認(rèn)為隊列與棧與其元素的物理位置分布有關(guān)嗎？問題5：你根據(jù)什么區(qū)分這兩個圖各自描述哪種結(jié)構(gòu)？抽象數(shù)據(jù)類型的概念–以隊列為例Queuecreate()

Precondition:none.

Postconditions:Ifq=create(),then:qreferstoanewlycreatedobjectisEmpty(q)=true;BooleanisEmpty(Queueq)

Precondition:none.

Objectfront(Queueq)

Precondition:isEmpty(q)=false;voidenqueue(Queueq,Objecte)

Precondition:none.

Postconditions:

IfisEmpty(/q/)=true,front(q)=e;

IfisEmpty(/q/)=false,

front(q)=front(/q/);

isEmpty(s)=false;voiddequere(Queueq)

Precondition:isEmpty(q)=false;

Postconditions:

（精確描述需要特殊手段）注意：整個描述中完全不設(shè)計如何“實現(xiàn)”，甚至不涉及“指針”。問題６：堆棧與隊列的本質(zhì)差別是什么？為什么我們需要這種差別？問題７：你能解釋下列情況在計算機(jī)中實現(xiàn)的關(guān)鍵嗎？１.你用鼠標(biāo)連續(xù)點擊了屏幕幾個不同的按鈕，計算機(jī)均能夠正確的一一相應(yīng)。２.你輸入計算式２＋３＊５，計算機(jī)會正確的算出結(jié)果１７，而不是象簡單計算器上只能得到２５。問題8:你覺得在我們的討論的“結(jié)構(gòu)”的背后是否有什么基本的數(shù)學(xué)概念嗎？從集合到“動態(tài)集合”問題9：“結(jié)構(gòu)”體現(xiàn)在那里？問題10：“實現(xiàn)”(implementation)數(shù)據(jù)結(jié)構(gòu)是什么意思？“指針”在數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)中有什么作用？鏈表：一切操作均圍繞指針問題11：這個結(jié)構(gòu)有什么不便之處嗎？問題12：刪除一個對象的代價是多少？進(jìn)一步的改進(jìn)監(jiān)控“邊界條件”問題13;為什么是“改進(jìn)”？“此指針”未必是“彼指針”通常我們熟悉的第一個“指針”是某種程序設(shè)計語言中提供的“語言設(shè)施”。在用“指針”方法實現(xiàn)一種數(shù)據(jù)結(jié)構(gòu)時，所謂的“指針”未必是語言中的指針，可以是實現(xiàn)其目的的其他手段。動態(tài)結(jié)構(gòu)的存儲管理基本原理：在一個數(shù)組空間維護(hù)兩個鏈表，“實際數(shù)據(jù)”和“可用空間”?！按讼碎L”問題14：你能解釋一下這幾個圖嗎？順便問一下：書上圖10.8是什么意思?根樹:如何從鏈表的角度看它?RootInnernodeBranchingnodeLeafLevel0Level1Level2Level3Height=3如何任意結(jié)點最多有兩個子結(jié)點,則該根樹成為二叉樹(binarytree),顯然用指針實現(xiàn)鏈表的方法很容易擴(kuò)展到二叉樹,但是…問題15:“但是”什么?這其實意味著:

即使問題邏輯需要多叉樹,我們也可以將其轉(zhuǎn)換為二叉樹來實現(xiàn)。注意：此轉(zhuǎn)換不可逆。課外作業(yè)TCpp.235-:ex.10.1-4;10.1-5;10.1-6TCpp.240-:ex.10.2-1;10.2-2;10.2-3;10.2-6;T