typedef struct LNode{       //定义单链表结点类型
 ? ElemType data;           //每个结点存放一个数据元素
 ? struct LNode *next;      //指针指向下一个结点
}LNode,*LinkList;           //LinkList为指向结构体Lnode的指针类型

3、单链表的基本操作

3.1 初始化

//初始化一个空的单链表
bool InitList(LinkList &L){
    L=new LNode;//或L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;       //空表，暂时还没有任何结点。防止脏数据
    return OK;
}

3.2 判断空表

int LIstEmpty(LinkList L){//若L为空表，贼返回1，否则返回0
    if(L—>next)//非空
        return 0;
    else
        return 1;
}

3.3 销毁

L指向头结点的指针域，这样就指向了下一个结点，然后再指向下一个结点的指针域，不断操作，销毁单链表

Status DestroyList_L(LinkLIst &L){
    Lnode *p;//LinkList p;
    while(L){
        p=L;//将头结点的指针赋值给p,从头结点开始
        L=L->next;
        delete p;
    }
}

3.4 清空

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

算法思路：依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList & L){
    Lnode *p，*q；//或者LinkList p,q;
    p=L->next;
    while(p){   //没到表尾
        q=p->next;
        delete p;
        p=q;
    }
    L->next=NULL;   //头结点指针为空
    return OK;
}

3.5 求单链表的表长

int ListLength_L(LinkList L){
    LinkList p;
    p=L->next;
    i=0;
    while(p){
        i++；
        p=p->next;
    }
    return i;
}

3.6 取第i个元素值

Status GetElem_L(LinkList L,int i,ElemType &e){
    p=L->next;  //初始化
    j=1;        //初始化
    while(p&&j<i){  //向后扫描，直到p指向第i个元素或p为空
        p=p->next;
        j++;
    }
    if(!p\\j>i) return ERROR;   //第i个元素不存在
    e=p->data;                  //取第i个元素
    return OK;
}//GetElem_L

3.7 查找

3.7.1 按值查找

//按值查找，找到数据域==e的结点(带头结点)
LNode LocateElem(LinkList L,ElemType e){
 ? ?LNode p=L->next;
 ? ?//从第1个结点开始查找数据为e的结点
 ? ?while(p&&p->data!=e)
 ? ? ? ?p=p->next;
 ? ?return p;   //找到后返回该结点的指针，否则返回NULL
}

3.7.2 按位查找

//按位查找，返回第i个元素(带头结点)
LNode GetElem(LinkList L,int i){
 ? ?if(i<0)
 ? ? ? ?return NULL;
 ? ?LNode *p;               //指针p指向当前扫描到的结点
 ? ?int j=0;                //当前p指向的是第几个结点
 ? ?p=L;                    //L指向头结点，头结点是第0个结点(不存数据)
 ? ?while(p!=NULL&&j<i){    //循环找到第i个结点
 ? ? ? ?p=p->next;
 ? ? ? ?j++;
 ?  }
 ? ?return p;
}

3.8 插入

1）首先找到ai-1的存储位置p

2）生成一个数据域为e的新结点s

3）插入新结点：

新结点的指针域指向结点ai
结点ai-1的指针域指向新结点

第一步、将p指向的结点的指针域（原本下个结点的地址）赋值给s的指针域 s->next = p->next;

第二步、将s的指针域赋值给将p指向的结点的指针域（原本下个结点的地址）p->next = s

Status ListInsert_L(LinkLIst &L,int i,ElemType e){
    p=L;
    j=0;
    while(p&&j<i-1){//寻找第i-1结点，p指向i-1结点
        p=p->next;
        j++;
    }
    if(!p||j>i-1)//大于表长+1或者小于1，插入位置非法
        return ERROR;
 ? ?s=new LNode；//生成新结点s，将结点s的数据域置为e
 ? ?s->data = e;
 ? ?s->next = p->next;
 ? ?p->next = s;
 ? ?return OK;
}//ListInsert_L

3.9 删除

算法步骤：

第一步、首先找到ai-1的存储位置p，保存要删除的ai的值

第二步、令p->next指向ai-1；

将i的指针域（i+1的指针）指向i-1的指针域（i的指针）：p->next = p->next ->next

Status ListDelete_L(LinkList &L,int i,ElemType &e){
 ? ?p=L;
 ? ?j=0;
 ? ?while(p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱
 ? ? ? ?p=p->next;
 ? ? ? ?j++;
 ?  }
 ? ?if(!(p->next)||j>i-1)//删除位置不合适
 ? ? ? ?return ERROR;
 ? ?q=p->next;//临时保存被删结点的地址以备释放
 ? ?p->next=q->next//改变删除结点前驱结点的指针域
 ? ?e=q->data;//保存删除结点的数据域
 ? ?delete q;//释放删除结点的空间
 ? ?return OK;
}//ListDelete_L

4、建立单链表

4.1 头插法——每次插在头结点的后头

1）从一个空表开始，重复读入数据

2）生成新结点，将读入数据存放到新结点的数据域中

3）从最后一个结点开始，依次将各结点插入到链表的前端

void CreateList_H(LinkList &L,int n){
 ? ?//逆位序输入n个元素的值，建立带表头结点的单链表L
 ? ?L=(LinkList)malloc(sizeof(LNode));//L = new LNode
 ? ?L->next=NULL;           //先建立一个带头结点的空链表
 ? ?LNode *p;
 ? ?for(int i=n;i>0;i--){
 ? ? ? ?p=(LinkList)malloc(sizeof(LNode));//生成新结点*p
 ? ? ? ?cin>>p->data;       //输入元素值复制给新结点*p的数据域
 ? ? ? ?p->next=L->next;L->next=p;  //将新结点*p插入到头结点之后    
 ?  }
}

4.2 尾插法——元素插入在链表的尾部

void CReateLIst_R(LinkList &L,int n){
 ? ?//正位序输入n个元素的值，建立带表头结点的单链表L
 ? ?L=(LinkList)malloc(sizeof(LNode));
 ? ?L->next=NULL;       //先建立一个带头结点的空链表
 ? ?LNode *p;
 ? ?LNode *r=L；         //尾指针r指向头结点
 ? ?for(i=0;i<n;i++){
 ? ? ? ?p=(LinkList)malloc(sizeof(LNode));//生成新结点
 ? ? ? ?cin>>p->data;       //输入元素值复制给新结点*p的数据域
 ? ? ? ?p->next=NULL;       //新插入的结点指针置空
 ? ? ? ?r->next=p;          //将新结点*p插入尾结点*r之后
 ? ? ? ?r=p;                //r指向新的尾结点*p
 ?  }
}