【資料結構】單向連結清單的實作

SList.h
           

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include <stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;
typedef struct SListNode
{
    struct SListNode *pNext;//指向下一個結點的位址
    DataType  data;
}SListNode;

SListNode *BuySlistNode(DataType x);//建立新空間和資料
void SListNodePushBack(SListNode **ppHead, DataType data);//後插
void SListNodePushFront(SListNode **ppHead, DataType data);//前插
void SListNodeDelBack(SListNode **ppHead);//尾删
void SListNodeDelFront(SListNode **ppHead);//前删
void SListDestory(SListNode **ppHead);//銷毀
SListNode *SListFind(SListNode **ppHead, DataType data);//查找第一個比對的值，并傳回位址
void SListInsert(SListNode **ppHead, SListNode *pos, DataType data);//指定位置插入
void SListErase(SListNode **ppHead, SListNode *pos);//指定位置删除
void SListRemove(SListNode **ppHead, DataType data);//删除第一個比對的資料
void SListRemoveAll(SListNode **ppHead, DataType data);//删除所有比對的資料
void SListPrint(SListNode *ppHead);//列印連結清單
int size(SListNode *ppHead);//連結清單資料個數
void TestSList();//測試函數

#endif //__SList_H__
           

SList.c
           

#include"SList.h"

//建立一個新空間和資料
SListNode *BuySlistNode(DataType x)
{
    SListNode*node = (SListNode*)malloc(sizeof(SListNode));
    assert(node);
    node->data = x;
    node->pNext = NULL;
    return node;
}

//尾插
void SListNodePushBack(SListNode **ppHead, DataType data)
{
    if (*ppHead == NULL)
    {
        *ppHead = BuySlistNode(data);
        return;
    }
    else
    {
        SListNode*pNode = *ppHead;
        while (pNode->pNext != NULL)
        {
            pNode = pNode->pNext;
        }
        pNode->pNext = BuySlistNode(data);
    }
}

//頭插
void SListNodePushFront(SListNode **ppHead, DataType data)
{
        SListNode*pNode = BuySlistNode(data);
        pNode->pNext = *ppHead;
        *ppHead = pNode;
}

//尾删
void SListNodeDelBack(SListNode **ppHead)
{
    //空
    if (*ppHead == NULL)
    {
        return;
    }
    //一個
    else if ((*ppHead)->pNext == NULL)
    {
        free(*ppHead);
        *ppHead = NULL;
    }
    //多個
    else
    {
        SListNode*prev = NULL;  //用兩個指針來實作
        SListNode*pNode = *ppHead;
        while (pNode->pNext != NULL)
        {
            prev = pNode;
            pNode = pNode->pNext;
        }
        prev->pNext = NULL;
        free(pNode);
    }
}


void SListNodeDelFront(SListNode **ppHead)
{
    if (*ppHead == NULL)
    {
        return;
    }
    else
    {
        SListNode*pNode = (*ppHead)->pNext;//注意*和->優先級的問題
        free(*ppHead);
        *ppHead = pNode;
    }
}
void SListDestory(SListNode **ppHead)
{

    SListNode* pNode = *ppHead;
    while (pNode)
    {
        SListNode*pNext = pNode->pNext;//注意釋放前需儲存下一個指針，防止指針丢失
        free(pNode);
        pNode = pNext;
    }
    *ppHead = NULL;
}

SListNode *SListFind(SListNode **ppHead, DataType data)
{
    SListNode* pNode = *ppHead;
    while (pNode)
    {
        if (pNode->data == data)
        {
            return pNode;
        }
        pNode = pNode->pNext;
    }
    return NULL;
}

//指定位置插入
void SListInsert(SListNode **ppHead, SListNode *pos, DataType data)
{
    //assert(pos&&(*ppHead));
    SListNode*pNode = *ppHead;
    SListNode*pNewNode = BuySlistNode(data);
    //頭插
    if (pos == *ppHead)
    {
        SListNodePushFront(ppHead, data);
    }
    //中間
    else
    {
        while (pNode->pNext != pos)//注意循環條件
        {
            pNode = pNode->pNext;
        }
        pNode->pNext = pNewNode;
        pNewNode->pNext = pos;
    }

}

//删除指定位置
void SListErase(SListNode **ppHead, SListNode *pos)
{
    if (*ppHead == NULL)
    {
        return;
    }

    //隻有一個，頭删
    if (pos == *ppHead)
    {
        SListNodeDelFront(ppHead);
        return;
    }
    SListNode*pNode = *ppHead;
    while (pNode->pNext != pos)
    {
        pNode = pNode->pNext;
    }
    pNode->pNext = pos->pNext;
    free(pos);
    pos = NULL;
}

//删除第一個比對的值
void SListRemove(SListNode **ppHead,DataType data)
{
    SListNode*pNode = SListFind(*ppHead,data);
    if (pNode != NULL)
    {
        SListErase(ppHead, pNode);
    }
}

//删除所有比對的值
void SListRemoveAll(SListNode **ppHead, DataType data)
{
    if ((*ppHead)->data == data)
    {
        SListNodeDelFront(ppHead);
    }

    SListNode *pNode = *ppHead;
    SListNode *pDel=NULL;

    while (pNode->pNext != NULL)
    {
        if (pNode->pNext->data == data) 
        {
            pDel = pNode->pNext;
            pNode->pNext = pDel->pNext;
            free(pDel);
        }
        else 
        {
            pNode = pNode->pNext;
        }
    }
}

//列印連結清單
void SListPrint(SListNode *ppHead)
{
    SListNode*pNode = ppHead;
    while (pNode)
    {
        printf("%d->", pNode->data);
        pNode = pNode->pNext;
    }
    printf("NULL\n");
}

//連結清單的大小
int size(SListNode *ppHead)
{
    SListNode*pNode = ppHead;
    int size = ;
    while (pNode != NULL)
    {
        pNode = pNode->pNext;
        size++;
    }
    return size;
}

//測試函數
void TestSList()
{
    SListNode *list = NULL;
    SListNodePushBack(&list, );//注意傳位址
    SListNodePushBack(&list, );
    SListNodePushBack(&list, );
    SListNodePushBack(&list, );
    SListNodePushBack(&list, );
    SListPrint(list);

    SListNodeDelFront(&list);
    SListNodeDelFront(&list);
    SListNodeDelFront(&list);
    SListNodeDelFront(&list);
    SListNodeDelFront(&list);
    SListNodeDelFront(&list);
    SListPrint(list);


    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListPrint(list);

    SListNodeDelBack(&list);
    SListNodeDelBack(&list);
    SListNodeDelBack(&list);
    SListNodeDelBack(&list);
    SListNodeDelBack(&list);
    SListNodeDelBack(&list);
    SListPrint(list);

    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListPrint(list);

    SListDestory(&list);
    SListPrint(list);

    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListNodePushFront(&list, );
    SListPrint(list);

    SListNode*pos;
    pos = SListFind(&list, );
    SListInsert(&list, pos, );
    SListPrint(list);

    pos = SListFind(&list, );
    SListErase(&list, );
    SListPrint(list);

    printf("%d\n", size(list));

    SListRemove(&list,);
    SListPrint(list);

    SListRemoveAll(&list, );
    SListPrint(list);

    Destroy(&list);
    SListPrint(list);
}
           

            test.c

#include "SList.h"

int main()
{
    TestSList();
    system("pause");
    return ;

}