考研408-数据结构完整代码 线性表的顺序存储结构 - 顺序表

发布于：2025-03-14 ⋅ 阅读:(15) ⋅ 点赞:(0)

线性表的顺序存储结构 - 顺序表

1. 顺序表的定义

​ 用一组地址连续的存储单元依次存储线性表的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻

2. 顺序表的特点

  • 随机访问： 即通过首地址和元素序号可以在O(1) 时间内找到指定元素！
  • 存储密度高： 每个节点只存储数据节点！（链表还要存储指针）
  • 不宜与插入删除与扩容： 进行这些操作需要进行大量的元素移动操作！

3. 顺序表的相关代码（Dev-C++）

​ 本代码使用万能头文件，如果运行失败，请自行修改头文件！

  • 顺序表创建 - 静态分配
#include<bits/stdc++.h>
#define MAXSIZE 10 //最大长度
using namespace std;

typedef struct{
	int data[MAXSIZE]; //静态数组存放数据元素
	int length;
}SeqList;

//初始化顺序表
void InitSeqList(SeqList &L){
	for(int i = 0 ; i < MAXSIZE ; i++ ){
		L.data[i] = 0;
	}
	L.length = 0;
}

int main(){
	SeqList L;
	InitSeqList(L); 
	return 0;
}
  • 顺序表创建 - 动态分配
#include<bits/stdc++.h>
#define INITSIZE 10 //初始长度
using namespace std;

typedef struct{
	int *data; //动态分配数组的指针
	int length;
	int MAXSIZE; //最大长度
}SeqList;

//初始化顺序表
void InitList(SeqList &L){
	L.data = (int*)malloc(INITSIZE*sizeof(int));
	L.length = 0;
	L.MAXSIZE = INITSIZE;
	cout << "初始化链表最大长度为：" << L.MAXSIZE << endl; 
}

void IncreaseSize(SeqList &L, int len){
	int *p = L.data;
	L.data = (int *)malloc((L.MAXSIZE + len)*sizeof(int));
	for(int i = 0 ; i < L.length ; i ++){ //复制数据到新申请的区域
		L.data[i] = p[i];
	}
	L.MAXSIZE = L.MAXSIZE + len; //增加长度
	free(p);  //释放内存空间
	cout << "增加后链表最大长度为：" << L.MAXSIZE; 
}

int main() {
	SeqList L;
	InitList(L);
	int len;
	cout << "现在进行动态链表长度扩充：(请输入增加长度)："; 
	cin >> len;
	IncreaseSize(L,len);
	return 0;
}
  • 顺序表的插入

​ 顺序表插入可以分解为两个步骤：

​ · 从后向前遍历，将顺序表中第 i 个元素及以后的元素都向后移动一个位置。

​ · 将需要插入的元素 e 放入 L.data[i - 1] 的位置即可。

#include<bits/stdc++.h>
#define MAXSIZE 20
using namespace std;

typedef struct{
	int data[MAXSIZE];
	int length;
}SeqList;

void InitList(SeqList &L){
	for(int i = 0 ; i < MAXSIZE ; i++){
		L.data[i] = 0;
	}
	L.length = 5; //Test: L.length = 0; 这里初始化为长度为5，是为了下面输出顺序表可以看到 要不然测试的时候不会打印顺序表！
	cout << "初始化后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
}

bool ListInsert(SeqList &L, int i, int e){
	if(i < 1 || i > L.length + 1) return false; //检查要插入的位置是否合理
	if(L.length > MAXSIZE) return false; //检查长度是否允许继续插入
	for(int j = L.length ; j >= i ; -- j ){ //从后向前遍历，一次向后挪动一个位置
		L.data[j] = L.data[j - 1];
	}
	L.length ++; //记得增加表长
	L.data[i - 1] = e;
	cout << "插入元素后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
}

int main(){
	SeqList L;
	int i, e;
	InitList(L);
	cout << "请输入要插入的位置及元素：" << endl;
	cin >> i >> e; 
	ListInsert(L, i, e);
	return 0;	
}

​ 时间复杂度分析：

​ 最好情况：要在最后一个位置插入元素，那么不需要移动元素，时间复杂度为O(1)。

