首页 > 其他分享 >数据结构之顺序表

数据结构之顺序表

时间:2024-04-07 19:02:37浏览次数:26  
标签:ps arr 顺序 void SL printf 数据结构 con

目录

一、顺序表源代码

1.1 SeqList.h

1.2 SeqList.c

二、顺序表的应用

2.1 Contact.h

2.2 Contact.c

2.3 SeqList.h

2.4 SeqList.c

2.5 main.c


一、顺序表源代码

顺序表的底层实现为数组,源代码以整形数据为例,使用C语言编写

1.1 SeqList.h

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;//数据类型
	int size;		//有效数据个数
	int capacity;	//空间大小
}SL;


//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL s);

//头部插入
void SLPushFront(SL* ps, SLDataType x);
//尾部插入
void SLPushBack(SL* ps, SLDataType x);
//头部删除
void SLPopFront(SL* ps);
//尾部插入
void SLPopBack(SL* ps);

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置擦除数据
void SLErase(SL* ps, int pos);
//寻找数据
int SLFind(SL* ps, SLDataType x);

1.2 SeqList.c

#include"SeqList.h"

void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}
//顺序表的初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr != NULL) 
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//检查空间是否足够
void SLCheckCapacity(SL* ps)
{
	//插入数据之前先看空间够不够
	if (ps->capacity == ps->size)
	{
		int newCapacity = 0;
		if (ps->capacity == 0)
		{
			newCapacity = 4;
		}
		else
		{
			newCapacity = 2 * ps->capacity;
		}
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//温柔的解决方式
	if (ps == NULL)
	{
		return 1;
	}
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//先让顺序表中已有的数据整体往后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	--ps->size;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//数据整体往前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1]; 
	}
	ps->size--;
}
//指定位置前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	//向后移动数据
	for (int i = ps->size ; i > pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
//指定位置擦除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//寻找数据
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
			break;
		}
	}
	if (i+1==ps->size )
	{
		return -1;
	}

}

二、顺序表的应用

实现基础通讯录的编写,本文使用C语言编写。基于顺序表的底层逻辑,仅仅将数据类型修改为了自定义数据类型-结构体。

2.1 Contact.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#define NAME_MAX 20
#define GENDER_MAX 10
#define TEL_MAX 20
#define ADDRESS_MAX 100


//定义联系人自定义数据类型
typedef struct personInfo
{
	char name[NAME_MAX];
	char gender[GENDER_MAX];
	int age;
	char tel[TEL_MAX];
	char address[ADDRESS_MAX];
}peoInfo;


typedef struct SeqList Contact;

// 初始化通讯录
void ContactInit(Contact* con);
// 添加通讯录数据
void ContactAdd(Contact* con);
// 删除通讯录数据
void ContactDel(Contact* con);
// 展⽰通讯录数据
void ContactShow(Contact* con);
// 查找通讯录数据
void ContactFind(Contact* con);
// 修改通讯录数据
void ContactModify(Contact* con);
// 销毁通讯录数据
void ContactDestroy(Contact* con);

2.2 Contact.c

#include"Contact.h"
#include"SeqList.h"

int FindByname(Contact* con, char* cmp)
{
	for (int i = 0; i < con->size; i++)
	{
		if (strcmp(con->arr[i].name, cmp) == 0)
		{
			return i;
			break;
		}
	}
	return -1;
}

