文章目录
?
1.线性表
? ? ? ??线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
? ? ? ? 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
? ? ? ? ?什么是逻辑结构？什么是物理结构？逻辑结构是一种人们想象的结构，数据并不一定按照逻辑结构来存储，物理结构是数据在内存中实际存储的结构。
? ? ? ? 比较经典的是链表，链表中的节点一般是由数据域和指针域组成，数据域存放数据，指针域存放指向下一个节点的指针，所以在逻辑上，我们认为它是这样的：
?
? ? ? ? 但是，这只是我们假想的结构，是逻辑结构。在实际存储中，并不是如此，它的物理结构可能是这样：最外层黑色方框表示内存，链表每个节点在内存里面的分布是随机的，并不知道它在哪里，所以说下图是可能的物理结构，因为实际上我们也不知道它的节点是如何分布的。
?
2.顺序表的实现
2.1概念及结构
? ? ? ??顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
? ? ? ? ?顺序表物理地址连续的，所以它实际上是连续的结构，其逻辑上也是连续的。如下图，一段连续的存储单元，每一个格子表示一个存储的数据（并不是一个格子代表一个字节，如果存储的数据是int类型，那么一个格子就表示4个字节）。
2.2顺序表的类型
? ? ? ? 顺序表一般可以分为 静态顺序表 和 动态顺序表，静态顺序表就是存储的元素个数不可以更改的顺序表；动态顺序表就是存储的元素个数可以更改的顺序表，利用动态内存函数。
?静态顺序表
? ? ? ? ?如下定义的就是静态顺序表，使用结构体，结构体首元素是一个数组，可以存储N个 SLDataType类型的数据；结构体第二个元素是表示这个顺序表中存储了多少个数据。比如这个图里面，N是7，SLDataType代表int，说明这个顺序表存储了7个int类型的数据，在图中，实际上存储了5个数据，这时顺序表中的第二个元素——size 的值就是5。
? ? ? ? 在这里，把数据类型typedef成SLDataType是一种非常精妙的设计，如果需要改变顺序表中存储的数据的类型，比如原本存储int类型数据的顺序表，要改成存储char类型的顺序表，只需要将typedef int SLDataType; 改成 typedef char SLDataType;? 就可以了，把 int 改成 char 就行，不需要在程序中一个一个去更改。
?动态顺序表
? ? ? ? ?如下就代表动态顺序表，和静态顺序表的区别是：结构体内部首元素是一个SLDataType类型的指针，而不是数组，此时就可以利用动态内存函数来动态开辟内存，实现存储更多数据的功能；结构体第二个元素代表数组中存储了多少个数据；第三个元素代表顺序表的容量，即顺序表中可以存放多少个数据。当size和capacity相等的时候，就意味着要扩容，即增加顺序表的容量。
? ? ? ? ?比如下图的动态顺序表，当前是开辟了存储8个int类型的数据的空间，实际上只有5个数据，那么size就等于5，capacity就等于8。
? ? ? ? 本文主要讲动态顺序表，因为其实用性比较好。
2.3动态顺序表各个接口的实现
2.3.1接口一揽图
? ? ? ? 接口命名不能随意，要从命名上知道这个接口的作用。在这些函数里，传参涉及到结构体的，都是传结构体的指针，因为只有传指针才可以改变结构体内元素的值。
2.3.2动态顺序表的创建
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* a; //一开始会想用数组，a[N]，但是这是静态的，长度无法确定，用指针，开辟空间，动态比较好
int size; //表示数组中存储了多少个数据
int capacity; //表示数组中可存放多少个数据
}SL;2.3.3初始化?
? ? ? ? 值得注意的是，在这里初始化并不需要开辟一个空间，直接把指针a指向NULL即可，因为realloc函数可以为指向NULL的指针分配空间。详见(97条消息) 【动态内存管理】malloc，calloc，realloc的使用方法以及常见错误_Austerlitzl的博客-CSDN博客
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}2.3.4检查容量
? ? ? ? ?在这里 assert(ps); 是断言的作用：如果括号里的内容（在这里是ps指针）为0，那么就报错，并且显示错误在哪一行，其头文件是<assert.h>。
? ? ? ? 如果顺序表里面，实际存储元素个数和容量相等，意味着要扩容。扩容扩的是ps->a，因为a是指向存储空间的指针。扩容分为两种情况，首先是该顺序表为空，那么分配可以存储4个SLDataType类型数据的空间；如果不为空，那么容量增加一倍。在这里定义newcapacity，即新的容量，用到了三目运算符。
? ? ? ? 至于在这里为什么要用一个新指针tmp来接收realloc的内存，然后再把ps->a指向这块空间，在“初始化”内容中的那个链接中的realloc部分也有详细解释。
void SeqListCheck(SL* ps)
{
//断言
assert(ps);
//检查
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail!\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}2.3.5尾插
? ? ? ? ?有了检查容量这个函数，那么尾插就非常容易了。首先，因为要插入元素，所以要检查容量是否足够。其次，ps->size代表了顺序表里存储了多少个数据，比如存储了5个数据，那么存储的5个元素下标依次是0，1，2，3，4 。下一个要存储的元素的下标就是5，正好是ps->size。所以在ps->size下标插入元素，再把ps->size加1。
void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
ps->a[ps->size] = x;
ps->size++;
}
2.3.5尾删
? ? ? ? 尾删就非常容易，直接ps->size减一就可以。但是要考虑一种情况，如果顺序表里面没有数据了，就无法删除了。所以先判断ps->size，如果大于0，才可以删除。这里不用“=”，是因为ps->size等于0的时候，顺序表里就没有数据了，也就不能删除。
void SeqListPopBack(SL* ps)
{
assert(ps);
if (ps->size > 0)
ps->size--;
}2.3.6头插
? ? ? ? 头插比尾插多一项步骤，就是把所有数据往后移一位，因为是要插入在顺序表的最前面嘛。又因为是后移，所以从最后一个数据开始移动，这样才不会出错。
void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
for (int i = ps->size - 1;i >= 0;i--)
{
ps->a[i+1] = ps->a[i];
}
ps->a[0] = x;
ps->size++;
}2.3.7头删
? ? ? ? 头删，同样的，如果数据没有了，就不执行，直接return。如果还有数据，那么所有数据前移，ps->size减一即可。因为是前移嘛，所以和后移相反，从头开始前移才不会出错。
void SeqListPopFront(SL* ps)
{
assert(ps);
if (ps->size == 0)
{
printf("数据删除完了！");
return;
}
for (int i = 1;i < ps->size;i++)
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}2.3.8寻找指定数据
? ? ? ? 这个比较容易，遍历顺序表的数据，存在就返回其下标，没有则返回-1即可。这里借助flag来寻找，一开始设置flag为0，默认没有，如果找到了，则flag设为1并跳出循环。再判断，flag不为0则找到了，返回下标；否则没有找到，返回-1。
//找到指定数据，找到了返回下标，没找到返回-1
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps);
assert(ps);
int i = 0, flag = 0;
for (i = 0;i < ps->size;i++)
{
if (x == ps->a[i])
{
flag = 1;
break;
}
}
if (flag)
return i;
else
return -1;
}2.3.9 在指定位置插入数据
? ? ? ? 因为实在某个位置插入，所以要先检查容量，然后把该位置及其之后的所有数据向后移动一位，再插入，类似于插入排序那种。
//在指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
for (int i = ps->size-1 ;i >= pos-1;i--)
{
ps->a[i + 1] = ps->a[i];
}
ps->a[pos-1] = x;
ps->size++;
}2.3.10在指定位置删除数据
? ? ? ? 直接从该位置后面的一个数据开始，往后所有数据前移一位，然后size减一。?
//删除pos位置的数据
void SeqListDelete(SL* ps, int pos)
{
assert(ps);
for (int i = pos;i < ps->size;i++)
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}总体而言，顺序表的代码并不难，只是细心的问题，比如插入数据要考虑容量，删除数据要考虑是否还有数据等等。当然本文也可能有一些地方写的不够好，大家也可以多多指正！
3.顺序表的应用
? ? ? ? 用顺序表可以实现例如两个顺序表的归并，两个集合的交、并、差集等等功能。
3.1两个有序顺序表的归并
? ? ? ? 两个有序顺序表归并需设置两个指针，分别指向两个顺序表，然后新开辟一个顺序表来存储归并后的数据。再设计3个int类型的变量，分别记录两个顺序表归并了多少个数据，以及新顺序表内有多少数据。
? ? ? ? 归并过程如图，两个指针分别指向两个顺序表第一个数据，比较大小，小的那个数字被拷贝到新顺序表，同时该顺序表的指针后移一位，然后接着比。
? ? ? ? 整个归并过程直到有一条顺序表被归并完，即count1==p1->size 或者?count2==ps->size。所以循环条件是count1 < ps1->size && count2<ps2->size; 此时还剩下一条顺序表没有归并完，而其剩下的数据都比之前归并过的要大，所以直接按顺序拷贝到新顺序表即可。而由于不知道哪一条顺序表未被归并完，所以两种可能都要写。
? ? ? ? 至于无序顺序表的归并，先排个序然后归并即可。
?
void gb(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a && ps2->a);
SLDataType* p1 = ps1->a;
SLDataType* p2 = ps2->a;
SLDataType* ret[N] = { 0 };
int count = 0;//记录ret存了多少个有效数据
//记录每一个顺序表归并了多少个数据
int count1 = 0;
int count2 = 0;
while (count1 < ps1->size && count2<ps2->size)
{
if (p1[count1] <= p2[count2])
{
ret[count++] = p1[count1++];
}
else if (p1[count1] > p2[count2])
{
ret[count++] = p2[count2++];
}
}
if (count1 == ps1->size)
{
while (count2 < ps2->size)
{
ret[count++] = p2[count2++];
}
}
else if (count2 == ps2->size)
{
while (count1 < ps1->size)
{
ret[count++] = p1[count1++];
}
}
//打印归并
printf("这两个集合归并后的结果是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
}3.2两个集合的交集
? ? ? ? 暴力解法，一个一个比过去，有相同的就拷贝到新顺序表。
void Intersection(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a && ps2->a);
SLDataType ret[N] = {0};
int count = 0;
//暴力解法
for (int i = 0;i < ps1->size;i++)
{
for (int j = 0;j < ps2->size;j++)
{
if (ps1->a[i] == ps2->a[j])
ret[count++] = ps1->a[i];
}
}
//打印交集
printf("这两个集合的交集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return ret;
}3.3两个集合的并集
? ? ? ? 先把一个集合A的元素拷到新顺序表，然后再遍历另一个集合B的元素。让B的元素和新顺序表里的元素比较，如果相同则不拷贝，不同则拷贝到新顺序表。
//并集
void Merge(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a || ps2->a);
SLDataType ret[N] = { 0 };
//把第一个集合的元素全部放进去
for (int i = 0;i < ps1->size;i++)
ret[i] = ps1->a[i];
int count = ps1->size;
//并上第二个集合的元素
for (int i = 0;i < ps2->size;i++)
{
int flag = 1;
for (int j = 0;j < ps1->size;j++)
{
if (ps2->a[i] == ps1->a[j])//有重复的那么就跳过
{
flag = 0;
break;
}
}
if (flag == 1)
ret[count++] = ps2->a[i];
}
//打印并集
printf("这两个集合的并集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return ret;
}3.4两个集合的差集
? ? ? ? 也是暴力解法，对于集合A、B，直接一个元素一个元素比较过去，如果集合B里面有集合A的某个元素，那么该元素就不拷贝到新顺序表，没有则拷贝到新顺序表。
//差集
void Minus(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a || ps2->a);
SLDataType ret[N] = { 0 };
int count = 0;
for (int i = 0;i < ps1->size;i++)
{
int flag = 1;
for (int j = 0;j < ps2->size;j++)
{
if (ps1->a[i] == ps2->a[j])
{
flag = 0;
break;
}
}
if (flag == 1)
{
ret[count++] = ps1->a[i];
}
}
//打印差集
printf("这两个集合的差集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return;
}测试：
? ? ? ? 关于顺序表的知识就到这里啦，下面是以上内容的源代码，可以借鉴一下！ 喜欢的话可以点赞支持！！！
源代码?
头文件SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* a; //一开始会想用数组，a[N]，但是这是静态的，长度无法确定，用指针，开辟空间，动态比较好
int size; //表示数组中存储了多少个数据
int capacity; //表示数组中可存放多少个数据
}SL;
//接口函数，命名风格更着STL走的
//打印
void SeqListPrint(SL* ps);
//初始化
void SeqListInit(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//检查容量是否足够，不够则扩容
void SeqListCheck(SL* ps);
//找到指定数据，找到了返回下标，没找到返回-1
int SeqListFind(SL* ps, SLDataType x);
//在指定位置插入数据
void SeqListInsert(SL* ps,int pos, SLDataType x);
//删除pos位置的数据
void SeqListDelete(SL* ps, int pos);
//归并
void gb(SL* ps1, SL* ps2);
//两个集合的交集
void Intersection(SL* ps1, SL* ps2);
//两个集合的并集
void Merge(SL* ps1, SL* ps2);
//两个集合的差集
void Minus(SL* ps1, SL* ps2);
接口文件SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListPrint(SL* ps)
{
assert(ps);
for (int i = 0;i < ps->size;++i)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListCheck(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail!\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)
{
assert(ps);
if (ps->size > 0)
ps->size--;
}
void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
for (int i = ps->size - 1;i >= 0;i--)
{
ps->a[i+1] = ps->a[i];
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFront(SL* ps)
{
assert(ps);
if (ps->size == 0)
{
printf("数据删除完了！");
return;
}
for (int i = 1;i < ps->size;i++)
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}
//找到指定数据，找到了返回下标，没找到返回-1
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps);
assert(ps);
int i = 0, flag = 0;
for (i = 0;i < ps->size;i++)
{
if (x == ps->a[i])
{
flag = 1;
break;
}
}
if (flag)
return i;
else
return -1;
}
//在指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
SeqListCheck(ps);
for (int i = ps->size-1 ;i >= pos-1;i--)
{
ps->a[i + 1] = ps->a[i];
}
ps->a[pos-1] = x;
ps->size++;
}
//删除pos位置的数据
void SeqListDelete(SL* ps, int pos)
{
assert(ps);
for (int i = pos;i < ps->size;i++)
{
ps->a[i - 1] = ps->a[i];
}
ps->size--;
}
//交集
int cmp(const void* e1, const void* e2)
{
return *(SLDataType*)e1 - *(SLDataType*)e2;
}
void Intersection(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a && ps2->a);
SLDataType ret[N] = {0};
int count = 0;
//暴力解法
for (int i = 0;i < ps1->size;i++)
{
for (int j = 0;j < ps2->size;j++)
{
if (ps1->a[i] == ps2->a[j])
ret[count++] = ps1->a[i];
}
}
//打印交集
printf("这两个集合的交集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return ret;
}
//并集
void Merge(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a || ps2->a);
SLDataType ret[N] = { 0 };
//把第一个集合的元素全部放进去
for (int i = 0;i < ps1->size;i++)
ret[i] = ps1->a[i];
int count = ps1->size;
//并上第二个集合的元素
for (int i = 0;i < ps2->size;i++)
{
int flag = 1;
for (int j = 0;j < ps1->size;j++)
{
if (ps2->a[i] == ps1->a[j])//有重复的那么就跳过
{
flag = 0;
break;
}
}
if (flag == 1)
ret[count++] = ps2->a[i];
}
//打印并集
printf("这两个集合的并集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return ret;
}
//差集
void Minus(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a || ps2->a);
SLDataType ret[N] = { 0 };
int count = 0;
for (int i = 0;i < ps1->size;i++)
{
int flag = 1;
for (int j = 0;j < ps2->size;j++)
{
if (ps1->a[i] == ps2->a[j])
{
flag = 0;
break;
}
}
if (flag == 1)
{
ret[count++] = ps1->a[i];
}
}
//打印差集
printf("这两个集合的差集是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
return;
}
void gb(SL* ps1, SL* ps2)
{
assert(ps1 && ps2);
assert(ps1->a && ps2->a);
SLDataType* p1 = ps1->a;
SLDataType* p2 = ps2->a;
SLDataType* ret[N] = { 0 };
int count = 0;//记录ret存了多少个有效数据
//记录每一个顺序表归并了多少个数据
int count1 = 0;
int count2 = 0;
while (count1 < ps1->size && count2<ps2->size)
{
if (p1[count1] <= p2[count2])
{
ret[count++] = p1[count1++];
}
else if (p1[count1] > p2[count2])
{
ret[count++] = p2[count2++];
}
}
if (count1 == ps1->size)
{
while (count2 < ps2->size)
{
ret[count++] = p2[count2++];
}
}
else if (count2 == ps2->size)
{
while (count1 < ps1->size)
{
ret[count++] = p1[count1++];
}
}
//打印归并
printf("这两个集合归并后的结果是：");
for (int i = 0;i < count;i++)
printf("%d ", ret[i]);
printf("\n");
}测试文件test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListTest()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 6);
SeqListPopBack(&s1);
SeqListPopBack(&s1);
SeqListPrint(&s1);
}
void SeqListTest2()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushFront(&s1, 4);
SeqListPushFront(&s1, 5);
SeqListPushFront(&s1, 6);
SeqListPopBack(&s1);
SeqListPopBack(&s1);
SeqListPopFront(&s1);
SeqListInsert(&s1, 2, 90);
SeqListPrint(&s1);
printf("\n%d",SeqListFind(&s1, 5));
}
void SeqListTest3()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 34);
SeqListPushBack(&s1, 66);
SeqListPushBack(&s1, 8);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 6);
SeqListDelete(&s1, 3);
SeqListPrint(&s1);
}
void SeqListTest4()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 6);
SeqListPrint(&s1);
SL s2;
SeqListInit(&s2);
SeqListPushBack(&s2, 4);
SeqListPushBack(&s2, 5);
SeqListPushBack(&s2, 6);
SeqListPushBack(&s2, 7);
SeqListPushBack(&s2, 8);
SeqListPushBack(&s2, 9);
SeqListPrint(&s2);
gb(&s1, &s2);
Intersection(&s1, &s2);
Merge(&s1, &s2);
Minus(&s1, &s2);
}
int main()
{
//SeqListTest();
//SeqListTest2();
//SeqListTest3();
SeqListTest4();
return 0;
}