C/C++與數據結構(第5版)（簡體書）

本書共26章。第1-9章是C語言部分，從物件和運算子概念開始，通過程式比較序列，不斷擴展到函數，指標和陣列，順序表；然後與順序表類比，展開字串、檔和鏈表等。第10-17章是C++語言部分，通過對稱變換，實現了順序表、字串、鏈表和檔從初級到高級再到標準化的發展，包括順序表類、String類、Date類和物件導向設計、向量類範本、鏈表類範本、C++流與檔等。第18-26章是資料結構非線性部分，包括二叉樹、堆、二又搜尋樹、平衡二又搜尋樹、樹、圖、B樹、散列、性能分析和排序。

王立柱，天津師範大學教授，湖北工業大學特聘教授，教育部-微軟精品課主持人，國j級十一五規劃教材主編，先後獲天津市教學成果二等獎，湖北省教學成果一等獎。

第1章對象和運算符1



1.1第一個C語言程序1



1.1.1什麼是程序1



1.1.2對象1



1.1.3表達式2



1.1.4第一個C語言程序4



1.1.5集成開發環境6



1.2循環結構7



1.2.1while語句8



1.2.2for語句11



1.3標準輸入函數12



1.4分而治之16



1.5選擇結構(ifelse語句)17



1.6關係運算和邏輯運算19



1.7條件表達式和複合賦值表達式20



1.8輸入驗證21



1.8.1break和continue語句22



1.8.2前哨24



練習26



第2章函數30



2.1函數的定義和調用30



2.2函數聲明35



2.3自設頭文件36



2.4應用函數設計舉例38



2.4.1階乘38



2.4.2質數41



2.4.3最大公約數43



2.4.4斐波那契數列44



2.4.5π的近似值46



2.5函數和對象的存儲類別48



2.5.1局部對象49



2.5.2靜態局部對象49



2.5.3外部對象50



2.5.4寄存器對象50



2.5.5動態對象51



練習51



C/C++與數據結構(第5版)目錄第3章指針和數組52



3.1指針和地址傳遞52



3.1.1地址和指針52



3.1.2兩種參數傳遞54



3.1.3對象值交換57



3.2數組和線性表60



3.3指針和數組的關係63



3.3.1指針和數組的統一63



3.3.2數組求和66



3.3.3數組逆置68



3.4const限定符71



3.5數組應用75



3.5.1最大元素75



3.5.2選擇排序78



3.5.3順序搜索和二分搜索81



3.5.4平均值84



3.6類型轉換85



3.7動態數組86



3.7.1內存分配函數86



3.7.2最近平均值89



3.8指針與索引91



3.9函數指針93



練習94



第4章順序表98



4.1數組求和分析98



4.2動態數組應用100



4.3結構初步101



4.4typedef名字103



4.5准構造和准析構105



4.6尾插108



4.7讀取110



4.8刪除113



4.9基本函數補充115



4.10參數合法性檢驗116



4.11順序表的意義和局限性117



4.12順序表頭文件119



練習121



第5章結構、聯合、枚舉123



5.1結構123



5.1.1結構與對象123



5.1.2結構Date126



5.1.3結構與數組129



5.2聯合131



5.3枚舉常量和switchcase語句134



練習139



第6章字符串141



6.1字符型141



6.2字符串特點144



6.3字符串基本操作147



6.3.1字符串輸入輸出147



6.3.2字符串求長148



6.3.3字符串複製148



6.3.4字符串連接149



6.3.5字符串大小寫150



6.3.6字符串比較151



6.3.7字符查找151



6.3.8字符串匹配152



6.4自設計字符串基本操作153



6.4.1設計字符串輸入和輸出153



6.4.2設計字符串求長154



6.4.3設計字符串複製155



6.4.4設計字符串連接156



6.4.5設計字符串大小寫157



6.4.6設計字符串比較158



6.4.7設計字符查找159



