線性表是最基本德频、最簡單路操、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)徘禁。
線性表中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系诅诱，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意送朱，這句話只適用大部分線性表娘荡，而不是全部。比如驶沼，循環(huán)鏈表邏輯層次上也是一種線性表（存儲層次上屬于鏈?zhǔn)酱鎯Γ┧模前炎詈笠粋€(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn)）。

線性表的兩種存儲方式

• 順序存儲
• 鏈?zhǔn)酱鎯?/li>

線性表的順序存儲

typedef struct LinkedList{
    int data[MAXSIZE];//存儲數(shù)組
    int Last;//游標(biāo)指針
}List;
List * MakeEmpty(){
    List *Ptrl;
    Ptrl=(List *)malloc(sizeof(List));
    Ptrl->Last=-1;
    return Ptrl;
}
/**T(n)=O(N)*/
int FindElement(int result,List* Ptrl){
    int i=0;
    while(i<=Ptrl->Last&&Ptrl->data[i]!=result)
        i++;
    if(i>Ptrl->Last)return -1;//如果沒有找到返回-1
    else return i;
}
void Insert(int result,int i,List *Ptrl){
    int j;
    if(Ptrl->Last==MAXSIZE-1){
        printf("表滿");
        return;
    }
    if(i<1||i>Ptrl->Last+2){
        printf("插入位置不合法");
        return;
    }
    for(j=Ptrl->Last;j>=i-1;j--)//倒序移動（注意j>=i-1）
        Ptrl->data[j+1]=Ptrl->data[j];
    Ptrl->data[i]=result;//插入數(shù)據(jù)
    Ptrl->Last++;//Last指針++
    return;
}
/*T(N)=O(N)*/
void DeleteElement(int i,List* Ptrl){
    int j;
    if(i<1||i>Ptrl->Last+1){//判斷位置的合法性（注：鏈表下標(biāo)是從1開始的）
        printf("第%d個(gè)元素不存在",i);
        return;
    }
    for(j=i;j<=Ptrl->Last;j++)//所有元素前移
        Ptrl->data[j-1]=Ptrl->data[j];
    Ptrl->Last--;
    return;
}

線性表的鏈?zhǔn)酱鎯?/h5>

typedef struct LinkedList {
    int data;
    struct LinkedList *next;
} List;

//求鏈表長度
int Length(List *Ptrl) {
    List *p = Ptrl;
    int j = 0;
    while (p) {
        p = p->next;
        j++;
    }
    return j;
}

//按序號查找
List *FindKth(int k, List *Ptrl) {
    List *p = Ptrl;//不改變頭節(jié)點(diǎn)商乎，返回移動指針p
    int i = 1;
    while (p != NULL && i < k) {
        p = p->next;
        i++;
    }
    if (i == k)return p;
    else return NULL;
}

//按值查找
List *Find(int result, List *Ptrl) {
    List *p = Ptrl;
    while (p != NULL && p->data != result)
        p = p->next;
    return p;
}

//構(gòu)造新的結(jié)點(diǎn)央拖，申請空間
//找到鏈表的低i-1個(gè)結(jié)點(diǎn)
//修改指針插入結(jié)點(diǎn)
List *Insert(int result, int i, List *Ptrl) {
    List *p, *s;
    if (i == 1) {//判斷鏈表為空的時(shí)候
        s = (List *) malloc(sizeof(List));
        s->data = result;
        s->next = Ptrl;
        return s;
    }
    p = FindKth(i - 1, Ptrl);//查找第i-1個(gè)節(jié)點(diǎn)
    if (p == NULL) {
        printf("參數(shù)錯(cuò)誤");
        return NULL;
    } else {
        s = (List *) malloc(sizeof(List));
        s->data = result;
        s->next = p->next;
        p->next = s;
        return Ptrl;
    }
}

List *Delete(int i, List *Ptrl) {
    List *p, *s;
    if (i == 1) {//檢查要刪除的是不是第一個(gè)結(jié)點(diǎn)
        s = Ptrl;//s指向第一個(gè)結(jié)點(diǎn)
        if (Ptrl != NULL)Ptrl = Ptrl->next;//從鏈表中刪除
        else return NULL;
        free(s);//釋放空間
        return Ptrl;
    }
    p = FindKth(i, Ptrl);
    if (p == NULL) {//后項(xiàng)前移
        printf("輸入錯(cuò)誤");
        return NULL;
    } else if (p->next != NULL) {
        s=p->next;
        p->next = s->next;
        free(s);//清理無用空間
        return Ptrl;
    }
}

更多關(guān)于java的文章請戳這里:（您的留言意見是對我最大的支持）

我的文章列表
Email:sxh13208803520@gmail.com