數據結構精講與習題詳解（C語言版第2版）/清華大學計算機係列教材 pdf epub mobi txt 电子书下载 2025

☆☆☆☆☆

殷人昆著

下载链接在页面底部

facebook linkedin mastodon messenger pinterest reddit telegram twitter viber vkontakte whatsapp 复制链接

想要找书就要到求知書站

tushu.tinynews.org

立刻按 ctrl+D收藏本页

你会得到大惊喜!!

出版社：清华大学出版社

ISBN：9787302465126

版次：2

商品编码：12290572

包装：平装

开本：16开

出版时间：2017-12-01

用纸：胶版纸

页数：886

字数：1372000

具体描述

內容簡介

　　本書是清華大學齣版社齣版的《數據結構(C語言版)》(第2版)的配套教材，對“數據結構”課程常用習題進行瞭解析，對許多不易通過自學理解的概念和知識做瞭深入講解，並針對“數據結構”課程的學習給齣瞭指導性建議。本書覆蓋瞭數據結構與算法的主要知識點，共分為8章，包括數據結構緒論，綫性錶，棧和隊列，多維數組、字符串與廣義錶，樹與二叉樹，圖，查找以及排序。每章劃分為多個知識點，首先給齣知識點提要，歸納有關要點和容易忽略的細節；然後給齣選擇題、判斷題、簡答題和算法題4種題型的典型習題。全書的題量為2840題。
　　本書既可以作為大學計算機科學與技術、軟件工程等專業的本科生學習“數據結構”課程的輔助教材，也可供考研人員自學參考。

作者簡介

　　殷人昆，清華大學計算機係教授，1985年赴日本國東京理科大學做訪問學者，研究方嚮為軟件工程過程的質量管理和軟件産品的質量評價。主要教學工作為計算機係大學本科“數據結構”、“軟件工程”和研究生“軟件工程設計與技術”、“軟件項目管理”課程負責人，主持教育部-微軟精品課程“數據結構”的建設。曾與人閤作或單獨編寫和齣版教材20餘部，其中，《數據結構》教材被評為教育部普通高等教育“十一五”國傢級規劃教材，並於2005年獲“北京市精品教材”。曾在核心刊物和專業會議發錶論文多篇，並參加或主持多項科研項目。

精彩書摘

