开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构学习笔记（数据结构概念、顺序表的增删查改等）详细整理 -> 正文阅读

[数据结构与算法]数据结构学习笔记（数据结构概念、顺序表的增删查改等）详细整理

数据结构概念

1.什么是数据结构？
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
2.什么是算法？
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
3.算法效率
算法效率分析分为两种：第一种是时间效率，第二种是空间效率。
时间复杂度：算法中的基本操作的执行次数，为算法的时间复杂度。
空间复杂度：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
实际中我们计算时间和空间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组存储。
线性表每个元素必须有前驱和后继

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

动态顺序表接口实现

**1.顺序表初始化**

// An highlighted block
void SeqListInit(SeqList *pst, size_t capacity)
{
	pst->capacity = capacity;
	pst->base = (ElemType*)malloc(sizeof(ElemType) * pst->capacity);
	assert(pst->base != NULL);
	memset(pst->base, 0, sizeof(ElemType)*pst->capacity);
	pst->size = 0;
}

**2.尾插**

在这里插入图片描述

// An highlighted block
void SeqListPushBack(SeqList *pst, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}
	pst->base[pst->size++] = v;
}

**头插**

在这里插入图片描述

// An highlighted block
void SeqListPushFront(SeqList *pst, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}
	//移动数据
	for(int i=pst->size; i>0; --i)
	{
		pst->base[i] = pst->base[i-1];
	}
	//插入数据
	pst->base[0] = v;
	pst->size++;
}

**3.存储数据显示**

// An highlighted block
void SeqListShow(SeqList *pst)
{
	for(int i=0; i<pst->size; ++i)
		printf("%d ", pst->base[i]);
	printf("\n");
}

**4.尾删**

// An highlighted block
void SeqListPopBack(SeqList *pst)
{
	if(_IsEmpty(pst))
	{
		printf("顺序表已空，不能删除.\n");
		return;
	}
	//删除数据
	pst->size--;
}

**5.头删**

在这里插入图片描述

// An highlighted block
void SeqListPopFront(SeqList *pst)
{
	if(_IsEmpty(pst))
	{
		printf("顺序表已空，不能删除.\n");
		return;
	}
	 //将顺序表中的数据前移一位(第一个数据除外)
	for(int i=0; i<pst->size-1; ++i)
		pst->base[i] = pst->base[i+1];
	//将size值减1，来达到删除的目的
	pst->size--;
}

**6.按位置插入数据**

在这里插入图片描述

// An highlighted block
void SeqListInsertByPos(SeqList *pst, int pos, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}
	//判断顺序表空间是否满且增加空间是否失败？
	if(pos<0 || pos>pst->size)
	{
		printf("插入的位置非法， %d 不能插入.\n", v);
		return;
	}
	//将该位置及其之后的数据都向后移动一位并插入数据
	for(int i=pst->size; i>pos; --i)
		pst->base[i] = pst->base[i-1];
	pst->base[pos] = v;
	pst->size++;
}

**7.按值插入**

// An highlighted block
void SeqListInsertByVal(SeqList *pst, ElemType v)
{
	//寻找插入的位置
	int pos = 0;
	while(pos<pst->size &&  v>pst->base[pos])
		pos++;

	//插入数据
	SeqListInsertByPos(pst, pos, v);
}
void SeqListEraseByPos(SeqList *pst, int pos)
{
	//检查位置
	if(pos<0 || pos>=pst->size)
	{
		printf("删除的位置非法，不能删除数据.\n");
		return;
	}
	//删除数据
	for(int i=pos; i<pst->size-1; ++i)
		pst->base[i] = pst->base[i+1];
	pst->size--;
}

**8.按位置删除**

在这里插入图片描述

// An highlighted block
void SeqListEraseByPos(SeqList *pst, int pos)
{
	//检查位置
	if(pos<0 || pos>=pst->size)
	{
		printf("删除的位置非法，不能删除数据.\n");
		return;
	}
	// //将该位置之后的数据都向前移动一位 删除数据
	for(int i=pos; i<pst->size-1; ++i)
		pst->base[i] = pst->base[i+1];
	pst->size--;
}

**9.按值删除**

// An highlighted block
void SeqListEraseByVal(SeqList *pst, ElemType key)
{
	//查找关键值
	int pos = SeqListFindByVal(pst, key);
	//顺序表中是否存在该值？
	if(pos == -1)
	{
		printf("要删除的数据不存在.\n");
		return;
	}
	//删除数据
	SeqListEraseByPos(pst, pos);
}

**10.按位置查找**      **11按值查找**

// An highlighted block
ElemType SeqListFindByPos(SeqList *pst, int pos)
{
	//检查位置
	assert(pos>=0 && pos<pst->size);
	return pst->base[pos];
}

