顺序表和链表的各种代码实现

news/2024/7/7 19:53:17

一、线性表

在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表（A,B,C,……，Z）是一个线性表，表中的数据元素式单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如在第一章中提到的学生基本信息表，每个学生为一个数据元素，包括学号、姓名、性别、籍贯、专业等数据项。

由以上两例可以看出，它们的数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在这序偶关系。诸如此类由n个数据特性相同的元素构成的有限序列成为线性表。对于非空的线性表或线性结构，其特点是：

（1）、存在唯一的一个被称作”第一个“的数据元素；

（2）、存在唯一的一个被称作”最后一个“的数据元素；

（3）、除第一个之外，结构中的每个数据元素均只有一个前驱；

（4）、除最后一个之外，结构中的每个数据元素均只有一个后继。

二、顺序表和链表

1、顺序表的定义:

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。
顺序表可以分为静态顺序表和动态顺序表：
静态顺序表：
静态顺序表：使用定长数组存储元素 。
存储结构 
typedef struct SeqList
{
    SLDataType x;
    int size;
}SeqList
动态顺序表： 
动态顺序表：使用动态开辟的数组存储。 
typedef struct SeqList
{
    SLDataType* Array;
    int size;     //顺序表当前的元素个数
    int capacity; //顺序表的最大容量
}

以下是实现顺序表的接口代码:

头文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}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, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
//修改顺序表pos位置的值
void SeqListModify(SeqList* ps, int pos, SLDateType x);

函数实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(sizeof(SLDateType)*4);
	ps->capacity = 4;
	ps->size = 0;
}
void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
//检查增容的函数
void CheckCapacity(SeqList* ps)
{
	if (ps->capacity == ps->size)
	{
		SLDateType* temp = (SLDateType*)realloc(ps->a, (ps->capacity * 2) * sizeof(SLDateType));
		if (temp == NULL)
		{
			perror("mallco fail");
			return;
		}
		else
		{
			ps->a = temp;
			ps->capacity = ps->capacity * 2;
		}
	}
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	//尾插首先检查增容
	CheckCapacity(ps);
	//增容完毕后开始插入数据
	ps->a[ps->size++] = x;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	//头插首先检查增容
	CheckCapacity(ps);
	//开始头插
	//往后面移动数据，从后往前移
	int end = 0;
	for (end = ps->size; end > 0; end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[end] = x;
	ps->size++;
}
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//头删
	int end = 0;
	for (end = 0; end < ps->size-1; end++)
	{
		ps->a[end] = ps->a[end + 1];
	}
	ps->size--;
}
void SeqListPopBack(SeqList* ps)
{
	assert(ps->size > 0);
	assert(ps);
	ps->size--;
}
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	//下标不可能是-1
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	//检查增容
	CheckCapacity(ps);
	int end = 0;
	for (end = ps->size; end > pos; end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int end = 0;
	for (end = pos; end < ps->size - 1; end++)
	{
		ps->a[end] = ps->a[end + 1];
	}
	ps->size--;
}
//修改函数
void SeqListModify(SeqList* ps,int pos,SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

测试文件：

define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void test1()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(&s);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 4);
	SeqListPushFront(&s, 3);
	SeqListPrint(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrint(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	//SeqListPopBack(&s);
	SeqListPrint(&s);
	SeqListDestroy(&s);
}
void test2()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListInsert(&s, 1, 2);
	SeqListPrint(&s);
}

void test3()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	/*SeqListInsert(&s, 1, 2);
	SeqListInsert(&s, 6, 6);
	SeqListInsert(&s, 0, 0);
	SeqListErase(&s, 0);
	SeqListErase(&s, 6);*/
	SeqListPrint(&s);
	int pos = SeqListFind(&s, 2);
	SeqListInsert(&s, pos, 3);
	SeqListPrint(&s);
	SeqListModify(&s, 1, 2);
	SeqListPrint(&s);
}
int main()
{
	//test1();
	//test2();
	test3();
	return 0;
}

2、单链表的定义：

概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表 中的指针链接 次序实现的 。
链表实现代码：
头文件： 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTypeData;
typedef struct SList
{
	SLTypeData data;
	struct SList* next;
}SList;
//打印函数
void SListPrint(SList* phead);
//头插函数
void SListPushFront(SList** pphead,SLTypeData x);
//头删函数
void SListPopFront(SList** pphead);
//尾插函数
void SListPushBack(SList** pphead,SLTypeData x);
//尾删函数
void SListPopBack(SList** pphead);
//查找单链表
SList* SListFind(SList* plist, SLTypeData x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SList* pos, SLTypeData x);
//单链表的修改
void SListModify(SList* pos, SLTypeData x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SList* pos);
// 单链表的销毁
void SListDestroy(SList* plist);

