选课时间段：  星期四           

序      号：                   

杭州电子科技大学信息工程学院

实验报告

课程名称：     数据结构          

实验名称：单链表插入、删除和修改    

指导教师：              

学生姓名：                     

学生学号：               

实验日期：  2009      

一、实验目的

1．理解数据结构中带头结点单链表的定义和逻辑图表示方法。

2．掌握单链表中结点结构的JAVA描述。

3．熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现。

4．熟练掌握简单的演示菜单与人机交互设计方法。

二、实验内容

1． 编制一个演示单链表插入、删除、查找等操作的程序。

三、实验步骤

1．需求分析

本演示程序用JAVA编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。

① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。

② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
　　③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。

④ 测试数据：

　A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表
　　　B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
　　　C． 删除操作中依次输入2，5，删除位于2和5的元素

2．概要设计

1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
　　ADT LinkList {
　　　数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
　　　数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}
　　　基本操作：
 （1）insert

初始化状态：单链表可以不为空集；操作结果：插入一个空的单链表L。
　    （2）decelt
　　　　操作结果：删除已有的单链表的某些结点。

（3）display
　　　　操作结果：将上述输入的元素进行排列显示。
　　　（4）modify
　　　　操作结果：将上述输入的某些元素进行修改。
　　　（5）save
　　　  操作结果：对上述所有元素进行保存。
　　　（6）load
　　　　操作结果：对上述元素进行重新装载。
　　}

　　2）本程序包含7个函数：
　　① 主函数main()
　　② 保存单链表函数save()
　　③ 重载操作菜单函数load()
　　④ 显示单链表内容函数display ()
　　⑤ 插入元素函数insert ()
　　⑥ 删除元素函数decelt ()
　　⑦ 修改元素函数modify()

　　各函数间关系如下：

3．详细设计

　　实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
　　1) 结点类型和指针类型
　　typedef struct node {
　　　int data;
　　　struct node *next;
　　}Node,*singleLIST.java;

　　2) 单链表的基本操作

　　为了方便，在单链表中设头结点，其data域没有意义。

bool insert(singleLIST) （伪码算法）
　　bool modify(singleLIST) （伪码算法）
　　void delect(singleLIST)
　　（伪码算法）
　　void display()
　　（伪码算法）
    3) 其他模块伪码算法

4．调试分析
　　(略)

5．使用说明

程序名为，运行环境为Windows。程序执行后显示
　　========================
　　0----EXIT
　　1----INSERT
　　2----DELETE
　　3----DISPLAY

4----MODIFY

5----EXIST

=======================
　　SELECT:

　　在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。

选择5：退出程序
　　选择1：显示“INSERT =” ，
　　要求输入要插入的位置和元素的值（都是整数）。
　　选择2：显示“DELETE =” ，
　　要求输入要删除元素的位置，执行成功后返回元素的值。

　　选择3：显示“MODIFY = ” ，

选择要修改的对象，执行成功后返回新的元素值。

选择4：显示“DIAPLAY= ”
　　显示所有单链表中的元素，自动进行排序。

6．测试结果

   

要查找到第i个节点，要让单链表先遍历一下，先找到第i-1个节点，然后找到delect的地方将代码修改一下

接着将下面的代码修改如下：prev.data=prev.next.next;

prev.next=prev.next.next;

1） 建立单链表：
　　　» 选择1，分别输入（a,99），（e,97），（j,94），（b,90）（i,90）（c,89）。得到单链表（99,97,94,90,90,89）
　　2） 插入：
　     选择1输入（d,88），得到单链表（99,97,94,90,90,89,88）
       选择1输入（h,86），得到单链表（99,97,94,90,90,89,88,86）
　　   选择1输入（f,85）,得到单链表（99,97,94,90,90,89,88,86,85）

选择1输入（g,84）,得到单链表（99,97,94,90,90,89,88,86,85,84）                          　　　　　　　　　        
　　3） 删除：
　　　  选择2，输入a。返回e=99，得到单链表（97,94,90,90,89,88,86,85,84）
　　4） 修改
　　    选择4，输入b。返回90--93
　　四、实验总结（结果分析和体会）

单链表的最后一个元素的next为null ,所以, 一旦遍历到末尾结点就不能再重新开始;而循环链表的最后一个元素的next为第一个元素地址,可返回头结点进行重新遍历和查找。

 

第二篇：数据结构链表的插入和删除实验报告

第三次实验报告——

单链表的建链表，插入结点，删除结点运算

一 需求分析

1、在演示程序中，出现的元素以数字出现

2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上

3、程序执行的命令包括如下：

（1） 定义结构体

（2） 链表的初始化及创建

（3） 元素的插入

（4） 元素的删除

