实验二之单链表
《数据结构》实验二：
线性表综合实验
一．实验目的
巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。
二．实验时间
准备时间为第3周到第4周，具体集中实验时间为第4周第2次课。2个学时。
三．.实验内容
1.建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。
要求如下：
1）用顺序表来实现。
2）用单链表来实现。
3）用双链表实现。
4）用静态链表实现。
5）用间接寻址实现。
分开写程序，可以一个方法分别写一博客文章上交作业。
2.实现两个集合的相等判定、并、交和差运算。要求：
1）自定义数据结构
2）自先存储结构，并设计算法。在VC中实现。
以上三题，第1题必须完成。第2和第3题可以作为选做题。
四．实验报告
1.在博客中先写上实习目的和内容，画出主要操作运算算法图，然后分别上传程序代码。插入调试关键结果截图。
2.单独写一个博文，比较总结线性表的几种主要存储结果。
单链表做的并不好，里面还有一些功能存在着缺陷，但是，这些是最难找的，我倒宁愿它出现程序上的错误。可是难找也要找，不然功能实现不了。可是问过舍友之后，我也是一脸蒙蒙的，然后就只能自己找了，不然越来越乱，后来改进一些了，可是还是很多功能有缺陷，上网也查了一些，可是并没有成功，对比也弄不出来，然后只能放弃了，毕竟后面还有好几个要弄，准备弄好之后在回来弄得，可是要交了，不过在交了之后我会继续改进的，哪怕做不了完美，也尽量改的好一点。
源代码如下：
#include<iostream>
using namespace std;
const int M=100;
struct Node
{
int data;
Node *next;
};
class LinkList //定义类SeqList
{
public:
LinkList();
LinkList(int a[],int n);
~LinkList();
int Length(); //表长
int Get(int i); //按位
void Insert(int i,int x); //插入
int Delete(int i); //删除
void PrintList(); //遍历
private:
Node *first; //头指针
};
LinkList::LinkList()
{
first=new Node; //生成头结点
first->next=NULL; //尾指针初始化
}
LinkList::LinkList(int a[],int n)
{
Node *r;
Node *s;
int i;
first=new Node;
r=first;
for(i=0;i<n;i++)
{
s=new Node;s->data=a[i]; //为每个数组元素建立一个结点
r->next=s;r=s; //将结点s插入到终端结点之后
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
}
LinkList::~LinkList()
{
while(first!=NULL)
{
Node *q;
q=first;
first=first->next;
delete q;
}
}
int LinkList::Length() //表长
{
Node *p;
int count;
p=first->next; count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return count;
}
int LinkList::Get(int i) //按位查找
{
Node *p;
int count;
p=first->next;count=1;
while(p!=NULL&&count<i)
{
p=p->next;
count++;
}
if(p==NULL)
throw"异常";
else
return p->data;
}
void LinkList::Insert(int i,int x) //插入
{
Node *p;
int count;
p=first->next;count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL) throw"位置";
else
{
Node *s;
s=new Node;s->data=x;
s->next=p->next;p->next=s;
}
}
int LinkList::Delete(int i) //删除
{
Node *p;
Node *q;
Node *x;
int count;
p=first->next;count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL)
throw"位置";
else{
q=p->next;x=q->next;
p->next=q->next;
delete q;
return x->data;
}
}
void LinkList::PrintList() //遍历操作
{
Node *p;
int i=0;
p=first->next;
while(p!=NULL)
{
i=i+1;
cout<<"第"<<i<<"个学生成绩"<<p->data;
cout<<endl;
p=p->next;
}
}
int main()
{
int x,n,loc,len;
cout<<"录入学生成绩信息"<<endl;
int j,b[M],s;
cout<<"要录入人数:";
cin>>n;
for(j=0;j<n;j++)
{
cout<<"第";
cout<<j+1;
cout<<"位学生成绩:";
cin>>b[j];
}
LinkList List(b,n);
while(1)
{
cout<<"学生的成绩信息"<<endl;
cout<<"1.输出学生总人数"<<endl;
cout<<"2.查找第i位学生成绩"<<endl;
cout<<"3.插入学生信息"<<endl;
cout<<"4.删除学生信息"<<endl;
cout<<"5.输出各学生的成绩信息"<<endl;
cout<<"6.退出"<<endl;
cout<<"请选择操作(1-6):"<<endl;
cin>>x;
cout<<endl;
if(x==6)
break;
switch(x)
{
case 1: //求长度
{
len=List.Length();
cout<<"学生总人数为:"<<len<<endl;
break;
}
case 2: //按位查找，第i个
{
cout<<"输入学生位置:";
cin>>loc;
n=List.Get(loc);
cout<<"该学生的成绩为:"<<n<<endl;
break;
}
case 3: //插入
{
cout<<"输入学生信息插入位置:";
cin>>loc;
cout<<"输入学生成绩:";
cin>>n;
List.Insert(loc,n);
cout<<"插入成功!"<<endl;
break;
}
case 4: //删除
{
cout<<"输入删除的学生位置:";
cin>>loc;
cout<<"删除成功！"<<endl;
break;
}
case 5: //输出
{
cout<<"输出各学生的成绩:"<<endl;
List.PrintList();
break;
}
default:
{
cout<<"请输入数字(1-6)！"<<endl;
}
}
}
}
实验结果如图所示：