前言

数据结构还是得来一手。

一.关于链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表通过指针域能把多个元素串联起来。
一般的链表中每个元素只有一个指向下一个元素的指针域，而我们的双向链表却有两个指针域，其中一个指针域指向下一个元素，另一个指针域指向这个元素的上一个元素。
接下来看程序设计:

//单个节点结构体
typedef struct Node
{
struct Node *prior;
int data;
struct Node *next;
}Node;
//链表结构体
typedef struct List
{
Node *first;
Node *last;
int size;
}List;

其中Node是为链表的每一个元素，有数据域data，prior是指向前继的指针域，next是指向后继的指针域。List便是我们的双向链表的实现。其中first的next指针指向头节点，last的next指向尾节点，这两个指针能帮助我们找到链表的头节点和尾节点。size便是我们链表中拥有的元素个数。

二.链表的基本操作实现

1.初始化一个链表

初始化一个双向链表的代码如下:

//初始化一个节点的链表
void Initlist(List *list,int x)
{
list->first=(Node*)malloc(sizeof(Node));
list->last=(Node*)malloc(sizeof(Node));
Node *p=(Node*)malloc(sizeof(Node));
if(p==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
p->data=x;
p->prior=NULL;
p->next=NULL;
list->first->next=p;
list->last->next=p;
list->size=1;
}

这里初始化的是带有一个节点的链表，这个节点的数据域就是输入的参数x。因为只有一个节点，所以头尾节点都是它，链表的头尾指针都指向它。这个节点的前继后继都是NULL(空),链表元素个数为1。

2.链表的插入

咱们先来看看头插

//头插
void push_front(List *list,int value)
{
Node *p=list->first->next;
Node *s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
s->data=value;
s->next=p;
p->prior=s;
s->prior=NULL;
list->first->next=s;
list->size++;
}

头插也是非常简单，也就是申请一个新节点，让这个节点变成新的头节点，那么为了让这个节点和链表串联起来，需要把这个节点的后继变成原来链表的头节点，这样这个节点的下个节点就是原来的头节点，这个节点的下下个节点就是原来链表的第二个节点了，这样就把新节点和原来的链表串联起来了，但是还没有完，我们还需要让这个新节点变成头节点。
咱们再来看看尾插：

//尾插
void push_last(List *list,int value)
{
Node *p=list->last->next;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
q->data=value;
p->next=q;
q->prior=p;
q->next=NULL;
list->last->next=q;
list->size++;
}

尾插也很简单，就是申请一个新节点，让这个节点串在链表上并且让它成为新的尾节点。因此需要将原来尾节点的后继变成这个新节点。

再来看一看按位置插入：

//按位置插入,位置还是从0开始，插入的节点直接代替那个节点
int insert_loc(List *list,int loc,int value)
{
Node *p=list->first;
//待插入的节点
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
q->data=value;
if(loc==0)
{
//直接头插的情况
push_front(list,value);
return 0;
}
//直接尾插的情况
if(loc>=(list->size-1))
{
push_last(list,value);
return 0;
}
else
{
//找到loc位置,把链表分为前后半区，位置在前半区从表头开始找，在后半区从表尾开始找
int m_node=int(list->size/2)-1;
//前半区
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
//插入
p->next->prior=q;
q->next=p->next;
p->next=q;
q->prior=p;
}
//后半区插入
else
{
p=list->last->next;
//算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
int loc3=list->size-loc-1;
//找到要插入位置的节点
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
Node *d=p->prior;
q->next=p;
d->next=q;
p->prior=q;
q->prior=d;
}
}
list->size++;
return 0;
}

我们首先处理的是头插和尾插的情况。然后在除了这两种情况的插入的时候，我们把整个链表分为了前半区和后半区，要插入的位置在前半区就从表头开始遍历寻找要插入的位置的前继，在后半区的话就从尾节点开始遍历寻找这个要插入位置的节点。

3.链表的遍历

首先看代码：

//头部遍历
void show_list(List *list)
{
cout<<"list size:"<<list->size<<"//";
Node *p=list->first->next;
while(p->next!=NULL)
{
cout<<p->data<<"->";
p=p->next;
}
cout<<p->data<<"->NULL"<<endl;
}
//尾部遍历
void show_list_last(List *list)
{
cout<<"list size:"<<list->size<<"//";
Node *p=list->last->next;
while(p->prior!=NULL)
{
cout<<p->data<<"->";
p=p->prior;
}
cout<<p->data<<"->NULL"<<endl;
}

