顺序表
2022-03-02 本文已影响0人
lxr_
SqList.h
#pragma once
#define MAXSIZE 20
//函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef int ElemType; //元素类型为char
/*
优点： 存储密度大（结点本身所占存储量/结点结构所占存储量）
可以随机存取表中任一元素
缺点： --------> 链表
在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充
*/
//静态数组
typedef struct
{
ElemType elem[MAXSIZE];
int length;
}SqList_static;
//动态数组
typedef struct
{
ElemType* elem;
int length;
}SqList_dynamic;
//*************动态数组操作****************
//构造一个空的顺序表
Status InitSqlList(SqList_dynamic& L);
//销毁线性表
void DestroySqlList(SqList_dynamic& L);
//清空线性表
int ClearList(SqList_dynamic& L);
//求线性表的长度
int GetLength(SqList_dynamic L);
//判断线性表是否为空
bool IsEmpty(SqList_dynamic L);
//判断线性表是否存在
bool IsExist(SqList_dynamic L);
//取位置i处相应元素
int GetElem(SqList_dynamic L, int i, ElemType& e);
//查找（找到返回位置序号，未找到返回0）
int LocateElem(SqList_dynamic L, ElemType e);
//插入
int ListInsert(SqList_dynamic& L, int i, ElemType e);
//删除
int ListDelete(SqList_dynamic& L, int i);
//遍历
int ListTraverse(SqList_dynamic L);
//线性表合并
void ListUnion(SqList_dynamic& L1, SqList_dynamic L2);
//有序表合并
void ListMerge_sq(SqList_dynamic L1, SqList_dynamic L2, SqList_dynamic& L3);
SqList.cpp
#include "SqList.h"
#include <iostream>
using namespace std;
//构造一个空的顺序表
Status InitSqlList(SqList_dynamic& L)
{
L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
if (!L.elem) //内存分配失败
{
cout << "内存分配失败" << endl;
exit(OVERFLOW);
}
L.length = 0; //空表长度为0
cout << "线性表初始化成功" << endl;
return OK;
}
//销毁线性表
void DestroySqlList(SqList_dynamic& L)
{
if (L.elem)
{
delete[] L.elem; //释放存储空间,即归还这块内存的所有权给系统，如果后面访问可能会读到不确定的值，故最好置为NULL
L.elem = NULL;
cout << "已销毁L" << endl;
}
}
//清空线性表
int ClearList(SqList_dynamic& L)
{
if (!IsExist(L))
{
cout << "L不存在" << endl;
return ERROR;
}
L.length = 0; //将线性表的长度置为0
cout << "已清空L" << endl;
return OK;
}
//求线性表的长度
int GetLength(SqList_dynamic L)
{
if (!IsExist(L))
{
cout << "L不存在" << endl;
return ERROR;
}
return L.length;
}
//判断线性表是否为空
bool IsEmpty(SqList_dynamic L)
{
if (!IsExist(L))
{
cout << "L不存在" << endl;
return ERROR;
}
else if (!L.length)
{
cout << "L为空" << endl;
return true;
}
else
{
cout << "L不为空" << endl;
return false;
}
}
//判断线性表是否存在
bool IsExist(SqList_dynamic L)
{
if (L.elem)
{
//cout << "L存在" << endl;
return true;
}
else
{
//cout << "L不存在" << endl;
return false;
}
}
//取位置i处相应元素
int GetElem(SqList_dynamic L, int i, ElemType& e)
{
if (i<1 || i>L.length || (!IsExist(L))) //判断i值是否合理，若不合理，返回ERROR
{
cout << i << "值不合理或L不存在" << endl;
return ERROR;
}
else
{
e = L.elem[i - 1]; //第i-1的单元存储第i个数据（随机存取）
cout << i << "处的值为:" << e << endl;
}
return OK;
}
//查找（找到返回位置序号，未找到返回0）(平均查找长度（n+1）/2,n=L.length),则平均时间复杂度为O(n)
int LocateElem(SqList_dynamic L, ElemType e)
{
if (!IsExist(L))
{
cout << "L不存在" << endl;
return ERROR;
}
for (int i = 0; i < L.length; i++)
{
if (L.elem[i] == e)
{
cout << e << "对应的序号为：" << i + 1 << endl;
return i + 1;
}
}
return 0;
}
//插入（平均移动次数n/2,n=L.length）,则平均时间复杂度为O(n)
int ListInsert(SqList_dynamic& L, int i, ElemType e)
{
if (i < 1 || i > L.length + 1 || L.length == MAXSIZE || (!IsExist(L))) //插入位置不合法或者存储空间已满
{
cout << "插入位置不合法或L不存在" << endl;
return ERROR;
}
for (int j = L.length - 1; j >= i - 1; j--) //插入位置及之后的元素后移
{
L.elem[j + 1] = L.elem[j];
} //新元素e放入第i个位置
L.elem[i - 1] = e;
L.length++; //表长增1
cout << "插入成功" << endl;
return OK;
}
//删除(平均移动次数(n-1)/2,n=L.length),则平均时间复杂度为O(n)
int ListDelete(SqList_dynamic& L, int i)
{
if (i < 1 || i > L.length || (!IsExist(L)))
{
cout << "删除位置不合法或L不存在" << endl;
return ERROR;
}
for (int j = i - 1; j < L.length - 1; j++)
{
L.elem[j] = L.elem[j + 1];
}
L.length--;
return OK;
}
//遍历
int ListTraverse(SqList_dynamic L)
{
if (!L.length || (!IsExist(L)))
{
cout << "L为空或L不存在" << endl;
return ERROR;
}
for (int i = 0; i < L.length; i++)
{
cout << L.elem[i] << " ";
}
cout << endl;
return OK;
}
//线性表合并
void ListUnion(SqList_dynamic& L1, SqList_dynamic L2)
{
for (int i = 0; i < L2.length; i++)
{
if (!LocateElem(L1, L2.elem[i])) //未找到返回0
{
ListInsert(L1, L1.length + 1, L2.elem[i]); //插入
}
}
}
有序表合并：
有序表合并
1.比较L1和L2中当前指针指向的数据大小
2.将较小的数据插入新表
3.后移两个表的指针
4.回到第一步，直到有一个表的数据全部被插入到新表中
5.将另一个表中剩下的数据全部插入到新表
//有序表合并
void ListMerge_sq(SqList_dynamic L1, SqList_dynamic L2, SqList_dynamic& L3)
{
//指向顺序表的开头
int* p1 = L1.elem;
int* p2 = L2.elem;
//指向顺序表的末尾
int* p1_last = L1.elem + L1.length - 1;
int* p2_last = L2.elem + L2.length - 1;
while (p1 <= p1_last && p2 <= p2_last)
{
if (*p1 > * p2)
{
ListInsert(L3, L3.length + 1, *p2++);
}
else
{
ListInsert(L3, L3.length + 1, *p1++);
}
}
while (p1 <= p1_last)
{
ListInsert(L3, L3.length + 1, *p1++);
}
while (p2 <= p2_last)
{
ListInsert(L3, L3.length + 1, *p2++);
}
}
main.cpp
测试
#include "SqList.h"
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
SqList_dynamic L;
InitSqlList(L); //初始化L
IsEmpty(L); //判空
ListInsert(L, 1, 1); //第1个位置插入1
ListInsert(L, 2, 2); //第2个位置插入2
ListInsert(L, 3, 3);
cout << "L的长度为：" << GetLength(L) << endl;
ListTraverse(L);
ListInsert(L, 1, 0); //第1个位置插入0
ListTraverse(L); //遍历
ListDelete(L, 1); //删除第一个位置
ListTraverse(L); //遍历
int e;
GetElem(L, 3, e); //获取第3个位置元素并存入到e中
cout << "第3个位置元素为：" << e << endl;
ClearList(L); //清空线性表
IsEmpty(L);
DestroySqlList(L); //销毁线性表
IsEmpty(L);
ListInsert(L, 1, 0);
ListTraverse(L);
//----------线性表合并---------
SqList_dynamic L1, L2;
InitSqlList(L1);
InitSqlList(L2);
ListInsert(L1, 1, 7);
ListInsert(L1, 2, 5);
ListInsert(L1, 3, 3);
ListInsert(L1, 4, 11);
ListInsert(L2, 1, 2);
ListInsert(L2, 2, 6);
ListInsert(L2, 3, 3);
cout << "L1:" << endl;
ListTraverse(L1);
cout << "L2:" << endl;
ListTraverse(L2);
//合并
ListUnion(L1, L2);
ListTraverse(L1);
//------------有序表合并------------
SqList_dynamic L3, L4, L5;
InitSqlList(L3);
InitSqlList(L4);
InitSqlList(L5);
ListInsert(L3, 1, 1);
ListInsert(L3, 2, 7);
ListInsert(L3, 3, 8);
ListInsert(L4, 1, 2);
ListInsert(L4, 2, 4);
ListInsert(L4, 3, 6);
ListInsert(L4, 4, 8);
ListInsert(L4, 5, 10);
ListInsert(L4, 6, 11);
//合并
ListMerge_sq(L3, L4, L5);
ListTraverse(L5);
return 0;
}
