整体思路:
要知道我们实现数据结构,是要理解他是有什么用处的。
顺序表就是连续存储数据,它可以实现增删查改,让我们的数据变得灵活可变,让我们能够灵活的使用数据。
顺序表有两个类型:一个是静态的顺序表,一个是动态的顺序表。他们都有各自的优点和缺点,我们这次是采取工程文件的形式。
静态版本:就是顺序表的大小是确定的,不管你的数据是多少,容量是固定的,在定义的是时候是这样的:
#define MAX 1000//设置最大容量为100.
//为什么要宏呢?
//因为我们后面会多次用到容量为1000,我们就直接都用MAX代替
//以防我们需要修改容量大小时候所以的1000都要修改。
//进行宏替换只需要修改宏中的数字就可。
tpyedef int STDataType;//重命名,后面要用到其他数据类型就可以在这里直接改变。
typedef struct SeqList
{
STDataType data[MAX];//顺序表存储的位置
int size;//记录已经存储的个数
}SL;
我这次主要介绍的是动态的版本,应为大部分的数据都是多变的,所以动态版本是更好的。
tpyedef int STDataType;//重命名,后面要用到其他数据类型就可以在这里直接改变。
typedef struct SeqList
{
STDataType* a;//这里用动态申请空间
int size;//数据个数
int capacity//动态顺序表的容量,用来判断是否需要增容。
}SL;
动态顺序表的增删查改等:
这些函数的定义是要放在头文件里面的,实现是放在一个.c文件中的:
(1)初始化:
一开始顺序表是什么都没有的,为空
//实现:
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
(2) 尾插
尾插就是在顺序表的最后面进行数据的插入,每当我们插入的时候都需要进行判断顺序表是否需要增容,以及后面的头插和在任何位置插入,都需要进行判断是否需要增容,所以为了防止代码的重复,我们直接封装一个增容函数。
增容
void SeqListCheckCapacity(SL* ps)//判断是否需要增容
{
if (ps->size == ps->capacity)
{
//判断ps->capacity是否为0.
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//进行增容,realloc中第一个人参数如果为NULL,则效果相当于malloc,第二个参数是字节数。
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("Realloc Failed");
exit(-1);//异常退出,终止程序。
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
这样我们就可以尾插了:
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
//1.判断是否要增容
SeqListCheckCapacity(ps);
//2.空间足够,进行尾插
ps->a[ps->size] = x;
ps->size++;
}
(3) 尾删
每当删除的时候都要判断顺序表中是否还有数据,如果有数据才能删除,没有数据是不能删除的。
void SeqListPopBack(SL* ps)//尾删
{
if (ps->size != 0)//没有数据可以删了就进不去
{
ps->size--;
}
}
(4)头插
头插的时候,因为数据是连续的,所以我们必须要把所以的数据从后往前一次向后挪动一个位置,所以时间复杂度是O(n),这也是顺序表的一个缺陷。
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
//1.判断是否要增容
SeqListCheckCapacity(ps);
//2.进行头插
int end = ps->size - 1;
//挪数据
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
(5)头删
头删也是跟头插类似,要把除了第一个数据以为从第二个数据开始依次覆盖数据:
void SeqListPopFornt(SL* ps)//头删
{
if (ps->size > 0)
{
int begin = 0;
for (begin; begin < ps->size - 1; begin++)
{
ps->a[begin] = ps->a[begin + 1];
}
ps->size--;
}
}
(6)查找
查找就是输入一个数据,如果找到这个数据就返回数据的下标,找不到就返回-1,从而告诉我们没有这个数据。
int SeqListFind(const SL* ps, SLDataType x)
//查找,找到返回下标,找不到返回-1
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
(7)在pos下标后进行插入
void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下标后进行插入
{
//1.判断pos是否小于ps->size或者小于0
if (pos < ps->size && pos >= 0)
{
//(1).判断是否需要增容
SeqListCheckCapacity(ps);
//(2).插入
int end = ps->size ;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[pos + 1] = x;
ps->size++;
}
//用错了返回
else
{
//给定的下标不合法我们就直接断言报错
assert(pos >= 0 && pos < ps->size);
}
}
(7)在pos下标后进行删除
void SeqListErase(SL* ps, int pos)//删除下标为pos的值
{
if (pos >= 0 && pos < ps->size)
{
int begin = pos;
while (begin < ps->size - 1)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
}
整体代码
1.SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#define N 100
//typedef int SLDataType;
//
静态顺序表
//typedef struct SeqList
//{
// SLDataType a[N];
// int size;//表示顺序表存储元素的个数
//}SL;
//
接口函数
//void SeqListInit(SL* ps);//初始化
//
//void SeqListPushBack(SL* ps, SLDataType x);//尾插
//void SeqListPopBack(SL* ps);//尾删
//void SeqListPushFront(SL* ps, SLDataType x);//头插
//void SeqListPopFornt(SL* ps, SLDataType x);//头删
typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size;//表示顺序表存储元素的个数
int capacity; //数组实际能存储空间的容量的个数。
}SL;
//接口函数(增删查改)
void SeqListInit(SL* ps);//初始化
void SeqListDestroy(SL* ps);//销毁
void SeqListCheckCapacity(SL* ps);//判断是否需要增容
void SeqListPushBack(SL* ps, SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFornt(SL* ps);//头删
void SeqListPrint(const SL* ps);//打印
int SeqListFind(const SL* ps, SLDataType x);//查找,找到返回下标,找不到返回-1
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos下标后进行插入
void SeqListErase(SL* ps, int pos);//删除下标为pos的值
2.SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListCheckCapacity(SL* ps)//判断是否需要增容
{
if (ps->size == ps->capacity)
{
//判断ps->capacity是否为0.
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//进行增容,realloc中第一个人参数如果为NULL,则效果相当于malloc,第二个参数是字节数。
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("Realloc Failed");
exit(-1);//异常退出,终止程序。
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void SeqListPrint(const SL* ps)//打印
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SeqListInit(SL* ps)//初始化
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListDestroy(SL* ps)//销毁
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
//1.判断是否要增容
SeqListCheckCapacity(ps);
//2.空间足够,进行尾插
ps->a[ps->size] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{
if (ps->size != 0)//没有数据可以删了就进不去
{
ps->size--;
}
}
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
//1.判断是否要增容
SeqListCheckCapacity(ps);
//2.进行头插
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFornt(SL* ps)//头删
{
if (ps->size > 0)
{
int begin = 0;
for (begin; begin < ps->size - 1; begin++)
{
ps->a[begin] = ps->a[begin + 1];
}
ps->size--;
}
}
int SeqListFind(const SL* ps, SLDataType x)//查找,找到返回下标,找不到返回-1
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListInsert(SL* ps, int pos, SLDataType x)//在pos下标后进行插入
{
//1.判断pos是否小于ps->size或者小于0
if (pos < ps->size && pos >= 0)
{
//(1).判断是否需要增容
SeqListCheckCapacity(ps);
//(2).插入
int end = ps->size ;
while (end > pos)
{
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[pos + 1] = x;
ps->size++;
}
//用错了返回
else
{
assert(pos >= 0 && pos < ps->size);
}
}
void SeqListErase(SL* ps, int pos)//删除下标为pos的值
{
if (pos >= 0 && pos < ps->size)
{
int begin = pos;
while (begin < ps->size - 1)
{
ps->a[begin] = ps->a[begin + 1];
begin++;
}
ps->size--;
}
}
3.test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void TestSeqList1()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void TestSeqList2()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPrint(&s1);
SeqListPushFront(&s1, 0);
SeqListPushFront(&s1, -1);
SeqListPushFront(&s1, -2);
SeqListPushFront(&s1, -3);
SeqListPopFornt(&s1);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void TestSeqList3()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListInsert(&s1, 1, 10);
SeqListInsert(&s1, 1, 20);
SeqListInsert(&s1, 1, 30);
SeqListPrint(&s1);
SeqListErase(&s1, 5);
SeqListPrint(&s1);
SeqListDestroy(&s1);
}
void menu()
{
printf("********************************************\n");
printf("************ 请选择 ***********\n");
printf("**** 1.头插 2.尾插 ****\n");
printf("**** 3.头删 4.尾删 ****\n");
printf("**** 5.打印 -1.退出 ****\n");
printf("********************************************\n");
printf("********************************************\n");
}
void Test()
{
int input;
int x;
SL s1;
SeqListInit(&s1);
printf("please Select\n");
do
{
menu();
scanf("%d", &input);
switch (input)
{
case 1:
printf("Please enter the contents of the header to end with-1\n");
scanf("%d", &x);
while (x != -1)
{
SeqListPushFront(&s1, x);
scanf("%d", &x);
}
break;
case 2:
printf("Please enter the contents of the tail insert ending in-1\n");
scanf("%d", &x);
while (x != -1)
{
SeqListPushBack(&s1, x);
scanf("%d", &x);
}
break;
case 3:
SeqListPopFornt(&s1);
printf("Pop successful\n");
break;
case 4:
SeqListPopBack(&s1);
printf("Pop successful\n");
break;
case 5:
SeqListPrint(&s1);
break;
case -1:
exit(0);
break;
default:
printf("Selected error!\n");
break;
}
} while (input != -1);
SeqListDestroy(&s1);
}
int main()
{
//menu() ;
//TestSeqList1();
//TestSeqList2();
//TestSeqList3();
Test();
return 0;
}