数据结构

2024-07-11 23:30| 来源: 网络整理| 查看: 265

前面我们学到线性表的顺序存储结构（顺序表），发现它有着明显的缺点：插入和删除元素时需要频繁的移动元素，运算效率低。必须按事先估计的最大元素个数申请连续的存储空间。存储空间估计大了，造成浪费空间；估计小了，容易产生溢出，空间难以扩大。

采用链式存储结构的线性表（链表）可以克服以上的不足。

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(存放的数据元素)+指针(指示下一个元素存储位置，单、双链表的最后一个节点除外，它们存储的是一个空指针NULL)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

节点的结构如下图所示：在这里插入图片描述对节点的定义如下：

typedef struct LNode { int data;//节点的数据域 struct LNode *next;//节点的指针域 }LNode,*LinkList;

这里我们用typedef进行类型重定义，把struct LNode定义一个新名字LNode，把struct LNode定义成另一个新名字* LinkLIst。这里注意：LNode和*LinkLIst是一样的。但在使用上LNode和LinkList是不同的。

在这里插入图片描述注：我们假设节点里存放的是int型数据。

单链表由多个节点依次连接而成，结构如下图：在这里插入图片描述

最开始的那个节点是头节点，头节点的数据域是不存放数据的，指针域指向链表的第一个节点。在单链表的定义中，带有头节点的称为带头节点单链表，不带头节点的称为不带头节点单链表。我们这次介绍的就是带头节点单链表。

单链表的基本操作： 1.链表的初始化 2.创建单链表 2.1.用头插法创建单链表 2.2.用尾插法创建单链表 3.打印单链表 4.插入元素 4.1.在指定位置插入元素 4.2.在指定节点后面插入元素（后插） 4.3.在指定节点前面插入元素（前插） 5.按位查找元素 6.按值查找元素 7.求表长 8.删除元素 9.判断是不是空表 10.销毁单链表 **全部代码：**

1.链表的初始化

我们先用malloc函数分配一个头节点，让头节点的指针域指向空指针，对产生的头节点的情况要进行判断。

#define _CRT_SECURE_NO_WARNINGS 1 #include #include typedef struct LNode { int data;//数据域 struct LNode *next;//指针域 }LNode,*LinkList; bool InitList(LinkList &L)//初始化单链表 { L = (LNode*)malloc(sizeof(LNode));//分配一个头节点 if (L == NULL) return false;//内存不足，分配失败 L->next = NULL;//头节点之后还没有节点 return true; } 2.创建单链表

链表的建立有两种方式，一种是头插法，一种是尾插法。由于单链表的头插和尾插性质，有时候常用来解决链表的逆置问题。

2.1.用头插法创建单链表

头插法：把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反,输出时为倒序。

用通俗的语言来说，有一家奶茶店开业了，人们去买奶茶，A第一个排队，而后来的B插到A前面排队，后来的C插到B前面排队，这样排队下去A到了最后一位。节点的插入也是这样子。假设往里面放入元素1 2 3 4 5，有趣的是存放进去的元素则是5 4 3 2 1，刚好是相反的，这种特性可以用于链表的逆置。

下图是节点s插入到单链表中：

在这里插入图片描述操作步骤：创建指针p指向头节点，用malloc函数申请空间给节点s，接下来让节点s的指针域等于头节点的指针域，头节点的指针域指向节点s。把这段代码放到循环里面，进行多次头插操作。

void Inita(LinkList &L)//初始化单链表(使用的是头插) { printf("请输入你要创建的单链表的长度："); int a; scanf("%d", &a); printf("请输入%d个数:",a); for (int i = 1; i data);//输入值放入插入节点的数据域 s->next = p->next;//改变插入节点的指针域 p->next = s;//使头节点的指针域指向插入的节点 } } 2.2.用尾插法创建单链表

尾插法就是在链表的尾部依次插入节点，和你去买奶茶依次排队是一个情况的，一个个排队。假设输入元素1 2 3 4 5，那么存储进去的元素也是 1 2 3 4 5。

操作步骤：先找到链表的最后一个节点，然后在最后一个节点后面插入节点。接下来的操作和头插差不多了。

void Initb(LinkList &L) { LNode *p = L; while (p->next)//用循环让p指向尾节点 p = p->next; int a; printf("请输入你要创建的单链表的长度:"); scanf("%d", &a); printf("请输入%d个数：", a); for (int i = 1; i next = s;//此时的p指向尾节点，让p指向s scanf("%d", &s->data);//输入值放入s节点的数据域 s->next = NULL;//让s节点的指针指向空指针 p = p->next;//让p指针指向此时的尾指针（s节点） } } 3.打印单链表

打印单链表就只能一个个从前往后打印。

void PrintList(LinkList &L)//打印单链表 { LNode *p=L;//创建一个p指针指向头节点 printf("表中的元素为："); while (p->next!=NULL)//判断下一个节点是不是空指针，也可以简写为p->next { p = p->next;//p指向下一个节点 printf("%d ", p->data); } printf("\n"); } 4.插入元素 4.1.在指定位置插入元素

在指定位置插入元素，我们只需要找到要插入元素位置的前一个节点就可以了，然后修改节点指针域即可。

bool ListInsert(LinkList &L)//插入操作，把一个值插入要求的位置 { int i,e; printf("请输入你要插入的元素和要插入的位置："); scanf("%d %d",&e, &i); if (i

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