链表基础操作
照着大话数据结构码的，学校课本看不太懂

#include <iostream>
using namespace std;

typedef struct LNode { //常用的结构体指针定义 
    int data;
    struct LNode* next;
}LNode, * LinkList;     //LinkList等价于LNode*,LNode强调于结点，LinkList强调于整个链表 

//初始化
bool InitList(LinkList& L) { //初始化链表只存在头节点 
    L = (LinkList)malloc(sizeof(LNode));//为头节点申请空间 
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

//单链表是否为空
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    }
    else {
        return false;
    }
}

//单链表的创建
void CreateListHead(LinkList& L, int n) {    //头插法
    LinkList p;
    for (int i = 0; i < n; i++) {//迭代n次 
        p = (LinkList)malloc(sizeof(LNode));
        cin >> p->data;

        p->next = L->next;
        L->next = p;//把节点p插到头节点L与L->next之间 
    }
}
void CreateListTail(LinkList& L, int n) {    //尾插法
    L = (LinkList)malloc(sizeof(LNode));
    LinkList p, r;
    r = L;          //先将r定义为头节点,r从头节点开始向后迭代 
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(LNode));
        cin >> p->data;
        r->next = p;//r后插入p 
        r = p;      //保证链表的最后元素一直为r 
    }
    r->next = NULL;    //最后一个结点指针指向NULL
}
//插入操作(存在头结点)        注：空链表插入时，插入位置只能为1 
bool InsertList(LinkList& L, int i, int e) {//在表L第i个位置之前插入元素e 
    if (i < 1)return false;//插入位置不合法 
    LinkList p;
    int j = 0;
    p = L;
    while (p && j < i - 1) { //插入时i-1位置为节点p 
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return false;
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
//删除操作
bool DeleteList(LinkList L, int i) {//删除表L的第i个元素，并用e返回其值 
    LinkList p, q;
    p = L;
    int j = 0;
    while (p->next && j < i - 1) { //删除时i位置为节点p->next 
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i - 1)return false;
    q = p->next;
    p->next = q->next;
    free(q);
    return true;
}
//删除指定元素elem 
void DeleteElems(LinkList L, int elem) {
    LNode* p, * q, * pre; //LNodep为工作指针，q指向需要删除的指针, pre始终为当前指针的前一位，类似双链表
    p = L->next;   //让p指向第一个节点，跳过头节点
    pre = L;       //pre先指向头节点， 
    while (p != NULL)
    {
        if (p->data == elem)
        {
            q = p;        //q指针指向需要删除的指针
            p = p->next;  //工作指针跳到下一个位置
            pre->next = p;//此时，可以理解为前驱节点跳过要删除的点，next指向P
            free(q);//释放内存
        }
        else             //没有找到elem 
        {
            pre = p;
            p = p->next;
        }
    }
}

//按位置查找值 
int GetElem_L(LinkList& L, int i, int& e) {
    LinkList p;
    int j;
    p = L, j = 0;
    while (p && j < i - 1) {
        p = p->next, j++;
    }
    if (!p || j > i - 1) return false;
    e = p->next->data;
    return e;
}

//按值查找位置 
void Locate_L(LinkList& L, int e) {
    LinkList p;
    int j;
    p = L, j = 0;
    while (1) {
        p = p->next; j++;
        if (p->data == e) {
            cout << "位置为：" << j << endl;
            break;
        }
    }
}

//遍历输出
void PrintList(LinkList& L) {
    LinkList p = L->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
//整表删除
void ClearList(LinkList& L) {
    LinkList p, q;
    p = L->next;
    while (p) {
        q = p->next;
        free(q);
        p = q;
    }
    L->next = NULL;
}
int main() {
    LinkList L;
    InitList(L);
    int n;
    cout << "初始数据元素个数n=";
    cin >> n;
    cout << "请输入单链表数据：";
    CreateListTail(L, n);            //用的尾插法
    int choice, i, e;
    do {
        cout << "输入选择(1.插入，2.以位置删除，3.以元素删除，4.按位查找，5.按值查找，6.输出，7.链表是否为空 8.清空链表 9.结束进程) " << endl;
        cout << "choice = ";
        cin >> choice;
        switch (choice) {
        case 1:
            cout << "输入插入位置和元素：";
            cin >> i >> e;
            InsertList(L, i, e);
            break;
        case 2:
            cout << "输入删除位置：";
            cin >> i;
            DeleteList(L, i);
            break;
        case 3:
            cout << "输入删除元素：";
            cin >> e;
            DeleteElems(L, e);
            break;
        case 4:
            cout << "输入查找位置：";
            cin >> i;
            cout << "查找元素为：" << GetElem_L(L, i, e) << endl;
            break;
        case 5:
            cout << "输入查找元素：";
            cin >> e;
            Locate_L(L, e);
            break;
        case 6:
            cout << "输出链表：" << endl;
            PrintList(L);
            break;
        case 7:
            if (Empty(L))
                cout << "链表为空." << endl;
            else
                cout << "链表不为空." << endl;
            break;
        case 8:
            ClearList(L);
            break;
        case 9:
            exit(1);
        default:
            cout << "不存在" << endl;
        }
    } while (1);

    system("pause");
    return 0;
}