?前言?

本文將決議線性表中的順序表以及鏈表

線性表

線性表的定義及基本表示

線性表的定義

線性表是具有相同資料型別的n個資料元素的有限集合，

常見的線性表有順序表、鏈表、堆疊和佇列，

基本操作

void InitList(&L);//初始化表，構造一個空的線性表，

int Length(L);//求表長，回傳線性表L的長度，即L中資料元素的個數，

void LocateElem(L,e);//按值查找操作，在表L中查找具有給定關鍵字值的元素，

void GetElem(L,i);//按位查找操作，獲取表L中第i個位置的元素的值，

void ListInsert(&L,i,e);//插入操作，在表L中的第i個位置上插入指定元素e，

void ListDelete(&L,i,&e);//洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值

void PrintList(L);//輸出操作，按前后順序輸出線性表L的所有元素值，

bool Empty(L);//判空操作，若L為空表，則回傳true,否則回傳false，

void DestroyList(&L);//銷毀操作，銷毀線性表，并釋放線性表L所占用的記憶體空間，

順序表

順序表的定義

簡而言之，陣列，這就是說，順序表的底層是通過陣列來實作的，

靜態陣列版

//C語言實作
#define MaxSize 50//定義線性表最大長度
struct List{
    int data[MaxSize];//順序表的元素，以int型資料為例
    int length;//順序表當前長度，元素個數
}SqList;

動態陣列版

//C語言實作
#define InitSize 100//表長度初始定義
struct List{
    int* data;//指示動態分配陣列的指標
    int MaxSize,length;//陣列最大容量和當前容量
}SeqList;
L.data=(int*)malloc(sizeof(int)*InitSize);
int* tmp=(int*)realloc(sizeof(int)*(MaxSize+10));
if(tmp){
    L.data=tmp;//判斷擴容成功然后再改變指標指向
}

順序表的基本操作

增刪查改

下面以Java語言實作，與C語言不同的是Java可以在類的內部存放方法，便于操作，

建議先看前面的注釋了解函式的作用，然后分析增刪查改函式

//Java語言實作
public class MyArrayList {
    public int[] elem;
    public int usedSize;//有效的資料個數
    public MyArrayList() {
        this.elem = new int[10];
    }

    // 列印順序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    // 獲取順序表的有效資料長度
    public int size() {
        return this.usedSize;
    }

    // 在 pos 位置新增元素，分析見后面
    public void add(int pos, int data) {
        if(pos<0||pos>this.usedSize){
            System.out.println("輸入不合法");
            return;
        }
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,this.elem.length+10);
        }
        for(int i=this.usedSize-1;i>=pos;i--){
            elem[i+1]=elem[i];
        }
        elem[pos]=data;
        this.usedSize++;
    }
    //判斷表是否滿
    public boolean isFull() {
        return this.usedSize==this.elem.length;
    }
    //判斷表是否為空
    public boolean isEmpty(){
        return this.usedSize==0;
    }

    // 判定是否包含某個元素
    public boolean contains(int toFind) {
        for (int x: elem) {
            if(x==toFind) return true;
        }
        return false;
    }
    // 查找某個元素對應的位置
    public int search(int toFind) {
        for (int i = 0; i < elem.length; i++) {
            if(elem[i]==toFind) return i;
        }
        return -1;
    }
    // 獲取 pos 位置的元素
    public int getPos(int pos) {
        if(pos<0||pos>=this.usedSize){
            return -1;
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return -1;
        }
        return elem[pos];
    }
    // 給 pos 位置的元素設為 value
    public void setPos(int pos, int value) {
        if(isEmpty()){
            System.out.println("順序表為空");
            return;
        }
        if(pos<0||pos>=this.usedSize){
            System.out.println("輸入不合法");
        }else{
            this.elem[pos]=value;
            System.out.println("設定成功");
        }
    }
    //洗掉第一次出現的關鍵字key
    public void remove(int toRemove) {
        if(isEmpty()){
            System.out.println("順序表為空");
            return;
        }
        int pos=this.search(toRemove);
        if(pos==-1){
            System.out.println("洗掉元素不存在");
        }else{
            for(int i=pos;i<this.usedSize-1;i++){
                elem[i]=elem[i+1];
            }
            this.usedSize--;
            System.out.println("洗掉成功");
        }
    }
    // 清空順序表
    public void clear() {
        this.usedSize=0;
        System.out.println("成功清空表");
    }
}

