1、北京邮电大学数据结构实验第一次实验线性表数据结构实验报告实验名称： 实验1线性表学生姓名：班 级： 班内序号： 学 号： 日 期： 1实验要求根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、 带头结点的单链表 2、 不带头结点的单链表 3、 循环链表 4、 双链表 5、 静态链表 线性表的基本功能： 1、 构造：使用头插法、尾插法两种方法 2、 插入：要求建立的链表按照关键字从小到大有序 3、 删除 4、 查找 5、 获取链表长度 6、 销毁 7、 其他：可自行定义 编写测试main()函数测试线性表的正确性。2.程序
2、分析 2.1 存储结构 2.2 关键算法分析1：头插法 自然语言描述： a:在堆中建立新结点 b:将ai写入到新结点的数据域 c:修改新结点的指针域 d:修改头结点的指针域。将新结点加入链表中 伪代码描述 a:Node * s=new Node b:s-data=ai c:s-next=front-next; d:front-next=s 2：尾插法 自然语言描述： a:在堆中建立新结点： b:将ai写入到新结点的数据域： c:将新结点加入到链表中 d:修改修改尾指针 伪代码描述 a:Node * s=new Node b:s-data=ai c:r-next=s; d:r=s 3：析构/删除
3、函数 自然语言描述： a:新建立一个指针，指向头结点 b:判断要释放的结点是否存在， c:暂时保存要释放的结点 d:移动a中建立的指针 e:释放要释放的指针 伪代码描述 a:Node * p=front b:while(p) c:front=p d:p=p-next e:delete front4：按位查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 c:若p为空，说明第i个元素不存在，抛出异常 d:否则，说明p指向的元素就是所查找的元素，返回元素地址 伪代码描述 a:Node *
4、 p=front-next;j=1; b:while(p&j!=1) b1:p=p-next b2:j+ c:if(!p) throw -1 d:return p 5：按值查找函数 自然语言描述： a:初始化工作指针p和计数器j，p指向第一个结点，j=1 b:循环以下操作，找到这个元素或者p指向最后一个结点 c：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一 d:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 伪代码描述 a:Node * p=front-next;j=1; b:while(p) c:if(p-next=x) return
5、j p=p-next j+ d:return -1 6：插入函数 自然语言描述： a:在堆中建立新结点 b:将要插入的结点的数据写入到新结点的数据域 c:修改新结点的指针域 d:修改前一个指针的指针域，使其指向新插入的结点的位置 伪代码描述 a:Node * s=new Node ; b:s-data=p-data c:s-next=p-next d:p-next=s e:p-data=x7：删除函数 自然语言描述： a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b:设q指向第i个元素 c:将q元素从链表中删除 d:保存q元素的数据 e:释放q元素 伪代码描述 a:q=p-n
6、ext b:p-next=q-next c:x=q-data d:delete q 8：遍历打印函数 自然语言描述： a:判断该链表是否为空链表，如果是，报错 b:如果不是空链表，新建立一个temp指针 c:将temp指针指向头结点 d:打印temp指针的data域 e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 伪代码描述 If front-next=NULL Throw ”an empty list ” Node* temp=front-next; while(temp-next) coutdatanext; 8：获取链表长度函数 自然语言描述： a:判断该链表
7、是否为空链表，如果是，输出长度0 b:如果不是空链表，新建立一个temp指针，初始化整形数n为0 c:将temp指针指向头结点 d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述 int n=0 if front-next=NULL n=0 else Node* temp=front-next; while(temp-next) n+; temp=temp-next; return n; 1：头插法插入链表 Node *s =new Node ; s-
8、data=ai; s-next=front-next; front-next=s; 2:尾插法插入链表 Node *s=new Node ; s-data=ai; r-next=s; r=s; 3：查找算法 Node*p=front-next; int j=1; while(p&j!=i) p=p-next; j+; 4：删除算法 Node*p=front; if(i!=1)p=Get(i-1); Node*q=p-next; p-next=q-next; T x=q-data; delete q; 头插法/尾插法 O(n) 按位查找/按值查找 O(n) 插入操作 O(n)3. 程序运行结果截
9、图流程图 开始 初始化对象 初始化整形数组 利用头插法和尾插法初始化，用遍历打印函数来显示数值 执行删除函数，然后用遍历打印函数来检测删除结果 执行插入函数，然后用遍历打印函数来检测插入结果 按位查找和按值查找 结束4. 总结 对链表的掌握不够扎实，对类的掌握不全面。代码：#includeusing namespace std;class Nodepublic: int data; Node*next;class LinkListpublic: LinkList() ; LinkList(int a,int n); Node * Get(int j); int Locate(int x); v
10、oid Insert(int j,int x); int Delete(int j); int Getlength(); void Print(); LinkList();private: Node* front; int length;LinkList:LinkList(int a,int n) front = new Node; front - next = NULL; for(int j=n-1;j=0;j-) Node*s=new Node; s-data=aj; s-next=front-next; front-next=s; /*LinkList:LinkList(int a,in
11、t n) front = new Node; Node*r=front; for(int j=0;jn;j+) Node*s=new Node; s-data=aj; s-next=s; r=s; r-next=NULL;*/Node*LinkList:Get(int i) Node*p=front-next; int j =1; while(p&j!=i) p=p-next; j+; return p;int LinkList:Locate(int x) Node*p=front-next; int j=1; while(p) if(p-data=x) return j; p=p-next;
12、 j+; return -888;void LinkList:Insert(int i,int x) Node*p=front; if(i!=1) p=Get(i-1); if(p) Node* s=new Node; s-data=x; s-next=p-next; p-next=s; else throw error;int LinkList:Delete(int i) Node*p=front; if(i!=1) p=Get(i-1); Node*q=p-next; p-next=q-next; int x=q-data; delete q; return x;LinkList:Link
13、List() Node*p = front; while(p) front = p; p=p-next; delete front; int LinkList:Getlength() length = 0; Node * n = front-next; while(NULL != n) length+; n = n-next; return length;void LinkList:Print() Node*n=front-next; while(NULL!=n) coutdatanext; coutendl;void main() int a10=7,9,10,11,22,8,33,2,21,80; LinkList*Lin=new LinkList(a,10); coutGetlength()endl; coutGet(7)endl; coutGet(100)endl; coutLocate(9)endl; coutLocate(50)Print(); Lin-Insert(3,20); Lin-Print(); Lin-Delete(5); Lin-Print(); Lin-LinkList; Lin-Print();
