1、数据结构概述及顺序表(附:可以直接打印显示的源码)

发布于:2024-11-29 ⋅ 阅读:(31) ⋅ 点赞:(0)

《数据结构》概述:

数据结构:数据元素之间的关系(逻辑关系)

数据类型:高地电平 表示 1/0

要做大量的运算:诞生了基本数据类型:int double .....--》反应了数据的取值范围

(int字节:占4B--->-2^31~~~(2^31)-1

1bit: 0~1

2bit: 0~(2^2)-1 个数:2^2

个数怎么算的 :00 01 10 11 四个

为什么要减一: 因为除二后0没有对称,先拿出一个数跟0对称,然后再要减一

32bit 表示多少个数:2^32

-2^31 ~~2^31-1)

要做什么系统之类的更复杂的东西:诞生了抽象数据类型:抽象

(人:信息(数据)+行为--->函数/方法--->数据+函数=抽象数据类型

使用抽象数据类型 定义一个数据结构--->数据集合+操作集合)

分析问题:逻辑结构--->逻辑上分析 事物之间的关系

解决问题:存储结构(物理结构/映像)--->在计算机中实现逻辑关系

存储结构就是用计算机语言实现的逻辑结构:密不可分


逻辑结构:线性逻辑结构:数据之间的关系是一对一的:线性表、栈、队列

非线性逻辑结构:数据之间的关系是一对多/多对多:树、图。。。

数据存储在存储器中

存储结构:1.顺序存储结构:逻辑上是连续的数据,存储时,在物理上也连续

2.链式存储结构:逻辑上是连续的数据,存储时,在物理上不连续,但是要实现逻辑上的连续:用指针把数据连起来,实现了逻辑上的连续

3.索引存储结构+4.散列存储结构(哈希)

数据结构:学一个一个的逻辑结构,选择合适的存储结构把它实现


线性逻辑结构:

线性表:n个数据元素的有限序列,按照线性结构排列

操作:增删改查

存储结构实现线性表:

顺序存储结构实现的线性表:

顺序表(在内存中画出以同一种数据类型存储的空间-->即数组):以一维数组的形式保存的线性表

操作:增删改查

1.增:在顺序表中添加一个元素

(1)在末尾添加一个元素

(2)在末尾元素之前的某个i位置指定添加元素

倒着循环 把i及i位置后面的数据 往后移动一个位置,把i位置空出来

//在顺序表末尾添加一个元素:在size下标位置添加一个元素
void add(Array * a,int k)
{
	//先判断是否超出最大容量值
	if(a->size < a->length)
	{
		a->data[a->size]=k;
		a->size++;
	 } 
	 else{
	 	printf("顺序表已满,不能放入数据\n");
	 }
} 

//在下标i位置 插入一个数据k
void insert(Array *a,int i,int k) 
{
	//先判断是否超出最大容量值 先判满 
	if(a->size < a->length)
	{
		//移动位置,把data[i]空出来 
		for(int j=a->size-1;j>=i;j--)
		{
			a->data[j+1]=a->data[j];
		}
		a->data[i]=k;
		a->size++;
	 } 
	 else{
	 	printf("顺序表已满,不能放入数据\n");
	 }
}

2.查找:查找到给定数据的下标(位置),如果该数据不存在 返回-1

//查 : 一一比对  找到后直接把这个值返回 
int find(Array a,int k)
{
	for(int i=0;i<a.size;i++)//i只能小于a.size  因为size那个位置没数据(它是实际数据之后的位置) ,因为数组中有0,所以size多占了一个位置 
	{
		if(k==a.data[i])
		{
			return i;
			//如果没有找到,则不会返回任何值退出循环 
		}
	}
	return -1;//最后返回-1 
}

3.删除:删除给定的数据k

查找k的下标,往前调用 覆盖

void del(Array *a,int k)
{
	//返回删除元素的下标 利用查找函数 
	int i =find(a,k);//或者直接加(*a) 即int i = find((*a),k); 
	if(i==-1)
	{
		printf("被删除的数据不存在\n");
	}
	else{
		for(int j=i;j<a->size-1;j++)//j<a->size 或者j<a->size-1 不过没影响 正常是j<a->size-1  data[size+1]不会越界 因为size<length,但是数组满的时候会越界所以保险起见还是用j<a->size-1 
		{
			a->data[j]=a->data[j+1];
		}
		a->size--;
	}
}

4.改:把数据i-->k

找i的下标b,然后a->data[b]=k;

void change(Array *a,int i,int k)
{
	//找到数据为i的下标 
	int b =find(a,i);
	if(b==-1)
	{
		printf("被修改的数据不存在\n");
	}
	else{
		a->data[b]=k;
	}
	
}

