天天看點
傳回

不會有人不會順序表吧

寫在前面

順序表是資料結構裡面最簡單的一個知識,不過它能夠充分展現出資料結構的思想,今天讓我們正式進入拉開資料結構的帷幕.讓我們一起來學習吧.

線性表

在談正式内容之前,我們先來看看什麼是線性表。

線性表（linear list）是n個具有相同特性的資料元素的有限序列. 線性表是一種在實際中廣泛使用的資料結構,常見的線性表：順序表、連結清單、棧、隊列、字元串...

這裡我想重點談談線性表,首先線性表是一個序列,不是那個升序降序的序列,就是一組數.對于存在多個資料,第一個元素找不到前驅,最後一個元素找不到後驅,其餘的都有一個前驅和一個後驅.再說一下,裡面的元素是相同資料類型的,不能存在不同的資料類型.說人話線性表就是我們可以拿一個繩子把所有相同的資料給串起來.

不會有人不會順序表吧

順序表

順序表是用一段實體位址連續的存儲單元依次存儲資料元素的線性結構,一般情況下采用數組存儲.在數組上完成資料的增删查改.它的本質就是一個數組.我們會疑惑我們既然有數組,為何還會出現順序表呢?實際上在C99之前,我們的編譯器不支援變常數組,在對資料的存儲方面有一定的不便之處,比如說我們要是空間開大了就浪費,小了不夠用這就出現了順序表.今天順序表的部落格是很簡單的,就是關于數組元素的增删查改.沒有很麼可以值德思考的地方,細心一點就可以了.順序表又分為：

  • 靜态順序表：使用定長數組存儲
  • 動态順序表：使用動态開辟的數組存儲.

靜态順序表

我們平常是不用靜态數組的,這裡我們為了知識的完整性,順便為下面的動态順序表做鋪墊.這裡我們想的是既然是順序表,這裡我們給一個結構體,裡面成員包含一個數組,既然有數組了,這裡是不是應該有一個變量存儲數組裡面有效元素的個數.這就構成了一一個簡單的順序表.

#define NUM 100      
struct StaticSeqList      
{      
  int array[NUM];      
  size_t size;      
};

靜态順序表都很大的缺點,一般它得大小在運作得時候已經确定了,也就是說在運作前我們需要估算該給這個數組多大得空間,但是有的項目資料是一直産生得,我們空間随着時間要的越來越大,如果我們要是一開始就給了很大得空間,這裡就占據了,其他程式就不能使用,很不好.是以一般我們不太提倡使用靜态順序表,除非是在它适當的地方.

動态順序表

我們這裡開始我們今天的大菜,既然靜态的有很大的缺點,那麼我們在C語言學過動态開辟記憶體,這裡我們就可以使用這個知識點.我們先來用一下.

struct SeqList 
{
  int* array;
  size_t size;     // 記錄元素的有效個數
  size_t capacity; // 記錄數組的大小
};

上面就是我們動态順序表的架構,我們可以根據自己資料擴大來動态的增長我們的空間,空間不夠了就擴容.但是我們上面的順序表還存在兩個小問題,這裡我們先來解決第一個.這裡我們存儲的是int類型的資料,如果我們要是存儲char或者其他的類型,這個就不太适用了,是以這裡我們需要這麼做.

typedef int SLDateType;
struct SeqList 
{
  SLDateType * array;
  size_t size;
  size_t capacity;
};

還有另外一個,在C語言中struct SeqList 才是我們的資料類型,這裡每一次帶上struct感覺都有點麻煩,這裡我們也修改下.

typedef int SLDateType;
typedef struct SeqList 
{
  SLDateType * array;
  size_t size;
  size_t capacity;
} SeqList;

常見接口

我們知道了順序表是什麼,這裡就來簡單的實作一下它的用法,順序表的操作莫過于增删改查,這裡函數的實作是非常簡單的,我們需要細心一點,前面如果看過我寫的通訊錄部落格,這裡了解的會更容易點.

SeqListInit()

