单链表的基本操作

文章目录

• 单链表的基本操作
• 1.基础知识预备
• 2.创建节点
• 3.创建指定长度的单链表并赋值
• 4.打印节点
• 5.插入节点
• 6.删除节点
• 7.查找节点
• 8.完整代码

1.基础知识预备

1. malloc()
   原型：void* malloc (size_t size);

作用：在堆区分配 size 字节的内存空间。

返回值：成功返回分配的内存地址，失败则返回NULL。

注意：分配内存在动态存储区（堆区），手动分配，手动释放，申请时空间可能有也可能没有，需要自行判断，由于返回的是void*，建议手动强制类型转换。
2) calloc()
原型：void* calloc(size_t n, size_t size);

功能：在堆区分配 n*size 字节的连续空间。

返回值：成功返回分配的内存地址，失败则返回NULL。

注意：calloc() 函数是对 malloc() 函数的简单封装，参数不同，使用时务必小心，第一参数是第二参数的单元个数，第二参数是单位的字节数。
3) realloc()
原型：void* realloc(void *ptr, size_t size);

功能：对 ptr 指向的内存重新分配 size 大小的空间，size 可比原来的大或者小，还可以不变（如果你无聊的话）。

返回值：成功返回更改后的内存地址，失败则返回NULL。
4) free()
原型：void free(void* ptr);

功能：释放由 malloc()、calloc()、realloc() 申请的内存空间。

2.创建节点

//创建链表结点typedef struct Table {    int data;    struct Table *next;} node;

3.创建指定长度的单链表并赋值

//初始化链表,有头结点，使用尾插法,输入长度，返回表头node *init(int len) {    printf("当前链表长度是:%d\n输入链表元素:", len);    node *head = (node *) malloc(sizeof(node));//head代表的是头节点的地址    if (!head) { printf("内存分配失败\n"); exit(0);    }    node *temp = head;//这个指针是用来连接链表的    temp->next = NULL;    for (int i = 0; i < len; i++) { node *new = (node *) malloc(sizeof(node));//创建新节点，申请内存空间 if (!new) {     printf("内存分配失败\n");     exit(0); } scanf_s("%d", &new->data); temp->next = new; temp = new;//这两句不能调换    }    temp->next = NULL;    return (node *) head;}

4.打印节点

//打印链表，接收表头，无返回值void prints(node *x) {    node *temp = x;    int first = 0;    printf("当前链表元素是:");    while (temp->next) { temp = temp->next;//最重要的一步,因为头节点没有数据域 //printf("%d", temp->data); if (first == 0) {     printf("");     printf("%d", temp->data); } if (first == 1) {     printf(" ");     printf("%d", temp->data); } first = 1;    }    printf("\n");}

5.插入节点

//插入元素，接收表头，插入位置和插入元素，返回新表头node *insert(node *x, int pos, int elem) {    node *temp = x;    int i = 0;    while ((temp != NULL) && (i < pos - 1)) { temp = temp->next; ++i;    }    if ((temp == NULL) || (i > pos - 1)) { printf("insert error!\n"); return (node *) temp;    }    node *new = (node *) malloc(sizeof(node));    new->data = elem;    new->next = temp->next;    temp->next = new;    return (node *) x;}

6.删除节点

//删除节点，接收表头，位置和数据与地址，返回新表头node *delete(node *x, int pos) {    node *temp = x;    for(int i = 1;i<pos;i++)    { temp = temp->next; if(temp->next==NULL) {     printf("没有该结点");     return x; }    }    node *del = temp->next;    temp->next = temp->next->next;    free(del);    return (node *) x;}

7.查找节点

//查找元素位置,接收表头和要查找的元素，返回位置int search(node *x, int elem) {    node *temp = x;    //int pos = 0;    int i = 1;    while (temp->next) { temp = temp->next;//指向开始结点 if (elem == temp->data) {     //pos = i;     printf("该元素的位置是:%d\n", i);     return i; } i++;    }    return -1;}

