資料結構 順序表

前言：本章介紹的主要內容是順序表

1.線性表

線性表 （linear list）是n個具有相同特性的資料元素的有限序列，線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串等

線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，

2.順序表

2.1 概念及結構

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

順序表的本質就是陣列，動態增長，并且要求里面存盤的資料必須是從左往右連續的，邏輯結構與物理結構是一致的，

這里介紹下邏輯結構與物理結構的概念：

• 邏輯結構: 人為想象出來的,實際并不存在.
• 物理結構: 實際存在,可以被觀察到

2.2順序表分類

1.靜態順序表：使用定長陣列存盤，
2.動態順序表：使用動態開辟的陣列存盤，容量不受限制,支持資料插入,洗掉,修改等一系列操作，（接下來著重介紹）

3.動態順序表專案創建

3.1 定義順序表

typedef int SQDataType;

typedef struct SeqList
{
    SQDataType* data;    
    int size;      
    int capacity;  
}SLT;  

思考下為何使用typedef？

如果一開始我們就確定了結構體中的變數型別，后續在專案程序中如果需要對這個變數型別進行調整，那么所需的操作是很繁瑣的，故使用typedef，后續若是需要修改，改動typedef就足夠了，

3.2 順序表的初始化

思考這樣進行初始化可行否？

//SeqList.c
void SeqListInit(SLT ps)
{
    ps.a=NULL;
    pa.size=ps.capacity=0;
}
//test.c
int main()
{
	SLT plist = { 1 };
	SeqListInit(plist);

	return 0;
}

這種初始化方式顯然不行，大家可以回想下函式傳參的內容，函式內的ps只是plist的一份臨時拷貝,此時拷貝量的改變不會影響plist，那我們想要改變plist怎么辦？傳址！

修改后的正確初始化：

//SeqList.c
void SeqListInit(SLT* ps)
{
	assert(ps);  //加個斷言，ps不能為空指標
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

//test.c
int main()
{
	SLT plist = { 1 };
	SeqListInit(&plist);

	return 0;
}

3.3 順序表的列印

直接用for進行列印

void SeqListPrint(SLT* ps)
{
    for(int i = 0;i<ps->size;i++)
    {
        printf("%d->",ps->data[i]);
    }
    printf("\n");
}

3.4 順序表的增容

1.首先檢查是否容量已經滿了（ps->size == ps->capacity）

2.如果沒滿就無所謂，如果滿了并且ps->capacity！=0,就增加容量,增加方式是2倍增加，如果滿了并且ps->capacity=0，說明還是空容量,就增加4個空間，

void SeqListCheckCapacity(ps)
{
    if(ps->size == ps->capacity)
    {
        //如果capacity為0就給他4個空間,否則進行2倍增容.
        int newcapacity = (ps->capacity) ==  0 ? 4:(ps->capacity)*2;
        SQDataType* p =
            (SQDataType*)realloc(ps->data,sizeof(SLT)*newcapacity);
        //判斷下p是否為空
        if(p==NULL)
        {
            perror("錯誤原因:");
            return;
        }
        ps->data = p;
        ps->capacity = newcapacity;
   }
}

3.5 順序表的尾插

1.和初始化類似，需要進行傳址，

2.檢查順序表是否還有容量，

3.在最后一個位置上插入新資料

void SeqListPushBack(SLT* ps,SQDataType elem)
{
    assert(ps); 
    
    SeqListCheckCapacity(ps);//檢查容量是否足夠，不夠就增容
    ps->data[ps->size] = elem; //尾部插入
    ps->size++;//實際容量加1
}

3.6 順序表的頭插

1.和初始化類似，需要進行傳址，

2.檢查順序表是否還有容量，

3.挪動資料,給第一個位置空出來，在空出來的位置上插入新資料

void SeqListPushFront(SLT* ps,SQDataType elem)
{
	assert(ps);    
    SeqListCheckCapacity(ps);//檢測是否還有空間
    
    for(int i= ps->size;i>0;i--)
    {
        ps->data[i] = ps->data[i-1];
    }
    
    ps->data[0] = elem;
    ps->size++;
}

3.7 順序表的尾刪

很簡單，直接讓ps->size-1即可，

void SeqListPopBack(SLT* ps)
{
    assert(ps->size > 0); //必須保證有資料可以洗掉
    ps->size--;
}

3.8 順序表的頭刪

直接挨個把資料向前挪進行覆寫,然后ps->size-1

void SeqListPopFront(SLT* ps)
{
    assert(ps->size > 0);
    
	for(int i= 0;i<ps->size-1;i++)
    {
        ps->data[i] = ps->data[i+1];
    }
    ps->size--;
}

3.9 順序表的查找操作

1.給一個元素,查找是否在順序表內,如果在,回傳下標.

2.如果不在,回傳-1

int SeqListFind(SLT* ps,SQDataType elem)
{
    assert(ps->size > 0);
    assert(ps);
    for(int i= 0;i<ps->size;i++)
    {
        if(ps->data[i] == elem)
            return i;
    }
    return -1;
}

3.10 順序表的插入操作

函式包含：指定插入下標,和想插入的元素

實作方法: 輸入的下標位置及其后,所有資料都往后面挪，然后插入資料,ps->size+1

void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
    assert(ps);
    assert(ps->size >= index); //被插入的位置必須小于等于size

	SeqListCheckCapacity(ps); 
	
    for(int i = ps->size;i>index;i--)
    {
        ps->a[i] = ps->a[i-1];
    }
    ps->a[index] = elem;
    ps->size++;
}

3.11 順序表的洗掉操作

函式包含：指定被洗掉元素的下標

實作方法: 直接覆寫被洗掉元素,并挨個往前覆寫，然后ps->size+1

void SeqListErease(SLT* ps,size_t index)
{
    assert(ps->size > 0);//必須有元素可以洗掉
    
    for(int i = index;i< ps->size-1;i++)
    {
        ps->data[i] = ps->data[i+1];
    }
    ps->size--;
}

3.12 順序表的元素數量查看操作

size_t SeqListSize(SLT* ps) 
{
	assert(ps);
	return ps->size;
}

3.13 順序表某個元素的修改操作

void SeqListAt(SLT* ps, size_t index, SQDataType elem)
{
	assert(ps);
	assert(index < ps->size);
	ps->a[index] = elem;
}

3.14 順序表的銷毀操作

void SeqListDestroy(SLT* ps)
{
    assert(ps);
    if(ps->data != NULL)
    {
        free(ps->data);
        ps->data = NULL;        
    }
    ps->size = ps->capacity = 0;
}

4.原始碼鏈接

https://gitee.com/linkylo/c_code_2021/tree/master/c_code_2021_8_11

資料結構的順序表內容到此設計結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我三連（點贊、收藏、關注）——做個手有余香的人，