C/C++ 實作線性表中的單連結清單

代碼隻進行了簡單的測試 如果代碼存在問題 歡迎各位帶哥在評論區指出

資料結構

typedef struct LNode{
    ElemType data; //資料域
    struct LNode *next; //指針域
}LNode, *LinkList;
           

單連結清單的原子操作實作

1.建立單連結清單

Status ListCreate_L(LinkList &L, int n)
{
    //建立一個長度為n的帶有頭結點的空連結清單
    LNode *p;

    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    p = L;

    for(int i = 0; i<n; i++)
    {
        p->next = (LNode *)malloc(sizeof(LNode));
        p = p->next;

        //scanf("%d", &p->data);
        p->data = i;
    }

    p->next = NULL; //表尾賦空

    return OK;
}
           

2.删除單連結清單

Status ListDestroy_L(LinkList &L)
{
    //删除連結清單
    LNode *p = L, *q = p;

    while(p)
    {
        p = p->next;
        free(q);
        q = p;
    }

    L = NULL;
    return OK;
}
           

3.向表中插入元素

Status ListInsert_L(LinkList &L, int n, ElemType e)
{
    //定位到第n-1個結點，在其後插入一個新開辟的結點.
    LNode *p=L;
    int i=0;

    while(p && i< n)    //定位到第n-1個結點
    {
        p = p->next;
        i++;
    }

    if(!p || n<0)   //第n-1個節點不存在或者n<0
        return ERROR;

    LNode *q;

    q = (LNode *) malloc(sizeof(LNode));

    if(!q)
        exit(OVERFLOW);

    q->data = e;
    q->next = p->next;
    p->next = q;

    return OK;
}
           

4.向表尾追加元素

Status ListAppend_L(LinkList &L, ElemType e)
{
    //在連結清單尾追加e節點
    LNode *p=L;

    if(!p) //為空表建立頭結點
    {
        L = (LNode *)malloc(sizeof(LNode));
        L->next = NULL;
        p = L;
    }

    while(p->next)    //定位到表尾
        p = p->next;
    LNode *q;

    q = (LNode *) malloc(sizeof(LNode));

    if(!q)
        exit(OVERFLOW);

    q->data = e;
    q->next = p->next;
    p->next = q;

    return OK;
}
           

5.從表中删除元素

Status  DeleteElem_L(LinkList &L,int n,ElemType &e)
{
    //L為帶頭結點的單連結清單的頭指針。
    //第n個元素存在時,其值賦給e并傳回OK,否則傳回ERROR
    LNode *p = L->next, *q = L;
    int i = 0;
    while(p && i<n) //找到待删除節點以及其前驅節點
    {
        p = p->next;
        q = q->next;
        i++;
    }

    if(!p || n<0)   //第n個元素不存在 或 n<0
        return ERROR;

    q->next = p->next;  //将待删除節點從連結清單斷開
    e = p->data;
    free(p);    //删除節點

    return OK;
}
           

6.擷取表中指定位置元素

Status  GetElem_L(LinkList L,int n,ElemType &e)
{
    //L為帶頭結點的單連結清單的頭指針。
    //第i個元素存在時,其值賦給e并傳回OK,否則傳回ERROR
    LNode *p = L->next;
    int i = 0;
    while(p && i<n)
    {
        p = p->next;
        i++;
    }

    if(!p || n<0)   //第n個元素不存在 或 n<0
        return ERROR;

    e = p->data;

    return OK;
}
           

7.擷取表長

int ListLength_L(LinkList L)
{
    if(!L)
        return 0;

    LNode *p = L->next;

    int n = 0;
    while(p)
    {
        p=p->next;
        n++;
    }

    return n;
}
           

完整代碼