视频转动图在线制作网站,免费的招聘网站,网络工程师好学吗,地推公司在C语言学习中#xff0c;我们经常会遇见增删查改等一系列操作#xff0c;而这些操作全都与线性表关联#xff0c;没有线性表将会对这些操作完成的十分艰难#xff01;那今天就让我们来了解一下顺序表如何增删查改#xff01;#xff01;#xff01;
目录
1.线性表
2…在C语言学习中我们经常会遇见增删查改等一系列操作而这些操作全都与线性表关联没有线性表将会对这些操作完成的十分艰难那今天就让我们来了解一下顺序表如何增删查改
目录
1.线性表
2.顺序表
2.1概念及结构
3.对顺序表的实现
3.1创建动态内容结构体
3.2内存销毁 3.3判断是否需要扩容
3.4尾插
3.5头插
3.6 尾删
3.7头删 3.8 顺序表查找
3.9 顺序表在pos位置插入x
3.10 顺序表删除pos位置的值
顺序表的问题及思考 1.线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储 2.顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素 确定的数组是不能改变的 2.动态顺序表使用动态开辟的数组存储 通过存放一个结构体指针使用动态内存开辟malloc函数开辟空间 如果空间不够用可以使用realloc函数进行扩容 3.对顺序表的实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空 间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间 大小所以下面我们实现动态顺序表。
3.1创建动态内容结构体
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SL;array是动态内存开辟的数组指针指向开辟的首元素地址。 size是记录存储有效内容的数据个数方便统计。 capicity是记录容量大小方便与size进行比较用来判断是否需要扩容。 我们使用typedef将int重命名为SLDataType将结构体命名为SL。 3.2对结构体进行初始化
//第一种方法
void SeqListInit(SL* ps)
{ps-a (SLDateType*)malloc(sizeof(SLDateType) * 4);if (ps-a NULL){perror(malloc);exit(-1);}ps-size 0;ps-capacity 4;
}
//第二种方法
void SeqListInit(SL s)
{s.a NULL;s.size 0;s.capacity 0;
}
第二种方法是直接将结构体的内容传给函数形参只是实参的一份临时拷贝形参的改变不会影响实参所以第二种方法是错误的
当我们使用第一种方法初始化时我们就可以适当的开辟一点空间如何使用malloc开辟空间在之前的博客中有所讲解http://t.csdn.cn/038La。如果开辟失败我们就直接退出程序exit(-1)。
3.2内存销毁
在我们使用动态内存开辟后一定要及时释放空间并置为NULL否则会出现内存泄漏等大问题
void SeqListDestroy(SL* ps)
{free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0;
}3.3判断是否需要扩容
在顺序表的增删查改中我们时不时需要判断存入的数据是否已满需不需要扩容。所以我们为了方便使用此功能避免程序冗余我们可以创建此函数用来判断开辟的内存是否需要扩容。
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){SLDateType* p (SLDateType*)realloc(ps-a, sizeof(ps-a) * 2);if (*p NULL){perror(realloc);exit(-1);}ps-capacity * 2;ps-a p;}
}
传入结构体指针判断size与capacity是否相等如果相等我们就使用realloc函数进行扩容我们创建新指针指向新创建的空间开辟比原来大二倍的空间。如果开辟成功我们将更新capacity的值开辟失败直接退出程序
3.4尾插
void SeqListPushBack(SL* ps, SLDateType x)
{SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
} 先使用函数SLCheckCapacity进行判断是否需要进行扩容在进行尾部插入即可。
3.5头插
将需要的数据在顺序表的头部进行插入对于顺序表而言效率会非常低但是我们也必须将其实现。
void SeqListPushFront(SL* ps, SLDateType x)
{SLCheckCapacity(ps);for (int i ps-size; i 0; i--){ps-a[i] ps-a[i-1];}ps-a[0] x;ps-size;
} 3.6 尾删
尾删非常的简单我们只需要将数组往前移动一位size--即可。我们不必担心数据问题下次再次使用时只需要将内容覆盖即可。
void SeqListPopBack(SL* ps)
{assert(ps-size 0);ps-size--;
}
但是在删除时我们得判断顺序表中内容是否为空防止数组越界。我们使用assert断言函数进行判断即可。
3.7头删
头删与头插的效率都很低下这也是顺序表的一个大缺点。基本原理与头插差不多时间复杂度都为O(n)牵一发而动全身。
void SeqListPopFront(SL* ps)
{assert(ps-size 0);for (int i 0; i ps-size-1; i){ps-a[i] ps-a[i 1];}ps-size--;
}
删除时我们必须判断数组是否为空防止越界。从前向后进行迭代前移进行覆盖最后将size--即可。 3.8 顺序表查找
为了让我们方便查找顺序表中每个内容的具体位置然后插入想插入的数据。我们创建一个寻找下标的函数。
int SeqListFind(SL* ps, SLDateType x)
{assert(ps-size 0);for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}elsereturn -1;
}
我们使用暴力查找法将数组遍历一遍如果能找到则返回其下标如果找不到则返回-1结束。
3.9 顺序表在pos位置插入x
我们使用3.8中的函数将需要插入位置找到然后使用此函数将其插入到顺序表中。
void SeqListInsert(SL* ps, int pos, SLDateType x)
{assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}
中间插入前面的数据不需要移动在pos后的位置要向后移动。
3.10 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos)
{assert(ps-size 0);for (int i pos - 1; i ps-size-1; i){ps-a[i] pos-a[i 1];}ps-size--;
}
与插入原理相同pos后的内容向前一位即可。
顺序表的问题及思考
问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。 我们可以使用链表解决以上问题下一期我们将走进链表章节。
欲知后事如何尽情期待下一期
