C語言實(shí)現(xiàn)順序表的基本操作的示例詳解
一、認(rèn)識(shí)順序表
1.線性表
線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表有順序表、鏈表、棧、隊(duì)列、字符串……線性表在邏輯上是線性結(jié)構(gòu)，也就是說是一條連續(xù)的直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式來存儲(chǔ)。
2.順序表的概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪改查。順序表一般可分為：靜態(tài)順序表和動(dòng)態(tài)順序表（使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)）。
1.靜態(tài)順序表：使用定長數(shù)組存儲(chǔ)元素
#define MAX 10
typedef int SLDataType;//當(dāng)存儲(chǔ)數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType arr[MAX];//用來存儲(chǔ)數(shù)據(jù)
int size;//用來記錄數(shù)組中存儲(chǔ)有效數(shù)據(jù)元素的個(gè)數(shù)
}SL;
2.動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)
//動(dòng)態(tài)順序表
typedef int SLDataType;//當(dāng)存儲(chǔ)數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動(dòng)態(tài)開辟的數(shù)組
int size;//用來記錄數(shù)組中存儲(chǔ)有效數(shù)據(jù)元素的個(gè)數(shù)
int capacity;//用來記錄容量大小
}SL;
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致MAX定大了，空間開多了浪費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以本文中使用動(dòng)態(tài)開辟的順序表實(shí)現(xiàn)順序表的基本操作。
二、順序表的基本操作（接口實(shí)現(xiàn)）
1.初始化順序表
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
初始化時(shí)設(shè)置其有效數(shù)據(jù)個(gè)數(shù)和容量都為0，指針指向NULL。
2.打印順序表
void SLPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
3.尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity)
{
int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->arr = tmp;
ps->capacity = NewCapacity;
}
ps->arr[ps->size] = x;
ps->size++;
}尾插就是在尾部插入數(shù)據(jù)，因?yàn)閯傞_始的時(shí)候沒有給數(shù)組分配空間，所以要考慮當(dāng)沒有空間時(shí)要去申請(qǐng)空間，realloc函數(shù)是擴(kuò)容函數(shù)，在指針為空的情況下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判斷當(dāng)前容量大小并確定要開辟的空間大小。
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用來在堆內(nèi)存中開辟空間，realloc之后注意將其強(qiáng)制轉(zhuǎn)化成SLDataType*類型。當(dāng)成功開辟空間之后賦給ps->arr，同時(shí)注意將NewCapacity賦給ps->capacity。
4.尾刪
void SLPopBack(SL* ps)
{
assert(ps);
//暴力的檢查
assert(ps->size > 0);//判斷ps->size是否大于0，當(dāng)?shù)扔?時(shí)再刪的話ps->size就會(huì)變?yōu)?1，越界
//溫柔的檢查
//if (ps->size == 0)
//{
// return;
//}
ps->size--;
}
當(dāng)ps->size等于0時(shí)直接返回，如果不返回，造成ps->size為負(fù)數(shù)，造成數(shù)組越界，當(dāng)我們再次插入數(shù)據(jù)的時(shí)候可能會(huì)出現(xiàn)報(bào)錯(cuò)，同時(shí)當(dāng)越界時(shí)可能不會(huì)報(bào)錯(cuò)，但是可能會(huì)在free時(shí)候報(bào)錯(cuò)。所以要用assert(ps->size > 0)檢查ps->size大小，等于0時(shí)直接退出，并提示。
擴(kuò)展：free時(shí)候報(bào)錯(cuò)可能的錯(cuò)誤原因有兩種，一是free時(shí)候指針不正確，可能是野指針，同時(shí)釋放的時(shí)候必須從起始位置釋放。二是越界時(shí)候free會(huì)報(bào)錯(cuò)。當(dāng)越界讀數(shù)組的時(shí)候基本不會(huì)被檢查出來報(bào)錯(cuò)，但是改變它的值的時(shí)候就可能會(huì)報(bào)錯(cuò)，是一種抽查行為，是在運(yùn)行時(shí)檢查。
5.擴(kuò)容
void SLCheckCapacity(SL* ps)
{
assert(ps);
//檢查是否需要擴(kuò)容
if (ps->size == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->capacity = NewCapacity;
ps->arr = tmp;
}
}擴(kuò)容函數(shù)，用于檢查數(shù)組空間大小是否適合繼續(xù)插入，當(dāng)數(shù)組空間不足時(shí)進(jìn)行擴(kuò)容，定義此函數(shù)之后可以對(duì)上面尾插函數(shù)進(jìn)行簡化，如下：
void SLPushBack(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}
6.頭插
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
int end = ps->size;
//挪動(dòng)數(shù)據(jù)
while (end > 0)
{
ps->arr[end] = ps->arr[end-1];
end--;
}
ps->arr[0] = x;
ps->size++;
}
利用擴(kuò)容函數(shù)對(duì)其檢查，注意控制循環(huán)結(jié)束條件。
7.頭刪
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size-1)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
注意判斷當(dāng)ps->size等于0時(shí)不能再進(jìn)行ps->size--，要加上一條判斷語句assert(ps->size > 0)。
8.任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
assert(ps);
assert(pos >= 0);
assert(pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size;
while (end>pos)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
pos是數(shù)組下標(biāo)，同時(shí)注意判斷pos的范圍。
9.任意位置刪除
void SLErase(SL* ps, int pos)//任意位置刪除
{
assert(ps);
assert(pos >= 0);
assert(pos < ps->size);
while (pos < ps->size-1)
{
ps->arr[pos] = ps->arr[pos + 1];
pos++;
}
ps->size--;
}
pos表示的是數(shù)組下標(biāo)，有assert(pos >= 0)和assert(pos <= ps->size)兩個(gè)判斷條件之后不用再加assert(ps->size>0)，因?yàn)楫?dāng)ps->size等于0時(shí)，assert(pos <= ps->size)會(huì)報(bào)錯(cuò)。
10.查找某個(gè)數(shù)的位置
int SLFind(SL* ps, SLDataType x)//返回類型為int,是數(shù)組下標(biāo)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
返回值是數(shù)組下標(biāo)。
思考：當(dāng)我們想刪除某個(gè)值時(shí)應(yīng)該怎么做？當(dāng)被刪除的值有多個(gè)時(shí)又要怎么做呢？
我們可以通過下面的代碼實(shí)現(xiàn)：
int SLNFind(SL* ps, SLDataType x, int begin)//begin是開始查找的位置
{
assert(ps);
int i = 0;
for (i = begin; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}三、順序表演示及代碼（含源碼）
1.演示效果
2.完整源代碼
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//動(dòng)態(tài)順序表
typedef int SLDataType;//當(dāng)存儲(chǔ)數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動(dòng)態(tài)開辟的數(shù)組
int size;//用來記錄數(shù)組中存儲(chǔ)有效數(shù)據(jù)元素的個(gè)數(shù)
int capacity;//用來記錄容量大小
}SL;
void SLInit(SL* ps)//初始化順序表
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//檢查是否需要擴(kuò)容
{
assert(ps);
//檢查是否需要擴(kuò)容
if (ps->size == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->capacity = NewCapacity;
ps->arr = tmp;
}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
SLCheckCapacity(ps);//檢查是否需要擴(kuò)容
//assert(ps);
//if (ps->size == ps->capacity)
//{
// int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
// SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
// if (tmp == NULL)
// {
// perror("realloc");
// exit(-1);
// }
// ps->arr = tmp;
// ps->capacity = NewCapacity;
//}
ps->arr[ps->size] = x;
ps->size++;
}
void SLPrint(SL* ps)//打印
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
void SLDestroy(SL* ps)//銷毀
{
assert(ps);
if (ps->arr != NULL)
{
free(ps->arr);
ps->arr = NULL;
}
ps->size = ps->capacity = 0;
}
void SLPopBack(SL* ps)//尾刪
{
assert(ps);
//暴力的檢查
assert(ps->size > 0);//判斷ps->size是否大于0，當(dāng)?shù)扔?時(shí)再刪的話ps->size就會(huì)變?yōu)?1，越界
//溫柔的檢查
if (ps->size == 0)
{
return;
}
ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{
SLCheckCapacity(ps);
int end = ps->size;
//挪動(dòng)數(shù)據(jù)
while (end > 0)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[0] = x;
ps->size++;
}
void SLPopFront(SL* ps)//頭刪
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
assert(ps);
assert(pos >= 0);
assert(pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size;
while (end > pos)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置刪除
{
assert(ps);
assert(pos >= 0);
assert(pos < ps->size);
while (pos < ps->size - 1)
{
ps->arr[pos] = ps->arr[pos + 1];
pos++;
}
ps->size--;
}
int SLFind(SL* ps, SLDataType x)//查找某個(gè)數(shù)并返回下標(biāo)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
int SLNFind(SL* ps, SLDataType x, int begin)//從begin開始查找某個(gè)數(shù)
{
assert(ps);
int i = 0;
for (i = begin; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
void menu()//菜單函數(shù)
{
printf("********************************\n");
printf("** 1.尾插 2.尾刪 **\n");
printf("** 3.頭插 4.頭刪 **\n");
printf("** 5.任意位置插入 **\n");
printf("** 6.任意位置刪除 **\n");
printf("** 7.查找某個(gè)數(shù)并返回其下標(biāo) **\n");
printf("** 8.刪除某個(gè)數(shù) **\n");
printf("** 9.打印 **\n");
printf("** 0.退出程序 **\n");
}
int main()
{
int input = 0;
int ret = 0;
int pos = 0;
SL sl;
SLInit(&sl);
do {
menu();
printf("請(qǐng)選擇：");
scanf("%d", &input);
switch (input)
{
case 1:
printf("請(qǐng)輸入你要尾插的值，以-1結(jié)束：");
scanf("%d", &ret);
while (ret != -1)
{
SLPushBack(&sl, ret);
scanf("%d", &ret);
}
printf("尾插成功！\n");
break;
case 2:
SLPopBack(&sl);
printf("尾刪成功！\n");
break;
case 3:
printf("請(qǐng)輸入你要頭插的值，以-1結(jié)束：");
scanf("%d", &ret);
while (ret != -1)
{
SLPushFront(&sl, ret);
scanf("%d", &ret);
}
printf("頭插成功！\n");
break;
case 4:
SLPopFront(&sl);
printf("頭刪成功！\n");
break;
case 5:
printf("請(qǐng)輸入你想插入的位置和數(shù)值：");
scanf("%d%d", &pos, &ret);
SLInsert(&sl, pos - 1, ret);
printf("插入成功！\n");
break;
case 6:
printf("請(qǐng)輸入你想刪除的位置：");
scanf("%d", &pos);
SLErase(&sl, pos - 1);
printf("刪除成功！\n");
break;
case 7:
printf("請(qǐng)輸入你想要查找的數(shù)：");
scanf("%d", &ret);
int s = SLFind(&sl, ret);
printf("查找的數(shù)的數(shù)組下標(biāo)為:%d！\n", s);
break;
case 8:
printf("請(qǐng)輸入你要?jiǎng)h除的數(shù)值：");
scanf("%d", &ret);
int tmp = SLNFind(&sl, ret, 0);
while (tmp != -1)
{
SLErase(&sl, tmp);
tmp = SLNFind(&sl, ret, tmp);
}
printf("刪除成功！\n");
break;
case 9:
SLPrint(&sl);
break;
default:
printf("請(qǐng)重新選擇！\n");
break;
}
} while (input);
SLDestroy(&sl);
return 0;
}
以上就是C語言實(shí)現(xiàn)順序表的基本操作的示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語言順序表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C++中判斷成員函數(shù)是否重寫的相關(guān)資料,需要的朋友可以參考下2017-04-04
虛函數(shù)主要通過V-Table虛函數(shù)表來實(shí)現(xiàn),該表主要包含一個(gè)類的虛函數(shù)的地址表,可解決繼承、覆蓋的問題,下面這篇文章主要給大家介紹了如何通過一篇文章帶你掌握C++虛函數(shù)的來龍去脈,需要的朋友可以參考下2022-12-12
Reactor反應(yīng)器的實(shí)現(xiàn)方法詳解
本篇文章是對(duì)Reactor反應(yīng)器的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
大家好，本篇文章主要講的是C++約瑟夫環(huán)問題詳解 ，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
這篇文章主要介紹了C語言實(shí)現(xiàn)二叉樹遍歷的迭代算法,包括二叉樹的中序遍歷、先序遍歷及后序遍歷等,是非常經(jīng)典的算法,需要的朋友可以參考下2014-09-09
C++的STL中accumulate函數(shù)的使用方法
這篇文章主要介紹了C++的STL中accumulate的使用方法，accumulate作用是累加求和即自定義類型數(shù)據(jù)處理，下文具體的操作方法需要的小伙伴可以參考一下2022-03-03
Visual C++ 常用數(shù)據(jù)類型轉(zhuǎn)換方法詳解
本文純粹是總結(jié)一下有關(guān)類型轉(zhuǎn)換的貼子,需要的朋友可以參考下2017-06-06
C++ 允許多個(gè)函數(shù)擁有相同的名字，只要它們的參數(shù)列表不同就可以，這就是函數(shù)的重載（Function Overloading），借助重載，一個(gè)函數(shù)名可以有多種用途2022-06-06
C/C++?判斷計(jì)算機(jī)存儲(chǔ)器字節(jié)序（端序）的幾種方式
字節(jié)序是計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)的格式,主存儲(chǔ)器（主存）的字節(jié)序?qū)Τ绦虻囊浦残院图嫒菪灾陵P(guān)重要,利用聯(lián)合體、指針、位移和掩碼等方法可以檢測和處理字節(jié)序問題,對(duì)于內(nèi)存數(shù)據(jù)操作重要,也關(guān)系到跨平臺(tái)和網(wǎng)絡(luò)通信的數(shù)據(jù)處理2024-10-10
以下是對(duì)C語言中堆空間的生成與釋放進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-08-08