【数据结构】单链表的基本操作（C语言版）

10月前作者：殊迟分类：Toy博客阅读(59) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】单链表的基本操作（C语言版）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、单链表

1、单链表的定义：

2、单链表的优缺点：

二、单链表的基本操作算法（C语言）

1、宏定义

2、创建结构体

3、初始化

4、插入

4、求长度

5、清空

6、销毁

7、取值

8、查找

9、删除

10、头插法创建单链表

11、尾插法创建单链表

三、单链表的全部代码（C语言）

四、运行结果

一、单链表

1、单链表的定义：

单链表是一种链式存储的线性表，它用一组地址任意的存储单元来存放线性表中的数据元素。每个节点包含两个部分：数据域和指针域。数据域用于存储数据元素，指针域则存储下一个节点的地址。单链表的第一个节点称为头结点，最后一个节点称为尾结点。

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

每个节点包含两个部分：数据域和指针域。数据域用于存储数据元素，指针域则存储下一个节点的地址。链表中的数据是以结点来表示的，每个结点的构成包括元素（数据元素的映像）和指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链表中的每个结点在内存中不是按顺序排列的，而是通过指针链接在一起。单链表的第一个节点称为头结点，最后一个节点称为尾结点。

【数据结构】单链表的基本操作（C语言版）,数据结构,c语言,算法,链表

与顺序表相比，单链表的优点在于插入和删除操作方便，时间复杂度较低，但随机访问和空间利用率不如顺序表。在实际应用中，单链表通常作为其他数据结构的子结构，如哈希表的桶、图的邻接表等。

单链表定义了节点的基本结构，包括数据元素和指向下一个节点的指针。节点的插入和删除操作涉及指针的修改，而非直接修改节点内容。由于其非连续性的特性，链表无法像数组一样随机访问任意元素，而只能从头到尾依次访问。因此，对于需要频繁插入和删除元素的应用场景，单链表是一种高效的数据结构。

2、单链表的优缺点：

单链表的优点：

插入和删除操作方便：只需修改指针即可，不需要移动大量元素。
动态分配内存：可以根据需要开辟内存空间，避免了顺序表中的空间浪费问题。

单链表的缺点：

存储密度低：以节点为单位存储，不支持随机访问，查找较为麻烦。
空间利用率低：每个节点需要额外的空间来存储指针，导致空间浪费。
查找效率低：由于链表在内存中不连续，需要从头节点开始逐个节点遍历，时间复杂度较高。

二、单链表的基本操作算法（C语言）

1、宏定义

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

2、创建结构体

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

3、初始化

//单链表初始化
Status InitList(LinkList &head){
    head=new LNode;
    head->next=NULL;
    return OK;
}

4、插入

创建一个新的结点。

将新结点的数据域置为所需插入的数据。

根据插入位置的不同，将新结点的指针域指向插入位置的后一个结点。如果是头部插入，则将新结点的指针域指向头结点；如果是尾部插入，则将新结点的指针域指向空；如果是中间插入，则将新结点的指针域指向插入位置的后一个结点。

将插入位置前一个结点的指针域修改为指向新结点。如果是头部插入，则将头结点的指针域修改为指向新结点；如果是尾部插入，则将尾结点的指针域修改为指向新结点；如果是中间插入，则将插入位置前一个结点的指针域修改为指向新结点。

//插入
Status ListInsert(LinkList &head,int i,ElemType e){
    LinkList p=head;
    int j=0;
    while (p && (j<i-1)){
        p=p->next;
        ++j;
    }
    if (!p||j>i-1){
        return ERROR;
    }

    LNode *s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;

    return OK;
}

4、求长度

//求单链表长度
Status GetLinkListLength(LinkList head){
    LinkList p=head->next;
    int length=0;
    while (p){
        p=p->next;
        length++;
    }
    return length;
}

5、清空