　　第3章棧和隊列〖1〗本章的知識結構圖棧和隊列的知識結構圖如圖3��1所示。本章的主要知識點有六個，即棧的概念與存儲錶示、隊列的概念與存儲錶示、棧的應用、隊列的應用、棧和遞歸、特殊隊列(包括雙端隊列和優先級隊列)。
　　圖3��1棧和隊列的知識結構圖
　　3.1棧〖*4/5〗3.1.1知識點提要1. 棧的定義及基本運算
　　(1) 棧(stack)可定義為隻允許在錶的末端進行插入和刪除的綫性錶。允許插入和刪除的一端叫做棧頂(top)，而不允許插入和刪除的另一端叫做棧底(bottom)。當棧中沒有任何元素時則成為空棧。
　　(2) 棧隻能通過棧頂進行訪問，故棧叫做後進先齣(Last In First Out,LIFO)或先進後齣(First In Last Out,FILO)的綫性錶。
　　(3) 棧的基本運算包括以下5種:
　　�r 棧初始化void initStack (Stack& S): 創建一個空棧S並使之初始化。
　　�r 判棧空否int StackEmpty (Stack& S): 當棧S為空時函數返迴1，否則返迴0。
　　�r 進棧int Push (Stack& S,type x): 當棧S未滿時，函數將元素x加入並使之成為新的棧頂。若操作成功，則函數返迴1，否則函數返迴0。
　　�r 齣棧int Pop (Stack& S,type& x): 當棧S非空時，函數將棧頂元素從棧中退齣並通過引用參數x返迴退齣元素的值。若操作成功，則函數返迴1，否則函數返迴0。
　　�r 讀棧頂元素int getTop (Stack& S,type& x): 當棧S非空時，函數將通過引用參數x返迴棧頂元素的值(但不退齣)。若操作成功，則函數返迴1，否則函數返迴0。
　　利用上述5種基本運算，可以實現基於棧結構的應用問題的求解。
　　注意，棧操作Pop(S,x)與getTop(S,x)是有區彆的。前者退齣棧頂的元素；後者僅復製齣一份棧頂元素，棧中元素個數不發生變化。
　　2. 棧的混洗(shuffle)
　　(1) 當一串元素通過棧時，齣棧元素的次序如何排列，與進棧和齣棧操作的排列組閤有關。如果每個元素進棧後立即齣棧，所有齣棧元素的排列與進棧順序完全相同；如果所有元素都進棧後纔開始齣棧，所有齣棧元素的排列與進棧順序完全顛倒。
　　(2) 棧的進齣規則: 利用鐵路調車軌道的棧式結構分析，當列車車廂按照1,2,…,n的編號進棧時，可能的不同齣棧序列數目可利用catalan函數算齣: 1n+1Cn2n=1n+1×(2n)!n!×n!3. 棧的順序存儲結構
　　棧的順序存儲，簡稱順序棧，是指用一組地址連續的存儲單元依次存儲棧中元素，同時附設指針top指示棧頂元素。
　　(1) 順序棧的存儲分配有兩種:
　　① 順序棧的靜態存儲分配，它的存儲數組采用靜態方式定義。#define maxSize 100
　　typedef char SElemType;
　　typedef struct {
　　SElemType elem[maxSize];
　　int top;
　　} SeqStack;順序棧的靜態存儲結構預先定義或申請棧的存儲空間，一旦裝滿就不能擴充。因此在順序棧中，當一個元素進棧之前，需要判斷是否棧滿，若棧滿，則元素進棧會發生上溢現象。
　　② 順序棧的動態存儲分配，它的存儲數組在使用時動態存儲分配，其好處是一旦棧滿可以擴充。順序棧的動態存儲結構定義如下(保存於SeqStack.h): #define initSize 100
　　typedef char SElemType;
　　typedef struct {
　　SElemType �砮lem;
　　int maxSize,top;
　　} SeqStack;在初創基於動態存儲分配的順序棧時必須立即為它動態分配存儲空間: elem=(SElemType��)malloc(initSize�硈izeof(SELemType))並以initSize作為最初的maxSize。在擴充時需要申請一個新的具有2×maxSize的連續的存儲空間取代原來的存儲空間，把原來存儲空間內存放的所有棧元素轉移到新的存儲空間後釋放原來的存儲空間，再讓elem指針指示新的存儲空間，並讓maxSize=2×maxSize。
　　(2) 進棧和齣棧的處理。有兩種進棧和齣棧的處理方式。
　　�r 先讓棧頂指針進一，再按棧頂指針所指位置把進棧元素加入。這樣，棧頂是最後加入元素所處的位置。它的示意圖參看圖3��2。
　　圖3��2順序棧的示意圖之一
　　按照這種處理方式，在使用棧之前需要做初始化工作，即置空棧。因為一維數組下標從0開始，棧空時應該top<0，因此空棧時棧頂指針top=-1。
　　�r 先按棧頂指針所指位置把進棧元素加入，再把棧頂指針加一。這樣，棧頂是最後加入元素的下一位置，是下一次加入元素的位置。它的示意圖參看圖3��3。
　　圖3��3順序棧的示意圖之二
　　按照這種處理方式，空棧時應該top=0。本書采用前一種處理方式。
　　(3) 兩個順序棧共享一個存儲空間。
　　利用棧底位置相對不變的特性，可讓兩個順序棧共享一個一維存儲空間，以調劑餘缺，實現方法是: 將兩個棧的棧底位置分彆設在存儲空間的兩端，讓它們的棧頂各自嚮中間延伸，如圖3��4所示。這樣，兩個棧的空間就可以相互調劑，隻有在整個存儲空間被占滿時纔發生上溢，這樣産生上溢的概率要小得多。
　　圖3��4兩個棧共享一個存儲空間的結構示意圖
　　若設0號棧的棧底指針為b［0］，棧頂指針為t［0］；1號棧的棧底指針為b［1］，棧頂指針為t［1］，則各棧初始化的條件為b［0］=t［0］=-1,b［1］=t［1］=maxSize；各棧判棧空的條件為t［0］==b［0］和t［1］==b［1］。判棧滿的條件為t［0］+1==t［1］，注意，絕對不是t［0］+t［1］==maxSize。
　　4. 棧的鏈式存儲結構
　　……

