C语言数据结构之数组模拟实现顺序表流程详解

线性表和顺序表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列，这是我们广泛使用的数据结构。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

常见的线性表：顺序表、链表、栈、队列、字符串…

C语言数据结构之数组模拟实现顺序表流程详解

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

一般可以分为：

静态顺序表：使用定长数组来存储元素
动态顺序表：使用动态开辟的数组来储存元素

静态顺序表

									//定义静态数组的大小，方便后续修改

									#define MAX_SIZE 50

									//重命名数组的数据类型，方便后续修改

									typedef int SLDataType;

									//定义结构体

									//成员变量为数组和记录当前数据个数的变量

									//重命名结构体数据类型，方便书写

									typedef struct SeqList {

									    SLDataType arr[MAX_SIZE];

									    int size;

									}SL;

									//-----------------------------------------------------------------------------

									//以下是一些常见的接口的声明

									//顺序表初始化

									//利用结构体类型创建一个静态顺序表变量后，可以对其进行初始化

									void SLInit(SL* psl);

									//打印顺序表

									//把顺序表的值按照先后顺序打印出来

									void SLPrint(SL* psl);

									//检查顺序表是否已满

									//每次进行加入数据的操作的时候需要先检查是否已经满了，如果满了就不能够插入了

									void SLCheck(SL* psl);

									//顺序表的尾插

									//在顺序表的尾部在插入一个元素

									//由于是数组加入数据很方便，直接使用数组下标就可以访问到

									void SLPushBack(SL* psl, SLDataType data);

									//顺序表的尾删

									//删除顺序表尾部的数据

									void  SLPopBack(SL* psl);

									//顺序表的头插

									//在顺序表的开头加入一个数据

									void SLPushFront(SL* psl, SLDataType data);

									//顺序表的头删

									//把顺序表第一位数据删除

									void SLPopFront(SL* psl);

									//顺序表查找某个数据

									//查找顺序表中是否存在某个数据，如果有就返回对应的下标

									//如果找不到就返回-1

									int SLFind(SL* psl, SLDataType x);

									//顺序表在pos位置插入x

									//在指定下标位置插入数据x，原来x位置的数据以及后面的数据往后移动

									void SLInsert(SL* psl, size_t pos, SLDataType x);

									//顺序表删除在pos位置的数据

									void SLErase(SL* psl, size_t pos);

									//顺序表某一位置数据的修改

									void SLModify(SL* psl, size_t pos, SLDataType x);

