C语言实现单链表基本操作方法

2024-10-16 17:03:26

存储结构

typedef int dataType；//爱护据类型
typedef struct Node {
    DataType data;   // 结点数据
    struct Node *next; // 指向下一个结点的指针
} Node, *LinkList;

基本功能

头插法创建单链表void CreateListHead( LinkList &head)
尾插法创建单链表void CreateListTail( LinkList &head)
获取指定位置的元素 int GetElement(LinkList head, int i, DataType &e)
获取指定元素的位置 int LocateElement(LinkList head, int e)
在指定位置插入元素 int InsertList(LinkList head, int i, DataType e)
删除指定位置的元素 int DeleteList(LinkList head, int i, DataType &e)
获取单链表的长度 int LengthLinkList(LinkList head)
合并两个非递减的单链表 void MergeList(LinkList La, LinkList Lb, LinkList &Lc)
寂链表void Destroy( LinkList &L)
遍历打印单链表中的所有元素 void PrintList(LinkList head)

头插法创建单链表

每次添加链的结点都能找到头结点的第1号位置，所以创建单表中的元素的顺序是输入元素的逆序。

/**
 * 头插法创建单链表，输入以-1结束
 */
void CreateListHead(LinkList &head) {
    DataType x;
    LinkList p;

    head = (LinkList)malloc(LEN);
    head->next = NULL;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        p->next = head->next; // 新增的结点指向头结点的下一个结点
        head->next = p;  // 头结点指向新增的结点
        scanf("%d", &x);
    }
}

尾插法创建单链表

每次新增的结点都放在单链表的后面，接下来和接下来的顺序保持一致。

/**
 * 尾插法创建单链表，输入以-1结束
 */
void CreateListTail(LinkList &head) {
    LinkList p, q;
    DataType x;

    head = (LinkList)malloc(LEN);
    q = head;
  	scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}

获取指定位置的元素

/**
 * 获取指定位置的元素
 * @param head 指向单链表头结点的指针（头指针）
 * @param i 位置
 * @param e 用来存放对应位置的元素值
 * @return 0：获取失败；1：获取成功
 */
int GetElement(LinkList head, int i, DataType &e) {
    LinkList p = head->next;
    int j = 1;

    while (p && j < i) { // 依次后移，直至为空或到达位置
        p = p->next;
        j++;
    }
    if (!p || j > i) { // p为空表示位置超过最大位置，j > i表示位置不合法(i < 1)
        return 0;
    }
    e = p->data;
    return 1;
}

在指定位置插入元素

/**
 * 在单链表插入元素到位置i
 * @param head 单链表的头指针
 * @param i 插入位置
 * @param e 插入元素
 * @return 1：插入成功，0：插入失败
 */
int InsertList(LinkList head, int i, DataType e) {
    LinkList p = head; // 从头结点开始
    int j = 1;
    while (p && j < i) { // 找到插入位置的前一个结点
        p = p->next;
        j++;
    }
    if (!p || j > i) { // p为空或i < 1，插入位置不合法
        return 0;
    }
    LinkList q = (LinkList)malloc(LEN); // 创建新结点
    q->data = e;
    q->next = p->next; // 将新结点指向前一个结点的后一个结点
    p->next = q; // 前一个结点指向新结点
    // 执行上述两个操作后，达到的效果是新结点插入到了前一个结点的后面
}

删除指定位置的元素

/**
 * 删除指定位置的元素
 * @param head
 * @param i 位置
 * @param e 被删除的元素的值存放在e中
 * @return 1：删除成功，0：删除失败
 */
