上一節學習了線性表的邏輯結構，線性表需要實現哪些基本運算/操作？在本節中，我們將學習順序表的定義、順序表的特性，以及如何用代碼來實現順序表。下個小節我們會介紹基于順序存儲（這種存儲結構）如何用代碼具體的實現之前定義的一系列基本操作。

從邏輯上看，線性表的各個元素構成一個有順序的序列。
數據元素之間存在先后順序關系，這種邏輯結構是從我們人類的視角來理解所看到的一些特性。
計算機如何表示數據元素間的邏輯關系？
我將分別介紹兩種線性表的實現方式：
采用順序存儲結構來實現線性表
采用鏈式存儲結構來實現線性表。
順序表的定義：
順序表——用順序存儲的方式實現線性表。
順序存儲——把邏輯上相鄰的數據元素存儲在物理上也相鄰的存儲單元中（緒論中提過），如圖。


這些數據元素之間的前后關系，通過物理內存上的連接關系來體現。
后面作者會在2025.5.25 00:00前整理出筆記和思維導圖大家放心，主頁還有其他文章歡迎參考 收藏文章 關注博主 高效學習

線性表當中的各個數據元素（上一小節強調過）的數據類型相同，即每個數據元素所占的內存空間一樣大。
所以如果順序表的第一個數據元素。
它的存放地址是這個地址的話，那么由于順序表當中各個數據元素，它們在。物理內存上是連續存放的，并且每個數據元素。
它們所占的空間大小都是相等的，因此它的第二個數據元素。所存放的位置就應該是這個順序表的起始地址，加上數據元素的大小，而第三個數據元素存放的位置就應該是它的起始地址。
加上二乘以數據元素的大小。以此類推。那我們怎么才能知道一個數據元素的大小到底是多少呢？C語言當中提供了一個很方便使用的關鍵字，叫size off size off打個小括號。
然后里邊傳入。你的順序表當中存放的這個數據元素的數據類型，比如如果你的順序表當中存放的是一個一個的整數，那么只要你用size off里邊。填入int就可以得到一個int型的整數。
在這個系統當中，它占多大的內存空間？那在C語言當中，很多情況下，一個int型的變量。
它是占四個字節。當然，你的順序表當中還可以存放呃，其他更復雜的數據，比如說可以存放結構類型的數據。
像這個地方，我們定義了一個叫custom的結構，里邊存了兩個整數，分別是num和people，那么兩個整數。
每個整數占四個字節，所以customer這種數據類型。它占的內存空間大小就應該是八個字節，當然你并不需要關心它的這個八個字節是怎么來的，你只需要使用C語言給你提供的。
這個很方便的size off關鍵字。啊，就可以了。所以如果知道了順序表的起始存放位置，也就是它的第一個數據元素的存放地址。
那么后面這些數據元素的存放地址是不是就可以很方便的用size off？這個關鍵字馬上就可以得到，馬上就可以算出來。好的，那接下來看順序表的第一種實現方式叫做靜態分配啊。
所謂靜態分配就是指使用這種大家最熟悉的數組的這種定義方式。來實現一個順序表，當然這是一個靜態的數組，也就是說這個數組的長度大小，一旦確定了之后。
它就不可以改變這是靜態數組的特點。我們的順序表用這樣的數據類型來表示，里邊定義了一個靜態數組，長度為max size啊，這是我們宏定義的一個常量。
另外，還定義了一個叫lens的變量，用于表示當前這個順序表，它的實際長度到底是多少，那么access的值決定了順序表。
它最多可以存放幾個數據元素。而lens的值表示的是當前這個順序表當中已經存入了多少個元素，如果從內存的視角來看的話，當你聲明了一個data數組的時候。那么。
其實就是在內存當中開辟了一整片的連續空間，這一整片的連續空間總共可以存放十個數據元素。我們這兒的代碼當中，數據元素的類型用呃I lin tap來表示il im其實就是ilmant就是元素的縮寫。數據元素的類型可以是int型。
可以是你自己定義的某一些更復雜的struct類型，這個具體要看你要用你的順序表來存什么？那這個地方我們用element type來表示，只是為了讓它更具有通用性，大家如果自己寫代碼實現的話。
那么你的數據元素類型呃，它具體是什么類型？你把這個element type。給替換掉就可以了。那我們把順序表起名為sq list。
這兒的SQ指的是sequence，所以這兒的SQ其實也是一個縮寫。好的，那么接下來來看一段具體的代碼在這兒，我們定義了一個順序表。
這個順序表是用于存放整數的，也就是說數據元素的數據類型是int。那在這兒我們定義了一個叫做data的數組，靜態的數組用于存放這些數據元素，最多只能存十個。
那定義了這樣的一個數據結構之后，我們在main行數里首先聲明，一個sq list也就是聲明，一個順序表。那么。
在執行這句代碼的時候，其實計算機就會在內存當中給這個順序表分配，它所需要的空間。首先是存放data數組的一整片的連續空間，那這片空間的大小就應該是十乘以每一個數據元素的呃大小。
那像這個地方，由于我們的數據元素是int型，所以每個數據元素的大小就應該是四個字節，也就是這個是四個字節，這一片是四個字節。
好以此類推。那除了data之外，也需要分配一個呃存放lens這個變量的空間，這個也是四個字節，因為它也是int型的。
好，那接下來在這個地方，我們實現了一個in it list這樣的一個函數，對這個順序表進行初始化，其實這個函數就是我們上。
上一小節當中提到的基本運算的第一個好，那既然main函數調用了in it list，所以接下來就會開始執行這個函數里邊的代碼。首先是一個for循環。這個for循環做的事情是把data這個數組當中所有的這些數據元素的啊值都置為零。
也就是給各個數據元素設置一個默認的初始值，當然這個設置默認初始值的步驟其實是可以省略的，這個我們一會兒再來解釋好，那除此之外還需要把lens的值置為零。因為剛開始順序表當中沒有存入任何一個數據元素。
所以此時順序表的當前長度應該是零。那這就是對順序表的一個初始化工作好，那接下來要探討的問題是，如果不給這個data數組設置一個默認的初始值的話。會發生什么情況？
我們把這個部分的代碼給去掉，也就是說在對一個順序表進行初始化的時候，只是設置了它的lens變量的值。那我們在main函數里添加了一個for循環，把data這個數組全部給打印出來。
那打印的結果是這樣的。可以看到data這個數組前面這些數據元素啊，它都是零，這很正常對吧？但是最后這兩個數據元素看一下是兩個很奇怪的值。
如果大家在自己的電腦上實現這段代碼的話，那么大家的電腦上打印出來的呃data這個數組當中各個元素的值跟我的還會不一樣？那產生這種奇怪現象的原因是內存當中會有遺留的臟數據，也就說當我們在聲明這個順序表的時候，雖然系統在背后給我們分配了這么一大片的內存空間。
但是這一片內存空間之前存的是什么數據？其實我們并不知道，所以如果我們不給這些呃數據元素設置默認值的話，那么呃會因為之前一個。遺留下來的臟數據。
而導致我們的這個數組當中出現一些奇怪的數據。不過，剛才我們說過，給這個數據元素設置默認值這一步，其實是可省略的。
原因在于我們在這個main行數里打印順序表當中的內容，這個操作其實是違規的，我們就不應該按照這樣的方式來訪問順序表。因為順序表當中不是定義了一個變量叫lens嘛。lens表示的是它當前的長度。
所以當我們在訪問順序表當中的各個數據元素的時候。不應該從第一個元素訪問到最后一個元素，而應該是訪問到順序表當中。當前實際已經存儲的啊，最后的一個元素。
那由于剛開始lens的值是零，所以如果用這種稍微正規一些的寫法的話，那么這個for循環當中的語句是不會被執行的。所以為什么說我們可以省略呃，給各個數據元素設置默認值這一步。
那是因為如果按正常的訪問方式的話，那么我們其實并不應該訪問。啊大于順序表實際長度的那些數據元素，當然了，其實更好的做法應該是使用基本操作來訪問各個數據元素。
大家可以回顧一下，上個小節我們提到過呃，我們應該實現一個基本操作，叫get all這個基本操作實現的事情是把l這個線性表當中的第二個元素給取出來。所以其實使用基本操作來訪問是最好的一種方式。
那這個地方想讓大家重點體會的是這個臟數據是怎么回事？那既然內存當中會有臟數據，所以當我們聲明這個變量的時候的初始值把它設為零，這一步是不是就肯定不能省略？因為你無法預知在這小片的呃內存區域內之前存放的到底是什么數據。
那有的同學可能會說哎C語言不是會自動給int型的變量設置一個默認初始值為零嗎？那其實這個默認初始值設置為多少？這是編譯器做的事情，如果換一個C語言的編譯器，也許它就不會幫你做這種初始化的工作。
所以當我們在聲明一個順序表的時候，剛開始把它的length值設為零，這一步是必須做的好的，那么通過剛才的代碼相信大家對順序表的靜態分配，這種實現方式。
已經有了更深入的理解，那這種實現方式的精髓在這個地方就是要定義一個靜態的數組來存放你的數據元素，那接下來要思考的問題是，如果你聲明的你剛開始聲明的這個數組的長度。不夠了。
它存滿了怎么辦？那遇到這種情況的話，給大家一個建議就是可以直接放棄治療，因為這種靜態數組的長度，只要你剛開始聲明了。
那之后它的容量就不可以再改變。也就是說給這個順序表分配的存儲空間是不可變的，是靜態的，那有的同學可能會說，那既然這樣的話。
你剛開始就申請一大片連續的。存儲空間把這個數組的長度設大一點不就行了嗎？那如果采用這種方式的話，存在的問題就是很浪費。你想假如你的這些數組。
你設置了一萬的長度，但是最后你只用了十個，那那這樣豈不是很浪費內存資源嗎？所以這種方式是不太機智的。那從這個地方。
大家就應該能夠體會到靜態分配這種實現方式，它存在一定的局限性，主要就是這個順序表的大小容量，它是不可調的。無法更改。
那如果要讓順序表的大小可變的話，那我們可以采用動態分配的，這種實現方式。如果采用動態分配來實現順序表的話，那么我們需要定義一個指針。
這個指針是指向了順序表當中的第一個數據元素。另外，由于動態分配方式當中順序表的容量大小是可以變的，所以我們需要在這兒增加一個變量，叫max size。
表示順序表的最大容量是多少？那除了最大容量之外，當然也需要用lens這個變量來記錄順序表的當前長度。也就是說，此時順序表當中實際上已經存放了多少個數據元素。
C語言當中提供了my lock和free這兩個函數來分別實現動態的申請，一片內存空間和釋放一片內存空間。這兩個函數是十分重要的好，那具體來看一下MA lock函數的原理MA lock這個函數，它所實現的事情是會申請一整片的啊。
連續的內存空間。那這一整片的內存空間，它肯定有一個起始的內存地址，所以MA lock函數執行結束之后，它會return會返回一個指向這一整片存儲空間。
開始地址的這個指針，那由于這一片存儲空間是用于存放我們一個一個的數據元素的，所以在這個地方我們需要把MA lock函數返回的這個指針，把它強制轉換成。你所定義的這個數據元素的數據類型所對應的指針。
比如如果你的順序表是用于存放整數的，也就是說數據元素是int類型，那么當你在使用melloc函數的時候呃，就需要把這個il im type把它換成int。那MA lock函數返回的這個內存的起始地址的這個指針。
我們需要把它賦給順序表當中的data，這個指針變量。也就是說data這個指針是指向了這一整片存儲空間的起始地址，那第二個需要注意的點，既然MA loc函數是申請一整片的連續存儲空間。
那么你到底要申請多大的空間呢？這就這個是由m數的這個參數所指明的，看一下左邊這個size of element type。之前我們講過這個部分的式子，得到的結果就是你的一個數據元素。
它所占存儲空間的大小，如果你的數據元素是int類型，那么它所占的大小就應該是四個字節。然后第二個部分，它要乘以in it size in it size。
指的是這個順序表，它剛開始初始的長度，那在這兒我們把它呃定義為一個常量是十。所以這一整個式子計算得到的結果就應該是存放十個，你的int型變量。
所需要的存儲空間大小，那這就是me loc函數，那如果學過C加加的同學啊，可以用new和delete這兩個關鍵字來實現類似于。和free的功能當然new和delay涉及到面向對象相關的一些知識點。
而我們為了照顧到更多的跨考的同學，所以我們在之后的學習當中會更多的使用和free這兩個函數。好的，那接下來還是用一個具體的代碼來看一下這個順序表的動態分配，在背后發生了一些什么事情。
我們在這兒定義了一個順序表，這個順序表的數據元素類型是int類型。那data這個指針指向了順序表當中的第一個數據元素，然后我們實現了一個函數in it list，用于初始化一個動態分配方式實現的順序表。
然后再實現一個函數用于動態的增加，這個順序表的長度，然后我們在main函數里調用這些相關的操作，一會兒我們來分析一下背后的過程，那需要注意的是。
in it list，這里邊使用到了malloc函數，然后增加動態數組的長度，或者說增加順序表長度，這個函數里邊又使用到了malloc和free這兩個函數。
malloc和free包含在了這個頭文件當中，所以如果大家自己寫代碼，需要使用到malloc和free這兩個函數的話，需要include這個頭文件。好。
那接下來來分析一下這段代碼運行的過程，首先在main函數里聲明一個順序表執行完這句代碼之后，其實計算機會在內存當中開辟這樣的一小片空間。這片存儲空間存放了呃，這個順序表當中的這幾個變量max size表示的是順序表的最大容量。
然后lens表示的是當前這個順序表當中有幾個數據元素，而data它是一個指針類型的變量。好，那接下來會開始執行我們定義的這個基本操作，也就是初始化順序表在這個函數的第一句會調用malloc函數。
malloc函數會申請一整篇連續的存儲空間。這片存儲空間的大小應該是能夠存得下十個int類型數據的啊，這樣的一個大小接下來malloc函數會返回一個指針，我們把這個指針的類型把它。轉換成和這兒相統一的呃指針類型。
然后把my lock返回的這些指針的值，把它賦給data。那之前我們說過my lock返回的是這一整片連續存儲空間的起始地址，所以在執行完這句代碼之后data這個指針應該是指向了這個位置。再次強調。
需要把me lock返回的指針把它轉換成我們這定義的同類型的指針好，那除了data之外，我們還需要把呃順序表的當前長度length把它設為零。然后把順序表的最大容量把它設置為這個初始值。和這個地方保持一致。
好，那接下來我們省略了一些代碼，可以往這個順序表當中插入數據，把它都給填滿，那此時lens的值就應該是。
10 max size的值也應該是十再往后，如果還想存入一些數據的話，這個順序表的大小是不是就不夠了？所以在這個地方，我們實現了一個函數。
動態的增加，這個數組的長度或者說增加這個順序表的長度，那這有個參數line。這個參數表示的是我需要拓展啊，多少的長度。
那我們這傳入五也就說想要讓這個順序表可以再多存五個數據元素。好，那第一句我們定義了一個指針p把順序表的data指針的值賦給這個p，也就是說這個p指針和data是指向了同一個位置。接下來要調用mo loc函數mo loc函數所做的事情是申請一整片的內存空間。
這片空間的大小應該能夠存得下當前的所有的這些數據元素。同時還可以再多存五個啊，新的數據元素，當然這還需要乘以每一個數據元素的大小size of element type。也就是需要使用size off這個關鍵字。
這樣的話就意味著這開辟了一片新的空間，這片空間可以存15個元素。以前只能存十個，現在可以多存五個好，那由于它申請的內存空間是另一片內存空間。
而這片內存空間此時啊，并沒有往里邊存任何數據。接下來，我們讓data這個指針指向新的這一片空間，然后再用一個for循環。
把以前這一片內存空間的這些數據把它給挪過來。然后由于順序表的最大容量增加了這么多，所以我們需要把max size的值把它加五，也就是變成了15。最后要做的一件事情是調用free函數。
free函數會把p這個指針所指向的這一整片的啊，存儲空間給釋放掉。把它歸還給系統，那由于p這個變量，它是一個局部于這個函數的變量。
所以當這個函數執行結束之后。存儲p這個變量的這些內存空間會被系統自動的回收，所以這就用my lock實現了一個呃動態數組的擴展，或者說順序表的擴展。那由于我們需要把數據復制到這個新的區域因此雖然動態分配這種方式可以讓順序表的啊。
大小能夠靈活的改變，但是其實時間開銷還是很大的。另外C語言基礎好的同學可能知道一個叫做re loc的函數，這個函數其實也可以實現，這邊我們所提到的這一系列的過程和功能。
但是re loc這個函數，其實它調用的過程當中會有一些意想不到的坑，所以我建議大家最好還是自己使用。和free這一對函數，并且用這兩個函數更能理解我們這個動態。
分配它背后所發生的這些過程。好的，那么我們介紹了順序表的兩種實現方式，第一種是靜態分配，第二種是動態分配。
那不管是用哪種方式實現順序表都具有這樣的一些特性。第一，叫隨機訪問，也就說可以在常數級的時間復雜度內就可以找到第二個元素。原因就在于順序表當中各個數據元素的存放位置是連續存放的。
因此只需要知道第一個數據元素的存放地址，那么后面這些數據元素的存放地址就可以馬上算出來。所以可以在常數集的時間內找到第二個元素，那對應我們的代碼，其實就是我們用數組。
然后給一個數組下標。就可以直接找到第二個元素，當然其實系統在背后還做了計算地址等等，這一系列的操作。那順序表的第二個特點是存儲密度高。
每個存儲節點只存儲數據元素本身，但如果我們采用鏈式存儲的話，除了存儲數據元素本身之外，還需要耗費一定的存儲空間來存放指針，這樣的信息。
所以這是存儲密度高的意思。第三個特點是拓展容量不方便靜態分配，這種方式直接就是不可以拓展容量。而動態分配這種方式，雖然可以拓展容量。
但是由于我們需要把數據給復制到新的區域，所以其實時間復雜度也比較高。第四個特點是插入刪除操作不方便，需要移動大量的元素。那這個特性。
我們會在下個小節當中結合具體的代碼，讓大家有更直觀的體會好的，那這個小節我們介紹了順序表的定義。所謂順序表，其實就是用順序存儲的方式實現的線性表。
順序存儲的存儲結構就決定了啊，邏輯上相鄰的數據元素在物理上也相鄰。那我們介紹順序表的兩種實現方式，分別是靜態分配和動態分配。靜態分配的代碼很好寫的。
就是定義一個大家很熟悉的數組，而動態分配里邊，我們需要使用到m lock和free這兩個函數。mo loc函數可以申請一整片的呃內存空間，如果當前順序表的容量不夠的話。
那么我們可以用mo loc再申請一片更大的存儲空間。然后把數據元素復制到這個新的區域，并且用free函數釋放掉原來的這個內存區域，把它歸還給系統。這個函數在考研當中是十分重要的。
大家一定要自己動手寫一寫，熟悉它的用法，最后我們介紹順序表的幾個特點，最重要的特點是這個。隨機訪問的特點可以在o1的時間復雜度內找到第二個元素。
這個美好的特性就是由于啊，數據元素在內存當中連續存放而導致的。下一個小節當中，我們會介紹呃，怎么實現順序表的插入和刪除這兩個基本操作。
到時候大家會更直觀的體會到什么叫插入和刪除數據不方便。好的，那以上就是這個小節的全部內容。