前言
什么是链表？
线性表的链式存储结构称为链表（Linked List）。链表是一种常见的线性数据结构，用于组织和存储一系列元素，这些元素以节点（Node）的形式连接在一起。每个节点包括两个主要部分：用于存储数据的数据域（Data Field）和指向节点的指针域（Next Pointer）。链表可以有不同的变种，包括单链表、双链表和循环链表等。
双链表和单链表的优缺点
1. 单链表
1.1 定义
typedef struct LNode//单链表定义 { int data; struct LNode *next; }LNode;
1.2 常用操作
1.2.1 创建
尾插法创建：(额...头插和尾插会一个就行，因为尾插法创建的顺序和输入数组一样所以习惯了）
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 输出
void DispList(LNode *L) //输出单链表 { LNode *p=L;//p指向头节点 while (p!=NULL) { printf("%d ",p->next->data); p=p->next; } printf("\n"); }
1.2.3 插入
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 删除
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 销毁
void DestoryList(LNode **L)//销毁链表 { LNode *p=*L,*p2=(*L)->next;//p指向头结点,p2指向首节点 while (p!=NULL) { free(p); p=p2; p2=p2->next; } }
1.3 完整代码
#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 定义
typedef struct LNode//单链表定义 { int data; struct LNode *next; }LNode;
2.2 常用操作
2.2.1 创建
尾插法创建：
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 插入
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 完整代码
#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 环形链表
环形链路： 环形链路指的是在链表中存在一个或多个节点形成了循环，其中一个节点指向先前的节点，导致链表永无止境地继续下去。是链表中的问题或异常情况
解决：判断链表是否为环形链表，通常可以使用两个指针（快慢指针）的方法，也称为弗洛伊德环检测算法。以下是判断环形链表的一般步骤：
- 使用两个指针，一个称为"慢指针"，另一个称为"快指针"，同时从链表的起始节点出发。
- 在每一步中，慢指针前进一步，快指针前进两步。如果链表中存在环，快指针最终会进入环中，并在某个时刻与慢指针相遇。如果链表不包含环，快指针将在某个时刻到达链表的末尾并未曾与慢指针相遇。
- 如果快慢指针相遇，那么链表包含环，可以判断为环形链表。
致读者
非知之难，行之为难；非行之难，终之斯难
