数据结构的基础概念

重要观念

在学习数据结构之前，必须先清晰的树立一个观念，它对于你能够在这条路上走多远尤为重要。
一个重要观念：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就成为了重要问题。
要知道，能够在小量数据下工作的程序（往往是for循环嵌套，耗时极多），在面对巨大数据集时往往是不切实际的。例如找出上百万个数据中第x个大的数，用简单的冒泡排序等算法，往往要花费数天，这是不现实的。因此需要更好的算法，并掌握一些能力，使得我们可以优化我们的代码。
要掌握的能力：
1/写出一个程序后，能在尚未具体编码前估算程序运行时间。
2/能够找出限制程序速度的瓶颈
3/掌握改进程序速度的方法

什么是数据结构

定义:
我们如何把现实中大量而复杂的问题以特定的 数据类型 和特定的 存储结构 存储到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。
个人理解：
研究数据存储方式和对数据进行操作的科学
数据结构 = 个体（数据类型） + 个体的关系（存储结构）
算法 = 对存储数据的操作（狭义）
（狭义算法依赖于数据结构，存储结构不同，算法实现方式不同。广义的算法不依赖于数据结构）

什么是算法

算法:
解题方法和步骤
狭义的算法是与数据的存储方式密切相关
广义的算法是与数据的存储方式无关
泛型：
利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

评价算法的标准

1.时间复杂度

大概程序要执行的次数（运行次数最多的那个程序的运行次数），而非时间（不同机器执行的速度是不同的，所以不能用时间作为标准）

2.空间复杂度

算法执行过程中大概所占用的最大内存

3.强壮性

4.难易程度

据结构的地位

	数据结构是软件中最核心的课程
	程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

补充：
编程语言中许多基本的东西都与数据结构有关。
如内存中的栈、堆。所谓的栈内存和堆内存指的是分配内存的算法不同。如果以压栈和出栈的方式分配内存就叫做栈内存；如果以堆排序的方式分配内存，就叫做堆内存。它们实质上讲的是算法，仍是数据结构里的内容。包括函数的调用是通过压栈和出栈实现的。
操作系统中的队列和现场。队列：所有与时间有关的东西必须有时间的先后顺序，先后顺序就用到存储数据的结构，这种数据存储结构就叫做队列。
数据库就是数据结构的简化版，数据库考虑的问题更狭窄。

预备知识

指针

略

结构体

访问结构体变量成员的方法：
1.通过结构体变量名来实现
st.sid
2.通过指向结构体变量的指针来实现【重点】
pst->sid(相当于)：
pst所指向的结构体中的sid这个成员
注意事项：
结构体变量不能加减乘除，但可以相互赋值
普通结构体变量和结构体指针变量作为函数传参的问题

动态内存的分配与释放

略

数据存储的两种方式：线形存储和非线性存储

模块一：线性结构——线性表

特点：各个元素在逻辑上彼此相邻。形象的说说：有一根线把所有的节点用一根直线穿起来，除了首项和末项外的每一个元素只有一个前项和后项。
线性结构的实现主要有两种方式：顺序表和链表。

连续存储——顺序表【数组】

1.什么叫做连续存储
元素逻辑上相邻，实际上物理地址也是相邻的。
用数组来表示顺序表
Struct Arr
{
int * pBase;//存储数组第一个元素地址
int len;//容纳最大元素个数
Int cnt;//当前有效元素个数
}
2.顺序表的基本运算

	void init_arr(struct Arr * pArr,int length);//初始化
	bool append_onetoarr(struct Arr * pArr，int val);//追加一个
	bool append_arrtoarr(struct Arr * pArr，struct Arr * pArr);//追加一组
	bool insert_arr(struct Arr * pArr,int pos,int val);//插入//pos的值从1开始
	bool delete_arr(struct Arr * pArr，int pos,int * pValue);//删除指定的值，并返回这个值
	int get_element();//获取指定元素
	bool is_empty(struct Arr * pArr);//判断是否为空
	bool is_full(struct Arr * pArr);//判断是否满
	void sort_arr(struct Arr * pArr);//把元素排序
	void show_arr(struct Arr * pArr);//显示所有元素
	void inversion_arr(struct Arr * pArr);//把元素倒置

