c++语言用链表实现循环队列？

一、c++语言用链表实现循环队列？

循环队列：

1.循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%maxSize。（我曾经想过为什么不用一个length表示队长，当length==maxSize时队满）原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。

2.用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

1 template<class T>

2 class SeqQueue{

3 protected:

4 T *element;

5 int front,rear;

6 int maxSize;

7 public:

8 SeqQueue(int sz=10){

9 front=rear=0;

10 maxSize=sz;

11 element=new T[maxSize];

12 }

13 ~SeqQueue(){

14 delete[] element;

15 }

16 bool EnQueue(const T& x){//入队

17 if(isFull()) return false;

18 element[rear]=x;

19 rear=(rear+1)%maxSize;

20 return true;

21 }

22 bool DeQueue(T& x){//出队

23 if(isEmpty()) return false;

24 x=element[front];

25 front=(front+1)%maxSize;

26 return true;

27 }

28 bool getFront(T& x){//获取队首元素

29 if(isEmpty()) return false;

30 x=element[front];

31 return true;

32 }

33 void makeEmpty(){//队列置空

34 front=rear=0;

35 }

36 bool isEmpty()const{//判断队列是否为空

37 return (rear==front)?true:false;

38 }

39 bool isFull()const{//队列是否为满

40 return ((rear+1)%maxSize==front)?true:false;

41 }

42 int getSize()const{

43 return (rear-front+maxSize)%maxSize;

44 }

45 };

测试代码如下：

1 void menu(){

2 cout<<"1.入队"<<endl;

3 cout<<"2.获取队首元素"<<endl;

4 cout<<"3.出队"<<endl;

5 cout<<"4.队列置空"<<endl;

6 cout<<"5.获取队中元素数量"<<endl;

7 cout<<"6.退出"<<endl;

8 }

9

10 void function(int num,SeqQueue<int> *sq){

11 switch(num){

12 int x;

13 case 1:

14 cin>>x;

15 sq->EnQueue(x);

16 break;

17 case 2:

18 sq->getFront(x);

19 cout<<x<<endl;

20 break;

21 case 3:

22 sq->DeQueue(x);

23 break;

24 case 4:

25 sq->makeEmpty();

26 break;

27 case 5:

28 x=sq->getSize();

29 cout<<x<<endl;

30 break;

31 default:

32 exit(1);

33 }

34 }

35 int main(int argc, char** argv) {

36 SeqQueue<int> *sq=new SeqQueue<int>;

37 int num;

38 while(true){

39 menu();

40 cin>>num;

41 function(num,sq);

42 }

43 delete sq;

44 return 0;

45 }

之后是链式队列，实现类代码和测试代码如下：

1 #include <iostream>

2 using namespace std;

3 template<class T>

4 struct LinkNode{

5 T data;

6 LinkNode<T> *link;

7 LinkNode(T& x,LinkNode<T> *l=NULL){

8 data=x;

9 link=l;

10 }

11 };

12 template<class T>

13 class LinkedQueue{

14 protected:

15 LinkNode<T> *front,*rear;

16 public:

17 LinkedQueue(){

18 front=rear=NULL;

19 }

20 ~LinkedQueue(){

21 makeEmpty();

22 }

23 bool enQueue(T& x){

24 if(front==NULL)

25 front=rear=new LinkNode<T>(x);

26 else{

27 rear=rear->link=new LinkNode<T>(x);

28 }

29 return true;

30 }

31 bool deQueue(T& x){

32 if(isEmpty()) return false;

33 LinkNode<T> *p=front;

34 x=front->data;

35 front=front->link;

36 delete p;

37 return true;

38 }

39 bool getFront(T& x)const{

40 if(isEmpty()) return false;

41 x=front->data;

42 return true;

43 }

44 void makeEmpty(){

45 LinkNode<T> *p;

46 while(front!=NULL){

47 p=front;

48 front=front->link;

49 delete p;

50 }

51 }

52 bool isEmpty()const{

53 return (front==NULL)?true:false;

54 }

55 int getSize()const{

56 LinkNode<T> *p;

57 int count=0;

58 p=front;

59 while(p!=NULL){

60 count++;

61 p=p->link;

62 }

63 return count;

64 }

65 };

