顺序表插入和删除(数据结构与算法)

您所在的位置：网站首页 › 顺序表的实现步骤 › 顺序表插入和删除(数据结构与算法)

顺序表插入和删除(数据结构与算法)

2024-06-07 01:28| 来源: 网络整理| 查看: 265

二、顺序表插入和删除(数据结构) 1. 顺序表的基本操作----插入顺序表是一种数据结构，其元素在内存中连续存储，并且可以使用下标直接访问每个元素。在顺序表中插入或删除元素时，需要移动后续元素的位置以保持顺序表的有序性。对于在下标位置i处插入值为x的元素，需要将下标为i~n-1的所有元素向右移动一个位置，然后将x插入到位置i的元素中。对于删除操作，需要将下标为i+1~n-1的所有元素向左移动一个位置，然后将下标为n-1的元素置空。需要注意的是，当动态扩展顺序表时，需要重新分配内存空间，因为当前内存空间可能已经被占满了。同时，为了减少多次扩充内存空间的开销，可以考虑一次性分配更大的内存空间。

在这里插入图片描述

#define MaxSize 10 //定义最大长度 typedef struct { int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义 void ListInsert(SqList &L, int i, int e)//在顺序表L的位序i处插入元素e { 。 //j大于等于3时，循环一直继续，data[4]放到data[5],data[3]放到data[4]统统后移一位。 for (int j = L.length; j >= i; j--) //将第i个元素及之后的元素后移 L.data[j] = L.data[j-1]; //插入位置后的元素后移，给插入位置腾出空间 L.data[i-1] = e; //在位置i处放入e，位序为3处插入，则在数组(从0开始数)中表示第3-1位置处。 L.length++; //长度加1 } int main() { SqList L; //声明一个顺序表 InitList(L); //初始化顺序表 //.......插入几个元素假设插入1 2 4 5 6五个元素，则length = 5 ListInsert(L, 3, 3);//往第3个位置插入数据元素3 ---- 1 2 e 4 5 6 位序3后的元素4 5 6后移 return 0; } 注意位序、数组下标的关系，并从后面的元素依次移动。在这里插入图片描述

注意：顺序表长度为5，在位序3处插入一个元素e,长度变为6。如上图所示，顺序表中各个数据元素必须是连续相邻的，而data[6]~data[9]之间都是空的，若此时要在位序9处插入元素3：**ListInsert(L, 9, 3);**是错误的操作。这样的话data[6]、data[7]中是空的，为无效操作，即这段代码是不够健壮的。此时可以加入条件判断语句。判断i的值是否合法，i 的合法值范围应该是 [1, length+1]。如果有人想往第九个位置插入元素，那么 i 的值超出合法范围。检查顺序表是否已经存满了，如果已满，那也不应该继续插入元素。

可以给代码加入反馈，判断插入操作是否满足当前条件，并给出反馈：

bool ListInsert(SqList &L, int i, int e) { if (i = MaxSize) //当前存储空间已满，不能插入 return false; for (int j = L.length; j > i; j--) //将第i个元素及之后的元素后移一位 L.data[j] = L.data[j-1]; L.data[i - 1] = e; //在位置i处放入e L.length++; //添加一个元素，长度加 1 return true; //好的算法，应该具有“健壮性” 能处理异常情况，并给使用者反馈

如下图：顺序表长度已满，不能再插入数据元素。在这里插入图片描述

插入操作的时间复杂度：最好、最坏、平均

在这里插入图片描述

2. 顺序表的基本操作-----删除

注意位序、数组下标的关系，并从前面的元素依次移动，思考如果参数没有引用会怎么样？加入引用，是为了确保将ListDelete()函数与main函数中的操作的相同数据类型如变量e，L在同一内存空间中，所对应的是同一份数据，而不是其中一方的复制体。

bool ListDelete(SqList &L, int i, int &e) //使用&e,则其与main函数中变量e在内存当中对应的是同一份数据。 { if (i L.length) //判断i的范围是否有效 return false； e = L.data[i - 1]; //将被删除的元素赋值给e for(int j = i; j

【本文地址】

顺序表插入和删除(数据结构与算法)

顺序表插入和删除(数据结构与算法)

今日新闻

推荐新闻