实验二 线性表综合实验之《双链表》

《数据结构》实验二：

线性表综合实验

一．实验目的

  巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。

二．实验时间

  准备时间为第3周到第4周，具体集中实验时间为第4周第2次课。2个学时。

三.实验内容

1.建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。

要求如下：

  1）用顺序表来实现。

  2）用单链表来实现。

  3）用双链表实现。

  4）用静态链表实现。

  5）用间接寻址实现。

分开写程序，可以一个方法分别写一博客文章上交作业。

 2.实现两个集合的相等判定、并、交和差运算。要求：

  1）自定义数据结构

  2）自先存储结构，并设计算法。在VC中实现。

以上三题，第1题必须完成。第2和第3题可以作为选做题。

四．实验报告

 1.在博客中先写上实习目的和内容，画出主要操作运算算法图，然后分别上传程序代码。插入调试关键结果截图。

 2.单独写一个博文，比较总结线性表的几种主要存储结构。

用双链表实现

1、程序代码

#include<iostream>
using namespace std;
const int M=100;

struct Node
{
		int data;
		Node *next,*prior;
};
                  
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];

s->prior=r;

r->next=s;r=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;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->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } } int LinkList::Delete(int i) //删除 { Node *p; Node *q; int x; int count; p=first;count=0; while(p!=NULL&&count<i) { p=p->next; count++; } if(p==NULL) throw"位置"; else{ (p->prior)->next=p->next; (p->next)->prior=p->prior; delete p; return x; } } void LinkList::PrintList() //遍历操作 { int i=0; Node *p; p=first->next; while(p!=NULL) { i=i+1; cout<<"\t\t\t第"<<i<<"个学生成绩:"<<p->data; cout<<endl; p=p->next; } } int main() { int x,n,loc,len; cout<<endl<<"\t\t\t录入学生成绩信息"<<endl; int j,b[M],s; cout<<"\t\t\t要录入人数："; cin>>n; for(j=0;j<n;j++) { cout<<"\t\t\t第"; cout<<j+1; cout<<"位学生成绩:"; cin>>b[j]; } LinkList List(b,n); while(1) { cout<<endl<<"\t\t\t双链表的实现"<<endl; cout<<" 1.输出学生总人数"<<endl; cout<<" 2.按位查找，取第i位学生成绩"<<endl; cout<<" 3.插入学生信息"<<endl; cout<<" 4.删除学生信息"<<endl; cout<<" 5.输出各学生成绩"<<endl; cout<<" 0.退出"<<endl; cout<<"\t\t\t请选择操作(0-5):"; cin>>x; cout<<endl; if(x==0) break; switch(x) {case 1: //求长度 { len=List.Length(); cout<<"\t\t\t学生总人数为:"<<len<<endl; break; } case 2: //按位查找，第i个 { cout<<"\t\t\t输入学生位置:"; cin>>loc; n=List.Get(loc); cout<<"\t\t\t该学生的成绩为:"<<n<<endl; break; } case 3: //插入 { cout<<"\t\t\t输入学生信息插入位置:"; cin>>loc; cout<<"\t\t\t输入插入数值:"; cin>>n; List.Insert(loc,n); cout<<"\t\t\t插入成功!"<<endl; break; } case 4: //删除 { cout<<"\t\t\t输入删除的学生位置:"; cin>>loc; cout<<"\t\t\t已删除的学生成绩:"<<List.Delete(loc)<<endl; cout<<"\t\t\t删除成功！"<<endl; break; } case 5: //输出 { cout<<"\t\t\t输出各元素:"<<endl; List.PrintList(); break; } default: { cout<<"\t\t\t请输入数字(0-5)！"<<endl; } } } }

2、调试截图

录入信息

按位查找

插入操作

删除操作