线性表的顺序存储结构与操作

发布于:2022-12-15 ⋅ 阅读:(384) ⋅ 点赞:(0)

                                                                     题目描述

思路:从题目可以看出这是数据结构算法的线性表的插入,查找,获取,删除,遍历等功能。

首先创建一个类class(线性表)

class SeqList
{
	public:
		//构造函数
		SeqList()
		{
			length = 0;
			int data[20] = {0};
		} 
		//按位查找
		void Seek(int Data); 
		//获取某个位置
		void Get(int location); 
		//插入
		void Insert(int location,int Data);
		//删除
		void Delete(int location); 
		//输出数据
		void Vshow();

	private:
		int data[20];
		int length;
		
};

第一个算法:    插入算法

但是插入之前我们会手动输入插入的位置(location),之后从该位置后的每一个数组单元进行后移一个位置,再把值插入即可,长度(length)加1。如果之前表为空,插入时则无需后移数组单元。还需要注意的是表满,输入位置不正确情况。

void SeqList::Insert(int location, int Data)
{
	int i; 
	if(length > 20 )
	{
		cout << "上溢"; 
	}
	else if(location < 0 || location > 20)
	{
		cout << "位置不正确";
	}else
	{
		if(length == 0)
		{
			data[location-1] = Data; 
		}
		else
		{
			for( i =length; i>= location; i--)
			{
				data[i] = data[i-1];
			}
			data[location-1] = Data;
		}
		
	}
		length++;
}

由代码可以看出首先判断是否表满,输入是否正确情况,再判断是不是之前列表为空,为空则直接插入第一个位置,不为空则从插入位置之后数组单元进行后移(从后往前移)

第二个算法:      查找(按值查找)

用查找的元素值在表中遍历的同时比对查找,查到即可输出该位置。注意:如有查不到情况则输出None

void SeqList::Seek(int Data)
{
	int i;
	int k = 0;
	int location = 0;

	for(i = 0; i < length; i++)
	{
		if(Data == data[i])
		{
			location = i+1;	
					
		}else
		{
			k++;
		}
    }
    if(k == length)
    {
    	cout <<"None";
    }
	cout << location;
}

这里k指的是在表中找不到则k会跟长度(length)一样,由此判断找不到。

第三个算法:     获取某个元素值(按位置)

这个算法就更简单了,直接输出该位置元素即可。注意:要判断查找的位置存不存在。

void SeqList::Get(int location)
{
	
	if(location < 0 || location >20)
	{
		cout <<"位置不正确";
	}else
	{
		cout << data[location-1];
	}
	
}

第四个算法:      删除某个位置的元素

输入删除的位置之后,输出该位置删除的元素值,再从该位置后的每一个数组单元进行前移一个位置即可(从前往后),长度(length)减1。注意:还需判断表是否为空,删除位置是否正确。

void SeqList::Delete(int location)
{
	int i;
	
	if(length == 0)
	{
		cout << "下溢";
	}else if(location < 0 || location > length)
	{
		cout << "位置不正确";
	}else
	{
		cout << data[location-1];
	
		for(i = location-1; i < length; i++)
		{
			data[i] = data[i+1];
		}
		
		length--;
	}
	
	
}

最后可以按照题目要求写出主函数,进行算法的拼接(拼接过程省略),接下来就看看整体代码吧:

#include <iostream>
using namespace std;
class SeqList
{
	public:
		//构造函数
		SeqList()
		{
			length = 0;
			int data[20] = {0};
		} 
		//按位查找
		void Seek(int Data); 
		//获取某个位置
		void Get(int location); 
		//插入
		void Insert(int location,int Data);
		//删除
		void Delete(int location); 
		//输出数据
		void Vshow();

	private:
		int data[20];
		int length;
		
};

void SeqList::Vshow()
{
	int i;
	for(i = 0; i < length; i++)
	{
		cout << data[i];
	} 
}
void SeqList::Seek(int Data)
{
	int i;
	int k = 0;
	int location = 0;

	for(i = 0; i < length; i++)
	{
		if(Data == data[i])
		{
			location = i+1;	
					
		}else
		{
			k++;
		}
    }
    if(k == length)
    {
    	cout <<"None";
    }
	cout << location;
}
void SeqList::Get(int location)
{
	
	if(location < 0 || location >20)
	{
		cout <<"位置不正确";
	}else
	{
		cout << data[location-1];
	}
	
}
void SeqList::Insert(int location, int Data)
{
	int i; 
	if(length > 20 )
	{
		cout << "上溢"; 
	}
	else if(location < 0 || location > 20)
	{
		cout << "位置不正确";
	}else
	{
		if(length == 0)
		{
			data[location-1] = Data; 
		}
		else
		{
			for( i =length; i>= location; i--)
			{
				data[i] = data[i-1];
			}
			data[location-1] = Data;
		}
		
	}
		length++;
}
void SeqList::Delete(int location)
{
	int i;
	
	if(length == 0)
	{
		cout << "下溢";
	}else if(location < 0 || location > length)
	{
		cout << "位置不正确";
	}else
	{
		cout << data[location-1];
	
		for(i = location-1; i < length; i++)
		{
			data[i] = data[i+1];
		}
		
		length--;
	}
	
	
}

int main(int argc, char** argv) {
	
	SeqList D;
	char letter;
	int k;
	int i;
	
	int data;
	int location;
	
	cin >> letter; 
	 
	while (letter != 'E')
	{
		switch (letter)
		{
			case 'I':
				cin >> k;
				for(i = 0; i < k; i++)
				{
					cin >> location;
					cin >> data;
					D.Insert(location, data);
				} 
				break;
			case 'S':
				cin >> data;
				D.Seek(data);
				break;		
			case 'G':
				cin >> location;
				D.Get(location);
				break;
			case 'D':
				cin >> location;
				D.Delete(location); 
				break;
			case 'V':
				D.Vshow();
			break;
			default:
				break;
		}
		cin >> letter;
	}
	
	return 0;
}