数据结构-----双向循环链表
瞎扯:白天被迫改一个重现都无法重现的错误.各种百度，各种测试,头发掉了一地，然鹅还是没解决出来 。所以晚上复习数据结构放松一下
DualCircleLinkList.h的代码(你也可以省略函数声明)
typedef int status;
typedef int ElemType;
typedef struct DualCircleLinkListNode
{ ElemType data;
struct DualCircleLinkListNode *next;
struct DualCircleLinkListNode *prior;
}DualCircleLinkListNode,*DualCircleLinkListList;
//定义链表的类
class DualCircleLinkList
{
public :
DualCircleLinkList();//初始化类:一个类就代表着一个双向循环链表
DualCircleLinkList(ElemType data);
status InsertDualCircleLinkList(int index,ElemType data);//向链表中插入数据
status DualCircleLinkListLength();//求其长度
status GetDualCircleLinkListElem(int index,ElemType &e);//获取特定位置上的数据
int DeleteDualCircleLinkListElem(int pos);//删除指定位置上的数据
int PrintDualCircleLinkListData();
void addData(int data);//直接在尾部插入数据
DualCircleLinkListList head;//头指针
DualCircleLinkListList cur;//当前指针
int size;//链表大小
};
函数实现代码
#include<iostream>
#include"DualCircleLinkList.h"
using namespace std;
DualCircleLinkList::DualCircleLinkList()
{
head =new DualCircleLinkListNode[sizeof(DualCircleLinkListNode)];
head->prior=head->next=NULL;
cur=head;
size = 0;
}//类的初始化函数
//DualCircleLinkList 代表类
//DualCircleLinkListNode 代表 结点
//DualCircleLinkListList 代表结点指针
int DualCircleLinkList::DeleteDualCircleLinkListElem(int pos){//删除指定位置的数据
//先检查数据的合法性
if (size >= pos && pos > 0)
{
int count = 1;//计数
DualCircleLinkListList temp = head;
while (pos != count){
temp = temp->next;//直到到达指定的位置
count++;
}
//先到达指定位置
if (size == pos)
{
if (1 == size)
{//只有一个节点的时候
delete []temp;
head = cur;
size--;
return 0;
}
else
{//删除最后一个节点
cur = temp->prior;//向前移动一个位置
}
}
else
{
if (1 == pos)
{
head = temp->next;//向后移动一个位置
}
}
temp->prior->next = temp->next;
temp->next = temp->prior;
size--;//长度-1
return 0;//成功返回0
}
return -1;//无数据或者越界返回-1
}
int DualCircleLinkList::InsertDualCircleLinkList(int pos, ElemType data){//在指定位置插入数据
if (size >= pos && pos > 0)
{//有数据并且没有越界才显示
int count = 1;//计数
DualCircleLinkListList dcl = new DualCircleLinkListNode[sizeof(DualCircleLinkListNode)];//结点的申请空间
dcl->data = data;
DualCircleLinkListList temp = head;
while (pos != count){
temp = temp->next;//直到到达指定的位置
count++;
}
//先到达指定位置
//分情况是因为如果插入到第一个节点会改变head的状态
if (size == pos)
{
if (1 == size)
{
head = dcl;
head->next = temp;
temp->prior = head;
head->prior = temp;
temp->next = head;
}
else
{
temp->prior->next = dcl;
dcl->prior = temp->prior;
dcl->next = temp;
temp->prior = dcl;
}
size++;
return 0;
}
else
{
if (1 == pos){
head = dcl;
head->next = temp;
temp->prior = head;
head->prior = temp->prior;
temp->prior->prior = head;
}
else
{
temp->prior->next = dcl;
dcl->prior = temp->prior;
dcl->next = temp;
temp->prior = dcl;
}
size++;
return 0;
}
}
return -1;//越界返回-1
}
int DualCircleLinkList::GetDualCircleLinkListElem(int pos,int &e)
{//获得指定位置的数据
if (size >= pos && pos > 0)
{
int count = 1;
DualCircleLinkListList temp = head;
while (pos != count){
temp = temp->next;
count++;
}
return temp->data;
}
return -1;//无数据或者越界返回-1
}
int DualCircleLinkList::DualCircleLinkListLength(){
return size;
}
int DualCircleLinkList::PrintDualCircleLinkListData()
{//打印链表
if (NULL != head)
{//链表非空
DualCircleLinkListList temp = head;
int count = 0;//计数
while (size != count){
std::cout<<temp->data<<" ";
temp = temp->next;
count++;
}
return 0;
}
return -1;//空表返回-1
}
//如果头结点为空那么就为其开辟头结点,如果不为空那么就直接添加到链表的末尾
void DualCircleLinkList::addData(int data)
{
DualCircleLinkListList dcl = new DualCircleLinkListNode[sizeof(DualCircleLinkListNode)];
dcl->data = data;//所要添加的结点
if (NULL != head->next)
{//表非空
DualCircleLinkListList temp = cur->next;
cur->next = dcl;
dcl->prior = cur;
dcl->next = temp;
temp->prior = dcl;
}
else {
head = dcl;//新加节点成为头结点
head->data = data;
head->prior = head->prior = head;//指向自身
}//已经添加完毕,新增节点成为当前节点
cur = dcl;
size++;//长度+1
}
函数调用
#include<iostream>
#include"DualCircleLinkList.h"
//判断双向循环链表是否对称
status ifSymmetric(DualCircleLinkList test)
{
DualCircleLinkListList p;
p=test.head->next;
DualCircleLinkListList q;
q=test.head->prior;
int i=1;
while(p==q&&i<=(test.DualCircleLinkListLength()/2))
{
i++;
p=p->next;
q=q->prior;
}
if(i==(test.DualCircleLinkListLength()/2))
return 1;
return 0;
}
int main()
{ //声明一个头结点
DualCircleLinkList test;
//向链表中添加一个数据
test.addData(1);
//在1的位置上插入9个数据
for(int i=1;i<10;i++)
{
if( test.InsertDualCircleLinkList(1,i)==0)
printf("添加成功!\n");
else
printf("添加失败!\n");
}
//打印当前的链表的长度
printf("当前长度为%d\n", test.DualCircleLinkListLength());
//打印当前的链表的数据
test.PrintDualCircleLinkListData();
//删除数据
test.DeleteDualCircleLinkListElem(1);
if(ifSymmetric(test)==1)
{ printf("对称\n");
}
else
{
printf("不对称\n");
}
}