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

顺序表的改进

问题：
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);}

运行结果