数据结构——顺序表专题

1. 数据结构的相关概念

什么是数据结构

数据结构是由“数据”和“结构”两词组合而来的。

数据：常见的数值、网页中肉眼可见的信息，这些都是数据。

结构：当我们想要使用大量同一类型的数据时，通过手动定义大量的独立的遍历对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

1. 能够存储数据（顺序表，链表等结构）
2. 存储的数据能够方便查找

为什么需要数据结构？

在程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构，能够有效将数据组织和管理在一起。按照我们的方式任意对书记进行增删改查等操作。

最基础的数据结构：数组

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：最基础的数据结构能够提供已经不能完全满足复杂算法实现。

2. 顺序表

顺序表的概念及结构

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

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表早无力上存储时，通常是以数组和链式结构的形式存储。

顺序表分类

顺序表和数组的区别

顺序表的底层结构是数组，对数组的分装，实现了常用的增删改查等接口

静态顺序表

概念：使用定长数组存储元素

静态顺序表：给定数组的长度，若不够，会导致后续的数据保存失败；给多了，会导致空间大量的浪费

数据丢失----非常严重的技术事故！！

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表

3. 动态顺序表的实现

准备工作

typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;

顺序表的初始化

//初始化和销毁
void SLInit(SL* ps)
{ ps->arr = NULL;ps->size = ps->capacity = 0;
}

顺序表的扩容

实现动态顺序表，当size和capacity相等时，有2中情况，第一种：一开始为0的时候，第二种情况是：当空间不足时
若是第一种情况就给4个字节的空间，若是第二种情况使用二倍思想来处理

oid SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc");exit(1);}//说明扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}

尾插

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{//断言//assert(ps != NULL);assert(ps);//空间不够，扩容SLCheckCapacity(ps);//空间足够，直接插入//空间没有满，直接进行尾插ps->arr[ps->size] = x;ps->size++;}

头插

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧数据往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=pa->arr[0]}ps->arr[0] = x;ps->size++;}

尾删

void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空//ps->arr[ps->size - 1] = -1;ps->size--;
}

头删

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//不为空执行挪动操作for (int i = 0;i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

指定位置插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位，pos空出来for (int i=ps->size;i>pos;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

指定位置删除数据

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i=pos;i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]}ps->size--;
}

在顺序表中查找

int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

销毁

void SLDestroy(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

4. 全部完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>//静态顺序表
//#define N 100
//typedef int SLDataType;
//struct Seqlist
//{
//	SLDataType a[N];
//	int size;
//};typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性//顺序表的插入
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插//顺序表的删除
void SLPopBack(SL* ps);
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.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"//初始化和销毁
void SLInit(SL* ps)
{ ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc");exit(1);}//说明扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{//断言//assert(ps != NULL);assert(ps);//空间不够，扩容SLCheckCapacity(ps);//空间足够，直接插入//空间没有满，直接进行尾插ps->arr[ps->size] = x;ps->size++;}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧数据往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=pa->arr[0]}ps->arr[0] = x;ps->size++;}//顺序表的删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空//ps->arr[ps->size - 1] = -1;ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//不为空执行挪动操作for (int i = 0;i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//指定位置插入数据
//删除指定位置的数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位，pos空出来for (int i=ps->size;i>pos;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i=pos;i<ps->size-1;i++){ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]}ps->size--;
}//在顺序表中查找x
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}void SLDestroy(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"void s1Test1()
{SL s1;SLInit(&s1);//测试尾插SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);/*SLPushBack(&s1, 9);SLPrint(&s1);*///测试头插SLPushFront(&s1, 5);SLPushFront(&s1, 6);SLPushFront(&s1, 7);SLPrint(&s1);//测试尾删SLPopBack(&s1);SLPrint(&s1);SLPopFront(&s1);SLPrint(&s1);//指定位置插入数据SLInsert(&s1, 0, 100);SLPrint(&s1);//删除指定位置的数据SLErase(&s1, 0);SLPrint(&s1);
}void s1Test2()
{SL s1;SLInit(&s1);//测试尾插SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);//测试查找int ret = SLFind(&s1, 3);if (ret <0){printf("数据不存在，查找失败");}else {printf("数据找到了，在%d位置", ret);}
}void s1Test3()
{SL s1;SLInit(&s1);SLDestroy(&s1);
}int main()
{void s1Test3();//s1Test2();//s1Test1();return 0;
}