初级数据结构--＞顺序表 单链表讲解〈一〉_将顺序表分为l1非素数单链表,以及l2素数单链表

                                                        优秀是一种习惯。

---

首先我们先来看看线性表的概念，由以下的概念我看可以得出一个结论：在逻辑结构上为呈线性的我们便称之为线性结构。哪怕物理结构不是呈现线性   ps：结构分为两种 1.逻辑结构 2.物理结构      ps：物理结构包含两种存储方式（顺序存储：静态    链式存储：动态）

---

那么什么是逻辑结构 什么又是物理结构呢？

我们先从 顺序表 来开始了解

 顺序表：本质就是数组，但是顺序表可以动态增长（利用realloc），（频繁扩容的缺点：空间碎片化：空间（硬盘物理空间、内存等）在长时间使用后，造成空间块不连续的现象，叫做空间碎片化。空间使用的时间越长，碎片化就越严重；所以使用内存对齐能让空间碎片没那么多）并且要求里面存储的数据要求按照从左到右的顺序存储。数组要是想增长空间只能用函数realloc来增容。

缺点：1.动态增容有性能消耗可能会造成空间浪费（频繁扩容），原因是顺序表的增容方式为一次增加原数组的2倍或者1.5倍的长度。 2.如果需要头部插入新的数据的话，那么整个数组都要往后移。    

头插中间插需要挪动数据  O(n)

优点：1.可以随机访问数据      2.cpu高速缓存命中率比较高（因为物理空间是连续的，打印数据时系统会预处理呀16个字节）

扩展：要是打印相同长度的顺序表跟链表，那么顺序表打印的速度比链表打印得要快，因为涉及到高速缓存命中率问题。

 

如图所示：逻辑结构（想象出来的）

而且数组在开辟空间的时候是在栈区（动态顺序表在堆区）上开辟一块连续的空间对数据进行存储的。 

如图所示：物理结构（内存中实际如何存储） 

 从开辟的方式我们也可以看到数组空间是一块连续的空间。

    

前面说到顺序表是有缺陷的，所以为了弥补这一个缺陷，又多出了一种方法，名叫：链表。

接下来往下再给大家简单的讲讲链表。

顺序表总结：综合上面两个图可以知道，顺序表在逻辑跟物理结构上是一致的，都为线性。

---

                        内容温馨提示： 接下来了解下的知识------>单链表

 

 

本节我们先来了解下单向链表的一些知识。

节点:用来存储单个数据的东西我们称它为链表的节点，一个节点至少有一个数据域跟指针域（这个指针域用来存储的是下一个节点的地址）指针是用来指向下一个节点的。

逻辑结构：单向链表的空间是一块一块独立的空间，链接顺序是前一个的指针指向后一个的数据（可以结合下面的逻辑结构图来理解），所以这样就不要求数据是顺序存储的了，而且在链表后尾增加数据的时候只需要开辟一个独立的空间（malloc开辟来的空间，不能够保证地址是连续的），使之前的尾部指针指向该数据就行，不需要挪动前面的数据。如果数头部加入数据，那就让头部的指针指向原来的头部数据就行，中间加入数据的话就让上一个数据的指针指向新插入的数据，让插入的数据指针指向下一个即可。最后的一个数据的指针指向NULL。 创建一个指针变量（phead），指针变量存放的是头节点的地址，所以称这个指针变量为头指针或者头节点，存储的是第一个节点的地址。

所以我们认为链表的存储顺序是连续的线性的，用指针把数据都链接了起来。（举例：好比你去买奶茶取了号，取完号以后你可以在奶茶店的任意地方站着，而不需要排成一排等待，虽然不是站着一排，但是奶茶号已经把取餐的人按顺序排列好了，这就相当于上面讲的逻辑结构跟物理结构）

优点：

1.链表的空间开辟是，按需申请空间，好处是不存在扩容的代价，不存在空间浪费。

2.头部或者中间插入数据不需要对数据再进行挪动了

3.任意数据插入删除 O（1）

缺点：不支持随机访问中间的数据，只能按顺序来访问

低命中还会导致缓存污染

如图所示： 逻辑结构（想象出来的）

 

 如图所示：物理结构（内存中实际如何存储）

 可以看到，这些数据都不是连续的，都是由一条链子把他们都链接了起来，所以在物理结构上呈现一个非线性。

链表总结：逻辑结构跟物理结构不一致一个是线性一个是非线性，但是我们也称它为线性表。

---

接下来将对动态顺序表（因为静态顺序表不实用所以不做展示）跟单链表代码进行一个具体的实现以及讲解 

                                                        首先是动态顺序表

第一步：先创建一个自定义库函数，对头文件 结构体 函数声明进行一个包含，并且通过这里简单了解下动态顺序表的基本功能，分别有：增删查改

                                                        1.自定义头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <assert.h>
 
 
//函数声明  头文件
 
