线性表运算--顺序存储结构实现

对于线性表我们应掌握如下要点：

1、  掌握线性表的结构特点：顺序存储和链式存储。

2、  掌握线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度等运算在顺序存储结构和链式存储结构上的实现。

顺序存储具有随机访问的特点，而链式存储具有顺序访问的特点。

对于不同的应用我们应当选择不同的结构。

顺序结构实现源代码如下：

HList.h  //线性表头文件定义
//数据结构头文件在定义，
//链表的头文件
#ifndef  _HLIST_H_
#define  _HLIST_H_
//#define  M_error -1 
#include"stdlib.h"
#define Length_Size 100
#define add_Length 10
typedef int Element; 
struct Link
{
    Element *p;            //链表表示的物理线形表
    Element leg   ;        //线形表的当前长度
    Element list_size;     //线形表分配的数据的长度

};
//定义一个函数指针类型P_ptr  
//用于compare();比较函数的调用
typedef bool (*P_ptr)(Element &a,Element &b);  

//定义一个函数指针类型P_Vs
typedef bool (*P_Vs)(Element &a,Element &b);

//初始化一个线形表
//成功返回ture 失败返回false;
bool InitList(Link &L);  

//销毁一个线形表
//显形表不存在提示错误
//销毁成功返回true,销毁失败返回false;
void DestroyList(Link &L);

//线形表不存在提示错误
//线形表存在清空
//清空成功返回ture,清空失败返回false;
bool ClearList(Link &L);

//线形表是否为空
//线形表存在不为空返回ture,线形表存在为空返回false
bool IsLink_Empty(Link &L);

//线形表存在，返回线形表数据元素的长度

int Get_Link_Length(Link &L);

//用e获得线形表中第i个元素
//前提线形表已经存在
//获得成功返回ture;获得非法，提示错误
bool Get_element(Link &L,int i,Element &e);

//线形表存在，e在线形表中第一个满足compare()
//条件的元素，若不满足，则提示错误，若不存在则提示
int Get_Compare(Link &L,Element &e,P_ptr p);

//获得前驱
//前提L存在，若cur是线形表中的元素，且cur不是第一元素，则返回
//cur的前面一个元素，若找不到则返回错误，
//若找到用pre_e返回，返回 ture
bool Get_Prior_Elm(Link &L,Element &cur,Element &pre_e);

//获得后继，
//前提L存在，若 cur是线形表中的元素，且cur不是第一元素，则返回
//cur的后面一个元素，若找不到则返回错误，
//若找到用next_e返回，返回为ture
bool Get_Next_Elm(Link &L,Element &cur,Element &next_e);

//链表存在，
//在链表的第i个元素前插入一个元素e。
//插入范围从i=1,到从末尾插入
//插入成功返回ture,失败返回错误提示
bool List_Insert(Link &L,int i,Element &e);

//链表存在，将链表中的第i个指定元素删除，
//删除成功返回ture,删除不合法或者错误返回false;
bool List_Delete(Link &L,int i);

//线形表存在，依次对线形表的每个元素调用vist();
//vist(),操作失败则返回false,操作成功返回ture;
bool ListTraverse(Link &L,P_Vs visit,Element &e);

//compare()函数的声明
bool Compare(Element &a,Element &b);


//输出打印线性表中的所有值
void Print_Link(Link &L);

bool visit(Element &a,Element &b);

#endif   //_HLIST_H_

HList.cpp

HList.cpp     //线性表实现文件

//数据结构在定义实现文件
//数据结构头文件在定义，
#include<iostream>
#include"HList.h"
//初始化一个线形表，首选默认调用
//成功返回ture 失败返回false;   1
bool InitList(Link &L)
{
    L.p = (Element*)malloc(Length_Size*sizeof(Element)); //分配100个元素的存储空间
    if(!L.p)
    {
        std::cout<<"内存空间分配失败"<<std::endl;
        return false;

    }
    else
    {
        L.list_size = Length_Size;  //初始分配量
        L.leg = 0;                 //当前线形表内容长度
        int i = 0;
        for(;i<6;i++)
        {
            L.p[i] = i+1;
            
        }
        L.leg = 6;
        return true;
    }
    
}


//销毁一个线形表  最后自动调用
//销毁成功返回true,销毁失败返回false;    2
void DestroyList(Link &L)
{
        L.list_size = 0;
        L.leg = 0;
        free(L.p);
}