int DeleteList(LinkList head, int i, DataType &e) {
    LinkList p = head;
    int j = 1;

    while (p && j < i) {  // 找到位置的前一个结点
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList s = p->next;
    e = s->data;
    p->next = s->next; // 改变前一个结点的指向，使其指向删除结点的后一个结点
    free(s);
    return 1;
}

获取单链表的长度

/**
 * 获取单链表的长度
 * @param head
 * @return 单链表的长度
 */
int LengthLinkList(LinkList head) {
    LinkList p = head->next;
    int count = 0;

    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

合并两个非递减的单链表

合并两个非递减的单链，新链表仍然保持非递减。

/**
 * 合并两个非递减的单链表，新的链表仍然非递减
 * @param La
 * @param Lb
 * @param Lc
 */
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
    LinkList pa, pb, pc;
    pa = La->next;
    pb = Lb->next;
    pc = Lc = (LinkList)malloc(LEN);
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}

晴链表

/**
 * 销毁链表
 */
void Destroy(LinkList &L) {
    LinkList p, q;
    p = L;
    while (p) { // 遍历所有结点，释放内存
        q = p;
        p = p->next;
        free(q);
    }
    L = NULL; // L置为NULL
}

遍历打印单链表

/**
 * 遍历打印单链表的所有元素
 */
void PrintList(LinkList head) {
    LinkList p = head->next;

    if (p == NULL) {
        cout << "List is NULL!" <<endl;
    } else {
        while (p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

附上完整代码

#include<cstdlib>
using namespace std;
#define LEN sizeof(Node)
typedef int DataType;
typedef struct Node {
    DataType data;
    struct Node *next;
} Node, *LinkList;

/**
 * 头插法创建单链表
 * @param head
 */
void CreateListHead(LinkList &head) {
    DataType x;
    LinkList p;

    head = (LinkList)malloc(LEN);
    head->next = NULL;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        p->next = head->next;
        head->next = p;
        scanf("%d", &x);
    }
}

/**
 * 尾插法创建单链表
 * @param head
 */
void CreateListTail(LinkList &head) {
    LinkList p, q;
    DataType x;

    head = (LinkList)malloc(LEN);
    q = head;
  	scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}

/**
 * 获取指定位置的元素
 * @param head 单链表头指针
 * @param i 位置
 * @param e 获取的元素赋值该参数
 * @return 0：获取失败；1：获取成功
 */
int GetElement(LinkList head, int i, DataType &e) {
    LinkList p = head->next;
    int j = 1;

    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    e = p->data;
    return 1;
}

/**
 * 获取某个元素的位置
 * @param head
 * @param e
 * @return 元素的位置
 */
int LocateElement(LinkList head, int e) {
    LinkList p = head->next;
    int j = 1;

    while (p && p->data != e) {
        p = p->next;
        j++;
    }
    if (!p) {
        return 0;
    }
    return j;
}

/**
 * 在单链表插入元素到位置i
 * @param head 单链表的头指针
 * @param i 插入位置
 * @param e 插入元素
 * @return 1：插入成功，0：插入失败
 */
int InsertList(LinkList head, int i, DataType e) {
    LinkList p = head;
    int j = 1;

    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList q = (LinkList)malloc(LEN);
    q->data = e;
    q->next = p->next;
    p->next = q;
}

/**
 * 删除指定位置的元素
 * @param head
 * @param i 位置
 * @param e 被删除的元素的值存放在e中
 * @return 1：删除成功，0：删除失败
 */
int DeleteList(LinkList head, int i, DataType &e) {
    LinkList p = head;
    int j = 1;

    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList s = p->next;
    e = s->data;
    p->next = s->next;
    free(s);
    return 1;
}

/**
 * 获取单链表的长度
 * @param head
 * @return
 */
int LengthLinkList(LinkList head) {
    LinkList p = head->next;
    int count = 0;

    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

/**
 * 合并两个非递减的单链表，新的链表仍然非递减
 * @param La
 * @param Lb
 * @param Lc
 */
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
    LinkList pa, pb, pc;

    pa = La->next;
    pb = Lb->next;
    pc = Lc = (LinkList)malloc(LEN);

    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}

/**
 * 销毁链表
 * @param L
 */
void Destroy(LinkList &L) {
    LinkList p, q;
    p = L;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    L = NULL;
}

/**
 * 遍历打印单链表的所有元素
 * @param head
 */
void PrintList(LinkList head) {
    LinkList p = head->next;

    if (p == NULL) {
        cout << "List is NULL!" <<endl;
    } else {
        while (p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
int main() {
    LinkList L;
    printf("头插法创建单链表：（输入以-1结束）\n");
    CreateListHead(L);
    PrintList(L);
    printf("尾插法创建单链表：（输入以-1结束）\n");
    CreateListTail(L);
    PrintList(L);
    InsertList(L, 1, 100);
    printf("在1号位置插入100后，单链表如下：\n");
    PrintList(L);
    DataType e;
    DeleteList(L, 1, e);
    printf("删除1号位置的元素，被删除的元素为：\n");
    printf("删除后的单链表为：\n");
    PrintList(L);
    printf("单链表的长度为：%d\n", LengthLinkList(L));
    GetElement(L, 1, e);
    printf("1号位置的元素为：%d\n");
    printf("元素4在单链表中的位置为：%d\n", LocateElement(L, 4));
	cout << endl;
    LinkList La, Lb, Lc;
    printf("尾插法创建单链表La：\n");
    CreateListTail(La);
    PrintList(La);
    printf("尾插法创建单链表Lb：\n");
    CreateListTail(Lb);
    PrintList(Lb);
    MergeList(La, Lb, Lc);
    printf("合并单链表La和Lb后的新单链表Lc如下：\n");
    PrintList(Lc);
    return 0;
}

运行结果：

注意：

写法采用了C++引用参数的写法，LinkList &head，C语言下不支持这种写法，需要在C++环境下使用，即.cpp文件。

下面附上C语言的：

 /**
 * LinkList 本身已经是结构体指针，参数再使用LinkList *的形式
 * 可以理解为要想改变一个结构体指针，则需要取指针的指针。
 * 类似于改变int a，则需要使用 int *a，这里要改变LinkList head，则需要使用LinkList *head
 */
void CreatListTail(LinkList *head) {
    int x;
    LinkList *p, *q;

    *head = (LinkList *) malloc(LEN);
    q = *head;

    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList *) malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}
// 可以不传参，函数里面定义头指针，创建链表，然后把头指针返回，主函数用结构体指针接收即可
LinkList CreateListhead() {
    int x;
    LinkList *head, *p;

    head = (LinkList *) malloc(LEN);
    head->next = NULL;

    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList *) malloc(LEN);
        p->data = x;
        p->next = head->next;
        head->next = p;
    }
    return head;
}

到此这篇关于C语言实现单链表基本操作方法的文章就介绍到这了,更多相关C语言单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

详解C语言之单链表

目录一.思路步骤 1. 定义结构体 2.初始化 3.求当前数据元素的个数 4.插入 5.删除 6.释放内存空间二.代码总结一.思路步骤 1. 定义结构体 a.数据域:用来存放数据 b.指针域:用来存放下一个数据的位置 2.初始化申请头结点,并将其初始化为空 3.求当前数据元素的个数 a.设置一个指针变量p指向头结点和计数变量size等于0 b.循环判断p->next是否为空,如果不为空,就让指针p指向它的直接后继结点,并让size自增 c.返回size 4.插入 a.设置两个指针,一个
C语言链表与单链表详解

链表是什么及链表的优势链表是一种介于数组的另外一种数据结构: 我们知道数组可以存放很多的元素,这些元素都是呈线性排列,也就是一个挨着一个连续存放但是当元素足够多时,还能继续正常的存放吗? 事实上的不可以的,虽然系统的内存足够大,但是这些内存不都是连续的,这就导致会出现没有足够的空间去存储这些元素. 其次就是数组的大小需要你去申请,如果你申请的空间足够大,就会导致内存的浪费而链表就很好的解决了这两个问题链表的组成链表的作用就是相当与数组一样,储存你数据的但又不同于数组,链表把每一个游离
一文弄懂C语言如何实现单链表

目录一.单链表与顺序表的区别: 一.顺序表: 二.链表二.关于链表中的一些函数接口的作用及实现 1.头文件里的结构体和函数声明等等 2.创建接口空间 3.尾插尾删 4.头插头删 5.单链表查找 6.中间插入(在pos后面进行插入) 7.中间删除(在pos后面进行删除) 8.单独打印链表和从头到尾打印链表 9.test.c 总结一.单链表与顺序表的区别: 一.顺序表: 1.内存中地址连续 2.长度可以实时变化 3.不支持随机查找 4.适用于访问大量元素的,而少量需要增添/删除的元素的程序 5
C语言实现单链表基本操作方法

目录存储结构基本功能头插法创建单链表尾插法创建单链表获取指定位置的元素在指定位置插入元素删除指定位置的元素获取单链表的长度合并两个非递减的单链表晴链表遍历打印单链表附上完整代码存储结构 typedef int dataType://爱护据类型 typedef struct Node { DataType data; // 结点数据 struct Node *next; // 指向下一个结点的指针 } Node, *LinkList; 基本功能头插法创建单链表void
用C语言实现单链表的各种操作(二)

上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序. 复制代码代码如下: /* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){ LinkList *p; int n,i,j; int temp; n = ListLength(head); if(head == NULL || head->next == NULL) return head;
C语言实现单链表实现方法

C语言实现单链表实现方法链表和我们之前实现过的顺序表一样,都是简单的数据结构,链表分为单向链表.双向链表.循环链表.而单向链表又分为两种实现方法,一种为带头节点的单链表,一种为不带头节点的单链表.我们来具体看看不带头节点的单链表的实现单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点. 今天我们来实现一些单链表的简单接口先看看单链表的结构: (为了通用性,我们将类型重命名为DataType) typedef int DataType; //
C语言实现单链表反转

一.理解指针看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑.所以,要想写对链表代码,首先就要理解好指针. 有些语言有"指针"的概念,比如 C 语言:有些语言没有指针,取而代之的是"引用",比如 Java.Python.不管是"指针"还是"引用",实际上,它们的意思都是一样的,都是存储所指对象的内存地址. 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变
C语言基于单链表实现通讯录功能

本文实例为大家分享了C语言基于单链表实现通讯录功能的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<string.h> #pragma warning(disable:4996)://解决VS报严重性代码错误 typedef struct LNode { char name[20]; double ph_number; struct LNode* next; }LinkNode; //创建通
C语言数据结构单链表接口函数全面讲解教程

目录前言一.链表的概念及结构 1.概念二.链表的使用 1.遍历整个链表 2.尾插 3.头插 4.头删 5.尾删 6.任意位置插入数据 7.任意位置删除数据后记前言上一期数据结构专栏我们学习了顺序表后:C语言数据结构顺序表在运用时,细心的同学可能会发现,如果要头插.尾插或者任意位置.如果原先的空间已经被占满了,你是需要扩容的,动态链表扩容往往是2倍,但是扩容后,如果后面没有使用完全扩容后空间就会造成空间浪费,为了解决这个问题,我们今天将学习链表. 提示:以下是本篇文章正文内容,下面案
C语言使用单链表实现学生信息管理系统

本文实例为大家分享了C语言使用单链表实现学生信息管理系统,供大家参考,具体内容如下初学数据结构,记录一下学习过程. 运行结果如图: 1.运行界面 2.录入学生信息 3.按照总分进行排序代码如下: #define ERROR 0 #define OK 1 #define OVERFLOW -1; typedef int ElemType; typedef int Status; #include<stdio.h> #include<stdlib.h> #include<ma
C语言实现单链表的基本功能详解

1.首先简单了解一下链表的概念: 要注意的是链表是一个结构体实现的一种线性表,它只能从前往后,不可以从后往前(因为next只保存下一个节点的地址).在实现单链表的操作时,需要用指针来操作.很简单,注释写的很详细,欢迎大家指正哈哈哈哈~之前写的太烂了重新写了一下..... 2.代码展示: #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef struct linklist { int data
C语言实现单链表的快速排序算法

目录背景设计思路算法主要步骤快速排序算法实现整个程序源代码测试案例总结背景传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历
C语言实现单链表的基本操作分享

目录导语单链表单链表的特点定义初始化操作头插法尾插法删除第i个元素在第i个位置插入导语无论是顺序存储结构还是链式存储结构,在内存中进行存放元素的时候,不仅需要存放该元素的相关信息,还需要存放该元素和其他元素之间的关系,而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系,不需要额外的信息去表达元素和元素之间的关系,而对于链式存储这种非顺序存储的结构,需要额外附加指针去表示这种关系. 单链表每个结点除了存放数据元素外,还要存储指向下一个节点的指针