数据结构与算法系列之顺序表的实现

顺序表的优缺点：

优点：存储密度高，可以随机存取结点。
缺点：1.长度为定值，中途无法扩充
2.插入删除需要移动结点，效率低

注意事项

1.N个数头删和尾删的时间复杂度是O(N)
N个数头插和尾插的时间复杂度是O(N^2)
//当数组只有一个元素时，移动1次，有两个元素时，移动两次，有三个元素时移动三次… 所以成等差数列经大O表达式为(N^2)

2.柔性数组与顺序表的关系
柔性数组是与结构体变量占一个空间
而顺序表是结构体额外开辟的空间

3.不能用realloc进行缩容
//缩容之后，可能缩容的部分会被使用，在进行扩容的话，不能回到原样

4.free()
//不能在动态数组中间进行释放，必须开辟多大空间，就一次释放完

顺序表

柔性数组

test.c（动态顺序表）

int main()
{SL s;SLInit(&s);int option = 0;while (option != -1){menu();scanf("%d", &option);if (option == 1){printf("请依次输入要尾插的数据");int x = 0;while (x != -1){scanf("%d", &x);SLPushBack(&s, x);}}else if (option == 7){SLPrint(&s);}}return 0; 
}

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define INT_CAPACITY 4
typedef int  SLDataType;typedef struct SepList
{SLDataType* a;int size;int capacity;
}SL;void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);void SLPushBack(SL* ps ,SLDataType * x );//尾插
void SLPopBack(SL* ps);//尾删
void SLPushFront(SL* ps,SLDataType * x );//头插
void SLPopFront(SL* ps);//头删
void SLCheckCapacity(SL* ps);//扩容void SLInsert(SL* ps, int pos, SLDataType x);//pos位置插入
void SLErase(SL* ps, int pos);//pos位置删除
int  SLFind(SL* ps, SLDataType x);

SeqList.c

#include "SeqList.h"
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){		//realloc 可能会原地扩容 也可能异地扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity* 2));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}}void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)*  INT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INT_CAPACITY;
}
void SLDestory(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
void SLPushBack(SL* ps, SLDataType  x)
{assert(ps);SLCheckCapacity(ps);//扩容ps->a[ps->size++] = x;//SLInsert(ps,ps->size, x)尾插
}
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);/*if (ps->size == 0){return;}*/ps->size--;//尾删SLErase(ps, ps->size-1);
}
void SLPushFront(SL* ps ,SLDataType x)
{assert(ps);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 SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//可以等于size，相当于尾插SLCheckCapacity(ps);int end = ps->size-1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin-1] = ps->a[begin];begin++;}ps->size--; 
}int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;}

各接口函数功能详解

void SLInit(SL* ps);//定义

assert(ps);//进行assert判断ps这个结构体指针是否存在ps->a = (SLDataType*)malloc(sizeof(SLDataType)*  INT_CAPACITY);//使用malloc函数进行扩容，必须用free()释放 if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;初始化ps->capacity = INT_CAPACITY;

void SLDestory(SL* ps);

{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

void SLPrint(SL* ps);

assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}

void SLPushBack(SL* ps ,SLDataType * x );

{assert(ps);SLCheckCapacity(ps);//判断是否扩容//扩容ps->a[ps->size++] = x;//SLInsert(ps,ps->size, x)尾插
}

void SLPopBack(SL* ps);

    assert(ps);assert(ps->size > 0);因为尾删判断数组是否有元素存在，如果没有元素则不可以尾删/*if (ps->size == 0){return;}*/ps->size--;//尾删SLErase(ps, ps->size-1);

void SLPushFront(SL* ps,SLDataType * x );

{assert(ps);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 SLPopFront(SL* ps);

{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

void SLCheckCapacity(SL* ps);

	
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){		//realloc所以扩容成功后，可能会原地扩容 也可能异地扩容，所以用ps->a = tmp来重新接收SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity* 2));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}}

void SLInsert(SL* ps, int pos, SLDataType x);//pos位置插入

//可用于头插和尾插

assert(ps);assert(pos >= 0 && pos <= ps->size);//可以等于size，相当于尾插SLCheckCapacity(ps);int end = ps->size-1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;

void SLErase(SL* ps, int pos);//pos位置删除

//可用于头删和尾删

assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin-1] = ps->a[begin];begin++;}ps->size--; 

int SLFind(SL* ps, SLDataType x);

assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;