循环双链表的基本操作实现

136 阅读 0 评论 90 点赞

我是靠谱客的博主沉默糖豆，这篇文章主要介绍循环双链表的基本操作实现，现在分享给大家，希望可以做个参考。

目的：巩固线性表的数据结构的储存方法和相关操作，理解循环双链表的特点以及算法的基本思想。

内容：用头插法建立带头结点的循环双链表并对已创建的双链表实现插入、删除、查找等基本操作。

特点：不使用模板机制，确定数据类型为int

双链表类的定义

复制代码

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
#include<iostream>
#include<iomanip>
//使用了setw()
using namespace std;
struct Node
{
int data;
Node *prior;
Node *next;
//前驱指针、和后继指针
};
class LinkList
{
public:
LinkList()
/*无参构造函数，建立只有头结点的空链表*/
{
Node *first;
first->next=first;
first->prior=first;
}
LinkList(int a[],int n);
/*建立有n个元素的链表*/
~LinkList();
void Insert(int i,int x);
/*在第i个位置中插入元素值为X的结点*/
int Length();
/*求双链表的长度*/
int Get(int i);
/*按位查找，在链表中查找第i个结点的元素值*/
int Locate(int x);
/*按值查找*/
int Delete(int i);
/*删除链表中第i个结点*/
void PrintList();
/*按序号依次输出各元素*/
private:
Node *first;
/*双链表的头指针*/
};

成员函数的定义

复制代码