66 void menu(){

67 cout<<"1.入队"<<endl;

68 cout<<"2.获取队首元素"<<endl;

69 cout<<"3.出队"<<endl;

70 cout<<"4.队列置空"<<endl;

71 cout<<"5.获取队中元素数量"<<endl;

72 cout<<"6.退出"<<endl;

73 }

74

75 void function(int num,LinkedQueue<int> *lq){

76 switch(num){

77 int x;

78 case 1:

79 cin>>x;

80 lq->enQueue(x);

81 break;

82 case 2:

83 lq->getFront(x);

84 cout<<x<<endl;

85 break;

86 case 3:

87 lq->deQueue(x);

88 break;

89 case 4:

90 lq->makeEmpty();

91 break;

92 case 5:

93 x=lq->getSize();

94 cout<<x<<endl;

95 break;

96 default:

97 exit(1);

98 }

99 }

100 int main(int argc, char** argv) {

101 LinkedQueue<int> *lq=new LinkedQueue<int>;

102 int num;

103 while(true){

104 menu();

105 cin>>num;

106 function(num,lq);

107 }

108 delete lq;

109 return 0;

110 }

二、线性链表和循环链表的区别？

线性表顺序存储结构：用数组（连续存放的）来存储的线性表就是顺序表；

线性表链式存储结构: 存储在链表上:单链表，双链表，循环链表. 栈和队列：只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；栈和队列的实现可以用顺序存储结构或链式存储结构。

当线性表需要频繁查找，较少插入和删除时，宜采用顺序存储结构。若需要频繁插入和删除，宜采用单链表

三、循环链表是什么？

循环链表是一种特殊的链表，其中最后一个节点指向第一个节点，形成一个环状结构。与普通链表不同的是，循环链表可以通过任意节点开始遍历整个链表。

这种特性使得循环链表可以在一些特定的应用场景中非常有用，例如循环队列和循环赛制。循环链表可以通过在链表的尾部节点指向头部节点的方式来实现。

四、如何判断循环链表？

最优的时间复杂度，两个指针，一个快一个慢，如果遇到了就是环形。

