在 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
版权:本文《数据结构:单链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/algorithm/ds-single-link.html
版权:本文《数据结构:单链表》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任