数据结构之链表

储备知识：

线性表 ：一对一的数据所组成的关系称为线性表。

• 线性表是一种数据内部的逻辑关系，与存储形式无关
• 线性表既可以采用连续的顺序存储(数组)，也可以采用离散的链式存储(链表)
• 顺序表和链表都称为线性表

顺序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，或者是匿名的堆数组。

栈空间：char buf[4];自动申请空间，函数结束后自动释放，{}内定义的局部变量，{}过后自动释放，空间大小为8M

堆空间:malloc(16) calloc(4,sizeof(int)) realloc()

手动分配空间，手动释放空间，空间大小为实际物理内存，空间生命周期为整个程序的生命周期

1.优点

• 不需要多余的信息来记录数据的关系，存储密度高
• 所有数据顺序存储在一片连续的内存中，支持立即访问任意一个随机数据

2.缺点

• 插入、删除时需要保持数据的物理位置反映其逻辑关系，需要成片移动数据
• 当数据节点较多时，需要一整片较大的连续内存空间
• 当数据节点数量变化剧烈时，内存的释放和分配不灵活

链表存储可以将数据存储到不连续的内存空间中，可以是单链表或双链表。

单链表

一种常见的数据结构，它由一系列节点组成，每个节点包含了数据部分和指向下一个节点的指针。在单链表中，第一个节点称为头节点，最后一个节点的指针指向空，表示链表的结束。

特点：

• 动态大小：单链表的大小可以根据需要动态增长或缩小。
• 插入和删除操作：在单链表中插入或删除节点通常比较灵活，只需要改变相邻节点的指针即可。
• 不需要连续内存：与数组不同，单链表的节点不需要在内存中连续存储，它们可以分散在内存的任何位置。
• 访问效率：访问单链表中的元素需要从头节点开始，逐个遍历到所需位置，因此访问效率相对较低。

单链表的常见操作包括：

• 插入：在链表的指定位置插入新节点。
• 删除：删除链表中的指定节点。
• 搜索：查找链表中包含特定数据的节点。
• 遍历：从头节点开始，依次访问链表中的每个节点。

创建有头结点单链表

1. 从无到有：第一个节点的诞生，此时的首节点和尾节点都是它本身

2 .从少到多(添加节点过程)：

• 尾插法

新节点插入在选定节点后面；若所选节点为尾节点（last）原指向的节点，则原来的尾节点被新节点替代，成为新的尾节点。

• 头插法

新节点插入在选定节点前面；若所选节点为首节点（last）原指向的节点，则原来的首节点被新节点替代，成为新的首节点。

// 定义数据节点
struct node
{dataType data; // 数据域struct node *next; // 指针域，存放(指向)下一个节点的地址
};// 定义头节点
struct headNode
{struct node *first; // 指向第一个数据节点struct node *last; // 指向最后一个数据节点int nodeNumber; // 记录链表节点数
};//创建头节点
struct headNode* create_new_headNode()
{struct headNode* head =  malloc(sizeof(struct headNode));if(head == NULL)return NULL;head->first = NULL;head->last = NULL;head->nodeNumber = 0;return head;
}// 创建新节点
struct node* create_new_node(dataType data)
{struct node* pnew =  malloc(sizeof(struct node));if(pnew == NULL)return NULL;pnew->data = data;pnew->next = NULL;return pnew;
}// 尾插法
void addTail(struct headNode *head,struct node* pnew)
{head->last->next = pnew;head->last = pnew;
}//创建链表
struct headNode* create_list()
{// 创建头节点struct headNode* head = create_new_headNode();if(head == NULL)return NULL;dataType data = -1;while(1){scanf("%d",&data);if(data == 0)break;// 创建新节点struct node* pnew = create_new_node(data);if(pnew == NULL)return NULL;// 从无到有if(head->first == NULL){head->first = pnew;head->last = pnew;}else // 从少到多{// 尾插法addTail(head,pnew);}// 更新节点head->nodeNumber++;}return head;
}//显示链表
void showList(struct headNode* head)
{if(head->first == NULL){printf("链表为空\n");return;}for(struct node* p = head->first;p != head->last->next;p = p->next){printf("%d\t",p->data);}printf("\n");printf("链表节点数为：%d\n",head->nodeNumber);
}

