数据结构——链表(C语言实现)

提起链表,我们每个人都不会陌生,不管对数据结构的掌握如何,都或多或少的听过与用过链表这样的常见的数据结构。链表是线性表的一种,最基础的线性表,在插入与删除数据时,我们需要对表的整体或部分做移动,为了允许表可以不按照线性的顺序存储数据结构,于是链表就应运而生。链表最大的特点就是在每个节点里存储了到下一个节点的指针。由于不必按照顺序存储,链表在插入的时候可以达到O(1)的复杂度,比我们学习的最基本的线性表要快得多。但是在查找一个节点,或者访问特定编号的结点则需要O(N)的时间。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的有点,同时由于增加了指针域,空间开销较大。不过这在算法与数据结构领域是很常见的,用空间换时间,毕竟鱼和熊掌不可兼得。

我的链表数据结构是使用C语言来实现的,那么下面来看一下链表的头文件定义了哪些操作。

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete( ElementType X, List L);
Position FindPrevious( ElementType X, List L);
void Insert( ElementType X, List L, Position P);
void DeleteList( List L );
Position Header( List L );
Position First( List L);
Position Advance( Position P );
ElementType Retrieve( Position P );

#endif /* _List_H */

下面是对于头结点的实现文件,末尾的main函数中还有针对各类函数的测试方法。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "List.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

struct Node
{
    ElementType Element;
    Position Next;
};

void init_list(List L)
{
    L = NULL;
    printf("初始化链表成功\n");
}

List create_list()
{
    List L = NULL;
    List p1, p2;
    p1 = (List)malloc(sizeof(struct Node));
    p2 = (List)malloc(sizeof(struct Node));
    if (p1 == NULL || p2 == NULL)
    {
        printf("内存分配失败!\n");
        exit(0);
        system("pause");
    }
    memset(p1, 0, sizeof(struct Node));
    printf("请输入链表元素的值: \n");
    scanf("%d", &(p1->Element));
    p1->Next = NULL;
    while(p1->Element > 0)
    {
        if (L == NULL)
        {
            L = p1;
        }
        else
        {
            p2->Next = p1;
        }

        p2 = p1;

        p1 = (List)malloc(sizeof(struct Node));
        if (p1 == NULL || p2 == NULL)
        {
            printf("内存分配失败\n");
            exit(0);
            system("pause");
        }
        memset(p1, 0, sizeof(struct Node));
        printf("请输入链表的值: \n");
        scanf("%d", &(p1->Element));
        p1->Next = NULL;
    }
    printf("创建链表成功\n");
    return L;
}

void print_list(List L)
{
    List p = L;
    if (NULL == p)
    {
        printf("print_list: 链表为空!\n");
        return;
    }

    printf("打印链表如下: \n");
    while(p != NULL)
    {
        printf("%d, \n", p->Element);
        p = p->Next;
    }
    printf("\n");
    return;
}

Status IsEmpty(List L)
{
    if (L == NULL)
        return TRUE;
    else
        return FALSE;
}

Status IsLast(Position P, List L)
{
    return P->Next == NULL;
}

Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while(P != NULL && P->Element != X)
    {
        P = P->Next;
    }
    return P;
}

void Delete(ElementType X, List L)
{
    Position P, TmpCell;

    P = FindPrevious(X, L);

    if (!IsLast(P, L))
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
}

Position FindPrevious(ElementType X, List L)
{
    Position P;

    P = L;
    while(P->Next != NULL && P->Next->Element != X)
    {
        P = P->Next;
    }
    return P;
}

void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;

    TmpCell = malloc(sizeof(struct Node));
    if (TmpCell == NULL)
        printf("Out of space!!!\n");
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

void DeleteList(List L)
{
    Position P, Tmp;

    P = L->Next;
    L->Next = NULL;

    while(P != NULL)
    {
        Tmp = P->Next;
        free(P);
        P = Tmp;
    }
}

int main(int argc, char const *argv[])
{
    List L;
    init_list(L);
    L = create_list();
    print_list(L);
    int isEmpty = IsEmpty(L);
    printf("链表是否为空: %d\n", isEmpty);
    Position p = Find(21, L);
    if (p == NULL)
        printf("没有找到21元素\n");
    else
        printf("查找21结果: %d\n", p->Element);
    for (int i = 0; i < 10; i++)
    {
        Insert(i, L, p);
    }
    Delete(21, L);
    DeleteList(L);
    print_list(L);
    printf("Hello world\n");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2645
来自专栏个人随笔

Java 关于集合框架那点事儿

 1.引入集合框架   采用数组存在的一些缺陷:    1.数组长度固定不变,不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

29610
来自专栏专注研发

插入排序—直接插入排序(Straight Insertion Sort)

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插插入到已入,直...

1291
来自专栏Java进阶之路

Java8 Optional 的正确使用方式

1950
来自专栏后端技术探索

Base64编码原理,快速掌握

Base64编码,是我们程序开发中经常使用到的编码方法。它是一种基于用64个可打印字符来表示二进制数据的表示方法。它通常用作存储、传输一些二进制数据编码方法!也...

760
来自专栏星汉技术

HIVE内置函数

7496
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-双向链表类定义《数据结构与算法分析》

将新的节点插入双向链表的时候: iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点 { ...

2246
来自专栏chenjx85的技术专栏

leetcode-367-Valid Perfect Square

2524
来自专栏Hongten

java中的移位运算符:<<,>>,>>>总结

value >>> num     --   num 指定要移位值value 移动的位数。

2125
来自专栏java初学

13.2 具体的集合

2799

扫码关注云+社区

领取腾讯云代金券