链表基础概念请参考其他书籍或文章。本文只列出完整测试代码
实现链表代码 头指针法(需要特判)，采用虚头节点，节省特判操作。
插入示例：
Node *p = &(l->head), *node = getNewNode(val);
while (ind--) p = p->next;
node->next = p->next;
p->next = node;
代码执行图解
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//结构定义
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct List {
Node head;//Node head虚拟头节点，注意与Node *head的区别
int length;
} List;
//函数声明
Node *getNewNode(int);
List *init_list();
void clear_node(Node *);
int insert(List *, int, int);
int erase(List *, int);
Node *getNewNode(int val) {//创建初始化节点
Node *node = (Node *)malloc(sizeof(Node));
node->data = val;
node->next = NULL;
return node;
}
List *init_list(){//创建初始化链表
List *l = (List *)malloc(sizeof(List));
l->head.next = NULL;//点是变量的访问，->是访问地址
l->length = 0;
return l;
}
int insert(List *l, int ind, int val){
if (l == NULL) return 0;
if (ind < 0 || ind > l->length) return 0;
Node *p = &(l->head), *node = getNewNode(val);
while (ind--) p = p->next;
node->next = p->next;
p->next = node;
l->length++;
return 1;
}
int erase(List *l, int ind) {
if(l == NULL) return 0;
if(ind < 0 || ind >= l->length) return 0;
Node *p = &(l->head), *q;
while(ind--) p = p->next;
q = p->next;
p->next = q->next;
clear_node(q);
l->length -= 1;
return 1;
}
void reverse(List *l){
if(l ==NULL) return;
Node *p = l->head.next, *q;//p = l->head.next指向第一个节点
l->head.next = NULL;//取下头节点
while(p) {
q = p->next;
p->next = l->head.next;
l->head.next = p;
p = q;
}
return ;
}
void output(List *l){
if(l ==NULL) return;
printf("list(%d) :", l->length);
for(Node *p = l->head.next; p; p = p->next) {
printf("%d->", p->data);
}
printf("NULL\n");
return ;
}
void clear_node(Node *node){//删除节点
if (node == NULL) return;
free(node);
return ;
}
void clear(List *l){//删除链表
if (l == NULL) return;
Node *p = l->head.next, *q;
while (p) {
q = p->next;
clear_node(p);
p = q;
}
free(l);
return ;
}
int main() {
srand(time(0));
#define MAX_OP 20
List *l =init_list();
for (int i = 0; i < MAX_OP; i++){
int val = rand() % 100;
int ind = rand() % (l->length +3) - 1;
int op = rand() % 4; // 百分之25的概率插入，因为case为0 1 2 3
switch (op) {
case 0:
case 2:{
printf("reverse the list!\n");
reverse(l);
output(l), printf("\n");
}
case 1:{
printf("insert %d at %d to List = %d\n", val, ind ,insert(l, ind, val));
}break;
case 3:{
printf("erase a item at %d from List = %d\n",ind, erase(l, ind));
}break;
}
output(l), printf("\n");
}
clear(l);
#undef MAX_OP
return 0;
}
