数据结构

typedef struct{
  elemType data;//结点数据域
  struct LNode* next;//结点指针域
}LNode,*linkList;

头文件 head.h

#include<iostream>
#define MAXSIZE 100  //最大表长100
//#define OK 1
//#define ERROR 0
//为使读者更易理解，一下代码不采用宏定义的OK,ERROR
using namespace std;

typedef int status;  //int实型
typedef int elemType;//int实型

一、初始化

（1）生成新节点作为头结点，用头指针L直线头结点

（2）头结点指针域置空

代码实现

status init_List(linkList &L){
  L=new LNode;
  L->next=NULL;
  return 1;
}

二、单链表取值

（1）用指针p指向首元结点，用j作为计数器并赋值为1

（2）从首元结点开始依次顺着链域next向下访问，只要指针p不为空（NULL），并且没有达到序号为i的节点，可以执行以下操作：

          p指向下一个节点

          计数器+1

代码实现

status get_Elem(linkList L,int i,elemType &e){
   LNode* p;
   p=L->next;
   j=1;
   while(p&&j<1){
      p=p->next;
      ++j;
   }
   if(!p||j>1)
      return 0;
   e=p->data;
   return 1;
}

三、查找

（1）用指针p指向首元结点

（2）从首元结点开始依次顺着链域next向下访问，只要指针p不为空（NULL），并且p指向的节点的数据域不为e值，可以执行以下操作：

          p指向下一个节点

（3）返回p。若查找成功，p为该节点的地址，若失败，p=NULL

代码实现

LNode* locate_List(linkList L,elemType e){
   LNode* p;
   p=L->next;
   while(p&&p->data!=e)
      p=p->next;
   return p;
}

四、删除

（1）查找节点Xi-1，用指针p指向该节点

（2）临时保存要删除节点ai的地址在e里

（3）将节点*p的指针域指向Xi-1的后继节点

（4）释放节点ai空间

代码实现

status delete_List(linkList &L,int i){
   LNode* p=L;
   int j=0;
   while(p->next && j<i-1){
      p=p->next;
      ++j;
   }
   if(!p->next||j>i-1)
      return 0;
   linkList q;
   p->next=q->next;
   delete q;
   return 1;
}

附加：插入之前插法

（1）创建只有一个头结点的空的单链表

（2）确定元素个数，假设为n，则循环n次执行下面的操作

         生成节点*p；

         输入*p的数据域；

         将新的节点*p插入到头结点的后面;

时间复杂度O(n)

代码实现

void create_List_Head(linkList &L,int n){
   L=new LNode;
   LNode* p;
   L->next=NULL;
   for (int i=0;i<n;i++){
      p=new LNode;
      cout<<"Please insert elem "<<i<<endl;
      cin>>p->data;
      p->next=L->next;
      L->next=p;//新节点插入头结点后面
   }
}

插入之后插法

（1）创建只有一个头结点的空的单链表

（2）初始化尾指针tail 并指向头结点

（3）确定插入元素个数，假设为n，则循环n次执行下面的操作

         生成节点*p;

         输入*p的数据域；

         将新节点*p插入到尾结点*tail后面

         尾指针tail指向新的尾结点*p；

代码实现

void create_List_Tail(linkList &L,int n){
   L=new LNode;
   L->next=NULL;
   LNode* tail=L;
   for (int i=0;i<n;i++){
      p=new LNode;
      cout<<"Please insert elem "<<i<<endl;
      cin>>p->data;
      p->next=NULL;
      tail->next=p;
      tail=p;
   }
}