单链表

1.链表的定义

通常将采用链式储存结构的线性表称为线性链表

什么是链式储存结构

用一组任意（可以连续，也可以不连续）的存储单元存放线性表的元素

特点：

逻辑次序和物理次序不一定相同
元素之间的逻辑关系用指针表示

描述ai和ai+1的逻辑关系：要求ai除了存储其本身的信息之外，还要存储其直接后继的地址信息。这两部分信息组成一个数据元素的存储映象，称为结点（Node），它包括两个域：存储数据元素信息的域称为数据域data；存储直接后继存储位置的域称为指针域next。

n 个结点由指针链接成一个链表。

什么是单链表？

链表中的每个结点只有一个指针域，这种链表称为单链表。

头指针指向链表第一个结点的指针。线性表中最后一个结点的指针域next为“空”即NULL

2.初始化单链表

2.1单链表的储存结构

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

2.2单链表的初始化

2.2.1头插法

2.2.1.1算法思想

先建立一个空链表L
利用循环，每次读取数据，生成新结点，将读取的数据放在新结点的数据域中
将新结点插入当前链表的表头结点的后面
读取到结束标识9999停止

2.2.1.1算法设计

void GreateFromHead(LinkList& L) 
{
    LinkList s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) 
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
}

2.2.2尾插法

2.2.2.1算法思想

先建立一个空链表L
利用循环，每次读取数据，生成新结点，将读取的数据放在相信结点的数据域中
增加一个新尾指针p，使之指向当前单链表的表尾
将新结点插入尾结点（也就是p指向的结点）的后面
p重新指向表尾
读取到结束标识9999停止

2.2.2.2算法设计

void GreateFromeEnd(LinkList& L) 
{
    LinkList s,p;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    p = L;
    scanf("%d",&x);
    while (x != 9999) 
    {
        s= (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = NULL;
        p->next = s;
        p = p->next;
        scanf("%d", &x);
    }
}

3.单链表的查

3.1在单链表中查找到第i个结点

3.1.1算法思想

从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描的结点
用j做计数器，累计当前扫描过的节点数
当j==i时，返回p

3.1.2算法设计

LinkList GetElem(LinkList L, int i) 
{
    LNode* p = L->next;
    int j = 1;
    if(i==0)
    {
        return L;//i是0 就返回头结点
    }
    if (i < 1)
        return NULL;//i为负数 就返回空
    while(j<i)
    {
        p = p->next;//让p指向下一个结点
        j++;
        if(p==NULL)
        {
            return NULL;
            break;
        }
    }
    return p;
}

3.2单链表按值查找

3.2.1算法思想

从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描的结点
判断扫描到结点的data域值是否等于e
如果不等于e，则接着扫描；等于e，则返回当前的p

3.2.2算法设计

LinkList LocateElem(LinkList L,int e) 
{
    LinkList p = L->next;
    while (p != NULL&&p->data!=e) 
    {
        p=p->next;
    }
    return p;
}

4.单链表的增(插入)

问题要求：在线性表的第i（1=<i<=表长+1）个位置之前插入一个新元素e

4.1算法思想

查找：在单链表中找到第i-1个结点，并用指针p指示
申请：申请一个新结点s，将气数据域的值赋值为e
插入：通过修改指针域将新结点s挂入单链表L

4.2 算法设计

bool ListFrontInsert(LinkList L, int i,int e ) 
{
    LinkList p = GetElem(L, i-1);//利用按序号查找的方法，找到i-1个结点
    if (NULL == p) 
    {
        return false;
    }
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s -> next = p->next;
    p->next = s;
    return true;

}

5.单链表的删除

问题要求：删除第i个位置的元素

5.1算法思想

找到第i-1个结点，用指针p指示
用q指示第i个结点也就是（p->next）
将p指向结点的next指向q指向结点的下一个结点
删除第i个结点

5.2算法设计

bool ListDelete(LinkList L,int i)
{
    LinkList p = GetElem(L, i - 1);//利用按序号查找的方法，找到i-1个结点
    if(NULL==p->next||NULL==p)
    {
        return false;
    }
    LinkList q = p->next;
    if(q==NULL)
    {
        free(q);
        p->next = NULL;
    }
    else
    {
    p->next = q->next;
    free(q);
    q = NULL;
    }
    return true;
    
}

6.单链表的改

问题要求：修改单链表第i个元素的值

6.1算法思想

找到第i个元素,用p指示
修改它的data域的值为e

6.2算法设计

bool UpdataList(LinkList L,int i，int e)
{
    LinkList p = GetElem(L, i);//利用按序号查找的方法，找到i个结点
    if(NULL==p->next||NULL==p)
    {
        return false;
    }
    p->data=e;
    return true;
}

标签：LinkList,结点,单链,next,链表,NULL
From： https://www.cnblogs.com/wlb429/p/16727485.html

链表之单链表

单链表