//头插法创建链表
LinkList::LinkList(int a[],int n)
{
Node *s,*f;
first=new Node;
f=first;
for(int i=0;i<n;i++)
{
s=new Node;
s->data=a[i];
s->prior=f;
f->next=s;
f=f->next;
}
f->next=first;
first->prior=f;
}
LinkList::~LinkList()
{
Node *p=first->next;
Node *t;
t=first;
while(p!=first)
{
delete t;
t=p;
p=p->next;
}
}
//插入算法
void LinkList::Insert(int i,int x)
{
Node *p=first;
Node *s;
int count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL) throw "没有找到结点";
else
{
s=new Node;
s->data=x;
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
}
}
//求双链表的长度
int LinkList::Length()
{
Node *p=first->next;
int count=0;
while(p!=first)
{
p=p->next;
count++;
}
return count;
}
//遍历双链表的数据
void LinkList::PrintList()
{
Node *q=first->next;
while(q!=first)
{
cout<<q->data<<endl;
q=q->next;
}
}
//按位查找数据
int LinkList::Get(int i)
{
Node *p=first->next;
int count=0;
if(p!=first)
{
while(count<i)
{
if(count==i-1)
{
cout<<'n'<<p->data<<endl;
}
p=p->next;
count++;
}
}
else
{
return 0;
}
}
//按值查找数剧
int LinkList::Locate(int x)
{
Node *p=first->next;
int count;
for(count=1;p!=first;count++)
{
if(p->data==x)
{
return count;
}
p=p->next;
}
return 0;
}
//删除链表中第i个结点
int LinkList::Delete(int i)
{
Node *p=first;
int count=0;
if(p->next!=first)
{
while(count<i)
{
if(count==i-1)
{
Node *q=p->next;
int x=q->data;
//暂存被删除的结点
(q->prior)->next=q->next;
(q->next)->prior=q->prior;
delete q;
return x;
}
p=p->next;
count++;
}
}
else
{
throw "位置";
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
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
//头插法创建链表
LinkList::LinkList(int a[],int n)
{
Node *s,*f;
first=new Node;
f=first;
for(int i=0;i<n;i++)
{
s=new Node;
s->data=a[i];
s->prior=f;
f->next=s;
f=f->next;
}
f->next=first;
first->prior=f;
}
LinkList::~LinkList()
{
Node *p=first->next;
Node *t;
t=first;
while(p!=first)
{
delete t;
t=p;
p=p->next;
}
}
//插入算法
void LinkList::Insert(int i,int x)
{
Node *p=first;
Node *s;
int count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL) throw "没有找到结点";
else
{
s=new Node;
s->data=x;
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
}
}
//求双链表的长度
int LinkList::Length()
{
Node *p=first->next;
int count=0;
while(p!=first)
{
p=p->next;
count++;
}
return count;
}
//遍历双链表的数据
void LinkList::PrintList()
{
Node *q=first->next;
while(q!=first)
{
cout<<q->data<<endl;
q=q->next;
}
}
//按位查找数据
int LinkList::Get(int i)
{
Node *p=first->next;
int count=0;
if(p!=first)
{
while(count<i)
{
if(count==i-1)
{
cout<<'n'<<p->data<<endl;
}
p=p->next;
count++;
}
}
else
{
return 0;
}
}
//按值查找数剧
int LinkList::Locate(int x)
{
Node *p=first->next;
int count;
for(count=1;p!=first;count++)
{
if(p->data==x)
{
return count;
}
p=p->next;
}
return 0;
}
//删除链表中第i个结点
int LinkList::Delete(int i)
{
Node *p=first;
int count=0;
if(p->next!=first)
{
while(count<i)
{
if(count==i-1)
{
Node *q=p->next;
int x=q->data;
//暂存被删除的结点
(q->prior)->next=q->next;
(q->next)->prior=q->prior;
delete q;
return x;
}
p=p->next;
count++;
}
}
else
{
throw "位置";
return 0;
}
}

主函数代码

复制代码

int main()
{
int n,i;
int a[100];
cout<<"******************"<<endl;
cout<<"*请输入数组的大小"<<endl;
cout<<"******************"<<endl;
cin>>n;
cout<<'n'<<endl;
cout<<"******************"<<endl;
cout<<"*请输入数组元素*"<<endl;
cout<<"******************"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
LinkList one(a,n);
cout<<'n'<<endl;
cout<<"~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"线性表的长"<<one.Length()<<endl;
cout<<'n'<<"线性表中的内容："<<endl;
one.PrintList();
//输出线性表的数据
//按位查找
int s;
cout<<"~~~~~~~~~~~~~~~~~~"<<endl;
cout<<'n'<<endl;
cout<<"**********************"<<endl;
cout<<"*请输入要查找数据的序号："<<endl;
cout<<"**********************"<<endl;
cin>>s;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"您所查询的数据以及所在的序号为";
cout<<one.Get(s)<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
//按值查找
int x;
cout<<'n'<<"**********************"<<'n'<<"*请输入要查找的数据:";
cout<<'n'<<"**********************"<<endl;
cin>>x;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"你所查找的值所在的位置为："<<one.Locate(x)<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
//按序号删除数据
int k;
cout<<'n'<<"**************************"<<'n'<<"*请输入需要删除的数据序号:";
cout<<'n'<<"**************************"<<endl;
cin>>k;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"删除成功！你所删除的数据为："<<one.Delete(k)<<endl;
cout<<'n'<<"线性表的内容为:"<<endl;
one.PrintList();
//输出线性表的数据
cout<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
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
int main()
{
int n,i;
int a[100];
cout<<"******************"<<endl;
cout<<"*请输入数组的大小"<<endl;
cout<<"******************"<<endl;
cin>>n;
cout<<'n'<<endl;
cout<<"******************"<<endl;
cout<<"*请输入数组元素*"<<endl;
cout<<"******************"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
LinkList one(a,n);
cout<<'n'<<endl;
cout<<"~~~~~~~~~~~~~~~~~~"<<endl;
cout<<"线性表的长"<<one.Length()<<endl;
cout<<'n'<<"线性表中的内容："<<endl;
one.PrintList();
//输出线性表的数据
//按位查找
int s;
cout<<"~~~~~~~~~~~~~~~~~~"<<endl;
cout<<'n'<<endl;
cout<<"**********************"<<endl;
cout<<"*请输入要查找数据的序号："<<endl;
cout<<"**********************"<<endl;
cin>>s;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"您所查询的数据以及所在的序号为";
cout<<one.Get(s)<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
//按值查找
int x;
cout<<'n'<<"**********************"<<'n'<<"*请输入要查找的数据:";
cout<<'n'<<"**********************"<<endl;
cin>>x;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"你所查找的值所在的位置为："<<one.Locate(x)<<endl;
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
//按序号删除数据
int k;
cout<<'n'<<"**************************"<<'n'<<"*请输入需要删除的数据序号:";
cout<<'n'<<"**************************"<<endl;
cin>>k;
cout<<'n'<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
cout<<'n'<<"删除成功！你所删除的数据为："<<one.Delete(k)<<endl;
cout<<'n'<<"线性表的内容为:"<<endl;
one.PrintList();
//输出线性表的数据
cout<<'n'<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
return 0;
}