单链表实验报告

计算机与信息技术学院综合性、设计性实验报告

一、实验目的

（1）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。

二、实验仪器或设备

（1）硬件设备：CPU为Pentium 4以上的计算机，内存2G以上

（2）配置软件：Microsoft Windows 7与VC++6.0

三、总体设计（设计原理、设计方案及流程等）

设计原理：

单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。

设计方案：

采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。

设计流程：

1.引入所需的头文件；

2.定义状态值；

3.写入顺序表的各种操作的代码；

写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输入值是否非法，从而执行相应的程序

四、实验步骤（包括主要步骤、代码分析等）

#include // EOF(=^Z或F6),NULL

#include // srand( ) ,rand( ),exit(n)

#include // malloc( ),alloc( ),realloc( )等

#include // INT_MAX等

#include

#include

#include // floor(),ceil( ),abs( )

#include // cout,cin

#include // clock( ),CLK_TCK,clock_t

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status; // Status是函数的类型,

//其值是函数结果状态代码，如OK等

typedef int ElemType;

typedef struct LNode

{

ElemType data; //结点的数据域

struct LNode *next; //结点的指针域

}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型

//初始化单链表

算法步骤：

1.生成新结点作为头结点，用头指针L指向头结点。

2.头结点的指针域置空。

Status InitList_L(LinkList &L)

{

L=new LNode; //生成新结点作为头结点，用头指针L指向头结点；

L->next=NULL; //头结点的指针域置空

return OK;

}

//单链表的取值

算法步骤：

1.用指针P指首元结点，用j做计数器初值赋为1.

2.从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空

（NULL），并且没有到达序号为i的结点，则循环执行以下操作：

P指向下一结点；

计数器j相应加1；

3.退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i 大于表长n或i小于等于0），取值失败返回ERROR，否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。

Status GetElem_L(LinkList L, int i, ElemType &e)

{

LinkList p;

int j;

p=L->next;

j=1;

while(p&&j

{

p=p->next;

++j;

}

if(!p||j>i) return ERROR;

e=p->data;

return OK;

}

//单链表的按值查找

算法步骤：

1.用指针p指首元结点。

2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，

并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。

3.返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。int LocateElem_L(LinkList L,ElemType e)

{

LinkList p;

int j;

p=L->next;

j=1;

while(p&&p->data!=e)

{

p=p->next;

j++;

}

if(p) return j;

else return 0;

}

//单链表的插入

算法步骤：

1.查找结点a i-1并由指针p指向该结点。

2.生成一个新结点*s。

3.将新结点*s的数据域置为e。

4.将新结点*s的指针域指向结点a i。

5.将结点*p的指针域指向新结点*s。

Status ListInsert_L(LinkList &L,int i,ElemType e)

{

LinkList p=L,s;

int j=0;

while(p&&(j

{

p=p->next;

++j;

}

if(!p||j>i-1)

{

return ERROR;

}

s=new LNode;