大多數(shù)編程語言中的數(shù)組, 無論靜態(tài)還是動(dòng)態(tài), 都可以被歸納為SequenceList, 在Java中, SequenceList被實(shí)現(xiàn)為ArrayList. 而LinkedList也在Java的集合框架中存在(就叫LinkedList).

優(yōu)缺點(diǎn)

• SqList知道index下標(biāo)以后(也叫做隨機(jī)訪問), 訪問一個(gè)元素是O(1)時(shí)間; 但是刪除, 和插入元素的時(shí)候, 需要移動(dòng)大量的元素, 時(shí)間是O(n);
• 對比之下, LinkedList沒有下標(biāo)一說, 隨機(jī)訪問一個(gè)元素的時(shí)間是O(n); 但是刪除頭和尾部的元素(有L和r頭尾指針情況下), 時(shí)間是O(1)的. 但是, 在刪除List中非頭尾, 某index要求位置的元素的時(shí)候, 由于要先獲取到元素所在前一位的節(jié)點(diǎn), 其實(shí)等于要先做一次隨機(jī)訪問, 要花O(n)時(shí)間.

SqList

要點(diǎn):

• 有index; 且下標(biāo)index從0開始;
• 強(qiáng)健性: 先檢查解決list的空滿和輸入合法性問題, 再開始操作;
• 同步性: 每個(gè)方法都要關(guān)注成員屬性length和listsize的同步更新

/*typedef 類型定義*/
//length用來描述當(dāng)前長度, listsize用來描述最大容納SIZE;
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}SqList;

/*InitSqList*/
//初始化的時(shí)候,先檢查是否成功(否則exit),然后要顧及到每個(gè)成員屬性的初始化
Status InitSqList(SqList *L) {
    L->elem = (ElemType *)malloc(SIZE*sizeof(ElemType));
    if (!L->elem) {printf("Init OVERFLOW\n");exit(OVERFLOW);}
    L->length = 0;
    L->listsize = SIZE;
    return 0;
}

/*InsertSqList*/
//插入的時(shí)候,先檢查一下是否滿了, 否則先移動(dòng)插入位置到結(jié)尾的所有元素往后一位, 然后再插入;
//要顧及成員屬性如length和listsize的變化;
Status InsertSqList(SqList *L, int index, ElemType e) {
    if (L->length>=L->listsize) {
        printf("Reallocate memory\n");
        L->elem = (ElemType *)realloc(L->elem, (SIZE+INCREMENT)*sizeof(ElemType));
        if (!L->elem) {printf("Insert OVERFLOW\n");exit(OVERFLOW);}
        L->listsize += INCREMENT;
    }
    int i = 0;
    for (i=L->length; i>index; i--) {  //從后往前,每個(gè)元素保存前一位的值,遍歷到插入位置index+1的地方就可以了;
        //注意, 因?yàn)槭遣迦? 所以要從arr[length] = arr[length-1]開始; 比如現(xiàn)在五個(gè)數(shù)arr[0]~arr[4],得先arr[5]=arr[4];
        L->elem[i] = L->elem[i-1];
    }
    L->elem[i] = e;
    printf("elem[%d]%d \n",i,L->elem[i]);
    L->length++;
    return 0;
}

/*RemoveElementInSqList*/
//刪除的時(shí)候,先檢查下是否空了
//(其實(shí)數(shù)據(jù)結(jié)構(gòu)就是這些討論,初始化檢查成功了嗎,插入檢查滿了,刪除和獲取的時(shí)候檢查空了嗎)
//然后直接通過arr[i] = arr[i+1]的辦法來實(shí)現(xiàn)刪除和移動(dòng);
Status RemoveElementInSqList(SqList *L, int index) {
    if (index<0 || index>=L->listsize) {printf("Invalid input\n"); return ERROR;}
    if (L->length<=0) {printf("Empty List\n"); return ERROR;}
    int i = 0;
    for (i=index; i<L->length-1; i++) {    //最多遍歷到arr[length-2]的位置,原先最后一位是arr[length-1];
        L->elem[i] = L->elem[i+1];
    }
    L->length--;
    return 0;
}

/*OutputSqList*/
//遍歷一下
Status OutputSqList(SqList *L) {
    int i=0;
    for (i=0; i<L->length; i++) {
        printf("%d ",L->elem[i]);
    }
    printf("\n");
    return 0;
}

附上一些常量的定義, 以后沒有說的話, 都默認(rèn)代碼頭部是這些東西;

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define Status int
#define OK 0
#define ERROR -1
#define OVERFLOW -1
#define SIZE 3
#define INCREMENT 1

檢驗(yàn)數(shù)據(jù)結(jié)構(gòu)正確性的main函數(shù);

int main() {
    int input[5] = {10, 20, 30, 40, 50};
    SqList L;
    InitSqList(&L);
    int i = 0;
    for (i=0; i<5; i++) {
        InsertSqList(&L, 0, input[i]);
    }
    OutputSqList(&L);
    RemoveElementInSqList(&L, 3);  //下標(biāo)是從0開始的;
    OutputSqList(&L);
    return 0;
}

