开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021-08-05 -> 正文阅读

[数据结构与算法]2021-08-05

本文你将了解数据结构中线性表的顺序存储与链式存储的基本操作.

文章目录

线性表

线性表

零个或多个元素的有限序列.

顺序存储

用一段地址连续的存储单元,依次存储线性表的数据元素

本代码用到的头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<Windows.h>
#define MAXSIZE 20 //最大存储空间

线性表顺序存储的结构

typedef int ElemType;
typedef struct SqList
{
	ElemType data[MAXSIZE]; //存储数据元素,最大位MAXSIZE
	int length;             //线性表当前长度             
}SqList;

线性表顺序存储的初始化

//线性表的初始化
void ListInit(SqList *sl)
{
	sl->length = 0;
}

获取任意元素

//从线性表中获取第i个元素
ElemType getElem(SqList *sl, int i)
{
	//判断位置是否合理或表是否为空
	if (sl->length == 0 || i < 1 || i > sl->length)
	{
		printf("不存在该元素\n");
		return INT_MIN; //当不存在时返回最小元素
	}
	return sl->data[i - 1];
}

线性表顺序存储的插入

//插入元素
void ListInseart(SqList *sl, int i)
{
	ElemType e = 0;
	if (sl->length == MAXSIZE) //线性表长度已满
	{
		printf("线性表长度已满\n");
		return;
	}
	if (i < 1 || i > sl->length + 1)//插入位置不合理
	{
		printf("插入位置不合理\n");
		return;
	}
	printf("请输入: \n");
	scanf("%d", &e);
	for (int j = sl->length - 1; j >= i - 1; j--)
	{
		sl->data[j + 1] = sl->data[j];
	}
	sl->data[i - 1] = e;
	sl->length++;      //插入成功,长度加1
}

线性表顺序存储的遍历

//删除元素
void ListDelete(SqList *sl, int i)
{
	if (sl->length == 0)//表为空
	{
		printf("表为空\n");
		return;
	}
	if (i < 1 || i > sl->length)//删除位置不合理
	{
		printf("删除位置不合理\n");
		return;
	}
	printf("删除的元素为: %d\n", sl->data[i - 1]);
	for (int j = i; j < sl->length; j++)
	{
		sl->data[j - 1] = sl->data[j];
	}
	sl->length--;//删除成功,长度减1
}

线性表顺序存储的测试

int main()
{
	SqList sl;
	ListInit(&sl);
	for (int i = 0; i < 10; i++)
	{
		sl.data[i] = i + 10;
		sl.length++;
	}
	ListPrint(&sl);

	printf("%d\n", getElem(&sl, 3));

	ListInseart(&sl, 0);
	ListInseart(&sl, sl.length+2);
	ListInseart(&sl, 0);
	ListDelete(&sl, sl.length+1);

	ListInseart(&sl, 3);
	ListPrint(&sl);
	ListDelete(&sl, 3);
	ListPrint(&sl);
	

	system("pause");
	return 0;
}

链式存储

本代码用到的头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<Windows.h>

线性表的单链表存储结构

/*线性表的单链表存储结构*/
typedef struct Node
{
	ElemType data;        //数据域
	struct Node * next;   //指针域
}Node;
typedef Node * LinkList;

链表获取元素

//获取元素
ElemType getElem(LinkList L, int i)
{
	LinkList p = L->next;
	int j = 1;

	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		printf("位置不合理\n");
		return INT_MIN;
	}
	return p->data;
}

链表插入元素

//链表插入元素
void ListInseart(LinkList *L, int i)
{
	LinkList p, s;
	p = *L;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		printf("插入位置不合理\n");
		return;
	}
	s = (Node *)(malloc(sizeof(Node)));
	printf("请输入: \n");
	scanf("%d", &s->data);

	//头插法
	s->next = p->next;
	p->next = s;
}

链表删除元素

//链表删除元素
void ListDelete(LinkList *L, int i)
{
	LinkList p, q;
	p = *L;
	int j = 1;
	while (p->next && j < i)
	{
		p = p->next;
		j++;
	}

	if (!(p->next) || j > i)
	{
		printf("删除位置不合理\n");
		return;
	}
	//删除
	q = p->next;
	p->next = q->next;

	printf("删除的元素为 %d\n", q->data);
	free(q);
}

链表的整表创建(头插法)

//单链表的整表创建(头插法)
void CreateListHead(LinkList *L, int n)
{
	*L = (Node *)malloc(sizeof(Node));
	(*L)->next = NULL;

	for (int i = 0; i < n; i++)
	{
		LinkList p = (Node *)malloc(sizeof(Node));
		p->data = rand() % 100 + 1;
		//头插法
		p->next = (*L)->next;
		(*L)->next = p;
	}
}

链表的整表创建(尾插法)

//单链表的整表创建(尾插法)
void CreateListRear(LinkList *L, int n)
{
	*L = (Node *)malloc(sizeof(Node));
	(*L)->next = NULL;
	LinkList r = *L;
	for (int i = 0; i < n; i++)
	{
		LinkList p = (Node *)malloc(sizeof(Node));
		p->data = rand() % 100 + 1;
		//头插法
		r->next = p;
		r = p;
	}
	r->next = NULL;
}

链表的整表删除

//单链表的整表删除
void ClearList(LinkList *L)
{
	LinkList p, q;
	p = (*L)->next;
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
}

链表的遍历

