【c语言】单链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【c语言】单链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7980字，纯文字阅读大概需要12分钟。

内容图文

单链表，顾名思义是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

我们在这里使用C语言实现：

.h 文件：

#pragma once
#include<assert.h>
#include <malloc.h>

typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;
}SListNode;

void PushBack(SListNode* & pHead, DataType x);
void PopBack(SListNode* & pHead);
void PushFront(SListNode* & pHead, DataType x);
void PopFront(SListNode* & pHead);
SListNode* Find(SListNode* pHead, DataType x);
void Insert(SListNode* pos, DataType x);
void Erase(SListNode* pos);
void DestoryList(SListNode*& pHead);

void DestoryList(SListNode*& pHead)
{
    SListNode* cur = pHead;
    while (cur)
    {
        SListNode* tmp =  cur;
        cur = cur->next;
        free(tmp);
    }

    pHead = NULL;
}

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);
    }
}

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);
    //SListNode* next = pos->next;
    //pos->next = tmp;
    //tmp->next = next;

    SListNode* tmp = _BuyNode(x);
    tmp->next = pos->next;
    pos->next = tmp;

}

void Erase(SListNode*& pHead, SListNode* pos)
{
    assert(pos);
    assert(pHead);

    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* next = del->next;

    pos->data = del->data;
    pos->next = next;
    free(del);
}

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

    //SListNode* tmp = _BuyNode(x);
    //tmp->next = pos->next;
    //pos->next = tmp;

    //DataType tmpData = pos->data;
    //pos->data = tmp->data;
    //tmp->data = tmpData;

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

//struct Ret
//{    
//    SListNode* first;
//    SListNode* second;
//};

SListNode* FindMidNode(SListNode* pHead)
{
    SListNode* fast = pHead;
    SListNode* slow = pHead;


    while (fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    //while (fast)
    //{
    //    if (fast->next)
    //    {
    //        fast = fast->next->next;
    //    }
    //    else
    //    {
    //        break;
    //    }

    //    slow = slow->next;
    //}

    return slow;
}

SListNode* FindKNode(SListNode* pHead, int k)
{
    SListNode* fast = pHead;
    SListNode* slow = pHead;

    while (fast && k--)
    {
        fast = fast->next;
    }

    if (k > 0)
        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;
}


.cpp 文件：

#include <stdio.h>

#include "SList.h"

// PushBack/PopBack
void Test1()
{
    SListNode* list = NULL;
    PushBack(list, 1);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);

    PrintSlist(list);


    PopBack(list);
    PopBack(list);
    PopBack(list);
    PopBack(list);
    PopBack(list);

    PrintSlist(list);
}

// PushFront/PopFront
void Test2()
{
    SListNode* list = NULL;
    PushFront(list, 1);
    PushFront(list, 2);
    PushFront(list, 3);
    PushFront(list, 4);
    PrintSlist(list);

    PopFront(list);
    PopFront(list);
    PopFront(list);
    PopFront(list);
    PopFront(list);

    PrintSlist(list);
}

// Find/Insert
void Test3()
{
    SListNode* list = NULL;
    PushFront(list, 1);
    PushFront(list, 2);
    PushFront(list, 3);
    PushFront(list, 4);
    PrintSlist(list);

    SListNode* pos = Find(list, 3);
    Insert(pos, 10);

    pos = Find(list, 1);
    Insert(pos, 100);

    PrintSlist(list);

    // ??
    pos = Find(list, 4);
    Erase(list, pos);

    pos = Find(list, 100);
    Erase(list, pos);

    pos = Find(list, 3);
    Erase(list, pos);

    PrintSlist(list);
}

//DelNonTailNode
void Test4()
{
    SListNode* list = NULL;
    PushBack(list, 1);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);

    PrintSlist(list);

    SListNode* pos = list;
    DelNonTailNode(pos);

    PrintSlist(list);
}

