[数据结构与算法]线性表之单链表

单链表

/*
	链式存储结构：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
	链表：n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构。
	链表（链式存储结构）的特点：
		1）节点在存储器中的位置是任意的， 即逻辑上相邻的数据元素在物理上不一定相邻。
		2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其他结点（这种存储元素的方法称为顺序存储法），
		   所以寻找第一个结点和最后一个结点的时间不等。
	注意：顺序表->随机存取、链表->顺序存取

	结点：数据元素的存储映像，由两个域组成：数据域（存储元素数值数据）、
		指针域（存储直接后继节点的存储位置，指针域中存储的信息称为指针或链）
	链表分为：
		单链表：节点只有一个指针域的链表，称为单链表或线性链表。
		双向链表：节点有两个个指针域的链表，称为双链表。
		循环链表：首尾相接的链表，称为循环链表。
   
	头指针：指向链表中第一个结点的指针。
	首元结点：指链表中存储第一个数据元素的结点。
	头结点：在链表的首元结点之前附设的一个结点。头结点指针域为空表示空表。
   
	链表的存储结构有两种形式：带头结点和不带头结点。
	讨论1：如何表示空表？
		-> 无头结点时，头指针为空时表示空表。
		-> 有头结点时，当头结点的指针域为空时表示空表。
	讨论2：在链表中设置头结点有什么好处？
		1）便于首元结点的处理
		   首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理。
		2）便于空表和非空表的统一处理
		   无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
	讨论3：头结点的数据域内装的是什么？
		头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此节点不能计入链表长度值。

	单链表：
		单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。

	重点
	1）2.6单链表的初始化
	2）2.7单链表的取值
	3）2.8单链表的按值查找
	4）2.9单链表的插入
	5）2.10单链表的删除
	6）2.11前插法创建单链表
	7）2.12后插法创建单链表

	注意：1）如何用循环找第i个节点，如果指向的是首元节点，计数器从1开始，如果指向的是头结点，从0开始
	      2）关于位置非法的表示方法if (!p || j > i - 1) return ERROR;
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// 函数结果状态代码
#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0

typedef int Status;         /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */

typedef struct LNode{   // 声明结点的类型和指向结点的指针类型
	ElemType data;      // 结点的数据域
	struct LNode *next; // 结点的指针域
}LNode,*LinkList;       // LinkList为指向结构体LNode的指针类型

/* 
	1）LNode    表示定义了一个struct LNode类型的变量；
      *LinkList 表示定义了一个struct LNode类型的指针；
	2）LinkList和LNode* 本质上是等价的
	通常习惯上用LinkList定义单链表（即LinkList是指向头结点的指针），用LinkNode*定义指向单链表中任意结点的指针变量
	例如：LinkList L,L为单链表的头指针，LNode *p,p为指向单链表中某个结点的指针
*/

/* 
   2.6 单链表的初始化
   LinkList是指针类型，形参 LinkList *L 相当于二级指针
   *L是LinkList类型(LinkList是一级指针)
   (LinkList)malloc(sizeof(LNode))等于(LNode*)malloc(sizeof(LNode));
   (*L)->next等于(**L).next;
*/
Status InitList(LinkList *L)
{
	*L = (LinkList)malloc(sizeof(LNode)); // 生成新结点作为头结点，用头指针L指向头结点
	(*L)->next = NULL;                    // 头结点的指针域置空
	return OK;
}

/* 
   2.7 单链表的取值
   初始条件：链式线性表L已存在，1≤i≤ListLength(L)
   操作结果：用e返回L中第i个数据元素的值
   注意：i是传入的序号（从1开始）
   */
