数据结构探险之线性表篇（上）：顺序表-白红宇

数据结构探险之线性表篇

将要学到得：

线性表（链表）

什么是线性表？

线性表是n个数据元素的有限序列

线性表

排列之后成线性展开。

有限 & 数据元素（简单 & 复杂） & 序列

线性表的分类:

线性表的分类

数组：访问速度快，搜索能力强。与内存地址相关

链表 & 线性链表 & 线性表的链式表达

链字：重要。

应用场景：通讯录。加，删，搜索。

一元多项式：

一元多项式

只有x一个变量x。一元。p0~pn为系数。多项。

线性表编码

前驱后继。前一个元素 & 后一个元素

要求：

线性表要求

在第i个位置插入元素。那么后面的所有都要后移

在第i个位置删除元素。那么后面的所有都要前移

//list.h#ifndef LIST_H#define LIST_Hclass 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 
     
      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_iSize)    {        return false;    }    //先把i及之后的先移动    //for (int k = i;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
        
         using namespace std;#include 
         
          //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:"<
          
           ListLength()<
           
            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:"<
            
             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 
     
      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
      
       printCoordinate();    }}bool List::ListInsert(int i, Coordinate *e){    if (i<0 || i > m_iSize)    {        return false;    }    //先把i及之后的先移动    //for (int k = i;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
        
         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 
         
          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 
          
           using namespace std;#include 
           
            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:"<
            
             ListLength()<
             
              ListInsert(0, &e1); cout << "length:" << list1->ListLength() << endl; list1->ListInsert(1, &e2); list1->ListInsert(2, &e3); list1->ListTraverse(); delete list1; system("pause"); return 0;}

运行结果：

运行结果