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. 順序表與數組的區別和聯系
順序表是在計算機內存蠢穗談中以帶碰數組的形式族帶保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。
只能這么說
數組是順序表的載體
順序表比數組包含的操作要多