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

第三次实验报告——单链表的建链表，插入结点，删除结点运算一需求分析在演示程序中，出现的元素以数字出现演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上程序执行的命令包括如下：（1）定义结构体（2）链表的初始化及创建（3）元素的插入（4）元素的删除（5）链表的打印结果测试数据二概要设计1、可能需要用到有序表的抽象数据类型定义：ADTList{数据对象: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个元素的值，建立带头结点的单链线性表LListInsert(L,i,e)初始条件：线性表L存在操作结果：在L中第i个位置之前插入新的数据元素eListDelete（&L，i)初始条件：线性表L存在且非空操作结果：删除L的第i个元素，并用e返回其值，L的长度减1}ADTList；2、程序包含的主要模块：(1)已给定的函数库：（2）单链表结构体：（3）链表初始化及创建:（4）主程序：（5）操模块作（插入、删除、输出函数）：三详细设计结构体typedefstructLNode//结点类型{ intdata;//数值域 structLNode*next;//指针域}LNode,*Linklist;LinklistInitlist_L(intn)//创建带头结点的单链表{ LinklistL; LinklistP; inti; 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; } returnL;}插入函数LinklistListInsert_L(LinklistL,inti,inte)//单链表的插入{ LinklistP,S; intj; 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; returnP;}删除函数LinklistListDelete_L(LinklistL,inti)//单链表的删除{ LinklistP,S; intj; 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); returnP;}输出函数voidprintlist_L(LinklistL)//输出单链表{ while(L->next!=NULL) {L=L->next; printf("%d",L->data); }}主函数#include"Base.h"#include"construct.h"#include"Link_operation.c"intmain(){ LinklistL; inti,choice,n,e; printf("请输入链表元素个数:"); scanf("%d",&n); L=Initlist_L(n); printf("请输入操作元素的位置:"); scanf("%d",&i); printf("请选择执行语句，选择输入1执行插入操作或选择输入2执行删除操作"); scanf("%d",&choice); switch(choice) { case1: { printf("请输入插入元素的值："); scanf("%d",&e); L=ListInsert_L(L,i,e); printf("插入后的链表为："); printlist_L(L); };break; case2: { 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()*//*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE四调试分析:操作函数中的指针变换错用了数组中的L++;应该为L=L->next；五用户手册:看提示内容六测试结果输入n的个数为3，链表的初始赋值为：123，操作数i的位置为2,执行choice=1，插入值为4，操作后的结果为：3421输入n的个数为4，链表的初始赋值为：1234，操作数i的位置为5，执行choice=1，插入值为5，操作后的结果为：“没有返回值”输入n的个数为3，链表的初始赋值为：123，操作数i的位置为0,执行choice=1，插入值为4，操作后的结果为：“没有返回值”输入n的个数为3，链表的初始赋值为：123