数据结构和算法（C）------4.线性表（2）单链表

2021-11-17 03:56:37

目录

1. 链式存储结构

1.1 定义

1.2 实现方式

1.3 与链式存储有关的术语   

1.4 链表（链式存储结构）的特点和优缺点

1.4.1 特点

 1.4.2 优点

1.4.3 缺点

2.  单链表的实现

2.1 单链表的存储结构定义

2.2  初始化(构造一个空表 )

2.2.1 算法步骤

2.2.2 算法描述 

2.3 销毁（删除整个表）

2.4 清空（删除表中所有数据）

2.5  求表长 

2.6 判断表是否为空

2.7 取值（根据位置i获取相应位置数据元素的内容）

2.7.1 算法步骤

2.7.2  算法描述（用e返回i位置上的数据）

2.8  按值查找（返回位置i,不存在返回0）

2.8.1 算法步骤

2.8.2 算法描述 

2.8.3 复杂度分析 

2.9 插入（插在第 i 个结点之前）

2.9.1 算法步骤

 2.9.2 算法描述

2.9.3 复杂度分析

2.10  删除（删除第 i 个结点）

2.10.1 算法步骤

2.10.2 算法描述

2.10.3 复杂度分析 

2.11 单链表的建立（头插法）

2.11.1 算法步骤

​ 2.11.2 算法描述

2.12 单链表的建立（尾插法）

2.12.1 算法步骤

2.12.2 算法描述 

2.13 main函数调用 

3. 完整代码

1. 链式存储结构

1.1 定义

        结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。

1.2 实现方式

数据结构和算法（C）------4.线性表（2）单链表

各节点有两个域组成：数据域和指针域

数据域：存储数据

指针域：存储后续节点的地址

数据结构和算法（C）------4.线性表（2）单链表

1.3 与链式存储有关的术语   

  1. 结点
  2. 链表
  3. 单链表、双链表、循环链表
  4. 头指针、头结点和首元结点

1、结点：数据元素的存储映像。由数据域和指针域两部分组成

2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构

3、单链表、双链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；首尾相接的链表称为循环链表

数据结构和算法（C）------4.线性表（2）单链表

4、头指针是指向链表中第一个结点的指针；

首元结点是指链表中存储第一个数据元素a1的结点；

头结点是在链表的首元结点之前附设的一个结点，数据域内只放空表标志和表长等信息

数据结构和算法（C）------4.线性表（2）单链表

 5. 单链表有头结点和无头结点的结构示意

数据结构和算法（C）------4.线性表（2）单链表

 思考：

（1）如何表示空表？

有头结点时，当头结点的指针域为空时表示空表。

 数据结构和算法（C）------4.线性表（2）单链表

 无头结点时，头指针为空时为空表。

数据结构和算法（C）------4.线性表（2）单链表

（2）在链表中设置头结点有什么好处？

①便于首元结点的处理

        首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;

②便于空表和非空表的统一处理

        无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

（3）头结点的数据域内装的是什么？

        头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

1.4 链表（链式存储结构）的特点和优缺点

1.4.1 特点

  1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
  2. 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。

 这种存取元素的方法被称为顺序存取法

 1.4.2 优点

1.数据元素的个数可以*扩充

2.插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高

1.4.3 缺点

  1. 存储密度小
  2.  存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问

2.  单链表的实现

2.1 单链表的存储结构定义

typedef int ElemType;
typedef int Status;

enum StatusCode
{
	TRUE = 1,
	FALSE = 0,
	OK = 1,
	ERROR = 0,
	INFEASIBLE = -1,
	OVERFLOW = -2
};
typedef struct LNode
{
	ElemType data;
	struct LNode* next;

}LNode,  *LinkList;

2.2  初始化(构造一个空表 )

2.2.1 算法步骤

  1. 生成新结点作头结点，用头指针L指向头结点。

  2. 头结点的指针域置空。

2.2.2 算法描述 

Status InitList(LinkList* pL)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	if ((*pL) == NULL)
	{
		perror("InitList");
		return ERROR;
	}
	(*pL)->next = NULL;
	return OK;
}

其中，参数使用的是LinkList*类型的参数，是二级指针，因为初始化需要对表进行修改，而表是用头指针表示的，所以需要用到二级指针，将表地址传进去。解引用就获得头指针。

2.3 销毁（删除整个表）

Status DestoryList(LinkList* pL)
{
	LNode* p = (LinkList)malloc(sizeof(LNode));
	while (*pL)
	{
		p = *pL;
		*pL = (*pL)->next;
		free(p);
	}
	p = NULL;
	return OK;
}