int SeqListFindByVal(SeqList *pst, ElemType key)
{
    //遍历顺序表，查找数据
	for(int i=0; i<pst->size; ++i)
	{
		if(key == pst->base[i])
			return i;//找到数据返回
	}
	return -1;
}

**12.排序**

// An highlighted block
void SeqListSort(SeqList *pst)
{
    //冒泡排序，每趟比较可以确定一个最大(最小)的数，所以需要size-1趟(最后一次自己跟自己比较不需要)
	for(int i=0; i<pst->size-1; ++i)
	{
		bool is_swap = false;
		//每趟中需要比较size-i-1次(前面比较完的i个数不需要重复比较，最后一次自己跟自己比较不需要)
		for(int j=0; j<pst->size-i-1; ++j)
		{
			if(pst->base[j] > pst->base[j+1])
			{
				Swap(&(pst->base[j]), &(pst->base[j+1]));
				is_swap = true;
			}
		}
		if(!is_swap)  //没有交换过数据
			break;
	}
}

**13.逆置**

// An highlighted block
void SeqListReverse(SeqList *pst)
{
	int left = 0;
	int right = pst->size-1;

	while(left < right)
	{
		Swap(&(pst->base[left]), &(pst->base[right]));
		left++;
		right--;
	}
}

**14.顺序表长度**

// An highlighted block
size_t SeqListLength(SeqList *pst)
{
	return pst->size;
}

**15.顺序表容量   16.清楚** 17.摧毁

// An highlighted block
size_t SeqListCapacity(SeqList *pst)
{
	return pst->capacity;
}
//清除
void SeqListClear(SeqList *pst)
{
	pst->size = 0;
}
//摧毁
void SeqListDestroy(SeqList *pst)
{
	free(pst->base);
	pst->base = NULL;
	pst->capacity = pst->size = 0;
}

我们一开始设置了顺序表的大小，但是容量是有限的，当插入数据超过这个容量时候就插不进去了，当然也不能一开始就设定很大的容量，这样会导致空间的浪费，因此需要让它根据需要动态的去扩容。

**容量扩展**

// An highlighted block
//空间不足，重新开辟
bool _Inc(SeqList *pst)
{
	pst->base = (ElemType *)realloc(pst->base, sizeof(ElemType) * (pst->capacity+INC_SIZE));
	//空间开辟是否失败？
	if(pst->base == NULL)
	    return false;
	pst->capacity += INC_SIZE;
	    return true;
}
    bool _IsFull(SeqList *pst)
{
        return pst->size >= pst->capacity;
}
    bool _IsEmpty(SeqList *pst)
{
        return pst->size == 0;
}

动态顺序表接口扩展

删除排序数组中的重复项

合并两个有序数组

动态顺序表的优缺点

优点：
无需为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速地存取
表中任一位置的元素。
缺点：
插入删除操作需要移动大量元素当线性表长度变化较大时，难以确定存储空间的容量
造成存储空间的碎片。

完整代码

**main.c**

