精华内容
下载资源
问答
  • 2019-10-03 11:38:52

    **

    线性表顺序存储完整代码

    **
    //顺序存储
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define MAXSIZE 20
    #define ERROR -1

    typedef int Position;
    typedef int ElementType;

    typedef struct LNode* PtrToLNode;
    struct LNode
    {
    ElementType Data[MAXSIZE];
    Position Last;
    };
    typedef PtrToLNode List;

    List L;

    //1.初始化
    List MakeEmpty()
    {
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;

    return L;
    

    }

    //2.创建顺序表
    void CreateList()
    {
    int i = 0, data = 0;
    printf(“输入一组正整数,以-1结束:\n”);
    scanf_s("%d", &data);

    while (data != -1 && L->Last < MAXSIZE)
    {
    	L->Data[i] = data;
    	L->Last++;
    	i++;
    	scanf_s("%d", &data);
    }
    printf("创建成功!\n");
    if (L->Last == MAXSIZE)
    	printf("表满!");
    

    }

    //3.查找
    Position Find(ElementType X)
    {
    Position i = 0;
    while (i <= L->Last && L->Data[i] != X)
    i++;
    if (i > L->Last)
    return ERROR;//查找失败
    else
    return i;//查找成功返回X的位置,即i
    }

    //4.插入
    bool Insert( ElementType X, int i)//在第i(i下标为i-1)个元素前插入新的元素 X
    {
    Position j;

    if (L->Last == MAXSIZE - 1)
    	printf("表满");
    if (i<1 || i>L->Last + 2)
    {
    	printf("插入位序不合法");
    	return false;
    }
    for (j = L->Last; j >= i + 1; j--)
    {
    	L->Data[j + 1] = L->Data[j];//将位序i及以后元素往后移动
    }
    L->Data[i - 1] = X;
    L->Last++;
    
    return true;
    

    }

    //5.删除
    bool Delete(int i)//从L中删除指定位序i的元素,i下标为i-1
    {
    Position j;

    if (i<1 || i>L->Last + 1)
    {
    	printf("输入该位序不合法");
    	return false;
    }
    
    for (j = i; j <= L->Last; j++)
    	L->Data[j - 1] = L->Data[j];
    
    L->Last--;
    return true;
    

    }

    //主函数
    int main()
    {

    int choice;
    
    while (1)
    {
    	printf("########################\n");
    	printf("1.初始化线线性表\n");
    	printf("2.创建线性表\n");
    	printf("3.查找\n");
    	printf("4.插入\n");
    	printf("5.删除\n");
    	printf("0.退出\n");
    	printf("########################\n");
    
    	printf("你的选择是:\n");
    	scanf_s("%d", &choice);
    
    	switch (choice)
    	{
    
    	case 1:
    	{
    
    
    		printf("1.初始化线线性表...\n");
    		MakeEmpty();
    		if (L->Last == 1)
    		{
    			printf("初始化成功!\n");
    			printf("线性表的长度:%d\n", L->Last);
    		}
    		break;
    	}
    
    	case 2:
    	{
    		printf("2.创建线性表...\n");
    		CreateList();
    		break;
    	}
    
    	case 3:
    	{
    		printf("3.查找...\n");
    		int x_1;//数值
    		printf("输入数值:\n");
    		scanf_s("%d\n", &x_1);
    
    		Find(x_1);
    
    		if (Find(x_1) == -1)
    			printf("查找失败\n");
    		else
    			printf("查找成功!位置是%d\n", Find(x_1)+1);
    		break;
    	}
    
    	case 4:
    	{
    		printf("4.插入...\n");
    		int x_2, position_1;
    		printf("输入数值:\n");
    		scanf_s("%d\n", &x_2);
    		printf("输入位置:\n");
    		scanf_s("%d\n", &position_1);
    
    		Insert(x_2, position_1);
    
    		if (Insert(x_2, position_1) == true)
    			printf("成功!\n");
    		if (Insert( x_2, position_1) == false)
    			printf("失败!\n");
    		break;
    	}
    
    	case 5:
    	{
    		printf("5.删除...\n");
    		int position_2;
    		printf("输入位置:\n");
    		scanf_s("%d\n", &position_2);
    
    		Delete(position_2);
    
    		if (Delete(position_2) == true)
    			printf("成功!\n");
    		if (Delete(position_2) == false)
    			printf("失败!\n");
    		break;
    	}
    
    	case 0:
    	{
    		return 0;
    		break;
    	}
    
    	default:
    		printf("选择有错,请重新选择\n");
    		break;
    
    	}
    
    	scanf_s("%c", &choice);
    }
    
    
    
    return 0;
    

    }

    #########C语言小白还有很多不足,欢迎大家批评指正######

    更多相关内容
  • 线性表顺序存储,此程序主要实现线性表顺序存储,有C++语言实现,还是比较轻易看得懂的!
  • 构造一个空的顺序表InitList_Sq; 初始化一个顺序表,将顺序表所有元素置为0 SetList_Sq 建立顺序表,给表各元素赋值SetList_Sq ...合并两个顺序表,即将一个顺序表接另一个顺序表之后Append_Sq
  • 线性表顺序存储与实现。采用顺序存储的方式实现线性表,并实现了一些基本功能,包括创建、销毁、清空、插入等一些常规的操作。
  • 线性表顺序存储结构,指的是用一段地址连续的 存储单元依次存储线性表的数据元素。 简单说就是内存找了一块地方,通过占位的形式,把一定内存空间给占了。 顺序存储结构的三个属性: 存储空间的起始位置 ...

    一、线性表

    1. 线性表:零个或多个数据元素的有限序列。
    2. 首先它是一个序列,也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最以后一个元素无后继,其他每个元素都有且一个前驱和后继。

    二、线性表的顺序存储结构

    1. 线性表的顺序存储结构,指的是用一段地址连续的 存储单元依次存储线性表的数据元素。
    2. 简单说就是在内存中找了一块地方,通过占位的形式,把一定内存空间给占了。
    3. 顺序存储结构的三个属性:
      1. 存储空间的起始位置
      2. 线性表的最大存储空间
      3. 线性表当前长度(元素的个数)

    三、顺序存储结构的实现

    #include <stdio.h>
    #include <stdlib.h>
    
    /*
     * 定义宏
     * LIST_LENGTH :存放初始长度
     * LIST_CREMENT :存放每次申请空间的大小
    */
    #define LIST_LENGTH 100
    #define LIST_CREMENT 20
    
    // 类型重定义
    typedef int tElem;      // 线性表元素的数据类型
    typedef tElem * pElem;  // 元素指针
    typedef struct List {
        pElem elem;         // 线性表存储元素
        int listLength;     // 线性表的长度
        int listSize;       // 线性表的空间大小
    } List;
    typedef enum Status     // 枚举数据
    {
        ok = 1,Error = 0
    } Status;
    
    
    /*
     * 初始化线性表
     * 步骤:
     *  使用 malloc 为线性表申请空间
     *  判断是否申请成功
     *  对线性表的长度和空间进行初始化
    */
    Status InitList(List * l)
    {
        l->elem = (pElem) malloc(sizeof(tElem) * LIST_LENGTH);
        if(l->elem == 0)
        {
            printf("空间申请失败!");
            return Error;
        }
    
        l->listLength = 0;
        l->listSize += LIST_LENGTH;
    }
    
    
    /*
     * 判断线性表长度
     * 步骤:
     *  长度为 0 输出线性表为空
     *  否则输出线性表的长度
    */
    void ListEmpty(List * l)
    {
        if(l->listLength == 0)
        {
            printf("线性表为空 \n");
        }
        else
        {
            printf("线性表的长度为 %d\n",l->listLength);
        }
    }
    
    
    /*
     * 在线性表的第 i 个位置插入元素 e
     * 步骤:
     *  判断参数是否合法,若位置 i 小于 0 或大于线性表的长度,则参数不合法。
     *  判断空间是否充足,用线性表长度和空间作比较,若长度大于或等于线性表的空间则表示空间不足,使用 realloc 重新为线性表申请空间。
     *  判断空间是否申请成功,若成功则修改线性表的空间大小。
     *  遍历线性表,将元素插入线性表中。
     *  修改线性表的长度,长度自增
     *
    */
    Status ListInsert(List * l,int i,tElem e)
    {
        if(i < 0 || i > l->listLength)
        {
            printf("ListInsert() 参数错误!\n");
            return Error;
        }
    
        if(l->listLength >= l->listSize)
        {
            l->elem = (pElem) realloc(l,sizeof(tElem) * LIST_CREMENT);
            if(l->elem == 0)
            {
                printf("空间申请失败!");
                return Error;
            }
            else
            {
                l->listSize += LIST_CREMENT;
            }
        }
    
        for(int j = l->listLength; j > i; j++)
        {
            l->elem[j] = l->elem[j - 1];
        }
        l->elem[i] = e;
        l->listLength++;
        return ok;
    }
    
    
    /*
     * 获取第 i 个元素
     * 步骤:
     *  判断参数是否合法,若位置 i 小于 0 或大于线性表的长度,则参数不合法。
     *  打印第 i 个元素
    */
    Status GetElem(List * l,int i)
    {
        if(i < 0 || i > l->listLength)
        {
            printf("ListInsert() 参数错误!\n");
            return Error;
        }
    
        printf("线性表第 %d 个元素是 %d\n",i,l->elem[i]);
        return ok;
    }
    
    
    /*
     * 获取元素 e 前一个元素
     * 步骤:
     *  初始化一个位置 i = -1,遍历线性表获取元素 e 的位置
     *  判断 i 的值:
     *      i = -1 表示元素 e 不在线性表中;
     *      i = 0 表示元素 e 是线性表的第一个元素,无前一个元素;
     *      否则打印元素 e 前一个元素
    */
    Status PriorElem(List * l,tElem e)
    {
        int i = -1;
        for(int j = 0; j < l->listLength; j++)
        {
            if(l->elem[j] == e) i = j;
        }
        if(i == -1)
        {
            printf("元素 %d 不在线性表中!\n",e);
            return Error;
        }
        else if (i == 0)
        {
            printf("元素 %d 是线性表的第一个元素,无前一个元素!\n",e);
            return Error;
        }
        else
        {
            printf("元素 %d 的前一个元素是:%d\n",e,l->elem[i-1]);
            return ok;
        }
    }
    
    
    /*
     * 获取元素 e 的后一个元素
     * 步骤:
     *  初始化一个位置 i = -1,遍历线性表获取元素 e 的位置
     *  判断 i 的值:
     *      i = -1 表示元素 e 不在线性表中;
     *      i 等于线性表长度减 1 表示元素 e 是线性表的最后一个元素,无后一个元素;
     *      否则打印元素 e 后一个元素
    */
    Status NextElem(List * l,tElem e)
    {
        int i = -1;
        for(int j = 0; j < l->listLength; j++)
        {
            if(l->elem[j] == e) i = j;
        }
        if(i == -1)
        {
            printf("元素 %d 不在线性表中!\n",e);
            return Error;
        }
        else if (i == l->listLength - 1)
        {
            printf("元素 %d 是线性表的最后一个元素,无后一个元素!\n",e);
            return Error;
        }
        else
        {
            printf("元素 %d 的后一个元素是:%d\n",e,l->elem[i+1]);
            return ok;
        }
    }
    
    
    /*
     * 遍历线性表
     * 步骤:
     *  判断线性表是否为空表。
     *  循环遍历,输出线性表索引和元素。
    */
    void ListTraverse(List * l)
    {
        if(l->listLength > 0)
        {
            for(int i = 0; i < l->listLength; i++)
            {
                printf("线性表的第 %d 个元素是:%d\n",i,l->elem[i]);
            }
        }
        else
        {
            printf("线性表为空!\n");
        }
    }
    
    /*
     * 删除第 i 个元素
     * 步骤:
     *  判断参数是否合法,若位置 i 小于 0 或大于线性表的长度,则参数不合法。
     *  遍历 i 后面线性表,用后一个元素替代前一个元素。
     *  修改线性表的长度。
    */
    Status ListDelete(List * l,int i)
    {
        if(i < 0 || i > l->listLength)
        {
            printf("ListInsert() 参数错误!\n");
            return Error;
        }
    
        for(int j = i; j < l->listLength; j++)
        {
            l->elem[j] = l->elem[j + 1];
        }
    
        l->listLength --;
        return ok;
    }
    
    
    /*
     * 清空线性表
     * 步骤:
     *  修改线性表的长度为 0
    */
    void ClearList(List * l)
    {
        l->listLength = 0;
    }
    
    /*
     * 销毁线性表
     * 步骤:
     *  释放线性表空间。
     *  修改线性表的长度为 0
     *  修改线性表空间大小为 0
    */
    void DestroyList(List * l)
    {
        free(l->elem);
        l->listLength = 0;
        l->listSize = 0;
    }
    
    int main() {
        List plist;
    
        // 初始化线性表
        InitList(&plist);
    
        // 判断线性表的长度
        printf("第一次判断线性表的长度:");
        ListEmpty(&plist);
        printf("\n");
    
        // 插入元素
        ListInsert(&plist,0,12);
        ListInsert(&plist,1,23);
        ListInsert(&plist,2,34);
        printf("第二次判断线性表的长度:");
        ListEmpty(&plist);
        printf("\n");
    
        // 获取第 i 个元素
        GetElem(&plist,1);
        printf("\n");
    
        // 获取元素 e 的前一个元素
        PriorElem(&plist,10);
        PriorElem(&plist,12);
        PriorElem(&plist,34);
        printf("\n");
    
        // 获取元素 e 的后一个元素
        NextElem(&plist,10);
        NextElem(&plist,34);
        NextElem(&plist,12);
        printf("\n");
    
        // 遍历线性表
        ListTraverse(&plist);
        printf("\n");
    
        // 删除第 i 个元素
        ListDelete(&plist,0);
        ListTraverse(&plist);
        printf("\n");
    
        // 清空线性表
        ClearList(&plist);
        ListTraverse(&plist);
        printf("\n");
    
        DestroyList(&plist);
        ListTraverse(&plist);
        printf("\n");
    
        return 0;
    }
    
    展开全文
  • 线性表的输入输出,插入删除,以及长度和置空操作。附带实验报告。
  • 数据结构(三)——基于顺序存储结构的线性表一、基于顺序存储结构的线性表实现1、顺序存储的定义线性表的顺序存储结构是用一段地址连续的存储单元依次存储线性表中的数据元素。2、顺序存储结构的操作使用一维数组实现...

    数据结构(三)——基于顺序存储结构的线性表

    一、基于顺序存储结构的线性表实现

    1、顺序存储的定义

    线性表的顺序存储结构是用一段地址连续的存储单元依次存储线性表中的数据元素。

    2、顺序存储结构的操作

    使用一维数组实现顺序存储结构。

    template

    class SeqList:public List

    {

    protected:

    T* m_array;//顺序存储空间

    int m_length;//当前线性表的长度

    };

    一维顺序存储结构可以是原生数组或是动态分配的空间。因此,根据空间分配的不同,分为静态线性表和动态线性表。

    (1)元素的获取

    顺序存储结构的元素获取操作:

    A、判断目标位置是否合法

    B、将目标位置作为数组下标获取元素

    bool get(int index, T& value)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //将目标位置作为下标获取元素

    value = m_array[index];

    }

    return ret;

    }

    (2)元素的插入操作

    顺序存储结构的元素插入操作:

    A、判断目标位置是否合法

    B、将目标位置后的所有元素向后移一位

    C、将新元素插入目标位置

    D、线性表长度增加1

    bool insert(int index, const T& value)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index <= m_length);

    ret = ret && ((m_length + 1) <= capacity());

    if(ret)

    {

    //将目标位置后的所有元素后移一个位置

    for(int i = m_length -1; index <= i; i--)

    {

    m_array[i+1] = m_array[i];

    }

    //将新元素插入到目标位置

    m_array[index] = value;

    //线性表长度加1

    m_length++;

    }

    return ret;

    }

    (3)元素的删除操作

    顺序存储结构的元素删除操作:

    A、判断目标位置是否合法

    B、将目标位置后的所有元素前移一个位置

    C、线性表长度减1

    bool remove(int index)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //将目标位置后的所有元素前移一位

    for(int i = index; i < m_length-1; i++)

    {

    m_array[i] = m_array[i+1];

    }

    //将线性表长度减1

    m_length--;

    }

    return ret;

    }

    (4)元素值的修改

    顺序存储结构中元素值的修改:

    A、判断目标位置是否合法

    B、修改目标位置元素的值

    bool set(int index, const T& value)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //修改目标位置元素的值

    m_array[index] = value;

    }

    return ret;

    }

    (5)线性表长度的获取

    顺序存储结构线性表的长度获取

    int length()const

    {

    //线性表长度

    return m_length;

    }

    (6)线性表的清空

    void clear()

    {

    //清空线性表

    m_length = 0;

    }

    (7)[]操作符重载

    //[]操作符重载

    T& operator[](int index)

    {

    //判断目标位置是否合法

    if((0 <= index) && (index < m_length))

    {

    //返回下标相应的元素

    return m_array[index];

    }

    else

    {

    THROW_EXCEPTION(IndexOutOfBoudsException, "Paramenter index is invalid...");

    }

    }

    //const对象的[]重载

    T operator[](int index)const

    {

    //转换为非const对象后使用[]操作

    return (const_cast&>(*this))[index];

    }

    (8)顺序存储结构空间的大小

    virtual int capacity()const = 0;

    由于存储空间在子类分配,因此为纯虚函数。

    3、顺序存储结构的抽象实现

    template

    class SeqList:public List

    {

    public:

    bool insert(int index, const T& value)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index <= m_length);

    ret = ret && ((m_length + 1) <= capacity());

    if(ret)

    {

    //将目标位置后的所有元素后移一个位置

    for(int i = m_length -1; index <= i; i--)

    {

    m_array[i+1] = m_array[i];

    }

    //将新元素插入到目标位置

    m_array[index] = value;

    //线性表长度加1

    m_length++;

    }

    return ret;

    }

    bool remove(int index)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //将目标位置后的所有元素前移一位

    for(int i = index; i < m_length-1; i++)

    {

    m_array[i] = m_array[i+1];

    }

    //将线性表长度减1

    m_length--;

    }

    return ret;

    }

    bool set(int index, const T& value)

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //修改目标位置元素的值

    m_array[index] = value;

    }

    return ret;

    }

    bool get(int index, T& value)const

    {

    //判断目标位置是否合法

    bool ret = (0 <= index) && (index < m_length);

    if(ret)

    {

    //将目标位置作为下标获取元素

    value = m_array[index];

    }

    return ret;

    }

    int length()const

    {

    //线性表长度

    return m_length;

    }

    void clear()

    {

    //清空线性表

    m_length = 0;

    }

    int find(const T& value)const

    {

    int ret = -1;

    //遍历线性表

    for(int i = 0; i < m_length; i++)

    {

    //如果找到元素,退出循环

    if(m_array[i] == value)

    {

    ret = i;

    break;

    }

    }

    return ret;

    }

    //[]操作符重载

    T& operator[](int index)

    {

    //判断目标位置是否合法

    if((0 <= index) && (index < m_length))

    {

    //返回下标相应的元素

    return m_array[index];

    }

    else

    {

    THROW_EXCEPTION(IndexOutOfBoudsException, "Paramenter index is invalid...");

    }

    }

    //const对象的[]重载

    T operator[](int index)const

    {

    //转换为非const对象后使用[]操作

    return (const_cast&>(*this))[index];

    }

    virtual int capacity()const = 0;

    protected:

    T* m_array;//顺序存储空间

    int m_length;//当前线性表的长度

    };

    4、顺序存储结构中数据元素移动的技巧

    数据元素的前移:

    将后面的数据元素向前移动,需要先将前面的数据元素前移,依次移动,直到最后一个数据元素前移,一般用于删除一个数据元素后将后面的数据元素前移。

    //将目标位置后的所有元素前移一位

    for(int i = index; i < m_length-1; i++)

    {

    m_array[i] = m_array[i+1];

    }

    数据元素的后移:

    将前面的数据元素向后移动,需要先将最后的数据元素后移,依次移动,直到第i个数据元素被后移,一般用于插入一个新的数据元素,需要先将插入位置后的所有数据元素后移,在位置处放入新的数据元素。

    //将目标位置后的所有元素后移一个位置

    for(int i = m_length -1; index <= i; i--)

    {

    m_array[i+1] = m_array[i];

    }

    5、原生数组实现的线性表

    使用原生数组作为顺序存储空间,使用模板参数确定数组大小。

    template

    class StaticList:public SeqList

    {

    public:

    StaticList()

    {

    this->m_array = m_space;//指定父类指针指向的空间

    this->m_length = 0;//设置初始长度

    }

    int capacity() const

    {

    return N;

    }

    protected:

    T m_space[N];//顺序存储空间,N为模板参数

    };

    需要父类的实现纯虚函数capacity()。

    6、动态分配空间实现的线性表

    使用动态申请的堆空间作为顺序存储空间,动态设置顺序存储空间的大小并确保重置顺序存储空间大小时的异常安全。

    函数异常安全要求不泄漏任何资源,不允许破坏数据。为了确保异常安全,在异常抛出时,必须确保:

    A、对象内的任何成员仍然能保持有效状态

    B、没有数据的破坏及资源泄漏。

    template

    class DynamicList:public SeqList

    {

    public:

    DynamicList(int capacity)

    {

    //申请动态空间

    this->m_array = new T[capacity];

    if(this->m_array)

    {

    this->m_length = 0;//初始长度

    this->m_capacity = capacity;//空间大小

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    int capacity() const

    {

    return m_capacity;

    }

    void resize(int capacity)

    {

    if(capacity != m_capacity)

    {

    T* array = new T[capacity];

    if(array)

    {

    int length = (this->length() < capacity ? this->length():capacity);

    for(int i = 0; i < length; i++)

    {

    array[i] = this->m_array[i];

    //如果抛出异常,原数组状态没有改变

    }

    T* temp = this->m_array;

    this->m_array = array;

    this->m_capacity = capacity;

    this->m_length = length;

    delete[] temp;

    //如果抛出异常,重置后的数组状态已经改变

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    }

    ~DynamicList()

    {

    delete[] this->m_array;//释放申请的动态空间

    }

    protected:

    int m_capacity;//顺序存储空间的大小

    };

    二、顺序存储结构线性表的效率分析

    1、顺序存储结构线性表的时间复杂度分析

    2、顺序存储结构线性表的效率分析

    顺序存储结构线性表的插入和删除操作的时间复杂度都是O(n),但是由于插入和删除操作都会涉及到线性表中数据元素的移动,因此会频繁涉及拷贝构造函数和赋值操作符的调用,如果数据元素对象内部的资源较多,对象间的复制、赋值将是非常耗时的,同时由于线性表是泛型模板,无法确定实际实例化的对象类型是否是占有资源的类类型,因此需要禁用拷贝构造函数和赋值操作符,禁用的方式只需要将拷贝构造函数和赋值操作符声明为protected即可。

    template

    class List:public Object

    {

    protected:

    List(const List& other);

    List& operator=(const List& other);

    public:

    List(){}

    virtual bool insert(int index, const T& value) = 0;

    virtual bool remove(int index) = 0;

    virtual bool set(int index, const T& value) = 0;

    virtual bool get(int index, T& value) = 0;

    virtual int length()const = 0;

    virtual void clear() = 0;

    };

    3、顺序存储结构线性表的缺陷

    顺序存储结构线性表重载了[]操作符,因此可以使用[]操作符访问顺序存储结构线性表中的元素。但是线性表中必须存在要访问的元素,即先插入元素才能使用[]操作符访问元素。

    三、数组类的工程实现

    1、数组类的抽象实现

    要创建一个数组类取代原生数组,数组类需要避免原生数组的缺陷:

    A、数组类包含长度信息

    B、数组类能够主动发现越界访问

    数组类的设计如下:

    A、抽象类模板,存储空间的位置和大小由子类完成

    B、重载数组操作符,判断访问下标是否越界

    C、提供数组长度的抽象访问函数

    D、拷贝构造函数和赋值操作符需要在子类实现

    数组的实现:

    template

    class Array:public Object

    {

    public:

    virtual bool set(int index, const T& value)

    {

    bool ret = (0 <= index) && (index < length());

    if(ret)

    {

    m_array[index] = value;

    }

    return ret;

    }

    virtual bool get(int index, T& value)

    {

    bool ret = (0 <= index) && (index < length());

    if(ret)

    {

    value = m_array[index];

    }

    return ret;

    }

    T& operator[](int index)

    {

    if((0 <= index) && (index < length()))

    {

    return m_array[index];

    }

    else

    {

    THROW_EXCEPTION(IndexOutOfBoudsException, "Parameter index is valid...");

    }

    }

    T operator[](int index)const

    {

    return const_cast(*this)[index];

    }

    virtual int length()const = 0;

    protected:

    T* m_array;

    };

    }

    2、静态数组类实现

    指定原生数组作为数组类的存储空间实现静态数组类,使用模板参数指定数组大小,实现函数返回数组的长度,实现重载拷贝构造函数和赋值操作符。

    template <typename T,int N>

    class StaticArray:public Array<T>

    {

    public:

    StaticArray()

    {

    this->m_array = m_space;

    }

    //拷贝构造函数

    StaticArray(const StaticArray<T,N>& other)

    {

    this->m_array = m_space;

    for(int i = 0; i < N; i++)

    {

    m_space[i] = other.m_space[i];

    }

    }

    //赋值操作符

    StaticArray& operator=(const StaticArray<T,N>& other)

    {

    if(this != &other)

    {

    for(int i = 0; i< N; i++)

    {

    m_space[i] = other.m_space[i];

    }

    }

    return *this;

    }

    int length() const

    {

    return N;

    }

    protected:

    T m_space[N];//存储空间

    };

    3、动态分配数组实现

    使用动态分配的堆空间作为数组类的存储空间实现动态分配数组类。

    类模板设计需要动态确定分配存储空间的大小,实现函数返回数组大小,实现拷贝构造函数和赋值操作符。

    template <typename T>

    class DynamicArray:public Array<T>

    {

    public:

    //构造函数

    DynamicArray(int length)

    {

    this->m_array = new T[length];

    if(this->m_array != NULL)

    {

    this->m_length = length;

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    //拷贝构造函数

    DynamicArray(const DynamicArray<T>& other)

    {

    this->m_array = new T[other.m_length];

    if(this->m_array != NULL)

    {

    this->m_length = other.m_length;

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    //赋值操作符

    DynamicArray<T>& operator=(const DynamicArray<T>& other)

    {

    if(this != &other)

    {

    T* array = new T[other.m_length];

    if(array != NULL)

    {

    for(int i = 0; i < other.m_length; i++)

    {

    array[i] = other.m_array[i];

    }

    T* temp = this->m_array;

    this->m_array = array;

    this->m_length = other.m_length;

    delete[] temp;

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    return *this;

    }

    int length()const

    {

    return m_length;

    }

    //重置数组长度

    void resize(int length)

    {

    if(this->m_length != length)

    {

    T* array = new T[length];

    if(array != NULL)

    {

    int size = (length < this->m_length)?length:this->m_length;

    for(int i = 0; i < size; i++)

    {

    array[i] = this->m_array[i];

    }

    T* temp = this->m_array;

    this->m_array = array;

    this->m_length = length;

    delete[] temp;

    }

    else

    {

    THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");

    }

    }

    }

    ~DynamicArray()

    {

    delete[] this->m_array;

    }

    protected:

    int m_length;//数组长度

    };

    展开全文
  • 下面给出了一种基于顺序存储线性表实现方案: 该方案将线性表存储一片连续空间里,并通过data、len和max三个属性元素。组织成为一个结构: data: 给出线性表存储空间的起始地址; max: 指明线性表存储...

    一.什么线性表

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中,数据元素之间通过一对一首尾相接的方式连接起来。具体实现时,线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表实现方案:

    预览大图

    该方案将线性表存储在一片连续空间里,并通过datalenmax三个属性元素。组织成为一个结构:

    • data: 给出线性表存储空间的起始地址;
    • max: 指明线性表存储空间最多可存储的数据元素个数;
    • len: 当前线性表里的数据元素个数。

    为了讨论简化,我们假设每个数据元素是一个整数:

     
    
    1. typedef char ElemType; // 数据元素的数据类型

    该线性表的结构定义如下:

     
    
    1. struct SqList{ 
    2. ElemType data[i]; // 数据元素存储空间的开始地址
    3. int length; // 线性表的当前长度
    4. };

    以上示意图中的L是指向该结构的一个指针,只要给定L指针,就可对线性表进行操作。

    对数据元素进行操作处理是一个数据结构的重要组成部分。线性表涉及的主要操作如下:

    • 创建线性表:创建一个最多可存储MaxSize个数据元素的顺序存储的线性表,并将其初始状态设置为length=0。void CreateList(SqList *& L,ElemType a[],int n)

    • 释放线性表存储空间:释放L->data所指向的用于存储线性表数据元素的存储空间。该操作函数具体定义如下: void EestorySqlist(SeqList* L);

    • 获取线性表当前长度:获取并返回线性表的当前长度L->length。该操作函数具体定义如下: int ListLength(SqList *L)

    • 判断线性表是否为空:若当前线性表是空表,则返回false,否则返回true。该操作函数具体定义如下:bool ListEmpty(SqList *& L)  

    • 返回线性表第i个数据元素:返回线性表的第i个数据元素L->data[i]。该操作函数具体定义如下: bool GetElem(SqList *L,int i,ElemType &e)

    • 在线性表位置i插入数据元素x: 将x插入L->data[i]之前。若插入失败(i>L->length或i<0时,无法插入),返回 false,否则返回 true。该操作函数具体定义如下:bool ListInsert(SqList *&L,int i,ElemType e)

    • 删除线性表位置i处的数据元素: 删除线性表的i号数据元素。输入参数i范围应在[0,L->length-1]内,否则会产生不能预料的异常或错误。返回被删除的数据元素的值。该操作函数具体定义如下:bool ListDelete(SqList *&L,int i,ElemType e)

    • 查找线性表中第一个值为e的数据元素的位置: 找到线性表中第一个值为x的数据元素的编号。返回值-1表示没有找到,返回值>=0表示该元素位置。该操作函数具体定义如下: int LocateElem(SqList *L,ElemType e) 

    • 打印线性表: 打印整个线性表。该操作函数具体定义如下:void DisList(SqList *L)

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中,数据元素之间通过一对一首尾相接的方式连接起来。具体实现时,线性表可以采用不同的存储策略。下面给出了一种基于顺序存储的线性表实现方案:

    预览大图

    代码展示:

    #include<stdio.h>
    #include<stdio.h>
    #include<malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    typedef struct 
    {
        ElemType data[MaxSize];  //存放顺序表元素
        int length;             //存放顺序表长度
        /* data */
    }SqList;
    
    void CreateList(SqList *& L,ElemType a[],int n){  //创立线性表
        L =(SqList *)malloc(sizeof(SqList));
        for(int i=0;i<n;i++){
            L->data[i]=a[i];
        }
        L ->length =n;
    }
    
    void InitList(SqList *& L){   //初始化线性表
        L =(SqList *)malloc(sizeof(SqList));
        L ->length =0;
    }
    
    void DestoryList(SqList *&L){  //销毁线性表
        free(L);
    }
    
    bool ListEmpty(SqList *& L){ //判断线性表是否为空
        return (L->length ==0);
    }
    
    int ListLength(SqList *L){  //求线性表的长度
        return  L->length;
    }
    
    void DisList(SqList *L){   //输出线性表
        for(int i=0;i<L->length;i++){
            printf("%c",L ->data[i]);
        }
        printf("\n");
    }
    
    bool GetElem(SqList *L,int i,ElemType &e){  //求线性表中第i个元素
        if(i<1||i>L->length){
            return false;       //判断是否在表内     
        }
        e =L->data[i-1];
        return true;
    }
    
    int LocateElem(SqList *L,ElemType e) { //查找第一个e的位置·
        int i=0;
        while (i<L->length &&L->data[i]!=e)
        {
            i++;
        }
        if(i>=L->length){
            return 0;
        }else {
            return i+1;
        }
        
        
    }
    
    bool ListInsert(SqList *&L,int i,ElemType e){ //插入第i个元素
        int j;
        if(i<1||i>L->length+1||L->length ==MaxSize){
            return false;
        }
        i--;
        for(j =L->length;j>i;j--){
            L->data[j]=L->data[j-1];
        }
        L->data[i]=e;
        L->length++;
        return true;
    }
    
    bool ListDelete(SqList *&L,int i,ElemType e){ //删除第i个元素
        int j;
        if(i<1||i>L->length){
            return false;
        }
        i--;
        e=L->data[i];
        for(j=i;j<L->length;j++){
            L->data[j]=L->data[j+1];
        }
        L ->length--;
        return true;
    
    }

    展开全文
  • 线性表顺序存储

    2019-10-16 15:39:42
    线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中,即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻...
  • 使用C++类模板实现了线性表的顺序存储结构,类中包含了线性表的常用方法:向线性表中插入一个元素、删除一个元素、清空线性表、获取一个元素、获取线性表长度、获取线性表的容量等。大致实现了STL中的线性表基本功能...
  • 数据结构顺序线性表的基本操作,适合刚学数据结构的同学用
  • 数据结构:线性表顺序存储

    千次阅读 2020-09-08 22:04:36
    文章目录一、线性表(List):0个或多个数据结构的有限序列二、线性表顺序存储结构1.顺序存储定义2.顺序存储方式3.顺序存储结构的插入与删除总结 一、线性表(List):0个或多个数据结构的有限序列 这里要强调几...
  • c语言实现的线性表顺序存储结构,包括初始化,设置线性表的值,增,删,改,查。
  • 这是一个顺序存储结构的线性表的c语言实现程序,实现对顺序表的操作
  • 线性表的基本概念 线性结构习惯称为线性表,线性表是n(n>=0)个数据元素构成的有限序列,表中除第...顺序存储是存储线性表最简单的结构,具体做法是将线性表中的元素一个接一个地存储一片相邻的存储区域中。这种顺
  • 顺序存储线性表

    2020-11-28 18:49:59
    本关任务:实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数,以实现线性表中数据的插入、删除与查找等功能。 相关知识 线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中,...
  • 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现 验 2. 以线性表的各种操作建立插入删除等的实现为重点 目 3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现 的 实 验 运行 Visual c++ 的微机一...
  • 我们学习数据结构的时候,第一个接触的一般就是线性表了,线性表虽然简单,但他起到了一个敲门砖的作用,理解并掌握了线性表在慢慢学习更高级的数据结构就可以慢慢入门了,此,把线性表顺序存储结构,API实现...
  • 线性表-顺序存储.c

    2020-04-10 11:43:31
    中国大学MOOC上浙大的《数据结构》课程第一章线性表顺序存储实现的代码。 包含线性表初始化、输入、输出、插入、查找、删除等函数
  • 线性表 顺序存储

    2022-04-09 09:55:14
    顺序存储
  • 主要介绍了Go语言实现顺序存储线性表的方法,实例分析了Go语言实现线性表的定义、插入、删除元素等的使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • #include<stdio.h> #include<stdlib.h> #define N 50 struct SeqList { int data[N]; int length; }; //初始化 void init_seqlist(struct SeqList *);...void insert_seqlist(struct SeqList *,int,...
  • 2.2_线性表的顺序存储结构_参考集合ArrayList [线性表的顺序存储从结构] 指的是用一段连续的存储单元一次储存线性表的数据元素. [线性表的顺序存储的结构代码 C语言版] #define MAXSIZE 20 /*存储空间初始分配量*/ ...
  • 通过C++类模板实现线性表顺序存储
  • 线性表顺序存储结构,指的是用一段地址连续的 存储单元依次存储线性表的数据元素。 简单说就是内存找了一块地方,通过占位的形式,把一定内存空间给占了。 顺序存储结构的三个属性: 存储空间的起始位置 ...
  • 该文档饱含了数据结构课程关于线性表的十二个基本操作的实现。对于不同的线性表存储结构,利用C语言分别实现相应的算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,507
精华内容 27,002
关键字:

在顺序存储的线性表中