C++： 单链表的基本操作实现

能够实现对链表的初始化、插入、删除、链表清空以及取值等一系列基本操作

代码片段

1、 自定义状态

部分操作可以通过返回值来验证是否能够执行

#define OK 1			
#define ERROR 0
typedef int Status;
typedef int ElemType;

2、单链表初始化

Status InitList_L(LinkList &L){
    L=new LNode;
    L->next=NULL;
    return OK;
}

3、判断链表是否为空，为空返回1，非空返回0

int ListEmpty(LinkList L){
    if(L->next)//非空
        return 0;
    else
        return 1;
}

4、单链表的销毁

Status DestroyList_L(LinkList &L){
    LNode *p;
    while(L){
    p=L;
    L=L->next;
    delete p;
    }
    return OK;
}

5、清空单链表（头指针和头节点仍然在）

Status ClearList_L(LinkList &L){
    LNode *p=L->next;       //  让p指向首元节点
    LNode *q;
    while(p){
        q=p;
        p=p->next;
        delete q;
    }
    delete p;
    L->next=NULL;
    return OK;
}

6、求单链表的表长

int GetListLength(LinkList L){
    int len=0;
    LNode *p=L->next;
    while(p){
        p=p->next;
        len++;
    }
    return len;
}

7、取单链表中第i个元素的data

Status GetElem_L(LinkList L,int i,ElemType &e){
    LinkList p=L->next;
    int j=1;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    if(!p||j>i)return ERROR;
    e=p->data;
    return OK;
}

8、按值查找————返回数据所在地址

LNode *GetElemLocation(LinkList L,ElemType e){
    //找到返回L中为e的数据元素的地址，查找失败返回NULL
    LinkList p=L->next;
    while(p&&p->data!=e) p=p->next;
    return p;
}

9、按值查找二————返回数据是链表的序号

int LocateElem_L(LinkList L,ElemType e){
    int i=1;
    LinkList p=L->next;
    while(p&&p->data!=e) {
        p = p->next;
        i++;
    }
    if(p) return i;
    else return 0;
}

10、插入————在第i个节点之前插入结点

Status InsertElem_L(LinkList &L,int i,ElemType e){
    LinkList p;
    p=L;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    LinkList s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

11、删除第i个节点

Status DeleteElem_L(LinkList &L,int i,ElemType &e){
    int j=0;
    LinkList p=L;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if((!p->next)||j>i-1) return ERROR;
    LinkList q=p->next;
    e=q->data;
    p->next=p->next->next;
    delete q;
    return OK;
}

12、头插法———元素插在链表头部，n表示生成链表的长度

void CreateList_H(LinkList &L,int n){  
//插入时因为是插入在头部，所以链表元素顺序与输入顺序相反
    L=new LNode;
    L->next=NULL;
    for(int i=n;i>0;i--){
        LinkList p=new LNode;
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}

13、尾插法——元素插入在链表尾部

void CreateList_R(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++){
        LinkList p=new LNode;
        p->next=NULL;
        cin>>p->data;
        r->next=p;
        r=p;
    }
}

14、打印链表信息

若链表为空则直接打印链表为空，否则依次打印 第i位的data

void PrintList(LinkList L){
    LinkList p=L->next;
    int i=1;
    if(!p) {
        cout<<"链表为空"<<endl;
        return;
    }
    while(p){
        cout<<"第"<<i<<"个结点为 : "<<p->data<<"  ";
        i++;
        p=p->next;
    }
    cout<<endl;
    cout<<"此时链表长度为"<<i-1<<endl;
}

完整代码

#include <bits/stdc++.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
using namespace std;
//结点定义
typedef struct LNode{
    int data;                       //数据域
    struct LNode *next;             //指针域
}LNode,*LinkList;
//单链表初始化
Status InitList_L(LinkList &L){
    L=new LNode;
    L->next=NULL;
    return OK;
}
//判断链表是否为空，为空返回1，非空返回0
int ListEmpty(LinkList L){
    if(L->next)//非空
        return 0;
    else
        return 1;
}
//单链表的销毁
//顺着链表从头结点依次向后释放结点
Status DestroyList_L(LinkList &L){
    LNode *p;
    while(L){
    p=L;
    L=L->next;
    delete p;
    }
    return OK;
}
//清空单链表（头指针和头节点仍然在）
Status ClearList_L(LinkList &L){
    LNode *p=L->next;       //  让p指向首元节点
    LNode *q;
    while(p){
        q=p;
        p=p->next;
        delete q;
    }
    delete p;
    L->next=NULL;
    return OK;
}
//求单链表的表长
int GetListLength(LinkList L){
    int len=0;
    LNode *p=L->next;
    while(p){
        p=p->next;
        len++;
    }
    return len;
}
//取单链表中第i个元素的data
Status GetElem_L(LinkList L,int i,ElemType &e){
    LinkList p=L->next;
    int j=1;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    if(!p||j>i)return ERROR;
    e=p->data;
    return OK;
}
//按值查找一————返回数据所在地址
LNode *GetElemLocation(LinkList L,ElemType e){
    //找到返回L中为e的数据元素的地址，查找失败返回NULL
    LinkList p=L->next;
    while(p&&p->data!=e) p=p->next;
    return p;
}
//按值查找二————返回数据是链表的序号
int LocateElem_L(LinkList L,ElemType e){
    int i=1;
    LinkList p=L->next;
    while(p&&p->data!=e) {
        p = p->next;
        i++;
    }
    if(p) return i;
    else return 0;
}
//插入————在第i个节点之前插入结点
Status InsertElem_L(LinkList &L,int i,ElemType e){
    LinkList p;
    p=L;
    int j=0;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1) return ERROR;
    LinkList s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
//删除第i个节点
Status DeleteElem_L(LinkList &L,int i,ElemType &e){
    int j=0;
    LinkList p=L;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if((!p->next)||j>i-1) return ERROR;
    LinkList q=p->next;
    e=q->data;
    p->next=p->next->next;
    delete q;
    return OK;
}
//头插法—————元素插在链表头部，n表示生成链表的长度
void CreateList_H(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    for(int i=n;i>0;i--){
        LinkList p=new LNode;
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}
//尾插法————元素插入在链表尾部
void CreateList_R(LinkList &L,int n){
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++){
        LinkList p=new LNode;
        p->next=NULL;
        cin>>p->data;
        r->next=p;
        r=p;
    }
}
//打印链表数据，若链表为空则直接打印链表为空，否则依次打印 第i位的data
void PrintList(LinkList L){
    LinkList p=L->next;
    int i=1;
    if(!p) {
        cout<<"链表为空"<<endl;
        return;
    }
    while(p){
        cout<<"第"<<i<<"个结点为 : "<<p->data<<"  ";
        i++;
        p=p->next;
    }
    cout<<endl;
    cout<<"此时链表长度为"<<i-1<<endl;
}

int main(){
    LinkList L;             //首先要初始化结点，也可以调用InitList_L函数
    CreateList_H(L,5);      //生成长度为5的链表
    PrintList(L);           //打印链表元素
    InsertElem_L(L,3,6);    //在链表元素的第3位插入data为6的元素
    PrintList(L);
    int e;
    DeleteElem_L(L,3,e);    //删除链表元素时用e来接收删除元素的data值
    cout<<e<<endl;
    PrintList(L);
    cout<<ListEmpty(L)<<endl;
    ClearList_L(L);
    PrintList(L);
    return 0;
}

代码执行结果

第一次写博客，如有问题，敬请指正
后面有机会也会接着更新新的内容