数据结构与算法基础-学习-02-线性表之顺序表-插入元素、删除元素

一、测试环境

名称	值
cpu	12th Gen Intel® Core™ i7-12700H
操作系统	CentOS Linux release 7.9.2009 (Core)
内存	3G
逻辑核数	2
gcc 版本	4.8.5 20150623

二、小发现

1、顺序表插入元素效率

顺序表插入的元素如果在首位，需要把所有的元素向后移动一位，和链表在插入元素效率上有一定差距。

2、顺序表定位元素效率

顺序表定位元素，可以根据索引号直接定位元素，而链表需要依次遍历比较，才可以定位想要的元素。

3、顺序表删除元素效率

顺序表删除的元素如果在首位，需要把所有的元素向前移动一位，比较耗时。如果删除元素在尾部，不需要移动其他数据，效率较高。但和链表在删除元素效率上有一定差距。

三、函数介绍

1、InsertOrderTableElem

（1）函数定义

Status InsertOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType VarElem)
{
    JudgePointerNull(OrderTablePointer);
    printf("ElemPosition : %d, VarElem : %c ,",ElemPosition,VarElem);
    if(ElemPosition < 1 || ElemPosition > OrderTablePointer->ElemArrayLen + 1)
    {
        printf("Error ElemPosition : %d, Need 1 <= ElemPosition <= %d\n",ElemPosition,OrderTablePointer->ElemArrayLen + 1);
        PrintPretty();
        return FailFlag;
    }
    if(OrderTablePointer->ElemArrayLen == ElemArrayMaxLen)
    {
        printf("ElemArrayLen Is Full, Can't Insert Data\n");
        PrintPretty();
        return FailFlag;
    }
    int i;
    for(i = OrderTablePointer->ElemArrayLen - 1; i >= ElemPosition - 1; i--)
    {
        OrderTablePointer->ElemArray[i+1] = OrderTablePointer->ElemArray[i];
    }
    OrderTablePointer->ElemArray[ElemPosition-1] = VarElem;
    OrderTablePointer->ElemArrayLen++;
    printf("Insert Data Success\n");
    PrintPretty();
    return SuccessFlag;
}
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

（2）参数说明

参数名	说明
OrderTablePointer	需要插入的顺序表。
ElemPosition	插入的位置，大于等于1，小于等于当前列表最大长度加一。
VarElem	需要插入的元素。

2、DeleteOrderTableElem

（1）函数定义

