【数据结构|C语言版】顺序表

---

前言

各位小伙伴大家好！小编来给大家讲解一下数据结构中顺序表的相关知识。

1. 初步认识数据结构

【概念】数据结构是计算机存储、组织数据的⽅式。

• 数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合
• 数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构
• 数据结构能够存储数据（如顺序表、链表等结构）
• 数据结构存储的数据能够方便查找
• 数组是最基础的数据结构

2. 线性表

【概念】零个或多个数据元素的有限序列。
【分类】

【补充】

3. 顺序表

3.1 顺序表的概念

【概念】用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。
【特点】逻辑上相邻的数据元素，物理次序也是相邻的。

3.1 顺序表的分类

【分类】

1. 静态顺序表：使用定长数组存储元素。
   

2. 动态顺序表：使用动态开辟的数组存储。
   

3.2 动态顺序表的实现

#define INIT_CAPACITY 4 
typedef int SLDataType; 
// 动态顺序表 -- 按需申请 
typedef struct SeqList 
{ SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 
}SL; 
//初始化和销毁 
void SLInit(SL* ps); 
void SLDestroy(SL* ps); 、
void SLPrint(SL* ps); 
//扩容 
void SLCheckCapacity(SL* ps); 
//头部插⼊删除 / 尾部插⼊删除 
void SLPushBack(SL* ps, SLDataType x); 
void SLPopBack(SL* ps); 
void SLPushFront(SL* ps, SLDataType x); 
void SLPopFront(SL* ps); 
//指定位置之前插⼊/删除数据 
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;      // 有效数据int capacity;  // 空间容量
}SL;void SLInit(SL* psl);//初始化顺序表
void SLDestroy(SL* psl);//摧毁顺序表void SLPrint(SL* psl);//打印顺序表
void SLCheckCapacity(SL* psl);//检测顺序表的容量// 头尾插入删除
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删// 任意下标位置的插入删除
void SLInsert(SL* psl, int pos, SLDataType x);//任意下标插
void SLErase(SL* psl, int pos);//任意下标删// 找到返回下标
// 没有找到返回-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);// 挪动数据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是下标
// size是数据个数，看做下标的话，他是最后一个数据的下一个位置
void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos <= psl->size);SLCheckCapacity(psl);// 挪动数据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);// 挪动覆盖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】

#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);
}// 多画图
// 写一个函数，编译一个 测试一个 -> 一步一个脚印
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、尾插数据  2、尾删数据************\n");printf("********3、头插数据  4、头删数据************\n");printf("**5、任意位置插入数据  6、任意位置删除数据**\n");printf("********7、查找数据  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("请输入你的选择:>");scanf("%d", &option);if (option == 1){printf("请依次输入你的要尾插数据个数和数据:>");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("请输入要尾删数据的个数：");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopBack(&s);}}else if (option == 3){printf("请依次输入你的要头插数据个数和数据:>");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("请输入要头删数据的个数：");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopFront(&s);}}else if (option == 5){printf("请先输入你的要任意插入的个数，在输入下标(下标第一个从0开始哦)，在输入这个位置的数据(推荐一个一个加，不然你的下标顺序会不好判断哦！):>");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("请输入要删除数据的个数和下标：");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("请输入要查找的的元素(一个)：");int num = 0;scanf("%d", &num);int pos = SLFind(&s, num);printf("该元素的下标为：");printf("%d", pos);}else if (option == 8){break;}else if (option == 9){printf("顺序表已打印,如下：\n");SLPrint(&s);Sleep(1500);}else{printf("无此选项，请重新输入\n");}} while (option != 0);SLDestroy(&s);return 0;
}

结语

以上就是小编对顺序表的一些初步认识。
如果觉得小编讲的还可以，还请一键三连。互三必回！
持续更新中~！