无序单链表数据结构课程设计.doc

无序单链表-数据结构课程设计-课程设计无序单链表-数据结构课程设计1. 课程设计目的及要求1）、建立一个由正整数组成的无序单链表，编写算法实现下列功能：找出最小值结点，且显示该数值；若该数值为奇数，则将其与直接后继结点的数值交换。若为偶数，则将其直接后继结点删除。2）、找出最小值结点，且显示该数值；值为奇数，将其与直接后继结点的数值交换；为偶数，将其直接后继结点删除。3）、windos XP 、1G 内存2. 课程设计步骤1)构造基本类2).确定类中的各函数功能；3).实现类中的各成员函数；4).输入程序代码，对其进行测试，对错误进行修改；5).测试成功，完善代码，多次对其修改，求得最精简代码；6).认真填写设计报告。3. 课程设计内容1）、设计概述(a) 开发平台：VC6.0(b) 参考书籍： 数据结构 C+ 教材(c) 开发周期： 3天（1天构思+雏形、1天修改、1天再修改、待完善）2）、处理流程(a)画出功能结构图 选择 4 选择 5 选择 1 选择 2 选择 3(b)画出类图class Node数据成员public T data/数据域成员函数public Node *NextNode(void) const public void InsertAfter(Node *p)public Node *DeleteAfter(void)/获取下一个结点/插入结点/删除结点class LinkedList数据成员private int size private int positionpublic T data/表中结点数/当前结点位置成员函数public int Size(void)constpublic int SetPosition(int pos)public int NextNode(void)public void InsertAfter(const T&item)public void DeleteAfter(void)public T GetData(void)constpublic void SetData(const T& item)public bool IsEmpty(void)constpublic void Clear(void)public void WuXu(int k)/获取表长/重定位当前结点(c)主要函数的程序流程图 选择1 选择2 选择 3 选择 4 选择 5(d)写出数据测试表（输入数据/预期结果） 序号输入数据预期结果11表为空!22表长为：033循环值：4数据：5 2 1 4 最小值结点位置：2最小值是：1当前结点数值为：4交换成功!41表不为空！52表长为：464清除成功!4. 课程设计结果运行正确 运行结果如下：请选择输入：1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录1表为空!1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录2表长为：01) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录3输入无序组的个数：4输入数据：5214最小值结点位置：2最小值是：1当前结点数值为：4交换成功!1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录4清除成功!1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录5. 课程设计总结分析1)、程序的优点：能够循环2)、遇到的问题：不能很好的把握循环值，导致程序出错3)、存在的缺陷：比较复杂烦琐4)、自我评价：很认真的完成课程设计，在老师和同学们的指点下完成了课程设计，也从中学到更多的知识，也对链表的应用有了更好的认识6. 附录（源程序清单，要求含有30%的注释）/Node.h#include #includetemplate class Node private: Node * next; /next 为指向下一个结点的指针 public: T data; /定义数据域 Data Node (const T& item,Node * ptr=NULL); /构造函数和析构函数 Node(void); Node *NextNode(void) const; /获取下一个结点指针的方法 void InsertAfter(Node *p); /插入和删除结点的方法163Node *DeleteAfter(void);/Node.cpp#include #include Node.htemplate Node:Node(const T& item,Node *ptr):data(item),next(ptr)template Node:Node(void)template Node * Node:NextNode(void) const return next;template void Node:InsertAfter(Node *p)p-next=next; /将当前结点的后继结点链接到结点 p 之后next=p; /将结点 p 作为当前结点的后继结点template Node * Node:DeleteAfter(void) Node *ptr=next; /保存当前结点的后继结点 if(ptr=NULL) return NULL; /若没有后继结点，则返回空指针 next=ptr-next; /当前结点指向其原来的后继的后继，即 ptr 的后继 return ptr; /返回指向被删除结点的指针/链表类的定义#ifndef LINKEDLIST_H#define LINKEDLIST_H#includeNode.cpptemplateclass LinkedListprivate:Node *front,*rear; /定义指向头指针和指向尾指针Node *prevptr,*currptr; /用于访问数据、插入和删除结点指针int size; /表中的结点数int position; /表中当前结点位置计数Node*GetNode(const T& item,Node*ptr=NULL); /申请结点的函数 void FreeNode(Node*p); /释放结点的函数public:LinkedList(void); /构造函数LinkedList(void); /析构函数int Size(void)const; /取表中结点大小的函数int SetPosition(int pos); /重定位当前结点的函数 int Getposition(void)const; /取当前结点位置的函数int NextNode(void); /将后继结点设置为当前结点的函数int InsertAt(const T&item);/在当前结点处插入新结点的函数void InsertAfter(const T&item); /在当前结点后插入新结点的函数void DeleteAt(void); / 删除当前结点的函数 void DeleteAfter(void); /删除当前结点后继的函数T GetData(void)const; /获取当前结点数据的函数 void SetData(const T& item); /修改当前结点数据的函数bool IsEmpty(void)const;/判断链表是否为空的函数 void Clear(void); /清空链表的函数void WuXu(int k); /显示最小值;# endif/ 链表的类的实现文件 LinkedList.cpp#includeLinkedList.h#include#includetemplate Node*LinkedList:GetNode(const T&item,Node*ptr) /申请结点空间的函数Node*newNode=new Node(item); if(!newNode) /若动态内存申请失败，给出相应的提示并返回空指针cerr GetNode: Memoery allocation failed!endl;return NULL; return newNode; /返回指向新生成结点的指针template void LinkedList:FreeNode(Node*ptr) /释放结点空间的函数if(!ptr) /若ptr为空，则给出相应提示并返回cerrFreeNode: invaild node pointer!endl;return ;delete ptr;/释放结点占用的内存空间template LinkedList: LinkedList(void)/建立一个空链表front=NULL;rear=NULL;prevptr=NULL;currptr=NULL;size=0;position=-1;template LinkedList:LinkedList(void) /析构函数Clear(); /清空链表，释放所有的结点的内存空间template int LinkedList:Size(void)const / 取连表的大小的函数return size;templateint LinkedList:NextNode(void) /将当后继结点设置为当前结点的函数if(position=0&positionNextNode();elseposition=0;prevptr=currptr; currptr=currptr-NextNode(); /否则将当前结点的位置设为表尾后return position; /返回新的位置template int LinkedList: Getposition(void)constreturn position;template int LinkedList:SetPosition(int pos) /重置当前结点位置的函数if(!size) return -1; /若为空，则返回-1prevptr=NULL; /寻找对应结点currptr=front;position=0;for(int k=0;kNextNode(); /返回当前结点位置return position;template int LinkedList:InsertAt(const T&item) /在当前结点处插入新的结点的函数 Node L*newNode; if(!size) /在空表中插入 newNode=GetNode(item,front); front=rear=newNode; postion=0; else if(!prevptr) /在表头结点插入 newNode=GetNode(item,front); front=newNode; else /在表中间位置插入 newNode=GetNode(item, currptr); prevptr-InsertAfter(newNode); size+; /增加链表的长度 currptr=newNode;/新插入的结点作为当前结点单链表的删除template void LinkedList:InsertAfter(const T& item) /在当前结点后插入新的结点的函数Node*newNode; if(!size) /在空表中插入 newNode=GetNode(item); front=rear=newNode; position=0; else if(currptr=rear|!currptr) /在表尾结点后插入newNode=GetNode(item); rear-InsertAfter(newNode); prevptr=rear; rear=newNode; position=size; else /在链表的中间位置插入 newNode=GetNode(item, currptr-NextNode(); currptr-InsertAfter(newNode); prevptr=currptr; position+; size+; /增加表的长度 currptr=newNode; /将插入的新结点作为当前结点template void LinkedList:DeleteAt(void) /删除当前结点的函数Node*oldNode;if(!prevptr)/删除的是表头结点oldNode=front;front=currptr-NextNode();elseoldNode=prevptr-DeleteAfter(); /删除的是表中的结点 if(oldNode=rear) /删除的是表尾结点，则修改表尾指针和当前结点位置rear=prevptr;position-; currptr=oldNode-NextNode(); /后继结点作为新的当前结点FreeNode(oldNode); /释放原当前结点size-; /链表的大小减1template void LinkedList:DeleteAfter(void) /删除当前结点后继的函数 Node *oldNode;if(size=0) cerr DeleteAfter: currptr postion is invalid!DeleteAfter(); /保存披删除结点是指针并从链表中删除该结点 if(oldNode=rear) rear=currptr;/删除的是表尾结点 FreeNode(oldNode); /释放披删除结点size-; /链表大小减1templateT LinkedList:GetData(void)const /获取当前结点数据的函数 if(!size) /若表为空或已到表尾，则给出错误提示并退出cerr Data: currptr node not existdata;templatevoid LinkedList:SetData(const T& item) /修改当前结点数据的函数if(!size) /若表为空或已到表尾，则给出错误cerrData:currptr node not existdata=item; /修改当前结点的值 template void LinkedList:Clear(void) /清空链表的函数Node *currNode=front, *nextNode;while(size1)nextNode=currNode-NextNode(); /保存后继结点指针FreeNode(currNode); /释放当前结点front=currNode=nextNode; /原后继结点成为当前结点size-; if(size=1)FreeNode(currNode); size-;front=rear=prevptr=currptr=NULL; /修改空链表数据size=0;position=-1;cout清除成功!endl;template bool LinkedList:IsEmpty(void)const / 判断表是否为空的函数if(!size) cout表为空!endl; return false;elsecout表不为空!endl; return true; template void LinkedList:WuXu(int k) int i=1; int t,p,s; p=Getposition(); /获得当前结点位置 currptr=front; s=Size(); /获取表长 while(iNextNode();position+;if (kcurrptr-data) /k 是否大于当前结点值 p=position; k=cur