单链表-数据结构
- C语言
- 2024-04-06
- 1999热度
- 0评论
单链表-数据结构
代码定义单链表
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//typedef struct LNode LNode; //typedef关键字(数据类型重命名)
struct LNode{ //定义单链表节点类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节点
}LNode,*LinkList; //数据类型重命名的另一种方式,等价于typedef
//新增节点,在内存中申请一个节点所需空间,并用指针p指向这个节点
struct LNode * p=(struct LNode *) malloc(sizeof(struct LNode));
//LNode * P=(LNode *)malloc(sizeof(LNode)) //重命名后写法
要表示一个单链表时,只需声明一个头指针L,指向单链表的第一个结点,这样可以使代码的可读性更强。
LNode * L //声明一个指向单链表第一个结点的指针
LinkList L //声明一个指向单链表第一个节点的指针
在定义单链表方法时,**LNode * 返回的结果是一个结点,并且在指定子函数形参时,LinkList**指明操作的对象是一个单链表,如代码所示。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
LNode * GetElem(LinkList L,int i){
int j=1;
LNode *p=L->next;
if(i==0)
{
return L;
}
while(p!=NULL && j<i){
p=p->next;
j++;
}
return p;
}
int main()
{
return 0;
}
头插法建立单链表算法如下
- 首先,创建一个头结点并将其指向 NULL,表示初始为空链表。
- 然后,循环读取用户输入的数据,直到用户输入 9999 表示结束。
- 在循环中,创建一个新节点,并将用户输入的值赋给新节点的数据域。
- 将新节点插入到链表的头部,即将新节点的 next 指针指向原来头节点的下一个节点,并将头节点的 next指针指向新节点。
- 继续读取用户输入的数据,重复上述步骤,直到用户输入 9999。
- 最后,函数返回建立好的链表的头指针。
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x;
L=(LinkList) malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while (x!=9999){ //输入9999表示结束
s=(LNode *) malloc(sizeof(LNode)); //创建新节点
s->data=x;
s->next=L->next;
L->next=s; //将新节点插入表中,L为头指针
scanf("%d",&x);
}
return L;
}
不带头结点的单链表
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L=NULL; //空表,暂时还没有任何结点(防止脏数据)
return true;
}
//判断单链表是否为空
bool Empty(LinkList L){
if(L==NULL)
{
return true;
} else
{
return false;
}
}
int main()
{
LinkList L; //声明一个指向单链表的指针(此时并没有创建一个节点)
//初始化一个空表
InitList(L);
//...后续代码...
return 0;
}
带头结点的单链表
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType 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;
}
//判断单链表是否为空(带头节点)
bool Empty(LinkList L){
if(L->next==NULL)
{
return true;
} else
{
return false;
}
}
int main()
{
LinkList L; //声明一个指向单链表的指针(此时并没有创建一个节点)
//初始化一个空表
InitList(L);
//...后续代码...
return 0;
}
不带头节点,书写代码会更麻烦,对于第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理需要用不同的代码逻辑。头结点不存储数据,但操作起来会更方便。
单链表的插入和删除
插入:
1、按位置插入
①带头结点
②不带头结点
2、指定结点的后插操作
3、指定结点的前插操作
删除:
1、按位序删除
2、指定结点的删除
按位序插入(带头结点)
定义子函数的名称为ListInsert(&L,i,e)。在表L的第i个位置插入指定元素e。思路:找到第i-1个结点,将新结点插入其后,头结点可以看作第0个结点。
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
{
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点,头节点是第0个结点(不存储数据)
while (p!=NULL && j<i-1) //循环找到第i-1个结点
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
LNode *s=(LNode *) malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s; //将结点s链接到结点p之后
return true; //插入成功
}
读者可以画图模拟代码的执行过程,链表的长度为5,头节点加4个数据结点,插入位置尝试1、5、7,观察代码的执行过程,尝试交换语句s->next=p->next;和p->next=s;观察代码是否还能正常执行。
按位序插入(不带头结点)
定义子函数的名称为ListInsert(&L,i,e)。在表L的第i个位置插入指定元素e。思路:找到第i-1个结点,将新结点插入其后,由于不存在第0个结点(头结点),因此在i=1时需要特殊处理。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
{
return false;
}
if(i==1)
{
LNode *s=(LNode *) malloc(sizeof(LNode));
s->data=e;
s->next=L;
L=s;
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前p指向的是第几个结点
p=L; //p指向第1个结点(不是头结点)
while (p!=NULL && j<i-1) //循环找到第i-1个结点
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
LNode *s=(LNode *) malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s; //将结点s链接到结点p之后
return true; //插入成功
}
int main()
{
return 0;
}
注意:p = L和 p->next = L是不等价的。
- p = L 将指针 p 指向了链表的头节点 L,它只是将 p
指向了
L 所指向的内存地址,而没有改变原链表结构。 - p->next = L 则是将 p 所指向的节点的指针域 next 指向了链表的头节点 L,这意味着它改变了链表结构,将 p 所指向的节点与头节点L 相连接,使得 L 成为了 p 所指向的节点的下一个节点。
在具体的插入操作中,p = L 用于将 p 指向链表中的某个位置,以便于遍历链表。而 p->next = L 用于将新节点插入到 p 所指向的节点的后面,以完成插入操作。这两个语句的作用不同,因此不是等价的。
提供一段测试代码,供读者调试,观察指针的变化过程。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
int main()
{
LNode *p;
LNode *c;
LNode *b;
b=(LNode *)malloc(sizeof(LNode));
p->next=b;
c=p;
return 0;
}
结果如图所示
指定结点的后插操作
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//后插操作:在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
if(p==NULL)
{
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL) //内存分配失败
{
return false;
}
s->data=e; //用结点s保存数据元素e
s->next=p->next;
p->next=s; //将结点s链接到结点p之后
return true;
}
int main()
{
return 0;
}
完成指定节点后插操作的子函数后,可以将此模块进行封装,在其他程序内调用,简化代码。
指定结点的前插操作
在之前的实验中,都是使用的后插法,但是对于前插操作我们并不熟悉。
方法有二,其一是插入一个头结点,假如需要在 p 前插入结点,通过头结点,找到 p 的前驱结点q,再对结点q使用后插法,变相完成了前插操作。方法二是先后插,再交换节点中的内容,也是变相完成了前插操作。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//前插操作:在p结点之前插入元素e
bool InsertPriorNode(LNode *p,ElemType e){
if(p==NULL)
{
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL) //内存分配失败
{
return false;
}
s->next=p->next;
p->next=s; //将结点s链接到结点p之后
s->data=p->data; //将结点p中的元素复制到结点s中
p->data=e; //p中元素覆盖为e
return true;
}
int main()
{
return 0;
}
按位序删除(带头节点)
定义子函数的名称为ListDDelete(&L,i,e)。删除表 L 中第i个位置的元素,并用e返回删除元素的值,思路:找到第i-1个结点,将其指针指向第 i+1 个结点,并释放第 i 个结点,头结点可以看做第0个节点。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i<1)
{
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=L; //L指向头结点,头节点是第0个节点,不存储数据
while (p!=NULL && j<i-1)
{
p=p->next;
j++;
}
if(p==NULL) //i值不合法
{
return false;
}
if(p->next==NULL) //第i-1个结点之后已无其他结点
{
return false;
}
LNode *q=p->next; //令q指向被删除结点
e=q->data; //同e返回元素的值
p->next=q->next; //将*q结点从链中"断开"
free(q); //释放节点删除空间
return true; //删除成功
}
int main()
{
return 0;
}
读者可以思考,果是不带头结点,删除第一个元素时,是否需要特殊处理?下面附带代码供读者参考。
bool ListDelete(LinkList& L, int i, ElemType& e) {
if (i < 1) {
return false;
}
if (i == 1) { // 删除第一个节点
if (L == NULL || L->next == NULL) { // 链表为空或只有一个节点
return false;
}
LNode* q = L->next; // 待删除的节点
e = q->data; // 保存数据
L->next = q->next; // 更新头节点的下一个指针
free(q); // 释放节点
return true; // 删除成功
}
// 删除非第一个节点的代码
LNode* p = L; // 指针p指向当前扫描到的结点
int j = 1; // 当前p指向的是第几个结点
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || p->next == NULL) {
return false; // 位置无效
}
LNode* q = p->next; // 待删除的节点
e = q->data; // 保存数据
p->next = q->next; // 将*q结点从链中"断开"
free(q); // 释放节点删除空间
return true; // 删除成功
}
指定结点的删除
需要删除某个结点,需要修改其前驱节点的next指针。实现的方法跟上面的前插法类似,插入头指针循环查找删除结点的前驱结点的next指针,或者是偷天换日,类似前插法的第二个方法。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
//删除指定结点p
bool DeleteNode(LNode *p){
if(p=NULL)
{
return false;
}
LNode *q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
return true;
}
int main()
{
return 0;
}
单链表的局限性:无法逆向检索。如果p是最后一个结点,上述代码会无法执行。每次寻找能从表头开始寻找p的前驱节点,时间复杂度为O(n)。
单链表的查找(按位查找、按值查找)
在上面的单链表的插入和删除代码中,已经有查找的操作,但是查找的是第i-1个节点,所以需要对代码进行修改。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode, *LinkList;
LNode * GetElem(LinkList L,int i){
if(i<0)
{
return NULL;
}
int j=0;
LNode *p;
p=L;
while(p!=NULL && j<i){
p=p->next;
j++;
}
return p;
}
int main()
{
return 0;
}
代码需要考虑边界情况
1、查找 i=0,此时返回头结点地址。
2、查找 i=6 (超过链表长度),假设链表长度为 4,会出现p->next=NULL的情况,在循环结束时,p 会指向链表的末尾节点的下一个位置,也就是 NULL。因为在循环中 j 会递增到 4,而 p 会指向第 4 个节点的下一个位置(即空地址)。因此,返回的 p 将是 NULL。附带实验代码供读者参考。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
} LNode, *LinkList;
// 创建一个只有头结点的链表
LinkList createList() {
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 初始时链表为空
return L;
}
// 在链表头部插入新节点
void insertNode(LinkList L, ElemType data) {
LNode* newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = data;
newNode->next = L->next;
L->next = newNode;
}
// 获取链表中的第i个节点
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
int j = 0;
LNode* p;
p = L->next; // 头结点不存储数据,从第一个节点开始
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
int main() {
// 创建链表
LinkList L = createList();
// 向链表中插入一些数据
insertNode(L, 10);
insertNode(L, 20);
insertNode(L, 30);
// 测试 GetElem 函数
for (int i = 0; i <= 5; i++) {
LNode* node = GetElem(L, i);
if (node == NULL) {
printf("Position %d: NULL\n", i);
} else {
printf("Position %d: %d\n", i, node->data);
}
}
// 释放链表中的内存空间
LNode* temp;
while (L->next != NULL) {
temp = L->next;
L->next = temp->next;
free(temp);
}
free(L); // 释放头结点内存
return 0;
}
按值查找
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
} LNode, *LinkList;
//按值查找,找到数据域等于e的结点
LNode * LocateElem(LinkList L, ElemType e){
LNode *p=L->next;
//从第一个结点开始查找数据域为e的结点
while (p!=NULL && p->data!=e)
{
p=p->next;
return p; //找到后返回该节点指针,否则返回NULL
}
}
int main() {
return 0;
}
平均时间复杂度为O(n)
求表的长度
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
} LNode, *LinkList;
//求表的长度
int Length(LinkList L){
int len=0;
LNode *p=L;
while (p->next!=NULL)
{
p=p->next;
len++;
}
return len;
}
int main() {
return 0;
}