typedef int SeqDateType;
 
 typedef struct  SeqList
{
	SeqDateType* a;  //动态指针
	SeqDateType size;  //当前数量大小
	SeqDateType seqcapacity;//总容量大小
 
}SeqList; //结构体类型重定义 等价于struct  SeqList
 
//实现增删查改的函数声明
void SeqListInfo(SeqList* p);//初始化
void SeqPushBack(SeqList*p, SeqDateType x);   //尾插
void SeqPushFront(SeqList* p, SeqDateType x);  //头插
void SeqPopBack(SeqList* p, SeqDateType x);  //尾删  
void SeqPopFront(SeqList* p, SeqDateType x); //头删
void SeqListInsert(SeqList* p, SeqDateType x);//中间插入
void SeqListErase(SeqList* p, SeqDateType x);//中间删除
void SeqReCapacity(SeqList* p);//扩容函数
void SeqPrint(SeqList* p);//输出数据
void SeqDel(SeqList* p);//恢复初始化
int SeqFind(SeqList* p,SeqDateType x);//查找数据

---

第二步：创建两个源文件，一个用来对函数进行实现，一个是主函数。

                                                               2. 主函数代码

#include "seqlist.h"
void Seqtest1()
{
	SeqList s;
	SeqListInfo(&s); //初始化；     数组传参最好用传地址  
	SeqPushBack(&s,1); //尾插
	SeqPushBack(&s,2);
	SeqPushFront(&s, 0);
	SeqPushBack(&s, 3);
	//SeqPrint(&s);
	//SeqListInsert(&s, 2, 30);//在哪个位置插入多少
	//SeqListErase(&s,3);//在哪个位置删除谁
	SeqPopBack(&s,1);  //尾删几位
	//SeqPrint(&s);
	//SeqPopFront(&s, 2); //头删几位
    SeqPrint(&s);
//	SeqPrint(&s);
	SeqDel(&s);
}
int main()
{
	Seqtest1();
	return 0;
}

---

                                                        3.函数实现的源文件代码

#include "seqlist.h"
//函数的实现
void SeqListInfo(SeqList* p)   //初始化
{
	assert(p);
	p->a = NULL;
	p->size = p->seqcapacity = 0;
}
 
 
 
void SeqDel(SeqList* p) //恢复初始化
{
	free(p->a);
	p->a = NULL;
	p->size = p->seqcapacity = 0;
}
 
 
 
void SeqPrint(SeqList* p)  //打印
{
	assert(p);
	for (int i = 0; i < p->size; i++) 
	{
		printf("%d ", p->a[i]);
	}
	printf("\n");
}
 
 
 
void SeqReCapacity(SeqList* p)  //扩容
{
	assert(p);
		if (p->size == p->seqcapacity)
		{
			SeqDateType newcapacity = p->seqcapacity == 0 ? 4 : p->seqcapacity * 2; //一般开启二倍空间
			SeqDateType* newA = realloc(p->a, sizeof(SeqList) * newcapacity);
			if (newA == NULL)
			{
				printf("Capacity   errno");
				exit(-1);
			}
			p->a = newA; //开辟成功就让原来的a指向新开辟的空间
			p->seqcapacity = newcapacity;
		}
}
 
 
void SeqPushFront(SeqList* p, SeqDateType x) //   头插  从后往前挪动
{
	assert(p);
	SeqReCapacity(p);
	int end = p->size - 1;
	while (end >= 0)
	{
		p->a[end + 1] = p->a[end]; //把前一个数据往后挪动，让a[0]的位置空出来后插入新数据就行
		end--;
	}
	p->a[0] = x;
	p->size++;
}
 
 
void SeqPushBack(SeqList* p, SeqDateType x) //尾插
{
	assert(p); 
	//插入前判断内存够不够，满没满
	SeqReCapacity(p);
	p->a[p->size] = x;  //因为size是表示目前有几个元素，而最后一个元素的下标为size-1，所以
	p->size++;         //新添加元素的时候把元素覆盖到size的位置就行了
}
 
 
void SeqPopBack(SeqList* p,SeqDateType x) //尾删  只需要把最后一个数字删掉就行
{ 
	assert(p);
	assert(p->size > 0); //判读数组中有没有数字
	while (x--)
	{
		--p->size;  //size代表有几个数 所以size--以后 ‘\0'就往前挪动了一个 就相当于把后面的删除了
	}
}
 
void SeqPopFront(SeqList* p, SeqDateType x) //头删    1 2 3 4 5       2
{
	assert(p);
	assert(p->size > 0);
	int input = 0;
	while (x)
	{
		input = 0;
		while (input < p->size-1)
			{
				p->a[input] = p->a[input + 1];
					input++;
			}
		p->size--;
		--x;
	}
}
 
