线性表-线性结构

用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;
}