2019獨角獸企業重金招聘Python工程師標準>>>

引言

我想通過這個教程，使得讀者不需要寫太多代碼，便能理解數據結構的概念和重要性。

很多算法是運行在特殊的數據結構之上的，可以說數據結構和算法是相輔相成的，有句出自某書的非常經典的話是這樣說的：

Algorithms Plus Data Structures Equals Programs

即算法加數據結構等于程序。注意這里是程序，不是軟件。軟件還有工程性在其中。

但是我依然希望能夠不講太多的算法，因為“算法”太多，通過學習大量算法來學習數據結構的方式有些舍本逐末。

我會盡量從構造和設計的角度來闡述數據結構。

構造即我們手上有什么，怎么利用這些去制造我們需要的結構。

設計即我們的目的是什么，為了達成這個目的我們需要什么結構。

在內存里存儲數據

在C語言中，我們要處理的數據，都存儲在內存中，即便是硬盤中某個文件里存放的小說，要對其內容進行處理，我們依然需要將其加載到內存中，再接著進行后續的處理。

當我們在C語言里定義一個變量，諸如：

int?o;

在這句代碼之后，我們便可以操作這個變量。

我們可以往里面存放一個整數，那這個整數有多大呢？使用

printf("%d",sizeof(int));

這句代碼，可以輸出int型變量在其運行設備上的大小。如果你在你的筆記本電腦上編譯運行，這個大小應該是4，即4bytes，換算成二進制位(bit)即4*8=32bits。

我們可以利用sizeof測出所有基本類型的大小。這樣就有很多不同的盒子去放數據了。

內存里的數據看起來怎么樣

上面我們創建了一個int型變量o。在內存里看起來是這樣的：

當然現在什么都沒有，因為在定義的時候并未初始化，我們也沒放任何東西進去。現在存點東西進去：

o?=?11;

這下變成這樣了：

最后我們顯示出這個數據存儲單元在內存中的位置（變量地址）：

printf("%d",&o);

現在我們什么都有了：

移動數據

先看看這樣一個程序：

#include?<stdio.h> void?showcopies(int?copies) {printf("copies?%d\n",&copies); } int?main(void) {int?o;o?=?11;printf("original?%d\n",&o);showcopies(o);return?0; }

在這個程序里我們定義了一個函數，并且利用參數傳遞，將變量o“移動”到了showcopies這個函數中，并且“改名”叫做copies。

主函數main里輸出了o這個變量的地址，showcopies里輸出了移動后的o的地址。

最后的結果是什么樣呢？可以試著運行看看。

我去泡杯咖啡喝……

如果你在程序里加入了輸出變量o和變量copies的值的語句，你會更加肯定，被“移動”的只有變量o的值而已。

也就是說，當我們進行參數傳遞的時候，其實是在新的一塊內存區域里開辟一個同樣大小的空間，然后把作為參數傳遞的變量的內存空間里的數據復制到新的空間中。

一組數據

數組（Array）這個名字其實有些呆，因為光看中文名給人的感覺就是一組數，諸如(1,2,3)這樣的，但事實上還可以是('a','b','c')。我傾向于把Array理解為一列數據或者一組數據。

#include?<stdio.h> int?main(void) {int?m[3];int?i;for(i=0;i<3;i++)?printf("%d\n",&m[i]);return?0; }

運行上面的程序，就可以看到（圖畫的我累，所以這里不畫了=。=）這樣的結果：

2686736

2686740

2686744

這三個地址便是數組m里三個依次相鄰元素的地址。因為每個int變量占據4bytes，所以這三個int變量的地址是依次相差4（bytes）。數據里的數據，在內存里是連續存放的。

這樣的好處在于訪問會特別快，我們只需要知道第一個變量的地址，就能通過向后移動一定的位置來讀取另一個變量。

正如我們在程序里使用的訪問方式一樣，[]括號里加入索引號，便能訪問，在實際的程序運行中，這種直接訪問的速度也非常快。

移動一組數據或自定義數據類型

當我們嘗試在函數調用的時候傳遞數組（Array）或者自定義的數據類型（結構體）時，會出現一種例外。

因為這兩類數據在內存里占用的空間可能會很大，所以全部復制到一個新空間里實在不是很劃算的一件事。甚至多數時候我們不需要一個新的備份，只需要在原來的數據上修改就行。

所以對于這兩類數據，C語言里使用指針（Pointer）來操作。

int?m[3]; int?*first_element_address; first_element_address?=?&m[0];

printf("%d\n",*(first_element_address+1)==m[1]);

當調用函數時，會生成傳遞參數的指針變量，再將這個指針變量傳遞過去。

至于驗證方法，可以利用移動數據一段中的程序來檢驗。作業1。

/*?Cheatsheet?for?using?pointer?in?C?*/ /*?生成指針?*/ pointer?=?&variable;? /*?用指針讀取指向變量的值，再與指向變量的值進行相等判斷?*/ *pointer?==?variable;? /*?當pointer指向一塊連續數據區域時，例如數組?*/ *(pointer+index)?==?array[index];

來，我們來實現一個可變數組

先看看C語言的數組，有兩個明細的缺陷：

如果訪問數組的時候下標（索引值）越界，會發生錯誤。

數組的大小是固定的。

因此我們要設計一個用起來更好的，比如擁有如下特性：

可以檢查是否越界

可變大小

數組的數據在內存中皆是連續存放的，因此我們需要一個用于存放連續數據的區域。

作業2

---

參考

http://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs

《Linux C編程一站式學習》?宋勁杉

轉載于:https://my.oschina.net/sooshian/blog/221101

總結

以上是生活随笔為你收集整理的写给你的数据结构教程（第一天）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。