3.具体实现：

#include <stdio.h>
	#include <malloc.h>//提供动态分配内存函数
	#include <stdlib,h>//包含exit函数

void init_arr(struct Arr * pArr,int length)
{
	pArr->pBase=(int *)malloc(sizeof(int)*length)//void *malloc(unsigned int size)返回的是无类型常指针
	if(NULL==pArr->pBase)//分配内存失败
{
	printf("动态内存分配失败！n");
	exit(-1);//终止整个程序
]
else
{
	pArr->len=length;
	pArr->cnt=0;
}
return;		
}

bool is_empty(struct Arr * pArr)
{
	if(0 == pArr->cnt)
		return true;
	else
		return false;
}

bool is_full(struct Arr * pArr)
{
	if(pArr->cnt == pArr->len )
		return ture;
	else
		return false;
}

void show_arr(struct Arr * pArr)
{
	int i;

	if(is_empty(pArr))
		printf("数组为空");
	else
		{
			for(i=0;i<=pArr->cnt;++i)
			printf("%d ",pArr->pBase[i]);
			printf("n");
		}
}

bool append_onetoarr(struct Arr * pArr，int val)
{
   //满时返回false
if(1 == is_full(pArr))
			return false;
		//不满时添加val
	pArr->pBase[cnt]=val;
	++(pArr->cnt);
	return true;
}

bool insert_arr(struct Arr * pArr,int pos,int val)//插入//pos的值从1开始
{
	if(is_full(pArr))
return false;		
if(pos<1||pos>pArr->cnt+1)
return false;				
for(int i=(pArr->cnt-1);i>=(pos-1);- -i)
{
pArr->pBase[i+1]=pArr->pBase[i];
}
pArr->pBase[pose-1]=val;
++(pArr->cnt);
return true;
}

bool delete_arr(struct Arr * pArr，int pos,int * pValue)//删除指定的值，并返回这个值
{
	if(is_empty(pArr))
return false;
	if(pos<1||pos>pArr->cnt)
return false;
	*pValue=pArr->pBase[pos-1];
	for(int i=(pos-1);i<pArr->cnt,++i)
{
		pArr->pBase[i]=pArr->pBase[i+1];
		pArr->pBase[i+1]=0;
}
--(pArr->cnt);
return true;
}

void inversion_arr(struct Arr * pArr)//把元素倒置
{
int i=0;
int j=pArr->cnt-1;
int temp;

while(i<j)
{
temp=pArr->pBase[i];
pArr->pBase[i]=pArr->pBase[j];
pArr->pBase[j]=temp;
++i;
--j;
}
return;	
}

void sort_arr(struct Arr * pArr)//把元素排序,从小到大排序
{
	int i,j;
	for(i=0;i<pArr->cnt-1;++i)
for(j=i+1;j<pArr->cnt;++j)
{
	if(temp=pArr->pBase[i]>temp=pArr->pBase[j])	
	{
temp=pArr->pBase[i];
pArr->pBase[i]=pArr->pBase[j];
pArr->pBase[j]=temp;
	}		
}
}

3、数组的优缺点
略

栈

队列

字符串和数组

树和二叉树

图

最后

以上就是寂寞大米为你收集整理的数据结构学习笔记——基础概念数据结构的基础概念据结构的地位预备知识数据存储的两种方式：线形存储和非线性存储栈队列字符串和数组树和二叉树图的全部内容，希望文章能够帮你解决数据结构学习笔记——基础概念数据结构的基础概念据结构的地位预备知识数据存储的两种方式：线形存储和非线性存储栈队列字符串和数组树和二叉树图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。