【数据结构】链表—C/C++实现

​

前言

什么是链表？

线性表的链式存储结构称为链表（Linked List）。链表是一种常见的线性数据结构，用于组织和存储一系列元素，这些元素以节点（Node）的形式连接在一起。每个节点包括两个主要部分：用于存储数据的数据域（Data Field）和指向节点的指针域（Next Pointer）。链表可以有不同的变种，包括单链表、双链表和循环链表等。

双链表和单链表的优缺点

---

1. 单链表

1.1 定义

代码语言：javascript复制

typedef struct LNode//单链表定义
{
    int data;
    struct LNode *next;
}LNode;

1.2 常用操作

1.2.1 创建

尾插法创建：(额...头插和尾插会一个就行，因为尾插法创建的顺序和输入数组一样所以习惯了）

代码语言：javascript复制

void CreateListB(LNode **L,int a[],int n) //尾插法创建单链表
{
    LNode *r,*s;
    *L=(LNode *)malloc(sizeof(LNode));
    r=*L;
    for(int i=0;i<n;i  ){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}

1.2.2 输出

代码语言：javascript复制

void DispList(LNode *L) //输出单链表
{
    LNode *p=L;//p指向头节点
    while (p!=NULL)
    {
        printf("%d ",p->next->data);
        p=p->next;
    }
    printf("n");
}

1.2.3 插入

代码语言：javascript复制

void InsertList(LNode **L,int i,int e)//位置i插入元素e
{
    LNode *p,*s,*q;
    p=*L;//p指向头结点

    int j=0;
    while (p!=NULL && j<i-1)//p定位到第i-1节点
    {
        p=p->next;
        j  ;
    }
    s=(LNode *)malloc(sizeof(LNode));
    s->data=e;

    q=p->next;
    s->next=q;
    p->next=s;
}

1.2.4 删除

代码语言：javascript复制

void DelList(LNode **L,int i)//删除第i位置元素
{
    LNode *p=*L;//p指向头结点
    int j=0;
    while (p!=NULL && j<i-1)//p定位第i-1节点
    {
        p=p->next;
        j  ;
    }
    p->next=p->next->next;
}

1.2.5 销毁

代码语言：javascript复制

void DestoryList(LNode **L)//销毁链表
{
    LNode *p=*L,*p2=(*L)->next;//p指向头结点,p2指向首节点
    while (p!=NULL)
    {
        free(p);
        p=p2;
        p2=p2->next;
    }
}

1.3 完整代码

代码语言：javascript复制

#include <iostream>

using namespace std;

struct LNode{
	int data;
	LNode *next;
};

//创建链表：尾插法
void CreateLNode(LNode **L,int a[],int n){
	LNode *s,*r;
	*L=(LNode *)malloc(sizeof(LNode));
	r=*L;
	for(int i=0;i<n;i  ){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;
}

//输出链表
void DispLNode(LNode **L){
	LNode *p=*L;
	while(p->next!=NULL){
		cout<<p->next->data<<" ";
		p=p->next;
	}
	cout<<endl;
}

//插入
void InsertLNode(LNode **L,int n,int e){
	LNode *p=*L;
	for(int i=0;i<n-1 && p!=NULL;){
		p=p->next;
		i  ;
	}
	if(p==NULL) cout<<"error!"<<endl;
	else{
		LNode *q,*s=(LNode *)malloc(sizeof(LNode));
		s->data=e;

		q=p->next;
		s->next=q;
		p->next=s;
	}
}
//删除
void DelLNode(LNode **L,int n){
	LNode *p=*L;
	for(int i=0;i<n-1 && p!=NULL;){
		p=p->next;
		i  ;
	}
	if(p==NULL) cout<<"error!"<<endl;
	else{
		LNode *q=p->next;
		p->next=q->next;
	}
}

//查找
void Sreach(LNode **L,int e){
	LNode *p=*L;
	int count=0,flag=0;
	while(p->next!=NULL){
		if(p->next->data==e){
			flag=1;
			break;
		}
		else p=p->next;
		count  ;
	}
	if(flag!=0){
		cout<<"查找成功，"<<e<<"位于第"<<count<<"位"<<endl;
	}
	else cout<<"查找失败"<<endl;
}

//销毁
void DesLNode(LNode **L){
	LNode *p=*L,*q=(*L)->next;
	while(p!=NULL){
		free(p);
		p=q;
		q=q->next;
	}
}

//判断是否为空串
void NullLNode(LNode **L){
    LNode *p=*L;
    if(p->next== NULL) cout<<"空串"<<endl;
    else cout<<"不是空串"<<endl;
}

int main(){
	LNode *L;
	int a[]={0,1,2,3,4,5,6,7,8,9,10};
	int n=sizeof(a)/sizeof(a[0]);

	CreateLNode(&L,a,n);
	DispLNode(&L);
    NullLNode(&L);

	//插入
	InsertLNode(&L,2,5);
	DispLNode(&L);
	
	//删除
	DelLNode(&L,2);
	DispLNode(&L);

	//查找
	Sreach(&L,5);

	//销毁
	DesLNode(&L);
	//NullLNode(&L);

	return 0;
}

---

2. 双链表

2.1 定义

代码语言：javascript复制

typedef struct LNode//单链表定义
{
    int data;
    struct LNode *next;
}LNode;

2.2 常用操作

2.2.1 创建

尾插法创建：

代码语言：javascript复制

void CreateDListB(DNode **L,int a[],int n) //尾插法创建双链表
{
    DNode *r,*s;
    *L=(DNode *)malloc(sizeof(DNode));
    r=*L;
    for(int i=0;i<n;i  ){
        s=(DNode *)malloc(sizeof(DNode));
        s->data=a[i];s->prior=r;//就这里不一样而已
        r->next=s;
        r=s;
    }
    r->next=NULL;
}

2.2.2 输出

和单链表一样。

2.2.3 插入

代码语言：javascript复制

void InsertDList(DNode **L,int i,int e)//位置i插入元素e
{
    DNode *p,*s,*q;
    p=*L;

    int j=0;
    while (p!=NULL && j<i-1)
    {
        p=p->next;
        j  ;
    }
    s=(DNode *)malloc(sizeof(DNode));
    s->data=e;

    q=p->next;
    s->next=q;q->prior=s;//就这里和单链表不一样
    p->next=s;s->prior=p;//就这里和单链表不一样
}

2.2.4 删除

和单链表一样。

2.2.5 销毁

和单链表一样。

2.3 完整代码

代码语言：javascript复制

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

typedef struct DNode
{
    int data;
    struct DNode *prior;
    struct DNode *next;
}DNode;

void CreateDListB(DNode **L,int a[],int n); //尾插法创建双链表
void DispDList(DNode *L); //输出双链表
void InsertDList(DNode **L,int i,int e);//位置i插入元素e
void DelDList(DNode **L,int i);//删除第i位置元素
void DestoryDList(DNode **L);//销毁链表


int main()
{
    DNode *L;
    int a[10]={0,1,2,3,4,5,6,7,8,9};
    CreateDListB(&L,a,10);
    InsertDList(&L,1,2);
    DelDList(&L,1);
    DispDList(L);

    DestoryDList(&L);
    DispDList(L);

    return 0;
}

void CreateDListB(DNode **L,int a[],int n) //尾插法创建双链表
{
    DNode *r,*s;
    *L=(DNode *)malloc(sizeof(DNode));
    r=*L;
    for(int i=0;i<n;i  ){
        s=(DNode *)malloc(sizeof(DNode));
        s->data=a[i];s->prior=r;
        r->next=s;
        r=s;
    }
    r->next=NULL;
}

void DispDList(DNode *L) //输出双链表
{
    DNode *p=L;//p指向头节点
    while (p!=NULL)
    {
        printf("%d ",p->next->data);
        p=p->next;
    }
    printf("n");
}

void InsertDList(DNode **L,int i,int e)//位置i插入元素e
{
    DNode *p,*s,*q;
    p=*L;

    int j=0;
    while (p!=NULL && j<i-1)
    {
        p=p->next;
        j  ;
    }
    s=(DNode *)malloc(sizeof(DNode));
    s->data=e;

    q=p->next;
    s->next=q;q->prior=s;//就这里不一样
    p->next=s;s->prior=p;//就这里不一样
}

void DelDList(DNode **L,int i)//删除第i位置元素
{
    DNode *p=*L;//p指向头结点
    int j=0;
    while (p!=NULL && j<i-1)//p定位第i-1节点
    {
        p=p->next;
        j  ;
    }
    p->next=p->next->next;
}

void DestoryDList(DNode **L)//销毁链表
{
    DNode *p=*L,*p2=(*L)->next;//p指向头结点,p2指向首节点
    while (p!=NULL)
    {
        free(p);
        p=p2;
        p2=p2->next;
    }
}

---

3. 循环链表

3.1 定义

循环链表是一种链表数据结构，其特点是链表的尾节点指向链表中的头节点，形成一个循环。包括循环单链表和循环双链表。 循环单链表：每个节点包含一个next指针，并且尾节点的next指针指向头节点。 循环双链表：每个节点包含next指针和piror指针。尾节点的next指针指向头节点，头节点的piror指针指向尾节点。

3.2 扫描链表结束的临界条件

p!=L //while语句内，正常为p!=NULL

3.3 环形链表

环形链路： 环形链路指的是在链表中存在一个或多个节点形成了循环，其中一个节点指向先前的节点，导致链表永无止境地继续下去。是链表中的问题或异常情况 解决：判断链表是否为环形链表，通常可以使用两个指针（快慢指针）的方法，也称为弗洛伊德环检测算法。以下是判断环形链表的一般步骤：

1. 使用两个指针，一个称为"慢指针"，另一个称为"快指针"，同时从链表的起始节点出发。
2. 在每一步中，慢指针前进一步，快指针前进两步。如果链表中存在环，快指针最终会进入环中，并在某个时刻与慢指针相遇。如果链表不包含环，快指针将在某个时刻到达链表的末尾并未曾与慢指针相遇。
3. 如果快慢指针相遇，那么链表包含环，可以判断为环形链表。

---

致读者

非知之难，行之为难；非行之难，终之斯难

c++ 数据结构 int 链表 指针

0 人点赞