数据结构——顺序表专题

1. 数据结构的相关概念

什么是数据结构

数据结构是由“数据”和“结构”两词组合而来的。

数据：常见的数值、网页中肉眼可见的信息，这些都是数据。

结构：当我们想要使用大量同一类型的数据时，通过手动定义大量的独立的遍历对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

1. 能够存储数据（顺序表，链表等结构）
2. 存储的数据能够方便查找

为什么需要数据结构？

在程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构，能够有效将数据组织和管理在一起。按照我们的方式任意对书记进行增删改查等操作。

最基础的数据结构：数组

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：最基础的数据结构能够提供已经不能完全满足复杂算法实现。

2. 顺序表

顺序表的概念及结构

线性表是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表早无力上存储时，通常是以数组和链式结构的形式存储。

顺序表分类

顺序表和数组的区别

顺序表的底层结构是数组，对数组的分装，实现了常用的增删改查等接口

静态顺序表

概念：使用定长数组存储元素

静态顺序表：给定数组的长度，若不够，会导致后续的数据保存失败；给多了，会导致空间大量的浪费

数据丢失----非常严重的技术事故！！

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表

3. 动态顺序表的实现

准备工作

typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}SL;
1
2
3
4
5
6
7
8

顺序表的初始化

//初始化和销毁
void SLInit(SL* ps)
{ 
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
1
2
3
4
5
6

顺序表的扩容

实现动态顺序表，当size和capacity相等时，有2中情况，第一种：一开始为0的时候，第二种情况是：当空间不足时
若是第一种情况就给4个字节的空间，若是第二种情况使用二倍思想来处理

oid SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//说明扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尾插

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{
	//断言
	//assert(ps != NULL);
	assert(ps);
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够，直接插入
	//空间没有满，直接进行尾插
	ps->arr[ps->size] = x;
	ps->size++;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头插

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否扩容
	SLCheckCapacity(ps);

	//旧数据往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
	
		ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=pa->arr[0]
	}
	ps->arr[0] = x;
	ps->size++;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	ps->size--;
}
1
2
3
4
5
6
7
8
9

头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//不为空执行挪动操作
	for (int i = 0;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

指定位置插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);

	//pos及之后的数据往后挪动一位，pos空出来
	for (int i=ps->size;i>pos;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

指定位置删除数据

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos以后的数据往前挪动一位
	for (int i=pos;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

在顺序表中查找

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

销毁

void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;

	ps->size = ps->capacity = 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

4. 全部完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>

//静态顺序表
//#define N 100
//typedef int SLDataType;
//struct Seqlist
//{
//	SLDataType a[N];
//	int size;
//};

typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插

//顺序表的删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//指定位置插入数据
//删除指定位置的数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

int SLFind(SL* ps, 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

seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"

//初始化和销毁
void SLInit(SL* ps)
{ 
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//说明扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{
	//断言
	//assert(ps != NULL);
	assert(ps);
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够，直接插入
	//空间没有满，直接进行尾插
	ps->arr[ps->size] = x;
	ps->size++;

}

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否扩容
	SLCheckCapacity(ps);

	//旧数据往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
	
		ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=pa->arr[0]
	}
	ps->arr[0] = x;
	ps->size++;

}

//顺序表的删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	ps->size--;
}
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//不为空执行挪动操作
	for (int i = 0;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//指定位置插入数据
//删除指定位置的数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);

	//pos及之后的数据往后挪动一位，pos空出来
	for (int i=ps->size;i>pos;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos以后的数据往前挪动一位
	for (int i=pos;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]
	}
	ps->size--;
}

//在顺序表中查找x
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;

	ps->size = ps->capacity = 0;
}

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[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
144
145
146
147
148

seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"

void s1Test1()
{
	SL s1;
	SLInit(&s1);

	//测试尾插
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(&s1);
	/*SLPushBack(&s1, 9);
	SLPrint(&s1);*/

	//测试头插
	SLPushFront(&s1, 5);
	SLPushFront(&s1, 6);
	SLPushFront(&s1, 7);
	SLPrint(&s1);

	//测试尾删
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);

	//指定位置插入数据
	SLInsert(&s1, 0, 100);
	SLPrint(&s1);

	//删除指定位置的数据
	SLErase(&s1, 0);
	SLPrint(&s1);
}

void s1Test2()
{
	SL s1;
	SLInit(&s1);

	//测试尾插
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(&s1);

	//测试查找
	int ret = SLFind(&s1, 3);
	if (ret <0)
	{
		printf("数据不存在，查找失败");
	}
	else {
		printf("数据找到了，在%d位置", ret);
	}
}

void s1Test3()
{
	SL s1;
	SLInit(&s1);
	SLDestroy(&s1);
}

int main()
{
	void s1Test3();
	//s1Test2();
	//s1Test1();
	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