双向链表的实现
摘要:本文介绍双向链表的实现:创建、插入、删除,以及宏定义版本
所谓双链表即每个节点有两个指针:prev指向前一个节点,next指向后一个节点
节点定义:
struct node {
int data;
struct node *prev;
struct node *next;
};
首先需要创建节点:
struct node* create_node(int data) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
if(newnode == NULL) {
printf("内存分配失败");
exit(1);
}
newnode->prev = NULL;
newnode->next = NULL;
newnode->data = data;
return newnode;
}
对节点进行插入操作:
1.头插法
void insert(struct node **head, int data) {
struct node *newnode = create_node(data);
if (*head == NULL){
*head = newnode;
return;
}
newnode->next = *head;
(*head)->prev = newnode;
*head = newnode;
}
2.尾插法:
void insert(struct node **head, int data) {
struct node *newnode = create_node(data);
struct node *current = *head;
if (current->next != NULL) {
current = current->next;
}
current->next = newnode;
newnode->prev = current;
}
删除一个节点:分为表头、表中、表尾
void delete(struct node**head, int data) {
int status = 0;
struct node *current = *head;
while (current != NULL) {//从头节点遍历到最后一个节点
if (current->data == data) {
status = 1;//找到了
break;
}
current = current->next;
}
if (!status) printf("未找到该数据所在节点\n");
else {//节点在表尾
if(current->next == NULL) {
if (current->prev != NULL) // 先判断
current->prev->next = NULL;
free(current);
}
else if(current->prev == NULL) {//*******节点在表头!需要修改*head!**********
*head = current->next;
if(current->next != NULL)
current->next->prev = NULL;//考虑删除该节点为唯一的节点的情况
free(current);
}
else{//节点在表中
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
}
(current) = NULL; /* 将current置为NULL 避免悬空指针(悬空指针指向一个已经被释放的空间的地址,没有访问权限)*/
}
}
宏定义头插法: list是链表头指针,item是要插入的指针
#define LIST_INSERT(item, list) do {\
if ((item) != NULL) {\
(item)->prev = NULL;\
if ((list) != NULL) {\
(item)->next = (list);\
(list)->prev = (item);\
} else {\
(item)->next = NULL;\
}\
(list) = (item);\ // 更新头指针
}\
} while(0)
宏定义尾插法:
#define LIST_APPEND(item, list) do {\
if ((item) != NULL) {\
if ((list) == NULL) {\
(list) = (item);\
(item)->prev = NULL;\
} else {\
ListNode *temp = (list);\
while (temp->next != NULL) {\
temp = temp->next;\
}\
temp->next = (item);\
(item)->prev = temp;\
}\
(item)->next = NULL;\
}\
} while(0)
宏定义删除节点: 提供要删除的指针,进行删除
#define LIST_REMOVE(item, list) do {\
if ((item) != NULL) {\
if ((item)->prev != NULL) (item)->prev->next = (item)->next;\
if ((item)->next != NULL) (item)->next->prev = (item)->prev;\
if ((list) == (item)) (list) = (item)->next;\
(item)->prev = (item)->next = NULL;\
}\
} while(0)
宏定义查找删除节点:根据节点的data数据,先查找后删除:
#define DELETE_NODE(head, data) do {\
int status = 0;\
struct node *current = *(head);\
while (current != NULL) {\
if (current->data == data) {\
status = 1;\
break;\
}\
current = current->next;\
}\
if (!status) {\
printf("未找到该数据所在节点\n");\
} else {\
struct node *temp = current;\
if (current->next == NULL) {\
if (current->prev != NULL)\
current->prev->next = NULL;\
free(temp);\
} else if (current->prev == NULL) {\
*(head) = current->next;\
current->next->prev = NULL;\
free(temp);\
} else {\
current->prev->next = current->next;\
current->next->prev = current->prev;\
free(temp);\
}\
(current) = NULL; /* 将current置为NULL 避免悬空指针*/\
}\
} while(0)
原文地址:https://blog.csdn.net/2303_77208351/article/details/140201122
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!