【数据结构】线性表与顺序表

謓泽

发布于 2024-07-29 08:34:18

790

发布于 2024-07-29 08:34:18

文章被收录于专栏：【C】系列

前言

概述⇢数据结构🐟算法真的很难对于刚接触的新手来说，所以希望在学习这个知识点的小伙伴们以及博主自己都可以坚持下来。

⛳来和博主一起干了这碗🐓汤。

所谓困难，其实是自己的本事不够；很多纠结的事情，当我们做出决定并迈出第一步的时候，最困难的那部分其实就已经完成了。

线性表

概述⇢线性表是数据结构相对来说入门的数据结构，线性主要就是呈现出"线性"，算了这样说也不太明白。直接用图形表示法会更加明显，带大家理解所谓的线性。

说明⇢像上述的形式通常我们在数组当中会经常的去使用也是线性结构。

正题⇢线性表(linear list) 是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，也是必须要牢牢掌握的。

常见的顺序表
1.顺序表
2.链表
3.栈
4.队列

注意⇢包括我们常用的数组(array)以及字符串(str)也是属于顺序表的。

顺序表实现

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

顺序表分类

⑴静态顺序表:使用定长的数组进行存储。

⑵动态顺序表:使用动态开辟的数组进行存储。

⒈示例－静态顺序表

概述⇢示例代码①会使用静态顺序表来实现相关的内容并且用结构体类型的方式来进行代码的示例，里面会设计到C语言当中比较高级的语法。如果你看起来觉得一头雾水的话，建议还是再去学习下C语言吧♬

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void TestSeqList1()
{
	unsigned int i = 0;
	SL sl;
	//这里传递地址,是因为形参实际上是实参的临时拷贝。如果不传递地址的话,形参的函数出了作用域就会被销毁。所以,我们就需要用地址传递,使得它们的地址空间是一样的,这样形参就会实例话,相当于也改变了实参。
	SeqListInit(&sl);
	for (i = 0; i < PB_MAX; i++)
	{
		SeqListPushBack(&sl, i);
	}
}

int main(void)
{
	TestSeqList1();
	return 0;
}

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SeqListInit(SL* ps)
{
	//对于结构体数组初始化可以用memset() - 内存填充块进行初始化操作。
	memset(ps->a, 0, sizeof(int) * MAX_SIZE);
	ps->Size = 0;
}

void SeqListPushBack(SL* ps, int x)  //顺序表
{
	if (ps->Size >= MAX_SIZE)
	{
		printf("SeqList is Full\n");
		return;
	}
	else
	{
		ps->a[ps->Size] = x;
		ps->Size++;
		printf("%d.SeqList is ok-%p\n",x,&(ps->a[ps->Size]));
	}
}

void SeqListPushFront(SL* ps, int y) 
{

}

void SeqListPopBack(SL* ps)			
{

}

void SeqListPopFront(SL* ps)		 
{

}

3.SeqList.h

#ifndef __SEQLIST_H
#define __SEQLIST_H

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 10
#define PB_MAX   10

typedef struct
{
	int a[MAX_SIZE];
	int Size;
}SL;


extern void SeqListInit(SL* ps);			//增删查改等接口

extern void SeqListPushBack(SL* ps, int x); //顺序表
extern void SeqListPushFront(SL* ps, int y);
extern void SeqListPopBack(SL* ps);			
extern void SeqListPopFront(SL* ps);		

#endif

说明⇢静态的顺序表在实际情况下是有缺陷的。

1.它数组大小是固定死的，我们是需要根据情况对数组下标进行相对应的修改，不方便。

2.浪费空间，假设要存储10个字节。而你数组存放了1000个字节的单位，这样就会浪费内存空间。

总结⇢静态的顺序表不推荐使用!

⒉示例－动态顺序表✨

概述⇢好!接下来用动态顺序表的方式来实现。如果你对于动态存储比较模糊的话，推荐你看下博主写的这篇博客相信会对你有所帮助的。

🔗malloc链接－【C语言】动态内存开辟的使用『malloc』

