循环队列本身是一种顺序存储结构,而循环列表是一种链式存储结构。两者之间是平级关系。
线性链表是线性表的链式存储结构,包括单链表,双链表,循环链表等。
队列的顺序存储结构一般采用循环队列的形式。
循环队列的操作是按数组取摸运算的,所以是顺序存储,而循环链表本身就是收尾相连的,所以循环链表不是循环队列,两种不同的存储结构,虽然实现的功能是一样的,实现循环两种方式 顺序存储就是循环队列,链式存储就是循环链表。
扩展资料:
1、比顺序存储结构的存储密度小(链式存储结构中每个结点都由数据域与指针域两部分组成,相比顺序存储结构增加了存储空间)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
4、查找节点时链式存储要比顺序存储慢。
5、每个节点是由数据域和指针域组成。
6、由于簇是随机分配的,这也使数据删除后覆盖几率降低,恢复可能提高。
参考资料来源:百度百科-链式存储结构
#include <iostream>using namespace std
typedef char ElemType
typedef int Status
#define OK 1
#define ERROR 0
typedef struct Lnode
{
ElemType data
struct Lnode *next
}Lnode,*LinkList
void Creat_List(LinkList L)//创建单链表并输入元素
{
LinkList p,q
q=L
char ch
cout<<"请输入链表元素,并且以输入#表示结束!"<<endl
while(cin>>ch&&ch!='#')
{
p=new Lnode[sizeof(Lnode)]
if(!p)
{
cout<<"获取内存失败"<<endl
exit(ERROR)
}
p->data=ch//尾插法
L->next=p
L=p
}
L->next=q
}
void output_List(LinkList L)//遍历单链表(输出单链表元素)
{
LinkList p
p=L->next
if(p==L)
{
cout<<"该链表是空链表!"<<endl
exit(ERROR)
}
while(p!=L)
{
cout<<p->data<<" "
p=p->next
}
}
Status main()
{
LinkList H
H=(LinkList)malloc(sizeof(Lnode))
H->next=NULL//设置头结点为空
Creat_List(H)
output_List(H)
return 0
}//头结点有和没有都是可以的,头结点只是为了让操作链表更方便,
至少需要一个元素,空的不能能建立数据结构。
1.循环链表
循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点:
1)在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2)在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。
2.双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。
3.双向循环链表例程:
#include <stdio.h>#include <stdlib.h>
typedef struct tagDbNode
{
int data
struct tagDbNode * left
struct tagDbNode * right
} DbNode, * pdbNode
//创建结点
pdbNode CreateNode(int data)
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode))
pnode->data = data
pnode->left = pnode->right = pnode //创建新结点时,让其前驱和后继指针都指向自身
return pnode
}
//创建链表
pdbNode CreateList(int head) //参数给出表头结点数据 (表头结点不作为存放有意义数据的结点)
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode))
pnode->data = head
pnode->left = pnode->right = pnode
return pnode
}
//插入新结点,总是在表尾插入 返回表头结点
pdbNode InsertNode(pdbNode node, int data) // 参数1是链表的表头结点,参数2是要插入的结点(结
点数据为data)
{
pdbNode pnode = CreateNode(data)
// 从左到右恢复链接
node->left->right = pnode
pnode->right = node
// 从右到左恢复链接
pnode->left = node->left
node->left = pnode
return node
}
//查找结点,成功则返回满足条件的结点指针,否则返回NULL
pdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点,参数2是要查找的结点(其中
结点数据为data)
{
pdbNode pnode = node->right
while (pnode != node && pnode->data != data)
{
pnode = pnode->right
}
if (pnode == node) return NULL
return pnode
}
//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL(失败的原因是不存在该结点)
pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点,参数2是要删除的结点(其
中结点数据为data)
{
pdbNode pnode = FindNode(node, data)
if (NULL == pnode) return NULL
pnode->left->right=pnode->right
pnode->right->left=pnode->left
free(pnode)
return node
}
//获取链表的长度
int GetLength(pdbNode node) // 参数为链表的表头结点
{
int nCount = 0
pdbNode pnode = node->right
while (pnode!= node)
{
pnode = pnode->right
nCount++
}
return nCount
}
//顺序打印整个链表
void PrintList(pdbNode node) // 参数为链表的表头结点
{
pdbNode pnode
if (NULL == node) return
pnode= node->right
while (pnode != node)
{
printf("%d ", pnode->data)
pnode = pnode ->right
}
printf("\n")
}
//将链表反序打印
void ReverPrint(pdbNode node) //参数为链表的表头结点
{
pdbNode pnode
if (NULL == node) return
pnode= node->left
while (pnode != node)
{
printf("%d ", pnode->data)
pnode = pnode->left
}
printf("\n")
}
//删除链表
void DeleteList(pdbNode node) //参数为链表表头结点
{
pdbNode pnode = node->right
pdbNode ptmp
if (NULL == node) return
while (pnode != node)
{
ptmp = pnode->right
free(pnode)
pnode = ptmp
}
free(node)
}
//测试程序
#include <stdio.h>
#include <stdlib.h>
#include "dblist.h"
#define FALSE 0
#define TRUE 1
typedef unsigned int bool
void main()
{
int nChoose
int data
bool bFlag = FALSE
pdbNode pnode
pdbNode list = CreateList(0)
while(bFlag == FALSE)
{
printf("Main Menu\n")
printf("1. Insert\n")
printf("2. Delete Node\n")
printf("3. Find\n")
printf("4. Length\n")
printf("5. Positive Print\n")
printf("6. Negative Print\n")
printf("7. Delete List\n")
printf("0. quit\n\n")
scanf("%d", &nChoose)
switch(nChoose)
{
case 1:
printf("Input the data to insert:")
scanf("%d", &data)
list = InsertNode(list, data)
PrintList(list)
printf("\n")
break
case 2:
printf("Input the data to delete: ")
scanf("%d", &data)
DeleteNode(list, data)
PrintList(list)
printf("\n")
break
case 3:
printf("Input the data to find: ")
scanf("%d", &data)
pnode = FindNode(list, data)
if (NULL != pnode)
{
printf("Find succeed!\n")
printf("\n")
}
else
{
printf("Find failed!\n")
printf("\n")
}
break
case 4:
printf("The list's length is %d\n", GetLength(list))
printf("\n")
break
case 5:
PrintList(list)
printf("\n")
break
case 6:
ReverPrint(list)
printf("\n")
break
case 7:
DeleteList(list)
printf("\n")
break
case 0:
DeleteList(list)
bFlag = TRUE
}
}
}