循环链表实验报告

《循环链表实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学牡姓名学牛学号所在地区提交口期(年/月)实践题目假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾(注意不设头指针)，试编写相应的置空队、入队、出队的算法。需求分析：置空setnull(queue)将队列queue置成空队列•入队enqueue(queue,x)将元素x插入队列queue的尾部•出队dequeue(queue)删除队列queue的队头元素，函数返冋被删除元素的值•算法分析，分析时间复杂度概要设计：为了实现上述程序的功能，需要构造…个空队列；实现队列元索的入队功能；实现队列元索的出队功能；队列的输出。在屏幕上显示菜单

2、操作建立空队列函数setnull(queue)；队列元素入队函数enqueue(queue,x)d,队列元素出队函数del()e,队列元素输出函数display()详细设计:typedefintDatatype;typedefstructqueuenode{Datatypedata;structqueuenode*next;JQueueNode;〃以上是结点类型的定义typedefstruct{queuenoderear;}LinkQueue;//只设一个指向队尾元素的指针voidInitQueue(LinkQueue&Q)〃置空队：就是使

3、头结点成为队尾元素Q.rear=(queuenode*)malloc(sizeof(queuenode))QueueNode*s;Q->rear=Q->rear->next;//^队尾指针指向头结点while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队{s=Q->rear->next;Q->rear->next=s->next;free(s);}//M收结点空间}intEmptyQueue(LinkQueue&Q){〃判队空〃当头结点的next指针指向自己时为空队returnQ・>rear・>next・

4、>next==Q・>reai*・>next;}voidEnQueue(LinkQueue&Q,Datatypex){〃入队〃也就是在尾结点处插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//H1请新结点p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p;Q->rear=p;//将尾指针移至新结点}DatatypeDeQueue(LinkQueue&Q,Datatype&x){〃出队，把头结点之后的元素摘下Dataty

5、pet;QueueNode*p;if(EmptyQueue(Q))Error("Queueunderflow");p=Q->rear->next->next;//p指向将要摘下的结点x=p->data;〃保存结点屮数据if(p==Q->rear){//当队列屮只有一个结点时，p结点出队后，要将队尾指针指向头结点Q->rear=Q・>rear・>next;Q・>rear・>next二ponext;}elseQ・>rear・>next・>next=p・>next;/^i®卜结点pfree(p);〃释放被删结点returnx;}调试分析：通过调试

6、分析，我们可以得岀用语句q.front==(q.rear+l)%MAXLEN判断，入队有两种输入方法，队首和队尾。出队要判断队是否为空，用语句q.front=q.rear判断。如果不判断，会影响程序运行，也会使程序结果不完善。设计总结:程序可以运行，结果正确，在实验中是对五个函数的调用，我在实验中更清楚的算法分析:认识到队列跟栈的不同，队列是先进先出，栈是后进先出。但这个程序只有对一个元索的处理，入队、出队、显示，出栈后队列长度为0。进队是通过把新元素插入队尾，出队是输出队头元索。我再次加深了入队要判断栈满，用语句q.front==(q.r

7、ear+l)%MAXLEN判断，入队有两种输入方法，队首和队尾。岀队要判断队是否为空，用语句q.front==q.rear判断。如果不判断，会影响程序运行,也会使程序结果不完善。在定义队列时还要定义队列的最大容量，队头指针始终指向对头前面一个位置，队尾指针始终指向队尾元索，当两者指向一个单元队列则为空。我认为这个实验让我们对队列的性质和应用更加熟悉，了解队列的初始化、入队、出队、显示函数。木题以带头结点循坏链表表示队列，冃只设一个指针指向队尾元索结点，注意不设头指针。队列的先进先出的特征是不变的；队列带头结点，但不设头指针；队列为空的条件；

8、队列是否满受系统的内存可用空间限制。时间复杂度：置成空队列、入队、出队的吋间复杂度都是O(n)。