用C++实现线性表线性结构
List.h
#pragma once
#include<iostream>
#include<vector>
typedef int ElemType;
#define MaxSize 30
struct List {
ElemType * data; //定义数据
int len; //给定长度
int size; //定义初始化大小
};
class sqList {
public:
List L;
sqList();
~sqList();
public:
void InitList(List &L); //初始化一个线性表
//清空线性表
void ClearList(List &L);
//销毁一个线性表
void DestroyList(List &L);
//判断线性表是不是为空
bool isListEmpty(List L);
//返回线性表的长度
int ListLength(List L);
//返回线性表上指定位置的元素，通过e返回
int GetElem(List L, int i, int &e);
//判断一个元素是不是列表中的某一个值
bool isElemList(List L, int e, std::vector<int>& i);
//返回非第一个元素的前一个元素值
bool PriorElem(List L, int cur_e, std::vector<int> &pri_e);
//返回非最后一个元素的后一个元素值
bool NextElem(List L, int cur_e, std::vector<int> &next_e);
//指定的位置插入某个元素
bool ListInsert(List &L, int i, int e);
//指定位置删除某个元素
bool ListDelete(List &L, int i);
//连接两个线性表，出去重复的部分
void Connect_Two_List(List a, List b, List &c);
//打印线性表
void printLst(List L);
};
List.cpp
#include"list.h"
#include <vector>
sqList::sqList(){
InitList(L);
}
sqList::~sqList() {
ClearList(L);
DestroyList(L);
}
void sqList::InitList(List &L) {
L.data = new ElemType[5];
L.data[0] = 9;
L.data[1] = 3;
L.data[2] = 8;
L.data[3] = 12;
L.data[4] = 16;
L.len = 5;
L.size = 5;
}
void sqList::ClearList(List &L) {
L.len = 0;
delete[] L.data;
L.data = NULL;
L.data = new ElemType[L.size];
}
void sqList::DestroyList(List &L) {
L.len = 0;
L.data = 0;
delete[] L.data;
L.data = NULL;
}
bool sqList::isListEmpty(List L) {
if (L.len != 0)
return false;
return true;
}
int sqList::ListLength(List L) {
return L.len;
}
int sqList::GetElem(List L, int i, int &e) {
if (i < 0 || i > L.len)
return -1;
e = L.data[i];
return 0;
}
bool sqList::isElemList(List L, int e, std::vector<int>& i) {
bool flag = isListEmpty(L);
if (flag)
return false;
for (int k = 0; k < L.len; k++) {
if (L.data[k] == e)
i.push_back(k);
}
if (0 == i.size())
return false;
return true;
}
bool sqList::PriorElem(List L, int cur_e, std::vector<int> &pri_e) {
std::vector<int> i;
bool flag = isElemList(L, cur_e, i);
if (flag) {
for (int k = 0; k < i.size(); k++) {
if (i[k] > 0 && i[k] <= L.len) //非第一个元素
pri_e.push_back(L.data[i[k] - 1]);
}
}
else
return false;
return true;
}
bool sqList::NextElem(List L, int cur_e, std::vector<int> &next_e) {
std::vector<int> i;
bool flag = isElemList(L, cur_e, i);
if (flag) {
for (int k = 0; k < i.size(); k++) {
if (i[k] < L.len) //非最后元素
next_e.push_back(L.data[i[k]]+1);
}
}
else
return false;
return true;
}
bool sqList::ListInsert(List &L, int i, int e) {
//插入的位置不合法
if (i < 1 || i > L.len + 1)
return false;
int j = 0;
//重新分配空间，因为插入的元素
if (L.len == L.size) {
//保存之前的内容
ElemType *p = new ElemType[L.len];
for (int j = 0; j < L.len;j++) {
p[j] = L.data[j];
}
//扩大容量
L.size += 1;
delete[] L.data;
//重新分配内存
L.data = new ElemType[L.size];
//L.len = L.size;
//恢复之前的数据
for (j = 0; j < L.len; j++) {
L.data[j] = p[j];
}
}
L.len++;
for (int k = L.len; k > i-1; k--) {
L.data[k] = L.data[k-1];
}
L.data[i-1] = e;
L.len+=1;
return true;
}
bool sqList::ListDelete(List &L, int i) {
if (i < 1 || i > L.len)
return false;
for (int k = i-1; k < L.len; k++) {
L.data[k] = L.data[k+1];
}
L.len--;
return true;
}
//合并两个链表
/*
* 1.
*/
void sqList::Connect_Two_List(List a, List b, List &c) {
//预处理链表C
c.len = c.size = a.len + b.len;
c.data = new ElemType[c.size];
int i = 0;
int j = 0;
int k = 0;
while (i <= a.len - 1 && j <= b.len - 1) {
if (a.data[i] < b.data[j]) {
c.data[k++] = a.data[i++];
}
else if (a.data[i] > b.data[j]) {
c.data[k++] = b.data[j++];
}
else {
c.data[k++] = a.data[i++];
j++;
--c.len;
}
}
while (i <= a.len - 1)
{
c.data[k++] = a.data[i++];
}
while (j < b.len - 1)
{
c.data[k++] = b.data[j++];
}
}
void sqList::printLst(List L) {
if (L.len <= 0)
return;
for (int i = 0; i < L.len; i++)
std::cout << L.data[i] << " ";
std::cout << std::endl;
}
测试程序main.cpp
#include<iostream>
#include"List.h"
int main() {
sqList sqL;
//1、创建一个链表
bool flag = sqL.isListEmpty(sqL.L);
if (!flag)
std::cout << "链表非空！" << std::endl;
else
return 0;
//2、打印链表
sqL.printLst(sqL.L);
//3、获取链表中特定的元素
int e;
sqL.GetElem(sqL.L, 3, e);
printf("%d\n", e);
//4、获取链表长度
int len = sqL.ListLength(sqL.L);
printf("%d\n", len);
//5、判断某一个元素是不是链表中的元素
std::vector<int> elem;
bool isElem = sqL.isElemList(sqL.L, 8, elem);
if (isElem)
std::cout << 8 << " is a elem in List, has " << elem.size() << " number"<< std::endl;
//6、获取某一元素的前一个元素
std::vector<int> pri_e;
bool pElem = sqL.PriorElem(sqL.L, 8, pri_e);
if (pElem)
{
for (int i = 0; i < pri_e.size(); i++)
{
std::cout << pri_e[i] << " ";
}
}
//7、获取某一个元素的后一个元素
std::vector<int> next_e;
bool nElem = sqL.NextElem(sqL.L, 8, next_e);
if (nElem)
{
for (int i = 0; i < next_e.size(); i++)
{
std::cout << next_e[i] << " ";
}
}
//8、线性表插入元素
int inum = 100;
sqL.ListInsert(sqL.L, 4, inum);
sqL.printLst(sqL.L);
//9、线性表删除元素
sqL.ListDelete(sqL.L, 4);
sqL.printLst(sqL.L);
//10、链接两个线性表
sqList a;
a.ClearList(sqL.L);
for (int i = 0; i < 6; i++)
a.ListInsert(a.L, i, i*2);
sqList c;
sqL.Connect_Two_List(a.L, sqL.L, c.L);
c.printLst(c.L);
return 0;
}