Status DeleteOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType *DelVarElem)
{
    JudgePointerNull(OrderTablePointer);
    *DelVarElem = OrderTablePointer->ElemArray[ElemPosition - 1];
    printf("ElemPosition : %d, DelVarElem : %c ,",ElemPosition,*DelVarElem);
    if(ElemPosition < 1 || ElemPosition > OrderTablePointer->ElemArrayLen)
    {
        printf("Error ElemPosition : %d, Need 1 <= ElemPosition <= %d\n",ElemPosition,OrderTablePointer->ElemArrayLen);
        PrintPretty();
        return FailFlag;
    }
    int i;
    for(i = ElemPosition - 1; i < OrderTablePointer->ElemArrayLen - 1; i++)
    {
        OrderTablePointer->ElemArray[i] = OrderTablePointer->ElemArray[i + 1];
    }
    OrderTablePointer->ElemArray[OrderTablePointer->ElemArrayLen - 1] = '\0';
    OrderTablePointer->ElemArrayLen--;
    printf("Delete Data Success\n");
    PrintPretty();
    return SuccessFlag;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（2）参数说明

参数名	说明
OrderTablePointer	需要删除的顺序表。
ElemPosition	删除的位置，大于等于1，小于等于当前列表最大长度。
VarElem	返回ElemPosition位置删除的元素。

四、测试代码

1、LinearTable_OrderTable.c

#include 
#include 
#include 
#include "LinearTable_OrderTable.h"

void PrintPretty()
{
    printf("*********************************\n");
}

void *MyMalloc(size_t size)
{
    void *Result = (void *)malloc(size);
    if(Result == NULL)
    {
        printf("malloc Function Exec Fail , Out Of Memory ,Exit!!!\n");
        exit(ExceptionExitFlag);
    }
    return Result;
}

void JudgePointerNull(OrderTable *OrderTablePointer)
{
    if(OrderTablePointer == NULL)
    {
        printf("Pointer Is Null ,Exit !\n");
        exit(ExceptionExitFlag);
    }
}

Status InitOrderTable(OrderTable *OrderTablePointer)
{
    printf("Start Init List\n");
    JudgePointerNull(OrderTablePointer);
    OrderTablePointer->ElemArray    = (ElemType *)MyMalloc(sizeof(ElemType) * ElemArrayMaxLen);
    memset(OrderTablePointer->ElemArray, '\0', sizeof(ElemType) * ElemArrayMaxLen);
    OrderTablePointer->ElemArrayLen = 0;
    printf("Init List Success !!!\n");
    PrintPretty();
    return SuccessFlag;
}

void DestroyOrderTable(OrderTable *OrderTablePointer)
{
    printf("Start Destroy List\n");
    JudgePointerNull(OrderTablePointer);
    free(OrderTablePointer->ElemArray);
    OrderTablePointer->ElemArray = NULL;
    free(OrderTablePointer);
    OrderTablePointer = NULL;

    printf("Destroy List Success !!!\n");
    PrintPretty();
}

void PrintOrderTable(OrderTable *OrderTablePointer)
{
    printf("Print List\n");
    JudgePointerNull(OrderTablePointer);
    int i;
    printf("ElemArray    : ");
    for(i=0; i<ElemArrayMaxLen -1; i++)
    {
        printf("%c ,",OrderTablePointer->ElemArray[i]);
    }
    printf("%c \n",OrderTablePointer->ElemArray[i]);
    printf("ElemArrayLen : %d\n",OrderTablePointer->ElemArrayLen);
    PrintPretty();
}

void ClearOrderTable(OrderTable *OrderTablePointer)
{
    printf("Clear Order Table\n");
    JudgePointerNull(OrderTablePointer);
    OrderTablePointer->ElemArrayLen = 0;
    PrintPretty();
}

int GetOrderTableLen(OrderTable *OrderTablePointer)
{
    JudgePointerNull(OrderTablePointer);
    printf("Get ElemArray Len : %d\n",OrderTablePointer->ElemArrayLen);
    PrintPretty();
    return OrderTablePointer->ElemArrayLen;
}

int JudgeOrderTableIsEmpty(OrderTable *OrderTablePointer)
{
    JudgePointerNull(OrderTablePointer);
    if(OrderTablePointer->ElemArrayLen == 0)
    {
        printf("Order Table Is Empty\n");
        PrintPretty();
        return SuccessFlag;
    }
    else
    {
        printf("Order Table Is Not Empty\n");
        PrintPretty();
        return FailFlag;
    }
}

// VarElem传入参数必须是malloc的，如果不是会出现段错误。
int GetOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType *VarElem)
{
    JudgePointerNull(OrderTablePointer);
    if(ElemPosition < 1 || ElemPosition > OrderTablePointer->ElemArrayLen)
    {
        printf("Error ElemPosition : %d, Need 1 <= ElemPosition <= ElemArrayLen(%d)\n",ElemPosition,OrderTablePointer->ElemArrayLen);
        PrintPretty();
        return FailFlag;
    }
    
    *VarElem = OrderTablePointer->ElemArray[ElemPosition-1];
    printf("ElemPosition : %d ,Elem : %c , Get Data Success\n",ElemPosition,*VarElem);
    PrintPretty();
    return SuccessFlag;
}

