数据结构__顺序表和单链表

顺序表的改进

问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看

扩容分为：原抵扩容，异地扩容

寻求解决方案

1、不扩容

2、按需求申请释放（内存释放需要申请多少还多少）

3、解决头部/中间插入删除需要挪动数据问题

问题的根源是顺序表是一块连续的物理空间

所以要用多少开多少，并且不能是连续的空间，所以需要管理每一块空间方便访问

单链表的建立

逻辑结构：方便理解想象出来的

物理结构：实际存在的真实的样子

SList.h

#pragma once
#include<stdio.h>
typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;//内容
	struct SListNode* next;//节点
}SLTNode;

void SLPrint(SLTNode* phead);

SList.cpp

#include"SList.h"
//打印
void SLPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf(" % d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

逻辑结构

物理结构

newnode->next = phead;
phead = newnode;

这两句话实现的功能

void SLPushFront(SLTNode* phead, SLDataType x)
{
	//开辟空间
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟空间失败报错
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	newnode->next = phead;
	phead = newnode;
}

 一级指针，二级指针，解引用

一级指针只能控制调用里面的内容
二级指针可以控制调用指针

*取内容/定义指针

&取地址

void Swap(int* p1, int* p2)
{
	//*p表示的里面的内容
	//实现内容的交换
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//int* 类型的指针
//*pp1是pp1指针的内容，它的类型是int*

void Swap1(int* *pp1, int* *pp2)
{
	//*p表示的里面的内容
	//实现内容的交换
	int* tmp = *pp1;
	*pp1 = *pp2;
	*pp2 = tmp;
}
int main()
{
	int a = 0, b = 1;
	Swap(&a, &b);

//&a:取指针px的地址
	int *px = &a, * py = &b;
//不会改变px，py	
//Swap(px, py);
	Swap1(&px,&py);
	
	return 0;
}

在链表中的使用

需要用二级指针

函数声明

void SLPrint(SLTNode* phead);
//因为要改变结构体的指针，所以需要用二级指针
//一级指针只能控制调用里面的内容
//二级指针可以控制调用指针
void SLPushFront(SLTNode* *pphead, SLDataType x);

函数定义

//需要用二级指针，因为需要使用指针，所以要用二级指针控制指针
void SLPushFront(SLTNode* *pphead, SLDataType x)
{
	//开辟空间，空间存放指针和data内容
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//开辟空间失败报错
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	newnode->next = *pphead;
	*pphead = newnode;
}

测试用例

void TestSList1()
{
	SLTNode* plist = NULL;
	//要改变结构体的指针，所以要用结构体指针的地址
	SLPushFront(&plist, 1);
	SLPushFront(&plist, 2);
	SLPushFront(&plist, 3);
	SLPushFront(&plist, 4);
	SLPrint(plist);

}

运行结果