由于我們的資料結構是由C語言寫的,我們首先要做的就是給我們的順序表進行初始化,這裡存在一個問題,我們對于初始化函數參數如何傳遞?我們先來看一下下面的代碼.

void SeqListInit(SeqList ps)                                        
{                                                                                              
  ps.array = NULL;                                                                           
  ps.capacity = 0;                                                                                   
  ps.size = 0;                                                      
}

這裡我們需要先測一下自己寫的函數對還是不對,大家在學習資料結構的時候一定要寫一個函數測一下功能,不要把所有的函數都實作了,最後測,這樣你會發現修改錯誤比你寫代碼的時間還要長.這裡VS2019檢測很嚴格,不允許使用未初始化的變量我們在Linux環境下測試,大家看不懂沒有關系,隻需看看結果就行了.

#include "SeqList.h"    
void TestInit()    
{    
    
  SeqList s;                                                                                                    
  SeqListInit(s);    
  printf("hello 資料結構");    
}    
    
int main()    
{    
  TestInit();    
  return 0;    
}
不會有人不會順序表吧

我們發現s1裡面的成員都沒有被修改,這裡的原因就和我們前面說的一樣,函數傳參會拷貝一個形參,改變形參是不會影響實參的.

void f(int b)
{
  b = 20;
}
int main()
{
  int a = 0;
  f(a);
  printf("%d", a);
  return 0;
}
不會有人不會順序表吧

是以這裡我們使用的是指針傳參,注意一點就可以了.

void SeqListInit(SeqList* ps)                                        
{                                                                    
  // 首先檢測 是否為空                                                                        
  assert(ps);                                                                                                     
                                                                                                            
  //這裡有兩個模式,一個是初始化的時候開辟點空間                                                    
  //一個不開,這裡我們選擇不開                                        
  ps->array = NULL;                                                                           
  ps->capacity = 0;                                                                                   
  ps->size = 0;                                                      
}

我們在測試一下.

void TestInit()  
{  
  
  SeqList s ;
  SeqListInit(&s);
  printf("hello 資料結構");
}
int main()
{
  TestInit();                                                                                                   
  return 0;             
}
不會有人不會順序表吧

SeqListPushBack()

我們來是實作一下尾插這個函數,這裡還是比較簡單的,不過我們在進行資料插入之前需要判斷一下這個順序表的空間是不是夠,不夠的話我們就要增容.大家看一下下面的代碼,要是不太明白realloc可以去檢視一下手冊,很簡單.

再談一下下面得擴容機制,這裡我們選擇得是2倍擴,我們是可以選擇4倍,5倍...但是這裡我們需要認識到一點,如果我們原數組有100個有效元素,我們隻是為了插入1個元素,你給我擴大了5倍,這裡不就是浪費了嗎?當然我們2倍擴容在上面的情況也是有點浪費,可以換成1.3倍,這裡看實際情況,無論我們如何選擇,盡量往浪費少的地方想就可以了.這個時候有人又會想,既然我們成倍數的擴容都會造成浪費,我們這裡插入一個擴一個空間不行嗎?那麼請問我們調用realloc函數擴容會不會降低效率 ,這裡都是需要我們考慮的. 
void SeqListPushBack(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 檢測擴容
    if (ps->size == ps->capacity)
    {
        size_t newSize = 2 * ps->capacity; // 我們先擇得是 2 倍 擴
        SLDateType* ret = realloc(ps->array, sizeof(SLDateType) * newSize);
        assert(ret);
        ps->capacity = newSize;
        ps->array = ret;
    }
    // 到這一步 空間夠了
    ps->array[ps->size++] = x;
}

在測試這個代碼之前,我們先吧列印函數簡單的寫一下,等下用來輔助驗證我們上面寫的函數對不對.注意這裡我們列印函數傳指針的原因和初始化函數是不一樣的,這裡是為了拷貝的時候消耗少一點,畢竟指針不是4位元組就是8位元組,結構體有點大.

