2021-09-08

2024-03-13 13:19:39

线性表

线性表中的数据元素可以是各种各样的，但同一线性表中元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。（唯一的头，唯一的尾，除头之外，其他节点都有唯一的前驱，除尾之外，其他节点都有唯一的后继。）
线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。
线性表有两种数据结构表现形式：

  1. 顺序表 （逻辑相邻，物理上也相邻） 是一种权限更多的数组
  2. 链表 （逻辑相邻，物理上不一定相邻）

时间复杂度：语句与问题规模之间的函数关系
经常遇见的时间复杂度：

  1. O（1） 没有循环， 要么有循环但是循环退出条件和问题规模之间没有关系——循环次数是一个常数
  2. O（n） 有循环，并且循环的次数与问题规模之间有关系（控制循环的变量每次+1或-1来执行）
  3. O（n^2）循环嵌套
  4. O（log n）有循环,并且循环次数与问题规模之间有关系（控制循环变量每次*2或者/2来执行）

空间复杂度：函数所需要的的额外（除函数数据计算本身的存储空间之外）的存储空间与问题规则之间的函数关系

时间复杂度的省略（渐变）规则：

  1. 只要最高项
  2. 不要系数

顺序表（需要挪动数据）

顺序表的特点：
1.很简单 好理解；
2.随机访问数据的时间复杂度为O（1）
3.插入数据的时候时间复杂度为O（n) 尾插的时候时间复杂度为O（1）
4.删除数据的时候时间复杂度为O(n) 尾删的时候时间复杂度为O（1）
为啥有这些特点：因为顺序表的数据之间，逻辑上相邻，物理上也相邻

定长顺序表
2021-09-08
2021-09-08
sqlist.h


//放函数的声明以及结构体的定义
#pragma once//防止头文件重复

//顺序表  定长的顺序表  10

typedef struct SQlist
{
	int data[10];
	int length;
}SQList, * PSQlist;

//typedef SQlist *PSQlist;

//增删改查
void Init_SQlist(PSQlist ps);//PSQlist == SQlist*   初始化
bool Insert(PSQlist ps, int pos, int val);//按位置插入值w为val
bool Del_pos(PSQlist ps, int pos);//按位置删除
bool Del_val(PSQlist ps, int val);//按值删除
bool IsEmpty(PSQlist ps);//判空
bool IsFull(PSQlist ps);//判满
int Get_Length(PSQlist ps);//获取有效长度
void Clear(PSQlist ps);//清空
void Destroy(PSQlist ps);//销毁
void Show(PSQlist ps);//打印

sqlist.cpp

#include <stdio.h>
#include <assert.h>
#include "sqlist.h"


void Init_SQlist(PSQlist ps)//PSQlist == SQlist*
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return;
	}

	//ps->data 数据域不需要初始化
	ps->length = 0;
}

bool Insert(PSQlist ps, int pos, int val)
{
	assert(ps != NULL && 0 <= pos && pos <= ps->length);
	if (ps == NULL || pos<0 || pos>ps->length)
	{
		return false;
	}

	if (IsFull(ps))
	{
		return false;
	}

	//挪动数据，将插入位置空出来
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->data[i + 1] = ps->data[i];
	}

	//把值插进去
	ps->data[pos] = val;
	ps->length++;
	return true;
}

bool Del_pos(PSQlist ps, int pos)
{
	assert(ps != NULL && pos >= 0 && pos < ps->length);
	if (ps == NULL || pos < 0 || pos >= ps->length)
	{
		return false;
	}

	if (IsEmpty(ps))
	{
		return false;
	}

	//将数据向前覆盖
	for (int i = pos + 1; i < ps->length; i++)
	{
		ps->data[i - 1] = ps->data[i];
	}

	ps->length--;
	return true;
}

bool Del_val(PSQlist ps, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}

	if (IsEmpty(ps))
	{
		return false;
	}

	//遍历一边，要删除的val存在与否
	int tmp = -1;
	for (int i = 0; i < ps->length; i++)
	{
		if (ps->data[i] == val)
		{
			tmp = i;
			break;
		}
	}
	if (tmp == -1)
	{
		return false;
	}
	//调用上一步写好的函数（按位置删除）
	Del_pos(ps, tmp);//这一个函数已经将length--了，所以不在需要length--

	return true;
}

