链表(单链表双向循环)实验报告

数据结构 实验报告

T1223-3-21 余帅 实验一

实验题目： 仅仅做链表部分 难度从上到下

1.双向链表，带表头，线性表常规操作。 2.循环表，带表头，线性表常规操作。 3.单链表，带表头，线性表常规操作。

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 常规操作至少有： 1.数据输入或建立 2.遍历 3.插入 4.删除

必须能多次反复运行 实验主要步骤： 1、 2、

分析、理解给出的示例程序。

调试程序，并设计输入数据，测试程序的如下功能：

1.数据输入或建立 2.遍历 3.插入 4.删除

单链表示意图：

创建

head

head

删除

head

双向循环链表示意图：

创建

程序代码:

//单链表

#include

#include const MAX=5;

enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55}; class node {

public:

int data; node *next; };

class linklist {

private:

node *headp; protected: int count; public:

linklist(); ~linklist(); bool empty(); void clearlist();

returninfo create(void);

returninfo insert(int position,const int &item); returninfo remove(int position) ; returninfo traverse(void); };

linklist::linklist() {

headp = new node; headp->next = NULL; count=0; }

linklist::~linklist() {

clearlist(); delete headp; }

bool linklist::empty() {

if(headp->next==NULL) return true; else

return false; }

void linklist::clearlist() {

node *searchp=headp->next,*followp=headp; while(searchp->next!=NULL) {

followp=searchp;

searchp=searchp->next; delete followp; }

headp->next = NULL; count = 0; }

returninfo linklist::create() {

node *searchp=headp,*newnodep; for(int i=0;i

newnodep = new node;

newnodep->data = defaultdata[i]; newnodep->next = NULL; searchp->next = newnodep; searchp = searchp->next; count++; }

searchp->next = NULL; traverse();

return success; }

returninfo linklist::insert(int position,const int &item) //插入一个结点 {

if(position=count) return range_error;

node *newnodep=new node,*searchp=headp->next,*followp=headp; for(int i=1; i

followp=searchp; searchp=searchp->next; }

newnodep->data=item; //给数据赋值

newnodep->next=followp->next; //注意此处的次序相关性 followp->next=newnodep;

count++; //计数器加一

return success; }

returninfo linklist::remove(int position) //删除一个结点 {

if(empty())

return underflow;

if(position=count+1) return range_error;

node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后

for(int i=1; i

followp=searchp; searchp=searchp->next; }

followp->next=searchp->next; //删除结点的实际语句 delete searchp; //释放该结点 count--; //计数器减一 return success; }

returninfo linklist::traverse(void) {

node *searchp; if(empty())

return underflow; searchp = headp->next;

cout

coutdatanext; }

cout

class interfacebase { public:

linklist listface; //定义一个对象Cskillstudyonface void clearscreen(void); void showmenu(void);

void processmenu(void); };

void interfacebase::clearscreen(void) {

system("cls"); }

