【数据结构】顺序表的基本操作

---

前言

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
比如大家感兴趣的12星座，它是不是线性表呢？

当然是，星座通常都是白羊座打头，双鱼座收尾，当中的星座都是有前驱和后继，而且一共也只有
个，所以它完全符合线性表的定义。

二、顺序表

1.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.顺序表一般可分为:

2.1 静态顺序表

使用定长数组存储元素（给小了不够用，给多了又浪费，不太实用）

动态顺序表

使用动态开辟的数组存储
优点:可根据我们的需求分配适当大小空间

三、顺序表的实现

创建接口

1、Test.c（主函数，该接口用于测试调试各接口的结果和功能）
2、SeqList.c（顺序表所有功能函数都在这里面实现）
3、SeqList.h（头文件，顺序表的类型定义、函数声明）

SeqList.h头文件代码如下

//SeqList.h头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDatatype;//方便后续更改类型

typedef struct SeqList
{
    SLDatatype *a;
    int size;     //有效数据
    int capacity; //空间容量
}SL;

//初始化顺序表
void SLInit(SL*psl);

//销毁
void SLDestory(SL*psl);

//检查容量是否需要增容
void SLCheckcapacity(SL*psl);
//打印数据
void SLPrint(const SL*psl);
//尾插
void SLPushBack(SL*psl,SLDatatype x);
//头插
void SLPushFront(SL*psl,SLDatatype x);
//尾删
void SLPopBack(SL*psl);
//头删
void SLPopFront(SL*psl);

//查找
void SLFind(SL*psl,SLDatatype x);

//指定位置插入
void SLInsert(SL*psl,int pos,SLDatatype x);
//指定位置删除
void SLErase(SL*psl,int pos);

//修改数据
void SLModify(SL*psl,int pos,SLDatatype x);

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

SeqList.c

1、顺序表初始化

void Init(SL*psl)
{
	assert(psl)//断言操作 确定传进来的指针不为空指针
	//初始化
	psl->a=NULL;//顺序表为空
	psl->size=0;//数据个数为0
	psl->capacity=0;//空间容量大小为0
}
1
2
3
4
5
6
7
8

2、销毁释放

void SLDestory(SL*psl)
{
	if(psl->a!=NULL)
	{
		free(psl);//释放
		psl->a=NULL;//置为空
		psl->size=0;
		psl->capacity=0;
	}
}
1
2
3
4
5
6
7
8
9
10

3、检查容量

因为考虑到后面许多接口实现都需要检查要不要扩容，所以直接把它封装成一个的函数，方便后续使用

