1. 用C语言的一维数组实现线性表的顺序存储
还是说只要是在内存中申请了一块连续的地址空间存储数据只要知道其首地址都可以用数组的形式访问其中的元素呢？
就是这样的。
线性表的特点就是长度可变，如果使用常规的数组，就不能实现这个特性，因为数组是定长的。而在堆中申请的内存可以通过参数在运行时指定它的大小，且可以调整它的大小，并且其使用方式和数组一样，使用索引访问。
int*p = (int*)malloc(sizeof(int)*5);
p[0]; //第一个元素
p[1]; //第二个元素
p[2]; //第三个元素
//...
free(p);
2. 数据结构中用数组或者链表实现线性表
1）自己实现线性表之顺序表
思路：
1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据
2.因为存储的具体对象类型不一定，所以采用泛型操作
3.数组操作优点：
1.通过指针快速定位到下表，查询快速
缺点：
1.数组声明时即需要确定扒携早数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据
2.当需要在中间进隐液行插入或者春雀删除时，则需要移动大量元素（size-index个）
具体实现代码如下：
/**
* 自己用数组实现的线性表
*/
public class ArrayList< E> {
Object[] data = null;// 用来保存此队列中内容的数组
int current;// 保存当前为第几个元素的指标
int capacity;// 表示数组大小的指标
/**
* 如果初始化时，未声明大小，则默认为10
*/
public ArrayList() {
this(10);
}
/**
* 初始化线性表，并且声明保存内容的数组大小
* @param initalSize
*/
public ArrayList(int initalSize) {
if (initalSize < 0) {
throw new RuntimeException("数组大小错误:" + initalSize);
} else {
this.data = new Object[initalSize];
this.current = 0;
capacity = initalSize;
}
}
/**
* 添加元素的方法 添加前，先确认是否已经满了
* @param e
* @return
*/
public boolean add(E e) {
ensureCapacity(current);// 确认容量
this.data[current] = e;
current++;
return true;
}
/**
* 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量
* @param cur 当前个数
*/
private void ensureCapacity(int cur) {
if (cur == capacity) {
// 如果达到容量极限，增加10的容量，复制当前数组
this.capacity = this.capacity + 10;
Object[] newdata = new Object[capacity];
for (int i = 0; i < cur; i++) {
newdata[i] = this.data[i];
}
this.data = newdata;
}
}
/**
* 得到指定下标的数据
* @param index
* @return
*/
public E get(int index) {
validateIndex(index);
return (E) this.data[index];
}
/**
* 返回当前队列大小
* @return
*/
public int size() {
return this.current;
}
/**
* 更改指定下标元素的数据为e
* @param index
* @param e
* @return
*/
public boolean set(int index, E e) {
validateIndex(index);
this.data[index] = e;
return true;
}
/**
* 验证当前下标是否合法，如果不合法，抛出运行时异常
* @param index 下标
*/
private void validateIndex(int index) {
if (index < 0 || index > current) {
throw new RuntimeException("数组index错误：" + index);
}
}
/**
* 在指定下标位置处插入数据e
* @param index 下标
* @param e 需要插入的数据
* @return
*/
public boolean insert(int index, E e) {
ensureCapacity(current);// 确认容量
validateIndex(index);
Object[] tem = new Object[capacity];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < current; i++) {
if (i < index) {
tem[i] = this.data[i];
}else if(i==index){
tem[i]=e;
}else if(i>index){
tem[i]=this.data[i-1];
}
}
this.data=tem;
current++;
return true;
}
}
（2）自己实现线性表之链表
思路：1.链表采用链式存储结构，在内部只需要将一个一个结点链接起来。（每个结点中有关于此结点下一个结点的引用）
链表操作优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可
缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表
实现代码如下：
/**
* 自己用链式存储实现的线性表
*/
public class LinkedList< E> {
private Node< E> header = null;// 头结点
int size = 0;// 表示链表大小的指标
public LinkedList() {
this.header = new Node< E>();
}
public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容，封装为结点
Node< E> newNode = new Node< E>(e);
// 得到当前最后一个结点
Node< E> last = getNode(size-1);
// 在最后一个结点后加上新结点
last.addNext(newNode);
}
size++;// 当前大小自增加1
return true;
}
//在index位置后插入元素
public boolean insert(int index, E e) {
Node< E> newNode = new Node< E>(e);
// 得到index处的结点
Node< E> cNode = getNode(index);
newNode.next = cNode.next;
cNode.next = newNode;
size++;
return true;
}
/**
* 遍历当前链表，取得当前索引对应的元素
*
* @return
*/
private Node< E> getNode(int index) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> tem = new Node< E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
return tem;
}
/**
* 根据索引，取得该索引下的数据
*
* @param index
* @return
*/
public E get(int index) {
// 先判断索引正确性
if (index >= size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> tem = new Node< E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
E e = tem.e;
return e;
}
public int size() {
return size;
}
/**
* 设置index处结点的值
*
* @param x
* @param e
* @return
*/
public boolean set(int index, E e) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错：" + index);
}
Node< E> newNode = new Node< E>(e);
// 得到index处的结点
Node< E> cNode = getNode(index);
cNode.e = e;
return true;
}
/**
* 用来存放数据的结点型内部类
*/
class Node< E> {
private E e;// 结点中存放的数据
Node() {
}
Node(E e) {
this.e = e;
}
Node next;// 用来指向该结点的下一个结点
// 在此结点后加一个结点
void addNext(Node< E> node) {
next = node;
}
}
}
（3）自己实现线性表之栈
栈是限定仅允许在表的同一端（通常为“表尾”）进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)
特点：后进先出 (LIFO)或，先进后出（FILO）
因为栈是限定线的线性表，所以，我们可以调用前面两种线性表，只需要对出栈和入栈操作进行设定即可
具体实现代码
/**
* 自己用数组实现的栈
*/
public class ArrayStack< E> {
private ArrayList< E> list=new ArrayList< E>();//用来保存数据线性表
private int size;//表示当前栈元素个数
/**
* 入栈操作
* @param e
*/
public void push(E e){
list.add(e);
size++;
}
/**
* 出栈操作
* @return
*/
public E pop(){
E e= (E)list.get(size-1);
size--;
return e;
}
}
至于用链表实现栈，则只需要把保存数据的顺序表改成链表即可，此处就不给出代码了
(4)自己实现线性表之队列
与栈类似
队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为队头(front)。
特点：先进先出 (FIFO)、后进后出 (LILO)
同理，我们也可以调用前面两种线性表，只需要对队列的入队和出队方式进行处理即可
/**
* 用数组实现的队列
*/
public class ArrayQueue< E> {
private ArrayList< E> list = new ArrayList< E>();// 用来保存数据的队列
private int size;// 表示当前元素个数
/**
* 入队
* @param e
*/
public void EnQueue(E e) {
list.add(e);
size++;
}
/**
* 出队
* @return
*/
public E DeQueue() {
if (size > 0) {
E e = list.get(0);
list.delete(0);
return e;
}else{
throw new RuntimeException("已经到达队列顶部");
}
}
}
(5)对比线性表和链式表
前面已经说过顺序表和链式表各自的特点，这里在重申一遍
数组操作
优点：1.通过指针快速定位到下标，查询快速
缺点：1.数组声明时即需要确定数组大小。当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据
2.当需要在中间进行插入或者删除时，则需要移动大量元素（size-index个）
链表操作
优点：1.，因为每个结点记录下个结点的引用，则在进行插入和删除操作时，只需要改变对应下标下结点的引用即可
缺点：1.要得到某个下标的数据，不能通过下标直接得到，需要遍历整个链表。
改进：
链表中我们每次添加一个数据时，都需要遍历整个表，得到表尾，再在表尾添加，这是很不科学的 现改进如下：设立一个Node
类的成员变量last来指示表尾，这样每次添加时，就不需要再重新遍历得到表尾，改进后add()方法如下public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容，封装为结点
Node< E> newNode = new Node< E>(e);
//在表尾添加元素
last.addNext(newNode);
//将表尾指向当前最后一个元素
last = newNode;
}
size++;// 当前大小自增加1
return true;
}
3. 顺序表与数组的区别和联系是什么
顺序表是在计算机内存中以数组的形族迅式保存的线性表。
顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表，顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。线性表采用指针链接的方式存储就称之为链表。
线性表是从逻辑结构的角度来说的，除了头和尾之外，它的每一个元素都只有一个前驱元素和一个后驱元素。各种队列（单向、双向、循环队列），栈等都是线性表的不同例子。
而数组是从物理存贮的角度来说的，线性表可以用数组存贮也可以用链表来存贮。同样扮蠢的队列和栈也可以用数组和链表存贮，各有利弊。具体使用时，根据具体情况选择。
所以说，数组是一个更大的兆缺此概念。使用数组，不但可以存储线性表，也可存储非线性结构的数据结构。比如堆、完全二叉树、乃至于其它类型的树、图等
4. 利用数组建立该线性表的顺序存储结构
一、线性表的顺序表示
用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。
2000:0001
2000:0003
2000:0005
2000:0007
2000:0009
2000:0011
2000:0013
2000:0015
2000:0017
...
2000:1001
2000:1003
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
a[9] 1
2
3
4
5
6
7
8
9
假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：
LOC(ai+1)=LOC(ai)+l
LOC(ai)=LOC(a1)+(i-1)*l
5. 顺序表与数组的区别和联系
顺序表是在计算机内存蠢穗谈中以带碰数组的形式族带保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。
只能这么说
数组是顺序表的载体
顺序表比数组包含的操作要多