目录
编辑
1.2链表
1.2.1 链表的特性
1.2.2 单向链表
遍历无头单向链表
遍历有头单向链表
链表尾插法练习
1.2.3 单向链表的函数操作
单向链表的特点：
1.2链表
链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
和顺序表不同同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。
例如存数据1 2 3
需要通过指针链接
所以在链表中，每个数据元素可以配有一个指针用于找到下一个元素即节点，这意味着，链表上的每个“元素”都长下图这个样子：
1.2.1 链表的特性
逻辑结构：线性结构
存储结构：链式存储
特点：内存不连续，大小不固定，通过指针链接。可以解决顺序表的长度固定的问题，以及插入删除麻烦的问题。
操作：增删改查
struct node
{int data; //数据域：存放数据struct node *next; //指针域：存放下一个节点的地址
}1.2.2 单向链表
有头链表：存在一个头节点，头节点数据域无效，指针域有效。
无头链表：每一个数据域和指针域都有效
遍历无头单向链表
#include <stdio.h>
#include <stdlib.h>typedef char datatype;
typedef struct node
{datatype data; //数据域：用来存放数据struct node *next; //指针域：用来存放下一个节点的地址
} link_node_t, *link_node_p;int main(int argc, char const *argv[])
{//1. 定义4个节点link_node_t A = {'a', NULL};link_node_t B = {'b', NULL};link_node_t C = {'c', NULL};link_node_t D = {'d', NULL};//2. 将4个节点连接起来A.next = &B;B.next = &C;C.next = &D;//3. 定义一个头指针，指向第一个节点，用于遍历链表。link_node_p p = &A;//4. 遍历无头单向链表while (p != NULL){printf("%c ", p->data); //打印节点中的数据p = p->next; //让p指向下一个节点}printf("\n");return 0;
}遍历有头单向链表
#include <stdio.h>
#include <stdlib.h>typedef char datatype;
typedef struct node
{datatype data; //数据域：用来存放数据struct node *next; //指针域：用来存放下一个节点的地址
} link_node_t, *link_node_p;int main(int argc, char const *argv[])
{//1. 定义4个节点link_node_t A = {'a', NULL};link_node_t B = {'b', NULL};link_node_t C = {'c', NULL};link_node_t D = {'d', NULL};//2. 将4个节点连接起来A.next = &B;B.next = &C;C.next = &D;//3. 定义一个头节点，数据域无效，指针域要赋值为第一个有效节点的地址。link_node_t H = {'\0', &A};//4. 定义一个头指针，指向头节点，用于遍历链表。link_node_p p = &H;//5. 遍历有头链表#if 0 //条件编译，相当于代码的开关，条件为真就编译以下代码//方法一：p = p->next; //先跨越头节点，指向有效的第一个节点while (p != NULL) //相当于遍历无头链表{printf("%c ", p->data);p = p->next;}printf("\n");#else//方法二while (p->next!=NULL){p=p->next;printf("%c ",p->data);}printf("\n");#endifreturn 0;
}链表尾插法练习
写一个有头单向链表，用于保存输入的学生成绩，实现一输入学生成绩就创建一个新的节点，将成绩保存起来。再将该节点链接到链表的尾，直到输入-1结束。
要求：每个链表的节点由动态内存分配得到 , 也就是用malloc。
过程：
1. malloc申请空间link_node_t大小作为头节点
2. 将新节点放到链表尾部
#include <stdio.h>
#include <stdlib.h>typedef struct node
{int score;struct node *next;
} link_node_t, *link_node_p;int main(int argc, char const *argv[])
{link_node_p pnew=NULL; //用于指向新节点link_node_p ptail=NULL; //用于指向尾节点int score = -1;//1. 定义一个头节点，定义一个头指针指向头节点link_node_p h = (link_node_p)malloc(sizeof(link_node_t));if(NULL==h){perror("h malloc err");return -1;}h->next=NULL; //初始化头节点ptail=h; //尾指针一开始指向头节点，因为只有一个头节点此时//2. 循环输入学生成绩，新建节点存入并且链接到链表中，直到-1结束while (1){scanf("%d", &score);if (score == -1)break;//（1）创建一个新节点用来保存学生成绩pnew=(link_node_p)malloc(sizeof(link_node_t));if(NULL==pnew){perror("pnew malloc err");return -1;}//（2）对新节点的数据域和指针域赋值pnew->score=score;pnew->next=NULL;//（3）将新节点链接到链表尾部ptail->next=pnew;//（4）移动尾指针到新节点，因为有了新尾巴ptail=pnew;}//3. 遍历有头链表while (h->next!=NULL){h=h->next;printf("%d ",h->score);}return 0;
}1.2.3 单向链表的函数操作
创空：
插入：
按位置删除：
按数据删除：
#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node
{datatype data; //数据域：用来存放数据struct node *next; //指针域：用来存放下一个节点的地址
} link_node_t, *link_node_p;//创建一个空的有头单项链表
link_node_p createEmptyLinkList()
{//创建头节点link_node_p h = (link_node_p)malloc(sizeof(link_node_t));if (NULL == h){perror("h malloc err");return NULL;}h->next = NULL;return h;
}//计算链表的长度。
int lengthLinkList(link_node_p p)
{int len = 0;while (p->next != NULL){len++;p = p->next;}return len;
}//向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int insertIntoPostLinkList(link_node_p p, int post, datatype data)
{int i;link_node_p pnew;//1. 容错判断if (post < 0 || post > lengthLinkList(p)){printf("insertIntoPostLinkList err\n");return -1;}//2. 让指针移动到插入位置的前一个节点for (i = 0; i < post; i++)p = p->next;//3. 开辟一个新节点pnew = (link_node_p)malloc(sizeof(link_node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}//4. 初始化新节点pnew->data = data;pnew->next = NULL;//5. 链接：先连后面，再连前面pnew->next = p->next;p->next = pnew;return 0;
}//遍历单向链表
void showLinkList(link_node_p p)
{while (p->next != NULL){p = p->next;printf("%d ", p->data);}printf("\n");
}// 删除单向链表中指定位置的数据 post 代表的是删除的位置
int deletePostLinkList(link_node_p p, int post)
{link_node_p pdel = NULL;int i;//1. 容错判断if (post < 0 || post >= lengthLinkList(p)){printf("deletePostLinkList err\n");return -1;}//2. 移动p到删除节点的前一个节点for (i = 0; i < post; i++)p = p->next;//3. 定义指针pdel记录要删除节点，也就是记录p所指节点的的下一个节点pdel = p->next;//4. 跨过被删除节点，也就是p的next要指向pdel的nextp->next = pdel->next;//5. 释放被删除节点free(pdel);pdel = NULL;return 0;
}//判空
int isEmptyLinkList(link_node_p p)
{return p->next == NULL;
}//清空
// 思想：
// 循环进行删除，每次删除的头节点的下一个节点：
// (1)定义一个pdel,指向被删除节点
// (2)跨过被删除节点
// (3)释放被删除节点
void clearLinkList(link_node_p p)
{link_node_p pdel = NULL;while (p->next != NULL){pdel = p->next; //每次删除的都是头节点的后一个p->next = pdel->next;free(pdel);pdel = NULL;}
}//查找指定数据出现的位置 data被查找的数据 //search 查找
int searchDataLinkList(link_node_p p, datatype data)
{int post = 0; //记录查找的位置//遍历有头链表while (p->next != NULL){p = p->next;if (p->data == data)return post;post++;}return -1;
}//修改链表中指定的数据
int changePostLinkList(link_node_p p, int post, datatype data)
{//1. 容错判断if (post < 0 || post >= lengthLinkList(p)){perror("changePostLinkList err");return -1;}//2. 将指针移动到要修改的节点for (int i = 0; i <= post; i++)p = p->next;//3.修改数据p->data = data;return 0;
}//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int deleteDataLinkList(link_node_p p, datatype data)
{link_node_p pdel = NULL; //用于指向删除的节点//1. 定义一个指针q指向头的后一个，用于遍历遍历链表。相当于遍历无头链表。link_node_p q = p->next;//2. 用q去遍历无头链表，将每个节点的数据域和data比较，判断成功就删除节点，不成功p和q都向后走while (q != NULL){if (q->data == data) //相等{//删除操作//（1）将pdel指向被删除节点pdel = q;//（2）跨过被删除节点p->next = pdel->next;//（3）释放被删除节点free(pdel);//（4）让q向后移动继续遍历链表q = p->next;}else //不相等{//q和p都向后走一个单位p = p->next;q = p->next;}}
}//链表倒置（转置）
// 解题思想：
// 1)将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表。
// 2)遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)。
void reverseLinkList(link_node_p p)
{link_node_p temp = NULL; //用来临时保存q的下一个节点，防止头插以后老链表找不到。//1.定义一个q保存头节点的下一个节点，用于遍历一个无头链表。link_node_p q = p->next;//2. 将头节点和老链表断开，需要用头插法做一个新的转置以后的链表p->next = NULL;//3.用q遍历无头链表while (q != NULL){//头插//（1）头插之前用temp保存q的下一节点，以免插入以后老链表找不到temp = q->next;//（2）头插：先连后面，再连前面q->next = p->next;p->next = q;//（3）q移动到temp处，继续找下一个节点来插入。q = temp;}
}int main(int argc, char const *argv[])
{link_node_p p = createEmptyLinkList();insertIntoPostLinkList(p, 0, 1);insertIntoPostLinkList(p, 1, 2);insertIntoPostLinkList(p, 2, 3);insertIntoPostLinkList(p, 3, 100);insertIntoPostLinkList(p, 4, 100);insertIntoPostLinkList(p, 5, 100);reverseLinkList(p);showLinkList(p);deletePostLinkList(p, 0);showLinkList(p);changePostLinkList(p, 4, 1000);showLinkList(p);// clearLinkList(p);// printf("is empty? %d\n", isEmptyLinkList(p));deleteDataLinkList(p, 100);showLinkList(p);return 0;
}单向链表的特点：
- 链表内存空间不连续
- 大小不固定
- 查和改麻烦，增和删简单