2.4 清空（删除表中所有数据）

Status ClearList(LinkList* pL)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	LNode* q = (LNode*)malloc(sizeof(LNode));
	p = (*pL)->next;  //p指向首元结点
	while (p) {
		q = p->next;
		free(p);     //释放当前p所指向的空间，避免内存溢出
		p = q;
	}
	(*pL)->next = NULL;
	return OK;
}

2.5  求表长 

int ListLength(LinkList L)
{
	LNode* p = L->next;
	int length = 0;
	while (p != NULL)
	{
		p = p->next;
		length++;
	}
	return length;
}

2.6 判断表是否为空

Status IsEmpty(LinkList L)
{
	if (L->next == NULL)
		return TRUE;
	return FALSE;
}

2.7 取值（根据位置i获取相应位置数据元素的内容）

2.7.1 算法步骤

  1.  从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
  2.  j 做计数器，累计当前扫描过的结点数，j 初值为1
  3. 当p指向扫描到的下一结点时，计数器j加1
  4. 当j = i 时，p所指的结点就是要找的第i个结点

2.7.2  算法描述（用e返回i位置上的数据）

Status GetElem(LinkList L, int i, ElemType* e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}   //找到第i-1位置

	if (!p || j > i)return ERROR;  
	*e = (p->data);
	return OK;
}

2.8  按值查找（返回位置i,不存在返回0）

2.8.1 算法步骤

  1. 从第一个结点起，依次和e相比较。
  2.  如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”
  3. 如果查遍整个链表都没有找到其值和e相等的元素，则返回0

2.8.2 算法描述 

int LocateElem(LinkList L, ElemType e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = L->next;
	int loc = 1;
	while (p && (p->data != e))
	{
		p = p->next;
		loc++;
	}
	if (p)
		return loc;
	else
		return 0;
}

2.8.3 复杂度分析 

        因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n) 

2.9 插入（插在第 i 个结点之前）

2.9.1 算法步骤

  1. 找到i-1元素存储位置p 

  2. 生成一个新结点*s

  3. 将新结点*s的数域置为插入的元素

  4. 新结点*s的指针域指向第i元素

  5. 令结点*p的指针域指向新结点*s

数据结构和算法（C）------4.线性表（2）单链表

 2.9.2 算法描述

Status InsertList(LinkList* pL, int i, ElemType e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = *pL;
	int j = 0;
	while (p && (j < i - 1))
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)return ERROR;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

2.9.3 复杂度分析

        因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 

2.10  删除（删除第 i 个结点）

2.10.1 算法步骤

  1.  找到i-1元素存储位置p
  2. 保存要删除的结点的值
  3. 令p-＞next指向第i+1元素
  4. 释放结点i位置元素空间

数据结构和算法（C）------4.线性表（2）单链表

2.10.2 算法描述

Status DeleteList(LinkList* pL, int i, ElemType* e)
{
	LNode* p = *pL;
	int j = 0;
	while ((p->next) && j < (i - 1))
	{
		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);
	q = NULL;
	return OK;
}

 思考：能不能直接p->next = p->next->next  ？

        可以，但是第i个元素空间没有释放，并且也不知道删除了什么元素

2.10.3 复杂度分析 

        因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 

2.11 单链表的建立（头插法）

2.11.1 算法步骤

  1.  生成新结点
  2. 将读入数据存放到新结点的数据域中
  3. 将该新结点插入到链表的前端

数据结构和算法（C）------4.线性表（2）单链表 2.11.2 算法描述

void CreateList_H(LinkList* pL, int n)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	(*pL)->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		scanf("%d", &(p->data));
		p->next = (*pL)->next;
		(*pL)->next = p;
	}
}

2.12 单链表的建立（尾插法）

2.12.1 算法步骤

  1. 从一个空表 L 开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点。
  2. 初始时， r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后， r 指向新结点。

数据结构和算法（C）------4.线性表（2）单链表

2.12.2 算法描述 

void CreateList_T(LinkList* pL, int n)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	(*pL)->next = NULL;
	LNode* tail = (LNode*)malloc(sizeof(LNode));//尾指针
	tail = *pL;
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		scanf("%d", &(p->data));
		p->next = NULL;
		tail->next = p;
		tail = p;         //让尾指针始终指向最后一个元素
	}
}

2.13 main函数调用 

