線性表

(1)邏輯結構和物理結構

物理結構：數據元素在內存中真實的存放次序，有可能是連續存放的，也可能是散落于內存里。

邏輯結構：為了便于描述數據元素之間的關系，我們想象出數據之間應該有某種的對應關系，如果是一對一就是線性結構，不是一對一那就是非線性結構。

(2)線性表

常見的線性結構就是線性表，所以說線性表在邏輯上是線性的，但是在物理上不一定是線性的。常見的線性表有順序表，鏈表，棧，隊列等。

線性表在物理上存儲時，通常以數組和鏈式的結構存儲

在這里插入圖片描述

順序表(數組)

(1)概念

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

(2)靜態順序表

頭文件內結構體的定義如下

#pragma once

typedef int SLDataType;

#define N 10

struct SeqList

{

SLDataType a[N];//定長數組

int size;//有效數據個數，也就是數組長度

};

這里一定要注意不要習慣性的定義結構體，所有的數據類型都是int型的，因為數組有時存放的不會是int數據，而是其他數據，為了結構體通用，防止日后反復修改，我們要利用typedef和#define進行前定義。

在這里插入圖片描述

可以發現靜態存儲結構，缺點還是很大的，比如說在做通訊錄這種東西的時候，大小無法準確控制，所以日常工作中基本不用靜態的這種結構

(3)動態順序表

A：頭文件內結構體的定義如下

#pragma once

typedef int SLDataType;

struct SeqList

{

SLDataType* Array;

int Size;//有效數據個數

int Capacity;//容量大小

};

動態順序表所變化的是多了一個表示容量大小的參數，因為如果一旦達到容量上限，就可以用relloc擴容，使用的是指向一片連續空間的指針

在這里插入圖片描述

B：操作

*說明

這是文件的邏輯

在這里插入圖片描述

下面是測試文件 SeqList_test.c

#include "SeqList.h"

//測試插入刪除元素

void Test1(SeqList* ps)

{

SeqListInit(ps);//初始化

SeqListPushBack(ps, 1);

SeqListPushBack(ps, 2);

SeqListPushBack(ps, 3);

SeqListPushBack(ps, 4);

SeqListPushBack(ps, 5);//尾部插入依次元素

SeqListPrint(ps);

SeqListPopBack(&s);

SeqListPopBack(&s);

SeqListPopBack(&s);//尾部依次刪除元素

SeqListPrint(&s);

SeqListPushFront(&s, 9);

SeqListPushFront(&s, 8);

SeqListPushFront(&s, 7);

SeqListPushFront(&s, 6);

SeqListPushFront(&s, 5);//頭部依次插入元素

SeqListPrint(&s);

SeqListPopFront(&s);

SeqListPopFront(&s);

SeqListPopFront(&s);//頭部依次刪除元素

SeqListPrint(&s);

SeqListInsert(&s, 1, 5);

SeqListInsert(&s, 1, 6);//向指定位置插入元素

SeqListPrint(&s);

SeqListErase(&s, 1);

SeqListErase(&s, 1);//把指定位置元素刪除

SeqListPrint(&s);

}

//測試接受用戶輸入刪除指定元素刪除

void Test2(SeqList* ps)

{

printf("請輸入要刪除的元素\n");

int res = 0;

scanf_s("%d", &res);

int index = SeqListFind(ps, res);

if (index == -1)

printf("沒有此元素");

else

{

printf("刪除后為\n");

SeqListErase(ps, index);

SeqListPrint(ps);

}

}

int main()

{

SeqList s;

Test1(&s);//測試插入刪除元素

Test2(&s);//測試用戶指定元素刪除

return 0;

}

下面是接口聲明"SeqList.h"

#pragma once

#include

#include

#include

typedef int SLDataType;

typedef struct SeqList

{

SLDataType* Array;

int Size;//有效數據個數

int Capacity;//容量大小

}SeqList;

void SeqListInit(SeqList* ps);//初始化

void SeqListDestory(SeqList* ps);//銷毀

void SeqListPrint(SeqList* ps);//屏幕輸出操作

void SeqListCheckCapacity(SeqList* ps);//檢查容量是否滿了

void SeqListPushBack(SeqList* ps, SLDataType x);//尾插(可以與任意位置插入復用)

void SeqListPopBack(SeqList* ps);//尾刪除(可以與任意位置刪除復用)

void SeqListPushFront(SeqList* ps, SLDataType x);//頭插(可以與任意位置插入復用)

void SeqListPopFront(SeqList* ps);//頭刪(可以與任意位置刪除復用)

void SeqListInsert(SeqList* ps, int pos, SLDataType x);//任意位置插入

void SeqListErase(SeqList* ps, int pos);//任意位置刪除

int SeqListFind(SeqList* ps, SLDataType x);//使用順序查找法查找某個元素的位置

int SeqListFindvalue_Bind(SeqList* ps, int pos);//使用二分查找法查找某個元素的位置

