線性表

1. 線性表的定義和特點(diǎn)

線性表：由(n>=0)個(gè)數(shù)據(jù)特性相同的元素構(gòu)成的有限序列吩坝。

  • 對(duì)于非空的線性表和線性結(jié)構(gòu)，其特點(diǎn)如下：

    1. 存在唯一的一個(gè)被稱作"第一個(gè)"的數(shù)據(jù)元素
    2. 存在唯一的一個(gè)被稱作"最后一個(gè)"的數(shù)據(jù)元素
    3. 除了第一個(gè)之外艇抠，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均有一個(gè)前驅(qū)
    4. 除了最后一個(gè)之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都有一個(gè)后繼

線性表中的元素的個(gè)數(shù)n定義為線性表的長度，如果n = 0則稱為空表蹋偏。

1.1 線性表的類型定義

ADT List{
        Data: 線性表的數(shù)據(jù)對(duì)象集合為{a1,a2,......an}尝偎，每個(gè)元素的類型均為DataType饶火。
                    除了第一個(gè)元素a1外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素致扯。
            除了最后一個(gè)元素an外肤寝，每個(gè)元素有且只有一個(gè)直接后繼元素。
              數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系抖僵。
    
Operation
    InitList(&L) 
    操作結(jié)果:初始化操作鲤看，建立一個(gè)空的線性表L.

    DestroyList(&L) 
    初始條件: 線性表L已存在
    操作結(jié)果: 銷毀線性表L.

    ClearList(&L)
    初始條件: 線性表L已存在
    操作結(jié)果: 將L重置為空表.

    ListEmpty(L)
    初始條件: 線性表L已存在
    操作結(jié)果: 若L為空表，則返回true耍群，否則返回false.

    ListLength(L)
    初始條件: 線性表L已存在
    操作結(jié)果: 返回L中數(shù)據(jù)元素的個(gè)數(shù)

    GetElem(L义桂，i，&e)
    初始條件: 線性表L已存在蹈垢，且1<=i<ListLength(L)
    操作結(jié)果: 用e返回L中第i個(gè)數(shù)據(jù)元素的值;

    LocateElem(L慷吊，e)
    初始條件: 線性表L已存在
    操作結(jié)果: 返回L中第1個(gè)值與e相同的元素在L中的位置. 若數(shù)據(jù)不存在則返回0;

    PriorElem(L，cur_e曹抬，&pre_e);
    初始條件: 線性表L已存在
    操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素溉瓶，且不是第一個(gè)，則用pre_e返回其前驅(qū)，否則操作失敗.

    NextElem(L堰酿，cur_e疾宏，&next_e);
    初始條件: 線性表L已存在
    操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)触创，則用next_e返回其后繼灾锯，否則操作失敗.

    ListInsert(L，i嗅榕，e);
    初始條件: 線性表L已存在顺饮，且1<=i<=listLength(L)
    操作結(jié)果: 在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L長度加1.

    ListDelete(L凌那，i);
    初始條件: 線性表L已存在兼雄，且1<=i<=listLength(L)
    操作結(jié)果: 刪除L的第i個(gè)元素，L的長度減1.

    TraverseList(L);
    初始條件: 線性表L已存在
    操作結(jié)果: 對(duì)線性表L進(jìn)行遍歷帽蝶，在遍歷的過程中對(duì)L的每個(gè)結(jié)點(diǎn)訪問1次. 
    
} ADT List;

2. 順序表

2.1 結(jié)構(gòu)設(shè)計(jì)

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType類型根據(jù)實(shí)際情況而定赦肋，這里假設(shè)為int */
typedef int ElemType;
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int Status;

/*線性結(jié)構(gòu)使用順序表的方式存儲(chǔ)*/

//順序表結(jié)構(gòu)設(shè)計(jì)
typedef struct {
    ElemType *datas;
    int length;
} SqList;

2.2 方法實(shí)現(xiàn)

//1.1 順序表初始化
Status InitList(SqList *L)
{
    // 為順序表分配一個(gè)大小為MAXSIZE的數(shù)組空間
    L->datas = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    // 存儲(chǔ)分配失敗退出
    if (!L->datas) exit(ERROR);
    //空表長度為0
    L->length = 0;
    return OK;
}