// 初始化通讯录
void ContactInit(Contact* con)
{
	SLInit(con);
}
// 添加通讯录数据
void ContactAdd(Contact* con)
{
	peoInfo info;
	printf("请输入要添加的联系人姓名\n");
	scanf("%s", info.name);

	printf("请输入要添加的联系人性别\n");
	scanf("%s", info.gender);

	printf("请输入要添加的联系人年龄\n");
	scanf("%d", &info.age);

	printf("请输入要添加的联系人电话\n");
	scanf("%s", info.tel);

	printf("请输入要添加的联系人住址\n");
	scanf("%s", info.address);

	SLPushBack(con, info);
}
// 删除通讯录数据
void ContactDel(Contact* con)
{
	char name[NAME_MAX];
	printf("请输入要删除的联系人姓名\n");
	scanf("%s", name);
	int ret = FindByname(con, name);
	if (ret >= 0)
	{
		SLErase(con, ret);
		printf("删除成功!\n");
	}
	else
	{
		printf("数据不存在!\n");
		return;
	}
}
// 展⽰通讯录数据
void ContactShow(Contact* con)
{
	printf("%s	%s	%s	%s	%s\n", "姓名", "性别", "年龄", "电话", "地址");
	for (int i = 0; i < con->size; i++)
	{
		printf("%s	", con->arr[i].name );
		printf("%s	", con->arr[i].gender );
		printf("%d	", con->arr[i].age );
		printf("%s	", con->arr[i].tel );
		printf("%s	", con->arr[i].address );
		printf("\n");
	}
}
// 查找通讯录数据
void ContactFind(Contact* con)
{
	char name[NAME_MAX];
	printf("请输入要查找的联系人姓名\n");
	scanf("%s", name);
	int ret = FindByname(con, name);
	if (ret>=0)
	{
		printf("查找成功!\n");
		printf("%s	%s	%s	%s	%s\n", "姓名", "性别", "年龄", "电话", "地址");
		printf("%s	", con->arr[ret].name);
		printf("%s	", con->arr[ret].gender);
		printf("%d	", con->arr[ret].age);
		printf("%s	", con->arr[ret].tel);
		printf("%s	", con->arr[ret].address);
		printf("\n");
	}
	else
	{
		printf("数据不存在!\n");
		return;
	}

}
// 修改通讯录数据
void ContactModify(Contact* con)
{
	char name[NAME_MAX];
	printf("请输入要修改的联系人姓名\n");
	scanf("%s", name);
	int ret = FindByname(con, name);
	if (ret >= 0)
	{
		printf("请输入新的联系人姓名\n");
		scanf("%s", con->arr[ret].name);

		printf("请输入新的联系人性别\n");
		scanf("%s", con->arr[ret].name);

		printf("请输入新的联系人年龄\n");
		scanf("%d", &(con->arr[ret].age));

		printf("请输入新的联系人电话\n");
		scanf("%s", con->arr[ret].tel);

		printf("请输入新的联系人住址\n");
		scanf("%s", con->arr[ret].address);

		printf("修改成功!\n");
	}
	else
	{
		printf("数据不存在!\n");
		return;
	}
}
// 销毁通讯录数据
void ContactDestroy(Contact* con)
{
	SLDestroy(con);
}

2.3 SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Contact.h"
#include<string.h>

typedef peoInfo SLDataType;

typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;


//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL s);

//头部插入
void SLPushFront(SL* ps, SLDataType x);
//尾部插入
void SLPushBack(SL* ps, SLDataType x);
//头部删除
void SLPopFront(SL* ps);
//尾部删除
void SLPopBack(SL* ps);

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置擦除数据
void SLErase(SL* ps, int pos);

2.4 SeqList.c

#include"SeqList.h"

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->capacity = 0;
	ps->size = 0;
}
void SLCheck(SL* ps)
{
	assert(ps);
	if (ps->capacity == ps->size)
	{
		int newCapacity = 0;
		if (ps->capacity == 0)
		{
			newCapacity = 4;
		}
		else
		{
			newCapacity = 2 * ps->capacity;
		}
		SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//空间申请成功
		ps->arr = temp;
		ps->capacity = newCapacity;
	}
}
//头部插入
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheck(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheck(ps);
	ps->arr[ps->size++] = x;
}
//头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size-1 ; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	ps->size--;
}
//指定位置前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheck(ps);
	//向后移动数据
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
//指定位置擦除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

2.5 main.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include"SeqList.h"
#include"Contact.h"

void menu()
{
	printf("******************通讯录******************\n");
	printf("*******1.增加联系人   2.删除联系人********\n");
	printf("*******3.修改联系人   4.查找联系人********\n");
	printf("*******5.展示联系人   0.   退出  *********\n");
	printf("******************************************\n");
}


