C语言数据结构之顺序表

目录

1.线性表

2.顺序表

2.1.静态顺序表

2.2.动态顺序表

2.2.1.初始化

2.2.2.清空顺序表

2.2.3.扩容＋尾插

2.2.4.尾出函数

2.2.5.头插函数

2.2.6.头出函数

2.2.7.在中间位置插入

2.2.8.删除中间位置数据

2.2.9.查找函数

2.2.10.总结

3.OJ例题

3.1.合并两个有序数组

3.2.删除有序数组中的重复项

3.3.移除数组元素

4.代码

4.1 SeqList.h文件

4.2.SeqList.c文件

---

1.线性表

        线性表式n个具有相同特性的数据元素的有限序列。应用广泛，常见的有：顺序表、链表、栈、队列、字符串……。

        线性性表在逻辑上是一条连续的条线；但在内存中是不一定是连续存储的，在存储的时候通常以数组和链式形式存储。

2.顺序表

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般使用数组存储。在数组的基础上完成数据的增删查改。

2.1.静态顺序表

#define N 10
typedef  int SLDataType;//此时定义的存储数据类型是int，也可以定义结构体
//等等数据类型 int 也可以换成 double char 
//静态顺序表  内存空间固定，申请空间少了，不够用，多了用不完
struct SeqList
{SLDataType a[N];  //定长数组int size;         //有效数据个数
};

        静态的通讯录和其相似，但是通讯录存储的数据类型是一种结构体；静态的特点是：开辟空间完全依靠经验，后续无法自主调整。

2.2.动态顺序表

typedef  int SLDataType;
//动态顺序表 按需申请空间
struct SeqList
{SLDataType* a;  //开始存储的起始地址，可以看作为数组名int size;      //有效数据个数int capacity;  //空间容量
};

        动态顺序表可以自主调整空间大小，空间不足的情况下，可以realloc向堆区申请内存空间，当然动态顺序表初始换使用malloc函数申请空间。

2.2.1.初始化

       最开始的初始化思想是，所空间容量和有效数据数置为0，指针置为NULL（空指针）。

void SeqInit(SL* pc)
{assert(pc);pc->a = NULL;pc->size = 0;pc->capacity = 0;printf("初始化成功");
}

       但是动态顺序表必须自带点儿空间，使用malloc函数向内存申请空间。INIT_CAPACITY暂定为3。

void SeqInit2(SL* pc)//形参是实参的拷贝；形参的修改无法作用在实参上，因此要用地址传值
{		assert(pc);			 //其SL结构体数个整体，(SLDataType*)pc = (SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);if (pc->a == NULL){perror("malloc fail");return;}pc->capacity = INIT_CAPACITY;//使用#define 定义任意大小 pc->size = 0;printf("初始化成功");
}

2.2.2.清空顺序表

        在顺序表使用完，需要将开辟的空间释放，返还给操作系统，使用free函数释放申请的空间；我们申请的内存空间只有使用权。

void SLDestroy(SL* pc)
{assert(pc);free(pc->a);//开的空间必须整体释放，不能一块儿一块释放pc->a = NULL;pc->size = pc->capacity = 0;if(pc->a == NULL)printf("清除成功");
}

free函数在使用时出现问题

• 指针是野指针，不指向任何空间。
• fres释放指针不是起始位置指针，如果对开辟的指针进行处理之后
• pc->a[i]数组指向的空间越界,申请的空间不足且不扩容；
• size的大小超过了capacity（容量）就是越界，若是size越界了，说明空间开辟少了。

2.2.3.扩容＋尾插

        在输入数据之前，要先检查顺序表的容量是否已满，若空间满了就使用realloc扩容；若没有满就输入数据就可以。这里每次扩容将会把空间扩大二倍。

        将X放入下面数据的尾部就是尾插

void SLPushBack(SL* pc, SLDataType x)
{//扩容if (pc->capacity == pc->size){SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*INIT_CAPACITY * 2);//扩充二倍if (pc->a == NULL){perror("realloc fail");return ;}pc->a = tmp；pc->capacity *= 2;printf("扩容成功\n");}pc->a[pc->size++] = x;
}

        realloc函数的使用如果没有 pc->a = tmp；可能会出错，realloc只会申请连续函数的使用权，若后续的内存不够，realloc将会重新申请一块儿内存，然后将新的地址赋给tmp，那么pc->a指向的位置，再次访问就是非法访问了；若是直接开辟，则问题还不明显，若是异地开辟，则会直接报错。

2.2.4.尾出函数

        尾出函数较为简单，只需要将size（有效数据个数）减去1就可以了；当然在进行删除之前就要判断顺序表中书否有数据（size是否为0）；

