首页 > 其他分享 >数据结构之线性表（单链表的实现）

数据结构之线性表（单链表的实现）

时间：2024-08-10 17:55:27浏览次数：13  
标签：单链 return 线性表 temp int NULL next LinkList 数据结构

目录

一、单链表的原理

二、单链表的实现

1.单链表的定义

2.单链表的初始化

3.清空单链表

4.单链表是否为空

5.单链表的长度

6.获取指定位置 i 的元素

7.获取指定元素 e 的位置  

8.向链表中插入指定位置的元素

9.向链表中删除指定位置的元素

10.遍历链表中的元素

三、打印测试功能

1.测试

2.结果输出

3.总代码

一、单链表的原理

        本章节紧跟上一篇文章《顺序表的实现》来继续讲述线性表的一种：单链表。

        前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

         要解决这个问题，我们就得考虑一下导致这个问题的原因。为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2，3，…，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

        我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它;在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到，而这就是单链表的特点，如下图所示。

         而链表的结构则如下图所示，第一个节点的指针由头节点所指，第二个节点的指针由第一个节点所指，以此类推。

二、单链表的实现

1.单链表的定义

        定义一些功能常量和单链表的结构。

        这里需要注意的是，我给链表起别名的是一个指针，后面我们在实现链表功能的时候，我们传递函数参数的时候要传递的是一个双指针（LinkList* L）。 这是因为链表的结构使然，因为链表存储的是其他链表的指针，它是一个地址，后面我们在进行链表的增加和删除的时候，会经常涉及到指针的变化。

        如果函数的参数是本身一级指针，那么在函数内部对指针的修改将不会反映到函数外部，因为函数接收到的是指针的一个副本。使用指针的指针作为参数，则可以确保在函数内部对指针的修改能够反映到原始的指针上。

typedef  struct  Node*  LinkList;

#include <iostream>

#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node;

typedef struct Node* LinkList;
2.单链表的初始化

        链表的初始化主要是为头节点分配内存空间，使它的data 和 next 都指向为 NULL，方便我们后续的操作。

Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(Node));
	if (*L == NULL) return ERROR;
	(*L)->data = 0;
	(*L)->next = NULL;
	return OK;
}
3.清空单链表

        对链表进行清空操作，因为是用 malloc 进行分配的空间，对堆中的空间进行释放操作。

Status ClearList(LinkList* L)
{
	LinkList p, q;

	p = (*L)->next;
	while (p != NULL) 
	{	
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return OK;
}
4.单链表是否为空

        判断头节点指向的元素是否为空。即 next 是否为 NULL。

Status isListEmpty(LinkList L)
{
	if (L->next  == NULL) return TRUE;
	return FALSE;
}
5.单链表的长度

        求链表的长度，定义一个变量，然后用while循环遍历链表。

int ListLength(LinkList L)
{
	int num{ 0 };
	LinkList temp = L->next;
	while (temp != NULL)
	{
		temp = temp->next;
		num++;
	}
	return num;
}
6.获取指定位置 i 的元素

        定义一个变量，进行while操作，判断是否与指定位置 i 相同，获取其节点值。

Status GetElem(LinkList L, int i, ElemType* e)
{
	int num{ 1 };
	LinkList temp = L->next;
	while (temp != NULL && num < i)
	{
		temp = temp->next;
		num++;
	}	
	if (temp == NULL || num > i) return ERROR;
	*e = temp->data;
}
7.获取指定元素 e 的位置  

        和上述功能类似，返回值为 int 位置。

int LocateElem(LinkList L, ElemType* e)
{
	int num{ 0 };
	LinkList temp = L->next;
	while (temp != NULL)
	{
		num++;
		if (temp->data = *e)
		{
			return num;
		}
		temp = temp->next;
	}
	return 0;
}
8.向链表中插入指定位置的元素

          此功能为链表的难点所在，需要根据图像理解实现，如下图所示。 

      

Status LinkInsert(LinkList* L, int i, ElemType e)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;

	while (p != NULL && j < i)
	{
		p = p->next;
		++j;
	}	
	if (!p || j > i) return ERROR;

	s = (LinkList)malloc(sizeof(Node));
	if (s == NULL) return ERROR;
	s->data = e;
	
	s->next = p->next;
	p->next = s;
	
	return OK;

}
9.向链表中删除指定位置的元素

        和上功能类似，如图所示。

Status LinkDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, s;
	j = 1;
	p = (*L);
 	while (p != NULL && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i) return ERROR;

	s = p->next;
	p->next = s->next;
	*e = s->data;
	free(s);
	return OK;
}
10.遍历链表中的元素

        功能比较简单，通过不断遍历打印其节点的data值。