public boolean isLoop(Node head){

Node slow = head;

Node fast = head;

while(fast!=null && fast.next!=null)

(slow = slow.next;fast = fast.next.next;

if(slow==fast)

return true;

}

return false;

五、单链表和循环单链表，链表为空的条件分别是？

判断是否有循环的方法：

对于任意一个节点，判断其next值是否和之前的任意节点地址相同。如果存在相同，说明有循环。

链表为空：

带头单链表：head->next==NULL

不带头单链表：list==NULL

带头循环链表:head->next==head

不带头循环链表：list==NULL

六、单链表，循环链表，双向链表，为空时都是怎么表示的？

这个是计算机考试公共基础的内容吧！在线性单链表中，每一个节点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。

因此在单链表中只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种方式下，由某一个节点出发。只能找到他的后件，而为了找到他的前件必须从头开始找！未了弥补单链表这个缺点，我们采用双向链表，它的每个节点设有两个指针，左指针和右指针，左指针指向前件，右指针指向后件。循环链表相比前面的单链表有两个特点：增加了一个表头指针：链表最后一个节点的指针域不是空，而是指向表头结点，这就形成循环了！再循环链表中，只要指出表中任意一个结点的位置，就可以从它出发访问表中其他所有的结点，耳线性链表做不到这一点。以上介绍了他们的特点，插入和删除运算就是利用栈来进行，而首先就是查找指定元素，以上三个查找上的不同决定了插入和删除的效率。此外循环链表和单链表的插入删除基本一样，都是一个指针，就是查找指定元素时方式不一！！！ 希望可以帮到你！！！

七、循环链表和双向链表的区别是是什么？

单向链表或者单链表 单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向表中的下一个节点，而最后一个节点则指向一个空值NULL。

单向链表只可向一个方向遍历。 查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。也可以提前把一个节点的位置另外保存起来，然后直接访问。 双向链表,也叫双链表 双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。第一个节点的"前连接"指向NULL，最后一个节点的"后连接"指向NULL。

这样可以从任何一个节点访问前一个节点，也可以访问后一个节点，以至整个链表。

一般是在需要大批量的另外储存数据在链表中的位置的时候用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。

这时候就要修改指向首个节点的指针。

有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个循环链表。

这个虚拟节点之后的节点就是真正的第一个节点。

这种情况通常可以用这个虚拟节点直接表示这个链表。 循环链表 在一个循环链表中, 首节点和末节点被连接在一起。

这种方式在单向和双向链表中皆可实现。

要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。

循环链表可以被视为"无头无尾"。 循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。

对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工跳转到第一个节点。访问到第一个节点之前的时候也一样。

这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

八、单循环链表的主要优点？

循环链表的主要优点是：

循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。 (1)单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。 (2)多重链的循环链表——将表中结点链在多个环上。

九、C语言二级考试循环链表是循环队列的链式存储结构？

循环队列本身是一种顺序存储结构，而循环列表是一种链式存储结构。两者之间是平级关系。（用于解释第一句话的错误原因。）

线性链表是线性表的链式存储结构，包括单链表，双链表，循环链表等。（补充说明）

队列的顺序存储结构一般采用循环队列的形式。（用于解释第二句话的正确原因。）

十、c 链表学生管理系统

链表是计算机科学中一种常用的数据结构，它的应用非常广泛。例如，在学生管理系统中，链表可以用来有效地存储和管理学生的信息。

什么是链表

链表是由一系列节点组成的数据结构，每个节点包含两部分内容：数据和指向下一个节点的指针。相比数组，链表可以动态地分配内存空间，具有更高的灵活性。

在学生管理系统中，我们可以使用链表来存储学生的信息。每个节点就代表一个学生，包含学生的姓名、学号、年龄等相关信息。通过节点之间的指针，我们可以轻松地遍历整个链表，查找特定的学生信息。

链表的优点

使用链表来实现学生管理系统有以下几个优点：

• 灵活性高：链表可以动态调整长度，可以轻松地插入、删除和修改学生信息。
• 存储效率高：链表只存储实际使用的内存空间，节省了存储空间。
• 数据结构清晰：每个节点都包含了学生的所有信息，方便查找和更新。

链表的实现

链表的实现主要包括两个方面：节点的定义和链表的操作。

节点的定义如下：

typedef struct StudentNode { char name[100]; int id; int age; struct StudentNode *next; } StudentNode;

其中，name、id和age分别表示学生的姓名、学号和年龄。next是指向下一个节点的指针。

链表的操作包括添加节点、删除节点、查找节点等。

链表的应用

学生管理系统可以通过链表来实现学生信息的增加、删除、修改和查找。

添加学生信息时，可以在链表的末尾添加一个新节点，将新节点的指针设置为NULL；删除学生信息时，可以通过遍历链表找到要删除的节点，并修改前一个节点的指针；修改学生信息时，可以根据学号定位到具体的节点，并修改节点的数据；查找学生信息时，可以通过遍历链表查找匹配的节点。

通过链表实现学生管理系统，可以方便地对学生信息进行增删改查，提高了系统的效率和灵活性。

总结

链表是一种重要的数据结构，特别适合在学生管理系统中使用。它可以有效地存储和管理学生的信息，具有灵活性高、存储效率高等优点。通过合理地定义节点和操作链表，就可以实现一个高效的学生管理系统。