6.4.8字符串頭文件161



6.5函數返回指針165



練習166



第7章文件168



7.1文件指針168



7.2文件打開與關閉168



7.3文件的讀寫171



7.3.1字符的讀寫171



7.3.2字符串的讀寫174



7.3.3格式讀寫175



7.3.4無格式讀寫177



練習181



第8章鏈表183



8.1鏈表設計183



8.1.1鏈表結點183



8.1.2鏈表雛形186



8.1.3鏈表邊界讀取188



8.1.4鏈表插入188



8.1.5鏈表刪除191



8.1.6鏈表頭文件193



8.2鏈表逆置194



8.3Josephus問題196



練習199



第9章二維數組和指針200



9.1二維數組200



9.1.1二維數組定義200



9.1.2二維數組初始化200



9.1.3二維數組和指針202



9.2二維數組和一維數組205



9.2.1二維數組作為一維數組205



9.2.2馬鞍點206



9.2.3一維數組作為二維數組208



9.3指針數組和二級指針209



9.4二級指針和二維數組210



練習212



第10章C++語言初步215



10.1對象和結構對象的定義215



10.2提取符和插入符216



10.3運算符重載217



10.4函數重載219



10.5引用220



10.5.1引用概念的由來220



10.5.2引用聲明225



10.5.3引用傳遞和返回引用225



10.6默認參數和默認函數228



練習229



第11章順序表類230



11.1順序表類230



11.1.1從C順序表到C++順序表類變換232



11.1.2複製賦值和複製構造238



11.1.3修飾詞explicit和初始化表241



11.1.4默認構造函數與零元242



11.1.5索引運算符重載243



11.1.6順序表類頭文件245



11.2函數模板247



11.3類模板248



11.4函數模板實例化中的問題252



練習253



第12章String類254



12.1String類雛形254



12.2連接258



12.3插入261



12.4刪除263



12.5取子串265



12.6比較267



12.7索引運算符重載268



12.8查找269



12.9String類頭文件272



練習276



第13章Date類和面向對象設計277



13.1Date類277



13.1.1雛形277



13.1.2轉換賦值278



13.1.3成員轉換278



13.1.4提取符和插入符重載279



13.1.5自增自減280



13.1.6取值和賦值282



13.2繼承282



13.3多態性和虛函數284



13.4虛析構函數286



13.5純虛函數和抽象類286



練習289



第14章向量類模板292



14.1迭代器292



14.2向量類模板293



14.3函數對象296



練習299



第15章鏈表類模板300



15.1鏈表類模板設計300



15.1.1雛形300



15.1.2迭代器301



15.1.3插入304



15.1.4刪除307



15.1.5複製賦值與複製構造310



15.1.6數據首尾元素引用313



15.1.7鏈表類頭文件314



15.2鏈表逆置318



15.3Josephus問題320



15.4適配器322



15.4.1鏈棧322



15.4.2鏈隊列323



15.4.3優先級鏈隊列325



15.5事件驅動模擬326



練習336



第16章C++流與文件337



16.1格式化輸入輸出337



16.1.1標誌字337



16.1.2格式化輸出函數338



16.1.3操作算子340



16.2文件的讀寫342



16.2.1字符讀寫函數343



16.2.2字符串讀寫函數345



16.2.3格式讀寫347



16.2.4無格式讀寫函數348



練習352



第17章命名空間353



17.1命名空間的定義353



17.2using namespace語句354



17.3命名空間的成員355



17.4命名空間的別名357



練習357



第18章二叉樹359



18.1二叉樹的基本概念359



18.2二叉樹的性質360



18.3二叉樹的存儲361



18.3.1二叉樹的順序存儲361



18.3.2二叉樹的鏈式存儲361



18.4層次遍歷362



18.4.1層次遍歷迭代算法362



18.4.2垂直輸出二叉樹364



18.4.3由順序存儲生成二叉鏈式存儲367



