指针应用-----链表二

今天继续完善自己的链表，上次已经实现了链表的插入、遍历、销毁方法，对于链表的插入，我们上次是在头结点进行插入的，这次，我们来实现一个在任意结点进行插入的方法。

实现链表的另外一种插入方法----在任意位置进行插入:

 在实现它之前，先实现获取任意位置的结点的函数，为便在实现任意插入时会使用到它，先在头文件中定义：

list.h:

#ifndef _LIST_H_ #define _LIST_H_#include <assert.h>typedef struct node {int data;struct node* next; } node_t;typedef void (*FUNC)(node_t*);node_t* list_insert_front(node_t* head, int data);void list_for_each(node_t* head, FUNC f);node_t* list_free(node_t* head);node_t* list_get_node(node_t* head, int index);//获取指定位置的结点#endif /* _LIST_H_ */

具体实现list.c:

#include "list.h" #include <stdlib.h>node_t* list_insert_front(node_t* head, int data) {node_t* n = (node_t*)malloc(sizeof(node_t));assert(n != NULL);n->data = data;n->next = NULL;if (head == NULL)head = n;else{n->next = head;head = n;}return head; }void list_for_each(node_t* head, FUNC f) {while (head){f(head);head = head->next;} }node_t* list_free(node_t* head) {node_t* tmp;while (head){tmp = head;head = head->next;free(tmp);}return head; }node_t* list_get_node(node_t* head, int index) {assert(index >= 0);int j = 0;while (head && j < index){head = head->next;j++;}if (j == index)//说明已经找到结点return head;return head;//说明最终head指向NULL,没有找到结点}

上面的也可简写：

node_t* list_get_node(node_t* head, int index) {assert(index >= 0);int j = 0;while (head && j < index){head = head->next;j++;}return head;}

测试一下：

main.c:

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_free(head);assert(head == NULL);return 0; }

编译运行：

如果没有找到呢？

main.c:

int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 5);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_free(head);assert(head == NULL);return 0; }

编译运行：

好了，接着正式来定义任意插入的函数：

list.h:

#ifndef _LIST_H_ #define _LIST_H_#include <assert.h>typedef struct node {int data;struct node* next; } node_t;typedef void (*FUNC)(node_t*);node_t* list_insert_front(node_t* head, int data);void list_for_each(node_t* head, FUNC f);node_t* list_free(node_t* head);node_t* list_get_node(node_t* head, int index);node_t* list_insert_at(node_t* head, int data, int index);#endif /* _LIST_H_ */

list.c:

#include "list.h" #include <stdlib.h>node_t* list_insert_front(node_t* head, int data) {node_t* n = (node_t*)malloc(sizeof(node_t));assert(n != NULL);n->data = data;n->next = NULL;if (head == NULL)head = n;else{n->next = head;head = n;}return head; }void list_for_each(node_t* head, FUNC f) {while (head){f(head);head = head->next;} }node_t* list_free(node_t* head) {node_t* tmp;while (head){tmp = head;head = head->next;free(tmp);}return head; }node_t* list_get_node(node_t* head, int index) {assert(index >= 0);int j = 0;while (head && j < index){head = head->next;j++;}return head;}node_t* list_insert_at(node_t* head, int data, int index) {assert(index >= 0);if (index == 0)//等于就是头插入结点，直接调用现成的方法return list_insert_front(head, data);node_t* p;p = list_get_node(head, index - 1);if (p == NULL){fprintf(stderr, "error insert pos\n");exit(EXIT_FAILURE);}
　　//新建一个节点node_t* n = (node_t*)malloc(sizeof(node_t));assert(n != NULL);n->data = data;n->next = NULL;
　　//将节点进行链接n->next = p->next;p->next = n;return head; }

说明：

①fprintf表示向什么地方输出，如fprintf(stdio,"hello!");等价于printf("hello!");

②exit()表示程序退出，参数EXIT_FAILURE代表错误退出，它还有另外一个宏定义EXIT_SUCCESS，代表成功退出

程序测试：

main.c:

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_insert_at(head, 15, 1);list_for_each(head, print_node);putchar('\n');head = list_free(head);assert(head == NULL);return 0; }

编译：

其中的fprintf需要头文件：

所以在list.c中加入此头文件：

再次编译，运行：

如果插入失败会怎样呢？

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_insert_at(head, 15, 5);//这个位置没有元素，应该会插入失败list_for_each(head, print_node);putchar('\n');head = list_free(head);assert(head == NULL);return 0; }

编译运行：

实现链表的删除方法：

先定义删除方法：

list.h:

 

