单链表的基本操作.doc

忻州师范学院计算机科学与技术系实验报告实验名称 单链表基本操作 专业班级 计算机科学与技术1003 姓名 张亚茹 学号 201008111180 指导教师 李荣 成绩 日期 2011-11-4 一、实验目的熟练掌握线性表的类型定义方法、存储方法及其基本运算（元素的插入、删除等）的实现方法，培养综合运用所学知识，根据具体问题进行数据结构设计和算法设计的能力。二、实验内容建立单链表，并实现单链表的插入、删除、查找运算。要求：要有良好的人机界面，具备插入、删除、显示以及查找的功能。三、实验要求1在问题分析的基础上选择合适的存储结构，进行算法设计，编制程序并上机调试成功。2按要求完成实验报告。3保存和打印出程序的运行结果，并结合程序进行分析。四、实验步骤1需求分析本演示程序用C语言编写，要有良好的人机界面，实现单链表的基本功能：插入、删除、显示以及查找。1) 输入的形式和输入值的范围：通过键盘输入数据，输入的数据可以是数字或字符，如：3 -23 100 56 或 r q r y u2) 输出的形式：以单链表的形式输出。如：3- -23- 100- 56或 r-q-r-y-u3) 预期结果：要求体现良好的人机界面，插入、删除和查找数或字符之前，要给出提示信息，插入、删除和查找完成之后，要提示操作成功，并显示结果。2概要设计本程序包含7个函数： 主函数main()显示操作菜单函数scan() 构造单链表函数createlist_l（） 查找单链表函数locatelist_l（） 插入运算函数listinsert_l（） 删除运算函数listdelete_l（）显示单链表函数printlist_l ()各函数间关系如下:main() createlist_l ()scan()locatelist_l () listinsert_l () listdelete_l () printlist_l ( )3详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。一 单链表Linklist的存储结构typedef char DataType; typedef struct nodeDataType data; struct node *next;LNode，*LinkList二 单链表的基本操作算法 （1）构造单链表算法void CreatLinkList(LinkList L)rear=L；打印输入提示：“请输入若干个正整数（用逗号分隔）；并用-1结束：”；读入一个数x；当x不是结束标志时，作如下处理 ： 申请一个新结点s; 如果申请失败，返回失败标志；将x送到s的data域； rear-next=s; rear=s; 读入下一个数xrear-next=NULL; 返回成功标志； （2）查找算法2.8void LocateList(LinkList L, ElemType e) P=首元素结点地址; while(p不为空) If(p-data!=e) p=p-next;k+; Else break; if(p不为空) return k; else return -1; （3） 插入算法2.9void InsertList(LinkList L,int pos,ElemType e) 从头开始，查找第i-1个结点pre;if(查找失败) 显示参数错误信息； return ERROR;else 申请一个新结点s;将e送到s的data域； 将s插到 pre后面； return OK;（4）删除算法2.10void DeleteList(LinkList L,int pos,ElemType e) if(查找失败) 显示参数错误信息； Return ERROR;elser=pre-next; 修改指针，删除结点r； 释放被删除的结点所占的内存空间； return OK（5）输出单链表算法:void DispLinkList(LinkList L) p=首元素结点地址; while(p不为空) 打印结点P的元素值;p=下一个结点地址;（6）显示操作菜单函数scan()输出所需信息；继续输入；(4调试分析1)分析算法的总体结构，分清程序中各部分应实现的功能； 2)调试方法通常有二种：总体调试、分块调试。你主要采用哪种调试方法？ 总体调试：把算法组装成单个程序，按C程序结构标准分层检查调试； 分块调试：把算法分拆成几个功能模块，按C程序结构标准分模块调试； 3)错误跟踪有两种方法：错误信息排查法、执行路线跟踪法。 错误信息排查法：根据错误信息进行分类排查，要求分析者对C的错误代码要有足够的了解和认识，有经验的程序员多用此法。 执行路线跟踪法：变量分析法（跟踪变量的值）、插入标签法（插入输出标签），这种方法适合初学者。 4）调试分析不宜面面俱到，具体写出关键问题就行。分析如下：主函数main()首先调用构造单链表函数createlist_l()，然后调用显示操作菜单函数scan()，再根据用户输入的数字选项分别调用以下函数： 查找函数: locatelist_l () 插入函数:listinsert_l () 删除函数:listdelete_l ()输出函数: printlist_l ( )由上述结构可知，采用分功能模块调试的方法较合理，即主要功能按以下顺序实现：构造查找删除(或插入)输出。5使用说明程序执行后，界面直接输出要求的结果。键入数字1程序执行显示：键入数字2程序执行显示：键入数字3程序执行显示：键入数字#程序执行显示：键入数字6程序执行显示：6测试结果： 程序如下：#include #include typedef char DataType; typedef struct nodeDataType data; struct node *next;LNode;LNode *head; void CreatLinkList()LNode *p,*s;char x;int z=1; head=(LNode *)malloc(sizeof(LNode);head-next=NULL;p=head;printf(nttt建立一个线性表);printf(nttt说明：请逐个输入字符，结束标记为#!n);while(z)printf(ttt输入：);scanf(%c,&x);getchar();if(x!=#)s=(LNode *)malloc(sizeof(LNode); s-data=x;s-next=p-next;p-next=s;p=s;else z=0;int LenLinkList()int n=0;LNode* p=head; while (p-next) p=p-next; n+; return n;void InsertLinkList(int i,char x)/* 在线性表L的第 i 个位置上插入一个值为 x 的新元素 1=idata=x;if(i1) printf(nttt插入位置不合法!n);free(s);return;elsej=0;p=head;while(p!=NULL & jnext;if(p!=NULL)s-next=p-next;p-next=s;else printf(nttt未找到插入位置!n);free(s);return;void DeleteLinkList(int i)LNode *p,*q;int j=0;if(head-next=NULL) printf(nttt链表为空没有元素可以删除!n);if (inext & jnext; j+; if (!(p-next) | ji-1) printf(nttt没找到要删除的位置n);return; q=p-next; p-next=q-next; free(q); int LocateLinkList(DataType x)/*在线性表中查找值为的数据元素*/int y;printf(tt本函数请同学自己编写!n);return y;void ShowLinkList()LNode *p=head;printf(nttt显示线性表的所有元素：);if(head-next=NULL)printf(nttt链表为空!n);elseprintf(ntt);while(p-next!=NULL)printf(t%c,p-next-data);p=p-next;/* 主函数 */main()char choice;int i,j=1;DataType x;while(j)printf(nnnn);printf(ttt-线 性 链 表-n);printf(nttt*);printf(nttt* 1-建 表 *);printf(nttt* 2-插 入 *);printf(nttt* 3-删 除 *);printf(nttt* 4-求 表 长 *);printf(nttt* 5-按 值 查找 *);printf(nttt* 6-显示线性表 *);printf(nttt* 0-退 出 *);printf(nttt*n);printf(ttt请选择菜单号(0-6)：);scanf(%c,&choice);getchar();if(choice=1)CreatLinkList();else if (choice=2)printf(nttt请输入的位置i和数值x(输入格式：i，x):);scanf(%d,%c,&i,&x);InsertLinkList(i,x);else if (choice=3)printf(nttt请输入要删除元素的位序：);scanf(%d,&i);De