线性表的实现及其功能的拓展

发表于 | 分类于

返回目录

本文目的在于，对线性表实现的描述，以及代码的简单实现

线性表概况描述

下面是函数的头文件部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class dataType, int MaxSize>class SeqList {
	dataType *data;						//用于存放数据元素的数组
	int length;							//顺序表中的元素个数
public:
	SeqList();							//无参构造函数
	SeqList(dataType a[], int n);		//有参构造函数
	~SeqList();
	int ListLength();					//求线性表的长度
	void SetLength(int length);
	dataType Get(int pos);				//按位查找，取顺序表的第pos个元素
	int Locate(dataType item);			//按值查找，求顺序表中值为item的元素序号
	void PrintSeqList();				//遍历顺序表，按序号一次输出各元素
	void Insert(int i, dataType item);	//在顺序表第i个位置插入值为item的元素
	dataType Delete(int i);				//删除顺序表的第i个元素‘
	*****
	扩展部分
	*****
	void quicksort(const int &first, const int &last );//快速排序
	void Merge(SeqList & LA, SeqList & LB);			  //合并有序表
	bool IsOrder();									 //判断表是否有序
	dataType DeleteMinData();						//删除最小元素，空位后值填补
	void DeleteStoT(dataType S,dataType T);			//删除S-T的元素
	void DeleteXitem(dataType X);					//删除元素X
	void Deleterepeated();							//删除重复元素
	bool IsExited(dataType &x,dataType *record,int length);//查看元素是否已存在
	void DevidedBya_1();							//按照键值A1分开数组
	bool cmp(const dataType&, const dataType&);		//用于比较
};

一、基本功能

1.1无参构造函数

这个函数，适用于无参的构造函数，实现对空间的申请，以及长度置0；

1
2
3
4
5
6
7
8
9
10
11
/**
* 无参数构造函数
* 仅设置长度为0
* @param[in] 无
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::SeqList()
{
	data=new dataType[MaxSize];
	length = 0;
}

1.2有参构造函数

此函数用来，带有参数的赋值,做合法性检查，申请空间，置线性表长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 构造函数
* 设置线性表的初始值，长度
* @param[in] 数据源a，数量n
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::SeqList(dataType *a, int n)
{	
	data=new dataType[MaxSize];
	if (n > MaxSize)			//数据合法性检查
	{
		cerr << "error";
		system("pause");
		exit(1);
	}
	for (int i=0; i <n; i++)
	{
		data[i] = a[i];				//需要重载运算符‘=’
	}
	length = n;
	cout << "\ncreate list success,length is " << length << endl;
}

1.3析构函数

用于在程序结束后，对申请空间进行销毁，做后续处理。

1
2
3
4
5
6
7
8
9
* 析构函数
* @param[in] 无
*/
template<class dataType, int MaxSize>
SeqList<dataType, MaxSize>::~SeqList()
{
	if(data) delete[]data;
	data=NULL;
}

1.4求表长

1
2
3
4
5
6
7
8
9
/**
* 返回线性表返回当前元素个数
* @param[out] 表长length
*/
template<class dataType, int MaxSize>
int SeqList<dataType, MaxSize>::ListLength()
{
	return length;
}

1.5其他基本功能

还有一些基本功能，不在此贴出，详细请见源程序

二、扩展功能

2.1快速排序

本函数采用快速排序的方法，对成员进行排序，目前采用的是运用cmp函数，以后可考虑用‘<’重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 按照CMP的方式进行快速排序
* @param[in] 起始位置first，终止位置last，比较函数cmp
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::quicksort(const int &first, const int &last)
{
	int i = first, j = last;
	const dataType m = *(data + ((first + last) >> 1));
	dataType temp;
	do
	{
		while (cmp(data[i], m)) i++;
		while (cmp(m, data[j])) j--;
		if (i <= j)
		{
			temp = data[i]; 
			data[i] = data[j]; 
			data[j] = temp;
			i++; j--;
		}
	} while (i < j);
	if (i < last) quicksort( i, last);
	if (first < j) quicksort(first, j);
}

2.2归并有序表

通过比较方法，取各数组较大值，最后把多余的附载在后面即可
其中，做了关于合法性的检测，还包含了先判断所给的数据是否有序的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 合并两个有序表，并存在第一个中，
* @param[in] 表1LA，表2LB， 比较方法，cmp
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::Merge(SeqList &LA,SeqList &LB)
{
	int i = 0; int  j = 0;int k = 0;
	SeqList C;
	if (LA.ListLength() + LB.ListLength() > MaxSize) {
		cerr << "溢出";
		system("pause");
		return;
	}
	C.length = LA.ListLength() + LB.ListLength();
	if(!LA.IsOrder(cmp)){LA.quicksort(0,LA.ListLength()-1,cmp);}//若A无序，先排序
	if(!LB.IsOrder(cmp)){LA.quicksort(0,LB.ListLength()-1,cmp);}
	while (i<LA.ListLength() && j<LB.ListLength()) {
		//循环，两两比较，小者存入结果表
		if (LA.data[i]<=LB.data[j])
			C.data[k++] = LA.data[i++];
		else
			C.data[k++] = LB.data[j++];
	}
	if(i==LA.ListLength()) {
		while (j< LB.ListLength()) {
			C.data[k++] = LB.data[j++];
		}
	}
	else{
		while (i<LA.ListLength()) {
			C.data[k++] = LA.data[i++];
		}
	}
	for (i=0;i<C.ListLength();i++)
	{
		LA.data[i]=C.data[i];
	}
	LA.SetLength(C.ListLength());
}

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
*检查元素是否有序
*/
template<class dataType, int MaxSize>
bool SeqList<dataType, MaxSize>::IsOrder()
{
	for (int j = 0; j <ListLength()  ; j++) {
		if (cmp(data[j], data[j + 1])) {
			return false;
		}
	}
	return true;
}

