ACM刷题之路（十二）数据结构——顺序表

青旅半醒 2023-10-21 07:28 48阅读 0赞

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

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

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

首先定义一个结构体，

#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，然后返回首地址就行了。

ss *chushihua()
    {
    	ss *L;
    	L=new ss;
    	L->len=-1;
    	return L;
    }

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

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

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即可。

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\]的数据还是存在，但是不用管。

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即可。

bool empty(ss *L)
    {
    	if(L->len==-1) return true;
    	return false;
    }

所以给出总的代码：

#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;
    }

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