線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結構
常見的線性表：順序表、鏈表、棧、隊列、字符串…
線性表在邏輯上是線性結構，也就說是連續(xù)的一條直線。但是在物理結構上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結構的形式存儲。
順序表和鏈表的存儲結構如下：
順序表的概念及結構
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結構，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改
而順序表又可以分為：
靜態(tài)順序表
使用定長數(shù)組存儲元素：
也就是說，已經(jīng)把數(shù)組的長度內(nèi)定了，用宏定義了數(shù)組的長度
動態(tài)順序表
使用動態(tài)開辟的數(shù)組存儲：
用malloc函數(shù)開辟空間，當數(shù)組的存儲空間不夠可以用realloc擴容，在順序表中我們用的更多的是動態(tài)的順序表
順序表的接口實現(xiàn)
這里我們只實現(xiàn)動態(tài)的順序表，靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導致N定大了，空間開多了浪費，開少了不夠用。所以現(xiàn)實中基本都是使用動態(tài)順序表，根據(jù)需要動態(tài)的分配空間大小，所以下面我們實現(xiàn)動態(tài)順序表
頭文件如下：
#include<stdio.h>
#include<assert.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SL;
// 對數(shù)據(jù)的管理:增刪查改
void SeqListInit(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListPrint(SL* ps);
void SeqListPushBack(SL* ps, SLDateType x);
void SeqListPushFront(SL* ps, SLDateType x);
void SeqListPopFront(SL* ps);
void SeqListPopBack(SL* ps);
// 順序表查找
int SeqListFind(SL* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x);
// 順序表刪除pos位置的值
void SeqListErase(SL* ps, int pos);
//修改pos位置的值
void SeqListModify(SL* ps, int pos, SLDateType x);
首先為了方便順序表的靈活運用，我們用typedef來在頭文件中定義int為SLDateType，如果下次是字符型的數(shù)據(jù)，我們只需要在這里將int改為char，后續(xù)的代碼就不用更改，其次我們定義一個結構體為順序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;//數(shù)組，存放數(shù)據(jù)
int size;//數(shù)組內(nèi)存放有效數(shù)據(jù)的元素
int capacity;//數(shù)組能夠存儲數(shù)據(jù)的容量
}SL;//將順序表有typedef簡化為SL，方便后面的代碼撰寫
初始化順序表
我們在順序表中創(chuàng)建一個表后，首先要做的就是初始化這個數(shù)據(jù)結構，在今后的學習中我們更是要養(yǎng)成一個初始化的習慣，不然很容易出現(xiàn)bug，有些編譯器甚至會警告
我們在這里將初始化函數(shù)取名為SeqListInit，所需參數(shù)為結構體的地址
我們首先斷言這個順序表，防止為空，所以我們在頭文件中直接寫下assert.h
在這里我們要實現(xiàn)的是動態(tài)順序表，所以我們用malloc動態(tài)開辟數(shù)組a的空間，記住，要判斷動態(tài)開辟是否為空，不然部分的編譯器會有警告
初始化我們直接將數(shù)組的size初始化為0，capacity我們初始化為4
這樣我們初始化就完成了
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc");
return;
}
ps->size = 0;
ps->capacity = 4;
}
銷毀順序表
在函數(shù)完成后我們需要銷毀順序表，避免內(nèi)存的浪費和野指針的出現(xiàn)，所以我們定義一個銷毀順序表的函數(shù)：
首先要做的還是斷言
然后將數(shù)組的空間free掉，并將其置為空指針（防止出現(xiàn)野指針），最后將size和capacity都置為0，就完成了銷毀
void SeqListDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
順序表打印
我們增刪查改后需要打印這個順序表
打印函數(shù)和數(shù)組一樣，不做過多的講解
void SeqListPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
順序表數(shù)據(jù)的插入
凡是插入數(shù)據(jù)，咱們都要檢查他的容量是否夠，所以我們可以先寫一個函數(shù)檢查容量，如果數(shù)組已滿，就擴容
當size和capacity相等的時候就是容量已滿，我們就realloc開辟一個新的空間，大小為原先a數(shù)組的兩倍，然后再將新的空間capacity給數(shù)組a，capacity變成原來的兩倍
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDateType* temp = (SLDateType*)realloc(ps->a,ps->capacity*sizeof(SLDateType*) * 2);
if (temp == NULL)
{
perror("realloc");
return;
}
ps->a = temp;
ps->capacity *= 2;
}
}
數(shù)據(jù)的尾插：
尾插很容易，先檢查容量
然后將數(shù)組的下標為size的位置插入數(shù)據(jù)x
同時size要++
void SeqListPushBack(SL* ps, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
頭插：
同樣的我們首先檢查容量，并且要將所有的數(shù)據(jù)后移一位，再將數(shù)據(jù)x插入數(shù)組下標為0的位置，同時size++
void SeqListPushFront(SL* ps, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
int end = ps->size - 1;
while (end>=0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
順序表數(shù)據(jù)的刪除
刪除的時候一定要記得斷言，因為空順序表就刪不了了
頭刪：
我們將下標為1的元素往前移動，然后size–就可以完成刪除了，移動一次，begin++，同時begin是要小于size的，也就是可以等于size-1
void SeqListPopFront(SL* ps)
{
assert(ps);
int begin = 1;
while (begin<ps->size)
{
ps->a[begin] = ps->a[begin - 1];
begin++;
}
ps->size--;
}
尾刪：
尾刪我們直接將size-1下標的位置置為0，然后size–就可以了，當然，首先就得記得斷言！
void SeqListPopBack(SL* ps)
{
assert(ps);
ps->a[ps->size - 1] = 0;
ps->size--;
}
順序表數(shù)據(jù)的查找
如果在順序表中查找一個數(shù)據(jù)的位置，該怎么辦呢？
很簡單，我們可以遍歷這個數(shù)組，然后返回下標就可以了，數(shù)據(jù)可以直接進行下標的訪問，這就很舒服了，如果找不到，這里我就然他返回-1，因為-1是不可能為數(shù)組的下標的
int SeqListFind(SL* ps, SLDateType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
return -1;
}
}
順序表pos位置的插入
在這里的插入數(shù)據(jù)，我們首先要將知道pos位置，而且pos位置要是大于等于0，小于等于size的，因為頭插就是下標為0的位置，尾插就是下標為size的位置，之前的頭插尾插我們可以直接用這個函數(shù)
插入數(shù)據(jù)我們先將pos位置以及后面的元素的值往后面移動，然后再直接將a[pos]賦值為x，
并且也要從最后一個位置開始往前移動，同時size++
void SeqListInsert(SL* ps, int pos, SLDateType x)
//先移動后插入
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size - 1;
while (pos <= ps->size - 1)
{
ps->a[end+1] = ps->a[end];
end++;
}
ps->a[pos] = x;
ps->size++;
}
順序表pos位置的刪除
pos位置的刪除我們可直接將pos+1位置的元素往前面移動，然后size–
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size - 1 )//這里是<size-1的原因是因為begin=size-2，begin+1就是size-1了
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
順序表pos位置的修改
修改也很容易，直接下標訪問，賦值為x
void SeqListModify(SL* ps, int pos, SLDateType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->a[pos] = x;
}
到這里，順序表的實習就完成了，完整代碼如下：
頭文件：
#include<stdio.h>
#include<assert.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SL;
// 對數(shù)據(jù)的管理:增刪查改
void SeqListInit(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListPrint(SL* ps);
void SeqListPushBack(SL* ps, SLDateType x);
void SeqListPushFront(SL* ps, SLDateType x);
void SeqListPopFront(SL* ps);
void SeqListPopBack(SL* ps);
// 順序表查找
int SeqListFind(SL* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x);
// 順序表刪除pos位置的值
void SeqListErase(SL* ps, int pos);
//修改pos位置的值
void SeqListModify(SL* ps, int pos, SLDateType x);
函數(shù)定義：文章來源：http://www.zghlxwxcb.cn/news/detail-766022.html
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc");
return;
}
ps->size = 0;
ps->capacity = 4;
}
void SeqListDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void CheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDateType* temp = (SLDateType*)realloc(ps->a,ps->capacity*sizeof(SLDateType*) * 2);
if (temp == NULL)
{
perror("realloc");
return;
}
ps->a = temp;
ps->capacity *= 2;
}
}
//尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//頭插
void SeqListPushFront(SL* ps, SLDateType x)
{
assert(ps);
CheckCapacity(ps);
int end = ps->size - 1;
while (end>=0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
//頭刪
void SeqListPopFront(SL* ps)
{
assert(ps);
int begin = 1;
while (begin<ps->size)
{
ps->a[begin] = ps->a[begin - 1];
begin++;
}
ps->size--;
//可以用SeqListErase（ps, 0）
}
//尾刪
void SeqListPopBack(SL* ps)
{
assert(ps);
ps->a[ps->size - 1] = 0;
ps->size--;
//可以用SeqListErase（ps,size-1）
}
// 順序表查找
int SeqListFind(SL* ps, SLDateType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
return -1;
}
}
// 順序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDateType x)
//先移動后插入
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size - 1;
while (pos <= ps->size - 1)
{
ps->a[end+1] = ps->a[end];
end++;
}
ps->a[pos] = x;
ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size - 1)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
void SeqListModify(SL* ps, int pos, SLDateType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->a[pos] = x;
}
今天的分享到這里就結束了，謝謝大家的支持！文章來源地址http://www.zghlxwxcb.cn/news/detail-766022.html
到了這里，關于數(shù)據(jù)結構之順序表的實現(xiàn)（詳解！附完整代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
