數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版 附試題及答案

數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版是一本pdf中文版的高清電子書(shū)，作者嚴(yán)蔚敏，吳偉民。全書(shū)總共分為12章節(jié)，第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽像數(shù)據(jù)類型等基本概念；第2章至第7章從抽像數(shù)據(jù)類型的角度，分別討論線性表，棧，隊(duì)列，串，數(shù)組，廣義表，樹(shù)和二叉樹(shù)以及圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；第8章綜合介紹操作系統(tǒng)和編譯程序中涉及的動(dòng)態(tài)存儲(chǔ)管理的基本技術(shù)；第9章到第11章討論查找和排序，除了介紹各種實(shí)現(xiàn)方法之外，并著重從時(shí)間上進(jìn)行定性或定量的分析和比較；第12章介紹常用的文件結(jié)構(gòu)。另外軟件包中還附帶了數(shù)據(jù)結(jié)構(gòu)試題及答案，以方便各位讀者學(xué)習(xí)和參考。

<

目錄節(jié)選：

第1章 緒論

1.1 什么是數(shù)據(jù)結(jié)構(gòu)

1.2 基本概念和術(shù)語(yǔ)

1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)

1.4 算法和算法分析

第2章 線性表

2.1 線性表的類型定義

2.2 線性表的順序表示和實(shí)現(xiàn)

2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.4 一元多項(xiàng)式的表示及相加

第3章 棧和隊(duì)列

3.1 棧

3.2 棧的應(yīng)有和舉例

3.3 棧與遞歸的實(shí)現(xiàn)

3.4 隊(duì)列

3.5 離散事件模擬

第4章 串

4.1 串類型的定義

4.2 串的表示和實(shí)現(xiàn)

4.3 串的模式匹配算法

4.4 串操作應(yīng)用舉例

……

章節(jié)內(nèi)容

第1章緒 論

自1946 年第一臺(tái)計(jì)算機(jī)問(wèn)世以來(lái)，計(jì)算機(jī)產(chǎn)業(yè)的飛速發(fā)展已遠(yuǎn)遠(yuǎn)超出人們對(duì)它的預(yù)料，在某些生產(chǎn)線上，甚至幾秒鐘就能生產(chǎn)出一臺(tái)微型計(jì)算機(jī)，產(chǎn)量猛增，價(jià)格低廉，這就使得它的應(yīng)用范圍迅速擴(kuò)展。如今，計(jì)算機(jī)已深入到人類社會(huì)的各個(gè)領(lǐng)域。計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算，而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。與此相應(yīng)，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計(jì)帶來(lái)一些新的問(wèn)題。為了編寫(xiě)出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門(mén)學(xué)科形成和發(fā)展的背景。

1.1 什么是數(shù)據(jù)結(jié)構(gòu)

一般來(lái)說(shuō)，用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)，大致需要經(jīng)過(guò)下列幾個(gè)步驟：首先要從具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問(wèn)題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型為線性方程組；預(yù)報(bào)人口增長(zhǎng)情況的數(shù)學(xué)模型為微分方程。然而更多的非數(shù)值計(jì)算問(wèn)題無(wú)法用數(shù)學(xué)方程加以描述。下面請(qǐng)看 3個(gè)例子。

例1-1 圖書(shū)館的書(shū)目檢索系統(tǒng)自動(dòng)化問(wèn)題。當(dāng)你想借閱一本參考書(shū)不知道書(shū)庫(kù)中是否有的時(shí)候；或者，當(dāng)你想找某一方面的參考書(shū)而不知圖書(shū)館內(nèi)有哪些這方面的書(shū)時(shí)，你都需要到圖書(shū)館去查閱圖書(shū)目錄卡片。在圖書(shū)館內(nèi)有各種名目的卡片：有按書(shū)名編排的，有按作者編排的，還有按分類編排的，等等。若利用計(jì)算機(jī)實(shí)現(xiàn)自動(dòng)檢索，則計(jì)算機(jī)處理的對(duì)象便是這些目錄卡片上的書(shū)目信息。列在一張卡片上的一本書(shū)的書(shū)目信息可由登錄號(hào)、書(shū)名、作者名、分類號(hào)、出版單位和出版時(shí)間等若干項(xiàng)組成，每一本書(shū)都有惟一的一個(gè)登錄號(hào)，但不同的書(shū)目之間可能有相同的書(shū)名，或者有相同的作者名，或者有相同的分類號(hào)。由此，在書(shū)目自動(dòng)檢索系統(tǒng)中可以建立一張按登錄號(hào)順序排列的書(shū)目文件和 3張分別按書(shū)名、作者名和分類號(hào)順序排列的索引表，如圖 1.1 所示。由這4張表構(gòu)成的文件便是書(shū)目自動(dòng)檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某個(gè)特定要求（如給定書(shū)名）對(duì)書(shū)目文件進(jìn)行查詢。諸如此類的還有查號(hào)系統(tǒng)自動(dòng)化、倉(cāng)庫(kù)賬目管理等。在這類文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。

例 1-2 計(jì)算機(jī)和人對(duì)弈問(wèn)題。計(jì)算機(jī)之所以能和人對(duì)是因?yàn)橛腥藢?duì)弈的策略事先已存人計(jì)算機(jī)。由于對(duì)弈的過(guò)程是在一定規(guī)則下隨機(jī)進(jìn)行的，所以，為使計(jì)算機(jī)能靈活對(duì)弈就必須對(duì)對(duì)弈過(guò)程中所有可能發(fā)生的情況以及相應(yīng)的對(duì)策都考慮周全，并且，一個(gè)“好”的棋手在對(duì)弈時(shí)不僅要看棋盤(pán)當(dāng)時(shí)的狀態(tài)還應(yīng)能預(yù)測(cè)棋局發(fā)展的趨勢(shì)，甚至最后結(jié)局。因此，在對(duì)弈問(wèn)題中，計(jì)算機(jī)操作的對(duì)象是對(duì)弈過(guò)程中可能出現(xiàn)的棋盤(pán)狀態(tài)一一稱為格局。例如圖1.2（a）所示為井字棋的一個(gè)格局，而格局之間的關(guān)系是由比賽規(guī)則決定的。通常，這個(gè)關(guān)系不是線性的，因?yàn)閺囊粋€(gè)棋盤(pán)格局可以派生出幾個(gè)格局，例如從圖1.2（a）所示的格局可以派生出 5個(gè)格局如圖1.2（b）所示而從每一個(gè)新的格局又可派生出 4 個(gè)可能出現(xiàn)的格局。因此，若將從對(duì)弈開(kāi)始到結(jié)束的過(guò)程中所有可能出現(xiàn)的格局都畫(huà)在一張圖上，則可得到一倒長(zhǎng)的“樹(shù)”。“樹(shù)根”是對(duì)弈開(kāi)始之前的棋盤(pán)格局，而所有的“葉子”就是可能出現(xiàn)的結(jié)局，對(duì)的過(guò)程就是從樹(shù)根沿樹(shù)權(quán)到某個(gè)葉子的過(guò)?！皹?shù)”可以是某些非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型，它也是一種數(shù)據(jù)結(jié)構(gòu)。

例 1-3 多路口交通燈的管問(wèn)題。通常在十路口只設(shè)紅綠兩色的交通燈便可保持正常的交通秩序，而在多叉路口需設(shè)幾種顏色的交通燈才能既使車(chē)輛相互之間不碰撞，又能達(dá)到車(chē)輛的大流通

……