• [一篇读懂]C语言九讲：线性表应用

    [一篇读懂]C语言九讲：线性表应用

    1. 与408关联解析及本节内容介绍

    1 与408关联解析

    【2010年顺序表】
    42. (13分)设将n (n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p (0 ( X 0 , X 1 , … , X n − 1 ) (X_0,X_1,…, X_{n-1}) (X0​,X1​,…,Xn−1​)变换为 ( X p , X p + 1 , … , X n − 1 , X 0 , X 1 , … , X p − 1 ) (X_p,X_{p+1},…,X_{n-1},X_0,X_1,…,X_{p-1}) (Xp​,Xp+1​,…,Xn−1​,X0​,X1​,…,Xp−1​)。要求:
    1)给出算法的基本设计思想。
    2)根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
    3)说明你所设计算法的时间复杂度和空间复杂度。

    【2012年链表】
    42. 假定采用带头结点的单链表保存单词，当两个单词有相同的后级时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。
    1
    设str1和 str2分别指向两个单词所在单链表的头结点，链表结点结构为data | next，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p)。要求:
    1)给出算法的基本设计思想。
    2)根据设计思想,采用C或C++或Java语言描述算法，关键之处给出注释。
    3)说明你所设计算法的时间复杂度。

    • 顺序表结合排序。
    • 链表本身。

    2 本节内容介绍

    本节分为四小节讲解。

    • 第一小节主要针对顺序表的原理进行解析。
    • 第二小节和第三小节主要讲解顺序表的初始化、插入，删除、查找进行实战。
    • 第四小节主要针对链表的原理进行解析。

    2. 线性表的顺序表示原理解析

    • 一切数据结构 - 增删查改

    1 线性表

    线性表的定义

    由n (n≥0）个相同类型的元素组成的有序集合。
    L = ( a 1 , a 2 , … , a i − 1 , a i , a i + 1 , … , a n ) L=(a_1,a_2,…, a_{i-1},a_i,a_{i+1},…, a_n) L=(a1​,a2​,…,ai−1​,ai​,ai+1​,…,an​)

    • 线性表中元素个数n，称为线性表的长度。当n=0时，为空表。
    • a 1 a_1 a1​是唯一的“第一个”数据元素， a n a_n an​是唯一的“最后一个”数据元素。
    • a i − 1 a_{i-1} ai−1​为 a i a_i ai​的直接前驱， a i + 1 a_{i+1} ai+1​为 a i a_i ai​的直接后继。

    线性表的特点

    • 表中元素的个数是有限的。
    • 表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间
    • 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序

    注意：
    本小节描述的是线性表的逻辑结构，是独立于存储结构的！

    2 线性表的顺序表示

    简称：顺序表

    顺序表的定义

    1

    • 顺序表逻辑上相邻的两个元素在物理位置上也相邻。

    顺序表的定义：

    #define Maxsize 50 //定义线性表的长度
typedef struct 
{
	ElemType data[Maxsize] ; //顺序表的元素
	int len; //顺序表的当前长度
}SqList; //顺序表的类型定义

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    顺序表优缺点

    优点：

    • 可以随机存取（根据表头元素地址和元素序号）表中任意一个元素。
    • 存储密度高，每个结点只存储数据元素。

    缺点：

    • 插入和删除操作需要移动大量元素。
    • 线性表变化较大时，难以确定存储空间的容量。
    • 存储分配需要一整段连续的存储空间，不够灵活。

    顺序表插入操作

    插入

    • 最好情况：在表尾插入元素，不需要移动元素，时间复杂度为O(1)。
    • 最坏情况：在表头插入元素，所有元素依次后移，时间复杂度为O(n)。
    • 平均情况：在插入位置概率均等的情况下，平均移动元素的次数为n/2，时间复杂度为O(n)。

    代码片段：

    //判断插入位置i是否合法（满足1≤i≤len+1 )
//判断存储空间是否已满（即插入x后是否会超出数组长度)
for(int j = L.len; j >= i; j--) //将最后一个元素到第i个元素依次后移一位
	L.data[j] = L.data[j-1] ;
L.data[i-l] = x; //空出的位置i处放入x
L.len++; //线性表长度加1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    顺序表删除操作

    删除

    • 最好情况：删除表尾元素，不需要移动元素，时间复杂度为O(1)。
    • 最坏情况：删除表头元素，之后的所有元素依次前移，时间复杂度为O(n)。
    • 平均情况：在删除位置概率均等的情况下，平均移动元素的次数为(n-1)/2，时间复杂度为O(n)。

    代码片段：

    //判断删除位置i是否合法（满足1≤i≤len)
e = L.data[i-1] ; //将被删除的元素赋值给e
for(int j = i; j < L.len; j++) //将删除位置后的元素依次前移
	L.data[j-1] = L.data[j];
L.len--; //线性表长度减1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 注意：插入和删除时，i的合法范围是不一样的。

    动态分配

    • 动态分配的数组仍属于顺序存储结构。
    #define Initsize 100 //表长度的初始定义
typedef struct {
	ElemType *data; //指示动态分配数组的指针
	int MaxSize,length; //数组的最大容量和当前个数
}SeqList; //动态分配数组顺序表的类型定义

    • 1
    • 2
    • 3
    • 4
    • 5

    指针指向哪？

    C的初始动态分配语句为:

    L.data = (ElemType*)malloc(sizeof(ElemType) *Initsize);

    • 1

    C++的初始动态分配语句为:

    L.data = new ElemType[Initsize];

    • 1

    3. 顺序表的初始化及插入操作实战

    • 业界命名规范（变量名，或者函数名）：
    1. 下划线命名法 list_insert - 不同单词用下划线隔开。
    2. 驼峰命名法 ListInsert - 每个单词的首字母大写。
    #include 

#define MaxSize 50
typedef int ElemType; //顺序表存储其他类型元素时，可以快速完成代码修改
//静态分配
typedef struct
{
	ElemType data[MaxSize];
	int length; //当前顺序表中有多少个元素
}SqList;

动态分配
//#define InitSize 100
//typedef struct
//{
//	ElemType *data;
//	int capacity; //动态数组的最大容量
//	int length;
//}SeqList;

//顺序表的插入，因为L会改变，因此这里要用引用，i是插入的位置
bool ListInsert(SqList &L, int i, ElemType element)
{
	//判断i是否合法
	if (i < 1 || i > L.length + 1)
	{
		return false;//未插入成功返回false
	}
	//如果存储空间满了，不能插入
	if (L.length == MaxSize)
	{
		return false;//未插入成功返回false
	}
	//把后面的元素依次往后移动，空出位置，来放要插入的元素
	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = element; //放入要插入的元素
	L.length++;//顺序表长度要加1
	return true;//插入成功返回true
}

//打印顺序表
void PrintList(SqList L) //不需要改变顺序表L的内容，不需要引用
{
	int i;
	for (i = 0; i < L.length; i++)
	{
		printf("%3d", L.data[i]);//为了打印到同一行，不用换行
	}
	printf("\n");
}


//顺序表的初始化及插入操作实战
int main()
{
	SqList L; //定义一个顺序表，变量L
	bool ret; //ret用来查看函数的返回值，布尔型是True，或者False
	ElemType del; //要删除的元素
	//首先手动在顺序表中赋值 - 放置元素
	L.data[0] = 1;
	L.data[1] = 2; 
	L.data[2] = 3;
	L.length = 3;//设置长度
	ret=ListInsert(L,2,60);//大驼峰命名法
	if (ret) //等价于if (true == ret)
	{
		printf("insert SqList success\n");
		PrintList(L);
	}
	else
	{
		printf("insert SqList failed\n");
	}

	return 0;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    运行结果：
    在这里插入图片描述
    成功在第二个位置插入了60。

    4. 顺序表的删除及查询实战

    #include 

#define MaxSize 50
typedef int ElemType; 

typedef struct
{
	ElemType data[MaxSize];
	int length; 
}SqList;

bool ListInsert(SqList &L, int i, ElemType element)
{
	if (i < 1 || i > L.length + 1)
	{
		return false;
	}
	if (L.length == MaxSize)
	{
		return false;
	}
	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = element;
	L.length++;
	return true;
}


void PrintList(SqList L) 
{
	int i;
	for (i = 0; i < L.length; i++)
	{
		printf("%3d", L.data[i]);
	}
	printf("\n");
}

//删除数据表中的元素，因为L会改变，因此这里要用引用，i是删除的位置，e是为了获取被删除的元素的值
bool ListDelete(SqList &L,int i, ElemType &e)
{
	//判断删除的元素的位置是否合法
	if (i < 1 || i > L.length)
	{
		return false;//一旦走到return函数就结束了
	}
	e = L.data[i - 1];//首先保存要删除元素的值
	int j;
	for (j = i; j < L.length; j++)
	{
		L.data[j - 1] = L.data[j];
	}
	L.length--;//顺序表长度减1
	return true;
}

//查找某个元素的位置，找到了会返回对应位置，没找到就返回0
int LocateElem(SqList L, ElemType element)
{
	int i;
	for (i = 0; i < L.length; i++)
	{
		if (element == L.data[i])
		{
			return i + 1;//因为i是数组的下标，加1以后才是顺序表的下标
		}
	}
	return 0;//循环结束没找到
}

//顺序表的删除和查找操作实战
int main()
{
	SqList L; //定义一个顺序表，变量L
	bool ret; //ret用来查看函数的返回值，布尔型是True，或者False
	//首先手动在顺序表中赋值 - 放置元素
	L.data[0] = 1;
	L.data[1] = 2;
	L.data[2] = 3;
	L.length = 3;//设置长度
	ret = ListInsert(L, 2, 60);
	if (ret) 
	{
		printf("insert SqList success\n");
		PrintList(L);
	}
	else
	{
		printf("insert SqList failed\n");
	}

	printf("---------------------------------------------\n");

	ElemType del; 删除的元素存入del内
	ret = ListDelete(L, 1, del);

	if (ret) //等价于if (true == ret)
	{
		printf("delete SqList success\n");
		printf("del element = %d\n", del);
		PrintList(L);//顺序表打印
	}
	else
	{
		printf("delete SqList failed\n");
	}

		int pos;//存储元素位置
	pos = LocateElem(L, 60);
	if (pos)
	{
		printf("find this element\n");
		printf("element pos = %d\n", pos);
	}
	else
	{
		printf("don't find this element\n");
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

    运行结果：
    1

    • 注意：
      1
      出现这种情况时，是因为顺序表长度没有减1。

    5. 线性表的链式表示

    顺序表有一些缺点：

    • 插入和删除操作移动大量元素。
    • 数组的大小不好确定。
    • 占用一大段连续的存储空间，造成很多碎片。

    1 单链表

    单链表的定义

    1

    • 链表中逻辑上相邻的两个元素在物理位置上不相邻。
    • 单链表节点的定义：
    typedef struct LNode //单链表结点类型
{
	ElemType data; //数据域
	struct LNode *next; //指针域
//当结构体中用到结构体本身时，名字无法省略
}LNode, *LinkList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    链表结点：
    1

    • 当指针域为NULL时结尾。

    头结点

    头结点

    • 头指针：链表中第一个结点的存储位置，用来标识单链表。

    • 头结点：在单链表第一个结点之前附加的一个结点，为了操作上的方便。

    • 若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，其标识一个链表。

    • 头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。

    链表的优缺点

    优点：

    • 插入和删除操作不需要移动元素，只需要修改指针。
    • 不需要大量的连续存储空间。

    缺点：

    • 单链表附加指针域，也存在浪费存储空间的缺点。
    • 查找操作时需要从表头开始遍历，依次查找，不能随机存取。

    2 单链表插入操作

    • 创建新结点代码：
     q = (LNode*)malloc(sizeof(LNode))
 q -> data = x;

    • 1
    • 2
    • 表头/中间插入元素的代码：
    q -> next = p -> next;
p -> next = q;

    • 1
    • 2
    • 表尾插入元素的代码：
    p -> next=q;
q -> next = NULL;

    • 1
    • 2

    11

    3 单链表删除操作

    • 表头/中间/表尾删除元素的代码：
    p = GetElem(L,i-1);//查找删除位置的前驱节点
q = p -> next;
p -> next = q -> next;//结点q断链
free(q);//必须

    • 1
    • 2
    • 3
    • 4

    1

    4 单链表查找操作

    1

    • 按序号查找结点值的算法如下：
    LNode *p = L -> next;
int j=1;
while (p && j < i)
{
	p = p -> next;
	j++;
}
return p;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 按值查找结点值的算法如下：
    LNode *p = L -> next;
while (p != NULL && p -> data != e) 
{
	p = p -> next;
}
return p;


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    总结

    2

    • 一切数据结构 - 增删查改

    2.1

    • a i − 1 a_{i-1} ai−1​为 a i a_i ai​的直接前驱， a i + 1 a_{i+1} ai+1​为 a i a_i ai​的直接后继。
    • 表中元素的个数是有限的。
    • 表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间
    • 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序

    2.2

    • 顺序表逻辑上相邻的两个元素在物理位置上也相邻。

    顺序表优点：

    • 可以随机存取（根据表头元素地址和元素序号）表中任意一个元素。
    • 存储密度高，每个结点只存储数据元素。

    顺序表缺点：

    • 插入和删除操作需要移动大量元素。
    • 线性表变化较大时，难以确定存储空间的容量。
    • 存储分配需要一整段连续的存储空间，不够灵活。
    • 动态分配的数组仍属于顺序存储结构。

    3.1

    • 业界命名规范（变量名，或者函数名）：
    1. 下划线命名法 list_insert - 不同单词用下划线隔开。
    2. 驼峰命名法 ListInsert - 每个单词的首字母大写。

    5.1

    • 链表中逻辑上相邻的两个元素在物理位置上不相邻。

    • 头指针：链表中第一个结点的存储位置，用来标识单链表。

    • 头结点：在单链表第一个结点之前附加的一个结点，为了操作上的方便。

    • 若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，其标识一个链表。

    • 头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。

    链表的优点：

    • 插入和删除操作不需要移动元素，只需要修改指针。
    • 不需要大量的连续存储空间。

    链表的缺点：

    • 单链表附加指针域，也存在浪费存储空间的缺点。
    • 查找操作时需要从表头开始遍历，依次查找，不能随机存取。
  • 相关阅读:
    process.env.NODE_ENV
    css主题切换
    一文详解企业数据分类分级的推进路径
    有关排序的算法
    【JavaScript高级】手写apply()、call()、bind()
    【虚幻引擎UE】UE5 材质动态修改的2种方法（含工程源码）
    maven打包可运行jar
    .NET 值类型 引用类型
    .NET跨平台框架选择之一 - Avalonia UI
    java Collections工具类
  • 原文地址：https://blog.csdn.net/m0_58991879/article/details/127945181