void SeqListPrint(SeqList* ps)
{
    assert(ps);
    for (size_t i = 0; i < ps->size; i++)
    {
        printf("%d ", *(ps->array + i));
    }
    printf("\n");
}
好了,萬事俱備,這個時候我們就需要來測試一下尾插函數究竟對不對了. 
void TestPuskBack()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPrint(&s);
}
int main()
{
  TestPuskBack();
  return 0;
}
不會有人不會順序表吧

我們一看很不錯,這裡我們得到結果是正确的,那麼真的是正确的嗎?我們調試一下,這裡有些東西我們被編譯器給騙了.要知道我們初始化的時候容量給的是0,第一次插入資料肯定要擴容,這裡就是我們出現問題的地方,0乘任何數都是0,我們怎麼擴容結果還是0,這裡就申請不出空間.

不會有人不會順序表吧

有的人可能異疑惑,我們沒有申請出空間,那麼這裡也就是我們越界通路了,使用了野指針,請問程式為何還運作成功了?這裡我們要提出一個結論,編譯器對于數組越界的檢測是随機的,也就是有的時候可以檢測出來,有的時候不能.我們看一下下面的結果.

int main()
{
  int arr[10] = { 0 };
  arr[10] = 1;
  printf("%d", arr[10]);
  return 0;
}
不會有人不會順序表吧

那麼下面的越界呢?你就會發現這裡就檢測不出來,是以我們需要一再小心,這裡每一步都是坑.

int main()
{
  int arr[10] = { 0 };
  arr[11] = 1;
  printf("%d", arr[11]);
  return 0;
}
不會有人不會順序表吧

這裡我們修改一下就可以了在第一次的時候給它開4個元素的空間,注意是一定要開4個,是你覺得開幾個好就開幾個.

void SeqListPushBack(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 檢測擴容
    if (ps->size == ps->capacity)
    {
        size_t newSize = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDateType* ret = realloc(ps->array, sizeof(SLDateType) * newSize);
        assert(ret);
        ps->capacity = newSize;
        ps->array = ret;
    }
    // 到這一步 空間夠了
    ps->array[ps->size++] = x;
}

SeqListPopBack()

談完了尾插這裡就說一下尾删吧.個是非常簡單的.我們這樣想,所謂的尾删不就是不要最後一個元素嗎,而不要最後一個元素不就是讓使用者看不到它嗎,看不到它不就是讓size減掉1嗎,至于最後一個有效空間的資料存儲的是啥我們一點都不關心.這裡需要注意一下原本的順序表沒有元素的情況.

void SeqListPopBack(SeqList* ps)  
{  
  assert(ps);  
  if(ps->size == 0)  
    return;  
    
  ps->size--;                                                                                              
}

我們這裡測試一下,倒是挺簡單的.

void TestPopBack()
{
  SeqList s;
  SeqListInit(&s);

  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);

  SeqListPrint(&s);
  SeqListPopBack(&s);
  printf("===============\n");

  SeqListPrint(&s);
}

int main()
{
  TestPopBack();
  return 0;
}
不會有人不會順序表吧

SeqListPushFront()

尾部的相關操作我們已經寫完了,這裡開始頭部的相關操作.先來談頭部的插入,我們插入資料之前首先要做的就是看看自己空間是不是夠,這裡就涉及到擴容操作.那麼我們是不是還要寫擴容的判斷呢?這裡要是寫了就是代碼備援了,是以這裡我們應該把擴容操作封成一個函數,需要的時候調用就可以了.

void SeqListCheckCapacity(SeqList* ps)
{
    assert(ps);
    if (ps->capacity == ps->size)
    {
        // z注意這個判斷很重要
        size_t newSize = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        // 開辟空間 使用 realloc
        // 這個函數 會開辟拷貝
        int* ret = (int*)realloc(ps->array, sizeof(SLDateType) * newSize);
        assert(ret);
        ps->array = ret;
        ps->capacity = newSize;
    }
}

那麼前面我們寫的尾插函數就要發生點改變了,不用自己再判斷是不是要擴容了.

void SeqListPushBack(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 檢測擴容
    SeqListCheckCapacity(ps);
    // 到這一步 空間夠了
    ps->array[ps->size++] = x;
}