双链表

是一种链式数据结构，它由一系列节点组成，每个节点除了包含数据外，还包含两个指针：一个指向前一个节点，一个指向后一个节点。这种结构允许双向遍历链表，即可以从头节点开始向前遍历，也可以从尾节点开始向后遍历。

特点：

1. 双向链接：每个节点都有指向前一个和后一个节点的指针，这使得在链表中的移动更加灵活。
2. 动态大小：与单链表一样，双链表的大小可以动态变化。
3. 插入和删除操作：在双链表中，插入和删除操作通常比单链表更加高效，因为可以直接访问前一个或后一个节点，而不需要像单链表那样从头节点开始遍历。
4. 不需要连续内存：节点在内存中不需要连续存储，可以分散在内存的任何位置。

双链表的常见操作包括：

• 插入：可以在链表的任意位置插入新节点，包括在头节点之前或尾节点之后。
• 删除：可以快速删除指定节点，因为可以直接访问前一个和后一个节点来更新指针。
• 搜索：可以从头或尾开始搜索特定数据的节点。
• 遍历：可以正向或反向遍历链表。

创建有头结点双链表

// 创建数据节点
struct node
{dataType data;struct node *prev;// 指向上一个节点struct node *next;// 指向下一个节点
};// 创建头节点
struct headNode
{struct node *first; // 指向首节点struct node *last; // 指向最后一个节点int nodeNumber; // 记录节点数
};// 创建头节点
struct headNode *create_head()
{// 创建头节点struct headNode *head = malloc(sizeof(struct headNode));if(head == NULL){perror("create head failed:");return NULL;}head->first = NULL;head->last = NULL;head->nodeNumber = 0;return head;
}// 创建新节点
struct node *create_new_node(dataType data)
{struct node *pnew = malloc(sizeof(struct node));if(pnew == NULL){perror("create new node failed:");return NULL;}pnew->data = data;pnew->prev = NULL;pnew->next = NULL;
}//增加节点
struct headNode *add_node_list(struct headNode *head,dataType newData,dataType data)
{// 创建新节点struct node *pnew = create_new_node(newData);if(pnew == NULL)return NULL;// 找节点struct node *p = head->first;while(p){if(p->data == data)break;else{p = p->next;}}// 如果找的是第一个节点if(p->data == head->first->data){addHead(pnew,head);}else if(p == NULL){addTail(pnew,head);}else{pnew->next = p;pnew->prev = p;p->prev->next = pnew;pnew->prev = pnew; }head->nodeNumber++;return head;
}//删除节点
struct headNode *del_node(struct headNode *head,dataType data)
{// 找节点struct node *p = head->first;while(p){if(p->data == data)break;elsep = p->next;}// 如果是第一个节点if(head->first->data == data){head->first->next->prev = head->first;head->first = p->next;p->next = NULL;p->prev = NULL;free(p);}else if(p->data == head->last->data){p->prev->next = NULL;p->prev = NULL;free(p);}else if(p == NULL){printf("没有可删除的节点\n");}else{p->next->prev = p->prev;p->prev->next = p->next;p->prev = NULL;p->next = NULL;free(p);}head->nodeNumber--;return head;
}//链表遍历
void showList(struct headNode *head)
{for(struct node *p = head->first;p != head->last->next;p = p->next){printf("%d\t",p->data);}printf("\n");printf("节点数为：%d\n",head->nodeNumber);
}// 销毁链表
struct headNode * distory_list(struct headNode *head)
{if(isEmpty(head))return false;// 逐一删除节点struct node *p = NULL;for(struct node *tmp = head->first;tmp != NULL; tmp = p){p = tmp->next;free(tmp);head->nodeNumber--;}return head;
}

双向循环链表

结构上和双向链表就只差首尾相连。

// 至少还有一个节点时将首尾相连
if(head->nodeNumber != 0)
{head->last->next = head->first;head->first->prev = head->last;
}