实现文件： 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTypeData;
typedef struct SList
{
	SLTypeData data;
	struct SList* next;
}SList;
//打印函数
void SListPrint(SList* phead);
//头插函数
void SListPushFront(SList** pphead,SLTypeData x);
//头删函数
void SListPopFront(SList** pphead);
//尾插函数
void SListPushBack(SList** pphead,SLTypeData x);
//尾删函数
void SListPopBack(SList** pphead);
//查找单链表
SList* SListFind(SList* plist, SLTypeData x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SList* pos, SLTypeData x);
//单链表的修改
void SListModify(SList* pos, SLTypeData x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SList* pos);
// 单链表的销毁
void SListDestroy(SList* plist);
测试文件： 
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void test1()
{
	SList* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	//SListPopFront(&plist);
	SListPrint(plist);
}
void test2()
{
	SList* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	//SListPopBack(&plist);
	SListPrint(plist);
}

void test3()
{
	SList* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	SList* pos = SListFind(plist,5);
	if (pos == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("%d\n", pos->data);
	}
	SListInsertAfter(pos, 6);
	SListPrint(plist);
	pos = SListFind(plist, 5);
	SListEraseAfter(pos);
	SListPrint(plist);
	SListModify(pos, 4);
	SListPrint(plist);
	SListDestroy(plist);
}
int main()
{
	//test1();
	//test2();
	test3();
	return 0;
}

双向带头循环链表的实现：

头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STListType;
typedef struct STList
{
	STListType val;
	struct STList* prev;
	struct STList* next;
}STList;
//初始化链表的函数
STList* initSTList();
//新建节点的函数
STList* BuyNode(STListType x);
//头插函数
void STListPushFront(STList* phead, STListType x);
//头删函数
void STListPopFront(STList* phead);
//尾插函数
void STListPushBack(STList* phead, STListType x);
//尾删函数
void STListPopBack(STList* phead);
//判空函数
bool EmptySTList(STList* phead);
//打印函数
void PrintSTList(STList* phead);
//查找函数
STList* FindSTList(STList* phead, STListType x);
//在任意位置插入
void STListPosInsert(STList* phead, STListType x);
//在任意位置删除
void STListPosErase(STList* phead);
//销毁函数
void DesSTList(STList* phead);

