数据结构之静态顺序表

静态顺序表属于数据结构开始的一种基本结构
首先我们要知道数据结构的概念

  1. 数据结构 数据的组织关系
  2. 算法 为了达到特定的目的的一系列过程。在这个过程中又分为两种角度
    1) 逻辑角度:线性结构,树形结构,图形结构
    2) 存储角度:顺序存储,链式存储

在线性结构中顺序存储的方式,在本次中为顺序表,分为静态和动态
而静态顺序表的理解可以分为
1) 结构体定义(定义、背后的内存布局模型)
2) 顺序表的基本操作:插/删/查/改重点需要去掌握的是插和删。插(头插/尾插/插入),删(头删/尾删/删除)
接下来开始对于整个代码进行一个分析。

1
2
3
4
5
6
7
8
9
10
11
12
#pragma once
#include<stdio.h>
#include<stdlib.h> //一般不着急于先定义一堆,你需要什么在去定义什么。

typedef int DataType; //为现有类型创建别名。用DataType来代替int。

#define MAX_SIZE(100) //开出一块空间,占用内存的最大位置。

typedef struct SeqList{ //定义结构体的别名
DataType array[MAX_SIZE];
int size;
}SeqList; //变量名

当把结构体都定义好了之后,我们开始先进行两个基本操作,对数组进行初始化和销毁
此时我们要用到assert()。在开头首先要定义这个宏#include<assert.h>,他的功能就是测试一个条件可能使程序终止。用法void assert(int test)

assert(), 断言,如果表达式为真,断言通过,无事发生;如果表达式为假,断言失败,程序直接退出。

在初始过程中,可能需要把内存清空一下,所以我们可能需要memset()这个函数。这个函数的用法void memset(void s, int ch, size_t n);
将s所指向的某一块内存中的后n个 字节的内容全部设置为ch指定的ASCII值,第一个值为指定的内存地址,块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为s。

1
2
3
4
5
6
7
8
9
10
11
12
//初始化
void SeqListInit(Seqlist *pSeq){
//初始化size
assert(pSeq != NULL);
pSep->size = 0;
memset(pSep->array,0,SIZE_MAX * sizeof(DataType));
}
//销毁
void SeqListDestory(SeqList *pSeq){
assert(pSeq);
pSeq->size = 0;
}

我们还需要部署一个测试函数,先暂时定义一下,当增删改查部署完后,可以往其中添加增删改查的函数来进行实验。

插入:有头插,尾插,插入

头插的使用

PS:考虑完了普通情况后,我们要考虑的是特殊情况,当size超过了定义的最大尺寸情况,我们需要进行一个判断,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListPushTop(SeqList *pSeq,DataType data){
assert(pSeq);
if(pSeq->size >= MAX_SIZE){
printf("满了\n");
assert(0);
return;
}
//从最后开始向每一个后面开始搬运,如果不这么做,将会将每一次的值覆盖掉
for(int i = pSeq->szie;i > 0; i--){ // i此时是定义的为位置,位置为[size,0],从后往前搬
pSeq->array[i] = pSeq->array[i - 1];
}
//将i定位为数据,位置size[0,size),将整体的位置向后移
for(int i = size - 1;i > 0;i++){
pSeq->array[i + 1] = pSeq->array[i];
}
pSeq->array[0]=data;
pSeq->size++;
}

这是一个自我思考的图示,仅供参考

数据结构头插

尾插的使用

尾插就相当于正常插入了,这个是比较简单的一种插入

1
2
3
4
5
6
7
8
9
10
11
void SeqListPushBack(SeqList *pSeq,DataType data){
//还是要先考虑特殊情况
assert(pSeq);
if(pSeq->size >= MAX_SIZE){
printf("满了\n");
assert(0);
return;
}
pSeq->array[pSeq->size] = data;
pSeq->size++;
}

中间插入的使用

