文档介绍：数据结构实验报告
实验名称: 实验1——线性表
学生姓名:
班级:
班内序号:
学号:
日期:
实验要求
1、实验目的: 熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法
学****指针、模板类、异常处理的使用
掌握线性表的操作的实现方法
学****使用线性表解决实际问题的能力
2、实验内容:
题目1:
线性表的基本功能:
构造:使用头插法、尾插法两种方法
插入:要求建立的链表按照关键字从小到大有序
删除
查找
获取链表长度
销毁
其他:可自行定义
编写测试main()函数测试线性表的正确性。
2. 程序分析

存储结构
带头结点的单链表
关键算法分析

a、伪代码实现:在堆中建立新结点
将x写入到新结点的数据域
修改新结点的指针域
修改头结点的指针域,将新结点加入链表中
b、代码实现:
Linklist::Linklist(int a[],int n)//头插法
{front=new Node;
front->next=NULL;
for(int i=n-1;i>=0;i--)
{Node*s=new Node;
s->data=a[i];
s->next=front->next;
front->next=s;
}
}
2、尾插法
a、伪代码实现:
[i]写入到新结点的数据域

b、代码实现:
Linklist::Linklist(int a[],int n,int m)//尾插法
{front=new Node;
Node*r=front;
for(int i=0;i<n;i++)
{Node*s=new Node;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
时间复杂度:O(n)
3、按位查找
a、伪代码实现: 初始化工作指针p和计数器j,p指向第一个结点,j=1
循环以下操作,直到p为空或者j等于1
b1:p指向下一个结点
b2:j加1
若p为空,说明第i个元素不存在,抛出异常
否则,说明p指向的元素就是所查找的元素,返回元素地址
b、代码实现
Node* Linklist::Get(int i)//得到指向第i个数的指针
{Node*p=front->next;
int j=1;
while(p&&j!=i)//p非空且j不等于i,指针后移
{p=p->next;
j++;
}
return p;
}
4、插入操作
a、伪代码实现: 如果链表为空,直接插入
判断p的下一个结点的值大于x且p的值小于x
在堆中建立新结点
将要插入的结点的数据写入到新结点的数据域
修改新结点的指针域
修改前一个指针的指针域,使其指向新插入的结点的位置
b、代码实现
void Linklist::Insert(int x)//将x按顺序插入
{Node*p=front->next;
if(!p)//如果链表为空,直接插入
{Node*s=new Node;
s->data=x;
s->nex