以下是这些接口的具体实现

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

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

									//顺序表初始化

									void SLInit(SL* psl) {

									    psl->arr[0] = 0;//此处只能初始化一个元素

									    psl->size = 0;

									}

									//打印顺序表

									void SLPrint(SL* psl) {

									    int i = 0;

									    if (psl->size) {

									        for (i = 0; i < psl->size; i++) {

									            //输出格式，记得根据SLDataTyped的类型来修改

									            printf("%d ", psl->arr[i]);

									        }

									        printf("\n");

									    }

									    else {

									        printf("Null\n");

									    }

									}

									/*

									//检查顺序表是否已满

									void SLCheck(SL* psl) {

									    if (psl->size == MAX_SIZE) {

									        printf("顺序表已满，无法进行后续操作");

									    }

									}

									*/

									//顺序表的尾插

									void SLPushBack(SL* psl, SLDataType data) {

									    //插入数据要先检查空间是否已满

									    //实现方法一不够好

									    /*

									    if (psl->size == MAX_SIZE) {

									        printf("空间已满\n");

									        return;

									    }

									    else {

									        psl->arr[psl->size] = data;

									        psl->size++;

									    }*/

									    //实现方法二，简单明了

									    assert(psl->size != MAX_SIZE);

									    psl->arr[psl->size] = data;

									    psl->size++;

									}

									//顺序表的尾删

									void  SLPopBack(SL* psl) {

									    //判断是否还有元素可以删除

									    assert(psl->size);

									    psl->size--;

									}

									//顺序表的头插

									void SLPushFront(SL* psl, SLDataType data) {

									    assert(psl->size != MAX_SIZE);

									    //src用来后移数据

									    int src = psl->size;

									    while (src >= 1) {

									        psl->arr[src] = psl->arr[src - 1];

									        src--;

									    }

									    psl->arr[src] = data;

									    psl->size++;

									}

									//顺序表的头删

									void SLPopFront(SL* psl) {

									    //判断是否还有数据可以删除

									    assert(psl->size);

									    int src = 0;

									    while (src < psl->size - 1) {

									        psl->arr[src] = psl->arr[src + 1];

									        src++;

									    }

									    psl->size--;

									}

									//顺序表查找某个数据

									int SLFind(SL* psl, SLDataType x) {

									    int i = 0;

									    for (i = 0; i < psl->size; i++) {

									        if (psl->arr[i] == x) {

									            //找到了就返回该数据在顺序表中的位置

									            return  i;

									        }

									    }

									    //找不到就返回-1

									    return -1;

									}

									//顺序表在pos位置插入x

									void SLInsert(SL* psl, size_t pos, SLDataType x) {

									    assert(psl->size < MAX_SIZE);

									    assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的时候，相当于头插，尾插

									    int end = psl->size;

									    while (end > pos) {

									        psl->arr[end] = psl->arr[end - 1];

									        end--;

									    }

									    psl->arr[pos] = x;

									    psl->size++;

									}

									//顺序表删除在pos位置的数据

									void SLErase(SL* psl, size_t pos) {

									    assert(psl->size);

									    assert(pos >= 0 && pos < psl->size);

									    int start = pos + 1;

									    while (start < psl->size) {

									        psl->arr[start - 1] = psl->arr[start];

									        start++;

									    }

									    psl->size--;

									}

									//顺序表某一位置数据的修改

									void SLModify(SL* psl, size_t pos, SLDataType x) {

									    assert(psl->size);

									    assert(pos >= 0 && pos < psl->size);

									    psl->arr[pos] = x;

									}

上面代码的测试，我放在了Gitee上，需要的小伙伴可以参考一下

动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

									//重命名SL的数据类型，方便后续修改

									typedef int SLDataType;

									//定义结构体

									//成员变量为指向动态顺序表的指针，数据的个数，顺序表的容量

									//capacity用来管理数组的总大小，如果size与capacity相等了，就表示数组已经满了需要扩容

									//重定义结构体类型名称，方便操作

									typedef struct SeqList {

									    SLDataType* p;

									    int size;

									    int capacity;

									}SL;

									//----------------------------------------------------------------------

									//一下是一些常用的接口，与静态顺序表差不多

									//SL初始化

									void SLInit(SL* ps);

									//SL空间检查

									//如若size与capacity相等表示数组已经满了，需要扩容

									void SLCheckCapacity(SL* ps);

									//SL打印

									void SLPrint(SL* ps);

									//SL销毁

									//因为数组是动态开辟的，所以在最后不使用的数组的时候要释放空间

									void SLDestory(SL* ps);

									//SL尾插

									void SLPushBack(SL* ps,SLDataType x);

									//SL尾删

									void SLPopBack(SL* ps);

									//SL头插

									void SLPushFront(SL* ps, SLDataType x);

									//SL头删

									void SLPopFront(SL* ps);

									//SL查找某个数据

									//如果能找到，返回该数据在顺序表中下标

									int SLFind(SL* ps, SLDataType x);

									//SL在pos位置插入x

									void SLInsert(SL* ps, size_t pos, SLDataType x);

									//SL删除pos位置的值

									void SLErase(SL* ps, size_t pos);

									//SL修改某一位置的数据

									void SLModity(SL* ps, size_t pos, SLDataType x);