// An highlighted block
#include"SeqList.h"
int main(int argc, char *argv[])
{
	SeqList mylist;
	SeqListInit(&mylist, 8);
	ElemType item, value, key;
	int pos;
	int select = 1;
	while(select)
	{
		printf("********************************************\n");
		printf("* [1] push_back           [2] push_front   *\n");
		printf("* [3] show_list           [0] quit_system  *\n");
		printf("* [4] pop_back            [5] pop_front    *\n");
		printf("* [6] insert_pos          [7] insert_val   *\n");
		printf("* [8] erase_pos           [9] erase_val    *\n");
		printf("* [10] find_pos           [11] find_val    *\n");
		printf("* [12] sort               [13] reverse     *\n");
		printf("* [14] length             [15] capacity    *\n");
		printf("* [16] clear              [*17] destroy    *\n");
		printf("********************************************\n");
		printf("请选择:>");
		scanf("%d", &select);
		if(select == 0)
			break;

		switch(select)
		{
		case 1:
			printf("请输入要插入的数据<以-1结束>:>");
			while(scanf("%d", &item), item!=-1)
			{
				SeqListPushBack(&mylist, item);
			}
			break;
		case 2:
			printf("请输入要插入的数据<以-1结束>:>");
			while(scanf("%d", &item), item!=-1)
			{
				SeqListPushFront(&mylist, item);
			}
			break;
		case 3:
			SeqListShow(&mylist);
			break;
		case 4:
			SeqListPopBack(&mylist);
			break;
		case 5:
			SeqListPopFront(&mylist);
			break;
		case 6:
			printf("请输入要插入的位置:>");
			scanf("%d", &pos);
			printf("请输入要插入的值:>");
			scanf("%d", &item);
			SeqListInsertByPos(&mylist, pos, item);
			break;
		case 7:
			printf("请输入要插入的值:>");
			scanf("%d", &item);
			SeqListInsertByVal(&mylist, item);
			break;
		case 8:
			printf("请输入要删除的位置:>");
			scanf("%d", &pos);
			SeqListEraseByPos(&mylist, pos);
			break;
		case 9:
			printf("请输入要删除的值:>");
			scanf("%d", &key);
			SeqListEraseByVal(&mylist, key);
			break;
		case 10:
			printf("请输入要查找的位置:>");
			scanf("%d", &pos);
			value = SeqListFindByPos(&mylist, pos);
			printf("在%d位置的值为:> %d\n", pos, value);
			break;
		case 11:
			printf("请输入要查找的值:>");
			scanf("%d", &key);
			pos = SeqListFindByVal(&mylist, key);
			if(pos == -1)
				printf("要查找的%d数据不存在.\n", key);
			else
				printf("要查找的数据%d在 %d位置.\n", key, pos);
			break;
		case 12:
			SeqListSort(&mylist);
			break;
		case 13:
			SeqListReverse(&mylist);
			break;
		case 14:
			printf("顺序表的长度为:> %d\n", SeqListLength(&mylist));
			break;
		case 15:
			printf("顺序表的容量为:> %d\n", SeqListCapacity(&mylist));
			break;
		case 16:
			SeqListClear(&mylist);
			break;
		default:
			break;
		}
	}

	SeqListDestroy(&mylist);
	printf("GoodBye.\n");
	return 0;
}

**seqlist.h**

// An highlighted block
#ifndef _SEQ_LIST_H_
#define _SEQ_LIST_H_

#include"Common.h"

#define INC_SIZE 3

//数据结构的定义
typedef struct SeqList
{
	ElemType *base;
	size_t    capacity;
	size_t    size;
}SeqList;

//函数声明
bool _Inc(SeqList *pst);
bool _IsFull(SeqList *pst);
bool _IsEmpty(SeqList *pst);
//--------------------------------------------------
void SeqListInit(SeqList *pst, size_t capacity);
void SeqListPushBack(SeqList *pst, ElemType v);
void SeqListPushFront(SeqList *pst, ElemType v);
void SeqListPopBack(SeqList *pst);
void SeqListPopFront(SeqList *pst);
void SeqListEraseByPos(SeqList *pst, int pos);
void SeqListEraseByVal(SeqList *pst, ElemType key);
void SeqListInsertByPos(SeqList *pst, int pos, ElemType v);
void SeqListInsertByVal(SeqList *pst, ElemType v);
size_t SeqListCapacity(SeqList *pst);
size_t SeqListLength(SeqList *pst);

ElemType SeqListFindByPos(SeqList *pst, int pos);
int SeqListFindByVal(SeqList *pst, ElemType key);

void SeqListSort(SeqList *pst);
void SeqListReverse(SeqList *pst);

void SeqListClear(SeqList *pst);
void SeqListDestroy(SeqList *pst);
void SeqListShow(SeqList *pst);

//函数实现
bool _Inc(SeqList *pst)
{
	pst->base = (ElemType *)realloc(pst->base, sizeof(ElemType) * (pst->capacity+INC_SIZE));
	if(pst->base == NULL)
		return false;
	pst->capacity += INC_SIZE;
	return true;
}
bool _IsFull(SeqList *pst)
{return pst->size >= pst->capacity;}
bool _IsEmpty(SeqList *pst)
{return pst->size == 0;}

void SeqListInit(SeqList *pst, size_t capacity)
{
	pst->capacity = capacity;
	pst->base = (ElemType*)malloc(sizeof(ElemType) * pst->capacity);
	assert(pst->base != NULL);
	memset(pst->base, 0, sizeof(ElemType)*pst->capacity);
	pst->size = 0;
}

void SeqListPushBack(SeqList *pst, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}

	pst->base[pst->size++] = v;
}

void SeqListPushFront(SeqList *pst, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}

	//移动数据
	for(int i=pst->size; i>0; --i)
	{
		pst->base[i] = pst->base[i-1];
	}
	//插入数据
	pst->base[0] = v;
	pst->size++;
}

void SeqListPopBack(SeqList *pst)
{
	if(_IsEmpty(pst))
	{
		printf("顺序表已空，不能删除.\n");
		return;
	}

	//删除数据
	pst->size--;
}

