单链表（C语言）

首先单链表，让我们回顾一下线性表的两种存储方法: 顺序存储和链存储

顺序存储在左侧，链式存储在右侧

在使用数组实现序列表之前，先对序列表的优缺点进行总结，因为它易于查找，添加和删除都很复杂.

回顾线性表顺序存储的优缺点

可以说链表的特性恰好相反，易于添加和删除，而且查找起来很复杂.

今天的实现是链表中最简单的-单个链表（每个节点仅包含一个指针字段）

对于链表，我们只知道每个节点的物理地址是不连续的，但是逻辑仍然符合线性表的“”特征. 因此，我们需要使用“线”（指针）顺序连接这些不连续的节点.

链接列表的节点不连续地存储在内存中

通过指针依次连接每个节点

在这里我们发现要表示链表中的节点，存储节点的数据不足，并且必须有一个指针. 因此，单链表的节点结构如下:

数据字段存储数据，而指针字段存储指针. // ===============线性表单链表存储结构================

typedef struct LNode {

ElemType数据； //数据字段

struct LNode * next; //指针字段

} LNode;

注意: 因为指针指向每个节点，即结构LNode的自定义结构类型，所以指针的类型为结构LNode *.

单链接列表的初始化实际上是创建多个节点，然后将它们与指针连接.

首先创建一个头指针，实际上是创建一个头节点，然后将头指针指向头节点. 好

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;
}

将链接列表初始化为abcdef，在第二个位置插入Y单链表，然后删除Y

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-235646-1.html