数据结构：顺序表及其函数的实现

数据结构：顺序表及其函数的实现

本文顺序表采用动态数组的方法来进行初始化。主要实现了以下一些功能。

函数功能：

void InitList(Sqlist &L); 初始化表。构造一个空的线性表

void IncreaseSize(Sqlist &L, int len);//增加动态数组长度

void DestroyList(Sqlist &L);//销毁操作。销毁L并释放L所占用的内存空间

int GetLength(Sqlist L);//求表长；即L中数据元素的个数

int LocateElem(Sqlist L, int e);//按值查找元素，找具有给定关键字值的元素

int GetElem(Sqlist L, int i);//按位查找元素，找到表中第i个元素的值

void ListInsert(Sqlist &L, int i, int e);//插入操作。在表中第i个位置插入指定元素e

void ListDelete(Sqlist &L, int i, int &e);//删除操作。删除表中第i个位置的元素，并用e返回删除元素的值

void PrintList(Sqlist L);//输出操作。按前后顺序输出L中所有的值

int Empty(Sqlist L);//判空操作。

下面展示代码。

///顺序表 :基本全是纯C语言  引用部分& 和 输出部分是C++   C语言中可以利用指针修改值 没有引用 
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
 
#define INITSIZE 5
#define ListIncreament 10

typedef struct Sqlist{
   
	int *data;//存储空间基地址 
	int MaxSize;//当前分配的存储容量 
	int length;//当前表长 
}Sqlist;

void InitList(Sqlist &L);//初始化表。构造一个空的线性表 
void IncreaseSize(Sqlist &L, int len);//增加动态数组长度 
void DestroyList(Sqlist &L);//销毁操作。销毁L并释放L所占用的内存空间 
int GetLength(Sqlist L);//求表长；即L中数据元素的个数 
int LocateElem(Sqlist L, int e);//按值查找元素，找具有给定关键字值的元素
int GetElem(Sqlist L, int i);//按位查找元素，找到表中第i个元素的值
void ListInsert(Sqlist &L, int i, int e);//插入操作。在表中第i个位置插入指定元素e
bool ListDelete(Sqlist &L, int i, int &e);//删除操作。删除表中第i个位置的元素，并用e返回删除元素的值
void PrintList(Sqlist L);//输出操作。按前后顺序输出L中所有的值
int Empty(Sqlist L);//判空操作。
 
 
void InitList(Sqlist &L){
   
	//动态初始化 
	L.data = (int *)malloc(INITSIZE * sizeof(int));
	if(!L.data) return ;//申请内存失败 
	L.MaxSize = INITSIZE;
	L.length = 0;
} 

void DestroyList(Sqlist &L){
   
	int *p;
	p = L.data;
	free(p);
}

//增加动态数组长度
void IncreaseSize(Sqlist &L, int len){
   
	int *p = L.data; 
	L.data = (int *)malloc(sizeof(int) * (L.MaxSize + len));
		if(!L.data) return ;//申请内存失败 
	for(int i = 0; i < L.length; i++){
   
		L.data[i] = p[i];
	}
	L.MaxSize += len;
	free(p); 
} 


//插入操作。在表中第i个位置插入指定元素e
// 1 <= i <= n
void ListInsert(Sqlist &L, int i, int e){
   
	if(i < 1 || i > L.length + 1){
   
		return ;
	}
	
	if(L.length >= L.MaxSize){
   
		int *newbase;
		newbase = (int *)realloc(L.data, sizeof(int)* (L.MaxSize + ListIncreament));
		if(!newbase) return ; //申请内存失败
		L.data = newbase;
		L.MaxSize += ListIncreament; 
	}
	//以上7行代码可以写成下面这样 （待验证） 
	/*
		if(L.length >= L.MaxSize){
			IncreaseSize(L, ListIncreament);
		}
	*/
	
	
	int *q;//q为插入位置
	q =  &(L.data[i - 1]);
	for(int *p = &(L.data[L.length - 1]); p >= q; p--){
   
		*(p+1) = *p;
	}
	*q = e;
	L.length++;
}



int GetLength(Sqlist L){
   
	return L.length;
}


//按值查找元素，找具有给定关键字值的元素
int LocateElem(Sqlist L, int e){
   
	for(int i = 0; i < L.length; i++){
   
		if(L.data[i] == e){
   
			return i+1;
		}
		
	}
	return -1;
}


//按位查找元素，找到表中第i个元素的值
int GetElem(Sqlist L, int i){
   
	return L.data[i - 1];
}


//删除操作。删除表中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(Sqlist &L, int i, int &e){
   
	if(i < 1 || i > L.length){
   
		return false;//i的信息错误 
	}
	e = L.data[i - 1];
	for(int j = i; j < L.length; j++){
   
		L.data[j - 1] = L.data[j];
	}
	--L.length;
	return true;
}


//输出操作。按前后顺序输出L中所有的值
void PrintList(Sqlist L){
   
	for(int i = 0; i <L.length; i++){
   
		cout<<L.data[i]<<" "; //用这个方法是方便输出 若data的数据类型改变 也不用改变输出代码 
	}
	return ; 
}


