链表结构：

SList.h

//--------------------------------------------------------------------------

          /*

          **功能：应用C语言实现单链表的各项操作

          **

          **

          **                  1：建立节点

          **                  2：打印单链表

          **                  3：尾插

          **                  4：尾删

          **                  5：头插

          **                  6：头删

          **                  7：清空整个链表

          **                  8：获取链表长度

          **                  9：查找数据

          **                10：在某位置后插入数据

          **                11：删除某位置的数据

          **                12：删除一个无头单链表的非尾节点

          **                13：在无头单链表的一个非头节点前插入一个节点

          **                14：查找中间节点

          **                15：查找倒数第k个节点(要求只能遍历一次)

          **                16：倒着打印单链表

          **                17：逆置单链表

          **                18：合并两个有序链表（合并后依然有序）

          **                19：冒泡排序

          **

          **

          **                                                        By ：Lynn-Zhang

          **

          */

//---------------------------------------------------------------------------

#pragma once

typedef int DataType;

typedef struct SListNode

{

    DataType data;    // 数据

    struct SListNode* next;   //指向下一个节点的指针

}SListNode;

// 如果要修改链表就必须加引用

SListNode* _BuyNode(DataType x);    //建立节点

void PrintSlist(SListNode* pHead);     //打印单链表

void PushBack(SListNode* & pHead, DataType x); //尾插(这里用了引用，指明是list的别名，调用时传参，不用传地址)(引用在.c文件中不可用)

//void PushBack(SListNode** pHead, DataType x);   // 这里的第一个参数指向链表第一个节点的指针的地址（调用时传参，传的是地址）

void PopBack(SListNode* & pHead);   //尾删

void PushFront(SListNode* & pHead, DataType x);    //头插

void PopFront(SListNode* & pHead);    //头删

void DestoryList(SListNode*& pHead);     //清空整个链表

int GetSize(SListNode* pHead);     //获取链表长度

SListNode* Find(SListNode* pHead, DataType x);    //查找数据

void Insert(SListNode* pos, DataType x);     //在某位置后插入数据

void Erase(SListNode*& pHead, SListNode* pos);        //删除某位置的数据

void DelNonTailNode(SListNode* pos);  //删除一个无头单链表的非尾节点

void InsertFrontNode(SListNode* pos, DataType x);    // 在无头单链表的一个非头节点前插入一个节点

SListNode* FindMidNode(SListNode* pHead);   //查找中间节点

SListNode* FindKNode(SListNode* pHead, int k);   //查找倒数第k个节点(要求只能遍历一次)

void PrintTailToHead(SListNode* pHead);    //倒着打印单链表（递归）

//SListNode* Reverse_(SListNode* pHead);  //逆置单链表（需要接收返回值），原链表会被改

void Reverse(SListNode*& pHead);  // 将原链表逆置

SListNode* Merge(SListNode* pHead1, SListNode* pHead2);   //合并两个有序链表（合并后依然有序）（递归）

void Sort(SListNode* pHead);   //冒泡排序

SList.cpp

#include"SList.h"

#include <stdio.h>

#include<assert.h>

#include <malloc.h>

SListNode* _BuyNode(DataType x)    //建立节点

{

    SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));

    tmp->data = x;

    tmp->next = NULL;

    return tmp;

}

void PrintSlist(SListNode* pHead)   // 打印单链表

{

    SListNode* cur = pHead;

    while (cur)

    {

        printf("%d->", cur->data);

        cur = cur->next;

    }

    printf("NULL\n");

}

//void PushBack(SListNode** ppHead, DataType x)   //尾插

//{

//  assert(ppHead);

//  // 1.空

//  // 2.不为空

//  if(*ppHead == NULL)

//  {

//      *ppHead = _BuyNode(x);

//  }

//  else

//  {

//      // 找尾

//      SListNode* tail = *ppHead;

//      while(tail->next != NULL)

//      {

//          tail = tail->next;

//      }

//

//      tail->next = _BuyNode(x);

//  }

//}

void PushBack(SListNode* & pHead, DataType x)  //尾插

{

    // 1.空

    // 2.不为空

    if (pHead == NULL)

    {

        pHead = _BuyNode(x);

    }

    else

    {

        // 找尾

        SListNode* tail = pHead;

        while (tail->next != NULL)

        {

            tail = tail->next;

        }

        tail->next = _BuyNode(x);

    }

}

void PopBack(SListNode* & pHead)      //  尾删

{

    //

    // 1.空

    // 2.一个节点

    // 3.多个节点

    //

    if (pHead == NULL)

    {

        return;

    }

    else if (pHead->next == NULL)

    {

        free(pHead);

        pHead = NULL;

    }

    else

    {

        SListNode* tail = pHead;

        SListNode* prev = NULL;

        while (tail->next)

        {

            prev = tail;

            tail = tail->next;

        }

        free(tail);

        prev->next = NULL;

    }

}