//尾出
void SLPopBack(SL* pc)
{assert(pc->size > 0);//方式1报错if (pc->size == 0)   //方式2return;pc->size--;
}

        在使用方式1：assert函数判断size是否大于0；如果大于0为真，执行下一步；若小于0为假，报错，而且会有具体的位置。assert函数会让程序维护更加简单。

若使用方式二报错，程序运行窗口会闪烁，一会儿会自动结束进程。

2.2.5.头插函数

        头插函数在输入数据之前，要先检测是否要进行扩容，因此可以将扩容另写一个函数，再复用扩容函数；然后对位于最后的数据开始依次向后一个位置挪动。

void SLPushFront(SL* pc, SLDataType x)
{assert(pc);//检查空间SLCheckCapacity(pc);//挪动数据int end = pc->size - 1;while (end >= 0){pc->a[end + 1] = pc->a[end];end--;}//赋值pc->a[0] = x;//有效数据+1pc->size++;
}

2.2.6.头出函数

        将第二个数据覆盖第一个数据，第三个数据覆盖第二个数据，然后有效数据减去一。

void SLPopFront(SL* pc)
{assert(pc);assert(pc->size > 0);int i = 0;for (i = 0; i < pc->size; i++){pc->a[i] = pc->a[i + 1];}pc->size--;
}

2.2.7.在中间位置插入

        中间位置的插入就是确定位置pos在哪里，确定pos变量是否合规；判断是否有多余的空间；然后将最后一个数据向后再移动一个位置，依次移动。

//在某个位置插入
void SLInsert(SL* pc, int pos, SLDataType x)
{//判断指针和位置是否有效assert(pc);assert(pos >= 0 && pos <= pc->size);//判断是否扩容SLCheckCapacity(pc);//挪动数据int end = pc->size - 1;while (pos <= end){pc->a[end + 1] = pc->a[end];end--;}//插入数据pc->a[pos] = x;pc->size++;
}

我们可以根据这个函数对尾插和头插函数进行修改，复用上述函数。

头插函数

头插函数的位置就是0 pc->a[0].

void SLPushFront(SL* pc, SLDataType x)
{assert(pc);//检查空间SLCheckCapacity(pc);//挪动数据SLInsert(pc, 0, x);
}

尾插函数

void SLPushBack(SL* pc, SLDataType x)
{assert(pc);SLInsert(pc, pc->size, x);	
}

2.2.8.删除中间位置数据

//删除某一个位置的数据
void SLErase(SL* pc, int pos)
{assert(pc);assert(pos >= 0 && pos < pc->size);int begin = pos + 1;while (begin < pc->size){pc->a[begin-1] = pc->a[begin];begin++;}pc->size--;
}

确定位置后，我们将其后面的数据依次递进，程序中的pos是数组的下标，从0开始。

当然上面的函数也可以复用

头出函数

void SLPopFront(SL* pc)
{SLErase(pc,0);
}

尾出函数

void SLPopBack(SL* pc)
{SLErase(pc, pc->size-1);
}

2.2.9.查找函数

将顺序表中的元素遍历一边，就可以找到了。

//查找函数
int SLFind(SL* pc, SLDataType x)
{assert(pc);int i = 0;for (i = 0; i < pc->size; i++){if (pc->a[i] == x){return i + 1;}}return -1;
}

2.2.10.总结

        在插入和删除一组数据的情况下，按照最坏的时间复杂度来说，尾插和尾出的时间复杂度是O(1)；头插和头出的时间复杂度是O(N);中间插入和删除的时间复杂度也是O(N);因此在处理数据的时候，在好用的还是的尾插和尾出。

3.OJ例题

3.1.合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{int end1 = m - 1;int end2 = n -1;int dst = m + n -1;while(end1 >= 0&& end2 >= 0){if(nums1[end1]>nums2[end2]){nums1[dst--]=nums1[end1--];}else{nums1[dst--]=nums2[end2--];}}while(end2>=0){nums1[dst--]=nums2[end2--];}
}

题解思路：

        目标将两个数组合并成有序的数组，比较大小，nums1中有效数有m个元素，而长度为m+n个，足够容下nums2；数组nums1中的前面不能覆盖，所以就倒叙排列了。

3.2.删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

int removeDuplicates(int* nums, int numsSize) 
{int src = 1;int dst = 0;while(src < numsSize){if(nums[src] == nums[dst]){src++;}else{dst++;nums[dst] = nums[src++];}}return dst+1;
}

        使用双指针，这里的双指针指的是两个下边；dst为目标指针，src为递进指针，src中的数组复制到src中；首先判断两个指针指向的数据是否一样，不一样复制；注意的是dst要增加一位；因为原来指向的位置不一样的；一样的话，src指针++，寻找下一个不一样的数据。