LinkedList

• 沒有index, 因此需要從頭開始找到一個(gè)元素的位置才能進(jìn)行獲取, 插入, 刪除的操作;
• 指針在循環(huán)中的指向: 要非常注意循環(huán)中p到底指到數(shù)組List的哪一位的問題, 要算好j循環(huán)到哪里了;
• 強(qiáng)健性: 先檢查解決list的空滿和輸入合法性問題, 再開始操作;

/*類型定義*/
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LList;

LinkedList的類型定義相當(dāng)簡單, 而真正難點(diǎn)在節(jié)點(diǎn)的操作;

/*創(chuàng)建鏈表L*/
//從頭加入的初始化; 注意: 輸入的時(shí)候需要倒序;
LList Creat_LL( ) {
    LList L = NULL;
    LNode *p;
    printf("Input elements: ");
    ElemType flag = -99;
    ElemType value;
    scanf("%d",&value);
    while (value!=flag) {
        p = (LNode *)malloc(sizeof(LNode));
        p->data = value;
        p->next = L;
        L = p;
        scanf("%d",&value);
    }
    return L;   //此處記得要返回L;
}

//從尾加入的初始化
//我們現(xiàn)在是只有頭指針, 而沒有頭結(jié)點(diǎn)的情況
LList Creat_LL( ) {
    LList L = NULL;
    LNode *p, *r = L;  //需要添加一個(gè)r指向尾巴
    printf("Input elements: ");
    ElemType flag = -99;
    ElemType value;
    scanf("%d",&value);
    while (value!=flag) {
        p = (LNode *)malloc(sizeof(LNode));
        if (L==NULL) {L=p;}  //單獨(dú)要判斷一下是否在指向第一個(gè)節(jié)點(diǎn)
        else {r->next = p;}    //如果不是第一個(gè)節(jié)點(diǎn)的情況, 讓原先的尾巴節(jié)點(diǎn);
        p->data = value;   //成員屬性賦值;
        p->next = NULL;   //成員賦值
        r = p;    //讓尾指針指向最后一個(gè)新加的元素;
        scanf("%d",&value);
    }
    return L;   //此處記得要返回L;
}

/*取節(jié)點(diǎn)操作*/
//能夠大大簡化后面insert和delete的操作;
LNode *Get_LL(LList L, int i) {
    int j = 0;
    LNode *p = L;
    while (p->next && j<i) {    //非常關(guān)鍵的一行
        p = p->next; j++;
    }
    if (j<i) {return NULL;} else {return p;}
}
/* 需要理解當(dāng)循環(huán)發(fā)現(xiàn)j=i的時(shí)候會(huì)跳出, 使得p指向前一個(gè)元素; 
或者是p->next為空的時(shí)候跳出, 使得最后j<i, 也就是說前一個(gè)節(jié)點(diǎn)存在,
而arr[i]位置節(jié)點(diǎn)不存在的情形將會(huì)被return NULL, 
因?yàn)槿〔坏絘rr[i], 而j=i且下一位沒有節(jié)點(diǎn), 
也就是最后一位存在的節(jié)點(diǎn)剛好就是arr[i]的情形將會(huì)被允許; */

/*在鏈表的第i個(gè)位置上插入e*/
//思路: 檢查是否有前一個(gè)元素, 然后給新節(jié)點(diǎn)分配一個(gè)LNode大小的內(nèi)存, 并賦予各項(xiàng)值(e, NULL);
//@L:要插入的鏈表
//@i:要插入的位置index
//@e:要插入的element
LList Insert_LL(LList L, int i, int e) {
    LNode *p = Get_LL(L, i-1);    //獲取前一個(gè)節(jié)點(diǎn);
    if (p==NULL) {
        printf("ERROR");
        return NULL;
    } else {
        LNode *q = (LNode *)malloc(sizeof(LNode));
        q->data = e;
        q->next = p->next;
        p->next = q;
        return L;
    }
}

/*刪除鏈表第i個(gè)位置上的元素*/
//思路: 先判斷是否為空, 不為空再利用p->next = p->next->next;
//@L: LinkedList
//@i: index
LList Delete_LL(LList L, int i) {
    LNode *p;
    p = Get_LL(L, i-1);
    if (p == NULL) {
        printf("ERROR!");
        return NULL;
    } else {
        p->next = p->next->next;
    }
    return L;
}

/*輸出鏈表L*/
//思路: 先檢查是否為空, 然后輸出;
void Output_LL(LList L) {
    if (L == NULL) {printf("Empty LinkedList!\n");}
    else {
        LNode *p = L;
        while (p) {
            printf("%d\t",p->data);
            p = p->next;
        }
        printf("\n");   
    }
}

提示: 測試數(shù)據(jù), 注意需要把不同實(shí)現(xiàn)的方法給注釋掉一個(gè);

int main(){
    //20,22,23,24,24
    LList L2;
    L2=Creat_LL( );
    Output_LL(L2);
    L2=Insert_LL(L2, 1, 21);
    Output_LL(L2);
    L2=Delete_LL(L2, 1);
    Output_LL(L2);
    return 0;
}