数据结构 单一列表

#ifndef LINKLIST_H

#define LINKLIST_H

#include<iostream>

using namespace std;

template <typename T>

struct Node

{

 T data;

 Node<T> *next;

};

template <typename T>

class LinkList

{

public:

 LinkList();                       //无參构造函数，建立仅仅有头结点的空链表

 LinkList(T a[], int n);           //有參构造函数，建立由n个元素的单链表

 ~LinkList();                      //析构函数

 int Length();                     //求单链表的长度

 T Get(int i);                     //按位查找，查找单链表中的第i个元素的数值

 int Locate(T x);                  //查找该元素在单链表中的位置

 void Insert(int i, T x);          //在第i个位置插入该元素

 T Delete(int i);                  //删除第i个元素

 void PrintList();                 //打印单链表

private:

 Node<T> *first;                  //创建单链表的头指针

};

template <typename T>

LinkList<T>::LinkList()

{

 Node<T> *first;                  //申明头结点

 first = new Node<T>;             //生成头结点

 first->next = NULL;              //初始化头节点

}

template <typename T>

LinkList<T>::LinkList(T a[], int n)

{

 Node<T> *r, *s;                //申明两个暂时结点

 first = new Node<T>;           //生成头结点

 r = first;                     //尾指针初始化

 for (int i = 0; i < n; i++)

 {

  s = new Node<T>;           //生成S结点来存储数组中相应的元素

  s->data = a[i];            //将数组中相应的元素赋值到相应结点的数值部位

  r->next = s;              

  r = s;                     //上两部是将s插入到终端结点之后

 }

 r->next = NULL;

}

template <typename T>

LinkList<T>::~LinkList()

{

 Node<T> *q = NULL;            //建立一个空的结点

 while (first != NULL)         //该循环释放结点的存储空间

 {

  q = first;

  first = first->next;

  delete q;

 }

}

template <typename T>

int LinkList<T>::Length()

{

 Node<T>*p=first->next;

 int count = 0;                   //初始化

 while (p != NULL)

 {

  p = p->next;                //p指针后移

  count++;

 }

 return count;

}

template <typename T>

T LinkList<T>::Get(int i)

{

 Node<T> *p = first->next;

 int count = 1;

 while (p != NULL&&count < i)

 {

  p = p->next;

  count++;

 }

 if (p == NULL)throw”位置”;

 else return p->data;           //单恋表中first是空结点，不算在单链表中的。所以第一个元素是在第一个结点中的。序号是相应的

}

template <typename T>

int LinkList<T>::Locate(T x)

{

 Node<T> *p = first->next;

 int count = 1;               //上述初始化工作量

 while (p != NULL)

 {

  if (p->data == x)

   return count;

  p = p->next;

  count++;

 }

 return 0;                    //推出循环查找，表示查找失败。

}
template <typename T>
void LinkList<T>::Insert(int i, T x)
{
 Node<T> *p = first;
 int count = 0;               //上述初始化工作量
 while (p != NULL&&count < i – 1)
 {
  p = p->next;
  count++;
 }
 if (p == NULL)throw”位置”;
 else
 {
  Node<T> *s;
  s = new Node<T>;
  s->data = x;
  s->next = p->next;
  p->next = s;
 }
}
template <typename T>
T LinkList<T>::Delete(int i)
{
 Node<T> *p = first;
 T x;
 int count = 0;
 while (p != NULL&&count < i – 1)
 {
  p = p->next;
  count++;
 }
 if (p == NULL || p->next == NULL)throw”位置”;
 else
 {
  Node<T> *q;
  q = p->next; x = q->data;
  p->next = q->next;
  delete q; return x;
 }
}
template <typename T>
void LinkList<T>::PrintList()
{
 Node<T> *p;
 p = first->next;
 while (p != NULL)
 {
  cout << p->data<<“->”;
  p = p->next;
 }
}
#endif
*******************************************************************
#include”LinkList.h”
#include<iostream>
#include<iomanip>
using namespace std;
void main()
{
 int a[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
 int ch;
 LinkList<int> zxh(a,10);
 cout << “生成的单链表为:”;
 zxh.PrintList();
 cout << endl;
 cout << “1-求长度”<<setw(17);
 cout << “2-按位查找” << endl;
 cout << “3-按值查找” << setw(15);
 cout << “4-插入操作” << endl;
 cout << “5-删除操作” << setw(15);
 cout << “6-遍历操作” << endl;
 cout << “请输入您想进行的操作:”;
 cin >> ch;
 switch (ch)
 {
 case 1:zxh.Length(); break;
 case 2:int m1;
  cout << “请输入您想按位查找的位号:”;
  cin >> m1;
  zxh.Get(m1); break;
 case 3:
  int m2;
  cout << “请输入您想查找的值:”;
  cin >> m2;
  zxh.Locate(m2); break;
 case 4:int m3, m4;
  cout << “请输入想插入的位置:”;
  cin >> m3;
  cout << “请输入想插入的元素:”;
  cin >> m4;
  zxh.Insert(m3, m4); break;
 case 5:
  int m5;
  cout << “请输入想删除的位置:”;
  cin >> m5;
  zxh.Delete(m5); break;
 case 6:
  zxh.PrintList();
 }
}
这个单恋表中我自己刚才測试了一下。

基本上没什么大问题。

但似乎球的时间长短是不正确的。我希望我们能提出作证。