【数据结构|【数据结构】【王道】【线性表】无头结点单链表的实现及基本操作（可直接运行）】总目录

文章目录

• 1.基本操作
• • 1.1 结构体定义
  • 1.2 初始化
  • 1.3 判空
  • 1.4 按位序插入
  • 1.5 指定结点后插操作
  • 1.6 指定结点前插操作_1
  • 1.7 指定结点前插操作_2
  • 1.8 按位序删除
  • 1.9 按位查找
  • 1.10 按值查找
  • 1.11 表的长度
  • 1.12 单链表建立（尾插法）
  • 1.13 单链表建立（头插法）
  • 1.14 输出所有链表元素
• 2.完整代码
• 3.运行截图

各部分的解释已经以注释形式写于代码中。
1.基本操作 1.1 结构体定义

// 不带头结点 typedef struct LNode {// 定义单链表结点类型 int data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList;

1.2 初始化

//初始化一个空的单链表 bool InitList(LinkList &L){ L = NULL; //空表，暂时还没有任何结点 return true; }

1.3 判空

// 判断单链表是否为空 bool Empty(LinkList L) { // 无头结点，那么头指针指向NULL，单链表即为空 if(L == NULL) { return true; } else { return false; } // 简洁 // return(L == NULL); }

1.4 按位序插入

// 按位序插入 // 在第i个位置插入元素e bool ListInsert(LinkList &L, int i, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // 判断插入位序是否存在问题 if(L == NULL || i < 1) { return NULL; } // 判断插入的位置是否是第1个 // 由于没有头指针，所以此处操作与其它结点不同，需要单独处理，以更新头指针 if(i == 1) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/e; // 令新结点指向之前头指针所指的结点 s->next = L; // 头指针指向新结点 L = s; return true; } LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 p = L; // 初始令p指向第一个结点 // 通过循环，找到第i-1个结点 // 如果i大于链表长度，则不可插入，此时p指向最后结点的指针域，即NULL while(p != NULL && j < i - 1){ p = p->next; j++; } // p值为NULL说明遍历完成后仍未为找到位序为i的结点，说明i大于链表长度，i不合法 if (p == NULL) return false; // 在第i-1个结点后插入新结点 LNode *s = (LNode *)malloc(sizeof(LNode)); // 注意顺序，应该先让要插入结点的指针域指向后一结点 // 之后再断开前一结点与后一结点的指针，使前一结点指向要插入结点 s->data = https://www.it610.com/article/e; s->next = p->next; //将结点s连到p后 p->next = s; return true; }

1.5 指定结点后插操作

// 指定结点后插操作：在p结点之后插入元素e // 此操作与带头结点情况相同，由于是指定结点后插，所以即使是第一个结点也无需特殊处理 // LNode强调为结点 bool InsertNextNode(LNode *p, int e) { // p不合理的情况 if(p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 此处先将要插入结点的指针域指向前一个结点的指针域，即后一个结点的地址 // 之后再令前一个结点的指针域指向要插入结点 // 顺序不可颠倒，否则可能出现找不到之后结点的情况 s->data = https://www.it610.com/article/e; s->next = p->next; p->next = s; return true; }

1.6 指定结点前插操作_1

// 指定结点前插操作：在p结点之前 // 此处需要传入头指针，因为是在p前插入 // 而由于此为单链表，如果只知道p节点，只能遍历找到p后的元素，而找不到p前的元素 // 所以只能通过头结点遍历，找到p的前驱结点 bool InsertPriorNodeRoutine(LinkList L, LNode *p, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // p不合理的情况 if(L == NULL || p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 插入时是第一个结点的情况，需要特殊处理，以更新头指针 if(L == p) { s->data = https://www.it610.com/article/e; s->next = p; L = s; return true; } // 定义一个指针，初始指向第一个结点 LNode *p1 = L; // 遍历找到p结点的前驱结点 while(p1 != NULL && p1->next != p) { p1 = p1->next; } // p1若等于NULL，表示p不存在或是链表无元素 if(p1 == NULL) { return false; } // 插入操作 s->data = https://www.it610.com/article/e; s->next = p; p1->next = s; return true; }