void interfacebase::showmenu(void) {

cout

cout

void interfacebase::processmenu(void) {

int returnvalue,item,position; char menuchoice; cin >>menuchoice;

switch(menuchoice) //根据用户的选择进行相应的操作 {

case '1':

returnvalue=listface.create(); if(returnvalue==success)

cout

cout>position;

cout>item;

returnvalue = listface.insert(position,item); if(returnvalue==range_error)

cout

cout

cout>position;

returnvalue = listface.remove(position); if(returnvalue==underflow) cout

else if(returnvalue==range_error)

cout

cout

listface.traverse(); break; case '0':

cout

system("pause"); exit(1); default:

cout

void main() {

interfacebase interfacenow; linklist listnow; system("color f0");

interfacenow.clearscreen(); while(1) {

interfacenow.showmenu(); interfacenow.processmenu(); system("pause");

interfacenow.clearscreen(); } }

/* 功能：用双向循环链表存储数据 1.创建链表 2.增加结点

3.删除结点 4.遍历链表 制作人：余帅 内容：239行 */

#include #include const MAX=5;

enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55}; class node {

public:

int data;

node * next; //指向后续节点 node * pre; //指向前面的节点 };

class linklist {

private:

node *headp; protected: int count; public:

linklist(); ~linklist(); bool empty(); void clearlist();

returninfo create(void);

returninfo insert(int position,const int &item); returninfo remove(int position) ; returninfo traverse(void); };

linklist::linklist() {

headp = new node; headp->next = NULL; headp->pre = NULL; count=0; }

linklist::~linklist() {

clearlist();

delete headp;

}

bool linklist::empty()

{

if(headp->next==NULL)

return true;

else

return false;

}

void linklist::clearlist()

{

node *searchp=headp->next,*followp=headp;

while(searchp->next!=NULL)

{

followp=searchp;

searchp=searchp->next;

delete followp;

}

headp->next = NULL;

headp->pre = NULL;

count = 0;

}

returninfo linklist::create()

{

node *searchp=headp,*newnodep;

for(int i=0;i

{

newnodep = new node;

newnodep->data = defaultdata[i];

newnodep->next = NULL;

searchp->next = newnodep;

newnodep->pre = searchp;

searchp = searchp->next;

count++;

}

searchp->next = headp;

headp->pre = searchp;

traverse();

return success;

}

returninfo linklist::insert(int position,const int &item) //插入一个结点

{

if(positioncount+1)

return range_error;

node *newnodep=new node;

node *searchp=headp->next,*followp=headp;

for(int i=1; i

{

followp=searchp;

searchp=searchp->next;

}

newnodep->data=item; //给数据赋值

newnodep->next = searchp;

searchp->pre = newnodep;

followp->next = newnodep;

newnodep->pre = followp;

count++; //计数器加一

return success;

}

returninfo linklist::remove(int position) //删除一个结点 {

if(empty())

return underflow;

if(position=count+1)

return range_error;

node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后

for(int i=1; i

{

followp=searchp;

searchp=searchp->next;

}

followp->next=searchp->next; //删除结点的实际语句 searchp->next->pre = followp;

delete searchp; //释放该结点

count--; //计数器减一

return success;

}

returninfo linklist::traverse(void)

{

node *searchp1,*searchp2;

if(empty())

return underflow;

searchp1 = headp;

searchp2 = headp;

cout

cout

while (searchp1->next!=headp ) {

searchp1 = searchp1 ->next;

cout data

}

cout

cout

while (searchp2->pre!=headp ) {

searchp2 = searchp2 ->pre;

cout data

}

cout

return success;

}

class interfacebase

{

public:

linklist listface; //定义一个对象Cskillstudyonface

void clearscreen(void);

void showmenu(void);

void processmenu(void);

};

void interfacebase::clearscreen(void)

{

system("cls");

}

void interfacebase::showmenu(void)

{

cout

cout

cout

cout

cout

cout

cout

cout

cout

}

void interfacebase::processmenu(void)

{

int returnvalue,item,position;

char menuchoice;

cin >>menuchoice;

switch(menuchoice) //根据用户的选择进行相应的操作

{

case '1':

returnvalue=listface.create();

if(returnvalue==success)

cout

break;

case '2':

cout

cin>>position;

cout

cin>>item;

returnvalue = listface.insert(position,item);

if(returnvalue==range_error)

cout

else

cout

break;

case '3':

cout

cin>>position;

returnvalue = listface.remove(position);

if(returnvalue==underflow)

cout

else if(returnvalue==range_error)

cout

else

cout

break;

case '4':

listface.traverse();

break;

case '0':

cout

用!!!"

system("pause");

exit(1);

default:

cout

}

}

void main()

{

interfacebase interfacenow;

linklist listnow;

system("color f0");

interfacenow.clearscreen();

while(1)

{

interfacenow.showmenu();

interfacenow.processmenu();

system("pause");

interfacenow.clearscreen();

}

}

运行结果：

1.创建链表：

2.增加结点

3．删除结点

心得体会：

本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。

通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得硬件基础语言。在这次课程设计中，虽然不会成功的编写一个完整的程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题和在老师的帮助下一步一步慢慢的正确运行程序，终于完成了这次课程设计，虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的

学习。

致谢：

马老师、付老师