前言
線性表是n個(gè)具有相同屬性的有限數(shù)列，常見的線性表有：=順序表，鏈表，棧，隊(duì)列，字符串…
線性表在邏輯上是線性結(jié)構(gòu)，也就是說連成一條直線，但是在物理結(jié)構(gòu)上不一定連續(xù)，線性表在物理上存儲(chǔ)是，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式進(jìn)行存儲(chǔ)。
本章，我們將通過順序表的實(shí)現(xiàn)來研究順序表
一、"SeqList.h"部分
一個(gè)大的工程，永遠(yuǎn)不可能只有一個(gè)源文件，所以我們要善于將一個(gè)工程分成幾個(gè)部分來完結(jié)，該頭文件則是包含了庫函數(shù)的引用頭文件及函數(shù)的定義，包括了幾個(gè)順序表的功能，這里我們將其一一列出
需要注意的部分博主已經(jīng)注釋
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//動(dòng)態(tài)順序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;//指向動(dòng)態(tài)開辟數(shù)組
int size;//存儲(chǔ)有效數(shù)據(jù)個(gè)數(shù)
int capacity;//空間大小
}SeqList;
// 對(duì)數(shù)據(jù)的管理:增刪查改
void SeqListInit(SeqList* ps);//初始化
void SeqListDestroy(SeqList* ps);//消除
void SLCheckCapacity(SeqList* ps);//擴(kuò)容空間
void SeqListPrint(SeqList* ps);//打印
void SeqListPushBack(SeqList* ps, SLDateType x);//尾插
void SeqListPopBack(SeqList* ps);//尾刪
void SeqListPushFront(SeqList* ps, SLDateType x);//頭插
void SeqListPopFront(SeqList* ps);//頭刪
// 順序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 順序表刪除low位置的值
void SeqListErase(SeqList* ps, int low);
下面我們就要圍繞著頭文件進(jìn)行程序的編寫
二、"SeqList.c"部分
1.初始化
既然是動(dòng)態(tài)規(guī)劃內(nèi)存，那便少不了malloc，relloc之類動(dòng)態(tài)內(nèi)存函數(shù)的使用，這里，我們使用malloc進(jìn)行動(dòng)態(tài)開辟數(shù)組空間
代碼如下：
void SeqListInit(SeqList* ps)
{
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc failed");
exit(-1);
}
ps->size = 0;
ps->capacity = 4;
}
初始化比較簡單，這里我們就講到這
2.銷毀
我們開辟空間后，不在使用時(shí)，要及時(shí)銷毀，對(duì)于釋放內(nèi)存空間，且與malloc經(jīng)常一起出沒的，那便是free函數(shù)，釋放內(nèi)存后，別忘了講指針置空
void SeqListDestroy(SeqList* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
3.擴(kuò)容及打印
有時(shí)候我們?cè)谔砑訑?shù)時(shí)可能會(huì)發(fā)生空間滿了的情況，所以這時(shí)候我們就要擴(kuò)容，但擴(kuò)容用哪個(gè)動(dòng)態(tài)內(nèi)存函數(shù)好呢，答案肯定是realloc，因?yàn)樗芨`活的對(duì)內(nèi)存大小進(jìn)行調(diào)整
注：realloc開辟的內(nèi)存空間千萬不能用free釋放，因?yàn)閞ealloc自己帶有釋放功能，盲目使用可能會(huì)造成意想不到的后果
void SLCheckCapacity(SeqList* ps)//擴(kuò)容
{
//滿了就要去擴(kuò)容
if (ps->size == ps->capacity)
{
SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
ps->capacity *= 2;
}
}
打印就比較簡單了，基本上寫代碼就能用，這里我們之間上代碼
void SeqListPrint(SeqList* ps)//打印
{
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->a[i]);
printf("\n");
}
4.尾插及尾刪
尾插，顧名思義就是在數(shù)組結(jié)尾處插入一個(gè)數(shù)字，這里我們的有效數(shù)字個(gè)數(shù)size就得加1，并防止ps->size>=ps->capacity即可
void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
{
SLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
尾刪也就是講最后一位數(shù)字刪去，這里我們要防止出現(xiàn)數(shù)組沒數(shù)據(jù)的情況即(ps->size=0).
這里我們可以采用斷言函數(shù)來控制size的范圍
void SeqListPopBack(SeqList* ps)//尾刪
{
//暴力刪除
assert(ps->size > 0);
ps->size--;
5.頭插及頭刪
這兩個(gè)也類似與上面的尾插和尾刪，同樣得注意ps->size=ps->capacity及ps->size=0的情況，這里與數(shù)組的首尾增添相似，這里就不細(xì)講了，直接上代碼
void SeqListPushFront(SeqList* ps, SLDateType x)//頭插
{
SLCheckCapacity(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(SeqList* ps)//頭刪
{
assert(ps->size > 0);
for (int i = 0; i < ps->size; i++)
ps->a[i] = ps->a[i + 1];
ps->size--;
}
6.順序表查找
順序表的查找原理與數(shù)組查找大致一致，讀者可以根據(jù)數(shù)組查找來復(fù)刻出順序表查找的方式，上代碼
int SeqListFind(SeqList* ps, SLDateType x)//順序表查找
{
for (int i = 0; i < ps->size; i++)
{
if (x == ps->a[i])
{
return 1;
}
}
return 0;
}
7.順序表在pos位插入x
這里插入問題首先還是要考慮ps->size=ps->capacity的情況，如何插入一個(gè)數(shù)字與數(shù)組同樣是大相徑庭，故這里就不細(xì)講
void SeqListInsert(SeqList* ps, int pos, SLDateType x)// 順序表在pos位置插入x
{
SLCheckCapacity(ps);
assert(pos>=0&&pos<=ps->size);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
SeqListPrint(ps);
}
8.順序表刪除low位置的數(shù)
提到刪除，第一時(shí)間想到會(huì)不會(huì)出現(xiàn)ps->size=0的情況，然后同樣利用數(shù)組知識(shí)，寫出代碼
void SeqListErase(SeqList* ps, int low)// 順序表刪除low位置的值
{
assert(low>=0&&low<ps->size);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (i != low - 1)
printf("%d ", ps->a[i]);
}
}
順序表的核心部分到此結(jié)束了，下面我們來進(jìn)行模擬實(shí)現(xiàn)
三、"text.c"部分
這里我們對(duì)照函數(shù)部分寫出對(duì)應(yīng)的實(shí)現(xiàn)方法，來確定函數(shù)是否有誤，這里我們直接放代碼
#include "SeqList.h"
void TestSeqList1()//尾插尾刪
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPopBack(&sl);
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist2()//頭插頭刪
{
SeqList sl;
SeqListInit(&sl);
SeqListPushFront(&sl, 1);
SeqListPushFront(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPopFront(&sl);
SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist3()//查找數(shù)
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
SeqListPrint(&sl);
int ret = SeqListFind(&sl, 2);
if (ret == 1)
{
printf("找到了，下標(biāo)為:%d\n", ret);
}
else
printf("該數(shù)字不在該順序表里\n");
//SeqListPrint(&sl);
SeqListDestroy(&sl);
}
void TestSeqlist4()//順序表在pos位置插入x，在low刪除數(shù)字
{
SeqList sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushFront(&sl, 3);
SeqListPushFront(&sl, 4);
printf("插入前:\n");
SeqListPrint(&sl);
printf("插入后:\n");
SeqListInsert(&sl, 3, 5);
printf("刪除low位置數(shù)字后:\n");
SeqListErase(&sl, 2);
SeqListDestroy(&sl);
}
int main()
{
printf("尾插尾刪用例\n");
TestSeqList1();
printf("頭插頭刪用例\n");
TestSeqlist2();
printf("順序表查找數(shù)據(jù)用例\n");
TestSeqlist3();
printf("順序表在pos位置插入x,刪除low位置的數(shù)用例\n");
TestSeqlist4();
return 0;
}
博主使用的用例結(jié)果如下圖所示：
文章來源：http://www.zghlxwxcb.cn/news/detail-621394.html
結(jié)語
關(guān)于順序表的內(nèi)容即實(shí)現(xiàn)到這里就結(jié)束了，希望可以幫到各位文章來源地址http://www.zghlxwxcb.cn/news/detail-621394.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-順序表各項(xiàng)功能的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
