带头结点的单链表

未分类

为什么我们需要带头结点的单链表？

因为在原来的单链表中，每次在某个节点前面插入元素，都需要先找到该节点的前驱结点才可实现插入操作，那么如果要在第一个结点前面插入元素，该怎么做？这是会带来困难，所以我们需要有一个不存储数据的头结点。
而且只有带头结点的单链表才可以就地逆置

类型定义同单链表：

typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型

相关操作

初始化

判断是否为空

Status ListEmpty_L(LinkList L)
/* 判定带头结点单链表L是否为空链表。   */
/* 若L是空链表，则返回TRUE，否则FALSE。*/
{
    if (L->next == NULL)
        return TRUE;
    else
        return FALSE;
}

销毁

注意：清空与销毁的区别
清空：只是把元素从链表里面去掉
销毁：把元素全部去掉之后，还要释放头结点的空间

Status DestroyList_L(LinkList &L)
/* 销毁带头结点单链表L，并返回OK。*/
{
    LinkList p,q;
    LinkList a,b,c;
    p = L->next;
    if (p == NULL)
    {
        free(L);
        return OK;  
    }
    while (p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
    free(L);
    return OK;
}

清空

Status ClearList_L(LinkList &L)
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
{
     if (NULL == L)
        return  ERROR;
   LinkList p,q;
    LinkList a,b,c;
    p = L->next;
    if (p == NULL)
        return OK;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
    L->next = NULL;
    return OK;
}

求链表的长度

int ListLength_L(LinkList L)
/* 求带头结点单链表L的长度，并返回长度值。*/
/* 若L不是带头结点单链表，则返回-1。      */
{
    if (NULL == L)
        return -1;
   LinkList p;
    p = L->next;
    int num = 0;
    while (p != NULL)
    {
        p = p->next;
        num++;
    }
    return num;
}

在第i各位值插入元素

Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */
{
    LinkList p = L;
    if (NULL == p || i <1)
        return ERROR;
    int num = 1;
    while (p->next != NULL && num<i)
    {
        p = p->next;
        num++;
    }
    if (num <i)
        return ERROR;
    LinkList m;
    m = (LinkList) malloc (sizeof(LNode));
    m->next = p->next;
    p->next = m;
    m->data = e;
    return OK;
}

删除第i个节点，并把数据返回

Status Delete_L(LinkList L, int i, ElemType &e)
/* 在带头结点单链表L删除第i元素到e，并返回OK。*/
/* 若参数不合理，则返回ERROR。                */
{
    LinkList p = L;
    LinkList q ;
    if (NULL == p || i <1)
        return ERROR;
    int num = 0;
    while (p->next != NULL && num<i)
    {
        q = p;
        p = p->next;
        num++;
    }
    if (i > num)
        return ERROR;
        LinkList m = p;
        e = m->data;
        q->next = m->next;
     //free(m);
     return OK;
}

测试代码

#include <iostream>
#include <cstdlib>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
#define ElemType char 
typedef struct LNode {
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */
{
    LinkList p = L;
    if (NULL == p || i <1)
        return ERROR;
    int num = 1;
    while (p->next != NULL && num<i)
    {
        p = p->next;
        num++;
    }
    if (num <i)
        return ERROR;
    LinkList m;
    m = (LinkList)malloc(sizeof(LinkList));
    m->next = p->next;
    p->next = m;
    m->data = e;
    return OK;
}
//初始化带头结点的单链表函数
void InitLinkList(LinkList &L)
{
    LinkList q;
    char c[] = {"abcdefg"};
    q = L;
    //q->next = L->next;
    for (int i = 0; i < 7; i++)
    {
        LinkList p = (LinkList)malloc(sizeof(LinkList));
        p->data = c[i];
        p->next = q->next;
        q->next = p;
        q = q->next;
    }
    //L = q;
}
//定义打印函数
void printLinkLIst(LinkList &L)
{
    LinkList p;
    p = L->next;
    while (p != NULL)
    {
        cout << p->data;
        p = p->next;
    }
    cout << endl;
}
int main()
{
    //定义一个带头结点的单链表
    //L3 = ( abcdefg)
    cout<<Fib2(0)<<endl;
    return 0;
}