void Test5()
{
    SListNode* list = NULL;
    PushBack(list, 1);

    SListNode* pos = FindMidNode(list);
    printf("%d\n", pos->data);

    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);

    pos = FindMidNode(list);
    printf("%d\n", pos->data);

    pos = FindKNode(list, 4);
    pos = FindKNode(list, 100);
}

void Test6()
{
    SListNode* list = NULL;
    PushBack(list, 1);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);

    //PrintTailToHead(list);

    list = Reverse(list);
    PrintSlist(list);

    //PrintTailToHead(list);
}

void Test7()
{
    SListNode* list = NULL;
    PushBack(list, 1);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);
    PushBack(list, 5);
    PushBack(list, 6);
    PushBack(list, 7);

    SListNode* tail = Find(list, 7);
    tail->next = list;

    SListNode* lastOne = JoseCycle(list, 3);
    printf("幸存者：%d\n", lastOne->data);
}

void Test8()
{
    SListNode* list = NULL;
    PushBack(list, 3);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 6);
    PushBack(list, 0);
    PushBack(list, 9);
    PushBack(list, 7);
    PrintSlist(list);

    BubbleSort(list);
    PrintSlist(list);
}

void Test9()
{
    SListNode* list1 = NULL, *list2 = NULL;
    PushBack(list1, 2);
    PushBack(list1, 3);
    PushBack(list1, 8);
    PrintSlist(list1);

    PushBack(list2, 1);
    PushBack(list2, 3);
    PushBack(list2, 5);
    PushBack(list2, 7);
    PrintSlist(list2);

    SListNode* list = MergeList(list1, list2);
    PrintSlist(list);

    DestoryList(list);
}

void Test10()
{
    SListNode* list = NULL;
    PushBack(list, 1);
    PushBack(list, 2);
    PushBack(list, 3);
    PushBack(list, 4);
    PushBack(list, 5);
    PushBack(list, 6);
    PushBack(list, 7);
    PrintSlist(list);

    SListNode* tail = Find(list, 7);
    SListNode* enrtyNode = Find(list, 4);
    tail->next = enrtyNode;

    SListNode* meetNode = CheckCycle(list);
    int length = GetCycleLength(meetNode);
    printf("meetNode:%d, length:%d\n", meetNode->data, length);

    SListNode* retEntryNode = GetEntryNode(list);
    //assert(retEntryNode == enrtyNode);
}

int main()
{
    //Test1();
    //Test2();
    //Test3();
    //Test4();
    //Test5();
    //Test6();
    //Test7();
    //Test8();
    //Test9();

    Test10();

    return 0;
}

本文出自 “Vs吕小布” 博客，谢绝转载！

原文：http://survive.blog.51cto.com/10728490/1733456

内容总结

以上是互联网集市为您收集整理的【c语言】单链表全部内容，希望文章能够帮你解决【c语言】单链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1333308.html

来源：【匿名】

【下一篇】C语言MD5的源码实例详解

更多 ►

【【c语言】单链表】教程文章相关的互联网学习教程文章

单链表，顾名思义是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。我们在这里使用C语言实现：.h 文件：#pragma once #include<assert.h> #include <malloc.h>typedef int DataType;typedef struct SListNode { DataType data; ...

C语言单向链表【图】

一、节点二、链表由一系列节点组成。每个节点至少包括：一个数据一个该节点类型的指针节点之间首尾相连头指针：指向第一个节点的指针尾节点：节点指针指向空三、建立一个单向链表1、创建节点2.使每个节点的指针域存储后继节点的地址原文：http://www.cnblogs.com/cellphone7/p/7677920.html

C语言实现链表节点的插入

对链表进行增删改查是最基本的操作。我在上一篇博客《C语言实现链表节点的删除》实现了删除链表中的某个节点。这里我们要来实现在某个位置插入节点。示例代码上传至https://github.com/chenyufeng1991/InsertList 。核心代码如下：Node *InsertToPosition(Node *pNode,int pos,int x){if (pos < 0 || pos > sizeList(pNode) ) {printf("%s函数执行，pos=%d非法，插入数据失败\n",__FUNCTION__,pos);return pNode;}Node *pMove;Nod...

