单链表实验报告及程序.doc

《单链表实验报告及程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法实验课程---单链表兰州财经大学班级：姓名：学号：指导老师：目录一．前言21.1实验目的21.2实验容21.3实验环境3二．需求分析32.1线性表32.2抽象数据类型线性表定义32.3线性表的链式表示42.3.1存储方法42.3.2链表的结点结构52.3.3头指针head和终端结点指针域的表示52.3.4单链表类型描述52.3.5 指针变量和结点变量6三．编程实现63.1主要函数代码63.1.1．主程序63.2．单链表的建立、插入、删除等操作。11四.测试调试与结果分析134.1正常测试数据及运行结果13五．收获及体会17六.参考文献17一．前言1.1实验目的掌握单链

2、表的基本操作，插入、删除、查找等算法的实现。1.2实验容(1)初始化单链表。   (2)在单链表中插入一个新结点。   (3)删除单链表中的某一个结点。   (4)在单链表中查找某结点并返回其位置。   (5)打印输出La中的结点元素值1.3实验环境1、硬件：PC/4G存/512G硬盘/100M/NIC2、软件：操作系统Windows7MicrosoftVisualStudio6.0集成开发环境VC++6.0二．需求分析2.1线性表1、线性表概念：n个数据元素组成的有限序列。表示为（a1，a2，…，ai，ai+1，…，an)。2、逻辑特征：（1）1

3、1，a1无直接前驱；ai的直接后继是ai+1，an无直接后继。（2）元素同构，且不能出现缺项。2.2抽象数据类型线性表定义通常采用抽象数据类型研究数据结构。线性表查询数据类型如下：ADTList{数据对象：D＝{ai

4、ai∈ElemSet，i=1,2,...,n,n≥0}数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则

6、FALSE。ListLength(L)初始条件：线性表L已存在。GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第i个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则

7、操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)操作结果：L中第i个元素赋值同e的值。Li

8、stInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList2.3线性表的链式表示2.3.1.存储方法方式存储的线性表简称为链表（LinkedList），链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了

9、能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2.3.2.链表的结点结构  ┌──┬──┐  │data│next│  └──┴──┘data域--存放结点值的数据域next域--存放结点的直接后继的地址（位置）的指针域（链域）注意：  ①链表通过每个结点的链域将线性表的n个