函数的实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include "STList.h"
//初始化链表的函数
STList* initSTList()
{
	STList* phead = malloc(sizeof(STList));
	phead->val = -1;
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//新建节点的函数
STList* BuyNode(STListType x)
{
	STList* newnode = (STList*)malloc(sizeof(STList));
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}
//头插函数
void STListPushFront(STList* phead, STListType x)
{
	assert(phead);
	STList* newnode = BuyNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;
}
//头删函数
void STListPopFront(STList* phead)
{
	assert(phead);
	assert(!EmptySTList(phead));
	STList* cur = phead->next;
	STList* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
	cur = NULL;
}
//尾插函数
void STListPushBack(STList* phead, STListType x)
{
	assert(phead);
	STList* newnode = BuyNode(x);
	STList* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//尾删函数
void STListPopBack(STList* phead)
{
	assert(phead);
	assert(!EmptySTList(phead));
	STList* tail = phead->prev;
	STList* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
}
//判空函数
bool EmptySTList(STList* phead)
{
	assert(phead);
	return phead->next == phead;
}

//打印函数
void PrintSTList(STList* phead)
{
	assert(phead);
	STList* cur = phead->next;
	printf("head<==>");
	while (cur != phead)
	{
		printf("%d<==>", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

//查找函数
STList* FindSTList(STList* phead, STListType x)
{
	assert(phead);
	STList* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//在任意位置前插入
void STListPosInsert(STList* pos, STListType x)
{
	assert(pos);
	STList* newnode = BuyNode(x);
	STList* prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
	prev->next = newnode;
}
//在任意位置删除
void STListPosErase(STList* pos)
{
	assert(pos);
	STList* prev = pos->prev;
	STList* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
//销毁链表
void DesSTList(STList* phead)
{
	STList* cur = phead;
	while (cur != phead)
	{
		STList* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

测试文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "STList.h"

void test1()
{
	STList* phead = initSTList();
	STListPushBack(phead, 1);
	STListPushBack(phead, 2);
	STListPushBack(phead, 3);
	STListPushBack(phead, 4);
	STListPushBack(phead, 5);
	PrintSTList(phead);
	STListPushFront(phead, 5);
	STListPushFront(phead, 4);
	STListPushFront(phead, 3);
	STListPushFront(phead, 2);
	STListPushFront(phead, 1);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	STListPopBack(phead);
	PrintSTList(phead);
	DesSTList(phead);
}
void test2()
{
	STList* phead = initSTList();
	STListPushBack(phead, 1);
	STListPushBack(phead, 2);
	STListPushBack(phead, 3);
	STListPushBack(phead, 4);
	STListPushBack(phead, 5);
	PrintSTList(phead);
	STListPushFront(phead, 5);
	STListPushFront(phead, 4);
	STListPushFront(phead, 3);
	STListPushFront(phead, 2);
	STListPushFront(phead, 1);
	/*STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);
	STListPopFront(phead);*/
	STList* pos = FindSTList(phead, 4);
	if (pos)
	{
		STListPosInsert(pos, 40);
	}
	PrintSTList(phead);
	pos = FindSTList(phead, 40);
	if (pos)
	{
		STListPosErase(pos);
	}
	PrintSTList(phead);
}

int main()
{
	//test1();
	test2();
	return 0;
}

                                                


http://lihuaxi.xjx100.cn/news/1126341.html

相关文章

进程与线程——嵌入式（驱动）软开基础（四）

进程与线程——嵌入式（驱动）软开基础（四）

1 异步IO和同步IO区别？ 答案：如果是同步IO，当一个IO操作执行时，应用程序必须等待，直到此IO执行完。相反，异步IO操作在后台运行，IO操作和应用程序可以同时运行，提高系统性能，提高IO流量。 解读：在同步文件IO中，线程启动一个IO操作然后就立即进入等待状态，直到IO操…
阅读更多...
如何在IVD行业运用IPD？

如何在IVD行业运用IPD？

IVD&#xff08;体外诊断&#xff0c;In Vitro Diagnostic&#xff09;是指对人体样本&#xff08;血液、体液、组织&#xff09;进行定性或定量的检测&#xff0c;进而判断疾病或机体功能的诊断方法。IVD目前已经成为疾病预防、诊断治疗必不可少的医学手段&#xff0c;约80%左…
阅读更多...
Java --- redis7之缓存预热+雪崩+穿透+击穿

Java --- redis7之缓存预热+雪崩+穿透+击穿

目录 一、缓存预热 二、缓存雪崩 三、缓存穿透 3.1、解决方案 3.1.1、空对象缓存或者缺省值 3.1.2、Goolge布隆过滤器Guava解决缓存穿透 四、缓存击穿 4.1、危害 4.2、解决方案 4.3、模拟百亿补贴活动案例 一、缓存预热 场景&#xff1a;MySQL有N条新记录&#xff…
阅读更多...
大数据Doris（十八）：Properties配置项和关于ENGINE

大数据Doris（十八）：Properties配置项和关于ENGINE

文章目录 Properties配置项和关于ENGINE 一、Properties配置项 二、关于ENGINE Properties配置项和关于ENGINE 一、Properties配置项 在创建表时，可以指定properties设置表属性，目前支持以下属性： replica
阅读更多...
商用密码产品认证中的随机数（二）

商用密码产品认证中的随机数（二）

商用密码产品认证中的随机数&#xff08;二&#xff09; 1 随机数相关规范概述2 随机数生成2.1 随机数发生概述2.2 编程语言自带的标准库2.3 操作系统提供的随机数2.4 第三方库2.5 使用符合密码行业要求的随机数发生器2.6 自行设计的随机数发生器 1 随机数相关规范概述 现行密…
阅读更多...
【华为OD机试python】异常的打卡记录【 2023 Q1 A卷 |100分】

【华为OD机试python】异常的打卡记录【 2023 Q1 A卷 |100分】

华为OD机试- 题目列表 2023Q1 点这里！！ 2023华为OD机试-刷题指南 点这里！！ ■ 题目描述 考勤记录是分析和考核职工工作时间利用情况的原始依据，也是计算职工工资的原始依据， 为了正确地计算职工工资和监督工资基金使用情况， 公司决定对员工的手机打卡记录进行异常排查…
阅读更多...
ChatGPT入门到高级【第四章】

ChatGPT入门到高级【第四章】

第一章&#xff1a;Chatgpt的起源和发展 1.1 人工智能和Chatbot的概念 1.2 Chatbot的历史发展 1.3 机器学习技术在Chatbot中的应用 1.4 Chatgpt的诞生和发展 第二章&#xff1a;Chatgpt的技术原理 2.1 自然语言处理技术 2.2 深度学习技术 2.3 Transformer模型 2.4 GPT模型 第…
阅读更多...
算法修炼之练气篇——练气十八层

算法修炼之练气篇——练气十八层

博主&#xff1a;命运之光 专栏&#xff1a;算法修炼之练气篇 前言&#xff1a;每天练习五道题&#xff0c;炼气篇大概会练习200道题左右&#xff0c;题目有C语言网上的题&#xff0c;也有洛谷上面的题&#xff0c;题目简单适合新手入门。&#xff08;代码都是命运之光自己写的…
阅读更多...
最新文章

Copyright @ 2022~2023