list.h
#include <iostream>
using namespace std;
class List{
private:
int *m_pList;//指针指向线性表
int m_iSize;//线性表的大小
int m_iLength; //线性表存储的元素
public:
List(int size); //构造函数
~List(); //默认传递this指针
void ClearList();//清空当前线性表里的元素，不等于释放线性表的内存
bool ListEmpty(); //判断线性表是否为空
int ListLength(); // 获取线性表的长度
bool GetElem(int i,int *e); //获取指定的元素
int LocateElem(int *e); //获取指定元素的位置
bool PriorElem(int* currentElem, int* preElem);//获取元素的前驱
bool NextElem(int* currentElem, int* nextElem);//获取元素的后继
void ListTraverse(); //遍历线性表
bool ListInsert(int i,int* e);//插入
bool ListDelete(int i,int* e);//删除
};
list.cpp
#define _CRT_SECURE_N0_WARNINGS 1
//线性表
//线性表是n个数据元素的有限数列。
//分为1.顺序表（数组） 2. 链表（静态链表 单链表 循环链表 双向链表）
//应用场景 通讯录 一元多项式
//顺序表
/*
线性表——顺序表
3 5 7 2 9 1 8
前驱 后继
*/
/*
创建线性表 销毁
C语言
BOOL InitList(List** list) void DestoryList(List *list)
C++
构造函数 析构函数
*/
//要求：建表 清空 插入 删除 查找
#include"list.h"
List::List(int size)
{
m_iSize = size;
m_pList = new int[m_iSize];//分配内存 线性表的容量
m_iLength = 0;//初始情况下 元素为0
}
List::~List()
{
delete[]m_pList;
m_pList = NULL;
}
void List::ClearList()
{
m_iLength = 0;
}
bool List::ListEmpty()
{
return (m_iLength == 0) ? true : false;
}
int List::ListLength()
{
return m_iLength;
}
bool List::GetElem(int i, int *e)
{
if (i < 0 || i >= m_iSize)
return false;
*e=m_pList[i];
return true;
}
int List::LocateElem(int *e)
{
for (int i = 0; i < m_iLength; i++)
{
if (m_pList[i] == *e)
{
return i; //找到了
}
}
return -1;
}
bool List::PriorElem(int* currentElem, int* preElem)
{
int temp=LocateElem(currentElem);//找到当前元素的位置，依据位置判断是否具有前驱
if (temp == -1) //没找到当前元素
return false;
else //找到了
{
if (temp == 0) //找到当前元素为首元素 不存在前驱 返回错误值
return false;
else //找到存在前驱的元素 下标-1 ——>前驱
{
*preElem = m_pList[temp - 1];
return true;
}
}
}
bool List::NextElem(int* currentElem, int* nextElem)
{
int temp = LocateElem(currentElem);//找到当前元素的位置，依据位置判断是否具有后继
if (temp == -1) //当前元素不存在
return false;
else
{
if (temp == m_iLength-1) //当前元素没有后继 当前元素为最后一个元素时
return false;
else
{
*nextElem = m_pList[temp + 1];
return true;
}
}
}
void List::ListTraverse()
{
for (int i = 0; i < m_iLength; i++)
cout << m_pList[i] << endl;
}
bool List::ListInsert(int i, int* e)
{
if (i < 0 || i > m_iLength)
{
return false;
}
for (int k = m_iLength-1; k >=i; k--)
{
m_pList[k + 1] = m_pList[k];
}
m_pList[i] = *e;
m_iLength++; //更新线性表的长度
return true;
}
bool List::ListDelete(int i, int* e)
{
if (i < 0 || i>= m_iLength)
{
return false;
}
*e=m_pList[i];
for (int k = i + 1; k < m_iLength; k++)
{
m_pList[k-1] = m_pList[k];
}
m_iLength--;
return true;
}
test.cpp
#define _CRT_SECURE_N0_WARNINGS 1
#include<stdlib.h>
#include"list.h"
int main()
{
//3 5 7 2 9 1 8
int e1 = 3;
int e2 = 5;
int e3 = 7;
int e4 = 2;
int e5 = 9;
int e6 = 1;
int e7 = 8;
int temp=0;
//插入
List *list1 = new List(10);
list1->ListInsert(0, &e1);
list1->ListInsert(1, &e2);
list1->ListInsert(2, &e3);
list1->ListInsert(3, &e4);
list1->ListInsert(4, &e5);
list1->ListInsert(5, &e6);
list1->ListInsert(6, &e7);
list1->ListTraverse();
list1->GetElem(0, &temp);
cout << "temp:" << temp << endl;
temp = 5;
cout << list1->LocateElem(&temp) << endl;
list1->PriorElem(&e3, &temp); //前驱
cout << "temp:" << temp << endl;
list1->NextElem(&e3, &temp); //后继
cout << "temp:" << temp << endl;
delete list1;
system("pause");
return 0;
}
线性表_顺序表.png
