顺序表基本操作_顺序表的插入

---

1. 顺序表插入元素

向顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：

• 插入到顺序表的表头；
• 在表的中间位置插入元素；
• 尾随顺序表中已有元素，作为顺序表中的最后一个元素；

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

• 将要插入位置元素以及后续的元素整体向后移动一个位置；
• 将元素放到腾出来的位置上；

例如，在 {1,2,3,4,5} 的第 3 个位置上插入元素 6，实现过程如下：

1. 找到目标元素位置：遍历至顺序表存储第 3 个数据元素的位置
   
2. 移动元素，将插入位置腾出：将元素 3 以及后续元素 4 和 5 整体向后移动一个位置
   
3. 将新元素 6 插入到腾出的位置：
   

因此，顺序表插入数据元素的 C 语言实现代码如下：

//插入函数，其中elem为插入的元素，position为插入到顺序表的位置
SqList ListInsert(SqList L, int elem, int position)
{
    //判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出）
    if((position > L.length + 1) || (position < 1))
    {
        printf("插入位置有问题");
        return L;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if(L.length == L.size)
    {
        L.head = (int *)realloc(L.head, (L.size + 1) * sizeof(int));
        if(L.head == NULL)
        {
            printf("存储分配失败\n");
            return L;
        }
        L.size++;
    }
    //插入操作，需要将从插入位置开始的后续元素，逐个后移
    for(int i = L.length - 1; i >= position - 1; i--)
    {
        L.head[i+1] = L.head[i];
    }
    //后移完成后，直接将所需插入元素，添加到顺序表的相应位置
    L.head[position - 1] = elem;
    //由于添加了元素，所以长度+1
    L.length++;
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

2. 顺序表删除元素

从顺序表中删除指定元素，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。

后续元素整体前移一个位置，会直接将目标元素的值覆盖，可间接实现删除元素的目的

例如，从 {1,2,3,4,5} 中删除元素 3 的过程如图所示：

因此，顺序表删除元素的 C 语言实现代码为：

 SqList ListDelete(SqList L, int position)
{
    if((position > L.length) || (position < 1))
    {
        printf("被删除元素的位置有误\n");
        return L;
    }
    for(int i = position; i < L.length; i++)
    {
        L.head[i-1] = L.head[i];
    }
    L.length--;
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

3. 顺序表查找元素

顺序表中查找目标元素就是遍历顺序表看是否存在元素和目标元素相等。C语言实现代码为：

//查找函数，其中，elem表示要查找的数据元素的值
int LocateElem(SqList L, int elem)
{
    for(int i = 0; i < L.length; i++)
    {
        if(L.head[i] == elem)
        {
            return i + 1;
        }
    }
    //如果查找失败，返回-1
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

4. 顺序表更改元素

顺序表更改元素的实现过程是：

1. 找到目标元素；
2. 直接修改该元素的值；

//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
SqList ListModify(SqList L, int OldElem, int NewElem)
{
    int position = LocateElem(L, OldElem);
    L.head[position - 1] = NewElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
    return L;
}
1
2
3
4
5
6
7

---

以上是顺序表使用过程中最常用的基本操作，如下是C语言完整代码清单：

#include<stdio.h>
#include<stdlib.h>

#define SIZE 5  //对SIZE进行宏定义，表示顺序表申请空间的大小
typedef struct List
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
}SqList;

SqList InitList();
SqList ListInsert(SqList L, int elem, int position);
SqList ListDelete(SqList L, int position);
int LocateElem(SqList L, int elem);
SqList ListModify(SqList L, int OldElem, int NewElem);
void DisplayList(SqList L);

int main()
{
    SqList L = InitList();
    for (int i=0; i < SIZE; i++) 
    {
        L.head[i] = (i + 1);
        L.length++;
    }
    printf("原顺序表：\n");
    DisplayList(L);
  
    printf("删除元素1:\n");
    L = ListDelete(L, 1);
    DisplayList(L);
  
    printf("在第2的位置插入元素5:\n");
    L = ListInsert(L, 5, 2);
    DisplayList(L);
  
    printf("查找元素3的位置:\n");
    int position = LocateElem(L, 3);
    printf("%d\n", position);
  
    printf("将元素3改为6:\n");
    L = ListModify(L, 3, 6);
    DisplayList(L);
    return 0;
}

SqList InitList()
{
    SqList L;

    L.head = (int*)malloc(SIZE * sizeof(int));  //构造一个空的顺序表，动态申请存储空间
    
    if(!(L.head))   //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }

    L.size = SIZE; //空表的初始存储空间为SIZE
    L.length = 0;   //空表的长度初始化为0

    return L;
}

//插入函数，其中，elem为插入的元素，position为插入到顺序表的位置
SqList ListInsert(SqList L, int elem, int position)
{
    //判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出）
    if((position > L.length + 1) || (position < 1))
    {
        printf("插入位置有问题");
        return L;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if(L.length == L.size)
    {
        L.head = (int*)realloc(L.head, (L.size + 1) * sizeof(int));
        if(L.head == NULL)
        {
            printf("存储分配失败\n");
            return L;
        }
        L.size++;
    }
    //插入操作，需要将从插入位置开始的后续元素，逐个后移
    for(int i = L.length - 1; i >= position - 1; i--)
    {
        L.head[i+1] = L.head[i];
    }
    //后移完成后，直接将所需插入元素，添加到顺序表的相应位置
    L.head[position - 1] = elem;
    //由于添加了元素，所以长度+1
    L.length++;
    return L;
}

SqList ListDelete(SqList L, int position)
{
    if((position > L.length) || (position < 1))
    {
        printf("被删除元素的位置有误\n");
        return L;
    }
    for(int i = position; i < L.length; i++)
    {
        L.head[i-1] = L.head[i];
    }
    L.length--;
    return L;
}

//查找函数，其中，elem表示要查找的数据元素的值
int LocateElem(SqList L, int elem)
{
    for(int i = 0; i < L.length; i++)
    {
        if(L.head[i] == elem)
        {
            return i + 1;
        }
    }
    //如果查找失败，返回-1
    return -1;
}

//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
SqList ListModify(SqList L, int OldElem, int NewElem)
{
    int position = LocateElem(L, OldElem);
    L.head[position - 1] = NewElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
    return L;
}

//输出顺序表中元素的函数
void DisplayList(SqList L)
{
    for(int i = 0; i < L.length; i++)
    {
        printf("%d ", L.head[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

程序运行结果为：

原顺序表：
1 2 3 4 5
删除元素1:
2 3 4 5
在第2的位置插入元素5:
2 5 3 4 5
查找元素3的位置:
3
将元素3改为6:
2 5 6 4 5