bool IsEmpty(PSQlist ps)
{	
	assert(ps != NULL);
	return ps->length == 0;
}

bool IsFull(PSQlist ps)
{
	assert(ps != NULL);
	return ps->length == 10;
}

int Get_Length(PSQlist ps)
{
	assert(ps != NULL);
	return ps->length;
}

void Clear(PSQlist ps)
{
	assert(ps != NULL);
	ps->length = 0;
}

void Destroy(PSQlist ps)
{
	assert(ps != NULL);
	Clear(ps);
}


void Show(PSQlist ps)
{
	assert(ps != NULL);

	for (int i = 0; i < ps->length; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

不定长顺序表
扩容：
1.5倍在某一刻，我们可以将前面不要的空间利用上
2倍 则不可以
vs用的扩容规则 1.5
gcc 用的扩容规则 2
DSQlist.h

#pragma once
//定长顺序表 简单 不实用    sqlist=sequence list

#define INIT_SIZE 10

typedef struct DSQlist
{
	int* data;//数据域 用来承接malloc申请来的空间
	int length;//有效长度个数
	int listsize;//总的空间大小（简单理解总的格子数）
}DSQlist,*PDSQlist;

//关于顺序表的增删改查

//初始化函数
void Init_list(PDSQlist ps);

//插入数据 按pos插入
bool Insert(PDSQlist ps, int pos, int val);

//删除数据 按位置删除 pos
bool Del_pos(PDSQlist ps, int pos);

//删除数据 按值删除 val
bool Del_val(PDSQlist ps, int val);

//查找 找到值为val的第一个元素 返回其下标 没有找到 返回-1
int Search(PDSQlist ps, int val);

//判空
bool IsEmpty(PDSQlist ps);

//判满
bool IsFull(PDSQlist ps);

//扩容
void Inc(PDSQlist ps);

//清空
void Clear(PDSQlist ps);

//销毁
void Destroy(PDSQlist ps);

//打印
void Show(PDSQlist ps);
//获取长度
int Get_length(PDSQlist ps);

DSQlist.cpp

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"DSQlist.h"

//关于顺序表的增删改查
//初始化函数
void Init_list(PDSQlist ps)
{
	assert(ps!= NULL);
	if (ps == NULL)
	{
		return;
	}
	ps->data = (int*)malloc(sizeof(int) * INIT_SIZE);
	assert(ps->data != NULL);

	ps->length = 0;
	ps->length = INIT_SIZE;
}

//插入数据 按pos插入
bool Insert(PDSQlist ps, int pos, int val)
{
	assert(ps!= NULL);
	//判断插入位置的合法性
	if (pos<0 || pos>ps->length)
	{
		return false;
	}
	//如果满了 则扩容
	if (IsFull(ps))
	{
		Inc(ps);
	}
	//挪动数据 把插入位置空间 空出来
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->data[i + 1] = ps->data[i];
	}
	//把值放进去
	ps->data[pos] = val;
	//有效长度length++
	ps->length++;
	return true;
}

//删除数据 按位置删除 pos
bool Del_pos(PDSQlist ps, int pos)
{
	assert(ps!= NULL);
	//判断删除位置pos的合法性
	if (pos < 0 || pos >= ps->length)
	{
		return false;
	}
	//如果空 就不允许删除操作  可以不写
	
	//挪动数据 往前覆盖
	for (int i = pos; i + 1 <=ps->length; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	//有效长度ps->length--
	ps->length--;
		return true;
}

//删除数据 按值删除 val
bool Del_val(PDSQlist ps, int val)
{
	assert(ps!= NULL);
	//通过函数Search来找val的下标
	int i = Search(ps, val);
	if (i == -1)//如果i=-1 代表没找到 则直接退出
	{
		return false;
	}
	//找到 则直接调用按位置pos删除函数 即可   ps->length 不需要减减 因为调用的函数已经减减过了
	Del_pos(ps, i);
	return true;
}

//查找 找到值为val的第一个元素 返回其下标 没有找到 返回-1
int Search(PDSQlist ps, int val)
{
	assert(ps!= NULL);
	for (int i = 0; i < ps->length; i++)
	{
		if (val == ps->data[i])
		{
			return i;
		}
	}
	return -1;
}

//判空
bool IsEmpty(PDSQlist ps)
{
	assert(ps!= NULL);
	return ps->length ==0;
}

//判满
bool IsFull(PDSQlist ps)
{
	assert(ps!= NULL);
	return ps->length == ps->listsize;
}

//扩容  按两倍扩容
void Inc(PDSQlist ps)
{
	assert(ps!= NULL);
	//malloc realloc calloc
	ps->data = (int*)realloc(ps->data, sizeof(int) * ps->listsize * 2);
	assert(ps->data != NULL);
	//ps->length;  不需要修改
	ps->listsize *= 2;
}

//清空
void Clear(PDSQlist ps)
{
	assert(ps!= NULL);
	ps->length = 0;
}

//销毁
void Destroy(PDSQlist ps)
{
	assert(ps!= NULL);
	free(ps->data);
	ps->data = NULL;
	ps->length = 0;
	ps->listsize = 0;
}

//打印
void Show(PDSQlist ps)
{
	assert(ps!= NULL);
	for (int i = 0; i < ps->length; i++)
	{
		printf("%d", ps->data[i]);
	}
	printf("\n");
}


int Get_length(PDSQlist ps)
{
	assert(ps!= NULL);
	int count = 0;
	for (int i = 0; i < ps->length; i++)
	{
		count++;
	}
	return count;
}

***单链表***有两种实现方式：

  1. 带头结点 （简单，实现简单，理解也简单）
  2. 不带头结点（头指针，难，因为会出现二级指针，不好实现，也不好理解）

2021-09-08
2021-09-08
找合适的位置：
for(p=plist;p->next!=NULL;p=p->next);//1 需要前驱，经常用于插入和删除操作等等
for(p=plist->next;p!=NULL;p=p->next);//2 不需要前驱,经常用于打印，查找
插入操作 两行代码 1.pnewnode->next=p->next;2.p->next=pnewnode;//pnewnode新节点的名字 p是插入位置
删除操作 三行代码 1.Node* q = p->next;//申请一个新指针，指向要删除的节点
2.p->next = q->next;让删除结点的上一个结点
3.free(q); //p指向删除结点的上一个节点，q指向删除节点

想通过子函数去影响父函数，必须有取地址操作并且还得有解引用操作（取地址和解引用缺一不可。

list.h

#pragma once
typedef int ELEMTYPE;

typedef struct Node
{
	ELEMTYPE data;//数据域  保存其数据本身
	struct Node* next;//指针域  指向下一个数据节点的地址
}Node, * PNode;

//增删改查

//初始化
void Init_list(Node* plist);//Node * == PNode

//头插
bool Insert_head(PNode plist, int val);

//尾插
bool Insert_tail(PNode plist, int val);

//按位置插入  pos  
bool Insert_pos(PNode plist, int pos, int val);

//按位置删除 pos 
bool Del_pos(PNode plist, int pos);

//按值删除 遇到值为val的第一个有效节点 删除掉 释放其内存
bool Del_val(PNode plist, int val);

//查找search 查找值我val的第一个节点，返回其地址
struct Node* Search(PNode plist, int val);

//寻找值为val的节点的前驱
Node* Get_prior(PNode plist, int val);

//寻找值为val的节点的后继
Node* Get_next(PNode plist, int val);

//判空
bool IsEmpty(PNode plist);

//判满
bool IsFull(PNode plist);

//获取其有效值长度
int Get_length(PNode plist);

//清空
void Clear(PNode plist);

//销毁
void Destroy(PNode plist);

//打印
void Show(PNode plist);

list.cpp

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include "list.h"

//初始化
void Init_list(Node* plist)//Node * == PNode
{
	assert(plist != NULL);
	if (plist == NULL)
		return;

	//plist->data; 不需要初始化， 因为没有使用，直接浪费掉了
	plist->next = NULL;
}

//头插
bool Insert_head(PNode plist, int val)
{
	assert(plist != NULL);
	//申请新节点
	Node* pnewnode = (Node*)malloc(sizeof(Node) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;
	//pnewnode->next = NULL; 这里不需要初始化， 因为接下来就会对其重新赋值

	//直接插入 1 2 顺序不能反
	pnewnode->next = plist->next;//1
	plist->next = pnewnode;//2
	return true;
}

//尾插
bool Insert_tail(PNode plist, int val)
{
	assert(plist != NULL);
	
	//1.创建新结点
	Node* pnewnode = (Node*)malloc(sizeof(Node));
	assert(pnewnode != NULL);
	pnewnode->data = val;
	//2.找到合适的插入位置
	Node* p = plist;
	for (p = plist; p->next != NULL; p = p->next);//让for循环跑完，p刚好指向最后一个有效节点

	//3.插入
	pnewnode->next = p->next;
	p->next = pnewnode;

}

//按位置插入  pos  
bool Insert_pos(PNode plist, int pos, int val)
{
	assert(plist != NULL);
	//创建新结点
	Node* pnewnode = (Node*)malloc(sizeof(Node) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;

	//找合适的插入位置 根据pos
	Node* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//插入
	pnewnode->next = p->next;//新节点的next域赋值为之前上一个结点的next（保证后面的结点不丢失）
	p->next = pnewnode;//让前驱结点的next指向新节点
	return true;

}

//按位置删除 pos 
bool Del_pos(PNode plist, int pos)
{
	assert(plist != NULL);
	if(pos<0||pos>=Get_length(plist))
	{
		return false;
	}
	//1.找到删除结点的上一个结点
	Node* p = plist;
	for (int i = 0; i < pos; i++)
	{
		p = p->next;
	}
	//2.删除要删除的结点
	Node* q = p->next;//申请一个新指针，指向要删除的节点
	p->next = q->next;//p->next=p->next->next;//让删除结点的上一个结点的next指向删除结点的下一个节点的结点
	free(q);//释放要删除的结点
	return true;
}

//按值删除 遇到值为val的第一个有效节点 删除掉 释放其内存
bool Del_val(PNode plist, int val)
{
	assert(plist != NULL);
	Node* p = Get_prior(plist, val);
		if (p == NULL)
		{
			return false;
		}
		Node* q = p->next;
		p->next = q->next;
		free(q);
		return true;
}

//查找search 查找值我val的第一个节点，返回其地址
struct Node* Search(PNode plist, int val)
{
	assert(plist != NULL);
	//遍历一遍单链表，找值为val的结点，将其地址返回
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		if (p->data == val) //判断当前节点的数据域是否为val
		{
			return p;
		}
	}
	return NULL;
}

//寻找值为val的节点的前驱
Node* Get_prior(PNode plist, int val)
{
	assert(plist != NULL);
	Node* p = plist;
	for (p; p->next!= NULL; p = p->next)
	{
		if (p->next->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//寻找值为val的节点的后继
Node* Get_next(PNode plist, int val)
{
	Node* p = Search(plist, val);
	if (p == NULL)
	{
		return NULL;
	}
	return p->next;
}

//判空
bool IsEmpty(PNode plist)
{
	return plist->next == NULL;
}

//判满
//bool IsFull(PNode plist) ; 单链表不存在判满操作

//获取其有效值长度
int Get_length(PNode plist)
{
	int count = 0;
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		count++;
	}
	return count;
}

//清空
//单链表的清空，和销毁实现方式一样，都是将malloc来的结点全部释放掉
void Clear(PNode plist)
{
	Destroy(plist);
}

//销毁
void Destroy(PNode plist)//一直头删
{
	assert(plist != NULL);
	while (plist->next != NULL)//每次判断第一个有效节点是否存在
	{
		Node* p = plist->next;
		plist->next = p->next;
		free(p);
	}
	plist->next = NULL;//此时没有有效结点，那么将plist->next置为空
}

void Destroy2(PNode plist)
{
	assert(plist != NULL && plist->next != NULL);
	Node* p = plist->next;
	Node* q;
	plist->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
}
//打印
void Show(PNode plist)
{
	for (Node* p = plist->next; p != NULL; p = p->next)
	{
		printf("%d", p->data);
	}
	printf("\n");
}

顺序表：逻辑相邻，物理相邻
随机访问时间复杂度O（1）
插入时间复杂度O（n） 尾插的时间复杂度O（1）
删除时间复杂度O（n） 尾删的时间复杂度O（1）
查找search时间复杂度O（n）
单链表：逻辑相邻，物理不一定相邻
随机访问时间复杂度O（n）
插入的时间复杂度O（1） 不需要挪动数据
删除的时间复杂度O（1） 不需要挪动数据
查找search时间复杂度O（n）
如果经常访问节点，不经常插入和删除结点 选顺序表
如果经常插入和删除结点，不经常访问结点 选单链表

上一篇：数据结构-单链表基本操作带图完整详解


下一篇：基础数据结构---顺序表（链式结构）