实验一 线性表 实验报告.docx

数据结构实验报告实验名称:实验一线性表学生姓名: 班级: 班内序号: 学号: 日期: 2012 年 11月3日 1、实验要求据线性表的抽象数据类型的定义, 选择下面任一种链式结构实现线性表, 并完成线性表的基本功能。线性表存储结构(五选一): 1 、带头结点的单链表 2 、不带头结点的单链表 3 、循环链表 4 、双链表 5 、静态链表线性表的基本功能: 1 、构造:使用头插法、尾插法两种方法 2 、插入:要求建立的链表按照关键字从小到大有序 3 、删除 4 、查找 5 、获取链表长度 6 、销毁 7 、其他:可自行定义编写测试 main() 函数测试线性表的正确性 2、程序分析 存储结构单链表的存储结构 A[2] 1080H ……结点地址: 1000H A[0] 10C0H …… A[3] NULL …… A[1] 1000H …… 关键算法分析一:关键算法 1 :头插法自然语言描述: a: 在堆中建立新结点 b:将 a[i] 写入到新结点的数据域 c: 修改新结点的指针域 d: 修改头结点的指针域,并将新结点加入链表中伪代码描述: a:Node * s=new Node ; b:s->data=a[i] ; c:s->next=front->next; d:front->next=s; 2: 尾插法自然语言描述: a: 在堆中建立新结点 b:将 a[i] 写入到新结点的数据域 c: 将新结点加入到链表中 d: 修改尾指针伪代码描述: a:Node * s=new Node ; b:s->data=a[i] ; c:r->next=s; d:r=s; 3: 删除大于 min 小于 max 元素算法: 自然语言描述: a: 建立新结点 b: 保存第一个结点的位置 c: 执行循环, 查找到 p 结点为第一个大于 min 小于 max 的元素,q 为比 min 大的前一个元素位置 d: 执行循环,查找到比 max 小的最后一个元素位置 e: 将上述两步骤中的满足条件的中间节点删掉 f: 将前后两条断链重新连接起来,连接 p和q 结点地址: 1020H 地址: 1080H 地址: 10C0H 头指针伪代码描述: a: Node *p,*q,*r; b: p=front->next; c: while(p&&p->data<=min) { q=p; p=p->next; }d和e: while(p&&p->data<max) // 找比 max 小的最后一个元素位置{ r=p; p=p->next; delete r; // 释放满足条件的结点} f: q->next=p; 4 :链表逆置算法自然语言描述: a: 建立新结点 b: 判断链表是否为空表或者单结点链表 c: 将开始结点变成终端结点 d: 执行循环,使每次循环都将后一个结点变成开始结点 e: 遍历打印伪代码描述: a: Node *p,*q; b: if(front->next&&front->next->next) c: p=front->next; q=p->next; p->next=NULL; d: while(q) { p=q; // 每次循环将后一个结点变成起始结点 q=q->next; p->next=front->next; front->next=p; } e: z=front->next; while(z) // 遍历打印逆置后的序列{ cout<<z->data<<" "; z=z->next; } 5. 销毁函数自然语言描述: a: 新建立一个指针,指向头结点 b: 判断要释放的结点是否存在 c: 暂时保存要释放的结点 d: 移动 a 中建立的指针 e: 释放要释放的指针伪代码描述: a:Node * p=front b:while(p) c:front=p d:p=p->next e:delete front 6. 按位查找函数(查找第 i 个元素的位置) 自然语言描述: a: 初始化工作指针 p 和计数器 j,p 指向第一个结点, j=1 b: 循环以下操作,直到 p 为空或者 j 等于 1 b1:p 指向下一个结点 b2:j加1 c:若p 为空,说明第 i 个元素不存在,抛出异常 d: 否则,说明 p 指向的元素就是所查找的元素,返回元素地址伪代码描述 a:Node * p=front->next;j=1; b:while(p&& ( j!=i )) b1:p=p->next b2:j++ c:if(!p) throw ”查找位置有误” d:return p 7 :按位查找函数(查找值为 x 的元素并返回其位置) 自然语言描述: a: 初始化工作指针 p 和计数器 j,p 指向第一个结点, j=1 b: 循环以下操作,找到这个元