数据结构探险之线性表篇
将要学到得：
- 线性表（链表）
什么是线性表？
线性表是n个数据元素的有限序列
线性表
排列之后成线性展开。
有限 & 数据元素（简单 & 复杂） & 序列
线性表的分类:
线性表的分类
- 数组：访问速度快，搜索能力强。与内存地址相关
- 链表 & 线性链表 & 线性表的链式表达
链字：重要。
应用场景：通讯录。加，删，搜索。
一元多项式：
一元多项式
只有x一个变量x。一元。p0~pn为系数。多项。
线性表编码
前驱后继。前一个元素 & 后一个元素
要求：
线性表要求
- 在第i个位置插入元素。那么后面的所有都要后移
- 在第i个位置删除元素。那么后面的所有都要前移
//list.h
#ifndef LIST_H
#define LIST_H
class List
{
public:
List(int size);
~List();
void CleanList();
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);
private:
int *m_pList;
int m_iSize;
int m_iLength;
};
#endif
//list.cpp:
#include "List.h"
#include <iostream>
using namespace std;
List::List(int size)
{
m_iSize = size;
m_pList = new int[m_iSize];
m_iLength = 0;
}
List::~List()
{
delete []m_pList;
m_pList = NULL;
}
void List::CleanList()
{
m_iLength = 0;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
else
{
return 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
{
*preElem = m_pList[--temp];
return true;
}
}
}
bool List::NextElem(int *currentElem, int *nextElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else
{
if (temp == --m_iLength)
{
return false;
}
else
{
*nextElem = m_pList[++temp];
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_iSize)
{
return false;
}
//先把i及之后的先移动
//for (int k = i;k<m_iLength;k++)//这样会导致覆盖掉
for (int k = m_iLength; k>=i; k--)
{
m_pList[k + 1] = m_pList[k];
}
m_pList[i] = *e;
m_iLength++;
return true;
}
//先删除再移动相应的元素(从i+1个逐次往前移)
bool List::ListDelete(int i, int *e)
{
if (i<0 || i >=m_iSize)
{
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;
}
//main.cpp:
#include "List.h"
#include <iostream>
using namespace std;
#include <stdlib.h>
//BOOL InitList(List **list);//创建线性表
//
//void DestroyList(List *list);//销毁线性表
//
//void CleanList(List *list);//清空线性表
//
//BOOL ListEmpty(List *list);//判断线性表是否是空
//
//int ListLength(List *list);//获取线性表长度
//
//BOOL GetElem(List *list, int i, Elem *e);//获取指定元素
//int LocateElem(List *list, Elem *e);//寻找第一个满足e的数据元素的位序
//BOOL PriorElem(List *list, Elem *currentElem, Elem *preElem);//寻找指定元素的前驱
//BOOL NextElem(List *list, Elem *currentElem, Elem *nextElem);//获取指定元素的后继
//BOOL ListInsert(List *list,int i, Elem *e);//在第i个位置插入元素
//BOOL ListDelete(List *list, int i, Elem *e); //删除第i个位置元素
//void ListTraverse(List *list); //遍历线性表
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);
cout <<"length:"<<list1->ListLength()<<endl;
list1->ListInsert(0, &e1);
cout << "length:" << list1->ListLength() << endl;
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->ListDelete(0, &temp);
if (!list1->ListEmpty())
{
cout << "not empty" << endl;
}
list1->CleanList();
if (list1->ListEmpty())
{
cout << "empty" << endl;
}
list1->ListTraverse();
cout << "#" << temp << endl;*/
list1->ListTraverse();
list1->GetElem(0, &temp);
cout << "temp:" << temp << endl;
temp = 5;
cout << "index:"<<list1->LocateElem(&temp) << endl;;
list1->PriorElem(&e4, &temp);
cout << "proior:" << temp << endl;
list1->NextElem(&e4, &temp);
cout << "next:" << temp << endl;
delete list1;
system("pause");
return 0;
}
运行结果：
运行结果
升级版（int 升级对象元素）
//list.h
#ifndef LIST_H
#define LIST_H
#include "Coordiante.h"
class List
{
public:
List(int size);
~List();
void CleanList();
bool ListEmpty();
int ListLength();
bool GetElem(int i, Coordinate *e);
int LocateElem(Coordinate *e);
bool PriorElem(Coordinate *currentElem, Coordinate *preElem);
bool NextElem(Coordinate *currentElem, Coordinate *nextElem);
void ListTraverse();
bool ListInsert(int i , Coordinate *e);
bool ListDelete(int i , Coordinate *e);
private:
Coordinate *m_pList;
int m_iSize;
int m_iLength;
};
#endif
//list.cpp:
#include "List.h"
#include <iostream>
using namespace std;
List::List(int size)
{
m_iSize = size;
m_pList = new Coordinate[m_iSize];
m_iLength = 0;
}
List::~List()
{
delete []m_pList;
m_pList = NULL;
}
void List::CleanList()
{
m_iLength = 0;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
else
{
return false;
}
}
int List::ListLength()
{
return m_iLength;
}
bool List::GetElem(int i, Coordinate *e)
{
if (i<0 || i >= m_iSize)
{
return false;
}
*e = m_pList[i];
return true;
}
int List::LocateElem(Coordinate *e)
{
for(int i=0;i<m_iLength;i++)
{
if (m_pList[i] == *e)
{
return i;
}
}
return -1;
}
bool List::PriorElem(Coordinate *currentElem, Coordinate *preElem)
{
int temp = LocateElem(currentElem);
if (temp == -1 )
{
return false;
}
else
{
if (temp == 0)
{
return false;
}
else
{
*preElem = m_pList[--temp];
return true;
}
}
}
bool List::NextElem(Coordinate *currentElem, Coordinate *nextElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else
{
if (temp == --m_iLength)
{
return false;
}
else
{
*nextElem = m_pList[++temp];
return true;
}
}
}
void List::ListTraverse()
{
for (int i=0;i<m_iLength;i++)
{
cout << m_pList[i] << endl;//已经完成了输出运算符重载
//m_pList->printCoordinate();
}
}
bool List::ListInsert(int i, Coordinate *e)
{
if (i<0 || i > m_iSize)
{
return false;
}
//先把i及之后的先移动
//for (int k = i;k<m_iLength;k++)//这样会导致覆盖掉
for (int k = m_iLength; k>=i; k--)
{
m_pList[k + 1] = m_pList[k];
}
m_pList[i] = *e;
m_iLength++;
return true;
}
//先删除再移动相应的元素(从i+1个逐次往前移)
bool List::ListDelete(int i, Coordinate *e)
{
if (i<0 || i >=m_iSize)
{
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;
}
//Coordinate.h
#ifndef COORDINATE_H
#define COORDINATE_H
#include <ostream>
using namespace std;
class Coordinate
{
friend ostream &operator<<(ostream &out, Coordinate &coor);
public:
Coordinate(int x = 0, int y = 0);
void printCoordinate();
bool operator==(Coordinate &coor);
private:
int m_iX;
int m_iY;
};
#endif
//Coordinate.cpp
#include "Coordiante.h"
#include <iostream>
using namespace std;
Coordinate::Coordinate(int x, int y)
{
m_iX = x;
m_iY = y;
}
void Coordinate::printCoordinate()
{
cout << "(" << m_iX << "," << m_iY << ")" << endl;
}
ostream &operator<<(ostream &out, Coordinate &coor)
{
out << "(" << coor.m_iX << "," << coor.m_iY << ")" << endl;
return out;
}
bool Coordinate::operator==(Coordinate &coor)
{
if(this->m_iX == coor.m_iX && this->m_iY == coor.m_iY)
{
return true;
}
else
{
return false;
}
}
//main.cpp:
//
#include "List.h"
#include <iostream>
using namespace std;
#include <stdlib.h>
int main()
{
//3 5 7 2 9 1 8
Coordinate e1(3,5);
Coordinate e2(5,7);
Coordinate e3(6,8);
Coordinate temp(0,0);
List *list1 = new List(10);
cout <<"length:"<<list1->ListLength()<<endl;
list1->ListInsert(0, &e1);
cout << "length:" << list1->ListLength() << endl;
list1->ListInsert(1, &e2);
list1->ListInsert(2, &e3);
list1->ListTraverse();
delete list1;
system("pause");
return 0;
}
运行结果：
运行结果
网友评论