//清空
Status ClearLinkList(LinkList &head){
    LinkList p = head->next;
    LinkList q;
    while(p){
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    return OK;
}

6、销毁


//销毁
Status DestoryLinkList(LinkList &head){
    LinkList p;
    while(head){
        p = head;
        head = head->next;
        delete p;
    }
    return OK;
}

7、取值

//取值
Status GetLinkList(LinkList head,int i,ElemType &e){
    LinkList p = head->next;
    int j = 0;
    while (p && j<i){
        p=p->next;
        j++;
    }
    if (!p || j>i){
        return ERROR;
    }
    e=p->data;

    return OK;
}

8、查找

//查找用函数返回查找元素的位置
int LocateLinkListElem(LinkList head,ElemType e){
    LinkList p=head->next;
    int j=1;
    while (p && (p->data != e)){
        p=p->next;
        j++;
    }
    if(p==NULL){
        return 0;
    }
    return j;
}

9、删除

找到要删除的结点的前一个结点。

将前一个结点的指针域修改为指向要删除的结点的下一个结点。

释放要删除的结点的存储空间。


//删除
Status ListDelete(LinkList &head,int i,ElemType &e){
    LinkList p=head;
    int j=0;
    while ((p->next) && (j<i-1)){
        p=p->next;
        ++j;
    }
    if (!(p->next)||j>i-1){
        return ERROR;
    }
    LinkList q=p->next;
    e=q->data;
    p->next=q->next;
    delete q;
    return OK;
}

10、头插法创建单链表

//头插法创建单链表
void CreateList_H(LinkList &head,int n){
    head=new LNode;
    head->next=NULL;
    for(int i=0;i<n;++i){
        LNode *p=new LNode;
        ElemType cin='a';
        cin>>p->data;
        p->next=head->next;
        head->next=p;
    }
}

11、尾插法创建单链表

//尾插法创建单链表
void CreateList_R(LinkList &head,int n){
    head=new LNode;
    head->next=NULL;
    LNode *r=head;
    for(int i=0;i<n;++i){
        LNode *p=new LNode;
        ElemType cin='a';
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

三、单链表的全部代码（C语言）

#include <stdio.h>

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//单链表初始化
Status InitList(LinkList &head){
    head=new LNode;
    head->next=NULL;
    return OK;
}

//功能菜单
int choice() {
    printf("==================================\n");
    printf("         单链表操作功能菜单          \n");
    printf("1、插入元素  2、查询表长  3、按位查找\n");
    printf("4、按值查找  5、删除元素  6、销毁链表\n");
    printf("7、清空链表  8、批量插入  9、结束程序\n");
    printf("10、头插法创建单链表11、尾插法创建单链表\n");
    printf("==================================\n");
    return 0;
}


//插入
Status ListInsert(LinkList &head,int i,ElemType e){
    LinkList p=head;
    int j=0;
    while (p && (j<i-1)){
        p=p->next;
        ++j;
    }
    if (!p||j>i-1){
        return ERROR;
    }

    LNode *s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;

    return OK;
}

//求单链表长度
Status GetLinkListLength(LinkList head){
    LinkList p=head->next;
    int length=0;
    while (p){
        p=p->next;
        length++;
    }
    return length;
}

//销毁
Status DestoryLinkList(LinkList &head){
    LinkList p;
    while(head){
        p = head;
        head = head->next;
        delete p;
    }
    return OK;
}

//清空
Status ClearLinkList(LinkList &head){
    LinkList p = head->next;
    LinkList q;
    while(p){
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    return OK;
}

//取值
Status GetLinkList(LinkList head,int i,ElemType &e){
    LinkList p = head->next;
    int j = 0;
    while (p && j<i){
        p=p->next;
        j++;
    }
    if (!p || j>i){
        return ERROR;
    }
    e=p->data;

    return OK;
}


//查找用引用型参数返回查找元素的位置
//LNode *LocateLinkList(LinkList head,ElemType e,Status &j){
//    LinkList p=head->next;
//    j=1;
//    while (p && p->data!=e){
//        p=p->next;
//        j++;
//    }
//    return p;
//}
//查找用函数返回查找元素的位置
int LocateLinkListElem(LinkList head,ElemType e){
    LinkList p=head->next;
    int j=1;
    while (p && (p->data != e)){
        p=p->next;
        j++;
    }
    if(p==NULL){
        return 0;
    }
    return j;
}

//删除
Status ListDelete(LinkList &head,int i,ElemType &e){
   LinkList p=head;
    int j=0;
   while ((p->next) && (j<i-1)){
       p=p->next;
       ++j;
    }

    if (!(p->next)||j>i-1){
        return ERROR;
    }
    LinkList q=p->next;
    e=q->data;
    p->next=q->next;
    delete q;
    return OK;
}

//头插法创建单链表
void CreateList_H(LinkList &head,int n){
    head=new LNode;
    head->next=NULL;
    for(int i=0;i<n;++i){
        LNode *p=new LNode;
        ElemType cin='a';
        cin>>p->data;
        p->next=head->next;
        head->next=p;
    }
}


//尾插法创建单链表
void CreateList_R(LinkList &head,int n){
    head=new LNode;
    head->next=NULL;
    LNode *r=head;
    for(int i=0;i<n;++i){
        LNode *p=new LNode;
        ElemType cin='a';
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

int main()
{
    LinkList list;

    //初始化
    printf("单链表正在初始化....\n");
    int InitStatus=InitList(list);
    if (InitStatus=OK){
        printf("单链表初始化成功！\n");
    }else{
        printf("单链表初始化失败！\n");
    }

    choice();    //调用功能菜单函数
    int temp=1;  //通过改变temp的值来跳出while循环

    while(temp) {
        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d",&flag);

        switch (flag) {//通过开关进行功能选择
            case 1:{//插入元素
                int insertIndex;
                ElemType inserElem;
                printf("请输入插入元素位置及插入元素(请在英文状态下输入): \n");
                scanf("%d,%c",&insertIndex,&inserElem);
                Status InsertS = ListInsert(list, insertIndex, inserElem);
                if(InsertS ==OK){
                    printf("向单链表%d个位置,插入元素为%c成功！\n",insertIndex,inserElem);
                    printf("======================================\n\n");
                }else{
                    printf("向单链表插入元素失败！\n");
                    printf("======================================\n\n");
                }
            }
                break;
            case 2:{//求单链表的长度
                int length=GetLinkListLength(list);
                printf("单链表的长度为:%d。 \n",length);
            }
                break;
            case 3:{//取值
                Status GetIndex;
                printf("请输入需要查询的元素的位置：\n");
                scanf("%d",&GetIndex);
                ElemType GetElem;
                int GetStatus=GetLinkList(list,GetIndex, GetElem);
                if (GetStatus=OK){
                    printf("从单链表中获取第%d位置元素成功，所获取到的元素为：%c。\n",GetIndex,GetElem);
                }else{
                    printf("从单链表中获取第%d位置元素失败！\n",GetIndex);
                }
            }
                break;
            case 4:{//查找
                //查找用引用型参数返回查找元素的位置
//                Status LocateIndex;
//                ElemType LocateElem;
//                printf("请输入想要查找元素：\n");
//                scanf("%c",&LocateElem);
//                LNode *LocateStatus = LocateLinkList(list,LocateElem,LocateIndex);
//                //printf("%d",LocateStatus);
//                if (LocateStatus == NULL) {
//                    printf("未查找到需要查找元素！\n");
//                } else {
//                    printf("查找到单链表中第%d元素为%c！\n",LocateIndex, LocateStatus->data);
//                }
                //查找用函数返回查找元素的位置
                ElemType LocateElem;
                printf("请输入想要查找元素：\n");
                getchar();    //用于接收回车
                scanf("%c",&LocateElem);
                Status LocateIndex = LocateLinkListElem(list,LocateElem);
                if (LocateIndex > 0) {
                    printf("从单链表中查找元素%c成功，它在单链表中的位置为第%d个！\n",LocateElem,LocateIndex);
                } else {
                    printf("从单链表中查找元素%c失败！\n",LocateElem);
                }
            }
                break;
            case 5:{//删除
                Status DeleteIndex;
                printf("请输入想要删除元素的位置：\n");
                scanf("%d",&DeleteIndex);
                ElemType DeleteElem;
                ElemType DeleteStatus = ListDelete(list,DeleteIndex,DeleteElem);
                if (DeleteStatus=OK){
                    printf("删除单链表第%d个位置的元素成功，删除的元素为：%c。\n",DeleteIndex,DeleteElem);
                }else{
                    printf("删除单链表第%d个位置的元素失败！\n",DeleteIndex);
                }
            }
                break;
            case 6:{//销毁
                Status DestoryStatus = DestoryLinkList(list);
                if (DestoryStatus == OK){
                    printf("单链表销毁成功！\n");
                }else{
                    printf("单链表销毁失败！\n");
                }
            }
                break;
            case 7:{//清空
                Status ClearStatus = ClearLinkList(list);
                if (ClearStatus == OK){
                    printf("单链表清空成功！\n");
                }else{
                    printf("单链表清空失败！\n");
                }
            }
                break;
            case 8:{//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                ElemType array[on];
                for (int i = 1; i <= on; i++) {
                    getchar();
                    printf("向单链表第%d个位置插入元素为:", (i));
                    scanf("%c", &array[i]);
                }

                for (int i = 1; i <= on; i++){
                    Status InsertStatus = ListInsert(list,i,array[i]);
                    if (InsertStatus=OK){
                        printf("向单链表第%d个位置插入元素%c成功！\n",i,array[i]);
                    }else{
                        printf("向单链表第%d个位置插入元素%c失败！\n",i,array[i]);
                    }
                }
            }
                break;
            case 9:{//退出程序
                temp=0;
//               return 0;
            }
                break;
            case 10:{//头插法创建单链表
//                ElemType EnterElement='e';
//                CreateList_H(list,EnterElement);
//                printf("前插法插入%c元素成功！\n",EnterElement);
            }
                break;
            case 11:{//尾插法创建单链表
//                ElemType EnterElem='a';
//                CreateList_R(list,EnterElem);
//                printf("后插法插入%c元素成功！\n",EnterElem);
            }
                break;
            default:
                printf("输入错误，无此功能，请检查输入:\n");
        }
    }

}

四、运行结果

【数据结构】单链表的基本操作（C语言版）,数据结构,c语言,算法,链表

【数据结构】单链表的基本操作（C语言版）,数据结构,c语言,算法,链表

【数据结构】单链表的基本操作（C语言版）,数据结构,c语言,算法,链表文章来源地址https://www.toymoban.com/news/detail-815496.html

到了这里，关于【数据结构】单链表的基本操作（C语言版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。 LinkList.h test.cpp （下面所有函数都默认在类中实现）我们以

2024年02月07日
浏览(58)
数据结构——单链表基本操作实现 (c++)

单链表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这里存储单元可以是连续的，也可以是不连续的），为了表示每个数据元素a与其直接后继数据元素之间的逻辑关系，除了存储信息本身外还要存储一个指示其直接后继的信息（地址）. 这两部分信

2024年02月03日
浏览(68)
【数据结构】单链表基本操作：查找、插入、删除、创建

链表由结点组成，结点由数据域和指针域组成。其中，数据域存放的就是数据元素，指针域存放下一个结点的地址。数据元素可以只有一个，也可以有多个不同类型的数据元素，甚至是数组。下图和代码来自《C Primer Plus》，该链表每个节结点同时含char类型和int类型。

2024年02月02日
浏览(63)
数据结构——单链表上基本操作的实现

1.按位序插入（带头结点）： ==ListInsert(L, i, e): ==在表L 中的第 i 个位置上插入指定元素 e = 找到第 i-1 个结点 ( 前驱结点 ) ，将新结点插入其后；其中头结点可以看作第 0 个结点，故 i=1 时也适用。 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; // 在第 i 个位置插入

2024年01月21日
浏览(57)
数据结构---双向链表的基本操作

头插法遍历链表尾插法头删法尾删法按位置插入数据按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

2024年02月22日
浏览(53)
数据结构 2.1 线性表的定义和基本操作

数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构）线性表是具有相同数据类型的n（n=0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。每个数据元素所占空间一样大，有次序。几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

2024年02月07日
浏览(53)
【数据结构】C语言实现双链表的基本操作

大家好，很高兴又和大家见面啦！！！经过前面几个篇章的内容分享，相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中，咱们将介绍双链表的创建以及一些基本操作，接下来跟我一起

2024年02月04日
浏览(62)
c语言数据结构——链表的实现及其基本操作

顺序表的问题及思考问题：中间/头部的插入删除，时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插

2023年04月09日
浏览(85)
【数据结构】循环双链表的基本操作（C语言版）

目录一、循环双链表 1、循环双链表的定义： 2、循环双链表的优缺点：二、循环双链表的基本操作算法（C语言） 1、宏定义 2、创建结构体 3、循环双链表的初始化 4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

2024年01月22日
浏览(59)
数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

实验的写法多种多样，但本文并未采用 #define 定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验其中，重点分析约瑟夫问题实验中代码的命名风格等均与下方博客

2024年02月16日
浏览(62)