下面是接口實現"SeqList.c"

#include "SeqList.h"

void SeqListInit(SeqList* ps)//初始化

{

/*也可以這樣申請

s.Size = 0;

s.Array = NULL;

s.Capacity = 0;

*/

ps->Array = (SLDataType*)malloc(sizeof(SLDataType) * 4);

if (ps->Array == NULL)

{

printf("申請失敗\n");

exit(-1);

}

ps->Size = 0;

ps->Capacity = 4;

}

void SeqListDestory(SeqList* ps)//銷毀

{

free(ps->Array);

ps = NULL;

ps->Capacity = ps->Size = 0;

}

void SeqListPrint(SeqList* ps)//打印

{

assert(ps);

for (int i = 0; i < ps->Size; ++i)

{

printf("%d ", ps->Array[i]);

}

printf("\n");

}

void SeqListCheckCapacity(SeqList* ps)//檢查容量是否滿了

{

if (ps->Size == ps->Capacity)

{

ps->Capacity *= 2;

ps->Array = (SLDataType*)realloc(ps->Array, sizeof(SLDataType)*ps->Capacity);

if (ps->Array == NULL)//擴容失敗

{

printf("擴容失敗\n");

exit(-1);

}

}

}

void SeqListPushBack(SeqList* ps, SLDataType x)//尾插

{

/*尾插就是size位置上的插入

assert(ps);//警告，指針為空

SeqListCheckCapacity(ps);//滿了就擴容

ps->Array[ps->Size] = x;//size表示有效個數，但同時是下一個元素的下標

ps->Size++;//元素加1

*/

SeqListInsert(ps,ps->Size, x);

}

void SeqListPopBack(SeqList* ps)//尾刪除

{

assert(ps);

ps->Size--;

}

void SeqListPushFront(SeqList* ps, SLDataType x)//頭插

{

/*頭插是0位置上的插入

assert(ps);

SeqListCheckCapacity(ps);//滿了就擴容

for (int i = ps->Size-1; i >= 0; i--)//頭插法：從最后一個元素開始，依次向后移，把0的位置空出來

{

ps->Array[i+1] = ps->Array[i];

}

ps->Array[0] = x;

ps->Size++;

*/

SeqListInsert(ps, 0, x);

}

void SeqListPopFront(SeqList* ps)//頭刪

{

/*頭刪是0位置的刪除

assert(ps);

for (int i = 0; i < ps->Size; i++)

{

ps->Array[i] = ps->Array[i + 1];//刪除時直接覆蓋即可

}

ps->Size--;

*/

SeqListErase(ps, 0);

}

void SeqListInsert(SeqList* ps, int pos, SLDataType x)//任意位置插入

{

assert(ps);

assert(pos <= ps->Size && pos>= 0);//插入位置有誤

SeqListCheckCapacity(ps);

for (int i = ps->Size - 1; i >= pos; i--)//從插入位置以后依次向后挪動

{

ps->Array[i + 1] = ps->Array[i];

}

ps->Array[pos] = x;

ps->Size++;

}

void SeqListErase(SeqList* ps, int pos)//任意位置刪除

{

assert(ps);

assert(pos < ps->Size && pos >= 0);//刪除位置有誤

for (int i = pos; i < ps->Size; i++)

{

ps->Array[i] = ps->Array[i + 1];

}

ps->Size--;

}

int SeqListFind(SeqList* ps, SLDataType x)//順序查找法

{

assert(ps);

int i = 0;

while (iSize)

{

if (ps->Array[i] == x)

return i;

++i;

}

return -1;

}

int SeqListFindvalue_Bind(SeqList* ps, int pos)//二分查找法(前提要排序)

{

int low = 0;

int high = ps->Size - 1;

while (low < high)

{

int mid = (low + high) / 2;

if (pos < ps->Array[mid])

high = mid - 1;

else if (pos > ps->Array[mid])

low = mid + 1;

else

return mid;

}

}

*結果展示

尾部依次插入五個元素后，再刪除兩個元素

[圖片上傳失敗...(image-1f79d9-1612934535403)]

頭部依次插入五個元素后，再刪除兩個元素

[圖片上傳失敗...(image-ad641d-1612934535403)]

在原有序列的某個位置插入兩個元素，再把元素刪除

[圖片上傳失敗...(image-60a273-1612934535403)]

接受用戶刪除元素

[圖片上傳失敗...(image-e3ead-1612934535403)]

結語

順序表的優點在于：

可以隨機訪問

緩存命中率比較高(這是因為其數據是連續的，依靠預加載的就有了優勢)

順序表的缺點在于：

中間或者頭部的插入刪除很慢，需要移動數據，時間復雜度為O(N)

空間不夠時，增容會導致一定空間的浪費

總結

以上是生活随笔為你收集整理的mysql 线性表_数据结构-线性表之顺序表的全部內容，希望文章能夠幫你解決所遇到的問題。

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