好了,現在我們就可以實作頭插函數具體實作了.我們先來整理一下思路,頭插就是我們把已有的元素整體往後移動一個,把下标為0的位置給空出來,最後把新元素插入進去就可以了.那麼我們看一下代碼吧.

void SeqListPushFront(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 擴容                                                                 
    SeqListCheckCapacity(ps);

    size_t pos = ps->size-1;
    while (pos >= 0)
    {
        ps->array[pos + 1] = ps->array[pos];
        --pos;
    }
    ps->array[0] = x;
    ps->size++;                                                                                             
}

注意上面的代碼存在很大的問題,我們來測試下.

void TestPushFront()
{
  SeqList s;
  SeqListInit(&s);

  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPrint(&s);
  SeqListPushFront(&s, 0);
  SeqListPrint(&s);
}

int main()
{
  TestPushFront();
  return 0;
}
不會有人不會順序表吧
下面我來簡單的分析一下,我們這裡想一想當這個順序表裡面沒有元素的時候,pos等于-1,不滿足循環條件,這裡不進入循環,按理說這裡應該是對的,那麼為何會報錯呢?這裡大家忘記了變量的類型,這裡我們用的是size_t,也就是無符号整數,一直是大于等于0的,不可能出現-1,是以這裡while循環一直運作,直到程式崩潰.至于為何要使用size_t的類型呢?這裡留到insert函數和大家解釋. 
void TestPushFront()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushFront(&s, 0);
  SeqListPrint(&s);
}

int main()
{
  TestPushFront();
  return 0;
}
不會有人不會順序表吧

既然這個方法不太行,我們有什麼解決方法嗎?這裡有兩個,一個就是強制類型轉化,這個代碼放在下面了.另外一個方法就比較容易了,我們把pos指向size,直接取前一個資料,這樣pos就不會到0了.

// pos 指向size
void SeqListPushFront(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 擴容                                                                 
    SeqListCheckCapacity(ps);
    size_t pos = ps->size;                                                                                       
    while(pos > 0)                                                                                   
    {                                                                                                       
      ps->array[pos] = ps->array[pos-1];                                                             
      --pos;                                                                                               
    }                                                                                                
    ps->array[pos] = x;                                                                              
    ps->size++;                                                                                             
}
//  強制類型轉換
void SeqListPushFront(SeqList* ps, SLDateType x)
{
    assert(ps);
    // 擴容                                                                 
    SeqListCheckCapacity(ps);

    size_t pos = ps->size-1;
    while ((int)pos >= 0)
    {
        ps->array[pos + 1] = ps->array[pos];
        --pos;
    }
    ps->array[0] = x;
    ps->size++;                                                                                             
}

這裡我們就可以簡單的驗證一下了,不用懷疑,這裡是正确的.

void TestPushFront()
{
  SeqList s;
  SeqListInit(&s);

  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPrint(&s);
  SeqListPushFront(&s, 0);
  SeqListPrint(&s);
}

int main()
{
  TestPushFront();
  return 0;
}
不會有人不會順序表吧

SeqListPopFront()

這個倒是挺簡單的,也沒有太多的坑,注意一點判斷順序表是不是為空就可以了.

void SeqListPopFront(SeqList* ps)
{
    assert(ps);
    if (ps->size == 0)
        return;
    for (size_t i = 1; i < ps->size; i++)
    {
        ps->array[i - 1] = ps->array[i];
    }
    ps->size--;
}

我們這裡要重點談一下如何測試代碼,一般而言,對于删除函數,.我喜歡删除尾部,中間,頭部各一個,這樣一般就可以覆寫大部分情況了,不過這裡是頭删,從頭删到尾就可以;了.

void TestPopFront()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  for (int i = 0; i < 4; i++)
  {
    SeqListPopFront(&s);
    SeqListPrint(&s);
  }
}

int main()
{
  TestPopFront();
  return 0;
}
不會有人不會順序表吧

SeqListInsert()

