北邮数据结构实验报告实验一线性表..docx

数据结构实验报告实验名称： 实验一线性表——题目1学生姓名： 申宇飞班 级： 信通3班班内序号： 03学 号： 2012210064日 期： 2013年11月4日实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：带头结点的单链表不带头结点的单链表循环链表双链表静态链表 线性表的基本功能：构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序删除查找获取链表长度销毁其他：可自行定义编写测试main()函数测试线性表的正确性。 程序分析2.1 存储结构链表的具体存储表示为：　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构? ┌──┬──┐? │data│next│? └──┴──┘?????? 　data域--存放结点值的数据域????? 　next域--存放结点的直接后继的地址（位置）的指针域（链域）地址 内存单元a[3]1080H……a[1]10C0H……a[4]^……a[2]1000H……1000H头指针 1020H1080H10C0Hfront………… 2.2 关键算法分析1、关键算法： 1：头插法 自然语言描述： a:在堆中建立新结点 b:将a[i]写入到新结点的数据域 c:修改新结点的指针域 d:修改头结点的指针域。将新结点加入链表中 伪代码描述 a:Node T * s=new Node T b:s-data=a[i] c:s-next=front-next; d:front-next=s 2：尾插法 自然语言描述： a:在堆中建立新结点： b:将a[i]写入到新结点的数据域： c:将新结点加入到链表中 d:修改修改尾指针 伪代码描述 a:Node T * s=new Node T b:s-data=a[i] c:r-next=s; d:r=s 3：析构/删除函数 自然语言描述： a:新建立一个指针，指向头结点 b:判断要释放的结点是否存在， c:暂时保存要释放的结点 d:移动a中建立的指针 e:释放要释放的指针 伪代码描述 a:Node T * p=front b:while(p) c:front=p d:p=p-next e:delete front 4：按位查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 c:若p为空，说明第i个元素不存在，抛出异常 d:否则，说明p指向的元素就是所查找的元素，返回元素地址 伪代码描述 a:Node T * p=front-next;j=1; b:while(pj!=1) b1:p=p-next b2:j++ c:if(!p) throw ”error” d:return p 5：按位查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，找到这个元素或者p指向最后一个结点 b1：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下 一个结点，并且j的值加一 c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 伪代码描述 a:Node T *