【数据结构】02.顺序表

一、顺序表的概念与结构

1.1线性表

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

1.2顺序表分类

1.2.1 顺序表和数组的区别

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

1.2.2顺序表分类

• 静态顺序表

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

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

• 动态顺序表

二、动态顺序表的实现

2.1结构体表示顺序表

首先需要一个结构体来表示顺序表：

typedef int SLDataType;//笔者在此直接使用了接下来要实现的顺序表的数据类型
//顺序表结构体
typedef struct SL
{
	SLDataType* a;
	int size;
	int capacity;
}SL;
1
2
3
4
5
6
7
8

2.2顺序表的初始化和销毁

//初始化顺序表
void init(SL* s)
{
	s->a = NULL;
	s->size = s->capacity = 0;
}
1
2
3
4
5
6

//顺序表销毁
void SLDestory(SL* s)
{
	assert(s);
 
	if(s->a)
	{
		free(s->a);
	}
	s->a = NULL;
	s->size = s->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3顺序表的增删查改

在每次插入时都会面对着是否扩容的问题，因此我们抽离出检查扩容的函数。

//检查是否满了
void check(SL* s)
{
	if (s->size == s->capacity)
	{
		int new_capacity = (s->capacity == 0) ? 4 : s->capacity * 2;
		SLDataType* temp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * new_capacity);
		if (temp == NULL)
		{
			perror("realloc is fail!");//如果realloc失败会报错
			exit (EXIT_FAILURE);
		}
		s->a = temp;
		s->capacity =new_capacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//头插
void PushFront(SL* s, SLDataType x)
{
	assert(s);
	
	check(s);
	for (int i =s->size;i>0;i--)
	{
		s->a[i] =s->a[i-1];
	}
	s->a[0] = x;
	s->size++;
}
 
//尾插
void PushBack(SL* s, SLDataType x)
{
	assert(s);
	
	check(s);
	s->a[s->size] = x;
	s->size++;
}
 
//头删
void PopFront(SL* s)
{
	assert(s && s->size);
	for (int i =0;i<s->size-1;i++)
	{
		s->a[i] = s->a[i+1];
	}
	s->size--;
}
 
//尾删
void PopBack(SL* s)
{
	assert(s);
	
	assert(s->size);
 
	s->size--;
}
 
//任意位置的插入
void Insert(SL* s, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= s->size);
	
	check(s);
	for (int i = s->size; i > pos; i--)
	{
		s->a[i] = s->a[i - 1];
	}
	s->a[pos] = x;
	s->size++;
}
 
//任意位置的删除，pos是下标
void Erase(SL* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);
 
	for (int i = pos; i < s->size; i++)
	{
		s->a[i] = s->a[i + 1];
	}
	s->size--;
}
 
//查找元素是否存在，存在返回下标，否则返回-1
int Find(SL* s, SLDataType x)
{
    assert(s);
 
	for (int i = 0; i < s->size; i++)
	{
		if (x == s->a[i])
			return i;
	}
	return -1;
}
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

2.4顺序表的打印

//打印
void print(SL* s)
{
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

三、顺序表的源代码

//order_table.h
 
#pragma once
 
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
//顺序表结构体
typedef struct SL
{
	SLDataType* a;
	int size;
	int capacity;
}SL;
 
 
//初始化顺序表
void init(SL *s);
//打印
void print(SL* s);
 
//增删查改
void PushFront(SL* s,SLDataType x);//头插
 
void PushBack(SL* s, SLDataType x);//尾插
 
void PopFront(SL* s);//头删
 
void PopBack(SL* s);//尾删
 
void Insert(SL* s, int pos, SLDataType x);//任意位置的插入，pos意为下标
 
void Erase(SL* s, int pos);//任意位置的删除,pos意为下标
 
int Find(SL* s, SLDataType x);//查找元素是否存在，存在返回下标，否则返回-1
 
void SLDestory(SL* s);
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

//order_table.c
#include"order_table.h"

//顺序表结构体
void init(SL* s)
{
   s->a = NULL;
   s->size = 0;
   s->capacity = 0;
}

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

//检查是否满了
void check(SL* s)
{
   if (s->size == s->capacity)
   {
   	int new_capacity = (s->capacity == 0) ? 4 : s->capacity * 2;
   	SLDataType* temp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * new_capacity);
   	if (temp == NULL)
   	{
   		perror("realloc is fail!");
   		exit (EXIT_FAILURE);
   	}
   	s->a = temp;
   	s->capacity =new_capacity;
   }
}
//头插
void PushFront(SL* s, SLDataType x)
{
   check(s);
   for (int i =s->size;i>0;i-- )
   {
   	s->a[i] =s->a[i-1];
   }
   s->a[0] = x;
   s->size++;
}


void PushBack(SL* s, SLDataType x)//尾插
{
   check(s);
   s->a[s->size] = x;
   s->size++;
}

void PopFront(SL* s)//头删
{
   assert(s && s->size);
   for (int i =0;i<s->size-1;i++)
   {
   	s->a[i] = s->a[i+1];
   }
   s->size--;
}

void PopBack(SL* s)//尾删
{
   assert(s);
   assert(s->size);

   s->size--;
}

void Insert(SL* s, int pos, SLDataType x)//任意位置的插入
{
   assert(pos >= 0 && pos <= s->size);
   check(s);
   for (int i = s->size; i > pos; i--)
   {
   	s->a[i] = s->a[i - 1];
   }
   s->a[pos] = x;
   s->size++;
}

void Erase(SL* s, int pos)//任意位置的删除
{
   assert(s);
   assert(pos >= 0 && pos < s->size);

   for (int i = pos; i < s->size; i++)
   {
   	s->a[i] = s->a[i + 1];
   }
   s->size--;
}

int Find(SL* s, SLDataType x)//查找元素是否存在，存在返回下标，否则返回-1
{
   assert(s);

   for (int i = 0; i < s->size; i++)
   {
   	if (x == s->a[i])
   		return i;
   }
   return -1;
}


void SLDestory(SL* s)
{
   assert(s);

   if(s->a)
   {
   	free(s->a);
   }
   s->a = NULL;
   s->size = s->capacity = 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