//1 2  30 3 4 5 6
 
 
//这个函数包括了头插 尾插 中间插的三种功能，只需要把这个接口放到其他两个接口里面就行
void SeqListInsert(SeqList* p, SeqDateType pos, SeqDateType x)//pos:插在哪个位置 x:加入哪个数字
{
	assert(p);
	assert(pos > 0 && pos <= p->size);  //pos == p->size的时候 相当于尾插的接口函数，这时候可以把这个函数副用在尾插函数
	SeqReCapacity(p);
	//利用双下标
	int end = p->size - 1;
	while (end>=pos) //取等于是因为要把pos原本的数字移走，让pos位置空出来
	{
		p->a[end + 1] = p->a[end];
		end--;
	}
	p->a[pos] = x; //把插入的数据覆盖在pos上
	p->size++;
}
 
//这个接口包含了头删  中间删  尾删的三种功能
void SeqListErase(SeqList* p, SeqDateType pos)
{
	assert(p);
	assert(pos >= 0 && pos < p->size);
	//利用下标，把pos后面的数往前移动把pos覆盖上就行
	int end = p->a + pos; //数组名=首元素地址 首元素地址+i访问第i个位置
	while (end<=p->size-1)
	{
		p->a[end] = p->a[end + 1];
		end++;
	}
	p->size--;
}

---

                            内容温馨提示：接下来讲解单链表代码的具体实现

                                                        1.自定义头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
 
typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
 
void SListPrint(SLTNode* plist);  //打印
void SListPushBack(SLTNode** pplist,SLTDataType x); //尾插
void SListPushFront(SLTNode** pplist, SLTDataType x);//头插
void SListNweNode(SLTDataType x);//创建新空间  头尾插都需要开辟新空间
void SListPopBack(SLTNode** pplist);//尾删
SLTNode* SListFind(SLTNode* plist,SLTDataType x);//查找
void SListInsertAfter(SLTNode* pos, SLTDataType x);//在POS前面增加数据
 

                                                   2. 主函数代码

#include "SList.h"
 
 
void SList1()
{
	SLTNode* plist = NULL; //因为是链表所以用指针来操作 要是不用指针那就是顺序表了
	SListPushBack(&plist, 1);//
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPrint(plist);
	SListPushFront(&plist,0);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
 
	SLTNode* pos = SListFind(plist,2);//查找
	if (pos)
	{
		printf("该数据存在\n");
	}
	else
	{
		printf("该数据不存在\n");
	}
 
	SListInsertAfter(pos, 30);//在POS后面增加数据
	SListPrint(plist);
	
}
int main()
{
	SList1();
	return 0;
}

                                                 3.函数实现的源文件代码

#include "SList.h"
 
void SListPrint(SLTNode* plist)  //打印链表
{
	SLTNode* cur = plist;
	while (cur != NULL) //判断第一个节点是不是空
	{
		printf("%d->",cur->data);//访问第一个节点的指针域
		cur = cur->next;
	}
 
	printf("NULL\n");
}
 
SLTNode* BuySLTNode(SLTDataType x) //返回个结构体类型的节点 所以返回类型为结构体类型
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	node->data = x;
	node->next = NULL;
	//指针域跟数据域都赋值好  头插就让node->next 指向头节点*pplist就行
	//尾插就让尾部最后一个指针域指向node这个节点就行
	return node;
}
 
 
void SListPushBack(SLTNode** pplist, SLTDataType x)  //尾插
{
	SLTNode* newnode = BuySLTNode(x); //无论头插尾插都要创建节点 所以先创建好
	//判断刚开始的有没有节点
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	//找尾指针
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next != NULL)   //访问下一个节点的指针域
		{
			tail = tail->next;  //指向下一个节点
		}
		tail->next = newnode; //尾指针域存放尾插节点的地址
	}
}
 
 
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x); //无论头插尾插都要创建节点 所以先创建好
	newnode->next = *pplist; //直接让创建的那个新节点的next指向头节点就行，让后再让头节点的指针转到第一位newnode
	*pplist = newnode;
}
 
void SListPopBack(SLTNode** pplist)//尾删
{
	//没有节点
	if (*pplist == NULL)
	{
		return;
	}
	//一个节点
	else if((* pplist)->next == NULL)//如果只有一个节点那么直接释放就行
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLTNode* prev = NULL; //找到尾部前一个节点
		SLTNode* tail = *pplist;//找到尾部的节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail); //释放最后一个节点的空间
		tail = NULL; //把最后一个节点的指针置为空
		prev->next = NULL;//让前一个节点的指针域指向NULL  因为这时候前一个节点已经是最后一个节点了
	}
}
 
SLTNode* SListFind(SLTNode* plist, SLTDataType x)  //查找X的位置
{
	
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;  //返回节点
		}
		cur = cur->next;
	}
 
	return NULL; //没找到或者说*pplist为NULL
}
 
 
void SListInsertAfter(SLTNode* pos, SLTDataType x)//在POS后面增加数据
{
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* cur = pos->next;
	//newnode->next = pos->next;
	//pos->next = newnode;
 
	pos->next = newnode;
	newnode->next = cur;
}