//1.2 順序表的取值
Status GetElem(SqList L, int idx, ElemType *elem)
{
    //判斷i值是否合理励稳，若不合理佃乘，返回ERROR
    if (idx < 0
        || idx > L.length) {
        return ERROR;
    }
    *elem = L.datas[idx];
    return OK;
}

//1.3 順序輸出List
Status TraverseList(SqList L)
{
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.datas[i]);
    printf("\n");
    return OK;
}

//1.4 順序表的插入
Status InsertList(SqList *L, int idx, ElemType elem)
{
    //idx值不合法判斷
    if (idx < 0
        || idx > L->length
        || L->length == MAXSIZE) { //存儲(chǔ)空間已滿
        return ERROR;
    }
    // 插入數(shù)據(jù)不在表尾,則先移動(dòng)出空余位置
    if (idx < L->length) {
        // 插入位置以及之后的位置后移動(dòng)1位
        for (int i = L->length; i > idx; i--)
            L->datas[i] = L->datas[i-1];
    }
    // 將新元素elem放入第idx個(gè)位置上
    L->datas[idx] = elem;
    // 長度+1
    ++L->length;
    return OK;
}

//1.5 順序表的刪除
Status ListDelete(SqList *L, int idx) {
    if (L->length == 0 //空表
        || idx < 0 //idx值不合法判斷
        || idx > L->length) {
        return ERROR;
    }
    if (idx < L->length) {
        // 被刪除元素之后的元素向前移動(dòng)
        for (int i = idx + 1; i < L->length; i++)
            L->datas[i-1] = L->datas[i];
    }
    // 長度-1
    --L->length;
    return OK;
}

//1.6 清空順序表
Status ClearList(SqList *L)
{
    L->length=0;
    return OK;
}

//1.7 判斷順序表清空
Status ListEmpty(SqList L)
{
    return L.length == 0;
}

//1.8 獲取順序表長度
int ListLength(SqList L)
{
    return L.length;
}

//1.9 順序表查找元素并返回位置
int LocateElem(SqList L, ElemType elem)
{
    int i;
    // 循環(huán)比較
    for (i = 0; i < L.length; i++)
        if (L.datas[i] == elem)
            return i;
    // 表里面沒找到
    return NOT_FOUND;
}