//线形表存在清空
//清空成功返回ture,清空失败返回false;    3
bool ClearList(Link &L)               
{
    if (L.leg>0)
    {
        L.leg = 0;
        return true;

    }
    else if(0==L.leg)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//线形表是否为空
//线形表存在不为空返回ture,线形表存在为空返回false      4
bool IsLink_Empty(Link &L)      
{
    if(0 == L.leg && L.p!=NULL )
    {
        return true;
    }
    else 
    {
        return false;

    }
}

//线形表存在，返回线形表数据元素的长度   5
int Get_Link_Length(Link &L)    
{
    if (L.p!=NULL)
    {
        return L.leg;
    }
    else
    {
        return -2;
    }
}

//用e获得线形表中第i个元素
//获得成功返回ture;获得非法，提示错误          6
bool Get_element(Link &L,int i,Element &e)
{
    if(L.p!=NULL &&L.leg!=0 && 0<i &&i<=L.leg)
    {
        e = L.p[i-1];
        return true;
    }
    else if (L.leg == 0)
    {
        std::cout<<"线性表为空"<<std::endl;
        return false;
    }
    else if(i<1||i>L.leg)
    {
        std::cout<<"i值不合法"<<std::endl;
        return false;
    }
    else
    {
        return false;
    }

}

//b为比较元素e
//a为线性表元素
bool Compare(Element &a,Element &b)
{
    if (a>b)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//线形表存在，e在线形表中第一个满足compare()
//条件的元素，若不满足，则提示错误，若不存在则提示
int Get_Compare(Link &L,Element &e,P_ptr p)
{
    int i=0;
    if(0 == L.leg)
    {
        return -1;
    }
    else
    {
        for(;i<L.leg;i++)
       {
           if(p(L.p[i],e))
           {
               return i+1;
           }
       }
        return -2;
    }
}
//获得前驱
bool Get_Prior_Elm(Link &L,Element &cur,Element &pre_e)
{
    int i = 1;
    if(0 ==L.leg)
    {
        std::cout<<"线性表为空，无法完成操作"<<std::endl;
        return false;
    }
    else if (L.p[0] == cur)
    {
        std::cout<<"cur为线性表中第一个元素，没有前驱"<<std::endl;
        return false;
    }
    else
    {
        for(;i<=L.leg;i++)
        {
            if(L.p[i]==cur)
            {
                pre_e = L.p[i-1];
                return true;
            }
            
        }
        std::cout<<"输入元素不存在"<<std::endl;
        return false;
    }

}

//获得后继，
bool Get_Next_Elm(Link &L,Element &cur,Element &next_e)
{
    int i = 0;
    if(0 ==L.leg)
    {
        std::cout<<"线性表为空，无法完成操作"<<std::endl;
        return false;
    }
    else if (L.p[L.leg-1] == cur)
    {
        std::cout<<"cur为线性表中最后一个元素，没有后继"<<std::endl;
        return false;
    }
    else
    {
        for(;i<L.leg-1;i++)
        {
            if(L.p[i]==cur)
            {
                next_e = L.p[i+1];
                return true;
            }
        }
    std::cout<<"输入元素不存在"<<std::endl;
    return false;
    }
}



bool List_Insert(Link &L,int i,Element &e)
{
    int j=L.leg;
    Element* new_p;
    if(i<1&&i>L.leg+1)
    {
        std::cout<<"i值不合法"<<std::endl;
        return false;

    }
    if(L.leg ==L.list_size)//内存不足，分配空间
    {
        new_p = (Element*)realloc(L.p,(L.list_size+add_Length)*sizeof(Element));
        if(!new_p)
        {
            std::cout<<"内存扩展失败"<<std::endl;
            return false;
        }
        L.p = new_p;
    }
    for(;j>=i;j--)
    {
        L.p[j]=L.p[j-1];
    }

    L.p[i-1] = e;
    L.leg++;

    return true; 
}


bool List_Delete(Link &L,int i)
{
    if(0==L.leg)
    {
        std::cout<<"线性表为空，无法执行删除操作"<<std::endl;
        return false;
    }
    else
    {
        int j = i;
        if(1<=i&&i<=L.leg)
        {
            while(j<L.leg)
            {
                L.p[j-1] = L.p[j];
                j++;
            }
            L.leg--;
            return true;
        }
        else if (i<1||i>L.leg)
        {
            std::cout<<"i值输入不合法"<<std::endl;
            return false;
        }
        else
        {
            return false;
        }
    }
}

bool visit(Element &a,Element &b)
{
    if(a<=b)
    {
        return false;
    }
    else
    {
        return true;
    }
}
//测试，；依次对元素调用visit函数
//有一个不满足则返回false
bool ListTraverse(Link &L,P_Vs visit,Element &e)
{
    if(0==L.leg)
    {
        std::cout<<"线性表为空"<<std::endl;
        return false;
    }
    else
    {
        while(L.leg>=1)
        {
            if(!visit(L.p[L.leg-1],e))
            {
                return false;
            }
            L.leg--;
        }
    }
    return true;

}


void Print_Link(Link &L)
{
    int i = 1;
    for(;i<=L.leg;i++)
    {
        std::cout<<L.p[i-1]<<" ";
    }
}