int LocateOrderTableElem_V1(OrderTable *OrderTablePointer, ElemType SelectElem)
{
    JudgePointerNull(OrderTablePointer);
    int i;
    for(i = 0; i < OrderTablePointer->ElemArrayLen; i++)
    {
        if(SelectElem == OrderTablePointer->ElemArray[i])
        {
            printf("Position : %d, Locate Order Table Elem Success\n",i+1);
            PrintPretty();
            return i + 1;
        }
    }
    printf("Locate Order Table Elem Fail!!!\n");
    PrintPretty();
    return FailFlag;
}

Status InsertOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType VarElem)
{
    JudgePointerNull(OrderTablePointer);
    printf("ElemPosition : %d, VarElem : %c ,",ElemPosition,VarElem);
    if(ElemPosition < 1 || ElemPosition > OrderTablePointer->ElemArrayLen + 1)
    {
        printf("Error ElemPosition : %d, Need 1 <= ElemPosition <= %d\n",ElemPosition,OrderTablePointer->ElemArrayLen + 1);
        PrintPretty();
        return FailFlag;
    }
    if(OrderTablePointer->ElemArrayLen == ElemArrayMaxLen)
    {
        printf("ElemArrayLen Is Full, Can't Insert Data\n");
        PrintPretty();
        return FailFlag;
    }
    int i;
    for(i = OrderTablePointer->ElemArrayLen - 1; i >= ElemPosition - 1; i--)
    {
        OrderTablePointer->ElemArray[i+1] = OrderTablePointer->ElemArray[i];
    }
    OrderTablePointer->ElemArray[ElemPosition-1] = VarElem;
    OrderTablePointer->ElemArrayLen++;
    printf("Insert Data Success\n");
    PrintPretty();
    return SuccessFlag;
}

Status DeleteOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType *DelVarElem)
{
    JudgePointerNull(OrderTablePointer);
    *DelVarElem = OrderTablePointer->ElemArray[ElemPosition - 1];
    printf("ElemPosition : %d, DelVarElem : %c ,",ElemPosition,*DelVarElem);
    if(ElemPosition < 1 || ElemPosition > OrderTablePointer->ElemArrayLen)
    {
        printf("Error ElemPosition : %d, Need 1 <= ElemPosition <= %d\n",ElemPosition,OrderTablePointer->ElemArrayLen);
        PrintPretty();
        return FailFlag;
    }
    int i;
    for(i = ElemPosition - 1; i < OrderTablePointer->ElemArrayLen - 1; i++)
    {
        OrderTablePointer->ElemArray[i] = OrderTablePointer->ElemArray[i + 1];
    }
    OrderTablePointer->ElemArray[OrderTablePointer->ElemArrayLen - 1] = '\0';
    OrderTablePointer->ElemArrayLen--;
    printf("Delete Data Success\n");
    PrintPretty();
    return SuccessFlag;
}

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

2、 LinearTable_OrderTable.h

#ifndef LinearTable_OrderTable_H
#define LinearTable_OrderTable_H

#define ExceptionExitFlag -1
#define SuccessFlag        1
#define FailFlag           0
#define ElemArrayMaxLen   10

typedef int Status;
typedef char ElemType;
typedef struct 
{
    ElemType *ElemArray;
    int      ElemArrayLen;
}OrderTable;

void *MyMalloc(size_t size);
void PrintOrderTable(OrderTable *OrderTablePointer);
Status InitOrderTable(OrderTable *OrderTablePointer);
void DestroyOrderTable(OrderTable *OrderTablePointer);
void JudgePointerNull(OrderTable *OrderTablePointer);
void ClearOrderTable(OrderTable *OrderTablePointer);
int GetOrderTableLen(OrderTable *OrderTablePointer);
int JudgeOrderTableIsEmpty(OrderTable *OrderTablePointer);
int GetOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType *VarElem);
int LocateOrderTableElem_V1(OrderTable *OrderTablePointer, ElemType SelectElem);
Status InsertOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType VarElem);
Status DeleteOrderTableElem(OrderTable *OrderTablePointer, int ElemPosition, ElemType *DelVarElem);

void PrintPretty();

#endif

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

3、main.c

#include 
#include 
#include 
#include "LinearTable_OrderTable.h"