关于链表的遍历笔者写了两种，分别是从头节点从前往后和尾节点从后往前开始遍历。前者是不断去节点的后继，而后者则是不断取节点的前继。

4. 链表的删除

首先看头删：

//头删
int pop_front(List *list)
{
Node *p=list->first->next;
//第二个元素前驱置空
p->next->prior=NULL;
//更新头节点
list->first->next=p->next;
//原来的第一个元素后继置空
p->next=NULL;
//删除
free(p);
list->size--;
return 0;
}

头删也就是让原链表的第二个节点变成头节点，把第一个节点从链表上拿下来。

再看看尾删:

//尾删
int pop_last(List *list)
{
Node *p=list->last->next;
Node *q=list->last->next;
// list->last->next=p->prior;
//倒数第二个元素后继置空
p=p->prior;
p->next->prior=NULL;
// //更新尾节点
list->last->next=p;
// //原来最后一个元素前继为空
p->next=NULL;
//删除
free(q);
list->size--;
return 0;
}

尾删也就是从链表上拿下尾节点，让原来的倒数第二个节点变成尾节点。

再来看看按位置删除：

//按位置删除
int delete_loc(List *list,int loc)
{
Node *p=list->first;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
if(loc==0)
{
//头删
pop_front(list);
return 0;
}
else if(loc>=(list->size-1))
{
//尾删
pop_last(list);
return 0;
}
else
{
//中间位置,分成两个半区
int m_node=int(list->size/2)-1;
if(m_node<0)
{
m_node=0;
}
//前半区,那就是从头节点开始
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);
}
else
{
//在后半区，从尾节点开始找
p=list->last->next;
int loc3=list->size-loc-1;
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
q=p->prior;
q->next=p->next;
p->next->prior=q;
free(p);
}
}
list->size--;
return 0;
}

按位置删除的代码和插入的思路差不多。

5.修改节点数据

来看看修改某一位置节点数据的实现：

//按位置更改数据，序号从0开始
int change_loc(List *list,int loc,int x)
{
Node *p=list->first->next;
if(loc==0)
{
//头删
list->first->next->data=x;
return 0;
}
else if(loc>=(list->size-1))
{
//尾删
list->last->next->data=x;
return 0;
}
else
{
//中间位置,分成两个半区
int m_node=int(list->size/2)-1;
//前半区,那就是从头节点开始
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
p->data=x;
}
else
{
//在后半区，从尾节点开始找
p=list->last->next;
//算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
int loc3=list->size-loc-1;
//找到要插入位置的节点
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
p->data=x;
}
}
return 0;
}

再来看看修改某个值第一次出现位置的数据的代码：

//按值更改数据,x需要修改的数据,x_change 修改后的数据
int change_value(List *list,int x,int x_change)
{
if(x==x_change)
{
cout<<"value error"<<endl;
return 0;
}
Node *p=list->first->next;
while(p->data!=x&&p->next!=NULL)
{
p=p->next;
}
if(p->next==NULL)
{
//到了尾节点
if(p->data==x)
{
p->data=x_change;
return 0;
}
cout<<"No this value"<<endl;
return 0;
}
p->data=x_change;
return 0;
}

代码实现也很简单，这里就 不多写了。

6.查找

查找某个位置的值：

int find_loc(List *list,int loc)
{
if(loc>(list->size-1))
{
cout<<"no this loc"<<endl;
return -1;
}
Node *p=list->first;
for(int i=0;i<=loc;i++)
{
p=p->next;
}
return p->data;
}

查找某个值第一次出现在链表中的位置：

//返回某个值第一次出现在链表的位置
int find_value(List *list,int value)
{
Node *p=list->first->next;
int i=0;
while(p->data!=value&&p->next!=NULL)
{
p=p->next;
i++;
}
if(p->next==NULL)
{
if(p->data==value)
{
return i;
}
else
{
cout<<"value error:No this value"<<endl;
return -1;
}
}
return i;
}

清除链表

再来看看将一个链表变成初始化样子的代码，也就是只有一个节点的样子：