🔗项目参考内容 【C语言】通讯录《动态内存版本》

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void TestSeqList1(s)
{
	unsigned int i = 0;
	SL sl;
	//这里传递地址,是因为形参实际上是实参的临时拷贝。如果不传递地址的话,形参的函数出了作用域就会被销毁。所以,我们就需要用地址传递,使得它们的地址空间是一样的,这样形参就会实例话,相当于也改变了实参。
	SeqListInit(&sl);

	for (i = 0; i < PB_MAX; i++)
	{
		SeqListPushInsert(&sl, i);//插入
	}
	printf("插入:");
	SeqListprint(&sl);		      //打印
	printf("\n");

	printf("插入->头插:");
	SeqListPushFront(&sl, 5);
	SeqListprint(&sl);		      //打印
	printf("\n");

	printf("插入->头插->尾删:");
	SeqListPopBack(&sl);
	SeqListprint(&sl);		      //打印
	printf("\n");

	printf("插入->头插->尾删->头删:");
	SeqListPopFront(&sl);
	SeqListprint(&sl);		      //打印
	printf("\n");

	printf("插入->头插->尾删->头删->尾插:");
	SeqListPushBack(&sl, 6);
	SeqListprint(&sl);		      //打印
	printf("\n");

	printf("插入->头插->尾删->头删->尾插->初始化:");
	SeqListInitClearZero(&sl);
	SeqListprint(&sl);		      //打印
	printf("\n");
}

int main(void)
{
	TestSeqList1();
	return 0;
}

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->Size = 0;
	ps->capacity = 0;
}

void SeqListCheckCape(SL* ps)			//检查空间,如果满了,进行增容。
{
	//扩容一般2倍进行,可以用relloc()进行内存填充
	if (ps->Size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDateType* tmp = (SQDateType*)realloc(ps->a, sizeof(SQDateType) * newcapacity);
		//如果tmp是空指针的话,说明扩容失败。
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1); //除了exit(0)其他参数均代表程序异常退出。
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

void SeqListPushInsert(SL* ps, int x)    //插入
{
	//扩容一般2倍进行,可以用relloc()进行内存填充
	SeqListCheckCape(ps);
	ps->a[ps->Size] = x;
	ps->Size++; 
}

void SeqListPushFront(SL* ps, int y)    //头插
{
	SeqListCheckCape(ps);
	for (int end = ps->Size - 1; end >= 0; end--)
	{
		ps->a[end + 1] = ps->a[end];
	}
	ps->a[0] = y;
	ps->Size++;
}

void SeqListPopFront(SL* ps)            //头删
{
	assert(ps->Size > 0);
	int starts = 1;
	while (starts < ps->Size)
	{
		ps->a[starts - 1] = ps->a[starts];
		starts++;
	}
	ps->Size--;
}

void SeqListPopBack(SL* ps)			   //尾删
{
	assert(ps->Size > 0);//断言,当Size大于0的时候断言失败,当Size小于等于0的时候断言成功。
	ps->Size--;
}

void SeqListPushBack(SL* ps, int z)    //尾插
{
	assert(ps->Size >= 0);
	ps->a[ps->Size++] = z;
}

void SeqListInitClearZero(SL* ps)          //初始化清0
{
	int i = 0;
	for (i = 0; i < ps->Size; i++)
	{
		ps->a[i] = 0;
	}
}

void SeqListprint(SL* ps)			   //打印
{
	for (int i = 0; i < ps->Size; i++)
	{
		printf("%d ", ps->a[i]);
	}
}

🕹说明⇢有很多小伙伴可能会在第十七行有所疑问？为什么realloc()的返回值是新的整形指针，而不能直接是 ps->a 这个是因为"relloc"可能返回null指针赋值给"ps->a"(后者将作为参数传递给"relloc"将导致原始内存块会被泄露，这是一个很不安全的做法。

3.SeqList.h

#ifndef __SEQLIST_H
#define __SEQLIST_H

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

#define PB_MAX   5

typedef int SQDateType;//增强程序的可维护性

typedef struct
{
	SQDateType* a;
	int Size;		//有效数据个数
	int capacity;	//容量
}SL;

extern void SeqListInit(SL* ps);			 //增删查改等接口初始化√
extern void SeqListCheckCape(SL* ps);		 //检查空间,如果满了,进行增容√
extern void SeqListPushInsert(SL* ps, int x);//插入√
extern void SeqListPushFront(SL* ps, int y); //头插√
extern void SeqListPopFront(SL* ps);		 //头删√
extern void SeqListPopBack(SL* ps);			 //尾删√ 
extern void SeqListPushBack(SL* ps, int z);  //尾插√
extern void SeqListInitClearZero(SL* ps);    //初始化0√
extern void SeqListprint(SL* ps);			 //打印√

#endif

运行结果↙