Status GetElem(LinkList L, int i, ElemType *e)
{
	int j=1;
	LinkList p = L->next;		// 初始化，p指向首元结点，计数器j赋初值为1
	while (p && j<i)            // 顺链域向后扫描，直到p为空或p指向第i个元素
	{
		p = p->next;            // p指向下一个结点
		++j;
	}
	/*
		不满足循环有三种情况：
		1：i<=j
			① i<j，比如i是0或者-1，一开始就不满足循环条件 ×
			② j=i,表示找到结点                            √
		2：p==NULL（i>j），说明链表已经遍历到底，但依然没有找到i，比如链表长度为6，但要查找的是15。×
		即序号大于链表长度，p为空;序号小于链表长度，j>i
	*/
	if (!p || j>i){
		return ERROR;           // i值不合法i>n或i<=0
	}
	*e = p->data;               // 取第i个结点的数据域
	return OK;
}

/* 
	2.8 单链表的按值查找
	在带头结点的单链表L中查找值为e的元素。找到，返回L中值为e的数据元素的地址，查找失败返回NULL
   */
LNode* LocateElem(LinkList L, ElemType e)
{
	LinkList p = L->next;    // 初始化,p指向首元结点
	while (p&&p->data != e)  // 循环结束条件，要么e找到了，要么p=NULL
	{
		p = p->next;
	}
	return p;
}

/*
	2.8变化 按值查找——根据指定数据获取该数据位置序号
    初始条件：链式线性表L已存在
	操作结果：返回L中第1个与e满足关系的数据元素的位序。
	返回L中值为e的数据元素的位置序号，查找失败返回0
	*/
int LocateElem_Pro(LinkList L, ElemType e)
{
	int j = 1;              // 初始化即是第一个结点的位序
	LinkList p = L->next;
	while (p&&p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p){
		return j;
	} else{
		return 0;
	}
}
/* 
   2.9 单链表的插入
   初始条件：链式线性表L已存在,1≤i≤ListLength(L)，
   操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
   注意：1）位置非法的条件是怎么表示的
         2）如何用循环找到i-1个位置
   */
Status ListInsert(LinkList *L, int i, ElemType e)
{
	int j = 0;               // i如果是1号位置，则前一个位置序号是0
	LinkList p = *L,s;       // 注意：这里从头结点开始遍历，计数器指向序数初始j=0，而查找从首元结点开始，计数器j=1
	while (p && j < i-1)     // 查找第i-1个结点，即p指向要插入节点的前一个节点
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1){
		return ERROR;        // i大于表长+1或者小于1，插入位置非法
	}
	s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
	s->data = e;
	s->next = p->next;      // 将结点*s的指针域指向ai
	p->next = s;            // 将结点*p的指针域指向*s
	return OK;
}

/*
   2.10 单链表的删除
   初始条件：链式线性表L已存在，1≤i≤ListLength(L)
   操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
	int j = 0;                  // i如果是1号位置，则前一个位置序号是0
	LinkList p = *L, q;
	while (p->next && j < i-1)	// 查找第i-1个节点，p指向该结点
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1){
		return ERROR;           // 删除位置不合理
	}
	q = p->next;                // 临时保存被删除结点的地址以备释放
	p->next = q->next;			// 改变删除节点前驱结点的指针域
	*e = q->data;               // 保存删除结点的数据域
	free(q);
	return OK;
}

/*
  2.11 前插法创建单链表
  注意：1）形参传入头指针(LNode*)，在函数中给头指针分配内存变量，
           即创建头结点，然后让头指针指向头结点
		2）(*L)是LNode*类型，是一级指针，不是LNode类型，因此是(*L)->next
		3）头插法是倒位序，比如要插入abcde，插入顺序是edcba
*/
void CreateList_H(LinkList *L, int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;                      // 先建立一个带头结点的单链表
	LNode* p;
	for (int i = 0; i<n; i++)
	{
		p = (LNode*)malloc(sizeof(LNode));   // 生成新结点
		scanf("%d",&(p->data));              // 输入元素值
		p->next = (*L)->next;                // 新结点的next指向原先头结点后面的链
		(*L)->next = p;						 // 头结点指向新结点
	}
}
/*
   2.12 后插法创建单链表
   注意：1）尾插法是正位序，即按照顺序插入元素
         2）增加一个尾指针，指向最后一个结点
*/
void CreateList_R(LinkList *L, int n)
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;                     // 先建立一个带头结点的单链表
	
	LinkList p, r;
	r = *L;                                // 尾指针指向头结点
	for (int i = 0; i<n; i++)
	{
		p = (LNode *)malloc(sizeof(LNode)); // 生成新结点
		scanf("%d", &(p->data));            // 输入元素值
		p->next = NULL;
		r->next = p;                        // 尾指针的next指向新结点
		r = p;                              // 尾结点（指针）等于新结点
	}
}