Status visit(ElemType e)
{
	printf("%d->", e);
	return OK;
}
Status ListTraverse(LinkList L)
{
	LinkList p = L->next;
	while (p != NULL)
	{
		visit(p->data);
		p = p->next;
	} 
	printf("\n");
	return OK;
}

三、打印测试功能

1.测试

        测试主要为测试以上的功能是否可以实现。

int TestSingleList()
{
	LinkList L;
	ElemType e;
	Status ret;
	int j, k;
	// 初始化
	ret = InitList(&L);
	printf("初始化长度：%d\n", ListLength(L));

	for(j = 1; j <= 5; j++)
	{
		ret = LinkInsert(&L, 1, j);
	}
	printf("插入5个元素后：");
	ListTraverse(L);
	ret = isListEmpty(L);
	printf("是否为空，%d\n", ret);
	ret = ClearList(&L);
	printf("清空后的长度：%d\n", ListLength(L));
	printf("是否为空，%d\n", ret);
	for (j = 1; j <= 10; j++)
	{
		ret = LinkInsert(&L, j, j);
	}
	printf("插入10个元素后：");
	ListTraverse(L);

	LinkInsert(&L, 3, 100);
	printf("在第2个节点后面增加元素100：");
	ListTraverse(L);

	LinkDelete(&L, 2, &e);
	printf("删除第二个节点,节点元素为%d :", e);
	ListTraverse(L);

	ClearList(&L);

	return 0;
}
2.结果输出

           结果输出如图所示：

3.总代码

        总代码如下：



#include <iostream>

#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node;

typedef struct Node* LinkList;

Status visit(ElemType e)
{
	printf("%d->", e);
	return OK;
}

Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(Node));
	if (*L == NULL) return ERROR;
	(*L)->data = 0;
	(*L)->next = NULL;
	return OK;
}

Status ClearList(LinkList* L)
{
	LinkList p, q;

	p = (*L)->next;
	while (p != NULL) 
	{	
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;
	return OK;
}

Status isListEmpty(LinkList L)
{
	if (L->next  == NULL) return TRUE;
	return FALSE;
}


int ListLength(LinkList L)
{
	int num{ 0 };
	LinkList temp = L->next;
	while (temp != NULL)
	{
		temp = temp->next;
		num++;
	}
	return num;
}

Status GetElem(LinkList L, int i, ElemType* e)
{
	int num{ 1 };
	LinkList temp = L->next;
	while (temp != NULL && num < i)
	{
		temp = temp->next;
		num++;
	}	
	if (temp == NULL || num > i) return ERROR;
	*e = temp->data;
}

int LocateElem(LinkList L, ElemType* e)
{
	int num{ 0 };
	LinkList temp = L->next;
	while (temp != NULL)
	{
		num++;
		if (temp->data = *e)
		{
			return num;
		}
		temp = temp->next;
	}
	return 0;
}

Status LinkInsert(LinkList* L, int i, ElemType e)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;

	while (p != NULL && j < i)
	{
		p = p->next;
		++j;
	}	
	if (!p || j > i) return ERROR;

	s = (LinkList)malloc(sizeof(Node));
	if (s == NULL) return ERROR;
	s->data = e;
	
	s->next = p->next;
	p->next = s;
	
	return OK;

}

Status LinkDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, s;
	j = 1;
	p = (*L);
 	while (p != NULL && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i) return ERROR;

	s = p->next;
	p->next = s->next;
	*e = s->data;
	free(s);
	return OK;
}

Status ListTraverse(LinkList L)
{
	LinkList p = L->next;
	while (p != NULL)
	{
		visit(p->data);
		p = p->next;
	} 
	printf("\n");
	return OK;
}

Status CreateListHead(LinkList* L,int n)
{
	LinkList p;
	srand((unsigned)time(0));
	*L = (LinkList)malloc(sizeof(Node));
	if (*L == NULL) return ERROR;
	(*L)->next = NULL;
	for (int i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		if (p == NULL) return ERROR;
		p->data = rand() % 100 + 1;
		p->next = (*L)->next;
		(*L)->next = p;
	}
	return OK;
}

Status CreateListTail(LinkList* L,int n)
{
	LinkList p, r;
	srand((unsigned)time(0));
	*L = (LinkList)malloc(sizeof(Node));
	if (*L == NULL) return ERROR;
	(*L)->next = NULL;
	r = (*L);
	for (int i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		if (p == NULL) return ERROR;
		p->data = rand() % 100 + 1;
		r->next = p;
		r = p;
	}
	return OK;
}