1.7 指定结点前插操作_2

// 指定结点前插操作：在p结点之前 // 此处可以通过一种特殊方法完成前插 // 本质上还是后插操作 bool InsertPriorNode(LNode *p, int e) { // p不合理的情况 if(p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 插入操作 // 通过将s插入p结点之后，然后将s结点与p结点的数据域进行互换 // 可以视作完成了前插操作 s->next = p->next; p->next = s; s->data = https://www.it610.com/article/p->data; p->data =https://www.it610.com/article/e; return true; }

1.8 按位序删除

// 按位序删除 bool ListDelete(LinkList &L, int i, int &e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // i不合理的情况 if(L == NULL || i < 1) { return false; } // 删除第一个结点的情况 // 需要更新头指针，要单独处理 if(i == 1) { LNode* q = L->next; e = q->data; // 一般情况为p->next = q->next // 但由于无头结点，所以需要直接令L指向q->next，以此更新头指针 L = q->next; free(q); return true; } LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 // 初始令p指向头指针 p = L; // 通过遍历找到第i - 1个结点，即要删除结点的前驱结点 while(p != NULL && j < i - 1) { p = p->next; j++; } // 若p等于NULL，则要么此链表为空，要么i值大于链表长度，显然不合理 // p->next为空表示第i-1个结点之后已经没有其他结点了，无法进行删除操作 if(p == NULL || p->next == NULL) { return false; } // 删除操作 // 就是将前驱结点指针域指向后继结点 LNode *q = p->next; e = q->data; p->next = q->next; // 不要忘记释放空间！！！ free(q); return true; }

1.9 按位查找

// 按位查找，返回第i个元素 // 之前操作部分按位查找部分可以以此部分代码代替，提高代码复用性（封装） LNode* GetElem(LinkList L, int i) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return NULL; } // 判断插入位序是否存在问题 // 由于此是不带头结点的情况，所以i值不能小于1，因为第一个结点前是头指针 // 带头结点的第一个结点前是头结点 if(i < 1) return NULL; LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 p = L; // 初始令p指向第一个结点 // 通过循环，找到第i个结点 // 如果i大于链表长度，则找不到此节点，此时p指向最后结点的指针域，即NULL // 如果i初始为1，会直接返回第一个结点结点地址 while(p != NULL && j < i) { p = p->next; j++; } return p; }

1.10 按值查找

// 按值查找，找到数据域等于e的结点 LNode* LocateElem(LinkList L, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return NULL; } LNode* p = L; // 从第一个结点开始查找数据域为e的结点 // 找不到，则会在遍历后指向NULL while (p != NULL && p->data != e) { p = p->next; } return p; }

1.11 表的长度

// 求表的长度 // 就是通过遍历所有结点，然后通过计数器来累加得到长度 int Length(LinkList L) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return 0; } int len = 0; LNode* p = L; while(p->next != NULL) { p = p->next; len++; } return len; }

1.12 单链表建立（尾插法）

// 尾插法 // 通过尾插法建立的链表，顺序为插入时元素的顺序 LinkList TailInsert(LinkList &L) { // 设置ElemType为整型 int x; // 定义表尾指针 // 对于尾插法，如果只通过头结点遍历的话 // 每次插入时都要先遍历到表尾，时间复杂度为O(1+2+...+n-1)=O(n^2) // 所以选择增加一个尾指针，来避免遍历 // s为要插入的结点，r为表尾指针 LNode *s, *r = L; // 输入结点的值 scanf("%d", &x); // 第一个结点需要特殊处理 L = (LNode*)malloc(sizeof(LNode)); L->data = https://www.it610.com/article/x; r = L; L->next = NULL; // 输入结点的值 scanf("%d", &x); // 表示键入9999后建表结束 while(x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/x; r->next = s; // r指向新的表尾结点 r = s; // 继续输入下一个结点的值，直至输入9999结束 scanf("%d", &x); } // 尾指针置空 r->next = NULL; return L; }