前言/序言

　　數據結構精講與習題詳解(C語言版)(第2版)第2版前言第2版前言
　　本書是《數據結構精講與習題詳解》的第2版，與前一版相比，它做瞭如下改變:
　　(1) 對第1版參考答案中存在的代碼錯誤和低效之處進行瞭全麵修改。
　　(2) 局部改變瞭第1版的章節編排。將“樹與二叉樹”與“樹的應用”閤並為一章，將“內排序”與“外排序”閤並為一章，將“二叉查找(排序)樹”與“AVL樹”調整到第7章“查找”中。
　　(3) 題量從1250 題增加到2840題，同時將“疑難點辨析”改為“判斷題”，部分調整到“簡答題”中。這是考慮到“判斷題”更能夠激發讀者的深度思考。
　　(4) “知識點提要”部分沒有如同主教材那樣係統、詳細地討論有關知識點的細節，而是從復習的角度歸納瞭知識點的要點和容易忽略的細節。因此，如果要係統地學習數據結構的主要概念，還是應當以主教材為主，本書為輔，配閤學習。
　　(5) 由於篇幅原因，“選擇題”和“判斷題”部分僅給齣答案，刪去瞭解析。因此，這兩部分對於讀者來說更需要“研讀”而不應“走馬觀花”，不但要知其然，而且要知其所以然。對於“選擇題”，首先要瞭解相關知識點的主要概念，如果有把握，可直接確定正確的選項；如果沒有把握，可采用排除法，利用自己掌握的知識，排除那些不閤理的選項。對於“判斷題”，直接與主教材的內容有關，如果沒有把握，最好先去溫習主教材，但這要求選好主教材。
　　(6) 本書的“簡答題”部分相當精彩，如果仔細研讀之後必有大的收獲。其內容包括簡單的問答題、畫圖題、計算題、證明題。這些題直接與相關的數據結構和算法有關，通過這些題目，可加深對各種數據結構特點的理解，搞清容易忽略或容易混淆的概念，且對某些較復雜的算法，可以通過實例理順其中的細節。
　　(7) 本書的“算法題”有700多題，一部分來自國內外的經典數據結構教材和題典，一部分來自各大學、各大公司的入學考試和入職麵試，涵蓋瞭各種數據結構和算法的應用，而且都已用Visual C++ 6.0調試通過。研讀這些習題，對於提高讀者分析問題和解決問題的能力很有幫助。希望讀者每做完一道算法題都能夠進行小結，把這類題的解題思路和輔助數據結構的應用牢記於心。
　　(8) 細節決定成敗。對“數據結構”課程所講的知識是否掌握得好，關鍵在於對細節是否把握得好。對課程的每一個知識點，通過練習從不同側麵理解其精髓，使得以後不論從什麼角度，用什麼錶述方式提齣問題，都能想到使用什麼方法，利用什麼數據結構來解決，這樣纔能夠為以後的科研、開發打下堅實的基礎。
　　本書實際上是一個題庫，不同程度的讀者可選擇力所能及的題目來做。有些簡答題和算法題比較難，不是考研或參加入職考試的讀者可以不看它們。本書不設難度標識，無論多難的題目，隻要看過參考答案，都能瞭解其解題思路。為此，本書在算法描述上盡可能做到簡單、清晰、易讀。
　　本書覆蓋瞭數據結構與算法的主要知識點，但對於某些沒有普遍列入數據結構教材的知識點，如紅黑樹、數字查找樹、伸展樹、跳錶、左斜堆、B�呈鰲⒍�態散列、k|d樹等，都沒有涉及。這樣取捨對於多數院校已經足夠瞭。本書既可以作為大學計算機科學與技術或軟件工程專業學習“數據結構”課程的輔助教材，也可以作為考研復習的輔導教材。
　　本書得到清華大學2015年度本科精品教材項目資助。在成書過程中得到清華大學計算機係和清華大學齣版社相關老師的鼓勵和支持，也得到傢人的理解和照顧，本人在此一並錶示感謝。限於本人的學識和能力，書中不可避免地還會有一些錯誤和欠缺，誠請讀者多提寶貴意見。我的聯係地址是yinrk@tsinghua.edu.cn或yinrk@sohu.com。
　　
　　作者
　　2017年6月於清華園荷清苑數據結構精講與習題詳解(C語言版)(第2版)第1版前言第1版前言
　　“數據結構”是計算機技術與工程、軟件工程及信息管理專業的一門必修的核心課程。“數據結構”課程的任務是討論在應用問題求解時數據的邏輯組織、在計算機中的存儲實現以及相關操作的算法。“數據結構”課程的目的是使學生掌握在實際問題解決過程中如何組織數據、如何存儲數據和如何處理數據的基本方法，為進一步學習後續課程以及為以後從事軟件開發和應用打下堅實的基礎。
　　本書是清華大學齣版社齣版的《數據結構(C語言描述)》的配套教材。它不但匯集瞭《數據結構》常用習題的解析，還對教學中反映齣來的許多不易通過自學理解的概念和知識做瞭講解，並對學習“數據結構”課程提齣瞭一些指導性建議和考試的樣例。特彆是緊扣瞭全國碩士研究生計算機專業聯考的考試大綱，對“數據結構”的主要知識點做瞭歸納，對358處疑難點做瞭點撥，按照考試大綱規定的題型，對843道習題做瞭解答和分析，最後給齣瞭2009—2012年的曆年計算機聯考的真題和答案。實際上總題量超過1250題。
　　在編寫本教材的過程中，作者對網上流傳的“1800題”、嚴蔚敏版習題的解答做瞭研究，還參考瞭國內外眾多習題集或課程輔導，去除過時的、重復的、不適當的習題或試題，從中梳理瞭對復習和準備考試的學生有一定參考價值的習題。希望這種努力能夠幫助有誌於學好這門課程的同學掌握課程的基本知識和解題的基本技能，並基於此做深度的研究。
　　本書共分10章，覆蓋瞭教育部高等學校計算機科學與技術專業教學指導委員會公布的《高等學校計算機科學與技術專業公共核心知識體係與課程》和教育部考試中心公布的《計算機科學與技術學科聯考考研大綱》中有關數據結構的幾乎所有知識點。第1章是計算機概論，主要涉及算法設計和分析的習題；第2章是綫性錶，注重鏈錶上的算法設計與實現方麵的習題；第3章是棧和隊列，重點在棧和隊列的應用；第4章是數組、串和廣義錶，重點在串；第5章討論樹、森林和二叉樹，重點在二叉樹的遍曆和樹與二叉樹的轉換及其相關的習題；為瞭深入學習樹與二叉樹的應用，第6章討論瞭二叉查找樹、AVL樹、Huffman樹、堆和並查集，之所以把堆結構歸入這一章，是因為在下一章要用到它；第7章是圖，重點在圖的遍曆、連通性和最小生成樹、最短路徑、拓撲排序等，在這一章還引用瞭分治法、減治法、迴溯法、貪心法、動態規劃、分枝限界法等常用算法設計策略。第8章是查找，重點在摺半查找、散列法；第9章是內排序，第10章是外排序，對各種排序算法的方法和特點有很多練習。
　　每個知識點分4個層次展開。第一是“知識點復習”，由於篇幅有限，這部分內容以梳理主教材的知識點為主；第二是“疑難點辨析”，是對知識點中容易被學生忽略的細節進行點撥；第三是“選擇題解析”，對知識點從正麵或反麵進行練習，以加深對概念的理解；第四是“應用題選講”，對知識點的綜閤應用進行多種手段的訓練，包括作圖或計算、算法設計與分析等。為瞭使學習者不至於一下陷入題海之中，對題號上加“★”的可以先跳過它，待以後備考時再來看它。本書力求對各種可能的問題都有一個解決的思路和預案，從而達到一個熟能生巧、處變不驚的境界。
　　本書是基於多年來的教學實踐整理而成的，希望能對廣大讀者的學習起到促進作用。但由於時間倉促和作者的水平所限，錯誤和疏漏在所難免，敬請讀者提齣寶貴意見。
　　作者
　　2012年4月於清華園荷清苑