顺序表的优缺点(说白了就是数组):

优点:(方便)随机访问 data[i] 可以根据下标直接访问

缺点:操作繁琐:插入和删除操作都需要移动大量的数据,不够灵活

应用场景:以随机访问为主的需求中---》需求很少

5.源码

#include<stdio.h>
#include<stdlib.h>
//实现一个存放int类型的顺序表 
//分析: 需要知道数据-->要一个数组 ,同时得知道这个数据的理论容量最大值跟实际值  三个方面来描述,放在一个里面-->声明结构体来实现
typedef struct ArrayList{
//	int data[105];//静态开数组
	int *data;//指针模拟开数组 
	int length;//声明理论容量的最大值
	int size;//声明实际个数 
}Array;

//初始化顺序表 
Array initArray(int n)
{
	Array ar;
	ar.data=(int *)malloc(sizeof(int)*n);//开辟顺序表的空间 :分配成功-->data是一个实际的内存地址;分配不成功则会返回NULL(malloc的语法) 
	if(ar.data==NULL)
	{
		printf("空间分配失败");
	}
	//申请下来后就可以赋值了 
	ar.length=n;
	ar.size=0;//还没放元素,则实际值为0
	return ar;//返回到下面代码a的地方 
	
}

//在顺序表末尾添加一个元素:在size下标位置添加一个元素
void add(Array * a,int k)
{
	//先判断是否超出最大容量值
	if(a->size < a->length)
	{
		a->data[a->size]=k;
		a->size++;
	 } 
	 else{
	 	printf("顺序表已满,不能放入数据\n");
	 }
} 

//在下标i位置 插入一个数据k
void insert(Array *a,int i,int k) 
{
	//先判断是否超出最大容量值 先判满 
	if(a->size < a->length)
	{
		//移动位置,把data[i]空出来 
		for(int j=a->size-1;j>=i;j--)
		{
			a->data[j+1]=a->data[j];
		}
		a->data[i]=k;
		a->size++;
	 } 
	 else{
	 	printf("顺序表已满,不能放入数据\n");
	 }
}

//查 : 一一比对  找到后直接把这个值返回 
int find(Array *a,int k)
{
	for(int i=0;i<a->size;i++)//i只能小于a.size  因为size那个位置没数据(它是实际数据之后的位置) ,因为数组中有0,所以size多占了一个位置 
	{
		if(k==a->data[i])
		{
			return i;
			//如果没有找到,则不会返回任何值退出循环 
		}
	}
	return -1;//最后返回-1 
}

void del(Array *a,int k)
{
	//返回删除元素的下标 利用查找函数 
	int i =find(a,k);//或者直接加(*a) 即int i = find((*a),k); 
	if(i==-1)
	{
		printf("被删除的数据不存在\n");
	}
	else{
		for(int j=i;j<a->size-1;j++)//j<a->size 或者j<a->size-1 不过没影响 正常是j<a->size-1  data[size+1]不会越界 因为size<length,但是数组满的时候会越界所以保险起见还是用j<a->size-1 
		{
			a->data[j]=a->data[j+1];
		}
		a->size--;
	}
}  

void change(Array *a,int i,int k)
{
	//找到数据为i的下标 
	int b =find(a,i);
	if(b==-1)
	{
		printf("被修改的数据不存在\n");
	}
	else{
		a->data[b]=k;
	}
	
}

void show(Array a)
{
	for(int i=0;i<a.size;i++)
	{
		printf("%d ",a.data[i]);
	}
	printf("\n");
}

int main()
{
	Array a;//顺序表 
	//初始化:
	int n; //假设理论容量的最大值 
	printf("请输入顺序表的理论最大容量:\n");
	scanf("%d",&n);
	a=initArray(n);//把n传入进去  写一个带返回值的函数 ,把线性表初始化好后再返回回来 

//操作:增  利用add函数  因为增加后顺序表(函数)发生变化,则利用地址传参 
	add(&a,6);
//  a=add(a,6) 也可以这样写	
	add(&a,7);
	add(&a,8);
	add(&a,9);
	add(&a,1);
	add(&a,5);	
	show(a);	
	insert(&a,3,7);
	show(a);
	
//查 
	//顺序表没有变,所以用值传递 
	printf("%d",find(&a,9));
	printf("\n");

//删	
	del(&a,6);//顺序表发生变化  因为del函数中要调用查找函数 所以把查找函数中的值传递a变成&a地址传递方便之后调用不会报错
			  //或者直接加(*a) 
	show(a);
//改 
	change(&a,1,10);//把数据1改成10 
	show(a);
	return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到