需要著重分析的是增加元素和洗掉元素

函式介面是void add(int pos,int data);

pos是插入位置，data是數值

首先判斷pos的合法性，小于0不可以，大于使用長度也不可以

合法性判斷后判斷線性表是否滿了，如果滿了需要擴容，幸運的是，不用判斷擴容的成功與失敗，

比如我們要在pos為3的位置插入元素，我們就需要將pos以后的元素往后移動一位

如果插入pos為6呢？顯然我們不需要移動元素了

那大于使用長度也不可以是什么意思？當我們插入pos=6時，pos等于usedSize的，當大于時，陣列下標為6的空間沒有被使用，這是不被允許的，

函式洗掉介面為void remove(int toRemove)

對表的洗掉首先要判斷是不是空表，如果時空表我們就不能執行洗掉操作

然后找到洗掉元素的下標，如果不存在直接回傳并提升不存在

如果存在,就需要后面的元素往前覆寫，

例如，我們要洗掉pos=2的元素，就要將后面的元素往前覆寫，

線性表的鏈式表示

單鏈表的定義

//C語言版
struct LNode{
    int data;//資料域，用一個整數來表示
    struct LNode *next;//指標域，指向下一個結點
};

下面給出鏈表的結構

下面給出單鏈表結構，雙鏈表的結構以及回圈單鏈表結構

鏈表的建立

建立鏈表前需要初始化鏈表

//C語言版
//初始化鏈表
struct LNode* InitList(struct LNode* head){
    head=(struct LNode*)malloc(sizeof(LNode));
    head->next=NULL;
    return head;
}

頭插法

顧名思義，就是再鏈表的頭指標前插入元素

先前鏈表1->2->3->4->NULL
我們將5插入鏈表中
插入后5->1->2->3->4->NULL

struct LNode* headInsert(struct LNode* head) {
	struct LNode* p1=(struct LNode*)malloc(sizeof(LNode));
	printf("輸入資料>");
	scanf("%d", &(p1->data));//結點的創建
	//核心操作
    p1->next = head;
	head = p1;
	return head;
}

尾插法

顧名思義，就是再鏈表的尾端插入

先前鏈表1->2->3->4->NULL
將5插入鏈表后1->2->3->4->5->NULL

需要注意的是，我們需要先前判斷頭指標是不是空指標，

struct LNode* tailInsert(struct LNode* head) {
    struct LNode* p2 = (LNode*)malloc(sizeof(LNode));
	printf("輸入資料>");
	scanf("%d", &(p2->data));
    if(head==NULL){
        head=p2;
        return head;
    }
    //核心操作
	struct LNode* p1 = head;//p1用來幫助我們找到尾結點，p2用來插入
	while (p1->next) {
		p1 = p1->next;
	}
	p1->next = p2;
	p2->next = NULL;//尾結點后面沒有了需要加NULL
	return head;
}

//上述尾插法室沒有頭結點的，如果有頭結點，那要怎么插入
struct LNode* tailInsert(struct LNode* head){
    struct LNode*p1=(struct LNode*)malloc(sizeof(LNode));
    p1->next=head->next;
    head->next=p1;
    return head;
}
//@->1->2->3->NULL
//@->4->1->2->3->NULL

鏈表的操作

插入節點

void ListInsert(&L,i,e);

要想在第i個位置插入元素e，就要找到i-1的位置，假設第i-1個結點是p，然后將新結點q插入其后，

q->next=p->next;//步驟1
p->next=q;//步驟2

需要說明的是：當執行完步驟1時，1和3都指向2

如果步驟1和2反過來呢?

當我們p->next=q后，我們就丟失后面的結點

此時就是1->3->null連接

在很多境況我們采用的是尾插法，那要是插在頭節點前呢？

可以使用頭插法，也可以弄一個頭節點來操作，

洗掉結點

洗掉結點需要找到前驅結點

假設p為前驅結點

q=p->next;
p->next=q->next;
free(q);

缺點是無法找到頭節點的前驅結點

也可以將后面結點覆寫前面結點

假設p為被洗掉結點

q=p->next;
p->data=q->data;
p->next=q->next;
free(q);

需要注意的，第一個結點不能洗掉頭結點，第二個方法不能洗掉尾結點，

第一個可以單獨判頭指標，但是尾指標判斷較為困難

對于常規插入洗掉好像都不能顧全面，這時候可以在前面加一個啞結點，那樣就不能考慮對頭節點插入洗掉的困擾，