Skip to content

Latest commit

 

History

History
382 lines (324 loc) · 8.86 KB

从零开始学习数据结构_线性表.md

File metadata and controls

382 lines (324 loc) · 8.86 KB

真正开始学习数据结构，可以说是从线性表开始。

我们知道每一个节点都可以保存用户数据，但选择不同的存储结构会导致具体实现程序的差异化，需要保证线性表工具对外接口的一致性。

一、线性表

是一种线性结构（理解为数组），数据结构就是研究数据与数据之间的关系，存储结构；

就是数组的管理机制，通过控制头进行结构数据的存储和与之对应的操作；

线性表函数功能：

  • 初始化；
  • 销毁；
  • 查找、插入、删除、排序、修改；
  • 合并、拆分；

1.1 结构体

typedef int Type //Type 是用户自定义类型，想定义什么类型就定义什么类型，我在这拿 int 举例

typedef struct LINEAR{
    Type *data;  //存放数据的指针
    int count;   //存放数据的总元素个数
    int elemCount; //有效元素个数
}LINEAR;

有个核心的思想：Type 是用户自定义类型，根据不同场景创建自己的数据类型，把类型在业务中定义好，传给工具即可，工具并不关心你的业务、场景、只实现通用方法，谁来关心业务、场景呢？肯定是开发人员，谁开发谁定义数据类型即可，这样做出来的工具具备：通用性。

1.2 模型如下

二、分析

其实对线性表的操作和对数组的操作极为类似；

并且这个还可以自动增长空间，就是在写一个函数的问题，这个函数的思想 :

  1. 先申请一个更大的空间；
  2. 在将原空间数据进行拷贝过来；
  3. 在释放原先数组空间；
  4. 最后更改指针的指向，使其指向这个空间；

三、代码实现

C++ 程序实现，函数名字模仿 STL 中的函数名称，通过控制头进行统一管理：

3.1 代码如下

#ifndef _SEQ_LIST_H_
#define _SEQ_LIST_H_

#include<iostream>
#include<stdlib.h>
using namespace std;

#define DEFAULTE_SIZE    10

template<typename Type>
class SeqList{
public:
    SeqList(size_t sz = 0){
        count = sz > DEFAULTE_SIZE ? sz : DEFAULTE_SIZE;
        data = new Type[count];
        elemCount = 0;
    }
    SeqList(const SeqList &t);
    SeqList& operator=(const SeqList &t);
    ~SeqList(){
        delete []data;
    }
public:
    bool isEmpty()const{
        return elemCount == 0;
    }
    bool isFull()const{
        return elemCount >= count;
    }
public:
    bool push_back();  //尾部增加数据
    bool show_list()const; //显示线性表
    bool push_front(); //头插
    bool insert_val(); //根据值插入
    bool insert_pos(); //根据位置插入
    bool pop_back();   //删除尾
    bool pop_front();  //删除头
    bool delete_pos(); //根据位置删除
    bool delete_val(); //根据值删除
    int search_val();  //查找值
    Type search_pos(); //查找位置
    void sort();       //进行排序
    void clear();      //清空线性表
    void destroy();    //销毁函数，释放空间
    bool revrese();    //转置输出
private:
    Type *data;  //存放数据的指针
    int count;   //存放数据的总元素个数
    int elemCount; //有效元素个数
};