以下是具体的实现

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

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

									//动态顺序表的实现

									#include"DynamicSeqList.h"

									//SL初始化

									void SLInit(SL* ps) {

									    ps->p = NULL;

									    ps->capacity = 0;

									    ps->size = 0;

									}

									//SL空间检查

									void SLCheckCapacity(SL* ps) {

									    if (ps->size == ps->capacity) {

									        ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity;

									        SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType));

									        if (tmp == NULL) {

									            printf("realloc fail\n");

									            exit(-1);

									        }

									        ps->p = tmp;

									    }

									}

									//SL打印

									void SLPrint(SL* ps) {

									    if (ps->size == 0) {

									        printf("顺序表为空\n");

									    }

									    else {

									        int i = 0;

									        for (i = 0; i < ps->size; i++) {

									            //打印格式记得根据SLDataType的类型来修改

									            printf("%d ", ps->p[i]);

									        }

									        printf("\n");

									    }

									}

									//SL销毁

									//这里并没有完全销毁结构体s，只是把成员变量都赋值为0

									void SLDestory(SL* ps) {

									    free(ps->p);

									    ps->p = NULL;

									    ps->size = ps->capacity = 0;

									}

									//SL尾插

									void SLPushBack(SL* ps, SLDataType x) {

									    SLCheckCapacity(ps);

									    ps->p[ps->size] = x;

									    ps->size++;

									}

									//SL尾删

									void SLPopBack(SL* ps) {

									    //删除数据需要判断一下顺序表是否为空

									    assert(ps->size > 0);

									    ps->size--;

									}

									//SL头插

									void SLPushFront(SL* ps, SLDataType x) {

									    SLCheckCapacity(ps);

									    int end = ps->size;

									    while (end > 0) {

									        ps->p[end] = ps->p[end - 1];

									        end--;

									    }

									    ps->p[end] = x;

									    ps->size++;

									}

									//SL头删

									void SLPopFront(SL* ps) {

									    //删除数据需要判断一下顺序表是否为空

									    assert(ps->size > 0);

									    int start = 0;

									    while (start < ps->size - 1) {

									        ps->p[start] = ps->p[start + 1];

									        start++;

									    }

									    ps->size--;

									}

									//SL查找某个数据

									int  SLFind(SL* ps, SLDataType x) {

									    //需要判断顺序表是否为空，可以用assert，也可以用if判断

									    assert(ps->size);

									    int i = 0;

									    for (i = 0; i < ps->size; i++) {

									        if (x == ps->p[i]) {

									            return i;

									        }

									    }

									    return -1;

									}

									//SL在pos位置插入x

									//当pos为0或者pos为size时，相当于头插、尾插

									void SLInsert(SL* ps, size_t pos, SLDataType x) {

									    SLCheckCapacity(ps);

									    assert(pos >= 0 && pos <= ps->size);

									    int end = ps->size;

									    while (end > pos) {

									        ps->p[end] = ps->p[end - 1];

									        end--;

									    }

									    ps->p[end] = x;

									    ps->size++;

									}

									//SL删除pos位置的值

									void SLErase(SL* ps, size_t pos) {

									    //判断要删除的位置是否在size之内

									    assert(pos >= 0 && pos < ps->size);

									    int start = pos + 1;

									    while (start < ps->size) {

									        ps->p[start - 1] = ps->p[start];

									        start++;

									    }

									    ps->size--;

									}

									//SL修改某一位置的数据

									void SLModity(SL* ps, size_t pos, SLDataType x) {

									    //判断要修改的位置是否在size之内

									    assert(pos >= 0 && pos < ps->size);

									    ps->p[pos] = x;

									}

同样的，我自己写的一些小测试也在Gitee上，需要的小伙伴可以去看看

到此这篇关于C语言数据结构之数组模拟实现顺序表流程详解的文章就介绍到这了,更多相关数组模拟实现顺序表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/weixin_61021362/article/details/121411921

C语言数据结构之数组模拟实现顺序表流程详解

目录

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

相关文章

热门资讯

C语言 数据结构之数组模拟实现顺序表流程详解

目录

线性表和顺序表

线性表

顺序表

静态顺序表

动态顺序表

相关文章

热门资讯

C语言数据结构之数组模拟实现顺序表流程详解