int TestSingleList()
{
	LinkList L;
	ElemType e;
	Status ret;
	int j, k;
	// 初始化
	ret = InitList(&L);
	printf("初始化长度：%d\n", ListLength(L));

	for(j = 1; j <= 5; j++)
	{
		ret = LinkInsert(&L, 1, j);
	}
	printf("插入5个元素后：");
	ListTraverse(L);
	ret = isListEmpty(L);
	printf("是否为空，%d\n", ret);
	ret = ClearList(&L);
	printf("清空后的长度：%d\n", ListLength(L));
	printf("是否为空，%d\n", ret);
	for (j = 1; j <= 10; j++)
	{
		ret = LinkInsert(&L, j, j);
	}
	printf("插入10个元素后：");
	ListTraverse(L);

	LinkInsert(&L, 3, 100);
	printf("在第2个节点后面增加元素100：");
	ListTraverse(L);

	LinkDelete(&L, 2, &e);
	printf("删除第二个节点,节点元素为%d :", e);
	ListTraverse(L);

	ClearList(&L);

	return 0;
}

int main()
{
	return TestSingleList();
}

标签：单链,return,线性表,temp,int,NULL,next,LinkList,数据结构
From： https://blog.csdn.net/m0_62681656/article/details/141092751

相关文章

  • 线性表——双链表
    在Java中，双链表（DoublyLinkedList）是一种常见的数据结构，它允许从两端进行元素的插入和删除操作。与单链表相比，双链表的每个节点除了存储数据本身外，还包含两个指针：一个指向前一个节点（prev），另一个指向后一个节点（next）。这使得双链表在遍历、插入和删除操作上更加灵活。双链表提供......
  • 数据结构：顺序二叉树（堆）
    目录前言一、堆的实现 1.1头文件1.2堆的初始化及销毁1.3 堆的插入1.4堆的删除1.5取堆顶数据和判空前言   前面我们讲了二叉树有顺序结构和链式结构，今天就来讲一下顺序结构  普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而......
  • 线性表
    目录1.顺序表1.1数组的插入删除操作1.2修改为last版本1.3顺序表的相关操作1.4顺序表总结：2.链表2.1单向链表2.1.1分类1）有头单向链表2）无头单向链表2.1.2操作函数1）创建一个空的（有头）单向链表2）向post位置插入一个数据3）删除指定位置的数据4）单向链表的转置2.2单向循......
  • 【数据结构与算法】输出二叉树中从每个叶子结点到根结点的路径 C++实现（二叉树+栈+深度
    二叉树叶子节点到根节点的路径题目描述给定一棵二叉树的后序遍历序列post[s1..t1]和中序遍历序列in[s2..t2]，设计一个算法，输出二叉树中从每个叶子节点到根节点的路径。请使用栈的数据结构解决。输入格式输入包括两行：第一行为后序遍历序列post[s1..t1]。第二行为中序......
  • 【数据结构】【模板】哈夫曼树
    哈夫曼树定义带权路径长度：结点的权值乘以结点到跟的距离。树上所有结点带权路径长度之和最小的二叉树称为哈夫曼树。性质哈夫曼是满二叉树。来自维基百科：原序列构成哈夫曼树的所有叶子结点。离根结点越近，点权越大。非叶子结点的点权之和就是所有叶子结点的带权路径之和......
  • 问题 E: 数据结构基础5-车厢调度
    题目描述有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。......
  • 单链表的增删查改
    头文件#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefstructMyStruct{   intdata;   structMyStruct*next;}SL;voidlistprint(SL**phead);//打印链表voidlistpushback(SL**phead,intx);/......
  • 模板 - 数据结构
    链表定义structPeter{ intval; intnxt,pre;}node[M];intidx=0;初始化inlinevoidInit()//head:0;tail:n+1{ node[0]={0,n+1,0}; node[n+1]={0,n+1,0}; return;}在p后插入valinlinevoidinsert(intp,intval){ node[++idx]={val,node[p].nxt,p}; ......
  • 【数据结构】关于栈你必须知道的内部原理！！！
    前言：......
  • redis数据结构
    redis数据类型 stringlisthashsetzsetHyperLogLogGEOBloomFilter（布隆过滤器）HyperLogLog基本概念：Redis在2.8.9版本添加了HyperLogLog结构。RedisHyperLogLog是用来做基数统计的算法，所谓基数，也就是不重复的元素。优点在输入元素的数量或者体积非常......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99