MENU

数据结构:单链表

October 5, 2020 • 算法

在 g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 测试下通过
/*
* ===============================================
* Filename: homework.cpp
* Description: 数据结构 单链表 来源于数据结构书P29
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
#define OK 1
#define ERR 0
using namespace std;
const int N = 1e6 + 10;
int a[N];

typedef int ElemType;
typedef int Status;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

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

Status GetElem(LinkList L, int i, ElemType &e)
{
    // 访问链表L的第i个元素,利用e进行返回
    LNode *p = L -> next;
    int j = 1;
    while (p && j < i)
    {
        p = p -> next;
        j++;
    }
    if (!p || j > i) return ERR;
    e = p -> data;
    return OK;
}


LNode *LocateElem(LinkList L, ElemType e)
{
    // 在单链表L中查找值为e的元素
    LNode *p = L -> next;
    while (p && p -> data != e)
    {
        p = p -> next;
    }
    return p;
    // 查找成功返回e元素所在地址,否则返回NULL
}

Status ListInsert(LinkList &L, int i, ElemType e)
{
    // 在单链表L的第i个位置插入元素e
    LNode *p = L;
    int j = 0;
    while (p && (j < i - 1))
    {
        p = p -> next;
        j++;
    }
    if (!p || j > i - 1) return ERR;
    LNode *s = new LNode;
    s -> data = e;
    s -> next = p -> next;
    p -> next = s;
    return OK;
}

Status ListDelete(LinkList &L, int i)
{
    // 删除单链表L的第i个元素
    LNode *p = L;
    int j = 0;
    while ((p -> next) && (j < i - 1))
    {
        p = p -> next;
        j++;
    }
    if (!(p -> next) || (j > i - 1)) return ERR;
    LNode *q = p -> next;
    p -> next = q -> next;
    delete q;
    return OK;
}

void CreatLinkList(LinkList &L, int n)
{
    // 逆位元输入n个元素的值,建立单链表L
    L = new LNode;
    L -> next = NULL;
    while (n--)
    {
        LNode *p = new LNode;
        cin >> p -> data;
        p -> next = L -> next;
        L -> next = p;
    }
}

void CreatLinkList_R(LinkList &L, int n)
{
    // 正序输入n个元素的值,建立带表头结点的单链表L
    L = new LNode;
    L -> next = NULL;
    LNode *r = L;
    while (n--)
    {
        LNode *p = new LNode;
        cin >> p -> data;
        p -> next = NULL;
        r -> next = p;
        r = p;
    }
    return ;
}

void ShowLinkList(LinkList L)
{
    LNode *p = L -> next;
    while (p != NULL)
    {
        cout << p -> data << endl;
        p = p -> next;
    }
    cout << "====================" << endl;
}

int main()
{
    LinkList L;
    
    // 逆序创建单链表 
    CreatLinkList(L, 10);
    ShowLinkList(L);

    // 顺序创建单链表
    CreatLinkList_R(L, 10);
    ShowLinkList(L);

    // 上述两种方式只选用一种 //
    // =============== CUT =============== //

    // 删除单链表元素
    ListDelete(L, 3);
    ShowLinkList(L);
    
    // 插入单链表元素
    ListInsert(L, 3, 99);
    ShowLinkList(L);
    
    // 获取单链表元素
    ElemType a;
    GetElem(L, 7, a);
    cout << a << endl;
    return 0;
}
/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-10-19 19:56:44
 * @Website: https://grimoire.cn
 * @Description: 单链表 博主手撸版本,简化了一些复杂的东西
 * @Copyright 2020 Mr.Sen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;

typedef struct LNode{
    int data;
    LNode *next;
}*LinkList, LNode;

LinkList creatList(int len)
{
    // 尾插法创建链表
    LinkList Head = new LNode;
    LinkList Tail = new LNode;
    Head -> next = NULL; Tail = Head;

    while (len--)
    {
        LinkList node = new LNode;
        cin >> node -> data;
        node -> next = NULL;
        Tail -> next = node;
        Tail = node;
    }
    return Head;
}

LinkList creatListTail(int len)
{
    // 头插法创建单链表
    LinkList Head = new LNode;
    Head -> next = NULL;
    while(len--)
    {
        LinkList node = new LNode;
        cin >> node -> data;
        node -> next = Head -> next;
        Head -> next = node;
    }
    return Head;
}

void print(LinkList L)
{
    while (L -> next)
    {
        L = L -> next;
        printf("%d ", L -> data);
    }
    cout << endl;
    return ;
}

int getElem(LinkList Head, int index)
{
    // 头结点作为零号节点
    while (index-- && Head -> next)
        Head = Head -> next;
    if (index != -1) return -1;
    return Head -> data;
}

void insertList(LinkList &L, int index, int value)
{
    // 在index插入value
    LinkList s = L;
    index--; 
    // 这里提前自减是为了寻找插入点前面一个节点
    while (index-- && s -> next)
        s = s -> next;
    if (index != -1) return ;

    LinkList node = new LNode;
    node -> data = value;
    node -> next = s -> next;
    s -> next = node;

    return ;
}

void deleteListNode(LinkList &L, int index)
{
    LinkList s = L;
    index--; 
    // 这里提前自减是为了寻找插入点前面一个节点
    while (index-- && s -> next)
        s = s -> next;
    if (index != -1) return ;

    LinkList d = s -> next;
    s -> next = d -> next;
    delete d;
    return ;
}

int main()
{
    LinkList L = creatList(5);
    // LinkList L = creatListTail(5);
    print(L);
    // insertList(L, 5, 99);
    deleteListNode(L, 3);
    print(L);
    // cout << getElem(L, -2) << endl;
    return 0;
}
作者:NorthCity1984
出处:https://grimoire.cn/algorithm/ds-single-link.html
版权:本文《数据结构:单链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任

Last Modified: October 19, 2020