産品特色

內容簡介

本書匯集國內外眾多著名IT企業近幾年的數據結構麵試筆試真題並予以解析，按知識點類型對常見的數據結構難點和疑點進行瞭係統歸納和透徹剖析，並提供瞭一定數量的自測題以便於讀者自我檢驗。

　　全書邏輯清晰、通俗易懂，適閤參加IT企業校園招聘和麵試筆試環節的同學復習，也適閤數據結構和算法設計編程愛好者以及在校學生閱讀和提高。

作者簡介

李春葆：武漢大學教授，主要研究方嚮為數據挖掘和算法設計，從事近30年計算機C/C++語言、數據結構和算法設計等課程的第一綫本科教學工作，具備豐富的教學經驗，曾參於深圳名企的筆試和麵試題庫建設。齣版多本C/C++語言、數據結構、算法設計與分析及數據庫開發方麵的精品教材和教學輔導書。

李筱馳：

美國俄亥俄州立大學計算機科學專業碩士畢業，曾參加榖歌等名企麵試，具備比較豐富的企業筆試和麵試經驗。目前在西雅圖亞馬*總部工作。

精彩書摘

·第5章·

棧

* 棧的特點。

* 棧的各種存儲方法。

* 棧的基本運算算法設計。

* 棧的應用，例如求錶達式值和迷宮問題等。

* 靈活運用棧解決一些較復雜的應用問題。

5.1 棧基本算法設計

5.1.1 要點歸納

1．棧的定義

　　棧是一種特殊的綫性錶，其元素的邏輯關係是綫性關係，其特殊性體現在隻能在一端插入和刪除元素。棧錶現齣後進先齣的特點。

　　棧的基本運算如下。

* InitStack(&s;)：初始化棧，構造一個空棧s。

* DestroyStack(&s;)：銷毀棧，釋放棧s占用的存儲空間。

* StackEmpty(s)：判斷棧是否為空，若棧s為空，返迴真，否則返迴假。

* Push(&s;,e)：進棧，將元素e插入到棧s中作為棧頂元素。

* Pop(&s;,&e;)：齣棧，從棧s中刪除棧頂元素，並將其值賦給e。

* GetTop(s,&e;)：取棧頂元素，返迴當前的棧頂元素，並將其值賦給e。

　　【例5-1】設n個元素進棧序列是1、2、3、……、n，其輸齣序列是p1、p2、……、pn，若p1=3，則p2的值為（ ）。

　　A．一定是2 B．一定是1 C．不可能是1 D．以上都不對

　　答：當p1=3時，說明1、2、3先進棧，然後齣棧3，此時可以讓2齣棧，也可能讓4進棧後再齣棧，也可以讓4進棧、5進棧後再齣棧，……，從中可以看到，p2可能是2，也可能是4、……、n，但一定不能是1，答案為C。

2．棧的實現

　　與綫性錶采用順序錶或者鏈錶存儲一樣，棧可以采用順序棧或者鏈棧來實現。

　　如果需要用到兩個相同類型的棧，這時若為它們各自開闢一個數組空間，極有可能齣現這樣的情況：第1個棧已滿，再進棧就溢齣瞭，而另一個棧還有很多空閑存儲空間。解決這個問題的方法是將兩個棧閤起來，用一個數組來實現這兩個棧，這稱為共享棧。

　　在設計共享棧時，由於一個數組（大小為MaxSize）有兩個端點，兩個棧有兩個棧底，讓一個棧的棧底為數組的始端，即下標為0處，讓另一個棧的棧底為數組的末端，即下標為MaxSize-1，這樣在兩個棧中進棧元素時棧頂嚮中間伸展。

　　 順序棧

　　通常，順序棧類型SqStack的聲明如下：

typedef struct

{ T data[MaxSize]; //存放棧中的數據元素

int top; //存放棧頂指針,即棧頂元素在data數組中的下標

} SqStack; //順序棧類型

　　對於順序棧s，通常將s.data[0]一端作為棧頂，將s.data[MaxSize-1]一端作為棧底，初始時設置s.top=-1，對應的4個要素如下。

* 棧空的條件：s.top==-1。

* 棧滿的條件：s.top==MaxSize-1（data數組的最大下標）。

* 元素e的進棧操作：先將棧頂指針top增1，然後將元素e放在棧頂指針處。

* 齣棧操作：先將棧頂指針top處的元素取齣放在e中，然後將棧頂指針減1。

　　【例5-2】若一個棧用數組data[1..n]存儲，初始棧頂指針top為n，則以下元素x進棧的操作正確的是（ ）。

　　A．top++; data[top]=x; B．data[top]=x; top++;

　　C．top--; data[top]=x; D．data[top]=x; top--;

　　答：初始棧頂指針top為n，說明data[n]端作為棧底，在進棧時top應遞減，由於存在data[n]的元素，所以在進棧時應先將x放到top處，再將top遞減。答案為D。

前言/序言

前 言

　　數據結構求解問題的思路是“數據邏輯結構→存儲結構→基本算法實現→應用”，這一思路展示瞭計算邏輯思維，也就是用計算機求解問題的基本過程。

　　編程的第一步需要理解問題本身，提煉齣數據邏輯結構和相關運算；然後實現數據的機內錶示，也就是數據的存儲結構設計，好的存儲結構設計會達到事半功倍的效果；最後在存儲結構上實現數據的運算，即算法實現。

　　常用的數據結構有綫性錶、棧、隊列、串、樹、二叉樹和圖等，除瞭圍繞這些數據結構的基本運算算法設計外，還包含查找和排序算法設計。

　　在麵試筆試中數據結構的考點主要包含兩個方麵：一是常用數據結構的基本知識點，包括各種數據結構的邏輯特點、存儲方式和運算算法，如一個城市圖的存儲、在城市圖中查找兩個城市之間的最短路徑等；二是常用數據結構的應用知識點，能夠熟練地利用數據結構解決問題，如用棧或者隊列求解迷宮問題，用棧求解皇後問題等。

　　很多數據結構都是遞歸數據結構，遞歸也是求解問題的基本方法，所以麵試者必須具有遞歸算法設計能力，掌握從遞歸模型、遞歸算法執行過程到遞歸算法設計的一般方法，為二叉樹、圖等復雜數據結構算法設計打下堅實的基礎。

　　本書係統歸納瞭數據結構常見的知識要點，匯集國內外眾多著名IT企業近幾年的數據結構麵試筆試真題並予以解析，透徹地剖析瞭難點和疑點，每道麵試題給齣瞭難度標識，從一星到五星難度依次遞增。

　　在本書的編寫過程中參考瞭眾多網站和博客，無法一一列齣，在此編者錶示衷心感謝。

　　限於編者水平，書中難免存在遺漏，懇請讀者批評指正。

編 者

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2018年3月