一、数据结构
1、什么是数据结构？
数据结构：计算机存储，组织数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
简单来说：程序 = 数据结构 + 算法
2、逻辑结构和物理结构
1）逻辑结构：研究数据结构之间的逻辑关系
①线性结构
②非线性结构
树状结构、集合结构、图状结构
2）物理结构：数据在物理内存上的存储形式（连续、非连续）
好了概念就介绍到这里，下面我们进入今天的正文——链表的学习
二、链表——线性结构
1、首先介绍下链表和数组的区别
1）数组：
- 数组空间是连续的，每个元素存储的类型都是一样的。
- 通过数组名+下标访问数组成员。
- 数组大小固定，在定义之后不允许重新改变数组大小，对数组的增加元素减少元素比较麻烦，效率低。
2）链表：
- 链表存储空间不连续
- 没有固定的大小，添加节点和删除节点非常方便
- 链表的大小不固定，是通过一系列的节点组成，链表节点就是链表用来存放数据的结构，本质是一个结构体。
- 链表的前后成员是通过指针来寻找的,所以想要删除一个链表成员 只要找到它,free掉其空间,前后链式关系上,可以让删除节点前后成员直接连接
- 增加成员,除了在堆空间malloc外,在链表成员前后关系,只要处理好成员间的链接关系 即可在链表任意位置上添加新成员-----灵活
- 成员的访问因为是通过指针寻找再访问的，访问速度会很慢（相对于数组来说）
2、链表的结构示意图
2、链表节点——节点本身是一个结构体
节点结构体分为两个区域：
数据域：存放数据
指针域：存放指向下一个成员或上一个成员的地址
例子：
记录图书馆的所有图书信息
typedef struct book { //数据域 char bookname[64];//书名 char Author[32];//作者 float price;//价格 //指针域 struct book *next;//指向下个和当前类型一致的成员 }BOOK,*pBOOK;
3、单向链表的一般性结构
4、单向链表节点的添加——插入节点
头插法：新的节点插入到头节点的下一个
尾插法：新的节点插入到最后一个节点的下一个
5、单向链表节点的查找——查找结点
6、单向链表删除节点
步骤：
1）遍历链表，找到需要被删除的节点p以及他的前一个节点q
2）从逻辑上删除节点p：q->next = p->next
3）从物理上删除节点p：free§
7、单向链表节点的销毁
遍历链表，销毁每一个节点
步骤：
1）使用两个指针对链表进行遍历：p（销毁节点）、q（记录p的下一个节点的地址）
2）释放节点空间free（p）
Node *p, *q; p = head; q = p->next; while(q != NULL) //释放head后面所有节点 { p = q; q = q->next; free(p); } free(head); //最后释放头节点
8、最后附上示例代码
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //0,设计链表节点 typedef struct node{ int data; //数据域 struct node *next; //指针域 }Node; //Node 等价于 struct node //1,创建链表 -->创建一个链表头 Node *List_Create(void) { //1）对链表头结点空间申请 --> malloc Node *list = (Node *)malloc(sizeof(Node)); if ( list == NULL ) { perror("malloc failed "); //打印出错信息 return NULL; //结束函数 } //2）对链表头结点进行赋值 list->next = NULL; //3）返回链表头结点地址 return list; } //2,链表节点插入 （头插法） bool List_Add_Node_Head(Node *head, int data) { //1）给新节点申请堆内存 Node *newnode = (Node *)malloc(sizeof(Node)); if (newnode == NULL) { perror("newnode malloc failed"); return false; } //2）新节点赋值 newnode->data = data; newnode->next = NULL; //3）头插法插入链表 newnode->next = head->next; head->next = newnode; return true; } //尾插法 bool List_Add_Node_End(Node *head, int data) { //1）给新节点申请堆内存 Node *newnode = (Node *)malloc(sizeof(Node)); if ( newnode == NULL) { perror("malloc newnode failed"); return false; } //2）给新节点赋值 newnode->data = data; newnode->next = NULL; //3）尾插法插入链表 //找到链表的最后一个节点 p (while(p->next !=NULL)p=p->next) Node *p = head; while(p->next != NULL) //当这个循环结束时，p节点就是最后一个节点 { p = p->next; } //新节点插入到p节点的后面 p->next = newnode; return true; } //3,链表数据输出 void List_Display(Node *head) { //1）定义一个指针用来遍历链表 Node *p = head->next; //头结点不存放数据 printf("链表数据："); //2）遍历链表，输出链表中的每一个节点的数据 while(p != NULL) { printf("%d ", p->data); p = p->next; //把p节点下一个节点的地址赋值给p } printf("\n"); } //4，链表节点查找 int List_Search(Node *head, int data) { int i = 1; Node *p = head->next; //遍历链表指针 while(p != NULL) { if(p->data == data) //找到这个节点 { printf("Find Node[%d]!\n", i); //return i; //返回序号值 } p = p->next; i++; } //printf("No such Node!\n"); return 0; } //5,链表节点删除 ==>删除节点时只能删除一个节点,思考：如何同时删除多个节点？ bool List_Remove(Node *head, int data) { int i = 1; //1）找到需要被删除的节点p和p的前一个节点q Node *p = head->next; Node *q = head; //q是p的前一个节点 while(p != NULL) { if(p->data == data)//2）找到之后，删除节点p { q->next = p->next; //从逻辑上删除p节点 free(p); printf("删除节点[%d]成功！\n", i); return true; } q = q->next; //遍历链表 p = q->next; i++; } //3）如果遍历完链表都没有找到，那就说明链表中没有这个节点 printf("链表中没有这个节点！\n"); return false; } //6,删除链表中所有节点数据 data的节点 bool List_Remove_All(Node *head, int data) { int i = 1; //1）找到需要被删除的节点p和p的前一个节点q Node *p = head->next; Node *q = head; //q是p的前一个节点 while(p != NULL) { if(p->data == data)//2）找到之后，删除节点p { q->next = p->next; //从逻辑上删除p节点 free(p); printf("删除节点[%d]成功！\n", i); i++; p = q->next; continue; //return true; } q = q->next; //遍历链表 p = q->next; i++; } //3）如果遍历完链表都没有找到，那就说明链表中没有这个节点 //printf("链表中没有这个节点！\n"); return false; } //7,链表销毁 void List_Destroy(Node *head) { int i = 0; Node *p = head; Node *q = p->next; while(q != NULL) //释放头结点后面的所有节点 { p = q; q = q->next; free(p); i++; } free(head); //最后释放头结点 printf("成功释放[%d]个节点\n", i); }