1.13 单链表建立（头插法）

// 头插法 // 通过头插法建立的链表，顺序为插入时元素的逆序 LinkList HeadInsert(LinkList &L) { // 设置ElemType为整型 int x; // 不同于尾插法，头插法无需定义更多指针 LNode* s; // 输入结点的值 scanf("%d", &x); // 第一个结点需要特殊处理 L = (LNode*)malloc(sizeof(LNode)); L->data = https://www.it610.com/article/x; L->next = NULL; // 输入结点的值 scanf("%d", &x); // 表示键入9999后建表结束 while(x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/x; s->next = L->next; // 更新头指针 L = s; // 继续输入下一个结点的值，直至输入9999结束 scanf("%d", &x); } return L; }

1.14 输出所有链表元素

// 输出所有链表元素 void PrintList(LinkList L) { if(Empty(L)) { printf("the list is empty"); } LNode* p = L; while(p !=NULL) { printf("%d", p->data); p = p->next; } printf("\n"); }

2.完整代码

#include #include/** * 注意：对于不带头结点的情况，一定要考虑L为NULL的可能性 * 因为在没有头结点的情况下，头指针为NULL是不能够取数据域或者指针域的 */// 不带头结点 typedef struct LNode {// 定义单链表结点类型 int data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; //初始化一个空的单链表 bool InitList(LinkList &L){ L = NULL; //空表，暂时还没有任何结点 return true; }// 判断单链表是否为空 bool Empty(LinkList L) { // 无头结点，那么头指针指向NULL，单链表即为空 if(L == NULL) { return true; } else { return false; } // 简洁 // return(L == NULL); }// 按位序插入 // 在第i个位置插入元素e bool ListInsert(LinkList &L, int i, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // 判断插入位序是否存在问题 if(L == NULL || i < 1) { return NULL; } // 判断插入的位置是否是第1个 // 由于没有头指针，所以此处操作与其它结点不同，需要单独处理，以更新头指针 if(i == 1) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/e; // 令新结点指向之前头指针所指的结点 s->next = L; // 头指针指向新结点 L = s; return true; } LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 p = L; // 初始令p指向第一个结点 // 通过循环，找到第i-1个结点 // 如果i大于链表长度，则不可插入，此时p指向最后结点的指针域，即NULL while(p != NULL && j < i - 1){ p = p->next; j++; } // p值为NULL说明遍历完成后仍未为找到位序为i的结点，说明i大于链表长度，i不合法 if (p == NULL) return false; // 在第i-1个结点后插入新结点 LNode *s = (LNode *)malloc(sizeof(LNode)); // 注意顺序，应该先让要插入结点的指针域指向后一结点 // 之后再断开前一结点与后一结点的指针，使前一结点指向要插入结点 s->data = https://www.it610.com/article/e; s->next = p->next; //将结点s连到p后 p->next = s; return true; }// 指定结点后插操作：在p结点之后插入元素e // 此操作与带头结点情况相同，由于是指定结点后插，所以即使是第一个结点也无需特殊处理 // LNode强调为结点 bool InsertNextNode(LNode *p, int e) { // p不合理的情况 if(p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 此处先将要插入结点的指针域指向前一个结点的指针域，即后一个结点的地址 // 之后再令前一个结点的指针域指向要插入结点 // 顺序不可颠倒，否则可能出现找不到之后结点的情况 s->data = https://www.it610.com/article/e; s->next = p->next; p->next = s; return true; }// 指定结点前插操作：在p结点之前 // 此处需要传入头指针，因为是在p前插入 // 而由于此为单链表，如果只知道p节点，只能遍历找到p后的元素，而找不到p前的元素 // 所以只能通过头结点遍历，找到p的前驱结点 bool InsertPriorNodeRoutine(LinkList L, LNode *p, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // p不合理的情况 if(L == NULL || p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 插入时是第一个结点的情况，需要特殊处理，以更新头指针 if(L == p) { s->data = https://www.it610.com/article/e; s->next = p; L = s; return true; } // 定义一个指针，初始指向第一个结点 LNode *p1 = L; // 遍历找到p结点的前驱结点 while(p1 != NULL && p1->next != p) { p1 = p1->next; } // p1若等于NULL，表示p不存在或是链表无元素 if(p1 == NULL) { return false; } // 插入操作 s->data = https://www.it610.com/article/e; s->next = p; p1->next = s; return true; }// 指定结点前插操作：在p结点之前 // 此处可以通过一种特殊方法完成前插 // 本质上还是后插操作 bool InsertPriorNode(LNode *p, int e) { // p不合理的情况 if(p == NULL) { return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); // 内存分配失败的情况 if(s == NULL) { return false; } // 插入操作 // 通过将s插入p结点之后，然后将s结点与p结点的数据域进行互换 // 可以视作完成了前插操作 s->next = p->next; p->next = s; s->data = https://www.it610.com/article/p->data; p->data =https://www.it610.com/article/e; return true; }// 按位序删除 bool ListDelete(LinkList &L, int i, int &e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 // i不合理的情况 if(L == NULL || i < 1) { return false; } // 删除第一个结点的情况 // 需要更新头指针，要单独处理 if(i == 1) { LNode* q = L->next; e = q->data; // 一般情况为p->next = q->next // 但由于无头结点，所以需要直接令L指向q->next，以此更新头指针 L = q->next; free(q); return true; } LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 // 初始令p指向头指针 p = L; // 通过遍历找到第i - 1个结点，即要删除结点的前驱结点 while(p != NULL && j < i - 1) { p = p->next; j++; } // 若p等于NULL，则要么此链表为空，要么i值大于链表长度，显然不合理 // p->next为空表示第i-1个结点之后已经没有其他结点了，无法进行删除操作 if(p == NULL || p->next == NULL) { return false; } // 删除操作 // 就是将前驱结点指针域指向后继结点 LNode *q = p->next; e = q->data; p->next = q->next; // 不要忘记释放空间！！！ free(q); return true; }// 按位查找，返回第i个元素 // 之前操作部分按位查找部分可以以此部分代码代替，提高代码复用性（封装） LNode* GetElem(LinkList L, int i) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return NULL; } // 判断插入位序是否存在问题 // 由于此是不带头结点的情况，所以i值不能小于1，因为第一个结点前是头指针 // 带头结点的第一个结点前是头结点 if(i < 1) return NULL; LNode *p; // 指针p指向当前扫描到的结点 int j = 1; // 当前p指向的是第几个结点 p = L; // 初始令p指向第一个结点 // 通过循环，找到第i个结点 // 如果i大于链表长度，则找不到此节点，此时p指向最后结点的指针域，即NULL // 如果i初始为1，会直接返回第一个结点结点地址 while(p != NULL && j < i) { p = p->next; j++; } return p; }// 按值查找，找到数据域等于e的结点 LNode* LocateElem(LinkList L, int e) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return NULL; } LNode* p = L; // 从第一个结点开始查找数据域为e的结点 // 找不到，则会在遍历后指向NULL while (p != NULL && p->data != e) { p = p->next; } return p; }// 求表的长度 // 就是通过遍历所有结点，然后通过计数器来累加得到长度 int Length(LinkList L) { // 链表为空时的情况 // 若为空，则取指针域或数据域会报错 if(L == NULL) { return 0; } int len = 0; LNode* p = L; while(p->next != NULL) { p = p->next; len++; } return len; }// 尾插法 // 通过尾插法建立的链表，顺序为插入时元素的顺序 LinkList TailInsert(LinkList &L) { // 设置ElemType为整型 int x; // 定义表尾指针 // 对于尾插法，如果只通过头结点遍历的话 // 每次插入时都要先遍历到表尾，时间复杂度为O(1+2+...+n-1)=O(n^2) // 所以选择增加一个尾指针，来避免遍历 // s为要插入的结点，r为表尾指针 LNode *s, *r = L; // 输入结点的值 scanf("%d", &x); // 第一个结点需要特殊处理 L = (LNode*)malloc(sizeof(LNode)); L->data = https://www.it610.com/article/x; r = L; L->next = NULL; // 输入结点的值 scanf("%d", &x); // 表示键入9999后建表结束 while(x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/x; r->next = s; // r指向新的表尾结点 r = s; // 继续输入下一个结点的值，直至输入9999结束 scanf("%d", &x); } // 尾指针置空 r->next = NULL; return L; }// 头插法 // 通过头插法建立的链表，顺序为插入时元素的逆序 LinkList HeadInsert(LinkList &L) { // 设置ElemType为整型 int x; // 不同于尾插法，头插法无需定义更多指针 LNode* s; // 输入结点的值 scanf("%d", &x); // 第一个结点需要特殊处理 L = (LNode*)malloc(sizeof(LNode)); L->data = https://www.it610.com/article/x; L->next = NULL; // 输入结点的值 scanf("%d", &x); // 表示键入9999后建表结束 while(x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = https://www.it610.com/article/x; s->next = L->next; // 更新头指针 L = s; // 继续输入下一个结点的值，直至输入9999结束 scanf("%d", &x); } return L; }// 输出所有链表元素 void PrintList(LinkList L) { if(Empty(L)) { printf("the list is empty"); } LNode* p = L; while(p !=NULL) { printf("%d", p->data); p = p->next; } printf("\n"); }int main() { LinkList L; InitList(L); TailInsert(L); PrintList(L); printf("get_2:%d\n",GetElem(L, 2)->data); printf("locate_5:%d\n",LocateElem(L, 5)->data); printf("length:%d\n", Length(L)); InsertPriorNode(GetElem(L, 2), 7); PrintList(L); InsertNextNode(GetElem(L, 2), 5); PrintList(L); ListInsert(L, 3, 3); PrintList(L); int e; ListDelete(L, 3, e); PrintList(L); printf("e:%d\n", e); }

