赞
踩
链表:
添加节点:(注意指向顺序,避免数据丢失)
删除节点:
C语言代码:
创建节点(结构体数据类型),并创建具体节点实例的函数:
- // 节点(结构体数据类型)
- typedef struct Node
- {
- int data; // 数据为整数
- struct Node *next; // 指针指向下一个节点
- } LinkNode; // 别名LinkNode
- // 创建具体节点实例的函数
- LinkNode * createNode(int data)
- {
- LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode)); // 给节点分配内存空间
- if(node == NULL)
- {
- perror("Memory allocation failed");
- exit(-1);
- }
- node->data = data;
- node->next = NULL;
- return node;
- }
本文将头指针和链表长度作为全局变量:
- LinkNode *header = NULL; // 头指针,初始化指向NULL
- int length = 0; // 统计链表元素个数
添加节点:
- // 添加节点(链表头部添加)
- void addtop(int data)
- {
- LinkNode *node = createNode(data); // 调用createNode函数,创建具体节点
- node->next = header; // 先新节点指向头指针指向的节点
- header = node; // 再头指针指向新节点
- length++; // 每添加一个数据,length+1
- }
- // 添加节点(链表尾部添加)
- void append(int data)
- {
- if(length == 0) // 若空链表,在链表头部添加
- {
- addtop(data);
- return ;
- }
-
- LinkNode *node = createNode(data);
-
- LinkNode *cur = header; // 从头遍历元素,找到最后
- while(cur->next != NULL)
- {
- cur = cur->next;
- }
- cur->next = node;
- length++;
- }

- // 添加节点(在指定位置,位置从0开始)
- void insert(int location, int data)
- {
- if(length == 0) // 若空链表,在链表头部添加
- {
- addtop(data);
- return ;
- }
- if(length <= location) // 若链表长度<=指定位置,在链表尾部添加
- {
- append(data);
- return ;
- }
-
- LinkNode *node = createNode(data);
-
- LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,找到指定位置
- while(location > 0)
- {
- prev = cur;
- cur = cur->next;
- location--;
- }
-
- node->next = cur;
- prev->next = node;
- length++;
- }

删除节点:
- // 删除节点(删除链表头部节点)
- void deltop(void)
- {
- if(length == 0) return ; // 空链表,直接退出程序
-
- header = header->next;
- length--; // 每删除一个元素,length-1
- }
- // 删除节点(删除链表尾部节点)
- void pop(void)
- {
- if(length == 0) return ; // 空链表,直接退出程序
- if(length == 1) // 一个元素,头指针直接指向NULL
- {
- header = NULL;
- return ;
- }
-
- LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到最后的位置
- while(cur->next != NULL)
- {
- prev = cur;
- cur = cur->next;
- }
- prev->next = NULL;
- length--;
- }

- // 删除节点(删除链表指定位置的节点,位置从0开始)
- void delat(int location)
- {
- if(length == 0) return ; // 空链表,直接退出程序
- if(length - 1 <= location) // 链表长度-1<=指定位置,删除链表尾部节点
- {
- pop();
- return ;
- }
-
- LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到指定位置
- while(location > 0)
- {
- prev = cur;
- cur = cur->next;
- location--;
- }
- prev->next = cur->next;
- length--;
- }

- // 删除节点(删除指定数据)
- void del(int data)
- {
- LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,比对数据内容
- while(cur != NULL)
- {
- if(cur->data == data)
- {
- if(header == cur) // 若是第一个节点,头指针直接跳过该节点指向下一个节点
- {
- header = cur->next;
- }
- else // 否则 该节点上一个节点,直接跳过该节点指向下一个节点
- {
- prev->next = cur->next;
- }
-
- length--;
- return ;
- }
- prev = cur;
- cur = cur->next;
- }
- return ;
- }

