数据结构02-链表(单/双/向普通及循环链表)
链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一个用来指向下一个节点地址的指针(next指针)。
- 数组内存连续，需要预先知道数据大小的缺点；
- 链表结构内存不需要连续，可以充分利用计算机内存空间，实现灵活的内存动态管理。但失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大
链表在插入的时候可以达到O⑴的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。
1：单向链表
单向链表：指存放链表的结点中只有一个指针，指向它的下一个结点，而链表中最后一个结点的next指针为NULL。
头结点：链表中的第一个结点。只要知道了链表的头结点，就可以通过next指针，遍历整个链表。因此，一般在函数中，我们使用头结点来代表整个链表，将头结点传参给函数。
单向链表的存储结构：
typedef struct _node {
int val;//值域，可以增加更多的值域，这里仅以int类型为代表
struct _node *next;//指针域，指向下一个结点，最后一个结点指向NULL
} Node, *PNode;
单链表.png
1.1：创建
在创建链表过程中，将新分配的一个链表结点插入到已知的链表中，可以分为两种情况：从头部插入和从尾部插入。
image.png
1.1.1：头部插入创建
分析：
image.png
//从头部插入创建链表算法
node *create_linklist_head() {
node *h = NULL;
while(1) {
node *p = (node*)malloc(sizeof(node));
if(p==NULL) {
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&(p->val));
p->next = NULL;
if(h==NULL) {//头结点指针为空，创建第一个结点
h=p;
} else {
p->next = h;
h=p;
}
if(p->value==0) {
break;
}
}
return h;
}
1.1.2：尾部插入创建
分析：
image.png
//从尾部插入链表算法
node *create_linklist_tail() {
node *h=NULL;
while(1) {
node *p = (node *)malloc(sizeof(node));
if(p==NULL) {
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&p->value);
p->next = NULL;
if(h==NULL) { //头结点指针为空，创建第一个结点
h=p;
} else {
node *q = h;//需要从头部遍历到尾部
while(q->next) {
q=q->next;
}
q->next = p;//q为尾部，q->next=p，将新建结点设置为尾部
p->next = NULL;
}
if(p->value==0) {//输入为零，则停止创建链表
break;
}
}
return h;
}
1.2：遍历
void traverse_list(node *h) {
node *p = h;
while(p) {
printf("%d ",p->value);
p=p->next;
}
printf("\n");
}
1.3：插入
将链表结点插入到某个指定的结点;
分析：
image.png
//在头结点之前插入某节点
bool insert_linklist_in_head_front(Node **h, int data) {
Node *p = *h;
if (p == NULL) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = p;
*h = node;//改变h的值，需要传h的地址
return true;
}
//在尾结点之后插入某节点
bool insert_linklist_in_tail_behead(Node *h, int data) {
Node *p = h;
if (p == NULL) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = NULL;//node之后要变为尾节点
while (p->next) {
printf("%d ", p->val);
p = p->next;
}
p->next = node;
return true;
}
//index_in_front(从0开始)
bool insert_linklist(Node **h, int index, int data) {//在链表h第index节点插入data
Node *p = *h;
if (!p) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = NULL;//node防止野指针
if (index == 0) {
node->next = p;
*h = node;//改变h的值，需要传h的地址
printf("0位置插入成功\n");
return true;
}
int i = 0;
Node *swap;
while (i < index - 1) {
p = p->next;
++i;
}
swap = p->next;//把下一个节点的地址，给用于交换的swap
p->next = node;//把要插入的节点的地址，给上个节点的指针域
node->next = swap;//把插入节点的下一个节点的地址，给插入节点的指针域
return true;
}
int main(int argc, const char * argv[]) {
printf("头部插入节点创建链表: Please creat_linklist_head\n");
Node *head1 = creat_linklist_head();//
printf("遍历节点head1: Please traverse_list\n");
traverse_list(head1);
//在尾结点之后插入某节点
printf("插入某节点: Please input a data\n");
int k;
scanf("%d", &k);
printf("插入节点的位置index：\n");
int index;
scanf("%d", &index);
bool binsert_linklist = insert_linklist(&head1, index, k);
if (binsert_linklist) {
printf("插入成功遍历节点head1: Please traverse_list\n");
traverse_list(head1);
} else {
printf("插入错误\n");
}
}
1.3：删除
分析：
image.png
void del_list_node(node **h,int value) {
if(h==NULL) {
return;
}
node *p = *h;
node *q = NULL;
while(p) {
if(p->value==value) {
if(p==h) {
//改变指针的值，需要在传参时传二级指针
*h=(*h)->next;
free(p);
p = NULL;
return;
} else {
q->next=p->next;
free(p);
p = NULL;
}
return;
}
q=p;
p = p->next;
}
}
1.5：销毁
void destroy_list(node \*p) {
node \*p =h;
while(p) {
node *q=p;//先用q保存这个待删除的结点
p=p->next;//p指向下一个结点
free(q);//现在可以删除q了
}
}
1.6：单向循环链表
循环链表：最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。
单向循环链表的遍历：判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非循环单链表判断链域值是否为NULL。
单向循环链表的4种不同的形式：
image.png
1.6.1：单向循环链表的创建
Node *create_list_loop() {
Node *h = NULL;
while(1) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) {
return h;
}
memset(node, 0, sizeof(Node));
printf("Please input a data\n");
scanf("%d",&(node->val));
node->next = NULL;
if(h == NULL) {//如果头结点指针为空，表明这是创建的第一个结点
h = node;
node->next = h;//单个节点的循环链表
} else {
Node *q = h;
while(q->next != h) {//q->next如果等于h，那么q就是最后一个结点
q = q->next;
}
q->next = node;
node->next = h;//将p的next指针指向h，构成一个循环
}
if(node->val == 0) {
break;
}
}
return h;
}
1.6.2：单向循环链表的遍历
void traverse_loop_list(node *h) {
if(h==NULL)
return;
node *p = h;
do {
printf("%d ",p->value);
p = p->next;
} while(p != h);
printf("\n");
}
1.6.3：单向循环链表的销毁
void destroy_loop_list(node *h) {
if(h==NULL)
return;
node *p = h->next;//防止头结点销毁,所以从第二个开始
do {
node *q = p;
p = p->next;
free(q);
} while (p != h);
free(h);
}
1.6.4：判断链表是否含有循环
//步长法判断链表是否含有循环
//思路是：定义2个指针遍历该链表，1个指针跑一步，1个指针跑两步；
//那么如果两个指针相遇，则表示有循环，否则无循环。
bool is_a_loop_list(node *h) {
node *p = h;
node *q = h->next;
while(p&&q&&q!=p&&q->next) {
p=p->next;
q=q->next->next;
}
if(p==q) {//循环退出，p和q相等了，表示链表中存在循环
return true;
}
return false;
}
2：双向链表
双向链表：结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
双向链表的存储结构定义如下：
typedef struct _dnode {
int data;
struct _dnode *pre;//前向指针，指向结点左边的结点
struct _dnode *next;//后继指针，指向结点右边的结点
} dnode, *pdnode;
image.png
2.1：创建
创建双向链表，将一个新建的结点p，插入已知的双向链表中，有2种插入方法：
- 直接插入头部
- 直接插入尾部
image.png
//1. 从头部插入方法创建双向链表：
dnode *create_dobulelist_head() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p == NULL) {
return h;
}
memset(p, 0, sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next = p->pre = NULL;
if(h==NULL){ //如果头结点指针为空，表明这是创建的第一个结点
h = p;
} else {
p->next = h;
h->pre = p;
h = p;
}
if(p->value==0) {
break;
}
}
return h;
}
//2. 从尾部插入创建双向链表：
dnode *create_dobulelist_tail() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p==NULL){
return h;
}
memset(p,0,sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next = p->pre = NULL;
if (h==NULL) {//如果头结点指针为空，表明这是创建的第一个结点
h = p;
} else {
dnode *q = h;
while(q->next) {//需要先从头结点开始遍历到尾结点
q=q->next;
}
q->next = p;
p->pre=q;
p->next = NULL;
}
if(p->value==0) {//创建循环退出
break;
}
}
return h;
}
2.2：插入
如图：将一个结点p插入到双向链表q的后面下面演示顺序插入
image.png
dnode *create_sorted_dlist() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p == NULL) {
return h;
}
memset(p, 0, sizeof(p));
printf("Please input your data\n");
scanf_s("%d", &(p->value));
p->next = p->pre = NULL;
if(h==NULL){ //如果头结点指针为空，表明这是创建的第一个结点 h = p;
} else {
dnode *q = h;
dnode *r = NULL;
while(q && q->val<p->val) {
r = q;//用r记录下q的前一个结点
q = q->next
}
//q非空，说明在链表中找到了一个节点，值比p->val大，此时p应插入到q的前面，r的后面
if(q) {//q非空
if (q == h) {
p->next = h;
h->pre = p;
h = p;
} else {
r->next = p;//r->next->pre = p;
p->pre = r;//
p->next = q;//p->next = r->next;
q->pre = p;//r->next->pre = p;
}
} else {//q为空，r为尾节点
r->next = p;
p-pre = r;
}
p->next = h;
h->pre = p;
h = p;
}
if(p->value==0) {
break;
}
if(p->value==0) {//创建循环退出
break;
}
}
return h;
}
2.3：遍历
void traverse_dlist_next(dnode *h) {
dnode *p=h;
while(p) {
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
2.4：销毁
void destroy_dlist(dnode *h) {
dnode *p = h;
while(p) {
dnode *q = p;
p = p->next;
free(q);
}
}
2.5：删除
双向链表中，将一个结点p从双向链表中删除方法：
image.png
int del_dlist_value(dnode **h, int value) {
if (*h == NULL) {
return 0;
}
node *p = *h;
while(p) {
if(p->value == value) {
if(p == *h) {//头结点
*h = (*h)->next;
(*h)->pre = NULL;
} else if (p->next == NULL) {
p->pre->next = NULL;
} else {
p->pre->next = p->next;
p->next->pre = p->pre;
}
free(p);
}
p = p->next;
}
}
2.6：双向循环链表
双向循环链表既是双向链表，又是循环链表。头结点的左链域指向最后一个结点，最后一个结点的右链域指向头结点。
image.png
网友评论