devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构入门——顺序表（SeqList）详解（初始化、增、删、查、改）

作者：盐析白兔 | 2024-06-28 01:37:52

赞

踩

seqlist

SeqList顺序表

1. 线性表介绍

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述
本篇博客我们主要介绍一下顺序表的内容，最后会给出顺序表的应用，也就是之前拖了大家很久的通讯录动态版。

2. 顺序表

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

2.1 顺序表的结构介绍

  1. 静态顺序表：使用定长数组存储元素。
    最直接的一个案例就是我们之前博客中写的通讯录静态版。
    在这里插入图片描述

  2. 动态顺序表：使用动态开辟的数组存储。
    需要用到动态内存开辟函数，大概结构如下：
    在这里插入图片描述
    我们之前也讲到过，静态的顺序表是有一定的缺陷的，所以我们之后的顺序表会使用动态顺序表。

2.2 顺序表的定义和接口声明——SeqList.h

#pragma once
// SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDateType;//顺序表的数据类型
typedef struct SeqList
{
	SLDateType* a;
	size_t size;//实际存储的数据个数
	size_t capacity; // unsigned int，顺序表容量
}SeqList;

// 对数据的管理:增删查改 

//初始化顺序表
void SeqListInit(SeqList* ps);

//销毁顺序表
void SeqListDestroy(SeqList* ps);

//打印顺序表数据信息
void SeqListPrint(SeqList* ps);

//在尾部增加数据
void SeqListPushBack(SeqList* ps, SLDateType x);

//在头部增加数据
void SeqListPushFront(SeqList* ps, SLDateType x);

//在头部删除数据
void SeqListPopFront(SeqList* ps);

//在尾部删除数据
void SeqListPopBack(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

  • 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

2.3 顺序表接口函数的具体实现——SeqList.c

#include "SeqList.h"

//检查顺序表容量与扩容
static void CheckSeqList(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->size == 0 ? 4 : 2 * ps->capacity;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}


//初始化顺序表
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//销毁顺序表
void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//打印顺序表数据信息
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//在尾部增加数据
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	//assert(ps);
	//CheckSeqList(ps);
	//ps->a[ps->size] = x;
	//ps->size++;
	SeqListInsert(ps, ps->size, x);
}

//在头部增加数据
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	//assert(ps);
	//CheckSeqList(ps);
	//ps->size++;
	//for (int i = ps->size; i > 0; i--)
	//{
	//	ps->a[i] = ps->a[i - 1];
	//}
	//ps->a[0] = x;
	SeqListInsert(ps, 0, x);
}

//在头部删除数据
void SeqListPopFront(SeqList* ps)
{
	/*assert(ps);
	CheckSeqList(ps);
	for (int i = 0; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;*/
	SeqListErase(ps, 0);
}

