C语言描述链表的实现及操作

目录

• 一.链表的创建操作
• 二.链表的遍历操作
• 三.链表的查询操作 
• 四.链表的插入操作
• 五.链表的删除操作
  • 删除整个链表操作
  • 删除链表中的元素
• 六.完整代码实现

 

正文

 

回到顶部

一.链表的创建操作

//    操作系统 win 8.1//    编译环境 Visual Stuido 2017#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef int ElementType;        //    定义数据类型,可根据需要进行其他类型定义                                //    链表节点的定义typedef struct ListNode {    ElementType  Element;        //    数据域，存放数据    ListNode* Next;        //    指向下一个链表节点}Node, *PNode;//    链表创建函数定义PNode CreateList(void) {    int len ;    //    用于定义链表长度    int val ;    //    用于存放节点数值    PNode PHead = (PNode)malloc(sizeof(Node));    //    创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）    if (PHead == NULL)    //    判断是否分配成功    {        printf("空间分配失败 \n");        exit(-1);    }    PNode PTail = PHead;    //    链表的末尾节点，初始指向头节点    PTail->Next = NULL;    //    最后一个节点指针置为空    printf("请输入节点个数：");    scanf_s("%d", &len);        //    输入节点个数    for (int i = 0; i < len; i++) {        PNode pNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点        if (pNew == NULL) {            printf("分配新节点失败\n");            exit(-1);        }        printf("请输入第 %d 个节点的数据：", i + 1);        scanf_s("%d", &val);    //    输入链表节点的数据        pNew->Element = val;    //    把数据赋值给节点数据域        PTail->Next = pNew;    //    末尾节点指针指向下一个新节点        pNew->Next = NULL;        //    新节点指针指向为空        PTail = pNew;    //    将新节点复制给末尾节点            }    printf("创建链表成功\n");    return PHead;    //    返回头节点}//    主函数 int main() {    PNode List = CreateList();    //创建一个指针，使其指向新创建的链表的头指针        return 0;}

运行结果

 

回到顶部

二.链表的遍历操作

//    定义链表遍历函数void TraverseList(PNode List) {    PNode P = List->Next;    //    首节点赋值给临时节点P    printf("遍历链表的值为：");    if (P == NULL)        printf("链表为空");    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值     {        printf("%d ", P->Element);        P = P->Next;    }    printf("\n");}

 

回到顶部

三.链表的查询操作 

//    定义链表查询函数PNode FindList(PNode List) {    PNode P = List->Next;    //    定义临时指针P指向首节点的地址    int num = 0;    //    用于记录链表节点位置    int val = 0;    //    用于存放要查询的值    printf("请输入要查询的数：");    scanf_s("%d", &val);    //    输入要查询的数值    while (P != NULL&&P->Element != val) {        P = P->Next;        ++num;    }    if (P != NULL)        printf("找到的节点为：%d", num + 1);    else        printf("找不到该节点");    printf("\n");    return P;}

 

回到顶部

四.链表的插入操作

//     定义链表插入函数//    在链表位置第pos节点前插入包含数据val的节点void InsertList(PNode List, int pos, int val) {    int position = 0;    PNode P = List;    //    定义节点p指向头节点                    //    寻找pos节点的前驱结点    while (P != NULL&&position<pos - 1)    {        P = P->Next;        ++position;    }    PNode Tmp = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据    if (Tmp == NULL)    {        printf("内存分配失败！");        exit(-1);    }    //    插入节点    Tmp->Element = val;    Tmp->Next = P->Next;    P->Next = Tmp;}

 

回到顶部

五.链表的删除操作

删除整个链表操作

//定义删除整个链表函数void DeleteTheList(PNode List) {    PNode P, Tmp;    P = List->Next;    //定义指针P指向链表要删除的链表List的第一个点节点    List->Next = NULL;    while (P != NULL) {        Tmp = P->Next;        //临时Tmp指向要删除的节点的下个节点        free(P);    //释放指针P指向的节点        P = Tmp;    //重新赋值    }    printf("删除链表成功！\n");}

 

删除链表中的元素

//   定义删除链表元素函数//    删除链表中的第pos节点void DeleteList(PNode List, int pos) {    int position = 0;    PNode P = List;    //    定义一个指针p指向链表头节点                    //    寻找pos节点位置的前驱节点    while (P != NULL&&position < pos - 1) {        P = P->Next;        ++position;    }    //    删除节点    PNode Tmp = P->Next;    //    定义临时指针Tmp指向要删除的节点    P->Next = Tmp->Next;    //    使要删除节点的前驱结点指向其后驱节点    free(Tmp);    //    释放删除节点的内存空间，防止内存泄漏    Tmp = NULL;    //    使q指向空指针，防止产生野指针}

回到顶部

六.完整代码实现

