单链表的基本操作

?1.单链表的初始化(带头结点的单链表)

生成新结点作头结点，用头指针L指向头结点。
将头结点的指针域置空。

//先去建立一个结构体
typedef struct Lnode
{
    ElemType data;//储存数据
    struct Lnode *next;//储存下一个结点的地址
}Lnode,*LinkList;

Status InitList_L(LinkList &L)
{
    L = new LNode;//L = (LinkList) malloc (sizeof (LNode))
    L->next = NULL;
    return OK;
}

2.判断链表是否为空

空表：链表中无元素，称为空链表(头指针和头结点仍然在)

//判断头结点指针域是否为空
int ListEmpty(LinkList L)
{
    if(L->next != NULL)//判断是否为空
    {
        return 0;    
    }
    else
    {
        return 1;    
    }
}

?3.单链表的销毁

链表销毁后不存在。?

Status DestroyList_L(LinkList &L)
{
    Lnode *p;//或者LinkList p;
    while(L)//如果L不为空，就一直执行，当为空时，就退出循环
    {
        p = L;
        L = L->next;
        delete p;
    }
    return OK;

}

?4.清空链表

Status ClearList(LinkList &L)
{
    Lnode *p,*q;//设置两个结点
    P = L->next;
    while(p)//判断p数据域是否为空，为空的话就退出循环
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;//头结点指针域为空
    return OK;
}

5.求单链表的表长?

?算法思路：从首元结点开始，依次计数所有结点。

int ListLength(LinkList L)//返回L中数据元素的个数
{
    int i = 0;
    Lnode *p = L->next;//p指向第一个结点
    while(p)//判断p是否为空，如果为空就退出循环
    {
        i++;
        p = p->next;
    }
    return i;
}

6.取单链表中第i个元素的值

算法思路：从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。
算法步骤：

?从第1个结点(L->next)顺链扫描，用指针p指向当前扫描到的结点，p的初值p=L->next.
j做计数器，累计当前扫描过的结点数，j的初值为1.
当p指向扫描到的下一个结点时，计数器j加1.

Status GetElem_L(LinkList L,int i,ElemType &e)//获取线性表L中的某个元素，并通过变量e返回
{
    Lnode *p = L->next;//初始化
    int j = 1;//j为计数器
    while(p && j < i)//顺指针向后查找，直到p指向第i个元素或p为空。
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i)//判断第i个元素是否存在
    {
        return ERROR;
    }
    e = p->data;
    return OK;
}

?7.单链表的按值查找

7.1.?根据指定数据获取该数据所在的位置或地址

获取地址算法步骤：

从第一个结点起，依次和e相比较。
如果找到一个与e值相等的数据，则返回在列表中的地址。
如果查遍整个链表都没有找到其值和e相等的元素，则停止循环返回0/NULL。

Lnode *LocateElem_L(LinkList L,Elemtype e)
{
    Lnode *p = L->next;//初始化
    while(p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

7.2.?根据指定数据获取该数据所在的位置序号

获取序号的算法：?

//在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(LinkList L,Elemtype e)
{
    Lnode *p = L->next;
    int j = 1;
    while(p && p->data != e)
    {
        p = p->next;
        j++;
    }
    if(p)
    {
        return j;
    }
    else
    {
        return 0;    
    }

?算法分析：该算法的执行时间与待查找的值e相关，其平均时间复杂度为O(n)。

?8.单链表的插入算法

//在L中第i个元素之前插入数据元素e，初始条件：1 <= i <= L.length
Status ListInsert_L(LinkList &L,ElemType e)
{
    Lnode *p = L;
    int j = 0;
    while(P && j < i-1)//寻找第i-1个结点，p指向i-1结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i-1)//i大于表长+1或者小于1，插入位置非法
    {
        return ERROR;
    }
    Lnode *s = new Lnode;//生成新结点s
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

算法分析：?

?9.单链表的删除结点

?删除第i个结点的算法步骤：

?首先找到第i-1个结点的存储位置p，保存要删除的a的值。
令p->next指向第i+1个结点。
释放第i个结点的空间。

p->next = p->next->next。

//将线性表L中第i个数据元素删除
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
    Lnode *p = L;
    int j = 0;
    while(p->next && j<i-1)//寻找第i个结点，并令p指向其前驱
    {
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i-1)//删除位置不合理
    {
        return ERROR;
    }
    q = p->next;//临时保存被删除结点的地址已被释放
    p->next = q->next;//改变删除结点前驱结点的指针域
    e = q->data;
    delete q;//释放删除结点的空间
    return OK;
}

算法时间效率分析：由于要从头查找前驱结点，所耗时间复杂度为O(n);

10.单链表的建立?

10.1.头插法?

?头插法：元素插入在链表头部，也叫前插法。

从一个空表开始，重复读入数据。
生成新结点，将读入数据存放新结点的数据域中
从最后一个结点开始，依次将各结点插入到链表的前端。?

void CreateList_H(LinkList &L,int n)
{
    L = new Lnode;
    L->next = NULL;//先建立一个带头结点的单链表
    for(int i = n,i>0,--i)
    {
        p = new Lnode;//生成新结点
        cin >> p->data;//输入元素值
        p->next = L->next;//插入表头
        L->next = p;
    }
}

时间复杂度O(n)?

10.2.尾插法?

?尾插法：元素插入在链表尾部，也叫后插法。

从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。?

//正位序输入n个元素的值，建立带表头结点的单链表L
void CreateList_R(LinkList &L,int n)
{
    L = new Lnode;
    L->next = NULL;
    Lnode *r = L;//尾指针r指向头结点
    for(int i = 0,i<n,++i)
    {
        Lnode *p = new Lnode;//生成新的结点
        cin >> p->data;
        p->next = NULL;
        r->next = p;//插入到表尾
        r = p;//r指向新的尾结点
    }
}