线性表——C语言顺序表的基本操作（静态分配）_c语言对线性表的顺序存储结构进行基本操作

线性表的基本操作

参考 严蔚敏《数据结构（C语言版）》及《2024王道数据结构复习指导》

本文介绍顺序表的基本操作并附C++代码（仅使用C++的引用，其他模块均使用C语言）
符号"&"表示C++的引用调用，在C语言种采用指针也可以达到同样的效果。使用引用&可以使代码具有更强的可读性。

C++引用&简要说明

简单来说，当需要在函数内改变原本的线性表或值时，则需要使用引用，例如：初始化线性表、线性表的插入操作、删除操作和销毁操作（&L，&e）。当不需要改变原本的线性表时，则不需要使用引用，例如：线性表的输出和查找操作。

InitList(&L) //初始化顺序表。构造一个空的顺序表
Length(L) //求表长。返回顺序表L的长度
LocateElem(L, e) //查找：按值查找操作
GetElem(L, i) //查找：按位查找操作
ListInsert(&L, i, e) //插入操作。在顺序表第i个位置上插入指定元素e
ListDelete(&L, i, &e) //删除顺序表L中第i个位置的元素，并用e返回删除元素的值
PrintList(L) //顺序表的输出
Empty(L) //判空操作。若L为空表，返回true；否则，返回false
DestroyList(&L) //销毁操作。销毁顺序表并释放顺序表L所占用的内存空间
1
2
3
4
5
6
7
8
9

顺序表的定义

线性表的顺序存储称为顺序表。它用一组地址连续的存储单元依次存储线性表种的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的存储结构

顺序表的存储结构定义可以使用静态分配和动态分配两种方式。
静态分配直接固定数组的大小和空间，一旦数据空间占满，再加入新的数据就会产生溢出，进而导致程序错误。
动态分配在结构体种定义指示动态分配数组的指针，存储数组的空间在程序执行过程中通过动态存储分配语句malloc分配，一旦数组空间占满，就另外开辟一块更大的存储空间替换原来的存储空间，达到扩充存储数组空间的目的。但本质上还是相同的，使用一段连续的存储空间。

静态分配和动态分配的区别：

• 静态分配的顺序表存储在栈空间中；
• 动态分配的顺序表存储在堆空间中。

顺序表的静态分配定义

#define MaxSize 50   //定义顺序表的最大长度
typedef int ElemType;//ElemType表示元素类型，为了让顺序表存储其他类型元素时可以快速完成代码修改
typedef struct {
    ElemType data[MaxSize];
    int length;//顺序表长度
}SqList;
1
2
3
4
5
6

顺序表的动态分配定义

#define InitSize 100  //表长的初始定义
typedef int ElemType;
typedef struct{
	ElemType *data; //指示动态分配数组的指针
	int MaxSize, length; //数组的最大容量和当前长度
}SeqList;
1
2
3
4
5
6

【注】：一般考试中大多数采用顺序表的静态存储结构，本文中顺序表的基本操作基于静态分配的存储结构实现。

顺序表的插入