​ 最坏情况：要在表头插入一个元素，那么所有元素都需要向后移动一个位置，时间复杂度为O(n)。其中 n 为表长度。

​ 平均情况：要插入的元素插入到任何一个位置的概率相同，平均时间复杂度为O(n)。

  • 顺序表的删除

​ 顺序表的删除（这里指删除第 i 个位置的元素）可以分为两个步骤：

​ · 将第 i 个位置的元素赋值给 e。这个目的是传回，如果没必要的话其实可以不用这个步骤。

​ · 从 i 位置开始向后遍历，让后面的元素都向前移动，填补删除元素的位置。

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;

typedef struct{
	int data[MAXSIZE];
	int length;
}SeqList;

void InitList(SeqList &L){
	for(int i = 0 ; i < MAXSIZE ; ++ i){
		L.data[i] = 0;
	} 
	L.length = 5; //Test: L.length = 5;
	cout << "初始化后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
}

bool ListDel(SeqList &L, int i, int &e){ //这里的e只是为了把删除的元素带回
	if(i < 1 || i > L.length) return false; //检查合理性
	if(L.length == 0) return false;
	e = L.data[i - 1];
	for(int j = i ; j < L.length ; ++ j){
		L.data[j - 1] = L.data[j];
	}
	L.length --; //记得减少长度
	cout << "删除后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
	return true;
}

int main(){
	SeqList L;
	int i, e;
	InitList(L);
	cout << "请输入要删除第几个元素" << endl;
	cin >> i;
	if(ListDel(L, i, e)){
		cout << "删除成功！删除的元素为：" << e << endl; 
	}else{
		cout << "删除失败！" << endl;
	}
	return 0;
}

​ 时间复杂度分析：

​ 最好情况：删除表尾元素，那么不需要移动元素，时间复杂度为O(1)。

​ 最坏情况：删除表头元素，那么n - 1元素都需要向前移动一个位置，时间复杂度为O(n)。其中 n 为表长度。

​ 平均情况：删除任何一个位置的元素概率都相同，那么平均时间复杂度为O(n)。

  • 顺序表按位查找

​ GetElem(L, i, e) 函数，传入要查找的位号，即要查找第几个元素，e是为了带回该元素的值！

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;

typedef struct{
	int data[MAXSIZE];
	int length;
}SeqList;

void InitList(SeqList &L){
	for(int i = 0 ; i < MAXSIZE ; ++ i){
		L.data[i] = i;
	}
	L.length = 5; //Test: L.length = 5;
	cout << "初始化后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
}

int GetElem(SeqList &L, int i, int &e){
	if(i < 1 || i > L.length) return false;
	if(L.length == 0) return false;
	e = L.data[i - 1];
	return e;
}

int main(){
	SeqList L;int i;int e;
	InitList(L);
	cout << "请输入查找第几个元素：" << endl; 
	cin >> i;
	if(GetElem(L, i, e)){
		cout << "查找成功，该元素为：" << e << endl;
	}else{
		cout << "查找失败！" << endl; 
	}
	return 0;
}

​ 时间复杂度分析： O(1)，因为可以直接通过索引访问元素。

  • 顺序表按值查找

​ LocateElem(L, e, loc) 函数，传入要查找的元素值，loc 是为了带回该元素的位序！

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;

typedef struct{
	int data[MAXSIZE];
	int length;
}SeqList;

void InitList(SeqList &L){
	for(int i = 0 ; i < L.length ; ++ i){
		L.data[i] = i;
	}
	L.length = 5; //Test: L.length = 0;
	cout << "初始化后的顺序表" << endl;
	for(int i = 0 ; i < L.length ; ++ i){
		cout << L.data[i] << " "; 
	} 
	cout << '\n'; 
}

int LocateElem(SeqList &L, int e, int &loc){
	for(int i = 0 ; i < L.length ; ++ i){
		if(L.data[i] == e){
			loc = i + 1;
			return loc;
		}
	}
	return false;
}

int main(){
	SeqList L;int e;int loc;
	InitList(L);
	cout << "请输入要查找的数值" << endl;
	cin >> e;
	if(LocateElem(L, e, loc)){
		cout << "查找成功，该元素位于第" << loc << "个位置！" << endl;
	}else{
		cout << "查找失败！" << endl; 
	}
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布