数据结构3-单链表的实现

我会带着你远行 2022-05-27 02:35 62阅读 0赞

#                                         数据结构3-单链表的实现 #

顺序表在进行数据操作时，都必须从头开始才能找到所需要的数据，而且顺序表必须一个数接着一个数进行存储，这样当我们对顺序表中的部分数据进行增删查改时候，对于修改数据之后的数据要进行移位。

显然，这样的操作时间复杂度比较大。

而链表可以看成由结点组成的特殊的顺序表，而所谓结点就是一个数据和该数据的数据的地址组成的。链表不需要按顺序一个接一个的排列，因为链表的结点中存储了该结点的下一个结点的地址，寻址访问即可。

下面给出单链表（不带头指针的单向不循环链表）的实现过程。

typedef int DataType; 
    
    typedef struct SListNode //定义一个单链表结构体
    { 
        struct SListNode* _next; 
        DataType _data; 
    }SListNode; 
    
    
    SListNode* BuySListNode(DataType x); //创建结点
    void SListPrint(SListNode* pHead); //打印单链表
    void SListDestory(SListNode** ppHead);// 销毁单链表
    
    void SListPushBack(SListNode** ppHead, DataType x); //尾部插入
    void SListPopBack(SListNode** ppHead); //尾部删除
    void SListPushFront(SListNode** ppHead, DataType x);//头部插入 
    SListNode* SListFind(SListNode* pHead, DataType x); //单链表中查找x
    void SListInsest(SListNode** ppHead, SListNode* pos, DataType x); //单链表pos位置插入x
    void SListErase(SListNode** ppHead, SListNode* pos); //删除pos结点
    
    
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21

//SlistNode.h #ifndef _SListNode_h_ #define _SListNode_h_ #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<Windows.h> #include<assert.h> typedef int DataType; typedef struct SListNode { struct SListNode* next; DataType data; }SListNode; SListNode* BuySListNode(DataType x)//创建链表结点 { SListNode*node = (SListNode*)malloc(sizeof(SListNode)); assert(node); node->data = x; node->next = NULL; return node; } void SListPrint(SListNode* phead)//打印单链表 { SListNode*cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } void SListDestory(SListNode** pphead)//销毁单链表 { SListNode*cur = *pphead; while (cur) { free(cur); cur = cur->next; } *pphead = NULL; } void SListPushBack(SListNode** pphead, DataType x)//尾部插入 { if (NULL == *pphead) { (*pphead) = BuySListNode(x); } else { SListNode*cur = *pphead; while (cur->next != NULL) { cur = cur->next; } cur->next = BuySListNode(x); } } void SListPopBack(SListNode** pphead)//尾部删除 { //节点一个，两个，多个，三种情况 if (NULL == *pphead) return; else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode*prev = NULL; SListNode*cur = *pphead; while (cur->next) { prev = cur; cur = cur->next; } free(cur); prev->next=NULL; } } void SListPushFront(SListNode** pphead, DataType x)//头部插入 { if (NULL == *pphead) { *pphead = BuySListNode(x); (*pphead)->next = NULL; } else { SListNode*node = BuySListNode(x); node->next = *pphead; (*pphead) = node; } } void SlistPopFront(SListNode**pphead) { if (*pphead == NULL) return; else { SListNode*next = (*pphead)->next; free(*pphead); *pphead = next; } } SListNode* SListFind(SListNode* phead, DataType x)//SList中查找x { SListNode*cur = phead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } void SListInsest(SListNode** pphead, SListNode* pos, DataType x)//pos位置插入x { assert(*pphead); if (*pphead == pos) { SListPushFront(pphead,x); } else { SListNode*node = BuySListNode(x); node->next = pos->next; pos->next = node; } } void SListErase(SListNode** pphead, SListNode* pos)//删除pos位置结点 { assert(*pphead); if (*pphead == pos) { free(*pphead); pphead = NULL; } else { SListNode*prev = *pphead; while (prev->next != pos) prev = prev->next; SListNode*next = pos->next; //prev next prev->next = next; free(pos); } } void test1() { SListNode*List = NULL; SListPushBack(&List, 0); SListPushBack(&List, 1); SListPushBack(&List, 2); SListPushBack(&List, 3); SListPushBack(&List, 4); SListPopBack(&List); SListPushFront(&List,20); SListFind(List, 0); SListPrint(List); } void test2() { SListNode*List = NULL; SListPushBack(&List, 0); SListPushBack(&List, 1); SListPushBack(&List, 2); SListPushBack(&List, 3); SListPushBack(&List, 4); SlistPopFront(&List); SListPrint(List); SListNode*pos = SListFind(List, 3); SListInsest(&List, pos, 100); SListPrint(List); SListErase(&List, pos); SListPrint(List); } #endif //源.c #include"SListNode.h" int main() { //test1(); test2(); system("pause"); return 0; }