资源描述
数据结构实 验 报 告 成绩_学号1217417007姓名严梦授课教师黄欣专业12信计实验报告递交日期2014.10.28实验题目用带头结点的循环单链表表示队列，并且只设置一个尾指针。编制程序完成队列操作。1 需求分析1.程序的实现功能：编写函数：(1) 建立循环队列，返回尾指针函数 linkqueue *create( )(2) X入队，返回尾指针函数 linkqueue * enqueue(linkqueue *rear,int x)(3) 出队返回队头元素函数 linkqueue * outqueue(linkqueue *rear)(4)显示队列元素函数 void list(linkqueue *rear)(5)删除队列函数 linkqueue * del(linkqueue *rear)(6)主函数完成功能：a). 调用 rear=creat( ) ; b). 调用 list(rear); c). 输入x值； d). 调用 enqueue(rear,x); e). 调用 list(rear); f). 调用 outqueue(rear)g).调用 list(rear); h) 调用 del(rear) i) list(rear).2数据输入的内容输入形式与范围 输入所创建的循环队列中的数据，以及要插入的x的值，其类型是整型数；输入数据以回车符相隔，以0为输入结束符。3数据输出的内容与形式 输出创建循环队列时队列数据，插入x后的队列中数据和出队之后队列的数据， 数据以“%3d”相隔。二. 主要算法的算法思想.1创建循环队列：用尾插法建立循环队列，每个新插入的结点都作为队列的最后一个结点。读入结点的数值，生成的新结点插入队尾。再把新结点的指针域指向头结点，然后返回尾指针函数。2. 显示队列元素的函数：从rear的第一个结点开始往后依次输出结点数据。3. 插入值为x的结点到rear的队头函数：生成值为x的结点*p在*rear之后，把*p的指针域指向头结点，*p作为*rear的后继。4. 出队返回队头元素函数： 保留头结点的位置，h是头结点，指针p指向队头元素，把队头元素的后继作为头结点的后继，释放p。即删除队头元素。4. 释放单链表rear结点空间函数:尾指针的后继是头结点，头结点就是尾结点，相当于将队列置空。5. 主函数:先申明函数首部，设置尾指针；依次调用创建队列函数、显示队列函数；输入x值，调用入队函数、显示队列函数，调用出队函数、显示队列函数和释放队列函数，调用显示队列函数。三. 设计：1线性表存储结构：链式存储。链表结点类型定义：typedef struct node int data; struct node *next; linklist; /*单链表结点类型*/2参数表（列出所有的符号常量与全局变量）参数名数据传递方式数据内容传递所属函数NULL符号常量宏定义0所有函数3 函数间的调用关系图4列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等1)创建单链表函数函数首部：linkqueue *creat( ) 形参：rear队列尾指针 函数作用：创建存放原始数据的队列 函数值：无 局部变量 rear：作为尾指针，指向生成的队列的尾结点 new：结点类型指针，指向新结点。 h:作为头指针，指向头结点。 输入一个结点算法主要步骤：(a) 开辟新结点空间news指向 news=(linklist *)malloc(sizeof(linklist);(b) 新结点*new插入队尾 rear-next=news;(c) 给新结点赋值x news-data=x; (d) 尾指针rear指向新的表尾 rear=news; (e) 读入下一个结点的值 scanf(“%d”,&x);getchar(); 输入链表结点循环条件： while(x !=0)输入结点数据结束后，尾指针指向头结点 rear-next=h; 2）输出循环队列函数 函数首部：void list(linkqueue *rear) 形参：rear :循环队列尾指针 函数作用：将单链表输出在窗口上 函数值：无 局部变量 指针p：指向队头元素 指针h：尾结点的后继是头结点，指向头结点。 算法主要步骤： 判断是否为空链表： (a)若空，则输出“this is an empty listqueue!” if(rear = h)printf(n empty list);return; (b)若不为空，则依次输出每一个结点数据 while(p != rear ) printf(%3dp-data); p=p-next; 3). 入队函数 函数首部：void enqueue(linkqueue *rear, datatype x) 形参：rear:队列尾指针； x: 插入结点的值。 函数作用：将值为x的结点插在队列的队尾。 函数值：无局部变量： 指针p：指向新结点；指针rear：是队列的尾指针指针h:是头指针算法主要步骤：(a) 开辟新结点p p=(linkqueue*)malloc(sizeof(linkqueue)(b) 为*p赋值 p-data=x(c) 将*p作为*rear的后继 rear-next=p(d) 指针指向下一个结点 rear=p4). 出队函数 函数首部：linkqueue * outqueue(linkqueue *rear) 形参：rear: 队列尾指针。 函数作用：将队头元素删除。 函数值：无局部变量： 指针p：指向队头元素；指针rear：队列的尾指针指针h：尾结点的后继是头结点，指向头结点。算法主要步骤：(a) *p指向队头元素的位置 p=rear-next-next (b)*h指向头结点 h = rear-next (c) 删除队头结点，将第二个结点作为*h的后继 h-next=p-next; 5）释放函数： 函数首部：linkqueue * del(linkqueue *rear) 形参：rear：队列尾指针 函数作用：释放删除循环队列 函数值：无 局部变量： 指针 h：指向头结点指针 rear：队列尾指针算法主要步骤：(a) 尾指针的后继是其本身，将队列置空。 h = rear-next; rear = h； rear-next = h; 四. 调试分析：1调试中出现的问题，解决的办法 1）没有把头结点表示出来，不知道把尾指针的指针域指向头结点怎么表示 2）写list函数时，没有注意到循环队列，陷入死循环。2每个函数的时、空复杂性分析 1）linkqueue * create()建单链表函数 T(n)=O(n)， S(n)=O(n); 2）linkqueue * enqueue(linkqueue *rear,int x) 输出队列函数 T(n)=O(1), S(n)=O(1); 3). linkqueue * outqueue(linkqueue *rear) 入队函数 T(n)=O(1) , S(n)=O(1); 4). void list(linkqueue *rear) 出队函数 T(n)=O(n) , S(n)=O(1); 5).linkqueue * del(linkqueue *rear) 删除队列 T(n)=O(1) , S(n)=O(1); 6). Int main() 主函数 T(n)=O(n) ， S(n)=O(n).3改进设想，经验体会 现在只能入队一个数，可以设置成想依次入队几个数。 五. 使用说明：如何使用你编制的程序、操作步骤. 编译程序成功后，按界面提示输入单链表结点数据与值x。六. 测试结果：输入输出数据内容：窗口显示如下：(下划线部分为输入部分，其余为输出部分)测试数据一：creat a linkqueue:type 0 to endinput the value of node= 1input the value of node= 2input the value of node= 34input the value of node= 5input the value of node= 0list the linkqueue: 1 2 34 5input x=6list the enqueue linkqueue: 1 2 34 5 6list the outqueue linkqueue:2 34 5 6delete the listqueue.This is an empty listqueue!测试数据二：creat a linklist:type 0 to endinput the value of node= 0This is an empty listqueue! 7 源代码清单#include #include typedef struct nodeint data;struct node *next;linkqueue;int main()linkqueue * create();linkqueue * enqueue(linkqueue *rear,int x);linkqueue * outqueue(linkqueue *rear);void list(linkqueue *rear);linkqueue * del(linkqueue *rear);linkqueue * rear;int x;printf(create a linkqueue:n);rear = create(); printf(list the linkqueue:n);list(rear);printf(n input x= );scanf(%d,&x);getchar();printf(nlist the enqueue linkqueue:);rear = enqueue(rear,x);list(rear);printf(nlist the outqueue linkqueue:);rear = outqueue(rear);list(rear);printf(n delete the listqueue.); rear = del(rear);list(rear);linkqueue * create()linkqueue *news,*rear,*h;int x;h = (linkqueue*)malloc(sizeof(linkqueue);rear = h;printf(type0 to endn);printf(input the value of node=);scanf(%d,&x);getchar(); while( x != 0 ) news = (linkqueue*)malloc(sizeof(linkqueue); news-data = x; rear-next = news; rear = news; printf(input the value of node=);scanf(%d,&x);getchar();rear-next = h;return rear;void list(linkqueue *rear)linkqueue *p,*h;h = rear-next;p = h-next;if(rear = h)printf(This is an empty listqueue!n);elsewhile(p != rear )printf(%3d,p-data);p = p-next;printf(%3d,p-data);linkqueue * enqueue(linkqueue *rear,int x)linkqueue *p,*h;h = rear-next;p = (linkqueue*)malloc(sizeof(linkqueue);p-data = x;p-next = h;rear-next = p;rear = p;return rear;linkqueue * outqueue(linkqueue *rear)linkqueue *p,*h;h = rear-next;p = rear-next-next;h-next = p-next;free(p);return rear;linkqueue * del(linkqueue *rear)linkqueue *h;h = rear-next;rear = h;rear-next = h;return rear; 源代码共 行
展开阅读全文