#ifndef _LIST_H_ #define _LIST_H_#include <assert.h>typedef struct node {int data;struct node* next; } node_t;typedef void (*FUNC)(node_t*);node_t* list_insert_front(node_t* head, int data);void list_for_each(node_t* head, FUNC f);node_t* list_free(node_t* head);node_t* list_get_node(node_t* head, int index);node_t* list_insert_at(node_t* head, int data, int index);node_t* list_remove_at(node_t* head, int index);#endif /* _LIST_H_ */

 

具体实现，在实现前，先用一个简单的图来解释下：

具体实现如下list.c:

node_t* list_remove_at(node_t* head, int index) {assert(index >= 0);node_t* n;if (index == 0)//这是移除首结点{n = head;head = head->next;free(n);}else{node_t* p = list_get_node(head, index - 1);if (p == NULL || p->next == NULL){fprintf(stderr, "error remove pos\n");exit(EXIT_FAILURE);}n = p->next;p->next = n->next;free(n);}return head; }

测试一下main.c:

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_insert_at(head, 15, 1);list_for_each(head, print_node);putchar('\n');head = list_remove_at(head, 1);list_for_each(head, print_node);putchar('\n');head = list_free(head);assert(head == NULL);return 0; }

编译运行：

如果移除的元素不存在呢？

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_insert_at(head, 15, 1);list_for_each(head, print_node);putchar('\n');head = list_remove_at(head, 5);//这个元素不存在，移除时会出错list_for_each(head, print_node);putchar('\n');head = list_free(head);assert(head == NULL);return 0; }

运行：

实现链表的查找方法：

list.h:

 

#ifndef _LIST_H_ #define _LIST_H_#include <assert.h>typedef struct node {int data;struct node* next; } node_t;typedef void (*FUNC)(node_t*);node_t* list_insert_front(node_t* head, int data);void list_for_each(node_t* head, FUNC f);node_t* list_free(node_t* head);node_t* list_get_node(node_t* head, int index);node_t* list_insert_at(node_t* head, int data, int index);node_t* list_remove_at(node_t* head, int index);node_t* list_find(node_t* head, int data, int* ret);//ret代表找到的链表的索引位置，返回值代表找到的链表结点#endif /* _LIST_H_ */

 

list.c:

#include "list.h" #include <stdlib.h> #include <stdio.h>node_t* list_insert_front(node_t* head, int data) {node_t* n = (node_t*)malloc(sizeof(node_t));assert(n != NULL);n->data = data;n->next = NULL;if (head == NULL)head = n;else{n->next = head;head = n;}return head; }void list_for_each(node_t* head, FUNC f) {while (head){f(head);head = head->next;} }node_t* list_free(node_t* head) {node_t* tmp;while (head){tmp = head;head = head->next;free(tmp);}return head; }node_t* list_get_node(node_t* head, int index) {assert(index >= 0);int j = 0;while (head && j < index){head = head->next;j++;}return head;}node_t* list_insert_at(node_t* head, int data, int index) {assert(index >= 0);if (index == 0)return list_insert_front(head, data);node_t* p;p = list_get_node(head, index - 1);if (p == NULL){fprintf(stderr, "error insert pos\n");exit(EXIT_FAILURE);}node_t* n = (node_t*)malloc(sizeof(node_t));assert(n != NULL);n->data = data;n->next = NULL;n->next = p->next;p->next = n;return head; }node_t* list_remove_at(node_t* head, int index) {assert(index >= 0);node_t* n;if (index == 0){n = head;head = head->next;free(n);}else{node_t* p = list_get_node(head, index - 1);if (p == NULL || p->next == NULL){fprintf(stderr, "error remove pos\n");exit(EXIT_FAILURE);}n = p->next;p->next = n->next;free(n);}return head; }node_t* list_find(node_t* head, int data, int* ret) {*ret = -1;int i = 0;while (head){if (head->data == data){*ret = i;break;}head = head->next;i++;}return head; }

测试main.c:

#include "list.h" #include <stdio.h>void print_node(node_t* n) {printf("data=%d ", n->data); }int main(void) {node_t* head = NULL;head = list_insert_front(head, 30);head = list_insert_front(head, 20);head = list_insert_front(head, 10);list_for_each(head, print_node);putchar('\n');node_t* n = NULL;n = list_get_node(head, 1);if (n != NULL)printf("data = %d\n", n->data);elseprintf("not found\n");head = list_insert_at(head, 15, 1);list_for_each(head, print_node);putchar('\n');head = list_remove_at(head, 1);list_for_each(head, print_node);putchar('\n');int ret;n = list_find(head, 20, &ret);if (n != NULL)printf("data = %d index = %d\n", n->data, ret);elseprintf("not found\n");head = list_free(head);assert(head == NULL);return 0; }

编译，运行：

好了，今天的学习到这，关于链表，下次会再次进行完善，下次见。

 

转载于:https://www.cnblogs.com/webor2006/p/3484812.html

总结

以上是生活随笔为你收集整理的指针应用-----链表二的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。