遍历节点:
- void travel(void)
- {
- if(length == 0) return ; // 空链表,直接退出程序
-
- printf("linklist elements: ");
- LinkNode *cur = header;
- while(cur != NULL)
- {
- printf("%d \t", cur->data);
- cur = cur->next;
- }
- printf("\n");
- }
完整代码:(linklist.c)
- #include <stdio.h>
- #include <stdlib.h>
-
- /* structure */
- typedef struct Node // node structure
- {
- int data;
- struct Node *next;
- } LinkNode;
-
- /* global variables */
- LinkNode *header = NULL; // header pointer
- int length = 0; // the number of linklist elements
-
- /* function prototype */
- void addtop(int data); // add element to the top of the linklist
- void append(int data); // add element to the end of the linklist
- void insert(int location, int data); // add element to the specify location (start with 0)
- void travel(void); // show element one by one
- void deltop(void); // delete element from the top of the linklist
- void pop(void); // delete element from the end of the linklist
- void delat(int location); // delete element from the specify location (start with 0)
- void del(int data); // delete the specify data
-
- /* main function */
- int main(void)
- {
- addtop(5);
- printf("length is %d \n", length);
- travel();
-
- append(9);
- printf("length is %d \n", length);
- travel();
-
- insert(1,8);
- printf("length is %d \n", length);
- travel();
-
- addtop(3);
- printf("length is %d \n", length);
- travel();
-
- deltop();
- printf("length is %d \n", length);
- travel();
-
- pop();
- printf("length is %d \n", length);
- travel();
-
- delat(1);
- printf("length is %d \n", length);
- travel();
-
- del(7);
- printf("length is %d \n", length);
- travel();
-
- del(5);
- printf("length is %d \n", length);
- travel();
- }
-
- /* subfunction */
- LinkNode * createNode(int data) // create a node
- {
- LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
- if(node == NULL)
- {
- perror("Memory allocation failed");
- exit(-1);
- }
- node->data = data;
- node->next = NULL;
- return node;
- }
-
- void addtop(int data) // add element to the top of the linklist
- {
- LinkNode *node = createNode(data);
- node->next = header;
- header = node;
- length++;
- }
-
- void append(int data) // add element to the end of the linklist
- {
- if(length == 0)
- {
- addtop(data);
- return ;
- }
-
- LinkNode *node = createNode(data);
-
- LinkNode *cur = header;
- while(cur->next != NULL)
- {
- cur = cur->next;
- }
- cur->next = node;
- length++;
- }
-
- void insert(int location, int data) // add element to the specify location (start with 0)
- {
- if(length == 0)
- {
- addtop(data);
- return ;
- }
- if(length <= location)
- {
- append(data);
- return ;
- }
-
- LinkNode *node = createNode(data);
-
- LinkNode *prev, *cur = header;
- while(location > 0)
- {
- prev = cur;
- cur = cur->next;
- location--;
- }
-
- node->next = cur;
- prev->next = node;
- length++;
- }
-
- void travel(void) // show element one by one
- {
- if(length == 0) return ;
-
- printf("linklist elements: ");
- LinkNode *cur = header;
- while(cur != NULL)
- {
- printf("%d \t", cur->data);
- cur = cur->next;
- }
- printf("\n");
- }
-
- void deltop(void) // delete element from the top of the linklist
- {
- if(length == 0) return ;
-
- header = header->next;
- length--;
- }
-
- void pop(void) // delete element from the end of the linklist
- {
- if(length == 0) return ;
- if(length == 1)
- {
- header = NULL;
- return ;
- }
-
- LinkNode *prev, *cur = header;
- while(cur->next != NULL)
- {
- prev = cur;
- cur = cur->next;
- }
- prev->next = NULL;
- length--;
- }
-
- void delat(int location) // delete element from the specify location (start with 0)
- {
- if(length == 0) return ;
- if(length - 1 <= location)
- {
- pop();
- return ;
- }
-
- LinkNode *prev, *cur = header;
- while(location > 0)
- {
- prev = cur;
- cur = cur->next;
- location--;
- }
- prev->next = cur->next;
- length--;
- }
-
- void del(int data) // delete the specify data
- {
- LinkNode *prev, *cur = header;
- while(cur != NULL)
- {
- if(cur->data == data)
- {
- if(header == cur)
- {
- header = cur->next;
- }
- else
- {
- prev->next = cur->next;
- }
-
- length--;
- return ;
- }
- prev = cur;
- cur = cur->next;
- }
- return ;
- }

编译链接: gcc -o linklist linklist.c
执行可执行文件: ./linklist
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。