文章目录
一、线性表
二、顺序表
2.1 概念和结构
2.2 分类
2.2.1 静态顺序表
2.2.2 动态顺序表
2.3动态顺序表的实现
1.SeqList.h
2.SeqList.c
打印顺序表
初始化
销毁
增容
尾插
头插
在指定位置之前插入数据
尾删
头删
在指定位置删除数据
3.test.c
一、线性表
- 逻辑结构（认为想象出来的数据的组织形式）：都是线性的
- 物理结构（数据在内存上的存储形式）：不一定是线性的
二、顺序表
2.1 概念和结构
- 顺序表是对数组进行封装：结构体
- 定义已经知道数组的大小： int arr【3】= {1，2，3}；
- 定义未知道数组的大小： int*arr；
2.2 分类
2.2.1 静态顺序表
上图中可以发现我们重新定义了 typedef int SLDataType，为什么？
比如当我们在测试代码中有 100000行代码，1000+会定义整型变量 int，当要把这 1000+ 的代码部分改成 char 类型时，如果逐个将这些代码找出一句句修改会非常麻烦而且工作量巨大；
而当 typedef int SLDataType之后 ，我们只需将其改成 typedef char SLDataType ，遍能一键替换为 char 或者想要修改的位置。
2.2.2 动态顺序表
2.3动态顺序表的实现
(注意：1.当我们每实现一个方法之后须测试一下，切记写完所有方法才测试，避免出现差错；
2.在调用过程中分清传值和传址的区别；
传值：形参是实参的值的拷贝，实参和形参指向的是两块不同的地址，但保存的数据是一样的
传址：形参指向的是实参指向的地址)
1.SeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义动态顺序表结构
typedef int SLDatatype;typedef struct SeqList {SLDatatype* arr;int capacity; //空间大小int size; //有效数据个数
}SL;//typedef struct SeqList 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, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);2.SeqList.c
-
打印顺序表
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}-
初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}-
销毁
void SLDestory(SL* ps)
{if (ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}-
增容
当size == capacity 时，说明顺序表满了，空间不足，先增容，再插入；
增容一般是成倍数的增加（增容的操作本身就有一定的程序性能的消耗，若频繁的增容会导致程序效率底下），所以 ”一次增容一个就没有空间浪费“ 这种说法是错误的。
增容分两种情况： 1.连续空间足够，直接扩容
2.连续空间不够，1）重新找一块地址，分配足够的内存
2）拷贝数据到新的地址
3）销毁旧地址
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size = ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int newCapacity = ps->arr == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp = NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}-
尾插
空间充足：将数据插入 size 指向的位置，size++；
void SLPushBack(SL* ps, SLDatatype x)
{assert(ps);//等价于assert(ps != NULL)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];}//将数据插入下标为0的位置ps->arr[0] = x;
}-
在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);// 头插 尾插 //pos及以后的数据整体向后移动一位,从后往前移，与头插的方法类似for (int i =ps->size ; i>pos; i--){ps->arr[i] = ps->arr[i - 1];}//将数据插入下标为pos的位置ps->arr[pos] = x;ps->size++; //不要忘记这一步
}-
尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表为空，不可删除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 SLDelete(SL* ps, int pos)
{assert(ps);assert(ps->size);//顺序表为空，不可删除assert(pos >= 0 && pos < ps->size);// 头删 尾删 //pos及以后的数据整体向前移动一位,从前往后移，与SLInsert的方法类似for (int i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}3.test.c
#include "SeqList.h"void SLtest01()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 10);SLPushBack(&s, 11);SLPushBack(&s, 12);printf("尾插后的数据：");SLPrint(&s);printf("头插后的数据：");SLPushFront(&s, 4);SLPrint(&s);printf("在下标为2的位置插入9后的数据：");SLInsert(&s, 9, 2);SLPrint(&s);printf("尾删后的数据：");SLPopBack(&s);SLPrint(&s);printf("头插后的数据：");SLPopFront(&s);SLPrint(&s);printf("删除下标为3的数据：");SLDelete(&s, 3);SLPrint(&s);SLDestroy(&s);
}int main()
{SLtest01(); return 0;
}