這個需要我們簡單的分析一下,我們在pos位置插入資料,這裡就要把pos和pos之後的資料往後移動,新資料插入pos位置.聽着是不是很熟悉,我們的頭擦就是如此,是以頭擦需要注意的,insert都需要注意,除此之外我們還需要注意另外的一件事時,我們需要判斷pos的合法性.順序表的資料是連續的,是以我們呢不能是以插入資料.

不會有人不會順序表吧

這裡我們就可以解釋我們為何傳參要使用size_t類型的了.由于無符号整數不會小于零,這就造成我們隻需要判斷一種情況就可以了,不過最關鍵的原因是在我們後續的C\++有一個STL,裡面儲存者我們常見的資料結構,其中vector就是我們的順序表,我們來看一下它們的函數接口也是size_t,這裡我們選擇和他一樣.

不會有人不會順序表吧

說了這麼多,我們來實作一個這個函數,注意點細節就可以了,不太難.

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
    assert(ps);
    //判斷pos的合法性   
    assert(pos <= ps->size); // 等于箱單于尾插 
    SeqListCheckCapacity(ps);   
    size_t end = ps->size;
    while (end > pos)
    {
        ps->array[end] = ps->array[end - 1];
        end--;
    }
    ps->array[pos] = x;
    ps->size++;
}

來都來了,這裡不驗證一下嗎,我們這裡驗證頭部尾部中間三大部分,

void TestInsert()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPrint(&s);
  printf("---------------\n");
  SeqListInsert(&s, 3, 4); // 尾插
  SeqListPrint(&s);

  SeqListInsert(&s, 0, 0); // 頭插
  SeqListPrint(&s);
  SeqListInsert(&s, 2, -1);// 中間插入
  SeqListPrint(&s);


}

int main()
{
  TestInsert();
  //TestPopFront();
  //TestPopBack();
  return 0;
}
不會有人不會順序表吧

這裡我們實作好了,那麼前面我們寫的尾插和頭插就可以直接複用這個函數了,不用自己實作了.

void SeqListPushBack(SeqList* ps, SLDateType x)  
{                    
  SeqListInsert(ps, ps->size, x);                                                                 
} 

void SeqListPushFront(SeqList* ps, SLDateType x)
{
  SeqListInsert(ps, 0, x);
}

SeqListErase()

這裡和前面我們的頭删一樣都是很簡單的,我們隻需要注意下細節就可以了.

void SeqListErase(SeqList* ps, size_t pos)
{
    assert(ps);
    assert(pos < ps->size); // 這裡不等 是因為數組下标越界
    if (ps->size == 0)
        return;
    for (size_t i = pos + 1; i < ps->size; i++)
    {
        ps->array[i-1] = ps->array[i];
    }
    ps->size--;
}

是不是正确我們來測一下代碼,這裡簡單的驗證一下.

void TestInsert()
{
  SeqList s;
  SeqListInit(&s);
  SeqListPushBack(&s, 1);
  SeqListPushBack(&s, 2);
  SeqListPushBack(&s, 3);
  SeqListPushBack(&s, 4);
  SeqListPrint(&s);

  SeqListErase(&s, 0);
  SeqListPrint(&s);

  SeqListErase(&s, 1);
  SeqListPrint(&s);

  SeqListErase(&s, 1);
  SeqListPrint(&s);
}
int main()
{
  TestInsert();;
  return 0;
}      
void SeqListPopFront(SeqList* ps)
{
    SeqListErase(ps, 0);
}

void SeqListPopBack(SeqList* ps)
{
    SeqListErase(ps, ps->size-1);
}

SeqListDestroy() 

void SeqListDestroy(SeqList* ps)    
{    
  assert(ps);    
  ps->capacity = 0;    
  ps->size = 0;    
  // 釋放 NULL 也不會報錯    
  // 不過最好判斷一下    
  if(ps->array)    
    free(ps->array);    
  ps->array = NULL;    
}
順序表 數組
上一篇: 計算機開機後桌面黑屏,電腦開機一直黑屏怎麼辦 電腦開機後桌面黑屏的解決方法...
下一篇: Redis資料結構(一)-Redis的資料存儲及String類型的實作

繼續閱讀