//清除链表中的节点，变成初始化的样子
void clear(List *list,int x)
{
if(list->size==1)
{
cout<<"list had be clear"<<endl;
return;
}
Node *p=list->first->next;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
while(p->next!=NULL)
{
q=p;
p=p->next;
q->next=NULL;
q->prior=NULL;
free(q);
}
list->first->next=list->last->next=p;
p->next=NULL;
p->prior=NULL;
p->data=x;
list->size=1;
}

其中参数x就是这个节点的值。

三.总结

总结的代码如下：
新建一个list.h文件：

#ifndef LIST_H
#define LIST_H
#include<iostream>
#include<malloc.h>
using namespace std;
//单个节点结构体
typedef struct Node
{
struct Node *prior;
int data;
struct Node *next;
}Node;
//链表结构体
typedef struct List
{
Node *first;
Node *last;
int size;
}List;
//初始化一个节点地链表
void Initlist(List *list,int x);
//头部遍历
void show_list(List *list);
//尾部遍历
void show_list_last(List *list);
//头插
void push_front(List *list,int value);
//尾插
void push_last(List *list,int value);
//按位置插入
int insert_loc(List *list,int loc,int value);
//头删
int pop_front(List *list);
//尾删
int pop_last(List *list);
//按位置删除
int delete_loc(List *list,int loc);
//按位置修改data
int change_loc(List *list,int loc,int x);
//按值修改数据
int change_value(List *list,int x,int x_change);
//返回某个位置上的data
int find_loc(List *list,int loc);
//返回某个值第一次出现在链表的位置
int find_value(List *list,int value);
//清除链表中的节点，变成初始化的样子
void clear(List *list,int x);
#endif

新建一个list.cpp文件，代码如下:

