数据结构—单链表的实现

时间:2025-03-14 08:55:25

关于单链表,是最熟悉不过的一种数据结构了。今天,花费了很长的时间写出了单链表,和大家分享一下,有问题大家可以提出来!!!

#define _CRT_SECURE_NO_WARNINGS 1

#ifndef __LINKLIST_H__
#define __LINKLIST_H__


#include<>
#include<>
#include<>

typedef int datatype;

typedef struct LinkNode
{
    datatype data;
    struct LinkNode *next;
}LinkNode,*pLinkNode;

typedef struct LinkList
{
    LinkNode *pHead;
}LinkList,*pLinkList;


static enum A
{
    EXIT,
    INIT,
    PUSHBACK,
    POPBACK,
    PUSHFRONT,
    POPFRONT,
    INSERT,
    REMOVE,
    REMOVEALL,
    BUBBLESORT,
    ERASE,
    PRINTLIST
};

void InitLinkList(pLinkList pList);
void DestroyList(pLinkList pList);
void PushBack(pLinkList pList,datatype x);
void PopBack(pLinkList pList);
void PushFront(pLinkList pList, datatype x);
void PopFront(pLinkList pList);
void PrintList(pLinkList pList);
pLinkNode Find(pLinkList pList, datatype x);
void Insert(pLinkList pList, pLinkNode pos, datatype x);
void Remove(pLinkList pList,datatype x);
void RemoveAll(pLinkList pList, datatype x);
void Erase(pLinkList pList,pLinkNode pos);
void BubbleSort(pLinkList pList);
void meau();


#endif //!__LINKLIST_H__

#define _CRT_SECURE_NO_WARNINGS 1


#include""


void meau()
{
    printf("$$$$$$$$$$$$$$    SEQLIST    $$$$$$$$$$$$$$$$\n");
	printf("$$$$$$$$$$$$$$$$$$$$$$¥$$$$$$$$$$$$$$$$$$$$$\n");
    printf("$$$                2.push_back      $$$\n");
    printf("$$$  3.pop_back          4.push_front     $$$\n");
    printf("$$$  5.pop_front                  $$$\n");
    printf("$$$                    $$$\n");
    printf("$$$                   $$$\n");
    printf("$$$                     $$$\n");
    printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
}

void InitLinkList(pLinkList pList)
{
    assert(pList);
    pList->pHead = NULL;

}
void DestroyList(pLinkList pList)
{
    assert(pList);
    pLinkNode p = NULL;
    pLinkNode cur = NULL;
    cur = pList->pHead;
    if (NULL == pList->pHead)
    {
        return;
    }
    while (cur != NULL)
    {
        p = cur;
        cur = cur->next;
        free(p);
    }
    pList->pHead = NULL;
}
void judgement(pLinkNode newnode)
{
    if (NULL == newnode)
    {
        printf("out of memory");
        exit(EXIT_FAILURE);
    }
}