//    操作系统 win 8.1//    编译环境 Visual Stuido 2017#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef int ElementType;        //    定义数据类型,可根据需要进行其他类型定义                                //    链表节点的定义typedef struct ListNode {    ElementType  Element;        //    数据域，存放数据    ListNode* Next;        //    指向下一个链表节点}Node, *PNode;//    函数声明PNode CreateList(void);    //    声明创建链表函数void TraverseList(PNode List);    //    声明遍历链表函数void InsertList(PNode List, int pos, int val);        //    声明链表插入函数void DeleteTheList(PNode List);    //    声明删除整个链表函数void DeleteList(PNode List, int pos);    //    声明删除链表元素函数PNode FindList(PNode List);    //    声明链表查询函数//    主函数 int main() {    PNode List = CreateList();    //    创建一个指针，使其指向新创建的链表的头指针        TraverseList(List);        //    遍历链表    FindList(List);        //    链表查询        InsertList(List, 3, 100);    //    链表插入，在第三个位置插入数值100    TraverseList(List);    DeleteList(List, 3);    //    删除链表第三个节点    TraverseList(List);    DeleteTheList(List);    //    删除整个链表    TraverseList(List);    return 0;}//    创建链表函数定义PNode CreateList(void) {    int len ;    //    用于定义链表长度    int val ;    //    用于存放节点数值    PNode PHead = (PNode)malloc(sizeof(Node));    //    创建分配一个头节点内存空间    if (PHead == NULL)    //    判断是否分配成功    {        printf("空间分配失败 \n");        exit(-1);    }    PNode PTail = PHead;    //    链表的末尾节点，初始指向头节点    PTail->Next = NULL;    //    最后一个节点指针置为空    printf("请输入节点个数：");    scanf_s("%d", &len);        //    输入节点个数    for (int i = 0; i < len; i++) {        PNode PNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点        if (PNew == NULL) {            printf("分配新节点失败\n");            exit(-1);        }        printf("请输入第 %d 个节点的数据：", i + 1);        scanf_s("%d", &val);    //    输入链表节点的数据        PNew->Element = val;    //    把数据赋值给节点数据域        PTail->Next = PNew;    //    末尾节点指针指向下一个新节点        PNew->Next = NULL;        //    新节点指针指向为空        PTail = PNew;    //    将新节点复制给末尾节点            }    printf("创建链表成功\n");    return PHead;    //    返回头节点}//    定义链表遍历函数void TraverseList(PNode List) {    PNode P = List->Next;    //    首节点赋值给临时节点P    printf("遍历链表的值为：");    if (P == NULL)        printf("链表为空");    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值     {        printf("%d ", P->Element);        P = P->Next;    }    printf("\n");}//    定义链表查询函数PNode FindList(PNode List) {    PNode P = List->Next;    //    定义临时指针P指向首节点的地址    int num = 0;    //    用于记录链表节点位置    int val = 0;    //    用于存放要查询的值    printf("请输入要查询的数：");    scanf_s("%d", &val);    //    输入要查询的数值    while (P != NULL&&P->Element != val) {        P = P->Next;        ++num;    }    if (P != NULL)        printf("找到的节点为：%d", num + 1);    else        printf("找不到该节点");    printf("\n");    return P;}//     定义链表插入函数//    在链表位置第pos节点前插入包含数据val的节点void InsertList(PNode List, int pos, int val) {    int position = 0;    PNode P = List;    //    定义节点p指向头节点                    //    寻找pos节点的前驱结点    while (P != NULL&&position<pos - 1)    {        P = P->Next;        ++position;    }    PNode Tmp = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据    if (Tmp == NULL)    {        printf("内存分配失败！");        exit(-1);    }    //    插入节点    Tmp->Element = val;    Tmp->Next = P->Next;    P->Next = Tmp;}//定义删除整个链表函数void DeleteTheList(PNode List) {    PNode P, Tmp;    P = List->Next;    //定义指针P指向链表要删除的链表List的第一个点节点    List->Next = NULL;    while (P != NULL) {        Tmp = P->Next;        //临时Tmp指向要删除的节点的下个节点        free(P);    //释放指针P指向的节点        P = Tmp;    //重新赋值    }    printf("删除链表成功！\n");}//    定义删除链表元素函数//    删除链表中的第pos节点void DeleteList(PNode List, int pos) {    int position = 0;    PNode P = List;    //    定义一个指针p指向链表头节点                    //    寻找pos节点位置的前驱节点    while (P != NULL&&position < pos - 1) {        P = P->Next;        ++position;    }    //    删除节点    PNode Tmp = P->Next;    //    定义临时指针Tmp指向要删除的节点    P->Next = Tmp->Next;    //    使要删除节点的前驱结点指向其后驱节点    free(Tmp);    //    释放删除节点的内存空间，防止内存泄漏    Tmp = NULL;    //    使q指向空指针，防止产生野指针}

运行结果