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

92 阅读 0 评论 61 点赞

我是靠谱客的博主沉默糖豆，最近开发中收集的这篇文章主要介绍循环双链表的基本操作实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

双链表类的定义

#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;
}
}

主函数代码

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.不懂得如何将双链表连接为循环链表，在查阅书籍后才知道，应该把头结点的prior指向first，同时next也指向first，也就是将终端结点的指针域由空指针，改为指向头结点。

2.一开始定义遍历函数的时候没有意识到这是一个循环列表，判断条件设置为工作节点的next是否为空，而出现死循环。后来才意识到判断条件应该是工作节点的next是否为first。

输入、查询功能的执行结果