欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的创建、增删改查

程序员文章站 2024-03-23 16:54:40
...

单链表的创建、增删改查:

#include <iostream>
#include <stdio.h>
using namespace std;

//定义节点(单链表的存储结构:数据域 + 指针域)
typedef struct LNode{
    int data;
    LNode * next;
}LNode, *LinkList;

//头插法创建链表
void CreatList_H(LinkList &L, int n){    //n 为待创建链表中元素个数
    //创建头结点
    L = new LNode;
    L->data = 0;
    L->next = NULL;

    //头插法创建链表
    for(int i=0; i<n; i++){
        LinkList p = new LNode;
        cin >> p->data;

        p->next = L->next;
        L->next = p;
    }
}

//尾插法创建链表
void CreatList_R(LinkList &L, int n){    //n 为待创建链表中元素个数
    //创建头结点
    L = new LNode;
    L->data = 0;
    L->next = NULL;
    LinkList r = L;     //定义尾指针 r 指向头结点 L

    //尾插法创建链表
    for(int i=0; i<n; i++){
        LinkList p = new LNode;
        cin >> p->data;
        p->next = NULL;

        r->next = p;    //向尾结点 r 后添加新结点 p
        r = p;         //r 指向新的尾结点 p
    }
}

//单链表的取值(取第 i 个值 为 e )
void GetElem(LinkList L, int i, int &e){
    LinkList p;
    p = L->next;  int j = 1;   //p 指向首元结点 , j 为计数器
    while(p && j<i){
        p = p->next;
        j++;
    }
    if(!p || j>i){
        return ;
    }
    e = p->data;
    return ;
}

//单链表的查找(查找结点值为 e 的结点地址 p)
LNode* LocateElem(LinkList L, int e){
    LinkList p;
    p = L->next;               //p 指向首元结点
    while(p && p->data!=e){
        p = p->next;
    }
    return p;
}

//单链表的插入(在第 i 位置插入值为 e 的结点)
void ListInsert(LinkList &L, int i, int e){
    LinkList p;
    p = L; int j = 0;  //j 为计数器
    while(p && j<(i-1)){
        p = p->next;
        j++;
    }    //查找第 i-1 个结点
    if(!p || j>(i-1)){
        return ;
    }
    //查找到了,此时p 指向第 i-1 个结点
    LinkList s;
    s = new LNode;
    s->data = e;
    s->next = p->next;   //让s 的后继结点为之前的第 i 个结点
    p->next = s;         //让p 的后继结点换为 s
    return ;
}

//删除(删除第 i 个结点)
void ListDelete(LinkList &L, int i){
    //首先查找到第 i-1 个结点
    LinkList p;
    p = L; int j = 0;  //j 为计数器
    while(p && j<(i-1)){
        p = p->next;
        j++;
    }
    if(!p || j>i-1){
        return ;
    }
    //查找到了,此时p 指向第 i-1 个结点
    if(!p->next){
        return ;
    }//第 i 个结点不存在

    //第 i 个结点存在
    LinkList q = p->next;   //q 记录第 i 个结点, 后面进行释放空间
    //让第 i-1 个结点指向第 i+1 个结点
    p->next = p->next->next;
    //释放空间
    delete q;
    return ;

}

int main()
{
    //创建一个单链表
    LinkList L;
    cout<<"请输入n和n个数据\n";
    int n;
    cin>>n;
    CreatList_R(L, n);

    //删
//    cout<<"请输入删除第几个结点\n";
//    int i;
//    cin>>i;
//    ListDelete(L, i);

    //插
//    cout<<"请输入在第i个位置插入结点e\n";
//    int i, e;
//    cin>>i>>e;
//    ListInsert(L, i, e);

    //取值
//    int i, e;
//    cout<<"请输入要取第i个结点的值\n";
//    cin>>i;
//    GetElem(L, i, e);
//    printf("所取值为:%d\n", e);

    //查找
//    int e;
//    cout<<"请输入要查找的结点的值e\n";
//    cin>>e;
//    LinkList q = LocateElem(L, e);
//    printf("所查结点地址为:%d\n", q);
//    printf("所查结点的值为:%d\n", q->data);

    //输出单链表
    LinkList p = L->next;
    while(p!=NULL){
        printf("%d ", p->data);
        p = p->next;
    }


    return 0;
}