无序单链表-数据结构课程设计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)写出数据测试表（输入数据/预期结果） 序号 输入数据 预期结果1 1 表为空!2 2 表长为：03 3循环值：4数据：5 2 1 4 最小值结点位置：2最小值是：1当前结点数值为：4交换成功!4 1 表不为空！5 2 表长为：46 4 清除成功!
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); //插入和删除结点的方法163
单链表程序 Node *DeleteAfter(void);};//Node.cpp#include #include "Node.h"
template 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#include"Node.cpp"templateclass LinkedList{ private: 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#include"LinkedList.h" #include#include
template Node*LinkedList::GetNode(const T&item,Node*ptr) //申请结点空间的函数{ Node*newNode=new Node(item);
if(!newNode) //若动态内存申请失败，给出相应的提示并返回空指针 { cerr<<" GetNode: Memoery allocation failed!"< } return newNode; //返回指向新生成结点的指针}template void LinkedList::FreeNode(Node*ptr) //释放结点空间的函数{ if(!ptr) //若ptr为空，则给出相应提示并返回 { cerr<<"FreeNode: invaild node pointer!"< }
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();
}
else { position=0; prevptr=currptr; currptr=currptr->NextNode(); //否则将当前结点的位置设为表尾后 }
return position; //返回新的位置}
template int LinkedList:: Getposition(void)const{ return position;}
template int LinkedList::SetPosition(int pos) //重置当前结点位置的函数{ if(!size) return -1; //若为空，则返回-1 prevptr=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();
}
else { oldNode=prevptr->DeleteAfter(); //删除的是表中的结点
}
if(oldNode==rear) { //删除的是表尾结点，则修改表尾指针和当前结点位置 rear=prevptr; position--; }
currptr=oldNode->NextNode(); //后继结点作为新的当前结点 FreeNode(oldNode); //释放原当前结点 size--; //链表的大小减1}template void LinkedList::DeleteAfter(void) //删除当前结点后继的函数 { Node *oldNode; if(size==0) { cerr<<" DeleteAfter: currptr postion is invalid!"<DeleteAfter(); //保存披删除结点是指针并从链表中删除该结点
if(oldNode==rear) { rear=currptr; //删除的是表尾结点 }
FreeNode(oldNode); //释放披删除结点 size--; //链表大小减1 }templateT LinkedList::GetData(void)const //获取当前结点数据的函数{ if(!size) //若表为空或已到表尾，则给出错误提示并退出
{ cerr<<" Data: currptr node not exist"< return currptr->data;
}
templatevoid LinkedList::SetData(const T& item) //修改当前结点数据的函数{ if(!size) //若表为空或已到表尾，则给出错误 { cerr<<"Data:currptr node not exist"< currptr->data=item; //修改当前结点的值
}
template void LinkedList::Clear(void) //清空链表的函数{ Node *currNode=front, *nextNode;
while(size>1) { 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<<"清除成功!"<template bool LinkedList::IsEmpty(void)const // 判断表是否为空的函数{ if(!size) { cout<<"表为空!"<template void LinkedList::WuXu(int k){ int i=1; int t,p,s; p=Getposition(); //获得当前结点位置 currptr=front; s=Size(); //获取表长 while(iNextNode(); position++; if (k>currptr->data) //k 是否大于当前结点值 { p=position; k=currptr->data; }单链表的删除 i++; } cout<<"最小值结点位置："<NextNode(); DeleteAt(); cout<<"删除成功!"<NextNode();lwfree.cn单链表的删除 SetData(t); cout<<"当前结点数值为："<data<//main.cpp #include #include#include "LinkedList.cpp"
void main(){ LinkedList Wu; //定义对象 int n,k,i,m=1; cout<<"请选择输入："; while(m<6) { cout<<"1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录"<>m; switch(m) //选择输入 { case 1 : Wu.IsEmpty (); break; case 2 : cout<<"表长为："<>n; cout<<"输入数据："; for (i=0;i>k; Wu.InsertAfter(k); //插入结点 } Wu.SetPosition(0); //重置当前结点 Wu.WuXu(Wu.GetData()); //把当前数据做为实参 } break; case 4 : Wu.Clear(); break; default : exit(1); } }}
