《数据结构》上机报告
_2011_年_ 3 _月_ 9 _日
姓名__ ___ 学号_ _ 同组成员 __ _无_ __ 1. 实验题目及要求
编写一个程序，实现单链表的各种基本运算
2. 需求分析
建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在单链表中的位置。
（1） 初始化单链表；
（2） 依次采用尾插入法插入a,b,c,d,e元素； （3） 输出单链表L；
（4） 输出单链表L的长度； （5） 判断单链表L是否为空；
（6） 输出单链表L的第三个元素； （7） 输出元素a的位置；
（8） 在第4个元素位置上插入f元素； （9） 输出单链表L；
（10） 删除L的第3个元素； （11） 输出单链表L； （12） 释放单链表。
3. 概要设计
（1） 为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：
ADT LinearList {
数据对象：D={ ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 结构关系：R={
InitList_L(L)
操作前提：L是一个未初始化的线性表 操作结果：将L初始化为一个空的线性表
CreateList_L(L)
操作前提：L是一个已初始化的空表 操作结果：建立一个非空的线性表L
ListInsert_L(L,pos,e)
操作前提：线性表L已存在
操作结果：将元素e插入到线性表L的pos位置
ListDelete_L(L,pos,e)
操作前提：线性表L已存在
操作结果：将线性表L中pos位置的元素删除，
删除的元素值通过e返回
LocateList_L(L,e)
操作前提：线性表L已存在
操作结果：在线性表L中查找元素e，
若存在，返回元素在表中的序号位置； 若不存在，返回-1
DestroyList_L(&L)
初始条件：线性表L已存在 操作结果：销毁线性表
ListEmpty_L(L)
初始条件：线性表已存在
操作结果：若L为空表，则返回ERROR，否则返回FALSE
ListLength_L(L)
初始条件：线性表L已存在
操作结果：返回L中数据元素个数
GetElem_L(L,I,&e)
初始条件：线性表L已存在
操作结果：用e返回L中第i个数据元素值 }
（2） 本程序包含10个函数：
? ? ? ? ? ? ? ?
主函数main()
初始化单链表函数InitList_L() 显示单链表内容函数DispList_L() 插入元素函数ListInsert_L() 删除元素函数ListDelete_L() 查找元素函数LocateList_L() 创建链表函数CreateList_L()
链表元素长度函数ListLength_L()
? ?
判断链表是否为空函数ListEmpty_L() 取值函数GetElem_L()
各函数间调用关系如下：
( 3 ) 主函数的伪码
main()
{ 说明一个单链表 L ； 初始化 L ； 建立 L ； 显示 L ； }
main
InitList DispList CreateList ListLength ListEmpty DestroyList GetElem ListInsert ListDelete LocateElem
4. 详细设计
采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义
如下：
（1） 类型定义
typedef int ElemType; typedef struct LNode
{ ElemType data; //数据域 struct LNode *next; //指针域 } LNode,* LinkList;
（2） 基本操作的伪码算法
?
初始化
Bool InitLinkList(LinkList *L) { *L=申请新结点;
如果申请失败，返回失败标志； (*L)->next=NULL; 返回成功标志； } ?
建立单链表
Bool CrtLinkList(LinkList L)
/* L是已经初始化好的空链表的头指针，通过键盘输入元素值， 利用尾插法建单链表L */ { rear=L;
打印输入提示：“请输入若干个正整数（用空格分隔），并用 -1 结束：” 读入一个数x;
当x不是结束标志时，循环做如下处理： {
申请一个新结点s；
如果申请失败，返回失败标志； 将x送到s的data域; rear->next=s; rear=s; 读入下一个数x; }
rear->next=NULL; 返回成功标志； } ?
显示单链表（输出）
void DispLinkList(LinkList L) {
p=首元素结点地址; while ( p不空 ) {
打印结点p 的元素值； p=下一个结点地址; } }