数据结构:顺序链表

#include "pch.h"
#include <iostream>
//c++实现线性表的链式存储结构
#define MAXSIZE 100
//单链表的结构体
typedef struct LNode
{
    int data;
    //---这里声明的是一个结构体的指针，保存结构体的地址
    struct LNode *next;
}LNode,*LinkList;
/* 
这里*LinkList主要作为头指针使用，
所以这个东西是用来保存地址的，和那个next是一样的
*/
using namespace std;
//结构体的初始化
bool InitList(LinkList &L)
{
    L = new LNode;
    L->next = NULL;
    L->data = 0;//前面第一个是首元节点不存数据
    LinkList p=L;
    int i = 6;
    while (--i!=1)
    {
        LinkList N = new LNode;
        p->next = N;
        p->next->data = i;
        p = p->next;
    }
    p->next = NULL;
    return true;
}
//打印单链表
void PrintLink(LinkList L)
{
    LinkList p = L->next;
    while (p)
    {
        cout << p->data<<endl;
        p = p->next;
    }
}

//获取单链表值
bool GetElem(LinkList L, int i, int &e)
{
    /*这里其实就是根据头结点
    然后通过计数器来不断计数来获取相应的值*/
    LinkList p = L->next;//这里定义一个指针变量来存放Lnode的地址
    //因为L是首元节点所以第一个数组其实是第二个Lnode
    int j=1;//计数器
    while (p && j <i)//当指针为空或者超过i还没有找到的话就跳出循环
    {
        //这里之所以是j<i是因为我们需要找到i位置的指针
        //而这里p指的的其实是第j个指针（j++之后）
        p = p->next;
        j++;
    }
    if (!p || j > i) return false;//这里说明没有找到
    e = p->data;
    return true;
}
//单链表的插入
bool ListInsert(LinkList &L, int i, int e)
{
    LinkList p = L;//先让p指向首元节点，以便后面处理
    int j = 0;
    while (p && j < i- 1)
    {
        //找到i前面那个数字,所以是j<i-1
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1) return false;//判断是否找到了
    LinkList s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
//单链表的删除
bool ListDelete(LinkList &L, int i)
{
    LinkList p = L->next;
    int j = 0;
    while (p && j < i - 1)//查找第i-1个节点
    {
        p = p->next;
        ++j;
    }
    if (!p->next || j > i - 1) return false;//判断是否第i个节点是否存在
    LinkList q = p->next;//找到第i个节点然后删除
    p->next = q->next;
    delete q;
    return true;
}
//前插法插入数据,其实就是把数据插在首元节点后面
bool InsertDataFront(LinkList &L, int e)
{
    LinkList s = new LNode;
    s->data = e;//这里L指向的是首元节点，所以我们可以直接修改L->next的值
    s->next = L->next;
    L->next = s;
    return true;
}
bool InsertDataBack(LinkList &L,int e)
{
    LinkList p = L->next;
    while ( p->next) p=p->next;
    LinkList s = new LNode;
    s->data = e;
    s->next = NULL;
    p->next = s;
    return true;
}
int main()
{	
    //这里定义了一个指向头结点的指针
    //*L保存的是头结点的地址，头结点也是一个指针
    //头结点指向的是LNdode
    LinkList *L = new LinkList;
    if (InitList(*L)) cout << "Init ok!"<<endl;
    PrintLink(*L);
    int e = 0;
    if (GetElem(*L, 1, e)) cout << "该值为：" << e << endl;
    else cout << "没有找到该值！" << endl;
    if (ListInsert(*L, 2, 10)) cout << "插入成功！" << endl;
    else cout << "插入失败！" << endl;
    PrintLink(*L);
    if(ListDelete(*L, 2))cout << "删除成功！" << endl;
    else cout << "删除失败！" << endl;
    PrintLink(*L);
    InsertDataFront(*L,20);
    PrintLink(*L);
    InsertDataBack(*L, 30);
    PrintLink(*L);
}