中间插入根据下标来使用,此时这么想,我们先将要插入的地方定义一个pos下标,此时将此下标之后的(包括此下标的)所有数据向后移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListInsert(SeqList *pSeq,int pos, DataType data){
//考虑特殊情况
assert(pSeq);
if(pSeq->size >= MAX_SIZE){
printf("满了\n");
assert(0);
return;
//此时i作为位置
for(int i = pSeq->size; i >= pos; i--){
pSeq->array[i] = pSeq->array[i - 1];
}
//此时i作为数据
for(int i = pSeq->size - 1;i >= pos; i--){
pSeq->array[i + 1] = pSeq->array[i];
}
pSeq->array[pos] = data;
pSeq->szie++;
}

自我图示,仅供参考

数据结构插入

删除:头删,尾删,删除

头删的使用

最开始的数删除后,其他的数据向前补进。当然,也别忘了特殊情况!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListPushFont(SeqList *pSeq){
//特殊情况
assert(pSeq)
if(pSeq->size <= 0){
printf("空了\n");
assert(0);
return;
}
//i此时为位置时
for(int i = 0; i < pSeq->size - 1;i++){
pSeq->array[i] = pSeq->array[i + 1];
}
//i此时为数据时
for(int i = 1;i < pSeq->size;i++){
pSeq->array[i - 1] = pSeq->array[i];
}
pSeq->size--;
}

尾删的使用

尾删比较简单,也就是直接将最后一个删除

1
2
3
4
5
6
7
8
9
void SeqListPushPop(SeqList *pSeq){
assert(pSeq)
if(pSeq->size <= 0){
printf("空了\n");
assert(0);
return;
}
pSeq->size--;//直接将空间减小
}

删除的使用

删除从中间删除,还是定义一个pos下标,删除之后,在将所有数据向前移动

1
2
3
4
5
6
7
8
9
10
11
void SeqListPushErase(SeqList *pSeq,int pos){
assert(pSeq)
if(pSeq->size <= 0){
printf("空了\n");
assert(0);
return;
}
for(int i = pos;i <= pSeq->size ;i--){
pSeq->array[i - 1] = pSeq->array[i];
}
}

当我们基本的这些操作编写完之后,我们需要输出这些数组,来观察。

1
2
3
4
5
6
7
void SeqListPrint(const SeqList *pSeq){
assert(pSeq != NULL);
for(int i = 0;i < pSeq->size;i++){
printf("%d",pSeq->array[i]);
}
printf("\n");
}

删除的第二种形态

用接口的方式来实现删除。

接口可以理解为封装一个函数来对其使用。这样我们就可以有一些其他的删除方式

删除第一个遇到的数据的形式

1
2
3
4
5
6
7
8
void SeqListRemove(SeqList *pSeq, DataType data){
int pos = SeqListFind(pSeq,data);
if(pos == -1){
//找不到删除
return;
}
SeqListPushErase(pSeq, pos);
}

删除遇到的所有数据的形式

1
2
3
4
5
6
void SeqListRemoveALL(SeqList *pSeq,DataType data){
//第一种方式
while(pos = SeqListFind(pSeq,data) != -1){
SeqListPushErase(pSeq,data);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SeqListRemovALL(SeqList *pSeq,DataType data){
//第二种方式
//一次遍历空间,时间快,但是开辟了新空间,空间大小和size有关系
//开辟一个新空间,遍历原来的数组
//if arr[i] != data
//new [j+1]= arr[j+1]
//else i++
//把数据在搬回来,还剩的数据个数为i个
DataType *newArray = (DataType *)malloc(sizeof(DataType)*pSeq->size);
int i, j;
for(i = 0,j = 0;i < pSeq->size;i++){
if(data != pSeq->array[i]){
newArray[j] = pSeq->array[i];
j++
}
}
for(i = 0;i < j; i++){
pSeq->array[i] = newArray[i];
}
pSeq->size = j;
free(newArray);
}
1
2
3
4
5
6
7
8
9
10
11
void SeqListRemoveALL(SeqList *pSeq,DataType data){
//第三种方法
//这个方法没有开辟新的空间,直接对其每个所对应的新区域赋值
//这样我们最后将数组size直接改为新开辟的大小
int i, j;
for(i = 0,j = 0;i < pSeq->size, i++){
pSeq->array[j] = pSeq->array[i];
j++;
}
pSeq->size = j;
}

查找的使用

查找也是一个关键的选择,因为,在查找到我们需要的下标之后,我们可以对此进行各种增删改操作

查找也有很多方式,这里先仅做一种顺序遍历查找。查找也有二分查找(前提有序)

1
2
3
4
5
6
7
8
int SeqListFind(SeqList *pSeq,DataType data){
for(int i = 0;i < pSeq->size;i++){
if(data = pSeq->size[i]){
return 1;
}
return -1;
}
}

一些其他的使用操作

对于顺序表的操作我们还有一些其他的操作

1
2
3
4
int SeqListSize(SeqList *pSeq){
//查看当前size的大小
return pSeq->size;
}
1
2
3
4
int SeqListEmpty(SeqList *pSeq){
//清空当前数组
return pSeq->size == 0;
}
1
2
3
4
int SeqListFull(SeqList *pSeq){
//将数组的size放到最大
return pSeq->size == MAX_SIZE;
}
1
2
3
4
5
6
void Swap(DataType *a,DataType *b){
//交换两个数据
DataType t = *a;
*a = *b;
*b = t;
}

改的使用

我们可以理解为,我们将要怎么让这个数组去改变,那么我们可以使用排序的方式将数组发生变化。这是一种改法。在静态顺序表中。通过举冒泡排序的例子来使用。

数据结构冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SeqListBubbleSort(SeqList *pSeq){
int i,j;
int isSort;
for(i = 0;i < pSeq->size - 1;i++){
isSort = 1;
for(j = 0;j <= pSeq->size - 1 - i; j++){
if(pSeq->array[i] > pSeq->array[i + j]){
Swap(pSeq->array + j, pSeq->array + j + i);
}
isSort = 0;
}
if(isSort){
break;
}
}
}

在这里调用冒泡排序的方法是可以进行数组的改变。

以上就是关于静态顺序数组的基本组成。总的来说,数据结构的难点在于思想过程。怎么把在纸上我们通过绘画的东西,利用代码的形式去表达出来,这是一个很关键的思考过程。

-------------The End-------------