做解析会员电影的网站,湘潭网站建设 问下磐石网络,微信小程序商城收费吗,最新源码论坛目录
1.线性表概念
1.1 什么是顺序列表
1.2 线性表
2.顺序表实现
将有以下功能#xff1a;
详细过程
顺序表的动态存储
顺序表初始化
尾插
扩容
头插
更改后的尾插
尾删
头删
打印
释放内存
优化顺序表 (任意位置插入删除)
优化后的头插尾插
优化后的头删尾…目录
1.线性表概念
1.1 什么是顺序列表
1.2 线性表
2.顺序表实现
将有以下功能
详细过程
顺序表的动态存储
顺序表初始化
尾插
扩容
头插
更改后的尾插
尾删
头删
打印
释放内存
优化顺序表 (任意位置插入删除)
优化后的头插尾插
优化后的头删尾删
查找和删除
进行装饰(菜单)
成品
SeqList.h
SeqList.c
Test.c: 1.线性表概念
1.1 什么是顺序列表
顺序列表Sequential List是一种使用连续的内存空间存储元素的线性数据结构。顺序列表中的元素按照其在内存中的物理顺序依次排列同时通过索引来访问元素。
顺序列表可以使用数组来实现数组的下标就是元素的索引。由于数组具有随机访问的特性即可以通过索引直接访问元素因此顺序列表在查找指定位置的元素时具有较高的效率。
顺序列表的特点包括 连续的内存空间顺序列表中的元素在内存中是连续存储的这样可以通过索引进行快速访问提高了访问效率。 固定大小顺序列表的大小在创建时就确定一旦分配了固定大小的内存空间就无法自动扩展或缩小。需要预估元素的个数以避免空间浪费或溢出。 随机访问效率高由于顺序列表基于数组实现并支持随机访问可以在O(1)的时间复杂度内获取指定位置的元素值。 插入和删除的效率较低当需要在顺序列表的中间位置插入或删除元素时需要移动部分元素导致时间复杂度为O(n)。因此在有频繁的插入和删除操作时顺序列表的效率可能较低。
需要注意的是顺序列表适用于元素个数固定且随机访问较为频繁的场景。当需要频繁进行插入和删除操作或者元素个数不确定时可以考虑其他数据结构如链表。
1.2 线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。
2.顺序表实现
将有以下功能
// 顺序表的动态存储
typedef struct SeqList// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);详细过程
定义三个文件 头文件 SeqList.h 函数的实现SeqList.c 代码的测试 Test.c
顺序表的动态存储
//SeLqist.h
#define N 200
typedef int SLDataType;//静态顺序表 -- N太小可能不够用 N太大可能浪费空间
//struct SeqList
//{
// SLDataType a[N];
// int size;
// int capa;
//};//动态顺序表
typedef struct SeqList
{SLDataType* a;// 指向数组的指针int size; // 数据个数int capacity;// 容量-空间大小
}SL;顺序表初始化
//SeqList.c
void SLInit(SL* ps)
{ps-a NULL;ps-size ps-capacity 0;
}尾插
void SLPushBack(SL* ps, SLDataType x)
{//检查容量空间满了扩容if (ps-capacity ps-size){int newCapacity 0;if (ps-capacity 0)newCapacity ps-capacity 4;elsenewCapacity 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;}ps-a[ps-size] x;ps-size;
}扩容
//动态增容
void SLCheckCapacity(SL* ps)
{//检查容量空间满了扩容if (ps-capacity ps-size){int newCapacity 0;if (ps-capacity 0)newCapacity ps-capacity 4;elsenewCapacity 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 SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}更改后的尾插
//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}尾删
void SLPopBack(SL* ps)
{//尾部要删除的数字无需重新定义数字意义不大//只需将 size-- 即可(要防止越界)assert(ps-size0);//防止空了还继续删除ps-size--;
}头删
//头删
void SLPopFront(SL* ps)
{assert(ps-size 0);int begin 1;while (beginps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}打印
//打印
void SLPrint(SL* ps)
{assert(ps!NULL);for (int i 0;i ps-size;i){printf(%d , ps-a[i]);}printf(\n);
}释放内存
//释放内存
void SLDestory(SL* ps)
{assert(ps ! NULL);if (ps-a){free(ps-a);ps-a NULL;ps-capacity ps-size 0;}
}优化顺序表 (任意位置插入删除)
增加顺序表功能在中间部分 插入/删除 数字也可简化头尾插删代的码量
//任意位置插入 插入数据都要防止越界
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (endpos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}//任意位置删除
void SLErase(SL* ps, int pos)
{assert(pos 0 pos ps-size);int begin pos;while (beginps-size){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
}既然已经做到在任意位置可以插入代码则可以对之前写的代码进行简化
优化后的头插尾插
//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLInsert(ps, ps-size, x);
}//头插
void SLPushFront(SL* ps, SLDataType x)
{SLInsert(ps, 0, x);
}优化后的头删尾删
//尾删
void SLPopBack(SL* ps)
{SLErase(ps, ps-size - 1);
}//头删
void SLPopFront(SL* ps)
{SLErase(ps, 0);
}查找和删除
//查找
int SLFind(SL* ps, SLDataType x)
{for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;//没找到
}//修改
int SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;
}测试该两项功能test.c:
//
int x 0;
printf(请输入你要删除的值:);
scanf(%d, x);
int pos SLFind(sl, x);
if (pos ! -1)
{SLErase(sl, pos);
}
elseprintf(没有找到%d\n,x);
SLPrint(sl);
//
int y, z;
printf(请输入你要修改的值和修改后的值:);
scanf(%d %d, y,z);
pos SLFind(sl, y);
if (pos ! -1)
{SLModify(sl, pos,z);
}
elseprintf(没有找到%d\n, y);
SLPrint(sl);
//
int f 0;
printf(请输入你要删除的值,并删除所有与之相同的值:);
scanf(%d, f);
pos SLFind(sl, f);
while (pos!-1)
{SLErase(sl, pos);pos SLFind(sl, f);
}进行装饰(菜单)
void menu()
{printf(*******************************\n);printf(1.头插 2.尾插 3.查找 \n);printf(4.删除 5.连续删除 6.修改 \n);printf(7.打印 8.退出 \n);printf(*******************************\n);
}成品
SeqList.h
#pragma once#include stdio.h
#include assert.h
#include stdlib.htypedef int SLDataType;//静态顺序表 -- N太小可能不够用 N太大可能浪费空间
//struct SeqList
//{
// SLDataType a[N];
// int size;
// int capa;
//};//动态顺序表
typedef struct SeqList
{SLDataType* a;// 指向数组的指针int size; // 数据个数int capacity;// 容量-空间大小
}SL;//初始化
void SLInit(SL* ps);//头插
void SLPushFront(SL* ps, SLDataType x);//头删
void SLPopFront(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//任意位置插入
void SLInsert(SL* ps,int pos, SLDataType x);//任意位置删除
void SLErase(SL* ps, int pos);//打印
void SLPrint(SL* ps);//动态增容
void SLCheckCapacity(SL* ps);//释放内存
void SLDestory(SL* ps);//查找
int SLFind(SL* ps, SLDataType x);//修改
void SLModify(SL* ps, int pos, SLDataType x);SeqList.c
#include SeqList.hvoid SLInit(SL* ps)
{ps-a NULL;ps-size ps-capacity 0;
}//打印
void SLPrint(SL* ps)
{assert(ps!NULL);for (int i 0;i ps-size;i){printf(%d , ps-a[i]);}printf(\n);
}//动态增容
void SLCheckCapacity(SL* ps)
{assert(ps ! NULL);//检查容量空间满了扩容if (ps-capacity ps-size){int newCapacity 0;if (ps-capacity 0)newCapacity ps-capacity 4;elsenewCapacity 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 SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);//挪动数据int end ps-size - 1;while (endpos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}//任意位置删除
void SLErase(SL* ps, int pos)
{assert(pos 0 pos ps-size);int begin pos;while (beginps-size){ps-a[begin] ps-a[begin 1];begin;}ps-size--;
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLInsert(ps, ps-size, x);
}//头插
void SLPushFront(SL* ps, SLDataType x)
{SLInsert(ps, 0, x);
}//尾删
void SLPopBack(SL* ps)
{SLErase(ps, ps-size - 1);
}//头删
void SLPopFront(SL* ps)
{SLErase(ps, 0);
}//查找
int SLFind(SL* ps, SLDataType x)
{for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;//没找到
}//修改
void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;
}//释放内存
void SLDestory(SL* ps)
{assert(ps ! NULL);if (ps-a){free(ps-a);ps-a NULL;ps-capacity ps-size 0;}
}Test.c:
#include SeqList.h
void menu()
{printf(*******************************\n);printf(1.头插 2.尾插 3.查找 \n);printf(4.删除 5.连续删除 6.修改 \n);printf(7.打印 8.退出 \n);printf(*******************************\n);
}int main()
{//初始化SL sl;SLInit(sl);int option -1;int x,y,z,f;do{menu();scanf(%d, option);int val, pos;switch (option){case 1:printf(请输入要头插的数据,以0结束:);scanf(%d, val);while (val!0){SLPushFront(sl, val);scanf(%d,val);}break;case 2:printf(请输入要尾插的数据,以0结束:);scanf(%d, val);while (val ! 0){SLPushBack(sl, val);scanf(%d, val);}break;case 3:printf(请输入要查找的数字:);scanf(%d, y);pos SLFind(sl, y);if (pos ! -1){printf(找到了%d\n, y);}elseprintf(没有找到%d\n, y);SLPrint(sl);break;case 4:printf(请输入你要删除的值:);scanf(%d, x);int pos SLFind(sl, x);if (pos ! -1){SLErase(sl, pos);}elseprintf(没有找到%d\n, x);SLPrint(sl);break;case 5:printf(请输入你要删除的值,并删除所有与之相同的值:);scanf(%d, f);pos SLFind(sl, f);if (pos ! -1){while (pos ! -1){SLErase(sl, pos);pos SLFind(sl, f);}}elseprintf(没有找到要删除的值%d\n, f);break;case 6:printf(请输入你要修改的值和修改后的值:);scanf(%d %d, y, z);pos SLFind(sl, y);if (pos ! -1){SLModify(sl, pos, z);}elseprintf(没有找到%d\n, y);SLPrint(sl);break;case 7:SLPrint(sl);break;case 8:break;default:printf(输入错误请重新输入\n);break;}} while (option!8);printf(退出成功\n);//释放内存SLDestory(sl);return 0;
}到这里就结束啦创作不易求求点个赞啦╰(°▽°)╯
