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

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

<

目錄節(jié)選：

第1章 緒論

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

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

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

1.4 算法和算法分析

第2章 線性表

2.1 線性表的類型定義

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

2.3 線性表的鏈式表示和實現(xiàn)

2.4 一元多項式的表示及相加

第3章 棧和隊列

3.1 棧

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

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

3.4 隊列

3.5 離散事件模擬

第4章 串

4.1 串類型的定義

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

4.3 串的模式匹配算法

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

……

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

第1章緒 論

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

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

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

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

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

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

……