2.3删除S-T之间元素

本函数比较复杂，目前版本没有实现完全功能，原因是没有重载运算符，对边界的处理不好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 删除顺序表S-T之间元素，若S<T报错，
* @param[in] S,T,
* @param[out] 
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DeleteStoT(dataType S,dataType T)
{
	if(!cmp(S,T))
	{
		cout<<"输入有误，删除失败。。"<<endl;
		return;
	}
	if (IsOrder()){
		quicksort(0,ListLength()-1);
	}
	
	for (int i=0;i<ListLength();i++){	//找到S所在的位置i
		bool flag = !cmp(data[i],S);
		if(flag){
			break;
		}
	}
	
	for (int j=0;j<ListLength();j++){	//	找到T所在的位置j
		bool flag = !cmp(data[j],T);
		if(flag){
			break;
		}
	}
	if(i>=0&&j<ListLength()){
		for(int k=j-1;k>=i;k--){
			Delete(k+1);	
		}
	}
}

2.3删除X元素

本函数用于删除顺序表中的X元素，未找到，提示消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DeleteXitem(dataType X){
	int k=0;
	for (int i=0;i<ListLength();i++)
	{
		if (X==data[i])
		{
			Delete(i+1);	
			i=i-1;
			k++;
		}
	}
	if (k==0)cout<<"Not Found!"<<endl;
}

2.4删除重复元素

本函数用于删除重复元素，编写时遍历表，找到第一次出现的元素，放在record数组中，后接受record的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 删除重复元素
* @param[in] 
* @param[out] 
* 位置从0开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::Deleterepeated(){
	dataType *record=new int[MaxSize];
	int k=0;
	for (int i=0;i<ListLength();i++)
	{
		if (!IsExited(data[i],record,k))
		{
			record[k++]=data[i];
		}
	}
	delete []data;
	data=record;
	SetLength(k);
}

其中用了一个辅助函数，判定是否第一次出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 判定元素是否出现过，辅助函数
* @param[in] 元素X，数组record，长度length
* @param[out] bool flag
* 位置从0开始。
*/
template<class dataType, int MaxSize>
bool SeqList<dataType, MaxSize>::IsExited(dataType &x,dataType *record,int length){
	for (int i=0;i<length;i++)
	{
		if(x==record[i]) return true;
	}
	return false;
}

###2.5 划分元素
按照A[0]值，划分数组，要求复杂度为O（n）
思路如下：先遍历一遍，找到小于键值的，放到前面（交换），从这个位置继续开始继续遍历，找到等于的元素放到中间即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 按照a0的值划分，要求时间复杂度为O（N）
* @param[in] 
* @param[out] 
* 位置从1开始。
*/
template<class dataType, int MaxSize>
void SeqList<dataType, MaxSize>::DevidedBya_1(){
	dataType v=data[0];//键值V
	int k=0;//递进下标
	for (int i=0;i<ListLength();i++)		//小于v的值归于左侧
	{
		if (data[i]<v)
		{
			int tmp=data[i];
			data[i]=data[k];
			data[k]=tmp;
			k++;
		}
	}
	
	for (i=k;i<ListLength();i++)		//等于v的值继续归于中间，剩下的自然是大于v的值
	{
		if (data[i]==v)
		{
			int tmp=data[i];
			data[i]=data[k];
			data[k]=tmp;
			k++;
		}
	}
}

三、测试（test.cpp）

下面是完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<stdlib.h>
#include"SeqList.h"
#include"SeqList.cpp"
using namespace std;

int main() {
	int MaxSize=100;
	int number;
	cout << "请输入数据个数\n";
	cin >> number;
	int *a = new int[number];
	for (int  i = 0; i < number; i++)
	{
		cin>>a[i];
	}
	SeqList<int, 100> lista(a, number);
	cout <<"当前元素个数是："<< lista.ListLength()<< endl;
	lista.quicksort(0,lista.ListLength() - 1);
	cout << "排序后遍历打印："<<endl;
	lista.PrintSeqList();
	system("pause");
	lista.DeleteStoT(70,90);
	cout << "删除S-T后遍历打印："<<endl;
	lista.PrintSeqList();
	lista.Insert(1,3);
	cout << "插入后遍历打印："<<endl;
	lista.PrintSeqList();
	lista.DeleteXitem(100);
	cout<<endl << "删除元素X后遍历打印："<<endl;
	lista.PrintSeqList();
	system("pause");
	cout <<endl<< "按照a0划分遍历打印："<<endl;
	lista.DevidedBya_1();
	lista.PrintSeqList();
	system("pause");
	cout <<endl<< "删除重复元素后遍历打印："<<endl;
	lista.Deleterepeated();
	lista.PrintSeqList();
	system("pause");
	if (a) delete []a;//扫尾
	return 0;
}

3.1测试结果

alt text

4、总结

这次编程，还算顺利，但是对于引用对象还是不是很清楚，感谢老师刚刚发的文件，会去仔细看看的。