void SLCheckcapacity(SL*psl)
{
	if(psl->size=psl->capacity)//说明空间满了需要开辟动态空间
	{
		//采用三目运算符，如果容量为零，就扩建给定的4个大小的空间,否则就扩原来容量大小的两倍
		int newcapacity=psl->capacity == 0?4:psl->capacity*2;
		//在这里为什么要创建一个tmp而不直接用psl->a呢？是为了防止空间扩容失败把空值返回，到时把原来的数据全部覆盖了
		SLDatatype*tmp=(SLDatatype*)realloc(psl->a,newcapacity*sizeof(SLDatatype));
		if(tmp==NULL)//判断空间是否开辟成功
		{
			//如果开辟空间失败，就输出对应的错误原因
			printf("realloc fail");
			//返回
			return;
		}
		//增容成功，更新数据
		psl->a=tmp;
		psl->capacity=newcapacity;
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4、打印顺序表

void SLPrint(const SL*psl)
{
	assert(psl);//断言，确定不传空指针
	//遍历一遍顺序表就好了
	for(int i=0;i<psl->szie;i++)
	{
		printf("%d ",psl->a[i]);
	}
	//换行
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

5、尾插

尾插就相对简单了，直接往后面插就行了

void SLPushBack(SL*psl,SLDatatype x)
{
	assert(psl);//断言，防止传空指针
	SLCheckcapacity(SL*psl);//检查容量
	psl->a[psl->size]=x;
	psl->size++;
}
1
2
3
4
5
6
7

测试

最好写一点点编译一点点测试一点点，不然写完一个程序一运行，发现开头就出问题了，那到时候就白搞了

Test.c函数中

void TestSL1()
{
	SL sl;
	//初始化
	SLInit(&sl);
	//插入操作,这里多插几个，一次扩4个，可以看到扩了两次容
	SLPushBack(&sl,1);
	SLPushBack(&sl,2);
	SLPushBack(&sl,3);
	SLPushBack(&sl,4);
	SLPushBack(&sl,5);
	SLPushBack(&sl,6);
	SLPushBack(&sl,7);
	SLPushBack(&sl,8);
	SLPushBack(&sl,9);
	//打印
	SLPrint(&sl);
	//销毁
	SLDestroy(&sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试结果

6、头插

void SLPushFront(SL*psl,SLDatatype x)
{
    assert(psl);//断言
    SLCheckcapacity(psl);//检查容量
    int end=psl->size-1;
    while(end>=0)
    {
        psl->a[end+1]=psl->a[end];
        --end;
    }
    psl->a[0]=x;
    psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试
在刚刚那个测试函数基础上继续测试

void TestSL1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl,1);
	SLPushBack(&sl,2);
	SLPushBack(&sl,3);
	SLPushBack(&sl,4);
	SLPushBack(&sl,5);
	SLPushBack(&sl,6);
	SLPushBack(&sl,7);
	SLPushBack(&sl,8);
	SLPushBack(&sl,9);
	SLPrint(&sl);
	SLPushFront(&sl,10);
	SLPushFront(&sl,20);
	SLPushFront(&sl,30);
	SLPushFront(&sl,40);
	SLPrint(&sl);
	SLDestroy(&sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试结果

黄色方框里面是头插结果

7、尾删

需要注意的是当顺序表大小为零的时候就不能往下删了

void SLPopBack(SL*psl)
{
    assert(psl);//断言
    //温柔检查
    //if(psl->size==0)//检查，没有数据就结束退出
    //{
    //    return;
    //}
    //除了上面的检查方法，还有一种暴力的检查
    assert(psl->size>0);//好处:直接终止程序，并告诉你在什么位置报错的
    psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

测试

void TestSL2()
{
	SL sl;
	SLInit(&sl);
	//插5个数
	SLPushBack(&sl,1);
	SLPushBack(&sl,2);
	SLPushBack(&sl,3);
	SLPushBack(&sl,4);
	SLPushBack(&sl,5);
	SLPrint(&sl);//打印
	//删一个
	SLPopBack(&sl);
	SLPrint(&sl);//再打印看看效果
	//插了5个删了一个，还剩一个，再删4个不出意外的话下次打印就没了
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);	
	//这里可不敢继续往下删了，再删出问题了
	SLPrint(&sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

测试结果

7、头删

void SLPopFront(SL*psl)
{
    assert(psl);
    assert(psl->size>0);
    int begin=0;
    while(begin < psl->size-1)
    {
        psl->a[begin]=psl->a[begin+1];
        begin++;
    }
    --psl->size;
}
1
2
3
4
5
6
7
8
9
10
11
12

测试

void TestSL3()
{
	SL sl;
	SLInit(&sl);
	//先插5个数
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);
	//删一个打印一下,剩4个,打印4个数
	SLPopFront(&sl);
	SLPrint(&sl);
    //删一个打印，剩3个，打印3个数
	SLPopFront(&sl);
	SLPrint(&sl);
	//再删一个打印，剩2个，打印2个数
	SLPopFront(&sl);
	SLPrint(&sl);
	//剩1个，打印1个数
	SLPopFront(&sl);
	SLPrint(&sl);
	//删光了
	SLPopFront(&sl);
	SLPrint(&sl);
}
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

测试结果

8、查找

void SLFind(SL*psl,SLDatatype x)//x为你要查找的数
{
    assert(psl);
    for(int i=0;i<psl->size;i++)//遍历顺序表
    {
        if(psl->a[i]==x)
        {
            return i;//如果找到了，返回下标
        }
    }
    //找不到退出
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9、指定位置插入

这里需要注意的是pos是下标，size是数据个数

void SLInsert(SL*psl,int pos,SLDatatype x)
{
    assert(psl);
    //断言,这个范围只能在0到size，也可以等于size，等于size就相当于是尾插了，没毛病
    assert(pos>=0 && pos<=psl->size);
    SLCheckcapacity(psl);
    //挪动数据 
    int end=psl->size-1;
    while(end>=pos)
    {
        psl->a[end+1]=psl->a[end];
        --end;
    }
    psl->a[pos]=x;
    psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试

void TestSL4()
{
	SL sl;
	//初始化
	SLInit(&sl);
	//插入5个数据
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);
	//在下标为2的位置插入20
	SLInsert(&sl, 2, 20);
	SLPrint(&sl);
	//在下标为6的位置插20
	SLInsert(&sl, 6, 20);
	SLPrint(&sl);
	//在下标为0的位置插20
	SLInsert(&sl, 0, 20);
	SLPrint(&sl);
	//销毁
	SLDestroy(&sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

测试结果

10、指定位置删除

void SLErase(SL*psl,int pos)
{
    assert(psl);
    assert(pos>=0 && pos<psl->size);
    SLCheckcapacity(psl);
    //挪动覆盖
    int begin=pos+1;
    while(begin<psl->size)
    {
        psl->a[begin-1]=psl->a[begin];
        ++begin;
    }
    psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试

void TestSL5()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLErase(&sl, 3);
	SLPrint(&sl);
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试结果

11、指定数据进行修改

void SLModify(SL*psl,int pos,SLDatatype x)
{
    assert(psl);
    assert(pos>=0 && pos<psl->size);
    //原理很简单直接给下标位置数据进行赋值就行了
    psl->a[pos]=x;
}
1
2
3
4
5
6
7

顺序表的基本操作大概就是这些，你们都get到了吗？

---

总结

SeqList.c总代码

#include "SeqList.h"

//顺序表初始化
void SLInit(SL*psl)
{
    asseert(psl);
    psl->a=NULL;
    psl->size=0;
    psl->capacity=0;
}

//顺序表销毁
void SLDestory(SL*psl)
{
    assert(psl);
    if(psl->a!=NULL)
    {
        free(psl->a);
        psl->a=NULL;
        psl->size=0;
        psl->capacity=0;
    }
}

//为了检查容量的函数
void SLCheckcapacity(SL*psl)
{
    if(psl->size=psl->capacity)
    {
        int newcapacity=psl->capacity==0 ? 4:psl->capacity*2;
        SLDatatype*tmp=(SLDatatype*)realloc(psl->a,newcapacity*sizeof(SLDatatype));
        if(tmp==NULL)
        {
            printf("realloc fail");
            return;
        }
        psl->a=tmp;
        psl->capacity=newcapacity;
    }
}

//尾插
void SLPushBack(SL*psl,SLDatatype x)
{
    assert(psl);
    SLCheckcapacity(psl);
    psl->a[psl->size]=x;
    psl->size++;
}
//头插
void SLPushFront(SL*psl,SLDatatype x)
{
    assert(psl);
    SLCheckcapacity(psl);
    int end=psl->size-1;
    while(end>=0)
    {
        psl->a[end+1]=psl->a[end];
        --end;
    }
    psl->a[0]=x;
    psl->size++;
}
//尾删
void SLPopBack(SL*psl)
{
    assert(psl);
    if(psl->size==0)
    {
        return;
    }
    psl->size--;
}
//头删
void SLPopFront(SL*psl)
{
    assert(psl);
    assert(psl->size>0);
    int begin=0;
    while(begin<psl->size-1)
    {
        psl->a[begin]=psl->a[begin+1];
        begin++;
    }
    --psl->size;
}

//查找
void SLFind(SL*psl,SLDatatype x)
{
    assert(psl);
    for(int i=0;i<psl->size;i++)
    {
        if(psl->a[i]==x)
        {
            return i;
        }
    }
    return -1;
}

//指定插入
void SLInsert(SL*psl,int pos,SLDatatype x)
{
    assert(psl);
    assert(pos>=0 && pos<=psl->size);
    SLCheckcapacity(psl);
    int end=psl->size-1;
    while(end>=pos)
    {
        psl->a[end+1]=psl->a[end];
        --end;
    }
    psl->a[pos]=x;
    psl->size++;
}

//指定删除
void SLErase(SL*psl,int pos)
{
    assert(psl);
    assert(pos>=0 && pos<psl->size);
    SLCheckcapacity(psl);
    int begin=pos+1;
    while(begin<psl->size)
    {
        psl->a[begin-1]=psl->a[begin];
        ++begin;
    }
    psl->size--;
}

//打印
void SLPrint(const SL*psl)
{
    assert(psl);
    for(int i=0;i<psl->size;i++)
    {
        printf("%d ",psl->a[i]);
    }
    printf("\n");
}

//修改数据
void SLModify(SL*psl,int pos,SLDatatype x)
{
    assert(psl);
    assert(pos>=0 && pos<psl->size);
    psl->a[pos]=x;
}
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

Test.c总代码

#include"SeqList.h"

void TestSL1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 7);
	SLPushBack(&sl, 8);
	SLPushBack(&sl, 9);
	SLPrint(&sl);

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSL2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSL3()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);

	SLPopFront(&sl);
	SLPrint(&sl);
}

void TestSL4()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLInsert(&sl, 2, 20);
	SLPrint(&sl);

	SLInsert(&sl, 6, 20);
	SLPrint(&sl);

	SLInsert(&sl, 0, 20);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSL5()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPrint(&sl);

	SLErase(&sl, 3);
	SLPrint(&sl);
}

int main()
{
	TestSL5();
	Test
	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