C++编程语言实现单链表详情

Z时代
2024-01-10
分类：IT

一、单链表简单介绍

首先，我们再回顾一下线性表的两种存储方式——顺序存储与链式存储

上图左边为顺序存储，右边为链式存储

之前我们利用数组来实现顺序表，对于顺序表的优点缺点，总结来说就是，查找方便，增删复杂。

线性表之顺序存储的优缺点

而链表特点可以说恰恰相反，增删方便，查找复杂。

今天实现的是链表中最简单的一种——单链表（每个结点中只含有一个指针域）

对于链表我们只知道它每个结点的存储的物理地址是不连续的，但逻辑上还是符合线性表“一对一”的特点。因此，我们就需要用“线”（指针）把这些不连续的结点按顺序连接起来。

链表的结点在内存中存储不连续

通过指针把每个结点按顺序连起来

到这里我们可以发现，要想表示链表中的结点，光存储结点的数据是不够的，还得有指针。因此，单链表的结点结构如下：

数据域存储数据，指针域存储指针


//================线性表的单链表存储结构=================
typedef struct LNode {
ElemType data;//数据域
struct LNode *next;//指针域
}LNode;

注意：因为指针是指向每个结点的，也就是指向struct LNode这个自定义的结构体类型，所以指针的类型就是struct LNode*。

二、下面我们先实现单链表的初始化。

单链表的初始化其实就是创建几个结点，然后用指针把他们连接起来。

先创建一个头指针，实际上就是创建一个头结点，然后头指针指向头结点就OK


LNode* CreateList_L(int n) {//顺位序输入n个元素的值，建立带表头结点的单链线性表L
 LNode *p = (LNode*)malloc(sizeof(LNode));//创建头结点（p也就是头指针）
 LNode *temp = p;//声明一个指针指向头结点,用于遍历链表(不是头指针，因为它只是暂时指向头结点)
 //生成链表
 for (int i = n; i > 0; --i) 
 {
  LNode *node = (LNode *)malloc(sizeof(LNode));//创建结点
  if (node){//分配地址成功
   scanf_s("%c", &(node->data));
   node->next = NULL;
   //建立新结点与直接前驱结点的逻辑关系
   temp->next = node;
   temp = temp->next;
  }
  else {//如果分配地址失败，则返回错误信息
    printf("结点创建失败！\n");
  }
 }
 return p;
}

三、实现单链表的插入与删除数据

单链表插数据情况

观察可知，我们要实现插入操作，需要的操作是一样的。

S1：将后继结点的指针赋给新结点的指针域；

S2：将前驱节点的指针域改为指向新结点的指针。

注意：S1和S2不能换顺序。


//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
 //在带头结点的单链表L中第i个位置之前插入元素e
 int j = 0;
 LNode *p = L;
 while (p&&j < i - 1) {
  p = p->next;
  ++j;
 }//寻找第i-1个结点
 if (!p || j > i - 1)return ERROR;//i小于1或者大于表长时
 LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的结点
 s->data = e; s->next = p->next;//S1
 p->next = s;//S2
 return OK;
}

单链表删除数据示意图

观察可知，只需要将待删结点的前驱结点的指针域的值换成待删结点的后继结点的指针即可。


//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
 //在带头结点的单链表L中，删除第i个元素，并由e返回其值
 LNode *p = L;
 int j = 0;
 while (p->next&&j < i - 1) {//寻找第i个结点，并令p指向其前驱
  p = p->next; ++j;
 }
 if (!(p->next) || j > i - 1)return ERROR;//删除位置不合理
 LNode *q = p->next; p->next = q->next;//删除并释放结点
 *e = q->data; free(q);
 return OK;
}
三、参考代码实现与截图
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define ElemType char
typedef int Status;
//================线性表的单链表存储结构==================
typedef  struct LNode {
 ElemType data;//数据域
 struct LNode *next;//指针域
}LNode;
LNode* CreateList_L(int n) {//顺位序输入n个元素的值，建立带表头结点的单链线性表L
 LNode *p = (LNode*)malloc(sizeof(LNode));//创建头结点
 LNode *temp = p;//声明一个指针指向头结点,用于遍历链表(不是头指针)
 //生成链表
 for (int i = n; i > 0; --i) 
 {
  LNode *node = (LNode *)malloc(sizeof(LNode));//创建结点
  if (node){//分配地址成功
   scanf_s("%c", &(node->data));
   node->next = NULL;
   //建立新结点与直接前驱结点的逻辑关系
   temp->next = node;
   temp = temp->next;
  }
  else {//如果分配地址失败，则返回错误信息
    printf("结点创建失败！\n");
  }
 }
 return p;
}
//===============================算法2.9==========================
Status ListInsert_L(LNode *L, int i, ElemType e) {
 //在带头结点的单链表L中第i个位置之前插入元素e
 int j = 0;
 LNode *p = L;
 while (p&&j < i - 1) {
  p = p->next;
  ++j;
 }//寻找第i-1个结点
 if (!p || j > i - 1)return ERROR;//i小于1或者大于表长时
 LNode* s = (LNode*)malloc(sizeof(LNode));//生成新的结点
 s->data = e; s->next = p->next;
 p->next = s;
 return OK;
}
//=====================算法2.10=================================
Status ListDelete_L(LNode *L, int i, ElemType *e) {
 //在带头结点的单链表L中，删除第i个元素，并由e返回其值
 LNode *p = L;
 int j = 0;
 while (p->next&&j < i - 1) {//寻找第i个结点，并令p指向其前驱
  p = p->next; ++j;
 }
 if (!(p->next) || j > i - 1)return ERROR;//删除位置不合理
 LNode *q = p->next; p->next = q->next;//删除并释放结点
 *e = q->data; free(q);
 return OK;
}
void display(LNode *L) {
 LNode *temp =L;//将temp指针重新指向头结点
 //只要temp指针指向的结点的next不是Null，就执行输出语句。
 while (temp->next) {
  temp = temp->next;
  printf("%c", temp->data);
 }
 printf("\n");
}
int   main() {
 LNode *L = NULL;
 L=CreateList_L(5);
 display(L);
 ListInsert_L(L, 2, 'Y');
 display(L);
 ElemType e;
 ListDelete_L(L, 2, &e);
 display(L);
 printf("返回值为：%c", e);
 system("pause");
 return 0;
}