哪些网站是做食品,聊城定制化网站建设,seo霸屏软件,建设银行招标网站首页目录 1.线性表
2.顺序表
2.1顺序表的概念
2.2动态顺序表实现 2.2-1 动态顺序表实现思路
2.2-2 动态顺序表的初始化 2.2-3动态顺序表的插入
检查空间 尾插
头插
中间插入
2.2-4 动态顺序表的删除
尾删
头删
中间删除
2.2. 5 动态顺序表查找与打印、销毁
查找 …
目录 1.线性表
2.顺序表
2.1顺序表的概念
2.2动态顺序表实现 2.2-1 动态顺序表实现思路
2.2-2 动态顺序表的初始化 2.2-3动态顺序表的插入
检查空间 尾插
头插
中间插入
2.2-4 动态顺序表的删除
尾删
头删
中间删除
2.2. 5 动态顺序表查找与打印、销毁
查找
打印
销毁 2.2 6 测试动态顺序表 1.线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。例如我们有一个数组这个数组中的元素都占相同大小的内存都具有相同的类型而它们也按顺序排列的。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。什么意思呢逻辑结构可以看作我们把它想象成一个排列有序的数组 物理结构就是这个表实际在内存的结构它有可能是一个排列有序的数组但是更大的可能是用指针连起来的无序的一块块空间 2.顺序表
2.1顺序表的概念 顺序表是线性表的其中一种。它是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素。
2. 动态顺序表使用动态开辟的数组存储。 那么二者哪个更具有优势呢答案是动态顺序表如果我们使用静态顺序表去存储某个app的用户数据那么我们该用多少空间呢如果空间太少我们就会丢失一部分用户的数据如果空间太大又会浪费内存而使用动态顺序表则不用考虑这两个问题如果我们空间太小就增加内存而一开始我们不会开辟太大的内存所以不用担心空间浪费的问题所以我们本期就要用代码实现动态顺序表。
2.2动态顺序表实现 我们要实现顺序表需要实现它的增删查改等功能
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size ;
// 有效数据个数
size_t capicity ;
// 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(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);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl)
接下来我们来一个一个实现吧。 2.2-1 动态顺序表实现思路 我们需要实现顺序表的增删查改等功能包含十几个方法为了避免代码混乱等问题我们将顺序表分成三个文件来实现1test.c这个文件负责我们实现接口之后的测试2SeqList.h这个文件负责包含所有头文件和放置所有的函数声明如果另外两个文件要使用这些头文件只需要包含这个文件就可以了3SeqList.h这个文件负责实现所有方法函数的功能我们顺序表的大部分代码也是在这个文件。
2.2-2 动态顺序表的初始化 有了思路之后我们就来实现我们的代码。首先我们创建三个文件 在SeqList文件中包含我们要用到的头文件输入输出需要用到stdio.h,开辟内存的函数需用到stdlib.h我们还会用到断言assert.h),为了避免多次包含头文件以免不必要的内存浪费我们还会用到#pragma once 这段代码
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
接下来我们创建一个顺序表我们用一个结构体来表示这个顺序表并用typedef将它更名为SL
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;//有效数据int capacity;//空间大小}SL;
那么存储数据的类型为什么也要改名呢因为我们将来如果使用顺序表存储数据时我们并不知道我们存何种类型的数据如果我们存储的数据是int而要将它们全部换成字符类型此时恰好我们已经写了100000行代码我们要修改的化会变得相当困难所以我们将数据类型改名是为了方便以后我们要存储不同类型数据时可以很方便的更换类型。
我们来实现第一个方法——初始化在开始时我们将它们都初始化为0
void SeqInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;
}//初始化 2.2-3动态顺序表的插入 我们使用顺序表最主要的功能就是存储数据而在一开始顺序表是没有数据的所以我们先实现插入功能插入分为尾插头插从中间插入。尾插就是在最后一个有效数据后插入我们要插入的数据 例如这个顺序表有三个有效数据那么我们的尾插就是将它放在最后一个有效数据3的后面如果我们将数字4用尾插的方式插入顺序表那么就是这样 头插则与尾插刚好相反它是将要插入的数据放在有效数据的最前面而使其他数据整体往后移一位假设我们要用头插插入数字0 使用中间插入我们可以指定插入的位置如果我们要将数字6插入到3的位置我们只需要将这个位置后的所有有效数据都往后挪一位 接下来我们用代码实现。
检查空间 使用插入前我们需要为顺序表开辟一块空间我们在空间上会遇到两个问题如果我们是第一次进来所有数据都为0那么我们要第一次开辟内存如果我们要存入数据时内存不足则需要新开辟内存。这两种情况都有一个共同点——有效数据与空间大小相等所以只要有序数据和空间大小相等时我们就增加1倍空间在进入函数时我们先判断这个指针是不是为空如果我们向空指针存入数据则一点会出错代码实现
void SeqCheckcapa(SL* ps)//检查内存够不够不够则增加
{assert(ps);if (ps-capacity ps-size){int Newcapecity ps-capacity 0 ? 4 : 2 * ps-capacity * sizeof(SLDataType);SLDataType* tem (SLDataType*)realloc(ps-arr, Newcapecity * 2 *sizeof(SLDataType));if (tem ! NULL){ps-arr tem;}}
} 尾插 我们使用尾插前先判断我们的空间够不够传入的指针是否为空。那么我们如何插入呢我们顺序表中的有效数据是size个而最后一个有效数据的下标是size-1我们只需要在下标为size的位置插入数据然后size加1就完成了尾插的操作
void SeqPushBack(SL* ps, SLDataType x)
{assert(ps);SeqCheckcapa(ps);ps-arr[ps-size] x;}//尾插画图演示 头插 头插前面做的事和尾插一样先判断指针是不是为空再判断空间够不够。然后将所有数据往后移一位最后在下标为0的位置插入数据size加1
void SeqPushFront(SL* ps, SLDataType x)
{assert(ps);SeqCheckcapa(ps);int i 0;for (i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];} ps-arr[0] x;ps-size;
}//头插
中间插入
先判断指针是否为空和判断空间够不够。因为中间插入是指定位置进行插入所以我们只能在已经有的数据中间插入我们指定的数字不能小于0也不能大于size。当我们指定了一个有效数字pos下标我们将这个位置及它后面的所有数据往后挪一位此时这个位置就空出来了我们也就可以插入我们想插入的数字插入之后我们让size加1
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SeqCheckcapa(ps);int i 0;for (i ps-size ; ipos; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[pos] x;ps-size;}//指定下标前插入数据
2.2-4 动态顺序表的删除
删除同样分为尾删头删中间删除这部分内容比插入相对简单一点。
尾删 我们先判断指针是否为空再判断有效数据的情况如果有效数据为0我们就不能删除数据。而删除数据只需要让size往前挪动一位我们打印时不会打印这个数据而插入数据时会将这个数据覆盖
void SeqPopBack(SL* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}//尾删
头删
与尾删一样先判断指针是否为空再判断数据情况。头删操作只需将第二位及后面的所以数据往前移动一位将第一位数据覆盖最后让size减1就可以了 代码实现
void SeqPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int i 0;for (i 0; i ps-size-1 ; i){ps-arr[i] ps-arr[i 1];}ps-size--;}//头删
中间删除 先判断指针是否为空再判断有效数据的情况。因为中间删除是指定位置删除那么这个制定的数字肯定不能小于0也不能大于等于size而删除操作与头删相似我们指定好数字后只需要将它后面的所有有效数据往前挪动一位将它覆盖然后让size减1就可以了
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int i 0;for (i pos; ips-size-1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//指定下标删除
2.2. 5 动态顺序表查找与打印、销毁
查找
查找数据我们先判断指针是否为空。使用循环判断顺序表中是否有我们要查找的数据如果找到了则返回它的下标如果找不到则返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
}//查找数据
我们使用一个整型来接收如果大于0说明找到了并打印它的下标如果小于0则表示顺序表中没有这个数据
int find SLFind(sl, 4);
if (find 0)
{printf(没有找到\n);
}
else
{printf(找到了下标是%d\n, find);
}
打印
打印顺序表中的数据要先判断指针是否为空。接着使用循环将它的内容打印出来
void SeqPrint(SL* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}//打印
销毁 当使用完这块动态开辟出来的空间不要忘了释放以免造成内存泄漏和出现野指针的情况
void SeqDestroy(SL* ps)
{assert(ps);free(ps-arr);if (ps-arr ! NULL);{ps-arr NULL;}ps-capacity ps-size 0;
}
//销毁
至此所有方法就实现完成了。 2.2 6 测试动态顺序表 我们来测试一下其中一些方法
void test2()
{SL sl;SeqInit(sl);//插入1 2 3 4SeqPushBack(sl, 1);SeqPushBack(sl, 2);SeqPushBack(sl, 3);SeqPushBack(sl, 4);SeqPrint(sl);//插入99 99SLInsert(sl, 0, 99);SLInsert(sl, 3, 88);SLInsert(sl, sl.size, 10000);SeqPrint(sl);//删除SLErase(sl,2);SeqPrint(sl);SLErase(sl, 5);SeqPrint(sl);//查找int find SLFind(sl, 4);if (find 0){printf(没有找到\n);}else{printf(找到了下标是%d\n, find);}//释放空间SeqDestroy(sl);
}
来看运行结果 可以看到我们实现的方法都没有问题我将原码放在下面感兴趣的小伙伴可以试试哦。
SeqList.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;//有效数据int capacity;//空间大小}SL;void SeqInit(SL* ps);//初始化void SeqDestroy(SL* ps);//销毁void SeqPushBack(SL* ps, SLDataType x);//尾插void SeqPushFront(SL* ps, SLDataType x);//头插void SeqPopBack(SL* ps);//尾删void SeqPopBack(SL* ps);//头删void SeqPrint(SL* ps);//打印void SLErase(SL* ps, int pos);//指定删除int SLFind(SL* ps, SLDataType x);//查找数据//指定下标前插入数据
void SLInsert(SL* ps,int pop, SLDataType x);
SeqList.c :
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqList.hvoid SeqInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;
}//初始化void SeqCheckcapa(SL* ps)//检查内存够不够不够则增加
{assert(ps);if (ps-capacity ps-size){int Newcapecity ps-capacity 0 ? 4 : 2 * ps-capacity * sizeof(SLDataType);SLDataType* tem (SLDataType*)realloc(ps-arr, Newcapecity * 2 *sizeof(SLDataType));if (tem ! NULL){ps-arr tem;}}
}void SeqPushBack(SL* ps, SLDataType x)
{assert(ps);SeqCheckcapa(ps);ps-arr[ps-size] x;}//尾插void SeqPushFront(SL* ps, SLDataType x)
{assert(ps);SeqCheckcapa(ps);int i 0;for (i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];} ps-arr[0] x;ps-size;
}//头插void SeqPopBack(SL* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}//尾删void SeqPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int i 0;for (i 0; i ps-size-1 ; i){ps-arr[i] ps-arr[i 1];}ps-size--;}//头删void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SeqCheckcapa(ps);int i 0;for (i ps-size ; ipos; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[pos] x;ps-size;}//指定下标前插入数据void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int i 0;for (i pos; ips-size-1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//指定下标删除int SLFind(SL* ps, SLDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
}//查找数据
void SeqPrint(SL* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}//打印void SeqDestroy(SL* ps)
{assert(ps);free(ps-arr);if (ps-arr ! NULL);{ps-arr NULL;}ps-capacity ps-size 0;
}
//销毁test.c :
#define _CRT_SECURE_NO_WARNINGS 1
#includeSeqList.h
//void SLPushBack(SL* ps, SLDatatype x)
//{
// assert(ps);
//
// if (ps-size ps-capacity)
// {
// int Newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;
//
// SLDatatype* tem(SLDatatype*)realloc(ps-arr,2* Newcapacity*sizeof(SLDatatype))
// if (tem NULL)
// {
// perror(realloc);
// exit(1);
// }
//
// ps-arr tem;
// ps-capacity Newcapacity;
// }
// ps-arr[size] x;
//
//}
//
//
//
//
//void SLPushBack(SL* ps, SLDataType x)
//{
// //1.判断指针是否为空为空则出错
// assert(ps);
//
// //2.判断空间够不够不够则申请空间
// if (ps-capecity ps-size)
// {
// //如果capecity为0我们就要第一次开辟出4个SLDataType类型的空间
// SLDataType NewCapecity ps-capecity 0 ? 4 : 2 * ps-capecity;
// //开辟空间如果下次空间不够则下次开辟此次2倍的空间
// SLDataType* tem (SLDataType*)realloc(ps-arr, NewCapecity * 2 * sizeof(SLDataType));
// if (tem NULL)
// {
// perror(realloc);
// exit(1);
// }
// //走到这里说明tem不为空将新开辟好的内存给arr
// ps-arr tem;
// ps-capecity NewCapecity;
// }
// ps-arr[ps-size] x;
// //3.进行尾插操作
//}
void test1()
{SL sl;SeqInit(sl);SeqPushBack(sl, 1);SeqPushBack(sl, 2);SeqPushBack(sl, 3);SeqPushBack(sl, 4);SeqPrint(sl);SeqPushFront(sl, 6);SeqPrint(sl);SeqPopBack(sl);SeqPrint(sl);SeqPopFront(sl);SeqPopFront(sl); SeqPopFront(sl); SeqPrint(sl);SeqDestroy(sl);
}
void test2()
{SL sl;SeqInit(sl);//插入1 2 3 4SeqPushBack(sl, 1);SeqPushBack(sl, 2);SeqPushBack(sl, 3);SeqPushBack(sl, 4);SeqPrint(sl);//插入99 99SLInsert(sl, 0, 99);SLInsert(sl, 3, 88);SLInsert(sl, sl.size, 10000);SeqPrint(sl);//删除SLErase(sl,2);SeqPrint(sl);SLErase(sl, 5);SeqPrint(sl);//查找int find SLFind(sl, 4);if (find 0){printf(没有找到\n);}else{printf(找到了下标是%d\n, find);}//释放空间SeqDestroy(sl);
}
int main()
{test2();//test1();return 0;
}