void SeqListPopFront(SeqList *pst)
{
	if(_IsEmpty(pst))
	{
		printf("顺序表已空，不能删除.\n");
		return;
	}

	for(int i=0; i<pst->size-1; ++i)
		pst->base[i] = pst->base[i+1];
	pst->size--;
}

void SeqListInsertByPos(SeqList *pst, int pos, ElemType v)
{
	//检查容量
	if(_IsFull(pst) && !_Inc(pst))
	{
		printf("顺序表容量不足，%d 不能插入.\n", v);
		return;
	}

	//检查位置
	if(pos<0 || pos>pst->size)
	{
		printf("插入的位置非法， %d 不能插入.\n", v);
		return;
	}

	//插入数据
	for(int i=pst->size; i>pos; --i)
		pst->base[i] = pst->base[i-1];
	pst->base[pos] = v;
	pst->size++;
}

void SeqListInsertByVal(SeqList *pst, ElemType v)
{
	//寻找插入的位置
	int pos = 0;
	while(pos<pst->size &&  v>pst->base[pos])
		pos++;

	//插入数据
	SeqListInsertByPos(pst, pos, v);
}

void SeqListEraseByPos(SeqList *pst, int pos)
{
	//检查位置
	if(pos<0 || pos>=pst->size)
	{
		printf("删除的位置非法，不能删除数据.\n");
		return;
	}

	//删除数据
	for(int i=pos; i<pst->size-1; ++i)
		pst->base[i] = pst->base[i+1];
	pst->size--;
}

void SeqListEraseByVal(SeqList *pst, ElemType key)
{
	//查找关键值
	int pos = SeqListFindByVal(pst, key);
	if(pos == -1)
	{
		printf("要删除的数据不存在.\n");
		return;
	}

	//删除数据
	SeqListEraseByPos(pst, pos);
}

ElemType SeqListFindByPos(SeqList *pst, int pos)
{
	//检查位置
	assert(pos>=0 && pos<pst->size);
	return pst->base[pos];
}

int SeqListFindByVal(SeqList *pst, ElemType key)
{
	for(int i=0; i<pst->size; ++i)
	{
		if(key == pst->base[i])
			return i;
	}
	return -1;
}

size_t SeqListLength(SeqList *pst)
{
	return pst->size;
}
size_t SeqListCapacity(SeqList *pst)
{
	return pst->capacity;
}

void SeqListClear(SeqList *pst)
{
	pst->size = 0;
}

void SeqListSort(SeqList *pst)
{
	for(int i=0; i<pst->size-1; ++i)
	{
		bool is_swap = false;

		for(int j=0; j<pst->size-i-1; ++j)
		{
			if(pst->base[j] > pst->base[j+1])
			{
				Swap(&(pst->base[j]), &(pst->base[j+1]));
				is_swap = true;
			}
		}

		if(!is_swap)  //没有交换过数据
			break;
	}
}

void SeqListReverse(SeqList *pst)
{
	int left = 0;
	int right = pst->size-1;

	while(left < right)
	{
		Swap(&(pst->base[left]), &(pst->base[right]));
		left++;
		right--;
	}
}

void SeqListDestroy(SeqList *pst)
{
	free(pst->base);
	pst->base = NULL;
	pst->capacity = pst->size = 0;
}

void SeqListShow(SeqList *pst)
{
	for(int i=0; i<pst->size; ++i)
		printf("%d ", pst->base[i]);
	printf("\n");
}
#endif /* _SEQ_LIST_H_ */;

**common.h**

// An highlighted block
#ifndef _COMMON_H_
#define _COMMON_H_

//预防头文件的重复引入
//#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<vld.h>  //内存泄漏的检测工具

#define ElemType int
void Swap(ElemType *a, ElemType *b)
{
	ElemType tmp = *a;
	*a = *b;
	*b = tmp;
}
#endif /* _COMMON_H_ */;

其他问题

内存泄漏检测工具需要将安装vld插件
库函数为：#include<vld.h>

#ifndef +名称与#endif+名称是预防头文件的重复引入的操作。
用#pragma once也可以。
其实“被重复引用”是指一个头文件在同一个cpp文件中被include了多次，这种错误常常是由于include嵌套造成的。比如：存在a.h文件#include "c.h"而此时b.cpp文件导入了#include “a.h” 和#include "c.h"此时就会造成c.h重复引用。
头文件被重复引用引起的后果：
有些头文件重复引用只是增加了编译工作的工作量，不会引起太大的问题，仅仅是编译效率低一些，但是对于大工程而言编译效率低下那将是一件多么痛苦的事情。有些头文件重复包含，会引起错误，比如在头文件中定义了全局变量(虽然这种方式不被推荐，但确实是C规范允许的)这种会引起重复定义。