/* 初始条件：链式线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{
	if (L->next){       // 非空返回FALSE(0)
		return FALSE;
	}else {
		return TRUE;    // 1
	}	
}
// 销毁单链表
Status DestroyList(LinkList *L){
	LNode *p;                // 或LinkList p;
	while (*L){
		p = *L;              // 缓存当前结点
		*L = (*L)->next;     // 指针后移
		free(p);             // 释放当前结点
	}
	return OK;
}
/*
   清空单链表
   清空单链表与销毁单链表的区别：清空不释放头结点
*/
Status ClearList(LinkList *L)    // 将L重置为空表
{
	LNode *p, *q;                // 或LinkList p,q;
	p = (*L)->next;              // p指向首元结点
	while (p)                    // 没到表尾
	{
		q = p->next;             // 缓存下一节点
		free(p);
		p = q;
	}
	(*L)->next = NULL;           // 头结点指针域为空
	return OK;
}

// 返回L中数据元素的个数
int ListLength(LinkList L){
	LinkList p = L->next;        // p指向首元结点;
	int i = 0;
	while (p){                   // 遍历单链表，统计结点数
		i++;
		p = p->next;
	}
	return i;
}

/* 打印单个元素 */
Status visit(ElemType c)
{
	printf("%d ", c);
	return OK;
}
/* 初始条件：链式线性表L已存在
   操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
	LinkList p = L->next;
	while (p)
	{
		visit(p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}


void main(){
	LinkList L;
	ElemType e;

	// 2.11 头插法测试
	CreateList_H(&L, 5);  // 输入54321

	printf("【头插法】插入后单链表的值：");
	ListTraverse(L);
	printf("【头插法】插入后单链表长度：%d \n\n", ListLength(L));

	// 链表清空
	ClearList(&L);

	// 2.12 尾插法测试
	CreateList_R(&L, 5);  // 输入12345

	printf("【尾插法】插入后单链表的值：");
	ListTraverse(L);
	printf("【尾插法】插入后单链表长度：%d \n\n", ListLength(L));

	// 2.9 单链表的插入 
	e = 66;
	ListInsert(&L, 4, e); // 给位序4插入元素
	printf("位序4插入后单链表的值：");
	ListTraverse(L);

	// 2.7 单链表的取值 
	GetElem(L, 4, &e);    // 获取第4个位序的元素
	printf("\n位序4获取到的元素值：%d\n\n", e);

	// 2.10单链表的删除
	ListDelete(&L, 4, &e);
	printf("删除位序4后单链表的值：");
	ListTraverse(L);

	// 链表销毁
	DestroyList(&L);
	if (L==NULL){
		printf("\n销毁完成！L=NULL\n");
	}
	system("pause");
}

/*
   控制台测试结果：

   1 2 3 4 5
   【头插法】插入后单链表的值：5 4 3 2 1
   【头插法】插入后单链表长度：5

   1 2 3 4 5
   【尾插法】插入后单链表的值：1 2 3 4 5
   【尾插法】插入后单链表长度：5

   位序4插入后单链表的值：1 2 3 66 4 5

   位序4获取到的元素值：66

   删除位序4后单链表的值：1 2 3 4 5

   销毁完成！L=NULL
   请按任意键继续. . .

*/