[数据结构与算法]线性表的链接存储结构

LinkList.h:

#ifndef LINKLIST_H
#define LINKLIST_
#include<iostream>
using namespace std;
//定义
template<class DataType>
struct Node
{
      DataType data;
      Node<DataType> *next;
};

template <class DataType>
class LinkList
{
public:
	LinkList();                     //无参构造函数，建立只有头结点的空链表
	LinkList(DataType a[], int n);  //有参构造函数，建立有n个元素的单链表
	~LinkList();                    //析构函数
	int Length();                   //获取当前长度
	int Empty();			//判断单链表是否为空
	DataType Get(int i);       //按位查找
	int Locate(DataType x);           //按值查找。在单链表中查找值为x的元素序号
	void Insert(int i, DataType x);      //插入操作，第i个位置插入元素值为x的结点
	DataType Delete(int i);           //删除操作，在单链表中删除第i个结点
	void PrintList();                 //遍历操作，按序号依次输出各元素
private:
	Node<DataType> *first;                     //单链表的头指针
};


#endif // LINKLIST_H

LinkList.cpp:

#include "LinkList.h"

template<class DataType>
LinkList<DataType>::LinkList(){
    first = new Node<DataType>;
    first->next = nullptr;
}
/*
    创建单链表（头插法和尾插法）
*/
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n){
    first = new Node<DataType>;
    first->next = nullptr;  //初始化一个空链表

    //头插法
   /* Node<DataType> *p;
    for(int i;i < n;++i){
        p = new Node<DataType>;
        p->data = a[i];
        p->next = first->next;  //将结点s插入到头结点之后
        first->next = p;
        p->next = first->next;
    }*/

    //尾插法
    Node<DataType> *p,*r; //p为工作指针，r为尾指针
    r = first;  //尾指针初始化
    for(int i = 0;i < n;++i){
        p = new Node<DataType>;
        p->data = a[i];
        r->next = p;
        r = p;
    }
    r->next = nullptr;//单链表建立完毕，将终端结点的指针域置空

}
//析构函数
template<class DataType>
LinkList<DataType>::~LinkList(){
    Node<DataType> *p;
    while(first != nullptr){
        p = first;
        first = first->next;
        delete p;
    }
}

template<class DataType>
int LinkList<DataType>::Length(){
    Node<DataType> *p = first->next;
    int count = 0;
    while(p != nullptr){
        count++;
        p = p->next;
    }
    return count;//长度为count
}

template<class DataType>
int LinkList<DataType>::Empty(){
    if(first->next == nullptr)
        return 1;
    else
        return 0;
}

template<class DataType>
DataType LinkList<DataType>::Get(int i){
    Node<DataType> *p = first->next;
    int count = 0;
    while(p != nullptr && count < i - 1){
        p = p->next;
        count++;
    }
    if(p = nullptr) throw"查找位置非法";
    else return p->data;
}

template<class DataType>
int LinkList<DataType>::Locate(DataType x){
    Node<DataType> *p = first->next;
    int count = 0;  //对应第一位
    while(p != nullptr){
        if(p->data == x)
            return count + 1; //对应第count位
        count ++;
        p = p->next;
    }
    return 0;
}

template<class DataType>
void LinkList<DataType>::Insert(int i,DataType x){
    Node<DataType> *s,*p = first;
    int count = 0;
    while(p != nullptr && count < i-1){ //令p指向第i-1个结点
        p = p->next;
        count++;
    }
    if(p == nullptr) throw"插入位置错误";
    //在p后插入结点
    else{
        s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

template<class DataType>
DataType LinkList<DataType>::Delete(int i){
    Node<DataType> *s,*p = first;
    int count = 0;
    DataType x;
    while(p != nullptr && count < i-1){//令p指向第i-1个结点
        p = p->next;
        count++;
    }
    if(p == nullptr) throw"删除位置错误";
    //删除第i个结点
    else{
        s = new Node<DataType>;
        s= p->next;
        x = s->data;
        p->next = s->next;
        delete s;
        return x;
    }
}

template<class DataType>
void LinkList<DataType>::PrintList(){
    Node<DataType> *p = first->next;
    while(p != nullptr){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

main.cpp:

#include"LinkList.cpp"

int main()
{
  int len;
  double r[5]={1, 2, 3, 4, 5};
  LinkList<double> L(r, 5);
  cout<<"执行插入操作前数据为："<<endl;
  L.PrintList( );                  //显示链表中所有元素
  cout<<"当前长度为："<<endl;
  len = L.Length();
  cout<<len<<endl;
  try
  {
    L.Insert(2, 3);
  }
  catch (char *s)
  {
    cout<<s<<endl;
  }
  cout<<"执行插入操作后数据为："<<endl;
  L.PrintList( );                  //显示链表中所有元素
  cout<<"值为5的元素位置为:";
  cout<<L.Locate(5)<<endl;        //查找元素5，并返回在单链表中位置
  cout<<"执行删除操作前数据为："<<endl;
  L.PrintList( );                  //显示链表中所有元素
  try
  {
    L.Delete(1);                    //删除元素4
  }
  catch (char *s)
  {
    cout<<s<<endl;
  }
  cout<<"执行删除操作后数据为："<<endl;
  L.PrintList( );                  //显示链表中所有元
    return 0;
}