//单链表遍历
void ListPrint(LinkList L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

链表的测试

int main()
{
	srand((unsigned int)time(NULL)); // 随机数种子
	LinkList L ;

	CreateListHead(&L, 10);
	ListPrint(L);
	CreateListRear(&L, 10);
	ListPrint(L);
	ListInseart(&L, 3);
	ListPrint(L);
	ListDelete(&L, 3);
	ListPrint(L);
	printf("%d\n", getElem(L, 3));

	system("pause");
	return 0;
}

顺序存储与链式存储的优缺点总结

在这里插入图片描述

静态链表

静态链表就是为了解决线性表顺序存储插入删除时要移动元素的缺点.

头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>

typedef int ElemType;
#define MAXSIZE 1000

静态链表的存储结构

/*线性表的静态链表存储结构*/
typedef struct
{
	ElemType data;
	int cur;      //游标
}Component, StaticLinkList[MAXSIZE];

静态链表的初始化

//静态链表的初始化
void InitList(StaticLinkList space)
{
	for (int i = 0; i < MAXSIZE - 1; i++)
	{
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0; //目前静态链表为空,存储元素的下标为0
}

返回静态链表第一个空闲下标

/*若备用链表非空,返回第一个空闲的下标*/
int Malloc_SLL(StaticLinkList space)
{
	int i = space[0].cur;
	if (space[0].cur)
	{
		space[0].cur = space[i].cur; //下一个空闲的下标
	}
	return i;
}

静态链表的插入

/*在数据第i个元素之前插入新的元素*/
void ListInsert(StaticLinkList L, int i)
{
	ElemType e;
	printf("请输入: \n");
	scanf("%d", &e);
	int k = MAXSIZE - 1;
	if (i < 1 || i > MAXSIZE + 1)
	{
		printf("插入位置有误\n");
		return;
	}
	//找到第i-1元素的下标k
	for (int j = 1; j <= i - 1; j++)
	{
		k = L[k].cur;
	}
	int j = Malloc_SLL(L);//空闲下标
	if (j)
	{
		L[j].data = e;
		//相当于链表中的头插法
		L[j].cur = L[k].cur;
		L[k].cur = j;
		printf("插入成功\n");
	}
}

释放元素

void Free_SLL(StaticLinkList space, int i)
{
	//相当于把要删除的元素插入(头插法)到备用链表里
	space[i].cur = space[0].cur;
	space[0].cur = i;
}

静态链表的删除

/*删除第i个数据元素*/
void ListDelete(StaticLinkList L, int i)
{
	if (i < 1 || i > MAXSIZE)
	{
		printf("删除位置有误\n");
		return;
	}
	int k = MAXSIZE - 1;
	for (int j = 1; j <= i - 1; j++)
	{
		k = L[k].cur;
	}
	int j = L[k].cur;//要删除元素的下标
	L[k].cur = L[j].cur;
	Free_SLL(L, j);
}

静态链表的元素个数

/*返回静态连表中的元素个数*/
int ListLength(StaticLinkList L)
{
	int k = L[MAXSIZE - 1].cur;
	int j = 0;
	while (k)
	{
		k = L[k].cur;
		j++;
	}
	return j;
}

静态链表的遍历

/*静态链表的遍历*/
void ListPrint(StaticLinkList L)
{
	int k = L[MAXSIZE - 1].cur;

	while (k)
	{
		printf("%d ", L[k].data);
		k = L[k].cur;
	}
	printf("\n");
}

静态链表的优缺点

在这里插入图片描述

双向循环链表

头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>

typedef int ElemType;

线性表的双向存储结构

/*线性表的双向存储结构*/
typedef struct DulNode
{
	ElemType data;
	struct DulNode * prior; //前驱指针域
	struct DulNode * next;  //后继指针域
}DulNode, *DulLinkList;

建立

//建立
void DulListCreate(DulLinkList * list)
{
	*list = (DulLinkList)malloc(sizeof(DulNode));
	(*list)->prior = *list;
	(*list)->next = *list;
	for (int i = 0; i < 8; i++)
	{
		DulLinkList s = (DulLinkList)malloc(sizeof(DulNode));
		s->data = i + i;

		s->prior = *list;
		s->next = (*list)->next;
		(*list)->next->prior = s;
		(*list)->next = s;
	}
}

插入

//插入
void DulListInsert(DulLinkList * list, int i)
{
	if (i < 1 || i > getLength(*list)+1)
	{
		printf("插入位置不合理\n");
		return;
	}
	DulLinkList p = (*list);
	int j = 1;
	while (p->next != *list && j <= i - 1)
	{
		p = p->next;
		j++;
	}
	if (p == *list || j > i)
	{
		printf("插入位置不合理\n");
		return;
	}

	DulLinkList s = (DulLinkList)malloc(sizeof(DulNode));
	printf("请输入: \n");
	scanf("%d", &s->data);
	
	//插入
	s->prior = p;
	s->next = p->next;
	p->next->prior = s;
	p->next = s;

}

删除

//删除
void DulListDelete(DulLinkList * list, int i)
{
	if (i < 1 || i > getLength(*list))
	{
		printf("删除位置不合理\n");
		return;
	}
	DulLinkList p = (*list);
	int j = 1;
	while (p->next != *list && j <= i)
	{
		p = p->next;
		j++;
	}
	if (p == *list)
	{
		printf("链表位置过短\n");
		return;
	}

	//删除
	p->prior->next = p->next;
	p->next->prior = p->prior;

}

遍历

/*遍历*/
void DulListPrint(DulLinkList list)
{
	DulLinkList p = list->next;
	while (p != list)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}