抱歉,你查看的文章不存在

数据结构探险之线性表篇(上):顺序表

数据结构探险之线性表篇

将要学到得:

  • 线性表(链表)

什么是线性表?

线性表是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;
}

运行结果:

运行结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

有趣的Python

0 篇文章106 人订阅

相关文章

来自专栏算法修养

浙江工业大学校赛 竹之书(大数,同余定理)

竹之书 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

3128
来自专栏懒人记的专栏

如何用 Go 实现单链表

每节运煤车就是单链表里的元素,每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连,作为单链表运煤车,从1号车厢开始,每节车厢都知道后面拉着哪一节车厢,却不...

4930
来自专栏Flutter入门到实战

老司机带你重构Android的v4包的部分源码

版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/a08d754944c4

1941
来自专栏数据结构与算法

P1967 货车运输

题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

3349
来自专栏西二旗一哥

Conclusion of objective-C structure

1223
来自专栏码匠的流水账

聊聊flink的InputFormatSourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/envi...

1702
来自专栏小樱的经验随笔

BZOJ 3097: Hash Killer I【构造题,思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

2146
来自专栏函数式编程语言及工具

FunDA(6)- Reactive Streams:Play with Iteratees、Enumerator and Enumeratees

    在上一节我们介绍了Iteratee。它的功能是消耗从一些数据源推送过来的数据元素,不同的数据消耗方式代表了不同功能的Iteratee。所谓的数据源就是我...

2089
来自专栏函数式编程语言及工具

PICE(5):MongoDBStreaming - gRPC -MGO Service

  我在前面提到过MongoDB不支持像SQL般字符式的操作指令,所以我们必须对所有的MongoDB操作指令建立protobuf类型才能支持MongoDB指令的...

1434
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。 * Modify homegarden data set with ass...

4744

扫码关注云+社区

领取腾讯云代金券