数据结构顺序表
1. 顺序表的实现
//一般在生活中用到的是动态顺序表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//typedef的目的是方便以后修改存储什么类型的数据
typedef struct SeqList
{
SLDataType* a;//指向动态开辟的数组
int size;//有效数据的个数
int capacity;//容量
}SL;
//定义顺序表的接口函数
void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void CheckCapacity(SL* ps);//增容函数
void SeqListPushBack(SL* ps,SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删
void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删
int SeqListFind(SL* ps, int pos);//查找接口
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos位置之前插入
void SeqListErase(SL* ps, int pos);//删除pos位置的数据
void SeqListDestory(SL* ps);//释放空间
- 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
然后在sqlist.c文件中实现接口
#include"SeqList.h"
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%%d ", ps->a[i]);
}
}
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
void CheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)//如果size==capacity就得增容
{
int newcapacity = ps->capacity == 0 ? 4: 2 * (ps->capacity);//如果capacity=0,就给他赋值为4,如果不为0就赋值它的2倍
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
//用一个指针接收它realloc后的地址
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}
void SeqListPushBack(SL* ps, SLDataType x)
{
CheckCapacity(ps);//先判断是否需要增容
ps->a[ps->size] = x;
ps->size++;//个数增加
}
void SeqListPopBack(SL* ps)
{
//断言的作用:如果顺序表中一个数据也没有,就没法尾删(方便找到错误)
assert(ps->size > 0);
ps->size--;
//size--就访问不到尾部,就能尾删
}
void SeqListPushFront(SL* ps, SLDataType x)
{
CheckCapacity(ps);
int end = ps->size;
while (end)
{
ps->a[end] = ps->a[end - 1];//从尾部开始,依次往后挪动一位
end--;
}
//这是end的值为0,ps->a[end]就是头
ps->a[end] = x;
ps->size++;
}
void SeqListPopFront(SL* ps)//头删
{
assert(ps->size);
int first = 1;
while (first<ps->size)
{
ps->a[first - 1] = ps->a[first];//从第二个位置开始,依次往前挪动一位
first++;
}
ps->size--;//数据个数减少
}
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] ==x)
{
return i;//i的位置就是pos的位置
}
}
return -1;//如果找不到返回-1
}
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//断言的作用:避免访问到顺序表中不存在的位置
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size;
while (end != pos)
{
ps->a[end] = ps->a[end - 1];//从pos位置开始,依次往后挪动一位
end--;
}
ps->a[pos] = x;//在pos位置插入数据
ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos <= ps->size);
while (pos <ps->size-1)
{
ps->a[pos] = ps->a[pos + 1];//从pos+1开始,依次往前挪动一位
pos++;
}
ps->size--;
}
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->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
剩下的就是在test.c中进行增删查改等功能
void TestSeqList2()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 6);
int pos = SeqListFind(&s1, 4);
if (pos != -1)
{
SeqListInsert(&s1, pos, 40);
}
pos = SeqListFind(&s1, 5);
if (pos != -1)
{
SeqListErase(&s1, pos);
}
SeqListPrint(&s1);
SeqListDestory(&s1);
}
int main()
{
TestSeqList2();
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
值得注意的是:
头插,尾插,头删,尾删都可以用 SeqListInsert 和 SeqListErase 代替
比如:
头插就可以直接调用SeqListInsert(ps,0,x);
尾插调用SeqListInsert(ps,ps->size,x);
头删调用SeqListErase(ps,0);
尾删调用SeqListErase(ps,ps->size);
推荐阅读