void PushFront(SListNode* & pHead, DataType x)   //头插

{

    // 1.空

    // 2.不空

    if (pHead == NULL)

    {

        pHead = _BuyNode(x);

    }

    else

    {

        SListNode* tmp = _BuyNode(x);

        tmp->next = pHead;

        pHead = tmp;

    }

}

void PopFront(SListNode*& pHead)   //头删

{

    //

    // 1.空

    // 2.一个节点

    // 3.一个以上的节点

    //

    if (pHead == NULL)

    {

        return;

    }

    else if (pHead->next == NULL)

    {

        free(pHead);

        pHead = NULL;

    }

    else

    {

        SListNode* tmp = pHead;

        pHead = pHead->next;

        free(tmp);

    }

}

void DestoryList(SListNode*& pHead)   //清空整个链表

{

    SListNode* cur = pHead;

    while (cur)

    {

        SListNode* tmp = cur;

        cur = cur->next;

        free(tmp);

    }

    pHead = NULL;

}

int GetSize(SListNode* pHead)   //获取链表长度

{

    assert(pHead);

    SListNode* cur = pHead;

    int count = ;

    while (cur)

    {

        count++;

        cur = cur->next;

    }

    return count;

}

SListNode* Find(SListNode* pHead, DataType x)  //查找节点

{

    SListNode* cur = pHead;

    while (cur)

    {

        if (cur->data == x)

        {

            return cur;

        }

        cur = cur->next;

    }

    return NULL;

}

void Insert(SListNode* pos, DataType x)   // 某位置后插入节点

{

    assert(pos);

    SListNode* tmp = _BuyNode(x);

    tmp->next = pos->next;

    pos->next = tmp;

}

void Erase(SListNode*& pHead, SListNode* pos)   //删除某位置的节点

{

    assert(pos);

    assert(pHead);

    //pos为头结点

    if (pHead == pos)

    {

        pHead = pHead->next;

        free(pos);

        return;

    }

    ////

    SListNode* prev = pHead;

    while (prev)

    {

        if (prev->next == pos)

        {

            prev->next = pos->next;

            free(pos);

            break;

        }

        prev = prev->next;

    }

}

void DelNonTailNode(SListNode* pos)  //// 删除一个无头单链表的非尾节点

{

    assert(pos);

    assert(pos->next);

    SListNode* del = pos->next;

    SListNode* dnext = del->next;

    pos->data = del->data;

    pos->next = dnext;

    free(del);

}

void InsertFrontNode(SListNode* pos, DataType x)     // 在无头单链表的一个非头节点前插入一个节点

{

    assert(pos);

    SListNode* tmp = _BuyNode(pos->data);

    tmp->next = pos->next;

    pos->next = tmp;

    pos->data = x;

}

void Sort(SListNode* pHead)    //冒泡排序

{

    assert(pHead);

    int size = GetSize(pHead);

    for (int i = ; i < size - ; i++)

    {

        SListNode* left = pHead;

        SListNode* right = pHead->next;

        for (int j = ; j < size - i - ; j++)

        {

            if (left->data>right->data)

            {

                int tmp = left->data;

                left->data = right->data;

                right->data = tmp;

            }

            right = right->next;

            left = left->next;

        }

    }

}

SListNode* FindMidNode(SListNode* pHead)   //查找中间节点

{

    SListNode* fast = pHead;

    SListNode* slow = pHead;

    while (fast&&fast->next)

    {

        slow = slow->next;

        fast = fast->next->next;

    }

    return slow;

}

SListNode* FindKNode(SListNode* pHead, int k)   //查找倒数第k个节点

{

    SListNode* fast = pHead;

    SListNode* slow = pHead;

    while (fast && k--)

    {

        fast = fast->next;

    }

    if (k > )

    {

        return NULL;

    }

    while (fast)

    {

        slow = slow->next;

        fast = fast->next;

    }

    return slow;

}

void PrintTailToHead(SListNode* pHead)    //倒着打印单链表（递归）

{

    if (pHead)

    {

        PrintTailToHead(pHead->next);

        printf("%d ", pHead->data);

    }

}

//SListNode* Reverse_(SListNode* pHead) //逆置单链表（需要接收返回值）原链表会被改

//{

//  SListNode* cur = pHead;

//  SListNode* newHead = NULL;

//  while (cur)

//  {

//      SListNode* tmp = cur;

//      cur = cur->next;

//      tmp->next = newHead;

//      newHead = tmp;

//  }

//  return newHead;

//}
void Reverse(SListNode*& pHead)  //逆置单链表 （无需返回值）
{

    SListNode* cur = pHead;

    SListNode* newHead = NULL;

    while (cur)

    {

        SListNode* tmp = cur;

        cur = cur->next;

        tmp->next = newHead;

        newHead = tmp;

    }

    pHead = newHead;

    //return newHead;

}