数据结构--单链表 C语言【代码】【图】

//单链表基本操作 1 #include <stdio.h>2 3 #include <stdlib.h>4 5 6 typedef struct _NODE7{8int data;9struct _NODE *pNext;10 }NODE,*PNODE;11 12 PNODE Create_List(void)13{14int len = 0;15int data,i = 0;16 PNODE pHead = NULL;17 pHead = (PNODE)malloc(sizeof(NODE));18 PNODE pTail = pHead;19 pTail->pNext = NULL;20 21if(pHead == NULL)22 {23 printf("内存分配失败!\r\n");24 }...

C语言常见单链表面试题（1）【代码】

1、删除单链表的非尾节点解题思路：按照一般的思路单链表删除节点是必须知道其前驱节点才能删除，而在本题中不知道前驱节点，所以转换思路，先将需要删除的节点跟其后继节点的数据域交换，然后再删除既可。void EraseNotTail(pLinkNode pos) { assert(pos);pLinkNode del = NULL;//删除的节点del = pos->next;pos->data = pos->next->data;pos->next = pos->next->next;free(del);del = NULL; }2、冒泡排序单链表void BubbleSo...

数据结构线性表链表的C语言实现【图】

数据结构线性表链表的C语言实现说明：线性表是一种最简单的线性结构，也是最基本的一种线性结构，所以它不仅是学习中的重点，也是应用开发非常常用的一种数据结构。它可以分为顺序表和链表。它的主要操作是数据元素的插入，删除，以及排序等。接下来，本篇文章将对线性表链表的基本操作和运用进行详细的说明（包含在源代码的注释中），并给予可运行的程序源代码。线性表链表不同于顺序表，它是一种链式的线性表，和顺序表...

(续)顺序表之单循环链表(C语言实现)【图】

单循环链表和单链表的唯一区别在于单循环链表的最后一个节点的指针域指向第一个节点,使得整个链表形成一个环.C实现代码如下:#include<stdio.h>typedef struct node {int data;struct node *next; }Node;//链表的初始化 Node* InitList(int number) {int i;Node *pHead=(Node *)malloc(sizeof(Node));Node *TempHead=pHead;Node *Head=pHead;int data;for(i=0;i<number;i++){pHead=(Node *)malloc(sizeof(Node));printf("Please inp...

C语言动态静态链表(基础)【代码】【图】

我本专业是C#, .net ，自学C ,感觉还行，也是基础小白，望大神们多多关照注意: 别忘了加上选址符 & 注意哦**** 单向动态链表原理很简单:就是结构体定义定义一个本身结构体类型指针变量用来保存下一个结构体组地址，最后一个本身结构体类型指针变量存NULL，然后定义一个结构体指针变量，指向首地址，就层层相扣了直接上代码把: 后面更新插入链表和修改删除 1#define Len sizeof(struct stude...

C语言实现单链表节点的删除（带头结点）

我在之前一篇博客《C语言实现单链表节点的删除（不带头结点）》中详细实现了如何在一个不带头结点的单链表的删除一个节点，在这一篇博客中我改成了带头结点的单链表。代码示例上传至 https://github.com/chenyufeng1991/DeleteLinkedList_HeadNode。删除类型有两种：（1）删除某个位置pos的节点；（2）判断x值是否在链表中，若存在则删除该节点；核心代码如下：//删除某个位置pos的节点 Node *DeletePosNode(Node *pNode,int pos){...

C语言链表头插法逆向输出【图】

输入：1 2 3 4 5 -1输出：5 4 3 2 1 此题考查头链表的创建之一：头插法。所谓头插法是从一个空链表开始，重复读入数据，生成新结点，将读入的数据存放新结点的数据域中，然后讲新结点插入到当前链表的头结点之后，直至读入结束标志为止。 #include <stdio.h>#include <stdlib.h> typedef struct Node{ int data ; struct Node * pNext ;}* PNODE ,NODE ;PNODE creat_list(void) ;void show_list(PNODE phead) ;int main(){ PNODE ...

C语言单向链表

1，为什么要用到链表数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题...

c语言双向循环链表【代码】

双向循环链表,先来说说双向链表,双向链表也叫双链表,是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点.而循环链表之前也有说过,单链表中就是让最后一个结点的指针指向第一个结点就能构成一个循环链表,这里其实也是一样的,只不过多了一步,让第一个结点的前驱指向最后一个结点就行了,(这里介绍的是带头结点的双向循环链...

C语言 ---单链表创建、求长度、删除、排序等操作

#include<stdio.h> #include<stdlib.h>//定义单链表结点结构体 typedef int ElemType; typedef struct Node {ElemType data;struct Node *next; }LNode,*LinkList;//建立一个带头结点的单链表void Build(LinkList L) {int n;LinkList p,q;p=L;printf("输入n和n个数字：\n");scanf("%d",&n);while(n--){q=(LinkList)malloc(sizeof(LNode));scanf("%d",&q->data);q->next=NULL;p->next=q;p=q;} }//求单链表的长度 void LinkLength(Li...

（转载）C语言单链表实现19个功能完全详解

最近在复习数据结构，想把数据结构里面涉及的都自己实现一下，完全是用C语言实现的。自己编写的不是很好，大家可以参考，有错误希望帮忙指正，现在正处于编写阶段，一共将要实现19个功能。到目前我只写了一半，先传上来，大家有兴趣的可以帮忙指正，谢谢在vs2010上面编译运行无错误。每天都会把我写的新代码添加到这个里面。直到此链表完成。#include "stdafx.h"#include "stdio.h"#include <stdlib.h>#include "string.h" typedef...

C语言链表【代码】

1 #include"stdio.h" 2 #include"stdlib.h" 3 #include"malloc.h" 4 5 6constint maxlen=1000;//线性表的最大长度7 8//------------线性表------------------ 9struct List10{11int Data[maxlen];//存放数据 12int CurNum;//当前线性表 13};14 15void Intialize( List &A)//线性表初始化 16{17 A.CurNum = 0;//线性表元素个数为0 18}19 20int Length(List &A)//求表长度的实现 21{22return A.CurNum;23}24 25int Ins...

首页 / C语言 / 【c语言】单链表

【c语言】单链表

内容导读

内容图文

内容总结

内容备注

内容手机端

【【c语言】单链表】教程文章相关的互联网学习教程文章

【c语言】单链表【代码】

C语言单向链表【图】

C语言实现链表节点的插入

数据结构--单链表 C语言【代码】【图】

C语言常见单链表面试题（1）【代码】

数据结构线性表链表的C语言实现【图】

(续)顺序表之单循环链表(C语言实现)【图】

C语言动态静态链表(基础)【代码】【图】

C语言实现单链表节点的删除（带头结点）

C语言链表头插法逆向输出【图】

C语言单向链表

c语言双向循环链表【代码】

C语言 ---单链表创建、求长度、删除、排序等操作

（转载）C语言单链表实现19个功能完全详解

C语言链表【代码】

C语言 - 相关标签

链表 - 相关标签

C语言 - 技术教程分类

C语言 - 最新教程

C语言 - 最热教程

首页 / C语言 / 【c语言】 单链表

【c语言】 单链表

内容导读

内容图文

内容总结

内容备注

内容手机端

【【c语言】 单链表】教程文章相关的互联网学习教程文章

C语言 - 相关标签

链表 - 相关标签

C语言 - 技术教程分类

C语言 - 最新教程

C语言 - 最热教程

首页 / C语言 / 【c语言】单链表

【c语言】单链表

【【c语言】单链表】教程文章相关的互联网学习教程文章