网站建设 选择题,互联网运营在线培训,重庆手机模板建站,做一个购物商城网站多少钱文章目录:star2:1. 顺序表概念:star2:2. 框架3. 基本功能3.1 头文件:star:3.2 初始化:star:3.3 扩容:star:3.4 打印:star:3.5 尾插:star:3.6 头插:star:3.7 尾删:star:3.8 头删:star:3.9 指定插入:star:3.10 指定删除:star:3.11 查找:star2:3.12 注意事项4. 顺序表的缺点#…
文章目录:star2:1. 顺序表概念:star2:2. 框架3. 基本功能3.1 头文件:star:3.2 初始化:star:3.3 扩容:star:3.4 打印:star:3.5 尾插:star:3.6 头插:star:3.7 尾删:star:3.8 头删:star:3.9 指定插入:star:3.10 指定删除:star:3.11 查找:star2:3.12 注意事项4. 顺序表的缺点1. 顺序表概念 顺序表是在计算机内存中以数组的形式保存的线性表线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 将数据一个一个连续的存放在数组中这种存储结构是顺序结构采用顺序结构的线性表简称为顺序表 顺序表一般可以分为
静态顺序表 使用定长数组存储数据 动态顺序表(本章实现)动态开辟内存来存放数据
2. 框架
较大程序分3个及以上文件来写这里分三个文件
SeqList.cSeqList.hText.c
SeqList.c文件用来实现与顺序表有关的函数 SeqList.h文件用来声明函数和结构体 Text.c文件用来测试代码是否正确
3. 基本功能
顺序表需要实现的基本功能有
头删尾删头插尾插随机删随机插查找打印
在正式实现顺序表功能之前我们先对顺序表执行初始化,将顺序表的初始容量置为0,初始化函数SeqListInit当我们插入数据时需要检查Capacity是否满了若满了则需要扩容,扩容函数SeqListCheckCapacity
3.1 头文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLtype;
typedef struct
{SLtype* a; //a是动态开辟的数组size_t size; //有效数据的个数size_t capcity;//动态开辟数组的容量
}SeqList;void SeqListInit(SeqList* ps);
//扩容
void SeqListCheckCapacity(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps, SLtype pos);
//尾删
void SeqListPopBack(SeqList* ps);
//头插
void SeqListPushFront(SeqList* ps, SLtype pos);
//头删
void SeqListPopFront(SeqList* ps);
//随机插入
void SeqListInsert(SeqList* ps, int pos, SLtype data);
//随机删除
void SeqListDelecate(SeqList* ps, int pos);以上函数的形参均是SeqList*类型的因为我是将上述函数放在测试函数中进行测试因此需要指针作为形式参数如果形参是SeqList类型则形参的改变不会影响实参即顺序表的数据不会收到改变
⭐️3.2 初始化
初始化函数形参定义为顺序表类型的指针SeqList* ps 为了让顺序表类型SL变量有意义先将SL的a成员赋值为NULLcapacity size成员赋值为0 void SeqListInit(SeqList* ps)
{ps-a NULL;ps-capcity ps-size 0;
⭐️3.3 扩容 当容量满了后顺序表选择将容量扩成原来最大容量的2倍这样既不会浪费太多空间也不会扩容太频繁,事实上随着扩容的次数逐渐增多一次扩容所产生的空间逐渐增加 扩容需要使用realloc函数 注当memblock是NULL时realloc会进行malloc的操作 void SeqListCheckcapacity(SeqList* ps)
{if (ps-size ps-capacity) //有效数据的个数和最大容量相等时需要扩容{ps-capacity ps-capacity 0 ? 4 : 2 * ps-capacity;//一开始将最大容量设置为4后面扩成2倍ps-a (SeqListDataType*)realloc(ps-a, sizeof(SeqListDataType) * ps-capacity);assert(ps);}
}⭐️3.4 打印
注意打印的个数是有效数据的个数而不是最大容量
void SeqListPrint(SeqList* ps)
{for (int i 0; i ps-size; i) //打印有效数据{printf(%d , ps-a[i]);}printf(\n);
}⭐️3.5 尾插
因为size标记的就是顺序表的尾部所以尾插较简单只需要将a[size]赋值为插入的元素
void SeqListPushBack(SeqList* ps, int pos)
{//当顺序表的容量满了SeqListCheckcapacity(ps);ps-a[ps-size] pos;ps-size;//有效数据1
}
⭐️3.6 头插
头插需要将所有的数据从前往后移动并且保证挪动方向是[size-1]-[size],[size-2]-[size-1]……
void SeqListPushFront(SeqList* ps, int pos)
{SeqListCheckcapacity(ps);size_t cnt 0;while (cnt ps-size)//有多少个有效数据移动多少次{ps-a[ps-size - cnt] ps-a[ps-size - 1 - cnt];cnt;}ps-a[0] pos;ps-size;
}⭐️3.7 尾删
尾删很简单只需要将有效数据的个数-1即可即使该数据在动态开辟的数组中但是不在有效数据范围内最后也不会打印
void SeqListPopBack(SeqList* ps)
{assert(ps-size);//注意当有效数据为0时不能够删数据ps-size--;
}⭐️3.8 头删
头删和头差类似都需要挪动其他的有效数据头删时挪动方向是从后往前挪并且保证最开始是[1]-[0],[2]-[1]……
void SeqListPopFront(SeqList* ps)
{assert(ps-size);size_t begin 1;while (begin ps-size - 1)//size个有效数据移动size-1次{ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
⭐️3.9 指定插入
有效数据元素为4时插入到下标pos为2的位置需要挪动数据3次 size越大挪动的次数越多pos越小挪动的次数越多因此在有效数据为size的数组中将数据差到pos位置需要挪动数据size-pos1次挪动方向[size-1]-[size],[size-2]-[size-1]……
void SeqListInsert(SeqList* ps, int pos, SeqListDataType data)
{assert(pos 1 pos ps-capacity);//判断插入的位置是否合法SeqListCheckcapacity(ps);size_t cnt 0;//一共循环size1-pos次while (cnt ps-size - pos 1){ps-a[ps-size - cnt] ps-a[ps-size - 1 - cnt];cnt;}ps-a[pos - 1] data;ps-size;//有效数据1
}⭐️3.10 指定删除
4个有效数据删除位置为2的元素需要挪动数据2次 推测size个有效数据删除位置为pos的元素需要挪动数据size-pos次,挪动方向[pos]-[pos-1],[pos1]-[pos]……
void SeqListDelecate(SeqList* ps, int pos)
{assert(ps-size);assert(pos 0 pos ps-size);//一共循环size-pos次while (pos ps-size){ps-a[pos - 1] ps-a[pos];pos;}ps-size--;
}⭐️3.11 查找
查找很简单直接遍历
void SeqListFind(SeqList* ps, int key)
{for (size_t i 0; i ps-size; i){if (key ps-a[i]){printf(The pos is %d\n, i 1);return;}}printf(Fail Find!\n);
}3.12 注意事项
凡是插入时需要使用assert来判断插入位置是否合法插入数据时有效数据的个数需要1删除数据时有效数据的个数需要-1
4. 顺序表的缺点
中间/头部的插入删除时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
针对顺序表的缺陷我们研究出了链表链表可以弥补顺序表得缺点我们下次内容来研究如何实现链表