int main()
{
	LinkList La; //定义链表
	CreateList_T(&La, 20);//1,2,3,...,20
    printf("%d\n", IsEmpty(La));
	int La_len = ListLength(La);
	for (int i = 1; i <= La_len; i++)
	{
		int e;
		GetElem(La, i, &e);
		printf("%d ", e);
	}
	printf("%d\n", La_len);
	printf("%d\n", LocateElem(La, 10));
	int a = 0;
	DeleteList(&La, 8, &a);
	printf("%d\n", a);
	printf("%d\n", ListLength(La));
	ClearList(&La);
	printf("%d\n", ListLength(La));
	printf("%d\n", DestoryList(&La));
	return 0;
}

3. 完整代码

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef int Status;

enum StatusCode
{
	TRUE = 1,
	FALSE = 0,
	OK = 1,
	ERROR = 0,
	INFEASIBLE = -1,
	OVERFLOW = -2
};

typedef struct LNode
{
	ElemType data;
	struct LNode* next;

}LNode,  *LinkList;  //LinkList为指向结构体Lnode的指针类型


//初始化链表
Status InitList(LinkList* pL)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	if ((*pL) == NULL)
	{
		perror("InitList");
		return ERROR;
	}
	(*pL)->next = NULL;
	return OK;
}

//判断单链表是否为空
Status IsEmpty(LinkList L)
{
	if (L->next == NULL)
		return TRUE;
	return FALSE;
}


//销毁单链表,头结点也销毁
Status DestoryList(LinkList* pL)
{
	LNode* p = (LinkList)malloc(sizeof(LNode));
	while (*pL)
	{
		p = *pL;
		*pL = (*pL)->next;
		free(p);
	}
	p = NULL;
	return OK;
}


//清空单链表
Status ClearList(LinkList* pL)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	LNode* q = (LNode*)malloc(sizeof(LNode));
	p = (*pL)->next;  //p指向首元结点
	while (p) {
		q = p->next;
        free(p);
		p = q;
	}
	(*pL)->next = NULL;
	return OK;
}

//求单链表的长度
int ListLength(LinkList L)
{
	LNode* p = L->next;
	int length = 0;
	while (p != NULL)
	{
		p = p->next;
		length++;
	}
	return length;
}

//单链表的取值
Status GetElem(LinkList L, int i, ElemType* e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)return ERROR;
	*e = (p->data);
	return OK;
}

//按值查找 返回地址
//LNode* LocateElem(LinkList L,ElemType e)
//{
//	LNode* p = L->next;
//	while (p&&(p->data != e))
//		p = p->next;
//	return p;
//}


// 按值查找 返回位置序号
int LocateElem(LinkList L, ElemType e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = L->next;
	int loc = 1;
	while (p && (p->data != e))
	{
		p = p->next;
		loc++;
	}
	if (p)
		return loc;
	else
		return 0;
}


//在第i个位置插入元素e
Status InsertList(LinkList* pL, int i, ElemType e)
{
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p = *pL;
	int j = 0;
	while (p && (j < i - 1))
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)return ERROR;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}


//
Status DeleteList(LinkList* pL, int i, ElemType* e)
{
	LNode* p = *pL;
	int j = 0;
	while ((p->next) && j < (i - 1))
	{
		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);
	q = NULL;
	return OK;
}


//头插法创建链表
void CreateList_H(LinkList* pL, int n)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	(*pL)->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		scanf("%d", &(p->data));
		p->next = (*pL)->next;
		(*pL)->next = p;
	}
}

//尾插法创建链表
void CreateList_T(LinkList* pL, int n)
{
	*pL = (LinkList)malloc(sizeof(LNode));
	(*pL)->next = NULL;
	LNode* tail = (LNode*)malloc(sizeof(LNode));//尾指针
	tail = *pL;
	for (int i = 0; i < n; i++)
	{
		LNode* p = (LNode*)malloc(sizeof(LNode));
		scanf("%d", &(p->data));
		p->next = NULL;
		tail->next = p;
		tail = p;         //让尾指针始终指向最后一个元素
	}
}

int main()
{
	LinkList La; //定义链表
	CreateList_T(&La, 20);//1,2,3,...,20
    printf("%d\n", IsEmpty(La));
	int La_len = ListLength(La);
	for (int i = 1; i <= La_len; i++)
	{
		int e;
		GetElem(La, i, &e);
		printf("%d ", e);
	}
	printf("%d\n", La_len);
	printf("%d\n", LocateElem(La, 10));
	int a = 0;
	DeleteList(&La, 8, &a);
	printf("%d\n", a);
	printf("%d\n", ListLength(La));
	ClearList(&La);
	printf("%d\n", ListLength(La));
	printf("%d\n", DestoryList(&La));
	return 0;
}
上一篇：数据结构 c代码2：单链表


下一篇：(C语言)数据结构-线性表之单链表操作（交集，并集，差集，排序，拼接，去重）