初阶数据结构的实现1 顺序表和链表

2024-07-19 10:06:04
开发
17

顺序表和链表

1.线性表

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

相同特性
逻辑结构：人为想象出来的数据的组织形式
物理结构：数据在想象出来的数据的组织形式。

1.1顺序表

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

1.1.1静态顺序表（不去实现）

#define N 5
typedef int SLdatatype;
typedef struct SeqList {
	SLdatatype array [N];
	int size;
};

1.1.2动态顺序表

typedef int SLdatatype;
typedef struct SeqList {
	SLdatatype *arr;
	int capacity;//容量
	int size;//有效数据个数
}SL

1.1.2.1 定义程序目标

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct SeqList {
	SLDatatype *arr;
	int capacity;//容量
	int size;//有效数据个数
}SL;

//初始化
void SLInitialize(SL*s);

//销毁
void SLDestroy(SL*s );

//打印顺序表
void SLPrint(SL* ps);


//插入数据
//尾插
void SLPushBack(SL*s, SLDatatype x);

//头插
void SLPushFront(SL*s, SLDatatype x);

//尾删
void SLPopBack(SL* s);

//头删
void SLPopFront(SL* s);

//在指定位置插入数据
void SLInsert(SL* s, SLDatatype x, int pos);

//在指定位置删除数据
void SLErase(SL* s,int pos);

//查找数据
int SLFind(SL* s, SLDatatype x);

1.1.2.2 设计程序

面向程序员自身的，能实现包括顺序表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.1.2.3编写代码

void SLInitialize(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->size == ps->capacity)
	{
		//增容
		//若capacity为0，给个默认值，否则×2倍
		int NewCapacity = ps->capacity == 0 ? 4 : 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 SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

void SLPushBack(SL*ps, SLDatatype x)
{
	assert(ps);
	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 && ps->size);
	ps->size--;
}
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

void SLInsert(SL* ps, SLDatatype x, int pos)
{
	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[ps->size] = x;
	ps->size++;

}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size&& 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);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

1.1.2.3测试和调试代码

#include"Seqlist.h"
void SLtest01()
{
	SL s;
	SLInitialize(&s);

	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	/*SLPushBack(NULL , 6);*/

	SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLPrint(&s); //4 3 2 1

	SLPopBack(&s);
	SLPrint(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLPopBack(&s);
	SLPrint(&s);
	SLPopBack(&s);
	SLPrint(&s);
	
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);

	SLInsert(&s, 11, 0);
	SLPrint(&s);
	SLInsert(&s, 22, s.size);
	SLPrint(&s);
	SLInsert(&s, 33, 1);
	SLPrint(&s);

	SLDestroy(&s);
}

int main()
{
	SLtest01();
	return 0;
}

在这里插入图片描述

1.1.2 顺序表的问题与思考

中间/头部的插入删除，时间复杂度为O(N)

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。

1.2链表

1.2.1链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的。

1.2.1.1 定义程序目标

实现

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

typedef int SLTDataType;

//定义结点结构;
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//链表的打印
void SLTPrint(SLTNode*);
//申请新结点
SLTNode* SLTBuyNode(SLTDataType);
//尾插
void SLTPushBack(SLTNode**, SLTDataType);
//头插
void SLTPushFront(SLTNode** , SLTDataType );

//删除

//尾删
void SLTPopBack(SLTNode**);
//头删
void SLTPopFront(SLTNode**);

//查找
SLTNode* SLTFind(SLTNode*, SLTDataType);

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDestroy(SLTNode** pphead);

1.2.1.2 设计程序

面向程序员自身的，能实现包括链表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.2.1.3编写代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = x;
	node->next = NULL;

	return node;
}

void SLTPushBack(SLTNode**pphead, SLTDataType x)
{
	//申请新结点
	SLTNode*NewNode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	//尾结点->新结点
	//找尾结点
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = NewNode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请新结点
	SLTNode* NewNode = SLTBuyNode(x);
	//进行头插
	NewNode->next = *pphead;
	*pphead = NewNode;
}

void SLTPopBack(SLTNode** pphead)
{
	//链表为空不可以删除
	assert(pphead && *pphead);
	//处理链表只有一个结点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找prev和ptail
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

void SLTPopFront(SLTNode** pphead)
{
	//链表为空不可以删除
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		else
		{
			pcur = pcur->next;
		}
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
		SLTPushBack(pphead, x);
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* NewNode = SLTBuyNode(x);
			while (prev->next != pos)
			{
				prev = prev->next;
			}
		prev->next = NewNode;
		NewNode->next = pos;
	}
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* NewNode = SLTBuyNode(x);
	NewNode->next = pos->next;
	pos->next = NewNode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead&&*pphead);
	assert(pos);
	if (*pphead = pos)
		SLTPopBack(pphead);
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

void SListDestroy(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

1.1.2.3测试和调试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);//1->2->3->4->NULL

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist); //4->3->2->1->NULL

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTNode* find = SLTFind(plist, 4);
	if (find == NULL)
	{
		printf("未找到！\n");
	}
	else
	{
		printf("找到了！\n");
	}
	SLTInsert(&plist, plist, 11);//4->3->2->11->1->NULL
	SLTInsertAfter(plist, 11);
	SLTPrint(plist);1->11->2->3->4->NULL

	SLTErase(&plist, plist);// 1->2->3->NULL
	SLTEraseAfter(plist);

	SLTPrint(plist);
	SListDestroy(&plist);
	SLTPrint(plist);
}
int main()
{
	SListTest01();
	return 0;
}

在这里插入图片描述

原文地址:https://blog.csdn.net/Yusei_0523/article/details/140505351 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1814119482067652608.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部