C++编程语言实现单链表详情-C/C++开发

这篇文章主要介绍的是利用C语言实现单链表，实现的是链表中最简单的一种单链表且每个结点中只含有一个指针域，下面将详细举例说明,需要的朋友可以参考一下

一、单链表简单介绍

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


//================线性表的单链表存储结构=================
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;
}

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

单链表插数据情况


//===============================算法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;
}