3.3.移除数组元素

27. 移除元素 - 力扣（LeetCode）

int removeElement(int* nums, int numsSize, int val) 
{int src = 0;int dst = 0;while(src < numsSize){if(nums[src] != val){nums[dst++] = nums[src++];}else{src++;}}return dst;
}

        使用双指针，从数组起始位置开始，和原来项相等便src++，dst保持不动，不相等的时候直接将val所占据的位置覆盖。

4.代码

4.1 SeqList.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//#define N 10
//typedef  int SLDataType;//此时定义的存储数据类型是int，也可以定义结构体
等等数据类型 int 也可以换成 double char 
静态顺序表  内存空间固定，申请空间少了，不够用，多了用不完
//struct SeqList
//{
//	SLDataType a[N];  //定长数组
//	int size;         //有效数据个数
//};
#define INIT_CAPACITY 3
typedef  int SLDataType;
//动态数组
struct SeqList
{SLDataType* a;  //开始存储的起始地址，可以看作为数组名int size;      //有效数据个数int capacity;  //空间容量
};
typedef struct SeqList SL;
//初始化
void SeqInit(SL* pc); 
//扩容+初始化
void SeqInit2(SL* pc);
//清空函数
void SLDestroy(SL* pc);
//尾插函数
void SLPushBack(SL* pc, SLDataType x);
//输出函数
void SLPrint(SL* pc);
//尾出函数
void SLPopBack(SL* pc);
//扩容函数
void SLCheckCapacity(SL* pc);
//前插函数
void SLPushFront(SL* pc, SLDataType x);
//头删函数
void SLPopFront(SL* pc);
//在某个位置插入
void SLInsert(SL* pc, int pos, SLDataType x);
//删除某一个位置的数据
void SLErase(SL* pc, int pos);
//查找函数
int SLFind(SL* pc, SLDataType x);

4.2.SeqList.c文件

#include "SeqList.h"//初始化
void SeqInit(SL* pc)
{pc->a = NULL;pc->size = 0;pc->capacity = 0;printf("初始化成功");
}
//初始化开辟空间
void SeqInit2(SL* pc)//形参是实参的拷贝；形参的修改无法作用在实参上，因此要用地址传值
{					 //其SL结构体数个整体，assert(pc);(SLDataType*)pc->a = (SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);if (pc->a == NULL){perror("malloc fail");return;}pc->capacity = INIT_CAPACITY;pc->size = 0;printf("初始化成功\n");
}
//清除函数
void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->a = NULL;pc->size = pc->capacity = 0;if(pc->a == NULL)printf("\n清除成功");
}
//尾插函数
void SLPushBack(SL* pc, SLDataType x)
{assert(pc);//扩容SLInsert(pc, pc->size, x);//SLCheckCapacity(pc); //pc->a[pc->size++] = x;
}
//输出函数
void SLPrint(SL* pc)
{int i = 0;for (i = 0; i < pc->size; i++){printf("%d ",pc->a[i]);}printf("\n");
}
//尾出函数
void SLPopBack(SL* pc)
{SLErase(pc, pc->size-1);
}
//扩容函数
void SLCheckCapacity(SL* pc)
{if (pc->capacity == pc->size){SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*INIT_CAPACITY * 2);//扩充二倍if (pc->a == NULL){perror("realloc fail");return;}pc->a = tmp;pc->capacity *= 2;printf("扩容成功\n");}}
//头插函数
void SLPushFront(SL* pc, SLDataType x)
{assert(pc);//检查空间SLCheckCapacity(pc);//挪动数据SLInsert(pc, 0, x);
}
//头出函数
void SLPopFront(SL* pc)
{SLErase(pc,0);
}
//在某个位置插入
void SLInsert(SL* pc, int pos, SLDataType x)
{//判断指针和位置是否有效assert(pc);assert(pos >= 0 && pos <= pc->size);//判断是否扩容SLCheckCapacity(pc);//挪动数据int end = pc->size - 1;while (pos <= end){pc->a[end + 1] = pc->a[end];end--;}//插入数据pc->a[pos] = x;pc->size++;
}
//删除某一个位置的数据
void SLErase(SL* pc, int pos)
{assert(pc);assert(pos >= 0 && pos < pc->size);int begin = pos + 1;while (begin < pc->size){pc->a[begin-1] = pc->a[begin];begin++;}pc->size--;
}
//查找函数
int SLFind(SL* pc, SLDataType x)
{assert(pc);int i = 0;for (i = 0; i < pc->size; i++){if (pc->a[i] == x){return i + 1;}}return -1;
}