数据结构上机报告:编写一个程序,实现单链表的各种基本运算

《数据结构》上机报告

_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={|ai,ai+1 ∈D} 基本操作:

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=下一个结点地址; } }

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4