<span class="bsf-rt-reading-time"><span class="bsf-rt-display-label" prefix="閱讀時間:"></span> <span class="bsf-rt-display-time" reading_time="5"></span> <span class="bsf-rt-display-postfix" postfix="mins"></span></span><!-- .bsf-rt-reading-time -->【資料結構】陣列 (Array) 是什麼?7大概念完整解析

【資料結構】陣列 (Array) 是什麼?7大概念完整解析

大家剛進入程式設計領域的時候,一定會有許多的概念都是第一次瞭解,而且都會有點模糊,不用擔心,這一系列的基礎資料結構文章會詳細介紹各種不同的資料結構,讓你能夠快速地了解這些專有名詞的概念,進而活用,接下來就跟著 Hani 的腳步,一起努力學習吧!

來吧!讓我們來介紹今天的主角 — 陣列(Array)

陣列是什麼?

Integer Array

陣列 (Array),又被稱為數組,基礎資料結構 (Data Structure) 之一

主要用來儲存一群『資料型態相同』之元素 (Elements)

直觀地來說,陣列是一個由許多數對 (pair) 所組成的集合,<索引,值>,每一個索引 (index) 會對應到一個值 (value) ,這樣的對應過程被稱為Mapping 或 Correspondence.

對於許多Programmer而言,最在乎的往往是執行層面的問題,因此陣列常會被當成是一個佔用連續記憶體位址的集合

但實際上並不全然如此,有時候也會有例外的情況發生。

如何定義一個陣列? – 以C語言為例

Data_Type Name_Of_Array[Length_Of_Array]

Data_Type : 即為資料型態,例如:int, char, float, double

Name_Of_Array : 想取的陣列名稱

Length_Of_Array : 陣列的長度,可以直接放數字,也可以放預先定義好的常數

舉例來說:

int age[10]; //說明:整數陣列age,有10個元素。
float s_id[5], n_id[20]; //說明:浮點數陣列s_id有5個元素,n_id有20個元素。
#DEFINE length_of_str 15 //說明:預先定義好的常數
char str[length_of_str]; //說明:字元陣列str,有15個元素。

初始化陣列(非常重要!!!)

陣列初始化是指在宣告陣列的時候給予陣列中的元素初始值。

為什麼需要做陣列的初始化?

  • 首先,記憶體位址是會重複使用的,如果之前使用這個位址所存的值並沒有被清除,那麼就可能會導致目前陣列所儲存的值是錯誤的。
  • 陣列初始化是在Compile階段去進行,因此是有助於提高程式效率的。

如何初始化陣列?

Data_Type Name_Of_Array[Length_Of_Array]={val,…,val}

val:即為值 (Value)

int age[5] = {25,36,48,57,68}; //確保陣列中所存的值的正確性

也可以只初始化部分的元素

int age[5] = {25,36,48}; //給予前三個元素值,而後面兩個元素則自動給予0

在C語言中,不可以直接給予陣列整體值喔!!!

例如:我們想要初始化age陣列中5個元素的值為30

int age[5] = 30; //錯誤寫法
int age[5] = {30,30,30,30,30}; //正確寫法

如何存取陣列?

在這之前,有一個非常重要的觀念!

陣列當中的第一個值,索引為0。

int age[4] = {13,24,56,76};

舉例來說:age[0] = 13, age[1] = 24, age[2] = 56, age[3] = 76

看到這裡,你一定會覺得相當地不直覺對吧?!

其實索引 (index) 內含的概念是偏移量 (offset) ,因此對於第一個元素來說,當然是沒有偏移量的,所以索引才會從0開始啦!

陣列同時支援 Sequential Access 以及 Random Access。

Sequential Access:順序存取,顧名思義也就是說要存取元素之前必須先經過所有在它之前的元素。

Random Access:隨機存取,直接透過索引來存取元素,可以任意存取特定元素。

由於陣列通常會是連續的記憶體位置,因此可以藉由索引 (index) 來計算出相對應元素的所在位址,藉以達成Random Access,也正是因為這個特性,使得陣列存取元素的時間複雜度是O(1),非常之快速!

相對於只能用Sequential Access的Single link list,時間複雜度為O(n),陣列的存取速度是它的優勢之一。

什麼時候會用到Sequential Access?

遍歷 (traverse) 陣列的時候就會需要用到Sequential Access

舉個例子:

當我們想要印出陣列當中所有的值的時候,就會去做Sequential Access

int age[5] = {10,24,32,46,58};
for (int i=0; i<5; i++) //遍歷age中所有的值,並印出
   printf("%d\n",age[i]);

陣列與字串之間的關係是?

在C語言當中,並沒有字串 (String) 的概念。

那不就糟糕了,我們怎麼宣告字串?

不要擔心,其實啊,字串就是由字元陣列所組合而成的,因此在C語言當中就是利用宣告字元陣列來儲存字串的啦。

