ACM刷题之路(十二)数据结构——顺序表

2023-07-31 15:42:03 浏览数 (2)

这周已经是第九周了,为了期末的时候能够兼顾其他课程的复习,所以提早对数据结构这门课进行回顾总结。

数据结构忽略前面两章的C语言基础(有机会以后再补),直接从第三章最简单的线性表开始。

线性表的第一种结构是 顺序表

首先定义一个结构体,

代码语言:javascript复制
#define MAXX 1000
typedef int lei;
struct ss
{
	lei data[MAXX];
	int len;
};

之所以用#define 定义MAXX ,是因为 需要改变 这个线性表大小的时候 只需要在这个语句改变大小即可 不需要再从整段代码再逐一修改。

typedef的意思是取别名。把lei这个小名 给int,作用同上  修改线性表数据类型的时候可以直接改动

这个结构体里面有两部分,一部分是数据,第二部分是长度,初始化为-1.

(ps:为什么从-1开始,因为数组是从0开始的)

顺序表根据《数据结构》这本书 需要会写初始化、指定位置插入、查找、删除、取长度、判断是否为空的函数。


首先是初始化函数。

初始化一个顺序表,只要用c 的new函数   ,new一个顺序表就可以,把长度初始化为-1,然后返回首地址就行了。

代码语言:javascript复制
ss *chushihua()
{
	ss *L;
	L=new ss;
	L->len=-1;
	return L;
}

第二个是查找函数,查找函数只要按照o~len的顺序遍历过去,凡是找到就返回,找不到就返回一个负数,思路简单粗暴,时间复杂度是o(n)。

ps:不考虑有数据重复的情况.

代码语言:javascript复制
int find(ss *L,lei X)
{
	for(int i=0;i<=L->len;i  )
	{
		if(L->data[i]==X) return i;
	}
	return -1;
}

第三个是插入函数。

插入只需要判断是否插入成功就可以,所以用bool类型作为返回值。

需要三个参数,顺序表的首地址、插入的数据、插入的位置。

需要考虑两种极端情况:第一种顺序表已经满了,第二种插入的位置越界。

否则就正常插入,把插入位置的后面元素往后移,再在插入的位置插入该插的数,然后让顺序表的长度 1即可。

代码语言:javascript复制
bool charu(ss* L,lei shu,int weizhi)
{
	if(L->len==MAXX-1)
	{
		cout<<"顺序表已满"<<endl;
		return false;
	}
	if(weizhi<0||weizhi>L->len 1)
	{
		cout<<"插入位置错误"<<endl;
		return false;
	}
	for(int i=L->len;i>=weizhi;i--)
	{
		L->data[i 1]=L->data[i];
	}
	L->data[weizhi]=shu;
	L->len  ;
	return true;
}

第四个是删除函数。

同上为bool类型,参数为顺序表的首地址和需要删除的位置。

考虑一种极端情况,如果需要删除的位置为空。

删除只需要把后面的元素往前移,覆盖掉前面的元素就可以,在把长度-1.

ps:此时L->[len]的数据还是存在,但是不用管。

代码语言:javascript复制
bool shanchu(ss *L,int weizhi)
{
	if(weizhi<0||weizhi>L->len)
	{
		cout<<"位置越界"<<endl;
		return false;
	}
	for(int i=weizhi;i<=L->len;i  )
	{
		L->data[i]=L->data[i 1];
	}
	L->len--;
	return true;
}

最后一个最简单,就是判断是否为空。

只要判断他的长度是否为初始化的-1即可。

代码语言:javascript复制
bool empty(ss *L)
{
	if(L->len==-1) return true;
	return false;
}

所以给出总的代码:

代码语言:javascript复制
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
#define MAXX 1000
typedef int lei;
struct ss
{
	lei data[MAXX];
	int len;
};
ss *chushihua()
{
	ss *L;
	L=new ss;
	L->len=-1;
	return L;
}
int find(ss *L,lei X)
{
	for(int i=0;i<=L->len;i  )
	{
		if(L->data[i]==X) return i;
	}
	return -1;
}
bool charu(ss* L,lei shu,int weizhi)
{
	if(L->len==MAXX-1)
	{
		cout<<"顺序表已满"<<endl;
		return false;
	}
	if(weizhi<0||weizhi>L->len 1)
	{
		cout<<"插入位置错误"<<endl;
		return false;
	}
	for(int i=L->len;i>=weizhi;i--)
	{
		L->data[i 1]=L->data[i];
	}
	L->data[weizhi]=shu;
	L->len  ;
	return true;
}
bool shanchu(ss *L,int weizhi)
{
	if(weizhi<0||weizhi>L->len)
	{
		cout<<"位置越界"<<endl;
		return false;
	}
	for(int i=weizhi;i<=L->len;i  )
	{
		L->data[i]=L->data[i 1];
	}
	L->len--;
	return true;
}
bool empty(ss *L)
{
	if(L->len==-1) return true;
	return false;
}
int main()
{
	ss *L;
	L=chushihua();
	charu(L,1,0);
	charu(L,2,1);
	cout<<"1在第"<<find(L,1)<<"个位置"<<endl;
	shanchu(L,1);
	shanchu(L,0);
	cout<<"下面判断是否为空,空为1"<<endl;
	cout<<empty(L)<<endl;
	return 0;
}

顺序表不难,明天复习链表。

0 人点赞