【数据结构初阶】实现顺序表的简单功能

一.线性表和顺序表的概念

• 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
  线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

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

二.顺序表的实现

1.动态顺序表的创建

我们先行定义一个初始容量INT_TIAL为 4.

typedef int SLDataList;
#define INT_TIAL 4
typedef struct SeqList
{SLDataList* a;int size;//现存个数int capacity;//容量
}SL;

2.初始化顺序表

先对顺序表进行功能实现前，我们需要先将初始值赋好。

void SeqInit(SL* pr)
{assert(pr);SLDataList* tmp = (SLDataList*)malloc(sizeof(SLDataList) * INT_TIAL);if (tmp == NULL){perror("malloc tmp is\n");return;}else{pr->a = tmp;}pr->size = 0;pr->capacity = INT_TIAL;
}

3.打印顺序表

void SeqPrin(SL* pr)
{assert(pr);for (int i = 0; i < pr->size; i++)printf("%d ", pr->a[i]);printf("\n");
}

4.销毁顺序表

void DisSeq(SL* pr)
{assert(pr);free(pr->a);pr->a = NULL;pr->size = 0;pr->capacity = 0;
}

5.检查容量

对顺序表所有的插入操作前都应该就检查顺序表的容量是否充足，所以应该编写检查容量函数对顺序表进行扩容。

void SeqCheckCapacity(SL* pr)
{assert(pr);if (pr->size == pr->capacity){SLDataList* tmp = (SLDataList*)realloc(pr->a, pr->capacity * sizeof(SLDataList) * 2);if (tmp == NULL){perror("realloc is\n");return;}pr->a = tmp;pr->capacity *= 2;}
}

6.头插 尾插

尾插比较简单，但是进行头插时需要进行类似memmove的操作，进行内存覆盖。

void PushBack(SL* pr)
{assert(pr);if (pr->size+1 > pr->capacity)SeqCheckCapacity(pr);else{int input;printf("输入要插入的数:>");scanf("%d", &input);pr->a[pr->size] = input;pr->size++;}
}void PushFront(SL* pr)
{assert(pr);if (pr->size+1 > pr->capacity)SeqCheckCapacity(pr);else{int input;printf("输入要插入的数:>");scanf("%d", &input);int end = pr->size-1;while (end >= 0){pr->a[end+1] = pr->a[end];end--;}pr->a[0] = input;pr->size++;}}

7.头删 尾删

void PopBack(SL* pr)
{assert(pr);assert(pr->size > 0);pr->size--;
}void PopFront(SL* pr)
{assert(pr);if (pr->size < 1)return;else{int i = 0;while (i < pr->size - 1){pr->a[i] = pr->a[i + 1];i++;}pr->size--;}
}

三.使用下标插入删除

1.删除指定位置

void SeqDel(SL* pr, int pos)
{assert(pr);assert(pos >= 0 && pos < pr->size);int end = pos + 1;while (end < pr->size){pr->a[end - 1] = pr->a[end];end++;}pr->size--;
}

2.向指定位置插入指定数

void SeaSert(SL* pr, int pos, int x)
{assert(pr);assert(pos >= 0 && pos < pr->size);if(pr->size+1>pr->capacity)SeqCheckCapacity(pr);else{int end = pr->size;while (end > pos){pr->a[end] = pr->a[end - 1];end--;}pr->a[pos] = x;pr->size++;}}

最后我们就实现了一个简单的顺序表功能，但是顺序表的缺点也非常明显:

1. 中间头部插入删除数据，需要挪动数据，效率低下
2. 空间不够，扩容。扩容有一定的消耗，其次还可能会有一定空间浪费

在接下来的链表的学习后，我们将会解决这个问题。