那麼相信聰明的各位一定已經想到如何宣告字串了吧!

char site_name[20] = 'Hani CS Daily';

別急,還有一個不得不知的字串重點!

在C語言中,字串會需要一個額外的’\0’符號當作結尾,而編譯器(compiler)會根據這個符號去判斷字串是否已經結束了。

p.s. ‘\0’會算進字串長度裡面喔!

陣列在記憶體中位址的儲存方式

char site_name[14] = 'Hani CS Daily'
String

當我們宣告了一個大小為 13 的字元陣列(就是字串啦)時,等同是跟OS請求了一個 13 bytes的連續空間。

p.s. 一個char會佔 1 個 byte,int 則是 4 個 bytes。

而陣列當中的每一格都是一個記憶體位址,且為連續的。

假設 site_name[0]的位址為 0x74450

那麼 site_name[1] 為 0x74450 + 1 => 0x74451

也就是說儲存 ‘a’ 這個字元的記憶體位址就是 0x74451 ,剩餘的就是以此類推啦!

這是由一位曾經在Google工作過的工程師CS Dojo所拍攝的教學影片,如果想要看比較生動的影片講解,我非常推薦喔!

 

陣列的基本運算 – Insert、Delete、Update

剛剛在上面提到陣列可以利用隨機存取達到O(1)的存取速度,是陣列的一大優勢!

但是魚與熊掌不可兼得,若想要在陣列中做新增、刪除等動作,相對來說會變得麻煩,因為會需要去挪動其他的元素,因此時間複雜度會變成O(n),是陣列的一大劣勢!

int std_id[5] = {1,2,3,4,5};
Initial Array

若將3這個元素刪除,會發生什麼事?

把3刪除後,我們要將4、5往前挪移,因此std_id會變成下面這個樣子。

Delete element from array.

接下來新增數字6到2跟4之間

我們必須把4、5往後移,然後將6插入至指定位置

Insert element to array.

新增前必須注意的事情!

一定要記得注意陣列的長度大小,如果新增完之後超出陣列的大小,就會導致索引值超出範圍的錯誤(index out of bounds)。

該怎麼更新陣列當中的值?

直接assign過去即可!

std_id[3] = 7; //說明:將std_id中的第4個元素,也就是4,更新成7
Update the value in array.

總結

以上就是陣列(Array)的7大重點概念整理,分別是

  1. 陣列是什麼?
  2. 如何宣告一個陣列? – 以C語言為例
  3. 初始化陣列(非常重要!!!)
  4. 如何存取陣列?
  5. 陣列與字串之間的關係
  6. 陣列在記憶體中位址的儲存方式
  7. 陣列的基本運算 – Insert、Delete 、 Update

希望對你們理解陣列會有幫助!

如果有不小心漏看了什麼,記得上去給它學起來!

對文章有任何問題,都非常歡迎下面留言讓我知道

By Hani

This Post Has 14 Comments

  1. Charlotte

    虽说我也是做“设计”的,很多名词也好熟悉!
    但程式设计真是另一个世界啊!🤭
    感谢版主那么用心地分析!长知识了!😎

    1. Han I

      之後還會有一系列的文章,如果有需要隨時都可以回來看看喔!

  2. Alex

    很佩服程式語言好,數學好,邏輯清晰的人
    雖然這不是我在行的領域,但看了文章之後有涉獵道許多之前不懂的東西👍

    1. Han I

      每個人都有自己擅長的領域,希望你也能在自己的領域中發光發熱!
      謝謝你的回覆,讓我更有動力繼續努力!

  3. 湯湯俠

    已前覺得程式設計的內容都很無聊,看完本篇版主的介紹之後,開始稍微有點了解陣列是什麼?雖然還不是很懂,但看的出來版主用心的介紹!感謝分享~~~

    1. Han I

      謝謝你~看來是時候該來想想如何寫的更淺顯易懂一些了!

  4. ZN

    你寫的文章很淺顯易懂
    這對很多新手來說是個不錯的開始
    我是前端工程
    期待你的新文章

    zn – https://starstock.com.tw/

    1. Han I

      前端工程領域我也有涉獵一些,以後可以多多交流~

  5. Kate

    最近正在學習,謝謝你的文章,幫助我不少!期待更多分享!

    1. Han I

      沒問題,我會繼續產出更多文章!

  6. yenbaby

    哈哈 讓我想起以前寫C語言的痛苦XD
    這篇真的很實用耶
    謝謝你的分享。

    1. Han I

      哈哈哈,就是這種感覺,回味起來XDD!

  7. 蔡明軒

    天啊感覺好專業!真佩服你們學程式設計的人!雖然我看得不是很懂哈哈!但會幫你分享給身邊對程式有興趣的朋友!感謝版主分享!

    1. Han I

      謝謝你的支持,再麻煩你分享有需要的人,感恩!!

Leave a Reply