目录
一.线性表
线性表：全名线性存储结构
线性存储结构分为顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表
1.顺序存储
顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到指定位置的一块连续的存储空间。
2.链式存储
用于存储逻辑关系为“一对一”的数据
用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），包括数据与和指针域。数据域存储数据，指针域存储后继的信息。
二.顺序表
分类：
- 静态顺序表：使用定长数组存储
- 动态顺序表：使用动态开辟的数组存储
静态顺序表?
问题：
给少了不够用 ，给多了用不完，不能灵活控制
动态顺序表
问题：
- 如果空间不够，增容。增容会付出一定性能消耗，其次可能存在一定的空间浪费
- 头部或者中部左右的插入和删除效率低
如何解决问题：
- ?空间上，按需给空间
- 不要求物理空间的连续
- 这里我们使用动态顺序表
三.代码实现
初始化
//初始化
void SeqListInit(SL* psl)
{
psl->a = NULL;
psl->capacity = 0;
psl->sizel = 0;
}尾插入
//增容
void SeqListCheckCapacity(SL* psl)
{
if (psl->capacity == psl->sizel)
{
int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
//realloc将第一个参数的值依次存入所申请的空间
assert(temp);
psl->a = temp;
psl->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SL* psl, SQDataType x)
{
SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
psl->a[psl->sizel] = x;
psl->sizel++;
}首插入
方法1：
使用常规的for循环进行增容。
void SeqListPushFront(SL* psl, SQDataType x)
{
SeqListCheckCapacity(psl);//增容
for (int i = psl->sizel-1; i >= 0; i--)
{
psl->a[i + 1] = psl->a[i];
}
psl->a[0] = x;
psl->sizel++;
}方法2：
使用memmove函数，以字节为单位，拷贝链表，使其每个元素的位置增加一个SQDataType的大小。
//头插——方法2
void SeqListPushFront(SL* psl, SQDataType x)
{
SeqListCheckCapacity(psl);//增容
memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
psl->a[0] = x;
psl->sizel++;
}头删
这里同样可以使用两种方法，这里我使用了最方便的memmove
//头删
void SeqListPopFront(SL* psl)
{
assert(psl->sizel > 0);//判断顺序表中是否有数据
memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
psl->a[psl->sizel - 1] = 0;
psl->sizel--;
}?尾删
//尾删
void SeqListPopBack(SL* psl)
{
assert(psl->sizel > 0);//判断顺序表中是否有数据
psl->a[psl->sizel - 1] = NULL;
psl->sizel--;
}?选择插入
方法1：
使用memmove函数调整表中元素位置后插入
//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
assert(pos <= psl->sizel);
SeqListCheckCapacity(psl);//增容
memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
psl->a[index] = x;
psl->sizel++;
}?方法2：
使用循环依次移动元素最终插入
//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
assert(index <= psl->sizel);//判断index范围是否合法
SeqListCheckCapacity(psl);//增容
int cou = psl->sizel;
while (cou > index)
{
psl->a[cou] = psl->a[cou - 1];
cou--;
}
psl->a[index] = x;
psl->sizel++;
}?选择删除
使用memmove函数覆盖所要删除的位置
//选择删除
void SeqListErase(SL* psl, int index)
{
assert(index < psl->sizel);
memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
psl->a[psl->sizel - 1] = NULL;
psl->sizel--;
}查找
在顺序表中查找x，若找到返回下标，找不到则说明顺序表中没有改值
//查找
void SeqListFind(SL* psl, SQDataType x)
{
int num = 0;
while (num < psl->sizel)
{
if (psl->a[num] == x)
{
printf("%d\n", num);
return;
}
num++;
}
printf("表中没有%d\b", x);
return;
}?修改
给出要修改元素的下标和替换的值，进行替换操作。
//修改
void SeqListModity(SL* psl, int pos, SQDataType x)
{
assert(pos < psl->sizel);//判断给出的下标是否在范围内
psl->a[pos] = x;
}
四.完整代码
SeqList.h文件
在头文件定义，存放函数、头文件和结构体的声明
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define N 10;
typedef int SQDataType;
typedef struct SeqList
{
SQDataType* a;
int sizel; //有效数据个数
int capacity; //容量
}SL;
//初始化
void SeqListInit(SL* psl);
//尾插入
void SeqListPushBack(SL* psl, SQDataType x);
//头插入
void SeqListPushFront(SL* psl, SQDataType x);
//头删
void SeqListPopFront(SL* psl);
//尾删
void SeqListPopBack(SL* psl);
//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x);
//选择删除
void SeqListErase(SL* psl, int index);
//查找
void SeqListFind(SL* psl, SQDataType x);
//修改
void SeqListModity(SL* psl, int pos, SQDataType x);
//打印
void SeqListPrint(SL* psl);
//销毁空间
void SeqListDestroy(SL* psl);SeqList.c文件
函数的实现放在此文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//初始化
void SeqListInit(SL* psl)
{
psl->a = NULL;
psl->capacity = 0;
psl->sizel = 0;
}
//增容
void SeqListCheckCapacity(SL* psl)
{
if (psl->capacity == psl->sizel)
{
int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
assert(temp);
psl->a = temp;
psl->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SL* psl, SQDataType x)
{
SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
psl->a[psl->sizel] = x;
psl->sizel++;
}
//头插——方法1
//void SeqListPushFront(SL* psl, SQDataType x)
//{
// SeqListCheckCapacity(psl);//增容
// for (int i = psl->sizel-1; i >= 0; i--)
// {
// psl->a[i + 1] = psl->a[i];
// }
// psl->a[0] = x;
// psl->sizel++;
//}
//头插——方法2
void SeqListPushFront(SL* psl, SQDataType x)
{
SeqListCheckCapacity(psl);//增容
memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
psl->a[0] = x;
psl->sizel++;
}
//头删
void SeqListPopFront(SL* psl)
{
assert(psl->sizel > 0);//判断顺序表中是否有数据
memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
psl->a[psl->sizel - 1] = 0;
psl->sizel--;
}
//尾删
void SeqListPopBack(SL* psl)
{
assert(psl->sizel > 0);//判断顺序表中是否有数据
psl->a[psl->sizel - 1] = NULL;
psl->sizel--;
}
//选择插入
//void SeqListInsert(SL* psl, int index, SQDataType x)
//{
// assert(index <= psl->sizel);
// SeqListCheckCapacity(psl);//增容
// memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
// psl->a[index] = x;
// psl->sizel++;
//}
//选择插入
void SeqListInsert(SL* psl, int index, SQDataType x)
{
assert(index <= psl->sizel);
SeqListCheckCapacity(psl);//增容
int cou = psl->sizel;
while (cou > index)
{
psl->a[cou] = psl->a[cou - 1];
cou--;
}
psl->a[index] = x;
psl->sizel++;
}
//选择删除
void SeqListErase(SL* psl, int index)
{
assert(index < psl->sizel);
memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
psl->a[psl->sizel - 1] = NULL;
psl->sizel--;
}
//查找
void SeqListFind(SL* psl, SQDataType x)
{
int num = 0;
while (num < psl->sizel)
{
if (psl->a[num] == x)
{
printf("%d\n", num);
return;
}
num++;
}
printf("表中没有%d\b", x);
return;
}
//修改
void SeqListModity(SL* psl, int pos, SQDataType x)
{
assert(pos < psl->sizel);
psl->a[pos] = x;
}
//打印链表
void SeqListPrint(SL* psl)
{
for (int i = 0; i < psl->sizel; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
//销毁空间
void SeqListDestroy(SL* psl)
{
free(psl->a);
psl->a = NULL;
psl->capacity = 0;
psl->sizel = 0;
}text.c文件
存放主函数，其它函数在此文件夹调用
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include "SeqList.h"
//菜单
void menu()
{
printf("**********************\n");
printf("1.尾插数据，2.头插数据\n");
printf("3.尾删数据，4.头删数据\n");
printf("5.选择插入，6.选择删除\n");
printf("7.查找元素，8.修改链表\n");
printf("9.打印数据，-1，退出\n");
printf("**********************\n");
printf("请输入你的选择:");
}
int main()
{
SL slist;
int choose = 0;
SeqListInit(&slist);//初始化
while (choose != -1)
{
int a = 0, b = 0;
menu();
scanf(" %d", &choose);
switch (choose)
{
case 1://尾插
printf("请输入你要插入的数据，以-1结束\n");
while (a != -1)
{
scanf("%d", &a);
if(a!=-1)
SeqListPushBack(&slist, a);
}
break;
case 2://头插
printf("请输入你要插入的数据，以-1结束\n");
while (a != -1)
{
scanf("%d", &a);
if (a != -1)
SeqListPushFront(&slist, a);
}
break;
case 3://尾删
SeqListPopBack(&slist);
printf("尾删，删除成功！\n");
break;
case 4://头删
SeqListPopFront(&slist);
printf("头删，删除成功!\n");
break;
case 5://选择插入
printf("请输入需要插入的下标和元素:");
scanf("%d%d", &a, &b);
SeqListInsert(&slist, a, b);
break;
case 6://选择删除
printf("请输入需要删除的元素的下标:");
scanf("%d", &a);
SeqListErase(&slist, a);
break;
case 7://查找元素
printf("请输入需要查找的元素的下标:");
scanf("%d", &a);
SeqListFind(&slist, a);
break;
case 8://修改链表
printf("请输入需要修改的下标和元素:");
scanf("%d%d", &a, &b);
SeqListModity(&slist, a, b);
break;
case 9://打印
SeqListPrint(&slist);
break;
case -1://退出
SeqListDestroy(&slist);//销毁空间
break;
default:
printf("输入错误，请重新输入！\n");
break;
}
system("pause");
system("cls");
}
return 0;
}