SListNode* Merge(SListNode* pHead1, SListNode* pHead2)   //合并两个有序链表（合并后依然有序）递归

{

    if (pHead1 == NULL)

        return pHead2;

    else if (pHead2 == NULL)

        return pHead1;

    SListNode* pMergedHead = NULL;

    if (pHead1->data < pHead2->data)

    {

        pMergedHead = pHead1;

        pMergedHead->next = Merge(pHead1->next, pHead2);

    }

    else

    {

        pMergedHead = pHead2;

        pMergedHead->next = Merge(pHead1, pHead2->next);

    }

    return pMergedHead;

}

Test.cpp

#include "SList.h"

#include<stdlib.h>

 
//测试用例

void Test1()

{

    // 尾插 打印 尾删 头插 头删 清空链表

    SListNode* list = NULL;

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PrintSlist(list);

    PopBack(list);

    PrintSlist(list);

    PushFront(list,);

    PrintSlist(list);

    PopFront(list);

    PrintSlist(list);

    DestoryList(list);

    PrintSlist(list);

}

void Test2()

{

    // 查找节点  在某位置插入节点 删除某位置节点

    SListNode* list = NULL;

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PrintSlist(list);

    SListNode* pos = Find(list, );

    Insert(pos, );

    PrintSlist(list);

    Erase(list, Find(list, ));

    PrintSlist(list);

}

void Test3()

{

    SListNode* list = NULL;

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PrintSlist(list);

    // 删除一个无头单链表的非尾节点

    /*SListNode* pos = Find(list, 2);

    DelNonTailNode(pos);

    PrintSlist(list);*/

    // 在无头单链表的一个非头节点前插入一个节点

    /*SListNode* pos = Find(list, 2);

    InsertFrontNode(pos, 0);

    PrintSlist(list);*/

    //查找中间节点

    //PrintSlist(FindMidNode(list));

    //查找倒数第k个节点

    //SListNode* ret = FindKNode(list, 2);

    //PrintSlist(ret);

    //倒着打印单链表（递归）

    //PrintTailToHead(list);

    //逆置单链表

    //SListNode* ret = Reverse(list);

    //PrintSlist(ret);

    //PrintSlist(Reverse_(list));
    //PrintSlist(list);

}

void Test4()

{   //合并两个有序链表（合并后依然有序）

    SListNode* list = NULL;

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PushBack(list, );

    PrintSlist(list);

    Sort(list);

    PrintSlist(list);

    /*SListNode* list1 = NULL;

    PushBack(list1, 2);

    PushBack(list1, 3);

    PushBack(list1, 3);

    PushBack(list1, 0);

    PrintSlist(list);

    Sort(list1);

    PrintSlist(list1);

    SListNode* ret = Merge(list, list1);

    PrintSlist(ret);

    PrintSlist(list);

    PrintSlist(list1);*/

}

int main()

{

    //Test1();

    //Test2();

    //Test3();

    Test4();

    system("pause");

    return ;

}

最新文章

  1. ABP模块化
  2. hihocoder1033交错和
  3. jQuery.snowflake雪花飘落插件
  4. String类的写时拷贝
  5. JavaScript定时器与执行机制解析
  6. Android Mediaplayer各种属性和方法简单介绍
  7. 我的PHP之旅--XML操作
  8. resultMap之collection聚集
  9. 【JavaEE基础】在Java中如何使用jdbc连接Sql2008数据库
  10. 2017-3-25 css样式表（一）
  11. react native 增量升级方案（转）
  12. 关于mdb数据库在插入过程中报错-&gt;Syntax error in INSERT INTO statement.(sql语句没问题)
  13. IntelliJ IDEA像Eclipse一样打开多个项目（转）
  14. L255
  15. JavaBasic_03
  16. EF中的1:0或1:1关系以及1:n关系
  17. C++ const 和static的总结以及使用
  18. BZOJ 1901: Zju2112 Dynamic Rankings 区间k大 带修改 在线 线段树套平衡树
  19. composer爆错：zlib_decode():data error
  20. pat1068. Find More Coins (30)

热门文章

  1. C#中执行存储过程并在SQL server中调试
  2. Dephi泛型generic的应用
  3. PHP面试题及答案解析(4)—PHP核心技术
  4. C/C++ 内存管理总结
  5. oracle中直方图的使用
  6. android常用权限
  7. 当客户端提交更新数据请求时，是先写入edits，然后再写入内存的
  8. 一个简单的数据增量更新策略（Android / MongoDB / Django)
  9. Elasticsearch5.3 学习（一）：安装、Yii2.0 下载es扩展
  10. div+css 画三角形