18.5前序遍歷368



18.5.1前序遍歷遞歸算法369



18.5.2前序遍歷迭代算法374



18.5.3快速排序376



18.6中序遍歷380



18.6.1中序遍歷遞歸算法380



18.6.2中序遍歷迭代算法386



18.6.3n階漢諾塔389



18.7後序遍歷391



18.7.1後序遍歷遞歸算法391



18.7.2後序遍歷迭代算法399



18.7.3複製二叉鏈表的遞歸算法403



18.7.4計算二叉樹高度403



18.7.5刪除二叉鏈表的遞歸算法403



18.7.6生成二叉鏈表的遞歸算法404



18.8二叉鏈表頭文件405



練習412



第19章堆415



19.1堆類415



19.1.1堆類聲明415



19.1.2堆插入416



19.1.3堆刪取419



19.1.4堆類頭文件423



19.2堆排序425



19.2.1對數組堆排序425



19.2.2堆排序頭文件428



19.3哈夫曼樹430



19.3.1哈夫曼樹定義和算法430



19.3.2哈夫曼結構431



19.3.3哈夫曼編碼432



19.3.4哈夫曼譯碼435



19.3.5哈夫曼結構頭文件437



練習440



第20章二叉搜索樹441



20.1二叉搜索鏈表類441



20.1.1類聲明441



20.1.2插入442



20.1.3刪除444



20.1.4查找和修改447



20.1.5中序迭代器452



20.1.6頻率統計455



20.2二叉搜索鏈表類頭文件457



練習463



第21章平衡二叉搜索樹464



21.1動態平衡方法464



21.1.1左單旋轉型調整464



21.1.2右單旋轉型調整466



21.1.3先右後左雙旋轉型調整467



21.1.4先左後右雙旋轉型調整469



21.2平衡二叉搜索鏈表類470



21.2.1類聲明470



21.2.2插入471



21.2.3刪除474



21.2.4查找和修改477



21.2.5中序迭代器479



21.3平衡二叉搜索鏈表類頭文件479



練習487



第22章樹489



22.1樹的基本概念和存儲489



22.2樹類的雛形491



22.3樹的廣度優先遍歷495



22.4樹的深度優先遍歷497



22.5八皇后499



22.6樹類頭文件502



練習506



第23章圖507



23.1圖的基本概念和存儲507



23.2圖類的雛形509



23.3圖的遍歷514



23.3.1廣度優先遍歷514



23.3.2深度優先遍歷516



23.4最小生成樹518



23.4.1普裡姆算法519



23.4.2克魯斯卡爾算法523



23.5最短路徑527



23.6拓撲序列533



23.7關鍵路徑537



23.8迷宮542



23.9圖類頭文件546



練習559



第24章B樹560



24.1線性索引560



24.2靜態m路搜索樹561



24.3B樹562



24.4B+樹566



練習567



第25章散列568



25.1散列表568



25.2散列函數569



25.2.1平方取中法569



25.2.2除留餘數法570



25.2.3折疊法570



25.2.4數字分析法570



25.3分離鏈接法571



25.4開放定址法574



25.4.1線性探查法574



25.4.2平方探查法575



25.4.3雙散列函數探查法575



第26章性能分析和排序576



26.1性能分析576



26.1.1時間複雜性分析576



26.1.2空間複雜性分析577



26.2插入排序578



26.2.1直接插入排序578



26.2.2折半插入排序580



26.3交換排序581



26.3.1冒泡排序581



26.3.2快速排序583



26.4選擇排序584



26.4.1直接選擇排序584



26.4.2堆排序585



練習586



附錄A命名規則587



附錄B基本類型588



B.1整型588



B.2實型589



B.3字符型590



附錄C編譯預處理592



C.1無參宏指令592



C.2帶參宏指令593



C.3條件編譯指令594



附錄D輾轉相除法求最大公約數的證明595



參考文獻596