void PushBack(pLinkList pList, datatype x)
{
    assert(pList);
    pLinkNode cur= NULL;
    pLinkNode prev = NULL;
    pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
    newnode->data = x;
    newnode->next = NULL;
    judgement(newnode);
    if (NULL == pList->pHead)
    {
        pList->pHead = newnode;
        return;
    }
    else 
    {
        cur = pList->pHead;
        while (cur != NULL)
        {
            prev = cur;
            cur = cur->next;
        }
        prev->next = newnode;
    }
}
void PopBack(pLinkList pList)
{
    pLinkNode cur = NULL;
    pLinkNode del = NULL;
    assert(pList);
    cur = pList->pHead;
    if (pList->pHead == NULL)
    {
        printf("此链表为空链表\n");
        return;
    }
    else if (NULL==pList->pHead->next)
    {
        free(cur);
        pList->pHead = NULL;
        return;
    }
    else
    {
        while (cur->next != NULL)
        {
            del = cur;
            cur = cur->next;
        }
        free(cur);
        del->next = NULL;

    }
}
void PushFront(pLinkList pList, datatype x)
{
    assert(pList);
    pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
    newnode->data = x;
    newnode->next = NULL;
    judgement(newnode);
    newnode->next = pList->pHead;
    pList->pHead = newnode;

}
void PopFront(pLinkList pList)
{
    pLinkNode cur = NULL;
    pLinkNode del = NULL;
    assert(pList);
    if (pList->pHead == NULL)
    {
        printf("此链表为空链表\n");
        return;
    }
    else
    {
        cur = pList->pHead->next;
        del = pList->pHead;
        free(del);
        pList->pHead = cur;
    }
}
void PrintList(pLinkList pList)
{
    pLinkNode cur = NULL;
    assert(pList);
    cur = pList->pHead;
    while (cur != NULL)
    {
        printf("%d  ", cur->data);
        cur = cur->next;
    }
    printf("\n");

}
pLinkNode Find(pLinkList pList, datatype x)
{
    pLinkNode cur = NULL;
    pLinkNode find = NULL;
    assert(pList);
    cur = pList->pHead;
    while (cur != NULL)
    {
        if (x == cur->data)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
void Insert(pLinkList pList, pLinkNode pos, datatype x)
{
    assert(pList);
    pLinkNode cur = pList->pHead;
    pLinkNode front =NULL;
    pLinkNode newnode = (pLinkNode)malloc(sizeof(LinkNode));
    judgement(newnode);
    newnode->data = x;
    newnode->next = NULL;
    if (pos == NULL)
    {

        printf("没有这样一个元素,无法插入\n");
        return;
    }
    while (cur != NULL)
    {
        if (cur == pos)
        {

            break;
        }
        front = cur;
        cur = cur->next;
    }
    if (NULL == front)
    {
        pList->pHead = newnode;
        newnode->next = cur;
    }
    else
    {
        front->next = newnode;
        newnode->next = cur;
    }
}
void Remove(pLinkList pList, datatype x)
{
    pLinkNode cur = NULL;
    pLinkNode del = NULL;
    pLinkNode front = NULL;
    assert(pList);
    if (pList->pHead == NULL)
    {
        printf("此链表为空链表\n");
        return;
    }
    cur = pList->pHead;
    front = cur;
    while (cur != NULL)
    {

        if (cur->data == x)
        {
            if (cur == pList->pHead)    //考虑第一个节点的情况
            {
                del = cur;
                pList->pHead = cur->next;
                free(del);
            }
            else                        //删除非第一个节点
            {
                del = cur;
                front->next = cur->next;
                free(del);
            }
            return;
        }
        else
        {
            front = cur;
            cur = cur->next;
        }
    }
    printf("没有值为%d的节点\n", x);
}
void RemoveAll(pLinkList pList, datatype x)
{
    pLinkNode cur = NULL;
    pLinkNode del = NULL;
    pLinkNode front = NULL;
    assert(pList);
    if (pList->pHead == NULL)
    {
        printf("此链表为空链表\n");
        return;
    }
    cur = pList->pHead;
    front = cur;
    while (cur != NULL)
    {

        if (cur->data == x)
        {
            if (cur == pList->pHead)    //考虑第一个节点的情况
            {
                del = cur;
                front = cur->next;          //记得要移动front
                pList->pHead = cur->next;
                free(del);
            }
            else                        //删除非第一个节点
            {
                del = cur;
                front->next = cur->next;
                free(del);
            }
            cur = front;            //让cur移动到当前的front进行操作

        }
        else
        {
            front = cur;
            cur = cur->next;
        }
    }
    //printf("没有值为%d的节点\n", x);
}
void Erase(pLinkList pList, pLinkNode pos)
{
    pLinkNode cur = NULL;
    pLinkNode erase = NULL;
    pLinkNode front =pList->pHead ;
    assert(pList);
    cur = pList->pHead;
    if (pList->pHead == NULL)
    {
        printf("此链表为空链表");
        return;
    }
    while (cur != NULL)
    {

        if (pos == cur)
        {
            if (pos == pList->pHead)
            {
                erase = pos;
                pList->pHead = cur->next;
                free(erase);
                erase->next = NULL;
            }
            else
            {
                erase = pos;
                front->next = cur->next;
                free(erase);
                erase->next = NULL;

            }
            return;
        }
        else
        {
            front = cur;
            cur = cur->next;

        }
    }


}
void BubbleSort(pLinkList pList)
{

    pLinkNode cur = NULL;
    pLinkNode tail = NULL;
    assert(pList);
    cur = pList->pHead;
    if ((pList->pHead == NULL)
        ||(pList->pHead->next==NULL))    //对于无节点和只有一个节点不进行排序
    {
        return;
    }
    while (cur != tail)     //当尾指针不等于头指针时进行冒泡
    {
        while (cur->next != tail)   //控制cur指针最后到的位置是倒数第二个节点
        {

            if (cur->data > cur->next->data)//进行冒泡
            {
                datatype tmp = cur->data;
                cur->data = cur->next->data;
                cur->next->data = tmp;
            }
            cur = cur->next;        //让cur向后移动进行下一次冒泡
        }
        tail = cur;             //让尾指针向前移动
        cur = pList->pHead;     //让当前的指针重置到头节点
    }
}



#define _CRT_SECURE_NO_WARNINGS 1

#include""

void Test()
{
    LinkList list;
    int input = 1;
    datatype x = 0;
    InitLinkList(&list);
    while (input)
    {
        meau();
        printf("请选择操作:");
        scanf("%d", &input);
        fflush(stdin);
        switch (input)
        {
        case INIT:
            InitLinkList(&list);
            break;
        case PUSHBACK:
            printf("请输入你要尾插节点的数据:\n");
            scanf("%d", &x);
            fflush(stdin);
            PushBack(&list,x);
            break;
        case POPBACK:
            PopBack(&list);
            break;
        case PUSHFRONT:
            printf("请输入你要尾插节点的数据:\n");
            scanf("%d", &x);
            fflush(stdin);
            PushFront(&list, x);
            break;
        case POPFRONT:
            PopFront(&list);
            break;
        case INSERT:
            printf("请输入你所插入位置的节点元素值");
            scanf("%d", &x);
            fflush(stdin);
            pLinkNode pos = Find(&list, x);
            printf("请输入你所插入节点元素值");
            scanf("%d", &x);
            fflush(stdin);
            Insert(&list, pos, x);
            break;
        case REMOVE:
            printf("请输入你需要删除单一节点的值:");
            scanf("%d", &x);
            fflush(stdin);
            Remove(&list,x);
            break;
        case REMOVEALL:
            printf("请输入你需要删除节点的值:");
            scanf("%d", &x);
            fflush(stdin);
            RemoveAll(&list, x);
            break;
        case BUBBLESORT:
            BubbleSort(&list);
            break;
        case ERASE:
            printf("请输入你所要擦除的节点数据:");
            scanf("%d", &x);
            fflush(stdin);
            pos = Find(&list, x);
            Erase(&list, pos);
            break;
        case PRINTLIST:
            PrintList(&list);
            break;
        case EXIT:
            DestroyList(&list);
            break;
        default:
            input = 1;
            break;
        }
    }
}
int main()
{
    Test();
    system("pause");
    return 0;
}