（5） 链表的打印结果

4、测试数据

二 概要设计

1、可能需要用到有序表的抽象数据类型定义：

ADT List{

数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0}

数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,...,n } 基本操作：

CreateList_L(&L,n)

操作结果：逆序位输入n个元素的值，建立带头结点的单链线性表L

ListInsert(L,i,e)

初始条件：线性表L存在

操作结果：在L中第i个位置之前插入新的数据元素e ListDelete（&L，i)

初始条件：线性表L存在且非空

操作结果：删除L的第i个元素，并用e返回其值，L的长度减1

}ADT List；

2、程序包含的主要模块：

(1) 已给定的函数库：

（2）单链表结构体：

（3）链表初始化及创建:

（4）主程序：

（5）操模块作（插入、删除、输出函数）：

三 详细设计

结构体

typedef struct LNode//结点类型

{

int data;//数值域

struct LNode *next;//指针域

}LNode,*Linklist;

Linklist Initlist_L(int n)//创建带头结点的单链表 {

Linklist L;

Linklist P;

int i;

L=(Linklist)malloc(sizeof(LNode));

L->next=NULL;/* 先建立一个带头结点的单链表 */ printf("请输入%d个数据\n",n);

for(i=n;i>0;--i)

{

P=(Linklist)malloc(sizeof(LNode)); /* 生成新结点 */

scanf("%d",&P->data); /* 输入元素值 */

P->next=L->next; /* 插入到表头 */

L->next=P;

}

return L;

}

插入函数

Linklist ListInsert_L(Linklist L,int i,int e)//单链表的插入

{

Linklist P,S;

int j;

P=L;

j=0;

while(P&&j<i-1)

{

P=P->next;

++j;

}//寻找第i-1个节点

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

printf("错");

S=(Linklist)malloc(sizeof(LNode));//生成新节点 S->data=e;

S->next=P->next;//插入到S中

P->next=S;

return P;

}

删除函数

Linklist ListDelete_L(Linklist L,int i)//单链表的删除 {

Linklist P,S;

int j;

P=L;

j=0;

while(P->next&&j<i-1)

{

P=P->next;

++j;

}//寻找第个节点，并令P指向其前驱 if(!(P->next)||j>i-1)

printf("错");

S=P->next;

P->next=S->next;//删除并释放节点 free(S);

return P;

}

输出函数

void printlist_L(Linklist L)//输出单链表 {

while(L->next!=NULL)

{

L=L->next;

printf("%d",L->data);

}

}

主函数

#include"Base.h"

#include"construct.h"

#include"Link_operation.c"

int main()

{

Linklist L;

int i,choice,n,e;

printf("请输入链表元素个数:");

scanf("%d",&n);

L=Initlist_L(n);

printf("请输入操作元素的位置:");

scanf("%d",&i);

printf("请选择执行语句，选择输入1执行插入操作或选择输入2执行删除操作");

scanf("%d",&choice);

switch(choice)

{

case 1:

{

printf("请输入插入元素的值：");

scanf("%d",&e);

L=ListInsert_L(L,i,e);

printf("插入后的链表为：");

printlist_L(L);

};break;

case 2:

{

L=ListDelete_L(L,i);

printf("删除后的链表为"); printlist_L(L);

};break;

}

}

库函数

* Base.h (程序名) */

#include<string.h>

#include<ctype.h>

#include<malloc.h> /* malloc()等 */ #include<limits.h> /* INT_MAX等 */

#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */

#include<io.h> /* eof() */

#include<math.h> /* floor(),ceil(),abs() */ #include<process.h> /* exit() */

/* 函数结果状态代码 */

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE

四 调试分析:

操作函数中的指针变换错用了数组中的L++;

应该为L=L->next；

五 用户手册:看提示内容

六 测试结果

1）输入n的个数为3，链表的初始赋值为：1 2 3，操作数i的位置为2,执行choice=1，插入值为4，操作后的结果为：3 4 2 1 2）输入n的个数为4，链表的初始赋值为：1 2 3 4，操作数i的位置为5，执行choice=1，插入值为5，操作后的结果为：“没有返回值”

3）输入n的个数为3，链表的初始赋值为：1 2 3，操作数i的位置为0,执行choice=1，插入值为4，操作后的结果为：“没有返回值” 4）输入n的个数为3，链表的初始赋值为：1 2 3，操作数i的位置为2，执行choice=2，操作后的结果为：3 1

5）输入n的个数为3，链表的初始赋值为：1 2 3，操作数i的位置为4，执行choice=2，操作后的结果为：“没有返回的值” 6）输入n的个数为3，链表的初始赋值为：1 2 3，操作数i的位置为0，执行choice=2，操作后的结果为：“没有返回的值”