线上学编程哪个机构比较好_旅游最新资讯 新闻_樱桃电视剧西瓜视频在线观看_网络舆情分析报告模板

链表可分为带头，不带头；单向，双向；循环，不循环。各种组合一共有8种；一般常用的就是单链表，和双向带头循环链表。

带头只需要加一个指向第一个节点的哨兵位就行了，循环只需要最后一个节点的next指针指向头节点。

1.单向链表（动态申请）

头文件 slist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;//动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
//打印链表
void SLTPrint(SListNode* phead);
//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SListNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SListNode** pphead);
//头删
void SLTPopFront(SListNode** pphead);
//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x);
//在pos位置之前插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//在pos位置之后插入
void SLTInsertAfter(SListNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SListNode* phead, SListNode* pos);
//销毁链表
void SLTDestroy(SListNode** pphead);

 源文件 slist.c

#include"slist.h"//动态申请一个节点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//打印链表
void SLTPrint(SListNode* phead)
{SListNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//尾插
void SLTPushBack(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;}//链表不为空else{SListNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}//头插
void SLTPushFront(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SListNode** pphead)
{assert(pphead && *pphead);//只有一个节点时if ((*pphead)->next == NULL){free(*pphead);//删除节点一定要释放内存*pphead = NULL;}else{SListNode* prev = NULL;SListNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);//防止内存泄露ptail = NULL;}
}//头删
void SLTPopFront(SListNode** pphead)
{assert(pphead && *pphead);SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在pos位置之前插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && pos);if (pos == *pphead){//头插SLTPushFront(pphead, x);}else{SListNode* prev = *pphead;SListNode* newnode = BuySListNode(x);while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}//在pos位置之后插入
void SLTInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead && pos);//不能穿空指针，不能删空链表if (pos == *pphead){//头删SLTPopFront(pphead);}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SListNode* phead, SListNode* pos)
{assert(phead && pos && pos->next);//链表不为空,pos不为NULL,pos之后有节点SListNode* ne = pos->next;pos->next = ne->next;free(ne);ne = NULL;
}//销毁链表
void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* pcur = *pphead;while (pcur){SListNode* ne = pcur->next;free(pcur);pcur = ne;}*pphead = NULL;
}

---

2.双向链表（动态申请）

头文件 list.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next, * prev;
}ListNode;//申请节点
ListNode* BuyNode(LTDataType x);//初始化
ListNode* InitList();//打印
void LTPrint(ListNode* phead);//尾插
void LTPushBack(ListNode* phead, LTDataType x);//头插
void LTPushFront(ListNode* phead, LTDataType x);//是否为空
bool LTempty(ListNode* phead);//头删
void LTPopFront(ListNode* phead);//尾删
void LTPopBack(ListNode* phead);//查找
ListNode* LTFind(ListNode* phead, LTDataType x);//指定位置删除
void LTErase(ListNode* pos);//pos位置前插入
void LTInsert(ListNode* pos, LTDataType x);//销毁
void LTDestroy(ListNode* phead);

 源文件 list.c

#include"list.h"//申请节点
ListNode* BuyNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//初始化
ListNode* InitList()
{ListNode* head = BuyNode(-1);return head;
}//打印
void LTPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* node = BuyNode(x);node->next = phead;node->prev = phead->prev;phead->prev->next = node;phead->prev = node;
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* node = BuyNode(x);node->next = phead->next;node->prev = phead;phead->next->prev = node;phead->next = node;
}//是否为空
bool LTempty(ListNode* phead)
{assert(phead);return phead->next == phead;
}//头删
void LTPopFront(ListNode* phead)
{assert(!LTempty(phead));//非空ListNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//尾删
void LTPopBack(ListNode* phead)
{assert(!LTempty(phead));ListNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//查找
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//指定位置删除
void LTErase(ListNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;
}//pos位置前插入
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node = BuyNode(x);node->next = pos;node->prev = pos->prev;pos->prev->next = node;pos->prev = node;
}//销毁
void LTDestroy(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);pcur = phead = NULL;
}

---

数组模拟的写法是在竞赛中使用的，因为动态申请的太慢了

3.单向链表（静态数组模拟）

要把e[]数组和ne[]数组一起看，相当于一个结构体的两个元素，可以多画图理解一下

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;//head指向头节点，空时为-1
//e[i]是第i个节点的数值
//ne[i]是第i个节点的后一个节点下标
//idx是当前使用的点的下标，也就是插入的顺序
int head;
int e[N],ne[N];
int idx;void init()
{head=-1;idx=0;
}//头插
void push_front(int x)
{e[idx]=x;ne[idx]=head;head=idx;idx++;
}//下标为k处后面一个位置插入，因为不知道前一个在哪里
void list_insert(int k,int x)
{e[idx]=x;//在数组中按顺序插入，中间删除的不管，算法题做出来就行了ne[idx]=ne[k];ne[k]=idx;idx++;
}//删除下标为k处后面一个的元素，也是因为找不到前一个的位置
void pop(int k)
{ne[k]=ne[ne[k]];//就是直接跳过了k后面一个元素，内存浪费，不用管
}

---

 

4.双向链表（静态数组模拟）

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
//把0，1作为左右边界
int l[N],r[N],e[N],idx;//l,r分别是左右指针域,idx还是插入的个数不过是+1//初始化
void init()
{r[0] = 1;l[1] = 0;idx  = 2;
}//在下标为k的位置右边插入x，左插也可以转化为右插，最左端和最右端同理
void insert(int k,int x)
{e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}//将下标为k的节点删除
void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}