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

���录

一、单链表

1、单链表的定义：

2、单链表的优缺点：

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

1、宏定义

2、创建结构体

3、初始化

4、插入

4、求长度

5、清空

6、销毁 

7、取值

8、查找

9、删除

10、头插法创建单链表

11、尾插法创建单链表

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

四、运行结果

---

一、单链表

1、单链表的定义：

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

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

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

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

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

2、单链表的优缺点：

单链表的优点：

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

单链表的缺点：

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

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

1、宏定义

#define OK 1#define ERROR 0typedef 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、插入

1. 创建一个新的结点。
2. 将新结点的数据域置为所需插入的数据。
3. 根据插入位置的不同，将新结点的指针域指向插入位置的后一个结点。如果是头部插入，则将新结点的指针域指向头结点；如果是尾部插入，则将新结点的指针域指向空；如果是中间插入，则将新结点的指针域指向插入位置的后一个结点。
4. 将插入位置前一个结点的指针域修改为指向新结点。如果是头部插入，则将头结点的指针域修改为指向新结点；如果是尾部插入，则将尾结点的指针域修改为指向新结点；如果是中间插入，则将插入位置前一个结点的指针域修改为指向新结点。

//插入Status ListInsert(LinkList &head,int i,ElemType e){    LinkList p=head;    int j=0;    while (p && (jnext;        ++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 && jnext;        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、删除

1. 找到要删除的结点的前一个结点。
2. 将前一个结点的指针域修改为指向要删除的结点的下一个结点。
3. 释放要删除的结点的存储空间。

//删除Status ListDelete(LinkList &head,int i,ElemType &e){    LinkList p=head;    int j=0;    while ((p->next) && (jnext;        ++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>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>p->data;        p->next=NULL;        r->next=p;        r=p;    }}

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

#include #define OK 1#define ERROR 0typedef 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 && (jnext;        ++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 && jnext;        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) && (jnext;       ++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>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>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