//判空操作。
int Empty(Sqlist L){
   
	if(L.length == 0){
   
		return 1;
	}
	else{
   
		return 0;
	}
}
 

下面是在主函数中的实现：（个人加入了一些菜单功能，代码看着有些笨拙，方便了解实现功能…）

// An highlighted block
int main()
{
   
	Sqlist L;
	int num;
	InitList(L);
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
	ListInsert(L, 4, 4);
	ListInsert(L, 5, 5);

	cout<<"\n菜单功能如下： \n";
	cout<<"1--------求表长；即L中数据元素的个数"<<endl;
	cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
	cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
	cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
	cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
	cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
	cout<<"7--------判空操作"<<endl;
	cout<<"8--------退出程序"<<endl;
	
	while(1){
   
		cout<<"请输入选项："<<endl;
		cin>>num;
		switch(num){
   
			case 1:
			
				cout<<"表长度为："<<GetLength(L)<<endl;;
				
				break;
				
				case 2:
					int a;
					system("cls");
					cout<<"菜单功能如下： \n";
					cout<<"1--------求表长；即L中数据元素的个数"<<endl;
					cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
					cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
					cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
					cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
					cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
					cout<<"7--------判空操作"<<endl;
					cout<<"8--------退出程序"<<endl;
					cout<<"请输入查找的值： \n";
					cin>>a; 
					cout<<"该值的位数是： "<<LocateElem(L, a)<<endl;;
					break;
					
					case 3:
						int b;
						system("cls");
						cout<<"菜单功能如下： \n";
						cout<<"1--------求表长；即L中数据元素的个数"<<endl;
						cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
						cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
						cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
						cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
						cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
						cout<<"7--------判空操作"<<endl;
						cout<<"8--------退出程序"<<endl;
					    cout<<"请输入查找的值： \n";
						cout<<"请输入要查找元素的位数： \n";
						cin>>b;
						cout<<"该元素的值是： "<<GetElem(L, b)<<endl;
						break;
						
						case 4:
							int c, d;
							system("cls");
							cout<<"菜单功能如下： \n";
							cout<<"1--------求表长；即L中数据元素的个数"<<endl;
							cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
							cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
							cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
							cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
							cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
							cout<<"7--------判空操作"<<endl;
							cout<<"8--------退出程序"<<endl;
							cout<<"请输入查找的值： \n";
							cout<<"请输入要插入元素的位数及插入元素的值： \n";
							cin>>c>>d;
							ListInsert(L, c, d);
							break;
							
							case 5:
								int o, f;
							system("cls");
							cout<<"菜单功能如下： \n";
							cout<<"1--------求表长；即L中数据元素的个数"<<endl;
							cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
							cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
							cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
							cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
							cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
							cout<<"7--------判空操作"<<endl;
							cout<<"8--------退出程序"<<endl;
				
								cout<<"请输入要删除元素的位数： \n";
								cin>>o;
								if(ListDelete(L, o, f))		cout<<"删除元素的值为："<<f<<endl;
								else cout<<"非法输入！\n";
								break;
								
								case 6:
							system("cls");
							cout<<"菜单功能如下： \n";
							cout<<"1--------求表长；即L中数据元素的个数"<<endl;
							cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
							cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
							cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
							cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
							cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
							cout<<"7--------判空操作"<<endl;
							cout<<"8--------退出程序"<<endl;
					
									cout<<"列表中所有元素： "<<endl;
									PrintList(L);
									cout<<endl;
									break;
									
									case 7:
										system("cls");
										cout<<"菜单功能如下： \n";
										cout<<"1--------求表长；即L中数据元素的个数"<<endl;
										cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
										cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
										cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
										cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
										cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
										cout<<"7--------判空操作"<<endl;
										cout<<"8--------退出程序"<<endl;
									
										int g;
										g = Empty(L);
										if(g) cout<<"表为空 \n";
										else cout<<"表为不空 \n";
									  break;
									  
									  case 8:
									  		system("cls");
											cout<<"菜单功能如下： \n";
											cout<<"1--------求表长；即L中数据元素的个数"<<endl;
											cout<<"2--------按值查找元素，找具有给定关键字值的元素"<<endl;
											cout<<"3--------按位查找元素，找到表中第i个元素的值"<<endl;
											cout<<"4--------插入操作。在表中第i个位置插入指定元素e"<<endl;
											cout<<"5--------删除操作。删除表中第i个位置的元素，并用e返回删除元素的值"<<endl;
											cout<<"6--------输出操作。按前后顺序输出L中所有的值"<<endl;
											cout<<"7--------判空操作"<<endl;
											cout<<"8--------退出程序"<<endl;
				
									  	exit(0); 
									  	break;
									  	
									  	default:
									  		cout<<"非法输入！"<<endl;
									  	
		} 
	}
	
	return 0;
}

下面是运行结果：

上机试试就知道啦！
本人第一次在CSDN发表文章~