线性表1.1.链表链表又称单链表、链式存储结构用于存储逻辑关系为“一对一”的数据。和顺序表不同使用链表存储数据不强制要求数据在内存中集中存储各个元素可以分散存储在内存中。所以在链表中每个数据元素可以配有一个指针用于找到下一个元素即节点这意味着链表上每个“元素”都长下图这个样子1.1.1.链表的特性逻辑结构线性结构存储结构链式存储特点内存不连续通过指针来链接解决问题长度固定和插入删除麻烦问题操作增删改查struct node_t { int data; // 数据域 struct node_t *next; // 指针域指向下一个节点存放的是下一个节点的地址 };1.1.2.单向链表1有单向链表存在头节点头节点数据域无效指针域有效2无头单向链表每一个节点都有数据域和指针域都有效遍历无头单向链表#include stdio.h typedef struct node_t { int data; // 数据域存放节点数据 struct node_t *next; // 指针域保存下一个节点的地址 } link_node_t, *link_list_t; int main(int argc, char const *argv[]) { // 1. 定义三个节点 link_node_t A {10, NULL}; link_node_t B {20, NULL}; link_node_t C {30, NULL}; // 2. 将节点链接起来 A.next B; B.next C; // 3. 定义一个指针指向第一个节点用于遍历链表 link_list_t p A; // 4. 遍历无头链表 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); return 0; }遍历有头单项链表#include stdio.h typedef struct node_t { int data; // 数据域存放节点数据 struct node_t *next; // 指针域保存下一个节点的地址 } link_node_t, *link_list_t; int main(int argc, char const *argv[]) { // 1. 定义三个节点 link_node_t A {10, NULL}; link_node_t B {20, NULL}; link_node_t C {30, NULL}; // 2. 将节点链接起来 A.next B; B.next C; // 3. 定义一个头节点数据域无效指针域指向第一个节点 link_node_t h {\0, A}; // 4. 定义一个指针指向头节点 link_list_t p h; // . 遍历有头链表 #if 1 // 方法一 while (p-next ! NULL) { p p-next; printf(%d , p-data); } printf(\n); #else // 方法二 p p-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); #endif return 0; }有头单向链表的函数操作linklist.h#ifndef __LINKLIST_H__ #define __LINKLIST_H__ typedef int datatype; typedef struct node_t { datatype data;//数据域 struct node_t *next;//指针域,指向自身结构体的指针 }link_node_t,*link_list_t; //1.创建一个空的有头单向链表 link_node_t *createEmptyLinkList(); //2.链表指定位置插入数据 int insertIntoPostLinkList(link_node_t *p,int post, datatype data); //3.计算链表的长度。 int lengthLinkList(link_node_t *p); //4.遍历链表 void showLinkList(link_node_t *p); //5.判断链表是否为空 int isEmptyLinkList(link_node_t *p); //6.链表指定位置删除数据 int deletePostLinkList(link_node_t *p, int post); //7.清空单向链表 void clearLinkList(link_node_t *p); //8.修改指定位置的数据 post 被修改的位置 data修改成的数据 int changePostLinkList(link_node_t *p, int post, datatype data); //9.查找指定数据出现的位置 data被查找的数据 //search 查找 int searchDataLinkList(link_node_t *p, datatype data); //10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除 int deleteDataLinkList(link_node_t *p, datatype data); //11.转置链表 //解题思想 //(1) 将头节点与当前链表断开断开前保存下头节点的下一个节点保证后面链表能找得到定义一个q保存头节点的下一个节点断开后前面相当于一个空的链表后面是一个无头的单向链表 //(2) 遍历无头链表的所有节点将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置) void reverseLinkList(link_node_t *p); #endif1创建一个空的有头单项链表只有一个头节点指针域赋值为NULL//1.创建一个空的有头单向链表 link_node_t *createEmptyLinkList() { link_list_t h (link_list_t)malloc(sizeof(link_node_t)); if(NULL h) { printf(createEmptyLinkList err\n); return NULL; } h-next NULL; return h; }2链表指定位置插入数据// 2.链表指定位置插入数据 int insertIntoPostLinkList(link_node_t *p, int post, datatype data) { link_list_t pnew NULL; // 1. 容错判断 if (post 0 || post lengthLinkList(p)) { printf(insertIntoPostLinkList err\n); return -1; } // 2. 创建新节点, 并初始化 pnew (link_list_t)malloc(sizeof(link_node_t)); if (NULL pnew) { printf(pnew err\n); return -1; } pnew-data data; pnew-next NULL; // 3. 将头指针移动指向插入位置前一个节点 for (int i 0; i post; i) p p-next; // 4. 将新节点插入到链表中先连后面在连前面 pnew-next p-next; p-next pnew; return 0; }3计算链表的长度// 3.计算链表的长度。 int lengthLinkList(link_node_t *p) { int len 0; while (p-next ! NULL) { p p-next; len; } return len; }4遍历链表//4.遍历链表 void showLinkList(link_node_t *p) { while(p-next ! NULL) { p p-next; printf(%d , p-data); } printf(\n); }5判断链表是否为空//5.判断链表是否为空 int isEmptyLinkList(link_node_t *p) { return p-next NULL; }6链表指定位置删除数据//6.链表指定位置删除数据 int deletePostLinkList(link_node_t *p, int post) { link_list_t pdel NULL; // 1. 容错判断 if(isEmptyLinkList(p) || post 0 || post lengthLinkList(p)) { printf(deletePostLinkList err\n); return -1; } // 2. 将头指针移动指向被删除位置的前一个节点 for(int i 0; i post; i) p p-next; // 3. 删除操作 // 1) 定义一个pdel指向被删除的节点 pdel p-next; // 2) 跨过被删除的节点 p-next pdel-next; // 3) 释放被删除的节点 free(pdel); pdel NULL; return 0; }7清空单向链表思想循环进行删除每次删除头节点的下一个节点:(1)定义一个pdel指针指向被删除节点(2)跨过被删除节点(3)释放被删除节点// 7.清空单向链表 void clearLinkList(link_node_t *p) { link_list_t pdel NULL; while (p-next ! NULL) { // 1. 定义一个pdel指向被删除的节点 pdel p-next; // 2. 跨过被删除的节点 p-next pdel-next; // 3. 释放被删除的节点 free(pdel); pdel NULL; } }8修改指定位置的数据// 8.修改指定位置的数据 post 被修改的位置 data修改成的数据 int changePostLinkList(link_node_t *p, int post, datatype data) { // 1. 容错判断 if (isEmptyLinkList(p) || post 0 || post lengthLinkList(p)) { printf(changePostLinkList err\n); return -1; } // 2. 将头指针移动到要修改的节点位置 for(int i 0; i post; i) p p-next; // 3. 修改数据 p-data data; return 0; }9查找指定数据在链表的位置//9.查找指定数据出现的位置 data被查找的数据 //search 查找 int searchDataLinkList(link_node_t *p, datatype data) { int post 0; // 记录找到的位置 while(p-next ! NULL) { p p-next; if(p-data data) { return post; } post; } return -1; }10删除单项链表中出现的指定数据思想p始终指向被删除节点的前一个让q相当于遍历无头结点pdel用于指向删除节点。// 10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除 int deleteDataLinkList(link_node_t *p, datatype data) { link_list_t pdel NULL; // 1. 定义一个指针q指向头节点的下一个节点 link_list_t q p-next; // 2. 用q来遍历无头链表将每一个节点与data做比较 while (q ! NULL) { if (q-data data) { // 1) 将pdel指向被删除的节点 pdel q; // 2) 将q指向删除节点的下一个节点 q pdel-next; // 3) 跨过被删除的节点 p-next pdel-next; // 4) 释放被删除的节点 free(pdel); pdel NULL; } else { // 不是指定的数据将p和q向后移动一个位置 q q-next; p p-next; } } return 0; }11转置链表解题思想(1) 将头节点与当前链表断开断开前保存下头节点的下一个节点保证后面链表能找得到定义一个q保存头节点的下一个节点断开后前面相当于一个空的链表后面是一个无头的单向链表(2) 遍历无头链表的所有节点将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)// 反转有头单向链表 (p 指向头节点) void reverseLinkList(link_node_t *p) { // 1. 判空保护如果链表为空直接返回 if (p NULL || p-next NULL) { return; } // 2. 断开链表q 指向第一个有效节点头节点 p 变成空链表 link_list_t q p-next; // q 用来遍历旧链表 p-next NULL; // 头节点与后面断开此时 p 是空链表的头 // 3. 遍历旧链表逐个头插到新链表即 p 后面 link_list_t r NULL; // r 用来保存当前要插入的节点 while (q ! NULL) { r q; // ① 取出当前旧链表的第一个节点 q q-next; // ② 指针后移**关键必须先移否则等会丢失旧链表** r-next p-next; // ③ 头插新节点的 next 指向当前新链表的第一个节点 p-next r; // ④ 头节点指向新插入的节点 } }
线性表1.1.链表链表又称单链表、链式存储结构用于存储逻辑关系为“一对一”的数据。和顺序表不同使用链表存储数据不强制要求数据在内存中集中存储各个元素可以分散存储在内存中。所以在链表中每个数据元素可以配有一个指针用于找到下一个元素即节点这意味着链表上每个“元素”都长下图这个样子1.1.1.链表的特性逻辑结构线性结构存储结构链式存储特点内存不连续通过指针来链接解决问题长度固定和插入删除麻烦问题操作增删改查struct node_t { int data; // 数据域 struct node_t *next; // 指针域指向下一个节点存放的是下一个节点的地址 };1.1.2.单向链表1有单向链表存在头节点头节点数据域无效指针域有效2无头单向链表每一个节点都有数据域和指针域都有效遍历无头单向链表#include stdio.h typedef struct node_t { int data; // 数据域存放节点数据 struct node_t *next; // 指针域保存下一个节点的地址 } link_node_t, *link_list_t; int main(int argc, char const *argv[]) { // 1. 定义三个节点 link_node_t A {10, NULL}; link_node_t B {20, NULL}; link_node_t C {30, NULL}; // 2. 将节点链接起来 A.next B; B.next C; // 3. 定义一个指针指向第一个节点用于遍历链表 link_list_t p A; // 4. 遍历无头链表 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); return 0; }遍历有头单项链表#include stdio.h typedef struct node_t { int data; // 数据域存放节点数据 struct node_t *next; // 指针域保存下一个节点的地址 } link_node_t, *link_list_t; int main(int argc, char const *argv[]) { // 1. 定义三个节点 link_node_t A {10, NULL}; link_node_t B {20, NULL}; link_node_t C {30, NULL}; // 2. 将节点链接起来 A.next B; B.next C; // 3. 定义一个头节点数据域无效指针域指向第一个节点 link_node_t h {\0, A}; // 4. 定义一个指针指向头节点 link_list_t p h; // . 遍历有头链表 #if 1 // 方法一 while (p-next ! NULL) { p p-next; printf(%d , p-data); } printf(\n); #else // 方法二 p p-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); #endif return 0; }有头单向链表的函数操作linklist.h#ifndef __LINKLIST_H__ #define __LINKLIST_H__ typedef int datatype; typedef struct node_t { datatype data;//数据域 struct node_t *next;//指针域,指向自身结构体的指针 }link_node_t,*link_list_t; //1.创建一个空的有头单向链表 link_node_t *createEmptyLinkList(); //2.链表指定位置插入数据 int insertIntoPostLinkList(link_node_t *p,int post, datatype data); //3.计算链表的长度。 int lengthLinkList(link_node_t *p); //4.遍历链表 void showLinkList(link_node_t *p); //5.判断链表是否为空 int isEmptyLinkList(link_node_t *p); //6.链表指定位置删除数据 int deletePostLinkList(link_node_t *p, int post); //7.清空单向链表 void clearLinkList(link_node_t *p); //8.修改指定位置的数据 post 被修改的位置 data修改成的数据 int changePostLinkList(link_node_t *p, int post, datatype data); //9.查找指定数据出现的位置 data被查找的数据 //search 查找 int searchDataLinkList(link_node_t *p, datatype data); //10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除 int deleteDataLinkList(link_node_t *p, datatype data); //11.转置链表 //解题思想 //(1) 将头节点与当前链表断开断开前保存下头节点的下一个节点保证后面链表能找得到定义一个q保存头节点的下一个节点断开后前面相当于一个空的链表后面是一个无头的单向链表 //(2) 遍历无头链表的所有节点将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置) void reverseLinkList(link_node_t *p); #endif1创建一个空的有头单项链表只有一个头节点指针域赋值为NULL//1.创建一个空的有头单向链表 link_node_t *createEmptyLinkList() { link_list_t h (link_list_t)malloc(sizeof(link_node_t)); if(NULL h) { printf(createEmptyLinkList err\n); return NULL; } h-next NULL; return h; }2链表指定位置插入数据// 2.链表指定位置插入数据 int insertIntoPostLinkList(link_node_t *p, int post, datatype data) { link_list_t pnew NULL; // 1. 容错判断 if (post 0 || post lengthLinkList(p)) { printf(insertIntoPostLinkList err\n); return -1; } // 2. 创建新节点, 并初始化 pnew (link_list_t)malloc(sizeof(link_node_t)); if (NULL pnew) { printf(pnew err\n); return -1; } pnew-data data; pnew-next NULL; // 3. 将头指针移动指向插入位置前一个节点 for (int i 0; i post; i) p p-next; // 4. 将新节点插入到链表中先连后面在连前面 pnew-next p-next; p-next pnew; return 0; }3计算链表的长度// 3.计算链表的长度。 int lengthLinkList(link_node_t *p) { int len 0; while (p-next ! NULL) { p p-next; len; } return len; }4遍历链表//4.遍历链表 void showLinkList(link_node_t *p) { while(p-next ! NULL) { p p-next; printf(%d , p-data); } printf(\n); }5判断链表是否为空//5.判断链表是否为空 int isEmptyLinkList(link_node_t *p) { return p-next NULL; }6链表指定位置删除数据//6.链表指定位置删除数据 int deletePostLinkList(link_node_t *p, int post) { link_list_t pdel NULL; // 1. 容错判断 if(isEmptyLinkList(p) || post 0 || post lengthLinkList(p)) { printf(deletePostLinkList err\n); return -1; } // 2. 将头指针移动指向被删除位置的前一个节点 for(int i 0; i post; i) p p-next; // 3. 删除操作 // 1) 定义一个pdel指向被删除的节点 pdel p-next; // 2) 跨过被删除的节点 p-next pdel-next; // 3) 释放被删除的节点 free(pdel); pdel NULL; return 0; }7清空单向链表思想循环进行删除每次删除头节点的下一个节点:(1)定义一个pdel指针指向被删除节点(2)跨过被删除节点(3)释放被删除节点// 7.清空单向链表 void clearLinkList(link_node_t *p) { link_list_t pdel NULL; while (p-next ! NULL) { // 1. 定义一个pdel指向被删除的节点 pdel p-next; // 2. 跨过被删除的节点 p-next pdel-next; // 3. 释放被删除的节点 free(pdel); pdel NULL; } }8修改指定位置的数据// 8.修改指定位置的数据 post 被修改的位置 data修改成的数据 int changePostLinkList(link_node_t *p, int post, datatype data) { // 1. 容错判断 if (isEmptyLinkList(p) || post 0 || post lengthLinkList(p)) { printf(changePostLinkList err\n); return -1; } // 2. 将头指针移动到要修改的节点位置 for(int i 0; i post; i) p p-next; // 3. 修改数据 p-data data; return 0; }9查找指定数据在链表的位置//9.查找指定数据出现的位置 data被查找的数据 //search 查找 int searchDataLinkList(link_node_t *p, datatype data) { int post 0; // 记录找到的位置 while(p-next ! NULL) { p p-next; if(p-data data) { return post; } post; } return -1; }10删除单项链表中出现的指定数据思想p始终指向被删除节点的前一个让q相当于遍历无头结点pdel用于指向删除节点。// 10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除 int deleteDataLinkList(link_node_t *p, datatype data) { link_list_t pdel NULL; // 1. 定义一个指针q指向头节点的下一个节点 link_list_t q p-next; // 2. 用q来遍历无头链表将每一个节点与data做比较 while (q ! NULL) { if (q-data data) { // 1) 将pdel指向被删除的节点 pdel q; // 2) 将q指向删除节点的下一个节点 q pdel-next; // 3) 跨过被删除的节点 p-next pdel-next; // 4) 释放被删除的节点 free(pdel); pdel NULL; } else { // 不是指定的数据将p和q向后移动一个位置 q q-next; p p-next; } } return 0; }11转置链表解题思想(1) 将头节点与当前链表断开断开前保存下头节点的下一个节点保证后面链表能找得到定义一个q保存头节点的下一个节点断开后前面相当于一个空的链表后面是一个无头的单向链表(2) 遍历无头链表的所有节点将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)// 反转有头单向链表 (p 指向头节点) void reverseLinkList(link_node_t *p) { // 1. 判空保护如果链表为空直接返回 if (p NULL || p-next NULL) { return; } // 2. 断开链表q 指向第一个有效节点头节点 p 变成空链表 link_list_t q p-next; // q 用来遍历旧链表 p-next NULL; // 头节点与后面断开此时 p 是空链表的头 // 3. 遍历旧链表逐个头插到新链表即 p 后面 link_list_t r NULL; // r 用来保存当前要插入的节点 while (q ! NULL) { r q; // ① 取出当前旧链表的第一个节点 q q-next; // ② 指针后移**关键必须先移否则等会丢失旧链表** r-next p-next; // ③ 头插新节点的 next 指向当前新链表的第一个节点 p-next r; // ④ 头节点指向新插入的节点 } }
