文章目录
- 1.顺序表的概念
- 线性表
- 物理结构
- 逻辑结构
- 2.顺序表的分类
- 2.1静态顺序表
- 2.2动态顺序表
- 3.顺序表接口的实现
- 头文件(SQList.h)如下
- 源文件
- 初始化顺序表
- 销毁顺序表
- 插入
- 扩容
- 尾插
- 头插
- 封装扩容函数
- 删除
- 尾删
- 头删
- 查找元素
- 在指定位置前插入数据
- 情况一(指定的位置不是首元素)
- 情况二(指定的位置是首元素)
- 删除指定位置
- 打印顺序表
- 完整代码
- SQList.h
- SQList.c
- test.c (测试部分)
- 结语
1.顺序表的概念
在认识顺序表之前,让我们先认识下线性表。
线性表
线性表是由n个相同类型的数据所组成的有限序列,线性表是一种在现实里被广泛使用的,常见的线性表有:顺序表、链表、栈、队列等等。
线性表在逻辑结构一定连续,但在物理结构中并不一定是连续的。
物理结构
物理结构就是数据存储于内存的结构,就那数组来说,数组开辟的空间是连续的,第x个数据的空间的下一块空间就是第x+1个数据,这就是物理结构连续。
如果我在设计表的时候,专门设计一个指针用来存放下一个数据的地址。
如下图:
第x数据和第x+1数据的空间并不是连续的,而是被指针位连接的,是像一个绳子,每个数据位就相当于绳结,指针位相当于绳结后面的绳子,这就是物理结构不连续。
逻辑结构
逻辑结构是我们自己抽象出来的,对于线性表来说,它的逻辑结构我们就可以把他想象成直线的线性结构,就拿上面物理结构不连续的例子来说,尽管它第一个数据和第二个数据在空间上并不是连续,但是我们可以把它们想象是连续的。
就类似于下图:
顺序表是线性表的一种,顺序表的特点就是物理层面和逻辑层面都连续,数据与数据之间都是相邻的
顺序表的底层是数组!!!
2.顺序表的分类
顺序表可以分为静态和动态两种
2.1静态顺序表
在创建之前将大小固定,这样虽然很简单,但是有局限性;如果给定的数据多了,就无法完整的存储数据;如果给定的数据少了,就会造成空间的浪费
typedef int SQLDATATYPE;
typedef struct SQList
{SQLDATATYPE a[100];//给定了100个数据,后续无法改动大小int size;//当前数据的个数
}SQList;
哪有什么方法可以解决呢?
2.2动态顺序表
内存大小是不固定的,需要使用时再进行动态开辟,如果后面有多的数据要存储,就可以使用realloc
函数来进行增容,所以就更加的灵活
typedef int SQLDATATYPE;
typedef struct SQList
{SQLDATATYPE* a;int size;//当前数据的个数int capacity;//当前顺序表的容量
}SQList;
我们本章讲解的是动态顺序表
3.顺序表接口的实现
首先我们需要一个头文件和一个源文件;
头文件是用来声明顺序表函数的,源文件是用来实现顺序表函数的实现
头文件(SQList.h)如下
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//typedef int SQLDATATYPE;
//typedef struct SQList
//{
// SQLDATATYPE a[100];//给定了100个数据,后续无法改动大小
// int size;//当前数据的个数
//}SQList;typedef int SQLDATATYPE;
typedef struct SQList
{SQLDATATYPE* a;int size;//当前数据的个数int capacity;//当前顺序表的容量
}SQList;//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);//打印顺序表
void SQListPrint(SQList* plist);
源文件
记住要包含头文件
#include"SQList.h"
初始化顺序表
//初始化顺序表
void SQListInit(SQList* plist)
{plist->a = NULL;//其实也可以在初始化的时候就给a开辟空间(看个人喜好)plist->size = plist->capacity = 0;
}
一定要传址调用,这样才能真正的改变到顺序表
销毁顺序表
//销毁顺序表
void SQListDestroy(SQList* plist)
{assert(plist);free(plist->a);plist->a = NULL;//这一步是为了让a不会野指针//也可以避免a被重复释放(free函数不会对NULL进行操作)plist->size = plist->capacity = 0;
}
插入
插入就意味这内容的增加,就必然会导致内容空间的不足,这时候我们就需要进行扩容。
扩容
我们在插入之前要看,内部是否还有空间可以让我们插入,当size==capacity时,就代表表内已经填满数据了,我们就需要进行扩容
扩容用到的是realloc
函数,我们扩容是默认是以两倍来扩容
尾插
void SQListPushBack(SQList* plist, SQLDATATYPE x)
{assert(plist);//检查plist是否为空指针if (plist->size == plist->capacity)//判断空间是否满了{int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式//如果plist->capacity==0为真,将4赋给NewCapacity;反之则赋值2*plist->capacitySQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));if (tmp == NULL){perror("realloc fail");exit(1);}plist->a = tmp;//将调整的空间赋给顺序表plist->capacity = NewCapacity;//调整容量}plist->a[plist->size] = x;plist->size++;
}
头插
头插我们就会遇到一个问题。
我们不能直接在顺序表的头部进行插入,这样会覆盖掉顺序表原来的数据,会造成数据的丢失。
解决方法也很简单
我们将整个顺序表往后挪动一位,让下标为x的数据等于下标为x-1的数据。
因为我们size处是一个待插入数据的空间,所以这样并不会造成数据的丢失。
代码如下:
void SQListPushFront(SQList* plist, SQLDATATYPE x)
{assert(plist);//检查plist是否为空指针if (plist->size == plist->capacity){int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式//如果plist->capacity==0为真,将4赋给NewCapacity;反之则赋值2*plist->capacitySQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));if (tmp == NULL){perror("realloc fail");exit(1);}plist->a = tmp;//将调整的空间赋给顺序表plist->capacity = NewCapacity;//调整容量}for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位{plist->a[i] = plist->a[i - 1];}plist->a[0] = x;plist->size++;
}
封装扩容函数
这时候我们看到,尾插函数和头插函数有一段代码是一模一样的,我们接下来还有个指定位置前的插入,它也是可能会进行扩容函数的,如果这三个函数都使用一段相同的代码,就会显得代码很冗余。
我们就可以将这段代码抽离出来,封装成一个独立的函数,需要扩容的时候调用该函数就可以了。
代码如下:
//扩容函数
//因为扩容函数是在源代码运行的,所以可以不用在头文件进行声明(当然你也可以在头文件进行声明 看个人喜好)
void SQListAdd(SQList* plist)
{int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式//如果plist->capacity==0为真,将4赋给NewCapacity;反之则赋值2*plist->capacitySQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));if (tmp == NULL){perror("realloc fail");exit(1);}plist->a = tmp;//将调整的空间赋给顺序表plist->capacity = NewCapacity;//调整容量
}
删除
尾删
//删除(尾部)
void SQListPopBack(SQList* plist)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢?plist->size--;//这里很简单,就是将他的size进行--//size指向的是尾数据的下一块空间,也就是待插入的空间//我们--size,就相当于把尾数据的空间变成了待插入的空间//我们新增数据的时候,会把原来的值覆盖掉的
}
头删
这里有个问题
因为是删除头元素,我们不能直接将size–。
解决方法也很简单
将整个顺序表往前挪动一位,原理和头插的解决方法是类似的。
代码如下:
//删除(头部)
void SQListPopFront(SQList* plist)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢?for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位{plist->a[i] = plist->a[i + 1];}plist->size--;
}
查找元素
//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{assert(plist);int i = 0;while (i < plist->size)//size-1处就是最后一个数据{if (plist->a[i] == x)//找到了return i;//返回的是下标i++;}//i=size 跳出循环//找不到return EOF;//EOF(-1)
}
在指定位置前插入数据
情况一(指定的位置不是首元素)
我们就将指定位置及以后的数据往后挪一位;,再将数据插入到指定位置的下标。
情况二(指定的位置是首元素)
那么是首元素了,我们在首元素前进行插入,这是什么?
这不就是头插吗
所以我们可以直接调用我们已经写好的头插函数
//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{assert(plist);if (plist->size == plist->capacity){SQListAdd(plist);//这里就直接调用了增容函数}//这里有两种情况//第一种当pst不是首元素if (pst != 0){for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位{plist->a[i] = plist->a[i - 1];}plist->a[pst] = x;}//第二种:当pst是首元素//那么是首元素了,我们在首元素前进行插入,这是什么?//这不就是头插吗//所以我们可以直接调用我们已经写好的头插函数else{SQListPushFront(plist, x);}
}
删除指定位置
我们只要将指定位置后面的数据往前挪动一位
//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位{plist->a[i] = plist->a[i + 1];}plist->size--;
}
打印顺序表
//打印顺序表
void SQListPrint(SQList* plist)
{assert(plist);if (plist->size == 0)printf(NULL);for (int i = 0; i < plist->size; i++){printf("%d ", plist->a[i]);}printf("\n");
}
完整代码
SQList.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//typedef int SQLDATATYPE;
//typedef struct SQList
//{
// SQLDATATYPE a[100];//给定了100个数据,后续无法改动大小
// int size;//当前数据的个数
//}SQList;typedef int SQLDATATYPE;
typedef struct SQList
{SQLDATATYPE* a;int size;//当前数据的个数int capacity;//当前顺序表的容量
}SQList;//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);//打印顺序表
void SQListPrint(SQList* plist);
SQList.c
#include"SQList.h"//初始化顺序表
void SQListInit(SQList* plist)
{plist->a = NULL;//其实也可以在初始化的时候就给a开辟空间(看个人喜好)plist->size = plist->capacity = 0;
}//销毁顺序表
void SQListDestroy(SQList* plist)
{assert(plist);free(plist->a);plist->a = NULL;//这一步是为了让a不会野指针//也可以避免a被重复释放(free函数不会对NULL进行操作)plist->size = plist->capacity = 0;
}//扩容函数
//因为扩容函数是在源代码运行的,所以可以不用在头文件进行声明(当然你也可以在头文件进行声明 看个人喜好)
void SQListAdd(SQList* plist)
{int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式//如果plist->capacity==0为真,将4赋给NewCapacity;反之则赋值2*plist->capacitySQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));if (tmp == NULL){perror("realloc fail");exit(1);}plist->a = tmp;//将调整的空间赋给顺序表plist->capacity = NewCapacity;//调整容量
}//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x)
{assert(plist);//检查plist是否为空指针if (plist->size == plist->capacity){SQListAdd(plist);}plist->a[plist->size] = x;plist->size++;
}//删除(尾部)
void SQListPopBack(SQList* plist)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢?plist->size--;//这里很简单,就是将他的size进行--//size指向的是尾数据的下一块空间,也就是待插入的空间//我们--size,就相当于把尾数据的空间变成了待插入的空间//我们新增数据的时候,会把原来的值覆盖掉的
}//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x)
{assert(plist);//检查plist是否为空指针if (plist->size == plist->capacity){SQListAdd(plist);}for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位{plist->a[i] = plist->a[i - 1];}plist->a[0] = x;plist->size++;
}//删除(头部)
void SQListPopFront(SQList* plist)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢?for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位{plist->a[i] = plist->a[i + 1];}plist->size--;
}//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{assert(plist);int i = 0;while (i < plist->size)//size-1处就是最后一个数据{if (plist->a[i] == x)//找到了return i;//返回的是下标i++;}//i=size 跳出循环//找不到return EOF;//EOF(-1)
}//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{assert(plist);if (plist->size == plist->capacity){SQListAdd(plist);}//这里有两种情况//第一种当pst不是首元素if (pst != 0){for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位{plist->a[i] = plist->a[i - 1];}plist->a[pst] = x;}//第二种:当pst是首元素//那么是首元素了,我们在首元素前进行插入,这是什么?//这不就是头插吗//所以我们可以直接调用我们已经写好的头插函数else{SQListPushFront(plist, x);}
}//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{assert(plist);assert(plist->size > 0);//如果为0了,我还删什么呢for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位{plist->a[i] = plist->a[i + 1];}plist->size--;
}//打印顺序表
void SQListPrint(SQList* plist)
{assert(plist);if (plist->size == 0)printf(NULL);for (int i = 0; i < plist->size; i++){printf("%d ", plist->a[i]);}printf("\n");
}
test.c (测试部分)
#include"SQList.h"void TestSQL()
{SQList sq;SQListInit(&sq);SQListPushBack(&sq, 1);SQListPushBack(&sq, 2);SQListPushBack(&sq, 3);SQListPushBack(&sq, 4);SQListPushBack(&sq, 5);SQListPushBack(&sq, 6);SQListPushFront(&sq, 0);SQListPopBack(&sq);SQListPushBack(&sq, 128);//SQListPrint(&sq);//SQListPopFront(&sq);//SQListPrint(&sq);int flag = SQListFind(&sq, 3);//if (flag != EOF)//{// printf("找到了 下标为%d\n", flag);//}//else//{// printf("找不到\n");//}SQListInsect(&sq, flag, 255);//SQListDelete(&sq, flag);SQListPrint(&sq);SQListDestroy(&sq);
}int main()
{TestSQL();return 0;
}
结语
最后感谢您能阅读完此片文章,如果有任何建议或纠正欢迎在评论区留言。
如果您认为这篇文章对您有所收获,点一个小小的赞就是我创作的巨大动力,谢谢!!!