int main()
{
    //ElemType *VarElem   = (ElemType *)MyMalloc(sizeof(ElemType));
    ElemType VarElem       = '\0';
    ElemType DelVarElem    = '\0';
    ElemType SelectElem    = 'A';
    int i;

    OrderTable *TestData = (OrderTable *)MyMalloc(sizeof(OrderTable));;
    InitOrderTable(TestData);
    for(i = 65; i <= 74; i++)
    {
        InsertOrderTableElem(TestData, 1, i);
    }
    PrintOrderTable(TestData);
    JudgeOrderTableIsEmpty(TestData);
    GetOrderTableElem(TestData, 1, &VarElem);
    LocateOrderTableElem_V1(TestData, SelectElem);
    DeleteOrderTableElem(TestData, 1, &DelVarElem);
    DeleteOrderTableElem(TestData, GetOrderTableLen(TestData), &DelVarElem);
    DeleteOrderTableElem(TestData, GetOrderTableLen(TestData) / 2, &DelVarElem);
    ClearOrderTable(TestData);
    PrintOrderTable(TestData);
    DestroyOrderTable(TestData);

    //free(VarElem);
    //VarElem = NULL;  
    return SuccessFlag;
}

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

4、makefile

CC = gcc
CFLAG_EXEC = -Wall -g
CFLAG_ALIAS = -o
RM_COMM = rm -rf

all : main

main : 
        $(CC) $(CFLAG_EXEC) LinearTable_OrderTable.c main.c $(CFLAG_ALIAS) Test_LinearTable_OrderTable 

clean : 
        $(RM_COMM) Test_LinearTable_OrderTable
1
2
3
4
5
6
7
8
9
10
11
12

五、编译运行

[gbase@czg2 LinearTable_OrderTable]$ make clean
rm -rf Test_LinearTable_OrderTable

[gbase@czg2 LinearTable_OrderTable]$ make
gcc -Wall -g LinearTable_OrderTable.c main.c -o Test_LinearTable_OrderTable 

[gbase@czg2 LinearTable_OrderTable]$ ./Test_LinearTable_OrderTable 
Start Init List
Init List Success !!!
*********************************
ElemPosition : 1, VarElem : A ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : B ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : C ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : D ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : E ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : F ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : G ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : H ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : I ,Insert Data Success
*********************************
ElemPosition : 1, VarElem : J ,Insert Data Success
*********************************
Print List
ElemArray    : J ,I ,H ,G ,F ,E ,D ,C ,B ,A 
ElemArrayLen : 10
*********************************
Order Table Is Not Empty
*********************************
ElemPosition : 1 ,Elem : J , Get Data Success
*********************************
Position : 10, Locate Order Table Elem Success
*********************************
ElemPosition : 1, DelVarElem : J ,Delete Data Success
*********************************
Get ElemArray Len : 9
*********************************
ElemPosition : 9, DelVarElem : A ,Delete Data Success
*********************************
Get ElemArray Len : 8
*********************************
ElemPosition : 4, DelVarElem : F ,Delete Data Success
*********************************
Clear Order Table
*********************************
Print List
ElemArray    : I ,H ,G ,E ,D ,C ,B , , , 
ElemArrayLen : 0
*********************************
Start Destroy List
Destroy List Success !!!
*********************************
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

相关阅读:
数仓的等待视图中，为什么会有Hashjoin-nestloop
Oracle/PLSQL: Corr Function
【Spring】Spring的AspectJ的AOP
element ui框架（准备）
uni-app:实现右侧弹窗
 PHP会话技术跟踪和记录用户？使用cookie会话你必须掌握
 西门子PLC S7-200和S7-300有什么差别？如何进行远程上下载？
【云原生 • Docker】docker 环境搭建、docker 与容器常用指令大全
 PieCloudDB Database 3.0 正式发布丨数仓虚拟化技术为数据要素流转注入创新动能
 JavaScript中的多种进制与进制转换
原文地址：https://blog.csdn.net/qq_45111959/article/details/128014943