双向链表实现(c/c++)二.链表的基本操作实现三.总结

74 阅读 0 评论 49 点赞

我是靠谱客的博主辛勤信封，这篇文章主要介绍双向链表实现(c/c++)二.链表的基本操作实现三.总结，现在分享给大家，希望可以做个参考。

前言

数据结构还是得来一手。

一.关于链表

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//单个节点结构体
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.初始化一个链表

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//初始化一个节点的链表
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.链表的插入

咱们先来看看头插

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//头插
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++;
}

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//尾插
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++;
}

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

再来看一看按位置插入：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//按位置插入,位置还是从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.链表的遍历

首先看代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//头部遍历
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. 链表的删除

首先看头删：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//头删
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;
}

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

再看看尾删:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//尾删
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;
}

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

再来看看按位置删除：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//按位置删除
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.修改节点数据

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//按位置更改数据，序号从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;
}

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//按值更改数据,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.查找

查找某个位置的值：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//返回某个值第一次出现在链表的位置
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;
}

清除链表

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//清除链表中的节点，变成初始化的样子
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文件：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
#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:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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++)二.链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数据结构与算法分析
浏览次数：74 次浏览
发布日期：2024-01-07 22:55:48
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_ogfx_14_j_6_z.html

双向链表实现(c/c++)二.链表的基本操作实现三.总结

前言

一.关于链表

二.链表的基本操作实现

1.初始化一个链表

2.链表的插入

3.链表的遍历

4. 链表的删除

5.修改节点数据

6.查找

清除链表

三.总结

最后

评论列表共有 0 条评论

发表评论取消回复

双向链表实现(c/c++)二.链表的基本操作实现三.总结

前言

一.关于链表

二.链表的基本操作实现

1.初始化一个链表

2.链表的插入

3.链表的遍历

4. 链表的删除

5.修改节点数据

6.查找

清除链表

三.总结

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复