1.线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.2 动态顺序表的实现

头文件

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
//静态顺序表
//#define N 1000
//typedef int SLDataType;
//typedef struct SeqList
//{
//	int a[N];
//	int size;
//};//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;//动态内存指针int size;//存储有效数据个数int capacity;//动态内存空间大小
}SL;//管理数据，增删查改
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//检查空间，如果满了，进行增容
void CheckCapacity(SL* ps);
// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x);
// 顺序表尾删
void SLPopBack(SL* ps);
// 顺序表头插
void SLPushFront(SL* ps, SLDataType x);
// 顺序表头删
void SLPopFront(SL* ps);
//打印
void SLPrint(SL* ps);

测试文件

//顺序表
#include"SeqList.h"
void TestSeqList1()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPushBack(&sl, 6);SLPushBack(&sl, 6);SLPushBack(&sl, 0);SLPushBack(&sl, 0);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);/*SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);*/SLPrint(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPrint(&sl);SLDestroy(&sl);
}void TestSeqList2()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLPushFront(&sl, 10);SLPushFront(&sl, 20);SLPushFront(&sl, 30);SLPushFront(&sl, 40);SLPrint(&sl);
}int main()
{//TestSeqList1();TestSeqList2();return 0;
}

实现文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"//初始化顺序表
void SLInit(SL* ps)
{//为顺序表开辟动态内存ps->a = (SLDataType*)malloc(sizeof(SLDataType) *4);if (ps->a == NULL){perror("malloc");exit(-1);//退出程序}ps->size = 0;ps->capacity = 4;
}
//检查空间，如果满了，进行增容
void CheckCapacity(SL* ps)
{//动态内存放满，需要扩容if (ps->size == ps->capacity){//用临时指针存放扩容后的动态内存地址SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * sizeof(SLDataType) * 2);if (tmp == NULL){perror("realloc");exit(-1);}//归还地址ps->a = tmp;ps->capacity *= 2;}
}
// 顺序表头插
void SLPushFront(SL * ps, SLDataType x)
{CheckCapacity(ps);//挪动数据，从后往前挪，次数为size-1int end = ps->size - 1;while (end>=0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}
// 顺序表头删
void SLPopFront(SL* ps)
{int end = 0;while (end<= ps->size - 1){//从左往右移，将首位覆盖ps->a[end] = ps->a[end + 1];end++;}
}
// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{//检查放满CheckCapacity(ps);ps->a[ps->size] = x;ps->size++;}
// 顺序表尾删
void SLPopBack(SL* ps)
{//如果size为0，就返回，继续删会导致越界(温柔检查）if (ps->size == 0){return;}//或者使用断言检查size（暴力检查）assert(ps->size);//size--就代表将数据删除了ps->size--;
}//销毁
void SLDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
//打印
void SLPrint(SL* ps)
{int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

测试