链表总结
| 单向链表 | 单向循环链表 | 双向链表 | 双向循环链表 | |
| 设计节点 | struct list_node{ int data; struct list_node* next; } | struct list_node{ int data; struct list_node* next; } | struct list_node{ int data; struct list_node* next; struct list_node* prev; } | struct list_node{ int data; struct list_node* next; struct list_node* prev; } |
| 初始化头节点 | 为头节点申请空间，数据域无效 head -> next = NULL; | 为头节点申请空间，数据域无效 head -> next = NULL; | 为头节点申请空间，数据域无效 head -> next = NULL; head -> prev = NULL; | 为头节点申请空间，数据域无效 head -> next = head; head -> prev = head; |
| 尾插数据 | 为新节点申请空间，数据域由用户赋值 new->data = data; new -> next = NULL; for(p=head;p->next!= NULL;p=p->next); p->next=new; | 为新节点申请空间，数据域由用户赋值 new->data = data; new -> next = NULL; for(p=head;p->next!= head;p=p->next); p->next=new; | 为新节点申请空间，数据域由用户赋值 new ->data = data; new ->next = NULL; for(p=head;p->next !=NULL;p=p->next); p->next=new; new->prev=p; | 为新节点申请空间，数据域由用户赋值 new->data = data; new ->next=head; struct list_node * p=head->prev; p->next=new; new->prev=p; head->prev = new; |
| 头插数据 | 为新节点申请空间，数据域由用户赋值 new->next = head->next; head->next = new; | 为新节点申请空间，数据域由用户赋值 new->next = head->next; head->next = new; | 为新节点申请空间，数据域由用户赋值 new ->next=head->next; new->prev=head; if(head->next!=NULL) { head->next->prev=new; } head->next = new; | 为新节点申请空间，数据域由用户赋值 new->next =head->next; new->prev=head; head->next->prev=new; head->next=new; |
| 往后遍历 | struct list_node *p=NULL; for(p=head->next;p!=NULL;p=p->next) { 打印内容； } | struct list_node *p=NULL; for(p=head->next;p!=head;p=p->next) { 打印内容； } | struct list_node *p = NULL; for(p=head->next;p!=NULL;p=p->next) { 打印内容； } | struct list_node *p=NULL; for(p=head->next;p!=head;p=p->next) { 打印内容； } |
| 往前遍历 | 无 | 无 | struct list_node *p = NULL; for(p=head;p->next!=NULL;p=p->next) for(;p!=head;p=p->prev) { 打印内容； } | struct list_node *p=NULL; p=head->prev; for(;p!=head;p=p->prev) { 打印内容； } |
| 删除链表 | struct list_node *p=NULL; struct list_node *q=NULL; for(q=p=head;p!=NULL;p=q) { q=p->next; free(p); } | struct list_node *p=NULL; struct list_node *q=NULL; for(p=head;p->next!=head;p=p->next); p->next = NULL; for(q=p=head;p!=head;p=q) { q=p->next; free(p); } | struct list_node *p=NULL; struct list_node *q=NULL; for(q=p=head;p!=NULL;p=q) { q=p->next; free(p); } | struct list_node *p=NULL; struct list_node *q=NULL; p=head->prev; p->next=NULL; for(q=p=head;p!=NULL;p=q) { q=p->next; free(p); } |
单向链表
#include <stdio.h>
#include <stdlib.h>
/*
*
* 单向链表 增删改查
*
*/
/* 节点 */
typedef struct list_node
{
int data;
struct list_node *next;
}list_node, *list;
/* 头节点初始化函数 */
list list_init(void)
{
list head = malloc(sizeof(list_node));
if (head == NULL)
{
printf("malloc head fail!\n");
return 0;
}
head->next = NULL;
return head;
}
/* 插入尾部节点函数 */
void insert_list_tail(list head, int data)
{
list new = malloc(sizeof(list_node));
/*找到当前链表最后一个节点*/
list p = head;
while (p->next != NULL)
{
p = p->next;
}
p->next = new;
new->data = data;
new->next = NULL;
return;
}
/* 插入节点在链表头部 */
void insert_list_head(list head, int data)
{
list new = malloc(sizeof(list_node));
new->data = data;
new->next = head->next;
head->next = new;
return;
}
/* 删除节点 */
void delete_node(list head, int data)
{
list p = head->next;
list tmp = head;
while (p != NULL)
{
if (p->data == data)
{
printf("p -> %d delete success!\n", p->data);
tmp->next = p->next;
free(p);
return;
}
tmp = p;
p = p->next;
}
printf("no data ! delete fail!\n");
return;
}
/* 查找节点 */
void search_node(list head, int data)
{
list p = head->next;
while (p != NULL)
{
if (p->data == data)
{
printf("p -> %d search success!\n", p->data);
return;
}
p = p->next;
}
/* 遍历链表没找到 */
printf("search fail!\n");
return;
}
/* 删除整个链表 */
void delete_list(list head)
{
list p = head;
list q = head;
while (p != NULL)
{
p = p->next;
free(q);
q = p;
}
printf("delete list success!\n");
return;
}
/* 打印链表 */
void printf_list(list head)
{
list tmp = head->next;
/* 判断是否为空 */
if (tmp == NULL)
{
printf("NULL!");
return;
}
while (tmp != NULL)
{
printf("%d", tmp->data);
tmp = tmp->next;
if (tmp != NULL)
{
printf(" -> ");
}
}
printf("\n");
return;
}
int main(int argc, char *argv[])
{
/*初始化头节点*/
list head = list_init();
printf_list(head);
return 0;
}
单向循环链表
#include <stdio.h>
#include <stdlib.h>
/*
* 单向循环链表 增删改查
*/
/* 节点*/
typedef struct list_node
{
int data;
struct list_node* next;
}list_node,*list;
/*列表初始化*/
list init_list(void)
{
list head = malloc(sizeof(list_node));
if (head == NULL)
{
printf("head malloc fail!\n");
return 0;
}
head->next = head;
return head;
}
/*插入头节点*/
void insert_node_head(list head,int data)
{
list new = malloc(sizeof(list_node));
if (new == NULL)
{
printf("new node malloc fail!\n");
return 0;
}
new->data = data;
new->next = head->next;
head->next = new;
return;
}
/*插入尾节点*/
void insert_node_tail(list head,int data)
{
list new = malloc(sizeof(list_node));
if (new == NULL)
{
printf("new node malloc fail!\n");
return 0;
}
/*找到最后一个节点(指向头节点)*/
list tmp = head;
while (tmp->next != head)
{
tmp = tmp->next;
}
new->data = data;
new->next = head;
tmp->next = new;
}
void delete_node(list head,int data)
{
list p = head->next;
list q = head;
while (p != head)
{
if (p->data == data)
{
printf("p -> %d delete success!\n", p->data);
q->next = p->next;
free(p);
return;
}
q = p;
p = p->next;
}
printf("delete fail!\n");
return;
}
void printf_list(list head)
{
list tmp = head->next;
while (tmp != head)
{
printf("%d", tmp->data);
if (tmp->next != head)
{
printf("->");
}
tmp = tmp->next;
}
printf("\n");
}
int main(int argc, char* argv[])
{
list head;
head = init_list();
/*插入尾节点*/
insert_node_tail(head, 50);
insert_node_tail(head, 60);
insert_node_tail(head, 70);
/*插入头节点*/
insert_node_head(head,40);
insert_node_head(head,30);
insert_node_head(head,10);
/*打印链表*/
printf_list(head);
delete_node(head, 30);
delete_node(head, 40);
printf_list(head);
delete_node(head, 6);
}
双向链表
#include <stdio.h>
#include <stdlib.h>
/*
* 双向链表
* 注意 双向链表头插法只有头节点时情况
*/
typedef struct list_node {
int data;
struct list_node* next;
struct list_node* prev;
}list_node,*list;
list init_list(void)
{
//头节点申请空间
list head = NULL;
head = malloc(sizeof(list_node));
if (NULL == head)
{
printf("head_node malloc fail!\n");
return 0 ;
}
//头节点赋值
head->next = NULL;
head->prev = NULL;
//返回头节点
return head;
}
/*头插数据*/
void insert_data_to_list_head(list head, int data)
{
//新节点申请空间
list new = malloc(sizeof(list_node));
if (NULL == new)
{
printf("new_node malloc fail!\n");
return;
}
new->data = data;
new->next = head->next;
//双向链表头插注意只有头节点时情况
if (head->next != NULL) {
head->next->prev = new;
}
new->prev = head;
head->next = new;
}
/*尾插数据*/
void insert_data_to_list_tail(list head, int data)
{
//新节点申请空间
list new = malloc(sizeof(list_node));
if (NULL == new)
{
printf("new_node malloc fail!\n");
return;
}
//赋值
new->data = data;
//遍历找最后一个节点
list p = head;
while (p->next != NULL)
{
p = p->next;
}
new->next = p->next;
new->prev = p;
p->next = new;
}
void delete_node(list head, int data)
{
list tmp = head->next;
while (tmp != NULL)
{
if (tmp->data == data)
{
tmp->prev->next = tmp->next;
if (tmp->next != NULL) {
tmp->next->prev = tmp->prev;
}
free(tmp);
return ;
}
tmp = tmp->next;
}
}
void delete_list(list head)
{
list p = head;
list q = head;
while (p != NULL)
{
p = p->next;
free(q);
q = p;
}
}
/*遍历数据*/
void show_list(list head)
{
list p = head->next;
while (p != NULL)
{
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
/*反向遍历*/
void show_list2(list head)
{
list p = head;
while (p->next != NULL)
{
p = p->next;
}
while(p!=head)
{
printf("%d\t", p->data);
p = p->prev;
}
printf("\n");
}
int main()
{
list head = init_list();
insert_data_to_list_head(head,30);
insert_data_to_list_head(head,20);
insert_data_to_list_head(head,10);
show_list(head);
delete_node(head, 20);
show_list(head);
delete_list(head);
show_list(head);
return 0;
}
双向循环链表
#include <stdio.h>
#include <stdlib.h>
/*
* 双向循环链表
*/
typedef struct list_node {
int data;
struct list_node* next;
struct list_node* prev;
}list_node,*list;
list init_list(void)
{
//头节点申请空间
list head = NULL;
head = malloc(sizeof(list_node));
if (NULL == head)
{
printf("head_node malloc fail!\n");
return 0 ;
}
//头节点赋值
head->next = head;
head->prev = head;
//返回头节点
return head;
}
/*头插数据*/
void insert_data_to_list_head(list head, int data)
{
//新节点申请空间
list new = malloc(sizeof(list_node));
if (NULL == new)
{
printf("new_node malloc fail!\n");
return;
}
new->data = data;
new->next =head->next;
new->prev=head;
head->next->prev=new;
head->next=new;
}
/*尾插数据*/
void insert_data_to_list_tail(list head, int data)
{
//新节点申请空间
list new = malloc(sizeof(list_node));
if (NULL == new)
{
printf("new_node malloc fail!\n");
return;
}
new->data = data;
new ->next=head;
list p=head->prev;
p->next=new;
new->prev=p;
head->prev = new;
}
void delete_node(list head, int data)
{
list tmp = head->next;
while (tmp != head)
{
if (tmp->data == data)
{
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
free(tmp);
return ;
}
tmp = tmp->next;
}
}
void delete_list(list head)
{
struct list_node *p=NULL;
struct list_node *q=NULL;
p=head->prev;
p->next=NULL;
for(q=p=head;p!=NULL;p=q)
{
q=p->next;
free(p);
}
}
/*遍历数据*/
void show_list(list head)
{
list p = head->next;
while (p != head)
{
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
/*反向遍历*/
void show_list2(list head)
{
list p = head->prev;
for(;p!=head;p=p->prev)
{
printf("%d\t", p->data);
}
printf("\n");
}
int main()
{
list head = init_list();
insert_data_to_list_head(head,30);
insert_data_to_list_head(head,20);
insert_data_to_list_head(head,10);
show_list(head);
delete_node(head, 20);
show_list(head);
insert_data_to_list_head(head, 5);
insert_data_to_list_head(head, 15);
delete_node(head, 30);
show_list(head);
delete_list(head);
return 0;
}
运行结果
?