template<typename Type>
bool SeqList<Type>::push_back(){
    int number;
    if(isFull()){
        cout<<"线性表已满"<<endl;
        return 0;
    }

    cout<<"请输入要尾随的数字(-1结束输入)"<<endl;
    cin>>number;
    while(number != -1){
        data[elemCount++] = number;
        cin>>number;
    }
    return true;
}
template<typename Type>
bool SeqList<Type>::show_list()const{
    int i;

    for(i = 0; i < elemCount; i++){
        cout<<data[i]<<"->";
    }
    cout<<"NULL";
    cout<<endl;
    return true;
}
template<typename Type>
bool SeqList<Type>::push_front(){
    int number;
    int i;

    if(isFull()){
        cout<<"线性表已满"<<endl;
        return 0;
    }
    cout<<"请输入要头插的数字: ";
    cin>>number;
    for(i = elemCount-1; i >= 0; i--){
        data[i+1] = data[i];
    }
    elemCount++;
    data[0] = number;

    return 0;
}
template<typename Type>
bool SeqList<Type>::insert_val(){
    int number1;
    int number2;
    int i;
    int local = 0;

    if(isFull()){
        cout<<"线性表空间已满"<<endl;
        return 0;
    }
    cout<<"请输入要查找的位置数字:";
    cin>>number1;
    cout<<"请输入要插入的数字";
    cin>>number2;
    for(i = 0; i < elemCount; i++){
        if(number1 == data[i]){
            local = i;
        }else{
            local = elemCount;
        }
    }
    for(i = elemCount-1; i >= local; i--){
        data[i+1] = data[i];
    }
    elemCount++;
    data[local] = number2;

    return true;
}
template<typename Type>
bool SeqList<Type>::insert_pos(){
    int pos;
    int number;
    int i;

    if(isFull()){
        cout<<"线性表为空"<<endl;
        return 0;
    }
    cout<<"请输入要插入的位置: ";
    cin>>pos;
    cout<<"请输入要插入的数字: ";
    cin>>number;
    if(pos < 0 || pos > elemCount){
        return 0;
    }
    for(i = elemCount-1; i >= pos; i--){
        data[i+1] = data[i];
    }
    data[pos] = number;
    elemCount++;

    return true;
} 
template<typename Type>
bool SeqList<Type>::pop_back(){
    if(isEmpty()){
        return 0;
    }
    elemCount--;
    return true;
}
template<typename Type>
bool SeqList<Type>::pop_front(){
    int i;
    if(isEmpty()){
        return 0;
    }
    for(i = 1; i < elemCount; i++){
        data[i-1] = data[i];
    }
    elemCount--;

    return true;
}
template<typename Type>
bool SeqList<Type>::delete_pos(){
    int pos;
    
    if(isEmpty()){
        return 0;
    }
    cout<<"请输入要删除数字的位置: ";
    cin>>pos;
    int i;

    for(i = pos+1; i < elemCount; i++){
        data[i-1] = data[i];
    }
    elemCount--;

    return true;
}
template<typename Type>
bool SeqList<Type>::delete_val(){
    int number;

    if(isEmpty()){
        return 0;
    }
    cout<<"请输入要删除的数字: ";
    cin>>number;
    int i;
    int local = 0;

    for(i = 0; i < elemCount; i++){
        if(data[i] == number){
            local = i;
        }
    }
    for(i = local+1; i < elemCount; i++){
        data[i-1] = data[i];
    }
    elemCount--;

    return true;
}
template<typename Type>
int SeqList<Type>::search_val(){
    int number;

    cout<<"请输入要查找的数字: ";
    cin>>number;
    int i;

    for(i = 0; i < elemCount; i++){
        if(data[i] == number){
            return i;        
        }
    }

    return -1;
}
template<typename Type>
Type SeqList<Type>::search_pos(){
    int pos;

    cout<<"请输入要查找数字的位置:";
    cin>>pos;

    if(pos < 0 || pos >= elemCount){
        return -1;
    }
    
    return data[pos];
}
template<typename Type>
void SeqList<Type>::sort(){
    int i;
    int j;
    Type tmp;

    for(i = 0; i < elemCount; i++){
        for(j = 0; j < elemCount-i-1; j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}
template<typename Type>
void SeqList<Type>::clear(){
    elemCount = 0;
}
template<typename Type>
void SeqList<Type>::destroy(){
    
}
template<typename Type>
bool SeqList<Type>::revrese(){
    if(isEmpty()){
        return false;
    }

    int i;
    Type tmp;
    for(i = 0; i < elemCount/2; i++){
        tmp = data[i];
        data[i] = data[elemCount-i-1];
        data[elemCount-i-1] = tmp;
    }
    return true;
}
#endif

3.2 测试代码

#include<iostream>
#include"seqlist.h"
using namespace std;

int main(void){
    SeqList<int> sl;
    
    sl.push_back();
    sl.show_list();
    sl.push_front();
    sl.show_list();
    sl.pop_back();
    cout<<"尾删节点如下:"<<endl;
    sl.show_list();
    sl.sort();
    cout<<"线性表排序后如下: "<<endl;
    sl.show_list();
    sl.destroy();

    return 0;
}

3.3 运行结果

四、说明

原创文章链接：从零开始学习数据结构-->线性表