赞
踩
1,顺序表特点
- 线性表的逻辑顺序与物理顺序一致,数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
- 对顺序表中的所有表项,即可以进行顺序的访问,也可以随机的访问,也就是说,
既可以从表的第一个表项开始逐个访问表项也可以按照表项的序号(下标)直接的访问。- 无需为表示结点间的逻辑关系而增加额外的存储空间,存储利用率提高。
- 可以方便的存储表中的任一结点,存储速度快。
缺点:
1)在表中插入新元素或删除无用元素时,为了保持其他元素的相对次序不变,平均需要移动一半元素,运行效率低
2)由于顺序表要求占用连续的空间,如果预先进性存储分配,则当表长度变化较大时,难以确定合适的存储空间带大小
3)若按可能达到的最大的长度预先分配表的空间,则容易造成一部分空间长期的限制而得不到充分的利用
2、链表
- 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
- 链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。
- 每个结点包括两个部分:数据域和指针域
特点:
1)可以方便的进行扩充。
2)可以方便的删除和插入。
3、顺序表的线性存储示意图
- 假设线性表中有n个元素,每个元素占k个存储单元,第一个元素的地址为Loc(a1),则第i个元素的地址Loc(ai):
- Loc(ai) = Loc(a1) + (i-1) * k; # 其中Loc(a1)称为基地址。
4、顺序表增删改查原理
# 1、顺序表的初始化 顺序表的初始化就是把顺序表 初始化为空的顺序表;只需把顺序表的长度length置为0即可; # 2、求顺序表的长度 顺序表的长度就是就顺序表中的元素的个数,由于在插入和删除操作中都有对数据表的长度进行修改,所以求表长只需返回length的值即可; # 3、按序号查找 查找顺序表中第i个元素的值(按序号查找),如果找到,将将该元素值赋给e。 查找第i个元素的值时,首先要判断查找的序号是否合法,如果合法,返回第i个元素对应的值。 # 4、插入元素 在数据表的第i个位置插入元素,在顺序表的第i个位置插入元素e 首先将顺序表第i个位置的元素依次向后移动一个位置,然后将元素e插入第i个位置,移动元素要从后往前移动元素, 即:先移动最后一个元素,在移动倒数第二个元素,依次类推; 插入元素之前要判断插入的位置是否合法,顺序表是否已满,在插入元素之后要将表长L->length++; # 5、删除操作 删除表中的第i个元素e,删除数据表中的第i个元素,需要将表中第i个元素之后的元素依次向前移动一位,将前面的元素覆盖掉。 移动元素时要想将第i+1个元素移动到第i个位置,在将第i+2个元素移动i+1的位置,直到将最后一个元素移动到它的前一个位置。 进行删除操作之前要判断顺序表是否为空,删除元素之后,将表长L->length--; # 6、按内容查找 查找数据元素e在表中的位置,可以从表头开始一直遍历表中元素。 如果找到与要查找元素e相等的元素,则返回元素在表中的位置,数组下标从0开始。 则元素在表中对应的位置序号值应为对应数组下标加1,没有找到则返回0。 # 7、头插 头插,即在表头插入元素e,在表头插入元素,需要将表中的元素依次后移一位, 然后将要插入的元素e赋给数字的首元素,执行插入操作后将表长L->length++; 需要注意的是移动元素要从顺序表的最后一个元素开始移动, 如果从第1个元素开始移动,会使得第1个元素的值覆盖第2个元素的值,然后把第二个元素后移则会使第2个元素的值 (原来第1个元素值)覆盖第3个元素的值,依次类推,最后出插入元素外,其余元素值均为原顺序表中第一个元素的值。 # 8、头删 删除顺序表中的第一个元素,只要将顺序表中的元素从第2个开始,依次向前移动1位,覆盖原来顺序表中元素对应位置的前一个值 在删除元素之前要判断顺序表是否为空,删除顺序表元素之后将顺序表长度L->length--; # 9、尾插 在顺序表表尾插入元素e,L->data[L->length] = e;将元素e的值赋给顺序表中最后一个元素的下一个元素; 尾插操作,需要判断顺序表是否已满,尾插后将顺序表长度L->length++; # 10、尾删 删除表尾元素,只需将顺序表的长度减1,类似于出栈操作,栈顶指针top –。 # 11、清空顺序表 清空顺序表就是将表中的元素删除。删除表中的元素只需将表的长度置为0。 # 12、判断表是否为空 如果顺序表的长度为0,则顺序表为空,返回1,否则,返回0; # 13、打印表中元素 依次打印顺序表中的元素,如果顺序表为空则输出提示。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。