8.完整代码

#include#include//创建链表结点typedef struct Table {    int data;    struct Table *next;} node;node *init(int len);//初始化int search(node *x, int elem);//查找元素位置node *revise(node *x, int pos, int new_elem);//修改数据域node *insert(node *x, int pos, int elem);//插入元素node *delete(node *x, int pos);//删除节点//初始化链表,有头结点，使用尾插法,输入长度，返回表头node *init(int len) {    printf("当前链表长度是:%d\n输入链表元素:", len);    node *head = (node *) malloc(sizeof(node));//head代表的是头节点的地址    if (!head) { printf("内存分配失败\n"); exit(0);    }    node *temp = head;//这个指针是用来连接链表的    temp->next = NULL;    for (int i = 0; i < len; i++) { node *new = (node *) malloc(sizeof(node));//创建新节点，申请内存空间 if (!new) {     printf("内存分配失败\n");     exit(0); } scanf_s("%d", &new->data); temp->next = new; temp = new;//这两句不能调换    }    temp->next = NULL;    return (node *) head;}//查找元素位置,接收表头和要查找的元素，返回位置int search(node *x, int elem) {    node *temp = x;    //int pos = 0;    int i = 1;    while (temp->next) { temp = temp->next;//指向开始结点 if (elem == temp->data) {     //pos = i;     printf("该元素的位置是:%d\n", i);     return i; } i++;    }    return -1;}//修改结点数据域，接收表头，修改位置，和新元素，返回新表头node *revise(node *x, int pos, int new_elem) {    node *temp = x;    temp = temp->next;    for (int i = 1; i < pos; i++) { temp = temp->next;    }    temp->data = new_elem;    return x;}//插入元素，接收表头，插入位置和插入元素，返回新表头node *insert(node *x, int pos, int elem) {    node *temp = x;    int i = 0;    while ((temp != NULL) && (i < pos - 1)) { temp = temp->next; ++i;    }    if ((temp == NULL) || (i > pos - 1)) { printf("insert error!\n"); return (node *) temp;    }    node *new = (node *) malloc(sizeof(node));    new->data = elem;    new->next = temp->next;    temp->next = new;    return (node *) x;}//删除节点，接收表头，位置和数据与地址，返回新表头node *delete(node *x, int pos) {    node *temp = x;    for(int i = 1;i<pos;i++)    { temp = temp->next; if(temp->next==NULL) {     printf("没有该结点");     return x; }    }    node *del = temp->next;    temp->next = temp->next->next;    free(del);    return (node *) x;}//打印链表，接收表头，无返回值void prints(node *x) {    node *temp = x;    int first = 0;    printf("当前链表元素是:");    while (temp->next) { temp = temp->next;//最重要的一步 //printf("%d", temp->data); if (first == 0) {     printf("");     printf("%d", temp->data); } if (first == 1) {     printf(" ");     printf("%d", temp->data); } first = 1;    }    printf("\n");}//init,search,revise,insert,delete,printint main() {    node *test;    int length;    int search_elem;    int revise_pos,revise_elem;    int insert_pos, insert_elem;    int delete_pos;    //测试init,prints    printf("输入链表长度:");    scanf_s("%d", &length);    test = init(length);    prints(test);    //测试search    printf("输入要查找的元素的值:");    scanf_s("%d", &search_elem);    search(test, search_elem);    //测试revise    printf("输入要修改的元素位置:");    scanf_s("%d", &revise_pos);    printf("输入新的元素:");    scanf_s("%d", &revise_elem);    revise(test, revise_pos, revise_elem);    prints(test);    //测试insert    printf("输入插入元素位置:");    scanf_s("%d",&insert_pos);    printf("输入要插入的新元素:");    scanf_s("%d",&insert_elem);    insert(test,insert_pos,insert_elem);    prints(test);    //测试delet    printf("输入删除元素的位置:");    scanf_s("%d",&delete_pos);    delete(test,delete_pos);    prints(test);    return 0;}