C++数据结构双链表
《数据结构》实验二：
线性表综合实验
一．实验目的
巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题,巩固课堂学习。
二. 实验内容
1.建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。
这里用双链表来实现。
//
// main.cpp
// 双链表
//
// Created by 梁华建 on 2017/9/17.
// Copyright © 2017年 梁华建. All rights reserved.
//
#include <iostream>
template<class DataType>
struct DulNode
{
DataType data;
DulNode<DataType> *prior,*next;
};
template<class DataType>
class LinkList
{
public :
LinkList(); //无参构造函数，建立只有头结点的双链表
LinkList(DataType a[],int n); //有参构造函数，建立有n个元素的双链表
~LinkList(); //析构函数，在对象被清空时候调用
int Length(); //求双链表的长度
DataType Get(int i); //按位置查找，在双链表中查找到第i个节点的袁术
int locate(DataType x); //按位置查找，在双链表中查找到值为x的元素
void Insert(int i ,DataType x);//插入操作，在第i个位置插入元素值为x的元素
DataType Delete(int i); //删除在第i个位置的元素
void PrintList(); //遍历输出所有双链表的函数
private :
DulNode<DataType >*first; //双链表的头指针
};
//遍历函数
template<class DataType>
void LinkList<DataType>::PrintList()
{
DulNode<DataType> * p=NULL; //创建工作结点
p=first->next;
while (p!=NULL) {
std::cout<<p->data<<" "; //遍历输出所有元素直到尾部
p=p->next;
}
}
//删除函数
template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
DulNode<DataType> * p=first;//p指向头结点
int count=0;
DataType x;
while (p!=NULL && count<i) {//遍历找到i-1的结点
p=p->next;
count++;
}
if (p==NULL||p->next==NULL) throw "i节点不存在或i的后续节点为空";
else {
// p为待删除节点
x=p->data;
(p->prior)->next=p->next; //p的prior指向p的next a(i-1)->a(i+1)
(p->next)->prior=p->prior; //p的next指向p的prior a(i+1)->a(i-1)
}
return x;
}
//插入函数
template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
DulNode<DataType> *s;
DulNode<DataType> * p=first;//p指向头结点
int count=0;
while (p!=NULL&&count<i-1) {//遍历找到i-1的结点
p=p->next;
count++;
}
if (p==NULL) throw "i节点不存在";
else{ s=new DulNode<DataType>;
s->data=x; //创建新结点
s->prior=p; //把s插入i-1和i中
s->next=p->next;
p->next->prior=s; //摘除i-1和i之间的链
p->next=s;
// s->next=p->next;p->next=s; //将结点s放在结点p之后
}
}
//查找函数 通过值
template<class DataType>
int LinkList<DataType>::locate(DataType x)
{
DulNode<DataType> *p=NULL;
p=first;
int count=1;
while (p!=NULL) {
if (p->data==x) {
return count;
}
else{
p=p->next;
count++;
}
}
return count;
}
//查找函数 通过下标
template<class DataType>
DataType LinkList<DataType>::Get(int i)
{
DulNode<DataType>* p=NULL;
p=first->next;
int count=1;
while (p!=NULL && count<i) {
p=p->next;
count++;
}
if (p==NULL) throw "输入的x有误";
else return p->data;
}
//求线性表长度算法
template<class DataType>
int LinkList<DataType>::Length()
{
DulNode<DataType> *p=first->next;
int count=0;
while (p!=NULL) {
p=p->next;
count++;
}
return count;
}
template <class DataType>
LinkList<DataType>::LinkList(DataType a[], int n) //尾插法
{
DulNode<DataType> *s, *r;
first = new DulNode<DataType>;
r = first;
for (int i = 0; i < n; i++)
{
s = new DulNode<DataType>;
s->data = a[i];
r->next = s;
r= s;
}
r->next = NULL;
}
//无参构造函数
template<class DataType>
LinkList<DataType>::LinkList()
{
DulNode<DataType>*p;
first=p; //生成头结点
first->next=NULL; //头结点的next指针域置空
first->prior=NULL;
}
//析构函数
template<class DataType>
LinkList<DataType>::~LinkList()
{
while (first!=NULL) {
DulNode<DataType> *p;
std::cout<<"我已经被销毁";
p=first; //暂存被释放结点
first=first->next; //指向下一个结点
delete p; //删除结点
}
}
int main(int argc, const char * argv[]) {
int n=0;
std::cout<<"你要录入的学生数量为";
std::cin>>n;
int a[]={50,60,70,80};
LinkList<int> Student(a,n);
std::cout<<"-----------";
Student.PrintList();
std::cout<<"在第三个位置插入一个成绩为20的学生";
Student.Insert(3, 20);
std::cout<<"-----------";
Student.PrintList();
std::cout<<"-----------";
std::cout<<"第三位学生的成绩"<<Student.Get(3);
std::cout<<"现在总学生数量为"<<Student.Length();
return 0;
}
上图的“我已经被销毁”，说明调用了四次析构函数删除了四个学生对象。
实验总结：
这次双链表实验与单链表大部分相似，通过next指针来寻找数据然后进行操作，不同的是插入与删除，要修改几个指针的指向,还算可以,加强了对指针的认识。