//在尾部删除数据
void SeqListPopBack(SeqList* ps)
{
	//assert(ps);
	//ps->size--;
	SeqListErase(ps, ps->size);
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
		{
			return i;
		}
	}
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	CheckSeqList(ps);
	ps->size++;
	for (int i = ps->size - 1; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

  • 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

3. 顺序表的应用——通讯录(动态版)

这一版的通讯录除了动态开辟内存还有文件操作的功能，大家可以自行删减。

3.1 通讯录定义与接口函数声明——MailList.h

//头文件包含
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <windows.h>

//define 宏定义
#define MAX_DATA 100
#define MAX_NAME 20
#define MAX_SEX 6
#define MAX_TELE 12
#define MAX_ADDR 30
//默认容量
#define DEFAULT_CAPACITY 3
//默认添加个数
#define DEFAULT_ADD 2

//创建结构体
//通讯录成员信息
struct Information
{
	char name[MAX_NAME];
	char sex[MAX_SEX];
	int age;
	char tele[MAX_TELE];
	char addr[MAX_ADDR];
};
//通讯录
struct MailList
{
	struct Information* data;
	int count;
	int capacity;
};

/*函数声明*/

//初始化通讯录
void InintMailList(struct MailList* pl);

//添加联系人
void AddInformation(struct MailList* pl);

//显示通讯录信息
void ShowMailList(struct MailList* pl);

//删除联系人
void DelInformation(struct MailList* pl);

//查找联系人
void SearchInformation(struct MailList* pl);

//修改联系人信息
void ModifyInformation(struct MailList* pl);

//按名字排序联系人
void SortMailList(struct MailList* pl);

//销毁通讯录
void DestoryMailList(struct MailList* pl);

//保存通讯录信息
void SaveMailList(struct MailList* pl);

//读取文件信息
void LoadMailList(struct MailList* pl);

  • 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

3.2 通讯录接口函数具体实现——MailList.c

#include "MailList.h"

//自动检查通讯录容量并且扩容
static int Check_MailList(struct MailList* pl)
{
	if (pl->capacity == pl->count)
	{
		struct Information* ptr = realloc(pl->data, (DEFAULT_ADD + pl->capacity) * sizeof(struct Information));
		pl->capacity += DEFAULT_ADD;
		if (ptr == NULL)
		{
			perror("Check_MaliList");
			return 0;
		}
		else
		{
			printf("通讯录已满，系统已经自动扩充通讯录\n");
			return 1;
		}
	}
	return 1;
}
//读取文件信息
void LoadMailList(struct MailList* pl)
{
	//打开文件
	FILE* pfr = fopen("data.txt", "r");
	if (pfr == NULL)
	{
		perror("LoadMailList::fopen");
		return;
	}

	//操作文件
	struct Information tmp = { 0 };
	while (fread(&tmp, sizeof(struct Information), 1, pfr))
	{
		pl->data[pl->count] = tmp;
		pl->count++;
		Check_MailList(pl);
	}
	//关闭文件
	fclose(pfr);
	pfr = NULL;
}
//初始化通讯录
void InintMailList(struct MailList* pl)
{
	assert(pl);
	pl->data = (struct Information*)calloc(DEFAULT_CAPACITY, sizeof(struct Information));
	pl->capacity = DEFAULT_CAPACITY;
	pl->count = 0;
	LoadMailList(pl);
}

//添加联系人
void AddInformation(struct MailList* pl)
{
	if (0 == Check_MailList(pl))
	{
		printf("通讯录已满!\n");
	}
	printf("请输入想要添加的联系人的姓名:>");
	scanf("%s", pl->data[pl->count].name);
	printf("请输入想要添加的联系人的年龄:>");
	scanf("%d", &pl->data[pl->count].age);
	printf("请输入想要添加的联系人的性别:>");
	scanf("%s", pl->data[pl->count].sex);
	printf("请输入想要添加的联系人的电话:>");
	scanf("%s", pl->data[pl->count].tele);
	printf("请输入想要添加的联系人的住址:>");
	scanf("%s", pl->data[pl->count].addr);
	pl->count++;
	printf("添加联系人成功！");
}

//显示通讯录信息
void ShowMailList(struct MailList* pl)
{
	if (!pl->count)
	{
		printf("通讯录为空！\n");
	}
	else
	{
		printf("%-20s\t%-6s\t%-6s\t%-12s\t%-30s\n", "姓名", "性别", "年龄", "电话", "地址");
		for (int i = 0; i < pl->count; i++)
		{
			printf("%-20s\t%-6s\t%-d\t%-12s\t%-30s\n", pl->data[i].name,
				pl->data[i].sex,
				pl->data[i].age,
				pl->data[i].tele,
				pl->data[i].addr);
		}
	}
}

//通过名字查找联系人
static int FindByName(struct MailList* pl, char n[])
{
	for (int i = 0; i < pl->count; i++)
	{
		if (0 == strcmp(pl->data[i].name, n))
		{
			return i;
		}
	}
	return -1;
}

//通过名字排序
CmpByName(const void* e1, const void* e2)
{
	return strcmp(((struct Information*)e1)->name, ((struct Information*)e2)->name);
}

//删除联系人
void DelInformation(struct MailList* pl)
{
	char name[MAX_NAME] = { 0 };
	printf("请输入想要删除的联系人的名字:>");
	scanf("%s", name);
	int ret = FindByName(pl, name);
	if (-1 == ret)
	{
		printf("没找到该联系人!\n");
	}
	else
	{
		for (int i = ret; i < pl->count - 1; i++)
		{
			pl->data[i] = pl->data[i + 1];
		}
		pl->count--;
		printf("删除成功!\n");
	}
}

//查找联系人
void SearchInformation(struct MailList* pl)
{
	char name[MAX_NAME] = { 0 };
	printf("请输入想要查找的联系人的姓名:>");
	scanf("%s", name);
	int ret = FindByName(pl, name);
	if (-1 == ret)
	{
		printf("没找到该联系人!\n");
	}
	else
	{
		printf("找到了！\n");
		printf("%-20s\t%-6s\t%-6s\t%-12s\t%-30s\n", "姓名", "性别", "年龄", "电话", "地址");
		printf("%-20s\t%-6s\t%-d\t%-12s\t%-30s\n", pl->data[ret].name,
			pl->data[ret].sex,
			pl->data[ret].age,
			pl->data[ret].tele,
			pl->data[ret].addr);
	}
}

//修改联系人信息
void ModifyInformation(struct MailList* pl)
{
	char name[MAX_NAME];
	printf("请输入想要修改的联系人的姓名:>");
	scanf("%s", name);
	int ret = FindByName(pl, name);
	if (-1 == ret)
	{
		printf("没有找到该联系人！\n");
	}
	else
	{
		printf("请输入想要添加的联系人的姓名:>");
		scanf("%s", pl->data[pl->count].name);
		printf("请输入想要添加的联系人的年龄:>");
		scanf("%d", &pl->data[pl->count].age);
		printf("请输入想要添加的联系人的性别:>");
		scanf("%s", pl->data[pl->count].sex);
		printf("请输入想要添加的联系人的电话:>");
		scanf("%s", pl->data[pl->count].tele);
		printf("请输入想要添加的联系人的住址:>");
		scanf("%s", pl->data[pl->count].addr);
		printf("修改联系人成功！ \n");
	}
}

//通过名字排序通讯录
void SortMailList(struct MailList* pl)
{
	printf("排序中...\n");
	qsort(pl, pl->count, sizeof(struct Information), CmpByName);
	Sleep(3000);
	printf("排序完成！\n");
}

//销毁通讯录
void DestoryMailList(struct MailList* pl)
{
	free(pl->data);
	pl->data = NULL;
	pl->capacity = 0;
	pl->count = 0;
	printf("正在并退出通讯录...\n");
	Sleep(3000);
}

//保存通讯录信息
void SaveMailList(struct MailList* pl)
{
	//打开文件，并且以二进制读取
	FILE* pfw = fopen("data.txt", "wb");
	if (pfw == NULL)
	{
		perror("SaveMailList::fopen");
		return;
	}

	//操作文件,保存数据
	for (int i = 0; i < pl->count; i++)
	{
		fwrite(pl->data + i, sizeof(struct Information), 1, pfw);
	}

	//关闭文件
	fclose(pfw);
	pfw = NULL;
}

  • 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
  • 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
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229

3.3 通讯录菜单、主要逻辑实现——test.c

#include "MailList.h"
enum Option
{
	EXIT,
	ADD,
	DEL,
	SEARCH,
	MODIFY,
	SHOW,
	SORT,
};
void menu()
{
	printf("**************************************\n");
	printf("*****    1.add      2.del        *****\n");
	printf("*****    3.search   4.modify     *****\n");
	printf("*****    5.show     6.sort       *****\n");
	printf("*****         0.exit             *****\n");
	printf("**************************************\n");

}
int main()
{
	struct MailList list;
	int input = -1;
	InintMailList(&list);
	do
	{
		menu();
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case ADD:
			AddInformation(&list);
			break;
		case DEL:
			DelInformation(&list);
			break;
		case SEARCH:
			SearchInformation(&list);
			break;
		case MODIFY:
			ModifyInformation(&list);
			break;
		case SHOW:
			ShowMailList(&list);
			break;
		case SORT:
			SortMailList(&list);
			break;
		case EXIT:
			SaveMailList(&list);
			DestoryMailList(&list);
			printf("退出通讯录\n程序结束\n");
			return;
			break;
		default:printf("输入不合法，请重新输入:>");
			break;
		}
		system("pause");
		system("cls");
		getchar();
	} while (1);
	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
  • 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

3.4 程序运行结果展示(部分)

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

4 总结

数据结构是我们必须掌握的知识，也是难点，希望大家坚持下去，不要放弃，之后我也会加入OJ题讲解的一些博客，希望能够帮助到大家，加油！
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/764510
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号