int main(int argc, const char * argv[]) {
    
    SqList L;
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入數(shù)據(jù)
    for (int i = 0; i < MAXSIZE; i++) {
        if (InsertList(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍歷
    TraverseList(L);
    
    //獲取第5個(gè)元素
    ElemType elem;
    GetElem(L, 5, &elem);
    printf("5th: %d\n", elem);
    
    //刪除第5個(gè)元素
    ListDelete(&L, 5);
    TraverseList(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is %dth element\n", loc);
    }
    
    return 0;
}

主函數(shù)：

int main(int argc, const char * argv[]) {
    
    SqList L;
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入數(shù)據(jù)
    for (int i = 0; i < MAXSIZE; i++) {
        if (InsertList(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍歷
    TraverseList(L);
    
    //獲取第5個(gè)元素
    ElemType elem;
    GetElem(L, 5, &elem);
    printf("5th: %d\n", elem);
    
    //刪除第5個(gè)元素
    ListDelete(&L, 5);
    TraverseList(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is %dth element\n", loc);
    }
    
    return 0;
}

// 輸出
Init OK.
0 1 2 3 4 5 6 7 8 9 
5th: 5
0 1 2 3 4 6 7 8 9 
6 is 5th element
Program ended with exit code: 0

3. 鏈表

3.1 結(jié)構(gòu)設(shè)計(jì)

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef int ElemType;
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼驹尼，如OK等 */
typedef int Status;

/*線性結(jié)構(gòu)使用順序表的方式存儲(chǔ)*/

//鏈表結(jié)構(gòu)設(shè)計(jì)
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node;

3.2 方法實(shí)現(xiàn)

//1.1 初始化單鏈表線性表
Status InitList(LinkList *L)
{
    //產(chǎn)生頭結(jié)點(diǎn),并使用L指向此頭結(jié)點(diǎn)
    *L = (LinkList)malloc(sizeof(Node));
    //存儲(chǔ)空間分配失敗
    if (*L == NULL) return ERROR;
    //將頭結(jié)點(diǎn)的指針域置空
    (*L)->next = NULL;
    return OK;
}

//1.2 單鏈表的取值
Status GetElem(LinkList L, int idx, ElemType *elem)
{
    // 用來計(jì)數(shù)
    int i = 0;
    // 聲明一個(gè)節(jié)點(diǎn)趣避，指向頭結(jié)點(diǎn)的下一個(gè)
    LinkList p = L->next;
    // p不為空，且i小于idx,則循環(huán)繼續(xù)
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    //如果p為空或者i>idx,則返回error
    if(!p || i > idx) return ERROR;
    //elem = p所指的結(jié)點(diǎn)的data
    *elem = p->data;
    return OK;
}

//1.3 順序輸出單鏈表
Status ListTraverse(LinkList L)
{
    // 聲明一個(gè)節(jié)點(diǎn)新翎，指向頭結(jié)點(diǎn)的下一個(gè)
    LinkList p = L->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

//1.4 單表的插入
Status ListInsert(LinkList *L, int idx, ElemType elem)
{
    int i = 0;
    LinkList p, s;
    // 尋找第idx-1個(gè)結(jié)點(diǎn)程帕，所以這里指向表頭
    p = *L;
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    // 第idx個(gè)元素不存在
    if(!p || i > idx) return ERROR;
    
    // 創(chuàng)建新節(jié)點(diǎn)
    s = (LinkList)malloc(sizeof(Node));
    s->data = elem;
    //將p的后繼結(jié)點(diǎn)賦值給s的后繼
    s->next = p->next;
    //將s賦值給p的后繼
    p->next = s;
    return OK;
}

//1.5 單鏈表刪除元素
Status ListDelete(LinkList *L, int idx, ElemType *elem)
{
    int i = 0;
    LinkList p, q;
    // 尋找第idx-1個(gè)結(jié)點(diǎn)，所以這里指向表頭
    p = *L;
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    // 第idx個(gè)元素不存在
    if(!p || i > idx) return ERROR;
    // q指向要?jiǎng)h除的結(jié)點(diǎn)
    q = p->next;
    // 將q的后繼賦值給p的后繼
    p->next = q->next;
    // 將q結(jié)點(diǎn)中的數(shù)據(jù)給elem
    *elem = q->data;
    // 釋放被刪除節(jié)點(diǎn)
    free(q);
    return OK;
}

//1.6 清空單鏈表
Status ClearList(LinkList *L)
{
    LinkList p, q;
    // 從表頭下一個(gè)開始刪
    p = (*L)->next;
    // 清空表頭地啰，防止野指針
    (*L)->next = NULL;
    while(p) {
        // q指向要?jiǎng)h除的結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        q = p->next;
        // 釋放被刪除節(jié)點(diǎn)
        free(p);
        // p變?yōu)橄乱粋€(gè)節(jié)點(diǎn)
        p = q;
    }
    return OK;
}

//1.7 判斷順序表清空
Status ListEmpty(LinkList L)
{
    return L->next == NULL;
}

//1.8 獲取順序表長度
int ListLength(LinkList L)
{
    int i = 0;
    LinkList p = L;
    while (p) {
        p = p->next;
        i++;
    }
    return i;
}

//1.9 順序表查找元素并返回位置
int LocateElem(LinkList L, ElemType elem)
{
    if (L->next == NULL) return NOT_FOUND;
    int i = 0;
    LinkList p = L->next;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        p = p->next;
        i++;
    }
    return NOT_FOUND;
}

主函數(shù)：

int main(int argc, const char * argv[]) {
    
    LinkList L;
    ElemType elem;
        
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入數(shù)據(jù)
    for (int i = 0; i < MAXSIZE; i++) {
        if (ListInsert(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍歷
    ListTraverse(L);
    
    //獲取第6個(gè)元素
    GetElem(L, 5, &elem);
    printf("6th: %d\n", elem);
    
    //刪除第6個(gè)元素
    ListDelete(&L, 5, &elem);
    //遍歷
    ListTraverse(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is at %d\n", loc);
    }
    
    return 0;
}

// 輸出
Init OK.
0 1 2 3 4 5 6 7 8 9 
6th: 5
0 1 2 3 4 6 7 8 9 
6 is at 5
Program ended with exit code: 0

3.3 初始化頭插法

新節(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后：

void CreateListHead(LinkList *L, int n){
    // 生成頭結(jié)點(diǎn)
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    // 循環(huán)前插入隨機(jī)數(shù)據(jù)
    LinkList p;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Node));
        p->data = i;
        // 新節(jié)點(diǎn)指向頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        p->next = (*L)->next;
        // 頭結(jié)點(diǎn)指向新節(jié)點(diǎn)
        (*L)->next = p;
    }
}

3.4 初始化尾插法

新節(jié)點(diǎn)插入到最后：

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    // 建立1個(gè)帶頭結(jié)點(diǎn)的單鏈表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的結(jié)點(diǎn)
    r = *L;
    // 循環(huán)尾插入隨機(jī)數(shù)據(jù)
    for (int i = 0; i < n; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        // 尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
        r->next = p;
        // r指向當(dāng)前的尾節(jié)點(diǎn)
        r = p;
    }
    // 插入完畢愁拭，尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)應(yīng)該為NULL
    r->next = NULL;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市亏吝，隨后出現(xiàn)的幾起案子岭埠，更是在濱河造成了極大的恐慌，老刑警劉巖蔚鸥，帶你破解...
    沈念sama閱讀 211,194評(píng)論 6贊 490
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件惜论，死亡現(xiàn)場離奇詭異，居然都是意外死亡株茶，警方通過查閱死者的電腦和手機(jī)来涨，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,058評(píng)論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門图焰，熙熙樓的掌柜王于貴愁眉苦臉地迎上來启盛，“玉大人，你說我怎么就攤上這事〗┐常” “怎么了卧抗？”我有些...
    開封第一講書人閱讀 156,780評(píng)論 0贊 346
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長鳖粟。 經(jīng)常有香客問我社裆，道長，這世上最難降的妖魔是什么向图？ 我笑而不...
    開封第一講書人閱讀 56,388評(píng)論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任泳秀，我火速辦了婚禮，結(jié)果婚禮上榄攀，老公的妹妹穿的比我還像新娘嗜傅。我一直安慰自己，他們只是感情好檩赢，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,430評(píng)論 5贊 384
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布吕嘀。 她就那樣靜靜地躺著，像睡著了一般贞瞒。 火紅的嫁衣襯著肌膚如雪偶房。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 49,764評(píng)論 1贊 290
  • 城市分裂傳說
    那天军浆，我揣著相機(jī)與錄音棕洋，去河邊找鬼。 笑死乒融，一個(gè)胖子當(dāng)著我的面吹牛拍冠，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播簇抵，決...
    沈念sama閱讀 38,907評(píng)論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼庆杜，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼！你這毒婦竟也來了碟摆？” 一聲冷哼從身側(cè)響起晃财，我...
    開封第一講書人閱讀 37,679評(píng)論 0贊 266
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎典蜕，沒想到半個(gè)月后断盛，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 44,122評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡愉舔，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,459評(píng)論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年钢猛，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片轩缤。...
    茶點(diǎn)故事閱讀 38,605評(píng)論 1贊 340
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡命迈，死狀恐怖贩绕，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情壶愤，我是刑警寧澤淑倾，帶...
    沈念sama閱讀 34,270評(píng)論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站征椒，受9級(jí)特大地震影響娇哆，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜勃救，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,867評(píng)論 3贊 312
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一碍讨、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧蒙秒，春花似錦垄开、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,734評(píng)論 0贊 21
  • 一樁弒父案溉躲，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至益兄，卻和暖如春锻梳，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背净捅。 一陣腳步聲響...
    開封第一講書人閱讀 31,961評(píng)論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來泰國打工疑枯， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人蛔六。 一個(gè)月前我還...
    沈念sama閱讀 46,297評(píng)論 2贊 360
  • 代替公主和親
    正文 我出身青樓荆永，卻偏偏與公主長得像，于是被迫代替她去往敵國和親国章。 傳聞我的和親對(duì)象是個(gè)殘疾皇子具钥，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,472評(píng)論 2贊 348