前言
-
<font color=blue size=4>顺序表作为数据结构中的小小弟,还是很好应付的</font><font size=4>。说到数据结构,顺序表是我们的向导,它让你明白数据结构到底是干啥的,为啥数据结构这么的重要。</font>
-
</font><font size=4>实际上,通讯录的底层就是一个顺序表,里面的增添联系人,删除联系人等一系列操作,都是基于顺序表实现的,这也侧面拖出了数据结构的作用。所以,学好数据结构是必须的。
-
</font><font size=4>要是能够自主实现通讯录,我肯定,顺序表学起来会非常的轻松。
初始化顺序表
- 实现顺序表需要三个文件:一个是
.h
为后缀的头文件SeqList.h
:用来放相关头文件,宏定义,结构体声明,以及函数声明。一个是.c
为后缀的C文件SeqList.c
:用来实现函数接口。还有一个是.c
为后缀的C文件test.c
:用来测试代码。我们只要在SeqList.c
文件和test.c
文件最上面包含一下SeqList.h
文件,整个程序链接就OK了。
<font color=red size=4>下面是所需头文件,宏定义,以及顺序表的定义的代码:</font>
// 防止SeqList.h被重复包含
#pragma once
// 所需头文件:
// 输入输出所需头文件
#include <stdio.h>
// realloc,free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>
// 初始化容量,每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;
// 顺序表
typedef struct SeqList
{
// a指向一个在堆上的空间(就是顺序表)
SLDateType* a;
// 顺序表数据个数
int size;
// 顺序表容量
int capacity;
}SL; // typedef将struct SeqList重新命名为SL
- 定义好主体后,首先是对顺序表初始化。可以看到,上面的结构体也就是顺序表里面的成员都是未初始化的,所以第一步就是将他们初始化,这里引出一个初始化函数接口,下面是相关功能代码实现:
// 初始化顺序表
void SLInit(SL* ps)
{
// 这里断言是防止ps为一个空指针(传个NULL直接暴打)
assert(ps);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
打印顺序表
-
该接口放在前面实现是为了后面能够更好的测试:通过对顺序表的数据的一个直观的展现,我们可以及时发现某些接口的bug。
-
顺序表的结构体中定义了一个
size
,这里size
的作用就体现出来了(当然,size
的作用很大,不止是这里),我们可以通过size
来对顺序表中的数据顺序打印:
// 打印顺序表
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);
printf("\n");
}
检查容量
-
当我们在顺序表中插入数据时,一定要检查容量够不够用,如果不够的话,再插入数据,就会出现非法访问空间的问题,此时程序会报错,因此这里要扩容。
-
由于
size
是统计数据个数的,所以,只要size
等于capacity
,就说明当前的容量已经满了,需要扩容。由于初始化顺序表时没有分配空间,所以当我们第一次插入数据的时候就要扩容,每次扩容增加的容量大小为INIT_CAPACITY(8)
,而每增容一次,capacity
就要更新一次。
下面是相关功能代码实现:
// 检查容量
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;
// 开始没有空间,其功能相当于malloc
SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);
assert(tmp);
ps->a = tmp;
ps->capacity = newcapacity;
}
}
这一步实现后,每次插入数据就要引用该函数检查一下容量。
判空
- 判空很容易理解,这里如果通讯录为空,返回真,不为空,返回假。
下面是相关功能代码实现:
// 判空
bool SLEmpty(SL* ps)
{
assert(ps);
return ps->size == 0;
}
顺序表数据个数
- 该功能只要返回
size
就ok啦。
// 顺序表数据个数
int SLSize(SL* ps)
{
assert(ps);
return ps->size;
}
尾部插入
- 尾部插入就是在最末尾插入数据,首先当然是要检查一下容量,然后将要插入的数据插入进去,最后
size
计数一次,该函数的功能就OK啦。
下面是相关功能代码实现:
void SLPushBack(SL* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->a[ps->size++] = x;
}
尾部删除
-
如果顺序表中没有数据,那还删个啥呢?直接
assert
暴打,也就是判断一下size
是否大于0
(判空一下)。 -
尾部删除实际上只要
size
减一就可以了,至于删除的那个数据改不改为0
,都无所谓,因为打印不会打印到那个数据,还有就是,不能在那个位置释放空间(free
),这是规定不允许的,要有占着茅坑不拉屎的原则。
下面是相关功能代码实现:
void SLPopBack(SL* ps)
{
assert(ps && !SLEmpty(ps));
ps->size--;
}
头部插入
-
对顺序表头部的操作相比于尾部的操作麻烦的多,主要是因为,顺序表是一段连续的空间,在头部插入或者删除需要挪动后面的数据,这样以来,整个程序的效率也会降低,但这是没办法的,该挪动还是嘚挪动,不然怎么进行操作对吧。==(顺序表最明显的缺点)==
-
挪动的时候,只要从后面开始依次将每一个数据向后挪动一位,直到将第一个数据挪动完停止挪动,再将要插入的数据放在头部即可,这里需要注意以下边界问题。
-
当然
size
要计数一次,可不敢忘记了。
下面是相关功能代码实现:
void SLPushFront(SL* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--) ps->a[i] = ps->a[i - 1];
ps->a[0] = x;
ps->size++;
}
头部删除
-
只要是删除就要
assert
判断是否要暴打。 -
有了头部插入的经验,头部删除显得游刃有余了,相反的,只要将每个数据向前挪动,也就是依次覆盖即可,最终第一个数据被覆盖的无影无踪。
-
当然
size
要减一,可不敢忘记了。
下面是相关功能代码实现:
void SLPopFront(SL* ps)
{
assert(ps && !SLEmpty(ps));
for (int i = 0; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
ps->size--;
}
在pos位置插入数据
-
首先插入需要检查容量。
-
在
pos
位置插入数据,首先对这个pos
理解一下:本章的pos
不是下标,注意!他不是下标,而是规规矩矩的第几个位置,比如一串数列1,2,3,4
,第一个位置就是只1
所占的位置,如果要在第一个位置插入,那么1
就会到当前的2
的位置上去,也就是所谓的第二个位置。所以,这个pos
,是以用户角度出发,但我们实现函数的时候要脑子清醒:我们操作的实际上是下标。 -
同样的,与头插差不多,都是要挪动数据,只不过挪动的数据范围不同,要操作的数的位置也不同,这也就更加要注意边界问题了。
-
当然,操作完成后,要记得
size
计数一次噢。
下面是相关功能代码实现:
// 在pos位置插入,pos表示在第几个位置插入,不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];
ps->a[pos - 1] = x;
ps->size++;
}
有了该函数之后,前面的头插尾插都可以复用这个函数。
删除pos位置的数据
-
既然是删除,首先就要来一套
assert
检查看是否要毒打。 -
删除,就是将
pos
后面的数据依次往前挪,最终pos
这个位置上的数据会被覆盖,因为会挪动数据,依次效率也不是很高。 -
当然别忘了
size
减一噢。
下面是相关功能代码实现:
// 删除第pos个数据,pos不是下标,表示删除第几个
void SLErase(SL* ps, int pos)
{
assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);
for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
ps->size--;
}
有了该函数后,前面的头删,尾删都可以复用这个函数。
查找数据
- 查找数据就是遍历一遍顺序表,如果找到了就返回
下标加一
,没找到就返回-1
。
下面是相关功能代码实现:
// 查找数据,返回正常对应位置,不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == val) return i + 1;
return -1;
}
修改数据
-
修改数据也是根据
pos
位置来修改的,传入你想修改的位置,然后传入修改后的新数据,然后直接在pos - 1
(下标)位置修改,不需要遍历。 -
如果传入的
pos
不正确,直接暴打。 -
当然也可以先查找,在修改,也就是说,查找数据和修改数据两个接口函数可以一起用。
**下面是相关功能代码实现:**
```c
// 修改数据,修改pos正常对应位置,不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{
assert(ps && pos > 0 && pos <= ps->size);
ps->a[pos - 1] = Mval;
}
销毁顺序表
- 由于向堆申请了空间,因此程序结束后需要将空间返还给系统,这里说的粗暴了点,销毁顺序表。
下面是相关功能代码实现:
// 销毁顺序表
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->size = 0;
}
整体代码
<font color=red size=5>SeqList.h</font>
// 防止SeqList.h被重复包含
#pragma once
// 所需头文件:
// 输入输出所需头文件
#include <stdio.h>
// realloc,free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>
// 初始化容量,每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;
// 顺序表
typedef struct SeqList
{
// a指向一个在堆上的空间(就是顺序表)
SLDateType* a;
// 顺序表数据个数
int size;
// 顺序表容量
int capacity;
}SL; // typedef将struct SeqList重新命名为SL
// 初始化顺序表
void SLInit(SL* ps);
// 打印顺序表
void SLPrint(SL* ps);
// 检查容量
void SLCheckCapacity(SL* ps);
// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);
// 在pos位置插入,pos表示在第几个位置插入,不是下标
void SLInsert(SL* ps, int pos, SLDateType x);
// 删除第pos个数据,pos不是下标,表示删除第几个
void SLErase(SL* ps, int pos);
// 查找数据,返回对应位置,不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val);
// 修改数据
void SLModify(SL* ps, int pos, SLDateType Mval);
// 判空
bool SLEmpty(SL* ps);
// 顺序表数据个数
int SLSize(SL* ps);
// 使用了realloc,在堆上申请了空间,程序结束时要返还空间给系统
// 销毁顺序表
void SLDestroy(SL* ps);
<font color=red size=5>SeqList.c</font>
#include "SeqList.h"
// 初始化顺序表
void SLInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
// 打印顺序表
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);
printf("\n");
}
// 检查容量
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;
// 开始没有空间,其功能相当于malloc
SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);
assert(tmp);
ps->a = tmp;
ps->capacity = newcapacity;
}
}
// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x)
{
//assert(ps);
//SLCheckCapacity(ps);
//ps->a[ps->size++] = x;
SLInsert(ps, ps->size + 1, x);
}
void SLPopBack(SL* ps)
{
//assert(ps && !SLEmpty(ps));
//ps->size--;
SLErase(ps, ps->size);
}
void SLPushFront(SL* ps, SLDateType x)
{
//assert(ps);
//SLCheckCapacity(ps);
//for (int i = ps->size; i > 0; i--) ps->a[i] = ps->a[i - 1];
//ps->a[0] = x;
//ps->size++;
SLInsert(ps, 1, x);
}
void SLPopFront(SL* ps)
{
//assert(ps && !SLEmpty(ps));
//for (int i = 0; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
//ps->size--;
SLErase(ps, 1);
}
// 在pos位置插入,pos表示在第几个位置插入,不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];
ps->a[pos - 1] = x;
ps->size++;
}
// 删除第pos个数据,pos不是下标,表示删除第几个
void SLErase(SL* ps, int pos)
{
assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);
for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];
ps->size--;
}
// 查找数据,返回正常对应位置,不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == val) return i + 1;
return -1;
}
// 修改数据,修改pos正常对应位置,不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{
assert(ps && pos > 0 && pos <= ps->size);
ps->a[pos - 1] = Mval;
}
// 判空
bool SLEmpty(SL* ps)
{
assert(ps);
return ps->size == 0;
}
// 顺序表数据个数
int SLSize(SL* ps)
{
assert(ps);
return ps->size;
}
// 销毁顺序表
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->size = 0;
}
<font color=red size=5>test.c</font>
#include "SeqList.h"
void test1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPrint(&s);
SLPushBack(&s, 2);
SLPrint(&s);
SLPushBack(&s, 3);
SLPrint(&s);
SLPushBack(&s, 4);
SLPrint(&s);
SLPushBack(&s, 5);
SLPrint(&s);
SLPushBack(&s, 6);
SLPrint(&s);
SLDestroy(&s);
}
void test2()
{
SL s;
SLInit(&s);
SLPushFront(&s, 1);
SLPrint(&s);
SLPushFront(&s, 2);
SLPrint(&s);
SLPushFront(&s, 3);
SLPrint(&s);
SLPushFront(&s, 4);
SLPrint(&s);
SLPushFront(&s, 5);
SLPrint(&s);
SLPushFront(&s, 6);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestroy(&s);
}
void test3()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPrint(&s);
SLInsert(&s, 3, 99999);
SLPrint(&s);
SLErase(&s, 3);
SLPrint(&s);
SLModify(&s, SLFind(&s, 3), 99999);
SLPrint(&s);
SLDestroy(&s);
}
int main()
{
//test1();
//test2();
test3();
return 0;
}
写在最后
<font color=red size=4>学到这里,数据结构总算是入门了,当然数据结构后面还有很长的路要走,要继续努力!</font>
<font color=blue size=4>感谢阅读本小白的博客,错误的地方请严厉指出噢!</font>
标签:ps,顺序,int,void,pos,SL,数据结构,size From: https://blog.51cto.com/u_16019252/6456181