#include"list.h"
//初始化一个节点的链表
void Initlist(List *list,int x)
{
list->first=(Node*)malloc(sizeof(Node));
list->last=(Node*)malloc(sizeof(Node));
Node *p=(Node*)malloc(sizeof(Node));
if(p==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
p->data=x;
p->prior=NULL;
p->next=NULL;
list->first->next=p;
list->last->next=p;
list->size=1;
}
//头部遍历
void show_list(List *list)
{
cout<<"list size:"<<list->size<<"//";
Node *p=list->first->next;
while(p->next!=NULL)
{
cout<<p->data<<"->";
p=p->next;
}
cout<<p->data<<"->NULL"<<endl;
}
//尾部遍历
void show_list_last(List *list)
{
cout<<"list size:"<<list->size<<"//";
Node *p=list->last->next;
while(p->prior!=NULL)
{
cout<<p->data<<"->";
p=p->prior;
}
cout<<p->data<<"->NULL"<<endl;
}
//头插
void push_front(List *list,int value)
{
Node *p=list->first->next;
Node *s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
s->data=value;
s->next=p;
p->prior=s;
s->prior=NULL;
list->first->next=s;
list->size++;
}
//尾插
void push_last(List *list,int value)
{
Node *p=list->last->next;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
q->data=value;
p->next=q;
q->prior=p;
q->next=NULL;
list->last->next=q;
list->size++;
}
//按位置插入,位置还是从0开始，插入的节点直接代替那个节点
int insert_loc(List *list,int loc,int value)
{
Node *p=list->first;
//待插入的节点
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
q->data=value;
if(loc==0)
{
push_front(list,value);
return 0;
}
//直接尾插的情况
if(loc>=(list->size-1))
{
push_last(list,value);
return 0;
}
else
{
//找到loc位置,把链表分为前后半区，位置在前半区从表头开始找，在后半区从表尾开始找
int m_node=int(list->size/2)-1;
//前半区
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
//插入
p->next->prior=q;
q->next=p->next;
p->next=q;
q->prior=p;
}
//后半区插入
else
{
p=list->last->next;
//算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
int loc3=list->size-loc-1;
//找到要插入位置的节点
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
Node *d=p->prior;
q->next=p;
d->next=q;
p->prior=q;
q->prior=d;
}
}
list->size++;
return 0;
}
//头删
int pop_front(List *list)
{
Node *p=list->first->next;
//第二个元素前驱置空
p->next->prior=NULL;
//更新头节点
list->first->next=p->next;
//原来的第一个元素后继置空
p->next=NULL;
//删除
free(p);
list->size--;
return 0;
}
//尾删
int pop_last(List *list)
{
Node *p=list->last->next;
Node *q=list->last->next;
// list->last->next=p->prior;
//倒数第二个元素后继置空
p=p->prior;
p->next->prior=NULL;
// //更新尾节点
list->last->next=p;
// //原来最后一个元素前继为空
p->next=NULL;
//删除
free(q);
list->size--;
return 0;
}
//按位置删除
int delete_loc(List *list,int loc)
{
Node *p=list->first;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
if(loc==0)
{
//头删
pop_front(list);
return 0;
}
else if(loc>=(list->size-1))
{
//尾删
pop_last(list);
return 0;
}
else
{
//中间位置,分成两个半区
int m_node=int(list->size/2)-1;
if(m_node<0)
{
m_node=0;
}
//前半区,那就是从头节点开始
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);
}
else
{
//在后半区，从尾节点开始找
p=list->last->next;
int loc3=list->size-loc-1;
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
q=p->prior;
q->next=p->next;
p->next->prior=q;
free(p);
}
}
list->size--;
return 0;
}
//按位置更改数据，序号从0开始
int change_loc(List *list,int loc,int x)
{
Node *p=list->first->next;
if(loc==0)
{
//头删
list->first->next->data=x;
return 0;
}
else if(loc>=(list->size-1))
{
//尾删
list->last->next->data=x;
return 0;
}
else
{
//中间位置,分成两个半区
int m_node=int(list->size/2)-1;
//前半区,那就是从头节点开始
if(loc<=m_node)
{
//找到loc位置的前继节点
for(int i=0;i<loc;i++)
{
p=p->next;
}
p->data=x;
}
else
{
//在后半区，从尾节点开始找
p=list->last->next;
int loc3=list->size-loc-1;
for(int i=0;i<loc3;i++)
{
p=p->prior;
}
p->data=x;
}
}
return 0;
}
//按值更改数据,x需要修改的数据,x_change 修改后的数据
int change_value(List *list,int x,int x_change)
{
if(x==x_change)
{
cout<<"value error"<<endl;
return 0;
}
Node *p=list->first->next;
while(p->data!=x&&p->next!=NULL)
{
p=p->next;
}
if(p->next==NULL)
{
//到了尾节点
if(p->data==x)
{
p->data=x_change;
return 0;
}
cout<<"No this value"<<endl;
return 0;
}
p->data=x_change;
return 0;
}
//返回某个位置上的data
int find_loc(List *list,int loc)
{
if(loc>(list->size-1))
{
cout<<"no this loc"<<endl;
return -1;
}
Node *p=list->first;
for(int i=0;i<=loc;i++)
{
p=p->next;
}
return p->data;
}
//返回某个值第一次出现在链表的位置
int find_value(List *list,int value)
{
Node *p=list->first->next;
int i=0;
while(p->data!=value&&p->next!=NULL)
{
p=p->next;
i++;
}
if(p->next==NULL)
{
if(p->data==value)
{
return i;
}
else
{
cout<<"value error:No this value"<<endl;
return -1;
}
}
return i;
}
//清除链表中的节点，变成初始化的样子
void clear(List *list,int x)
{
if(list->size==1)
{
cout<<"list had be clear"<<endl;
return;
}
Node *p=list->first->next;
Node *q=(Node*)malloc(sizeof(Node));
if(q==NULL)
{
cout<<"No space"<<endl;
exit(0);
}
while(p->next!=NULL)
{
q=p;
p=p->next;
q->next=NULL;
q->prior=NULL;
free(q);
}
list->first->next=list->last->next=p;
p->next=NULL;
p->prior=NULL;
p->data=x;
list->size=1;
}

然后是一个简单的运行程序，main.cpp:

#include"list.h"
#include<malloc.h>
#include<iostream>
using namespace std;
int main()
{
int loc=0,x=2;
List *L=(List*)malloc(sizeof(List));
Initlist(L,1);
push_last(L,2);
push_front(L,3);
push_last(L,7);
insert_loc(L,9,4);
push_last(L,6);
show_list(L);
show_list_last(L);
return 0;
}

这里一定要注意(List*)malloc(sizeof(List))是必要的，不然我们的链表就没有内存空间就会运行不了。

最后

以上就是辛勤信封为你收集整理的双向链表实现(c/c++)二.链表的基本操作实现三.总结的全部内容，希望文章能够帮你解决双向链表实现(c/c++)二.链表的基本操作实现三.总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。