//顺序表的插入，因为L会改变，因此要用引用
bool ListInsert(SqList &L, int i, ElemType elemType)
{
    //判断i的范围是否合法 i>=1 && i<=L.length+1
    if(i<1 || i>L.length+1)
        return false;
    //如果存储空间满了就不能插入
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length; j>=i; j--)
    {
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = elemType;//放入插入的元素
    L.length++;//顺序表长度加一
    return true;//插入成功返回true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

顺序表的删除

//删除顺序表中的元素，i是要删除元素的位置，e是为了获取被删除元素的值
bool ListDelete(SqList &L, int i, ElemType &e)
{
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];//首先保存被删除元素的值
    for(int j=i;j<L.length;j++)//j=i-1;j<L.length-1;j++ L.data[j]=L.data[j+1]
    {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

打印顺序表

//打印不需要改变顺序表，因此不需要使用引用
void PrintList(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        printf("%3d", L.data[i]);//为了打印到同一行
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10

顺序表的按值查找

//查找某个元素值，找到了返回对应位置，没找到返回0
int LocateElem(SqList L,ElemType element)//不改变结构体变量，不需要使用引用
{
    for(int i=0; i<L.length; i++)
    {
        if(element == L.data[i])
        {
            return i+1;//i是数组下标，加一才是顺序表下标
        }
    }
    return 0;//循环结束没找到
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表的按位查找

//按位查找,找到了返回对应下标的值
//如果有相同元素只考虑查找第一个元素
int GetElem(SqList L, ElemType e)//e是查找的位置
{
    if(e<1 || e>L.length)
    {
        printf("not found");
        return -1;//没找到
    }else{
        return L.data[e-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

所有模块集成的测试代码：

#include <stdio.h>

#define MaxSize 50   //定义顺序表的最大长度
typedef int ElemType;//ElemType表示元素类型，为了让顺序表存储其他类型元素时可以快速完成代码修改
typedef struct {
    ElemType data[MaxSize];
    int length;//顺序表长度
}SqList;
//顺序表的初始化和插入
//顺序表的插入，因为L会改变，因此要用引用
bool ListInsert(SqList &L, int i, ElemType elemType)
{
    //判断i的范围是否合法 i>=1 && i<=L.length+1
    if(i<1 || i>L.length+1)
        return false;
    //如果存储空间满了就不能插入
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length; j>=i; j--)
    {
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = elemType;//放入插入的元素
    L.length++;//顺序表长度加一
    return true;//插入成功返回true
}

//打印顺序表
//打印不需要改变顺序表，因此不需要使用引用
void PrintList(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        printf("%3d", L.data[i]);//为了打印到同一行
    }
    printf("\n");
}

//删除顺序表中的元素，i是要删除元素的位置，e是为了获取被删除元素的值
bool ListDelete(SqList &L, int i, ElemType &e)
{
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];//首先保存被删除元素的值
    for(int j=i;j<L.length;j++)//j=i-1;j<L.length-1;j++ L.data[j]=L.data[j+1]
    {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

//按值查找
//查找某个元素位置，找到了对应位置，没找到返回0
int LocateElem(SqList L,ElemType element)//不改变结构体变量，不需要使用引用
{
    for(int i=0; i<L.length; i++)
    {
        if(element == L.data[i])
        {
            return i+1;//i是数组下标，加一才是顺序表下标
        }
    }
    return 0;//循环结束没找到
}

//按位查找,找到了返回对应下标的值
//如果有相同元素只考虑查找第一个元素
int GetElem(SqList L, ElemType e)//e是查找的位置
{
    if(e<1 || e>L.length)
    {
        printf("not found");
        return -1;//没找到
    }else{
        return L.data[e-1];
    }
}

int main() {
    SqList L;//定义一个顺序表,变量L
    bool ret;//用来装函数的返回值
    L.data[0]=1;//放置元素
    L.data[1]=2;
    L.data[2]=3;
    L.length=3;//设置函数
    //顺序表的插入
    ret=ListInsert(L, 2, 60);
    if(ret)
    {
        printf("Insert sqlist success\n");
        PrintList(L);
    }else{
        printf("Insert sqlist Failed\n");
    }
    printf("---------------------------------\n");
    //顺序表的删除
    ElemType del;//删除元素的值存入del中
    ret=ListDelete(L, 1, del);
    if(ret)
    {
        printf("Delete SqList success\n");
        printf("del element=%d\n", del);
        PrintList(L);
    }else{
        printf("Delete SqList Failed\n");
    }
    printf("---------------------------------\n");
    //顺序表的按值查找
    int pos;//存储元素位置
    pos=LocateElem(L, 60);
    if(pos)
    {
        printf("success find this element!\n");
        printf("element position=%d, element=%d\n", pos, L.data[pos]);
    }else{
        printf("not found this element\n");
    }
    printf("---------------------------------\n");
    //顺序表的按位查找
    int val;//存储按位查找元素的值
    val=GetElem(L, 3);
    if(val!=-1)
    {
        printf("success found this element\n");
        printf("element=%d", val);
    }else{
        printf("not found this element\n");
    }
    return 0;
}

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

测试结果