3.运行截图
文章图片

推荐阅读

• 

  互联网销售数据分析
• 

  redis解决高并发问题,如商品秒杀 redis高并发架构与底层原理
• 

  tcl洗衣机快洗要多久 tcl洗衣机快速洗衣多久
• 

  销售是做什么的 销售具体是做什么的
• 

  缅甸红酸枝是红木吗
• 

  射击游戏最帅角色排行榜，射击游戏高手
• 

  adb push build.prop system 重启后无法进入系统解决方法
• 

  莆田本土“19+17”:含15名小学生
• 

  道声|道声 再见
• 

  哪些食物含有花青素 为什么鸡蛋和紫薯一起就变绿
• 

  DOTA2暗影萨满怎么玩 DOTA2小y技能介绍
• 

  sap现金管理与预算控制，erp现金管理
• 

  pdf阅读器的文字怎么粘贴复制
• 

  豁牙巴是什么意思 豁牙巴应该是什么意思
• 

  新冠疫苗|海口新增19个60岁及以上人群新冠疫苗接种点 老年人接种点达27个
• 

  健康码灰色几天能变绿
• 

  支付宝账户管理在哪
• 

  mongodb 集合内文档之间关联 mongodb 合并数据
• 

  儿童肾病综合症治疗方法首选 儿童肾病综合症治疗方法
• 

  管钳价格 「管钳什么牌子的最好」

• C语言中文网课后作业day01
• 数据结构|MySQL主从复制详细介绍
• 数据结构|红黑树（RBTree）原理及实现
• 力扣|力扣打卡之最小栈
• MySQL零基础入门|MySQL 数据库基础知识（系统化一篇入门）
• C
• scau|18937 阿克曼(Ackmann)函数
• 链表|数据结构与算法（环形链表，栈）
• dp|最近写过的dp题单（持续更新）