前言
各位小伙伴大家好！小編來(lái)給大家講解一下數(shù)據(jù)結(jié)構(gòu)中順序表的相關(guān)知識(shí)。
1. 初步認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)
【概念】數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的?式。
- 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在?種或多種特定關(guān)系的數(shù)據(jù)元素的集合
- 數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)的內(nèi)部構(gòu)成，即數(shù)據(jù)由那部分構(gòu)成，以什么?式構(gòu)成，以及數(shù)據(jù)元素之間呈現(xiàn)的結(jié)構(gòu)
- 數(shù)據(jù)結(jié)構(gòu)能夠存儲(chǔ)數(shù)據(jù)（如順序表、鏈表等結(jié)構(gòu)）
- 數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)能夠方便查找
- 數(shù)組是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)
2. 線性表
【概念】零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。
【分類】
【補(bǔ)充】
3. 順序表
3.1 順序表的概念
【概念】用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，這種存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表。
【特點(diǎn)】邏輯上相鄰的數(shù)據(jù)元素，物理次序也是相鄰的。
3.1 順序表的分類
【分類】
-
靜態(tài)順序表：使用定長(zhǎng)數(shù)組存儲(chǔ)元素。
-
動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲(chǔ)。
3.2 動(dòng)態(tài)順序表的實(shí)現(xiàn)
#define INIT_CAPACITY 4
typedef int SLDataType;
// 動(dòng)態(tài)順序表 -- 按需申請(qǐng)
typedef struct SeqList
{
SLDataType* a;
int size; // 有效數(shù)據(jù)個(gè)數(shù)
int capacity; // 空間容量
}SL;
//初始化和銷毀
void SLInit(SL* ps);
void SLDestroy(SL* ps); 、
void SLPrint(SL* ps);
//擴(kuò)容
void SLCheckCapacity(SL* ps);
//頭部插?刪除 / 尾部插?刪除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插?/刪除數(shù)據(jù)
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps,int pos);
int SLFind(SL* ps, SLDataType x);
【Seqlist.h】
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>
typedef int SLDataType;
// sequence list
typedef struct SeqList
{
SLDataType* a;
int size; // 有效數(shù)據(jù)
int capacity; // 空間容量
}SL;
void SLInit(SL* psl);//初始化順序表
void SLDestroy(SL* psl);//摧毀順序表
void SLPrint(SL* psl);//打印順序表
void SLCheckCapacity(SL* psl);//檢測(cè)順序表的容量
// 頭尾插入刪除
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//頭插
void SLPopBack(SL* psl);//尾刪
void SLPopFront(SL* psl);//頭刪
// 任意下標(biāo)位置的插入刪除
void SLInsert(SL* psl, int pos, SLDataType x);//任意下標(biāo)插
void SLErase(SL* psl, int pos);//任意下標(biāo)刪
// 找到返回下標(biāo)
// 沒有找到返回-1
int SLFind(SL* psl, SLDataType x);
【Seqlist.c】
#include"seqlist.h"
#include <string.h>
void SLInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
void SLDestroy(SL* psl)
{
assert(psl);
if (psl->a != NULL)
{
free(psl->a);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
}
void SLPrint(SL* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
void SLCheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
psl->a = tmp;
psl->capacity = newCapacity;
}
}
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
SLCheckCapacity(psl);
// 挪動(dòng)數(shù)據(jù)
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;
psl->size++;
}
void SLPopBack(SL* psl)
{
assert(psl);
// 空
// 溫柔的檢查
/*if (psl->size == 0)
{
return;
}*/
// 暴力檢查
assert(psl->size > 0);
//psl->a[psl->size - 1] = -1;
psl->size--;
}
void SLPopFront(SL* psl)
{
assert(psl);
// 暴力檢查
assert(psl->size > 0);
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
// 注意pos是下標(biāo)
// size是數(shù)據(jù)個(gè)數(shù)，看做下標(biāo)的話，他是最后一個(gè)數(shù)據(jù)的下一個(gè)位置
void SLInsert(SL* psl, int pos, SLDataType x)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
SLCheckCapacity(psl);
// 挪動(dòng)數(shù)據(jù)
int end = psl->size - 1;
while (end >= pos)
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[pos] = x;
psl->size++;
}
void SLErase(SL* psl, int pos)
{
assert(psl);
assert(pos >= 0 && pos < psl->size);
// 挪動(dòng)覆蓋
int begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
int SLFind(SL* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
void SLclear(SL* psl, SLDataType x)
{
psl->size = 0;
memset(psl->a, 0, sizeof(psl->a));
printf("順序表已清空?。?！\n");
Sleep(1500);
}
【test.c】文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-853119.html
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <Windows.h>
#include "seqlist.h"
void TestSL1()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPushBack(&sl, 6);
SLPushBack(&sl, 7);
SLPushBack(&sl, 8);
SLPushBack(&sl, 9);
SLPrint(&sl);
SLPushFront(&sl, 10);
SLPushFront(&sl, 20);
SLPushFront(&sl, 30);
SLPushFront(&sl, 40);
SLPrint(&sl);
SLDestroy(&sl);
}
void TestSL2()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLPopBack(&sl);
SLPrint(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);
//SLPopBack(&sl);
//SLPrint(&sl);
SLPushFront(&sl, 10);
SLPushFront(&sl, 20);
SLPushFront(&sl, 30);
SLPushFront(&sl, 40);
SLPrint(&sl);
SLDestroy(&sl);
}
// 多畫圖
// 寫一個(gè)函數(shù)，編譯一個(gè) 測(cè)試一個(gè) -> 一步一個(gè)腳印
void TestSL3()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
SLPopFront(&sl);
SLPrint(&sl);
//SLPopFront(&sl);
//SLPrint(&sl);
}
void TestSL4()
{
//SL* ptr = NULL;
//SLInit(ptr);
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLInsert(&sl, 2, 20);
SLPrint(&sl);
SLInsert(&sl, 6, 20);
SLPrint(&sl);
SLInsert(&sl, 0, 20);
SLPrint(&sl);
SLInsert(&sl, 10, 20);
SLPrint(&sl);
SLDestroy(&sl);
}
void TestSL5()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPrint(&sl);
SLErase(&sl, 3);
SLPrint(&sl);
SLErase(&sl, 3);
SLPrint(&sl);
//SLErase(&sl, 3);
//SLPrint(&sl);
}
void menu()
{
printf("********************************************\n");
printf("********************************************\n");
printf("********1、尾插數(shù)據(jù) 2、尾刪數(shù)據(jù)************\n");
printf("********3、頭插數(shù)據(jù) 4、頭刪數(shù)據(jù)************\n");
printf("**5、任意位置插入數(shù)據(jù) 6、任意位置刪除數(shù)據(jù)**\n");
printf("********7、查找數(shù)據(jù) 8、退出順序表**********\n");
printf("******** 9、打印順序表 ********************\n");
printf("********************************************\n");
printf("********************************************\n");
}
int main()
{
/*void TestSL4();
void TestSL3();
void TestSL2();
void TestSL1();*/
SL s;
SLInit(&s);
int option = 0;
do
{
menu();
printf("請(qǐng)輸入你的選擇:>");
scanf("%d", &option);
if (option == 1)
{
printf("請(qǐng)依次輸入你的要尾插數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù):>");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x = 0;
scanf("%d", &x);
SLPushBack(&s, x);
}
}
else if (option == 2)
{
printf("請(qǐng)輸入要尾刪數(shù)據(jù)的個(gè)數(shù)：");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
SLPopBack(&s);
}
}
else if (option == 3)
{
printf("請(qǐng)依次輸入你的要頭插數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù):>");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x = 0;
scanf("%d", &x);
SLPushFront(&s, x);
}
}
else if (option == 4)
{
printf("請(qǐng)輸入要頭刪數(shù)據(jù)的個(gè)數(shù)：");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
SLPopFront(&s);
}
}
else if (option == 5)
{
printf("請(qǐng)先輸入你的要任意插入的個(gè)數(shù)，在輸入下標(biāo)(下標(biāo)第一個(gè)從0開始哦)，在輸入這個(gè)位置的數(shù)據(jù)(推薦一個(gè)一個(gè)加，不然你的下標(biāo)順序會(huì)不好判斷哦！):>");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x = 0;
int pos = 0;
scanf("%d %d", &pos, &x);
SLInsert(&s, pos, x);
}
}
else if (option == 6)
{
printf("請(qǐng)輸入要?jiǎng)h除數(shù)據(jù)的個(gè)數(shù)和下標(biāo)：");
int n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int pos = 0;
scanf("%d", &pos);
SLErase(&s, pos);
}
}
else if (option == 7)
{
printf("請(qǐng)輸入要查找的的元素(一個(gè))：");
int num = 0;
scanf("%d", &num);
int pos = SLFind(&s, num);
printf("該元素的下標(biāo)為：");
printf("%d", pos);
}
else if (option == 8)
{
break;
}
else if (option == 9)
{
printf("順序表已打印,如下：\n");
SLPrint(&s);
Sleep(1500);
}
else
{
printf("無(wú)此選項(xiàng)，請(qǐng)重新輸入\n");
}
} while (option != 0);
SLDestroy(&s);
return 0;
}
結(jié)語(yǔ)
以上就是小編對(duì)順序表的一些初步認(rèn)識(shí)。
如果覺得小編講的還可以，還請(qǐng)一鍵三連。互三必回！
持續(xù)更新中~！
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-853119.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)|C語(yǔ)言版】順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