int main()
{
	int a = -1;
	Contact con;
	ContactInit(&con);

	do {
		menu();
		printf("请选择您的操作:\n");
		scanf("%d", &a);
		switch (a)
		{
		case 1:
			ContactAdd(&con);
			break;
		case 2:
			ContactDel(&con);
			break;
		case 3:
			ContactModify(&con);
			break;
		case 4:
			ContactFind(&con);
			break;
		case 5:
			ContactShow(&con);
			break;
		case 0:
			printf("退出通讯录....\n");
			break;
		default:
			printf("输入错误,请重新选择您的操作!\n");
			break;
		}
	} while (a != 0);

	ContactDestroy(&con);
	return 0;
}

标签:ps,arr,顺序,void,SL,printf,数据结构,con
From: https://blog.csdn.net/paradiso989/article/details/137289383

相关文章

  • 顺序栈功能函数(包括判断回文、数值转化、括号匹配)
    一,具体代码#include<iostream>#include<stdlib.h>usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemType;typedefintStatus;typedefstruct {   ElemType*elem;   inttop;}Sqstack;StatusInitStack(Sqstack......
  • 顺序栈和链栈的部分功能完整代码
    一、顺序栈代码#include<iostream>#include<stdlib.h>usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemType;typedefintStatus;typedefstruct {   ElemType*elem;   inttop;}Sqstack;StatusInitStack(Sqsta......
  • 1600. 王位继承顺序
    题面核心思想纯模拟!没反应过来是前序遍历~privateMap<String,List<String>>children;表示一个人的孩子当调用getInheritanceOrder时通过map搜索答案,由于孩子也有可能有孩子,无限套娃,所以通过递归搜索建立答案。建立答案的时候也不用考虑是否死亡,我们搜索完成后在去删除......
  • 【C语言】顺序表(原理+实现)
    一.原理1.线性表、顺序表线性表(Linearlist)是n个具有相同特性的数据元素的有限序列。线性表在逻辑上是线性结构,就如同一条连续的直线,但是在物理结构上不一定是连续的。顺序表(Sequencelist)是线性表的一种,但顺序表不仅在逻辑上是线性的,它在物理上同样是线性的。顺序表的底层......
  • 简单顺序链- - 将第一个链的输出作为第二个链的输入
    fromlangchain.chainsimportLLMChain,SimpleSequentialChain#简单序列链fromlangchain_community.llms.ollamaimportOllamafromlangchain_core.promptsimportPromptTemplatellm=Ollama(model="qwen:7b")template="""您的工作是根据用户建议的区域制......
  • 基于顺序表实现通讯管理系统!(有完整源码!)
    ​​​​​​​                                                                 个人主页:秋风起,再归来~                                   ......
  • 数据结构 第八章(排序算法)【上】
    写在前面:本系列笔记主要以《数据结构(C语言版)》为参考(本章部分图片来源于王道),结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言,如有错误欢迎指出。视频链接:第01周a--前言_哔哩哔哩_bilibili基数排序部分的代码参考了一位小伙伴分享的代码,特此说明一......
  • 数据结构---顺序表实现
    目录1.顺序表2.动态顺序表的实现(4)顺序表初始化(5)顺序表销毁(6)顺序表的插入a.尾插b.头插(7)顺序表的删除a.尾删b.头删(8)指定位置之前插入(9)指定位置删除(10)顺序表查找数据3.我的心得体会(可跳过)4.顺序表完整代码(1)seqlist.h文件(2)seqlist.c文件(3)test.c文件1.顺序表......
  • 数据结构:实验四:队列的操作
    一、实验目的领会队列的存储结构特点掌握环形队列中的各种基本运算算法设计熟悉利用队列解决实际问题二、实验要求实现环形队列的定义,头文件命名”SqQueue.h”。利用所定义的环形队列,设计一个算法实现下面问题的求解:问题描述:设有n个人站成一排,从左向右的编号分别为1—n,......
  • 通讯录(顺序表的应用)
    文章目录顺序表思想实现通讯录头文件接口函数主函数顺序表思想实现通讯录实现通讯录前,我们考虑一下,通讯录需要包含什么内容?联系人,联系人需要包含姓名年龄电话性别这3种基本信息。我们知道顺序表实质是个数组,如果我们让数组的每个元素都代表一个联系人,每个联系人又......