【数据结构篇】~顺序表

顺序表前言

想要学好数据结构的三大基本功：1.结构体2.指针3.动态内存开辟,这三样将是贯彻整个数据结构的工具。（可以去这里了解这三大基本功）
顺序表也是线性表的一种，那线性表又是什么呢？
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的
数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… ​
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性
表在物理上存储时，通常以数组和链式结构的形式存储。

1.静态顺序表

静态顺序表顾名思义也就是不用动态开辟内存，是用定长数组实现的！
如图：

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

2.动态顺序表

顺序表和数组的区别就在于它可以实现"增、删、查、改"等功能。

头文件

1.这是头文件

#pragma once
#include <stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int sqdatatype;//定义数据类型
typedef struct sqlist 
{ 
	sqdatatype* arr;
	 int size;//有效数据个数
	 int capacity;//容量
}Sq;
void sqcapacitycheck(Sq* sq);//检查容量
void sqlistinit(Sq* sq);//初始化

void sqDestroy(Sq* sq);//销毁
//1.'增'（尾插、头插、任意地方插入）
void sqpushback(Sq* sq, sqdatatype x);
void sqpushfront(Sq*sq,sqdatatype x);//头插
void sqinsertf(Sq* sq, size_t pos, sqdatatype n);//任意地方插入
//2.'删'（尾删、头删、任意地方删除）
void sqpopback(Sq* sq);//尾删
void sqpopfront(Sq* sq);//首删
void sqearse(Sq* sq, size_t pos);//指定位置删除


int sqfind(Sq* sq, sqdatatype n);//3.'查'(查找数据)
//4.'改'（改数据）
void sqchange(Sq* sq, sqdatatype n1, sqdatatype n2);//把n1改为n2; 

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

源文件

2.这是源文件

#include"sqlist.h"
//顺序表的"初始化"和"销毁"
//顺序表的"增、删、查、改"实现
// 第一次写顺序表时有许多"坑"
//1.初始化
void sqlistinit(Sq* sq)
//！！第一个坑
//这里要传 "地址" ，不能传"值",传值不会改变（形参只是实参的临时拷贝）
{
	//初始化顺序表就要把结构体里的内容全部初始化
	sq->arr = NULL;
	sq->capacity = sq->size = 0;
}
//销毁
void SqDestroy(Sq* sq)
{
	//和初始化一样，所有内容都要销毁
	free(sq->arr);
	sq->arr = NULL;
	sq->size = sq->capacity = 0;
}
//打印数据
void sqprint(Sq sq)
{
	for (int i = 0; i < sq.size; i++)
	{
		printf("%d ", sq.arr[i]);
	}
	printf("\n");
}
void sqcapacitycheck(Sq* sq)//检查容量
{
	

	if (sq->capacity == sq->size)//容量不够了
	{
		//第二个坑，capacity不能为空
		int newcapacity = (sq->capacity==0)? 4:(2*sq->capacity);
		sqdatatype* tmp= (sqdatatype*)realloc(sq->arr, newcapacity * sizeof(sqdatatype));
		//第三个坑realloc时要 乘 数据类型
		if (tmp==NULL)
	 {
		perror("realloc fail!");
		return 1;
	 }
	sq->capacity = newcapacity;
	sq->arr = tmp;
	}
	
}
//"增"的时候每次（size（有效数据个数）都要++）
// 判断容量够不够，不够就要增容！
//1.尾插（）
void sqpushback(Sq* sq, sqdatatype x)
{
	assert(sq);//这里不能传空，不能对null解引用
	sqcapacitycheck(sq);
	sq->arr[sq->size++]=x;
}
//2.头插
void sqpushfront(Sq* sq, sqdatatype x)
{
	assert(sq);
	sqcapacitycheck(sq);
	for (int i=sq->size;i>0;i--)
	{
		sq->arr[i] = sq->arr[i-1];
	}
	sq->arr[0] = x;
	sq->size++;
}
//3.指定位置插入
void sqinsertf(Sq* sq, size_t pos, sqdatatype x)
{
	assert(sq);
	assert(pos <= sq->size);//(因为pos是无符号整型所以>0 )   pos得满足条件！
	sqcapacitycheck(sq);
	for (int i = sq->size; i>pos;i--)
	{
		sq->arr[i]= sq->arr[i - 1];
	}
	sq->arr[pos] = x;

	sq->size++;
}
//删除数据的时候(size都要--)
void sqpopback(Sq* sq)//尾删
{
	assert(sq);
	sqcapacitycheck(sq);
	sq->size--;
}
void sqpopfront(Sq* sq)//首删
{
	assert(sq);
	sqcapacitycheck(sq);
	for (int i=0;i<sq->size-1;i++)
	{
		sq->arr[i] = sq->arr[i+1];//最后一次把size-1给size-2
	}
	sq->size--;
}
void sqearse(Sq* sq, size_t pos)//指定位置删除
{
	assert(sq);
	assert(pos <= sq->size);//(因为pos是无符号整型所以>0 )   pos得满足条件！
	sqcapacitycheck(sq);
	for (int i = pos; i < sq->size - 1; i++)
	{
		sq->arr[i] = sq->arr[i + 1];//第一次：  arr[pos]=arr[pos+1]
		                            //最后一次：arr[size-2]=arr[size-1]
	}
	sq->size--;
}
//查找数据
int sqfind(Sq* sq, sqdatatype n)
{
	assert(sq);
	sqcapacitycheck(sq);
	for (int i = 0; i < sq->size; i++)
	{
		if (n == sq->arr[i])

		{
			printf("找到了，下标是：");
			return i;
		}
	}
}
//改数据
void sqchange(Sq* sq, sqdatatype n1, sqdatatype n2)//把n1改为n2
{
	assert(sq);
	sqcapacitycheck(sq);
	for (int i = 0; i < sq->size; i++)
	{
		if (n1 == sq->arr[i])

		{
			sq->arr[i] = n2;
		}
	}
}
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

详解全部都注释起来了哦！