///////////////////////////////////////////////////////////////////日期：2014-11-03//作者：Davis//功能：单链表的定义与操作实现/////////////////////////////////////////////////////////////////#pragma oncetemplate<class T>struct Node{    T data;     //数据域，存放表元素    Node *next; //指针域。指向下一个结点};template<class T>class linkList{private:    Node<T> *Head; //链表头指针public:    //构造函数、创建空链表    linkList(void)    {      Head = new Node<T>;      Head->next = NULL;    }    //析构函数、删除空链表    ~linkList(void)    {      Node<T> *p;      while(Head)      {        p = Head;//从头节点开始，依次释放结点        Head = Head->next;        delete p;      }      Head = NULL;//头结点指向空    }    //创建具有n个元素的线性链表    void createList(int n)    {                 //尾插法（正序）创建具有n个元素的线性表      Node<T> *p,*s;  //设置工作指针，p指向尾结点      p=Head;      cout<<"请依次输入"<<n<<"个元素值"<<endl;      for(int i=1;i<=n;i++)      {        s = new Node<T>;   //新建元素结点        cin>>s->data;      //输入新建数据元素值        s->next = p->next; //新结点链入表尾        p->next = s;        p = s;             //p是工作指针      }    }    //在表中第i个位置插入元素    void Insert(int i,T e)    {      int j = 0;      Node<T> *p;      p = Head;         //工作指针p指向头结点      while(p && j<i-1) //查找第i-1个结点      {        p = p->next;        j++;      }      if(!p || j>i-1)throw"位置异常";      else      {        Node<T> *s;        s = new Node<T>;  //创建新节点        s->data =http://www.mamicode.com/ e;        s->next = p->next;//结点s链到p结点之后        p->next = s;      }    }    T Delete(int i)//删除表中第i个元素    {          T x;        Node<T> *p,*q;        p = Head;  //从头结点开始查找        int j = 0; //计数器初始化        while(p->next && j<i-1)//p定位到删除结点的前驱        {          p = p->next;          j++;        }        if(!p->next || j>i-1)throw"位置异常";//删除位置不合理        else                                 //删除位置合理        {          q = p->next;      //暂存删除结点位置          p->next = q->next;//从链表中摘除删除结点          x = q->data;      //取删除数据元素的值          delete q;         //释放删除点          return x;         //返回删除元素的值        }     }    //获取第i个元素的值    T getElem(int i)    {      Node<T> *p;     //设置工作指针      p = Head->next; //从首结点开始      int j = 1;      //计数器初始化      while(p && j<i) //定位到第i个元素结点      {          p = p->next;          j++;      }      if(!p || j>i)      {          throw "位置异常";      }      else   //位置合理      {        return p->data;      }    }    //在链表中查找值为e的元素    int Locate(T e)    {      int j = 1;      Node<T> *p;      p = Head->next;      while(p && p->data != e)      {        p = p->next;        j++;      }      if(!p )//未找到，范围0      {          return 0;      }      else  //找到，返回位序      {          return j;      }    }    //返回元素e的前驱    T prior(T e)    {      Node<T> *p,*q;      p = Head;      q = p->next;      while(q && q->data != e)      {        p = q;        q = q->next;      }      if(p == Head)      {        throw "首元素，无前驱";      }      else if(!q)      {        throw "元素不存在";      }      else      {        return p->data;      }    }        //测表空    int Empty()    {      if(Head->next == NULL)          return 1; //空表返回1      else          return 0; //非空表，返回0    }    //测表长    int Length()    {      int len = 0; //计数器初始化      Node<T> *p;  //设置头指针      p=Head;      //指向头指针      while(p->next)      {        len++;        p = p->next;      }      return len;  //返回表长    }    //输出表元素    void listDisplay()    {      Node<T> *p;      p = Head->next;      int i = 1;      while(p)      {        cout<<i<<"\t";        cout<<p->data<<endl;        p = p->next;        i++;      }    }};///////////////////////////////////////////////////////////////////功能：单链表类的测试//////////////////////////////////////////////////////////////////// linkList_Test.cpp : 定义控制台应用程序的入口点。#include "stdafx.h"#include "linkList.h"#include "process.h"//exit()#include<iostream>using namespace std;char pause;typedef int T;int _tmain(int argc, _TCHAR* argv[]){    int i;    T e,prior_e;    linkList<int>L;   //建立整形空链表    system("cls");    //执行系统命令，清屏    int choice;    do    {      cout<<"1-创建链表\n";      cout<<"2-在链表第i个位置插入元素\n";      cout<<"3-删除链表中第i个位置的元素\n";      cout<<"4-返回第i个元素的值\n";      cout<<"5-元素定位\n";      cout<<"6-按值求前驱\n";      cout<<"7-测表空\n";      cout<<"8-测表长\n";      cout<<"9-显示链表\n";      cout<<"10-退出\n";      cout<<"Enter choice:";      cin>>choice;      switch(choice)      {      case 1://创建链表             cout<<"请输入要创建的链表中元素的个数:";             cin>>i;             cout<<endl;             L.createList(i);                      break;      case 2://元素插入           cout<<"请输入插入的位置";           cin>>i;           cout<<endl;           cout<<"请输入插入元素的值:";           cin>>e;           cout<<endl;           try           {               L.Insert(i,e);           }           catch(char* err)           {             cout<<err<<endl;           }           break;      case 3://元素删除          cout<<"请输入删除位置";          cin>>i;          cout<<endl;          try          {              e = L.Delete(i);              cout<<"被删除元素为："<<e<<endl;          }          catch(char* err)          {             cout<<err<<endl;          }          cin.get(pause);          system("pause");          break;      case 4://返回第i个元素值          cout<<"请输入要查询的元素位置:";          cin>>i;          try          {              e = L.getElem(i);              cout<<"第"<<i<<"个元素值为:"<<e<<endl;          }          catch(char* err)          {            cout<<err<<endl;          }          cin.get(pause);          system("pause");          break;      case 5://按值进行元素查询          cout<<"请输入要查询的元素值：";          cin>>e;          i = L.Locate(e);          cout<<"查询元素"<<e<<"在链表中的位置为："<<i<<endl;          cin.get(pause);          system("pause");          break;      case  6://求元素前驱          cout<<"请输入要求前驱元素的值：";          cin>>e;          try          {              prior_e = L.prior(e);              cout<<"元素"<<e<<"的前驱值为:"<<prior_e<<endl;          }          catch(char *err)          {            cout<<err<<endl;          }          cin.get(pause);          system("pause");          break;      case 7://测表空          i = L.Empty();          if(i)          {            cout<<"表空"<<endl;          }          else          {            cout<<"表不空"<<endl;          }          cin.get(pause);          system("pause");          break;      case 8://测表长          cout<<"链表长度为:"<<L.Length()<<endl;          cin.get(pause);          system("pause");          break;      case 9://遍历输出表          L.listDisplay();          cout<<endl;          cin.get(pause);          system("pause");          break;      case 10://退出          break;      default://非法选择          cout<<"Invalid choice";          break;      }           }while(choice != 10);    return 0;}