前言

編程語言，相當(dāng)于各個門派的武功；數(shù)據(jù)結(jié)構(gòu)，則相當(dāng)于內(nèi)功。習(xí)得一招一式，稱霸武林，內(nèi)功修煉必不可少！
這篇文章系本人原創(chuàng)，謝絕轉(zhuǎn)載。
以下將介紹數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)也是最重要的一種結(jié)構(gòu)——線性表。
線性表是最基本的數(shù)據(jù)結(jié)構(gòu)，有兩種存儲方式：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)
注意：同一個線性表中的元素類型必須相同。

一、順序結(jié)構(gòu)

順序表中，相鄰元素之間的物理地址是連續(xù)的，也就是說，計算機(jī)會用一組連續(xù)的內(nèi)存單元存放表中各個元素。從下面的代碼中可以看出數(shù)組cs的指針地址指向第一個元素。

    char cs[] = {'a','b','c'};
    printf("cs = %p \n",cs);//打印數(shù)組地址
    
    for (int i = 0; i < 3; i++) {
        printf("cs[%d] = %p\n", i, &cs[i]);//打印元素地址
    }
    /*
     打印結(jié)果
     cs = 0x7ffee82dc08d
     cs[0] = 0x7ffee82dc08d
     cs[1] = 0x7ffee82dc08e
     cs[2] = 0x7ffee82dc08f
     */

下面是一道經(jīng)典的數(shù)組指針的面試題

int a[5] = { 1, 2, 3, 4, 5 };
int *p = (int *)(&a + 1);
printf("%d,%d \n", *(a + 1), *(p - 1));
//打印結(jié)果：2，5

由于數(shù)組中的元素的地址是連續(xù)的，又因為int型占4個字節(jié)。*是指針運算符，&是取址運算符，它倆是互為相反的。具體可以看*運算符與&運算符

分析步驟
1.打印數(shù)組中元素地址
for (int i=0; i < 5; i++) {
     printf("a[%d] = %p\n", i, &a[i]);
 }
/*
a[0] = 0x7ffee79d3080
a[1] = 0x7ffee79d3084
a[2] = 0x7ffee79d3088
a[3] = 0x7ffee79d308c
a[4] = 0x7ffee79d3090
*/
2.&a取出a的地址，也就是第一個元素的地址，然后+1，則p指向a數(shù)組最后一個元素的后面一個存儲空間，打印出p的指針為p = 0x7ffee79d3094，然后p-1，則相當(dāng)于向前移動4個字節(jié)，所以指向的是數(shù)組a中最后一個元素，結(jié)果為5。a是數(shù)組名，也是首元素的地址，然后+1，則相當(dāng)于后移動4個字節(jié)，所以指向第二個元素，結(jié)果為2。

1.插入刪除操作時，效率比較低

這是因為在插入、刪除時，需要移動大量的數(shù)據(jù)元素，比較耗時。假設(shè)順序表中元素個數(shù)為n(不考慮順序表擴(kuò)容問題)，將新元素插入最后一個位置，則時間復(fù)雜度為O(1)；插入新的元素到第一個位置，則需要將之后的n個元素整體向后移動，時間復(fù)雜度為O(n)，平均的時間復(fù)雜度為O((n+1)/2)，也就是平均需要移動一半的元素。刪除元素也是同理。

2.存取元素值效率比較高

如果已知元素的下標(biāo)，則可以直接取出或修改元素的值，時間復(fù)雜度為O(1)。如果已知元素值為x，查找出元素的下標(biāo)，則需要從第一個元開始分別與x比較，如果該元素剛好在第一個元素，則時間復(fù)雜度為O(1)，如果在最后一個元素則為O(n)，平均為O((n+1)/2)。
總結(jié)：順序表在插入刪除時，需要大量移動數(shù)據(jù)元素，效率較低。由于是靜態(tài)存儲結(jié)構(gòu)，需要確定數(shù)組的大小，容量有限。適用于頻繁存取元素數(shù)據(jù)。
具體實現(xiàn)如下：

 #define MAXSIZE 10

typedef struct {
    int data[MAXSIZE];
    int last;//記錄數(shù)組中最后一個元素的位置，默認(rèn)值為-1，表是空表
}SeqList;

//指定位置插入元素
int insert_seqList(SeqList *list,int i,int x){
    if(list->last == MAXSIZE-1){
        return -1;//表空間已滿，不能插入
    }
    
    if(i < 0 || i > list->last+1){
        return -1;//插入位置不正確
    }else{
        //將i之后的元素整體向后移動
        for (int j = list->last; j>=i; j--) {
            list->data[j+1] = list->data[j];
        }
        list->data[i] = x;
        list->last++;
    }
    return 1;
}

//刪除指定位置的元素
void delete_seqList(SeqList *list,int i){
    if(list->last < 0){
        return;//空表
    }
    if(i<0 || i>list->last+1){
        return;//刪除的下標(biāo)越界
    }
    //i之后的元素整體向前移動
    for (int j=i; j<list->last; j++) {
        list->data[j] = list->data[j+1];
    }
    list->last--;
}
//根據(jù)數(shù)值查找出在表中的下標(biāo)
int location_seqlist(SeqList *list,int x){
    if(list->last < 0){
        return -1;//空表
    }
    for (int i=0; i<=list->last; i++) {
        if(list->data[i] == x){
            return i;
        }
    }
    return -1;
}
//打印數(shù)組
void print_list(SeqList *list){
    if(list->last < 0){
        printf("數(shù)組為空 \n");
    }else{
        printf("--------------數(shù)據(jù)個數(shù)為 %d--------------\n",list->last+1);
        for (int i=0; i<list->last+1; i++) {
            printf("數(shù)組第%d個 = %d \n",i,list->data[i]);
        }
    }
}

int main(int argc, char * argv[]) {
    NSLog(@"%s",__func__);
    
    SeqList list;
    //設(shè)置默認(rèn)值
    list.last = 2;
    list.data[0] = 1;
    list.data[1] = 2;
    list.data[2] = 3;
    
    //插入
    insert_seqList(&list, 0, 11);
    insert_seqList(&list, 0, 22);
    insert_seqList(&list, 0, 33);
    insert_seqList(&list, 0, 44);
    insert_seqList(&list, 0, 55);
    print_list(&list);
    
    //刪除
    delete_seqList(&list, 0);
    delete_seqList(&list, 5);
    print_list(&list);
    
    int i = location_seqlist(&list, 3);
    printf("數(shù)據(jù)下標(biāo) i = %d \n",i);
}

二、鏈表結(jié)構(gòu)

鏈表中元素的物理地址可以是不連續(xù)的。鏈表與順序表不同，它是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個節(jié)點占用的內(nèi)存空間不是預(yù)先分配的，而是運行時系統(tǒng)根據(jù)需求生成的。
每個節(jié)點包含元素數(shù)值外，還包含下一個節(jié)點的地址，如果是雙向鏈表，還包含上一個節(jié)點的地址。

1.插入刪除操作，效率較高

由于鏈表在插入刪除時，不需要大量移動數(shù)據(jù)元素。又因為是動態(tài)存儲結(jié)構(gòu)，不需要預(yù)先定義大小，可根據(jù)需求申請或釋放節(jié)點。如果在某個節(jié)點p之后插入新的節(jié)點s，則時間復(fù)雜度為O(1)。如果在某個節(jié)點p之前插入新的節(jié)點s，則需要從第一個節(jié)點開始遍歷找到新節(jié)點s的直接前驅(qū)節(jié)點p，時間復(fù)雜度為O(n)，有一種更好的實現(xiàn)方式，直接將新的節(jié)點s插入到節(jié)點p之后，然后交換節(jié)點p于節(jié)點s的數(shù)值，這樣的操作時間復(fù)雜度為O(1)。

2.存取元素值效率比較低

不適用于直接存取操作，要取出表中任意一個元素必須從第一個元素開始向后查詢。如果查找的節(jié)點是第一個節(jié)點，則時間復(fù)雜度為O(1)；如果查找的節(jié)點是最后一個節(jié)點，則時間復(fù)雜度為O(n)，平均操作時間復(fù)雜度為O((n+1)/2)。
1.單向鏈表
對單向鏈表而言，只能從頭節(jié)點開始遍歷整個鏈表。
單向鏈表的使用例子，計算兩個多項式的和

//頭文件
@interface WLPoly : NSObject

@property (nonatomic,assign) NSInteger coef;//系數(shù)
@property (nonatomic,assign) NSInteger exp;//指數(shù)

@property (nonatomic,strong) WLPoly *nextNode;

//兩個多項式相加
+(void)addPoly:(WLPoly *)poly1 poly2:(WLPoly *)poly2;
//打印多項式
+(void)printPoly:(WLPoly *)poly;

@end


//實現(xiàn)
//多項式的相加
+(void)addPoly:(WLPoly *)poly1 poly2:(WLPoly *)poly2{
    WLPoly *p = poly1.nextNode;//多項式1的相加指針變量
    WLPoly *q = poly2.nextNode;//多項式2的相加指針變量
    WLPoly *r = poly1;//
    WLPoly *pc = poly1;//
    
    while (p != nil && q != nil) {
        //多項式的指數(shù)相等，系數(shù)相加
        if(p.exp == q.exp){
            NSInteger sum = p.coef + q.coef;
            
            if(sum != 0){//系數(shù)和非零
                p.coef = sum;
                r = p;
            }else{//系數(shù)和為零
                r.nextNode = p.nextNode;
            }
            p = p.nextNode;
            q = q.nextNode;
            
        }else if(p.exp > q.exp){
            r.nextNode = p;
            r = p;
            p = p.nextNode;
        }else{
            r.nextNode = q;
            r = q;
            q = q.nextNode;
        }
    }
    if(p == nil){
        r.nextNode = q;
    }else{
        r.nextNode = p;
    }
    [self printPoly:pc];
}

+(void)printPoly:(WLPoly *)poly{
    if(poly == nil){
        return;
    }
    NSMutableString *string = [[NSMutableString alloc]initWithCapacity:10];
    WLPoly *p = poly.nextNode;
    while (p != nil) {
        
        NSString *s = [NSString stringWithFormat:@"%ldX%ld",p.coef,p.exp];
        if(p.coef < 0){
            s = [NSString stringWithFormat:@"%ldX%ld",-p.coef,p.exp];
            if(string.length > 0){
                [string appendString:@" - "];
            }
        }else{
            if(string.length > 0){
                [string appendString:@" + "];
            }
        }
        if(p.exp == 0){
            s= [NSString stringWithFormat:@"%ld",p.coef];
        }
        [string appendString:s];
        p = p.nextNode;
    }
    NSLog(@"最后結(jié)果：%@",string);
}

測試代碼
-(void)testPoly{
    WLPoly *polyA = [[WLPoly alloc]init];
    WLPoly *p1 = [self nextNodeWithCoef:6 exp:13];
    WLPoly *p2 = [self nextNodeWithCoef:2 exp:10];
    WLPoly *p3 = [self nextNodeWithCoef:-5 exp:4];
    WLPoly *p4 = [self nextNodeWithCoef:14 exp:0];
    polyA.nextNode = p1;
    p1.nextNode = p2;
    p2.nextNode = p3;
    p3.nextNode = p4;
    
    WLPoly *polyB = [[WLPoly alloc]init];
    WLPoly *q1 = [self nextNodeWithCoef:5 exp:13];
    WLPoly *q2 = [self nextNodeWithCoef:3 exp:11];
    WLPoly *q3 = [self nextNodeWithCoef:8 exp:6];
    WLPoly *q4 = [self nextNodeWithCoef:5 exp:4];
    polyB.nextNode = q1;
    q1.nextNode = q2;
    q2.nextNode = q3;
    q3.nextNode = q4;
    
    [WLPoly printPoly:polyA];
    [WLPoly printPoly:polyB];
    //[WLPoly addPoly:polyA poly2:polyB];
}

2.雙向鏈表
在單鏈表中，可以找到任意一個節(jié)點的后繼節(jié)點，但是無法找出他的前趨節(jié)點，這是單鏈表的缺點。
在雙向鏈表中，每個節(jié)點中，除了數(shù)據(jù)字段外，還包含了兩個指針，一個直線該節(jié)點的前趨節(jié)點，一個指向該節(jié)點的后繼節(jié)點。有兩個好處：一個是可以從頭和尾搜索某個節(jié)點。二是如果某一條鏈?zhǔn)Я耍€可以利用另一條鏈修復(fù)整個鏈表。
(1)插入一個新的節(jié)點
設(shè)p是雙向鏈表中的一個節(jié)點，pre代表前趨節(jié)點，next代表后繼節(jié)點，s指向值為x的新的節(jié)點。操作步驟如下：

s->pre = p->next;//1
p->pre ->next = s;//2
s->next = p;//3
p->pre = s;//4

示意圖如下

插入新節(jié)點.png

(2)刪除一個節(jié)點
設(shè)p是雙向鏈表中的一個節(jié)點，pre代表前趨節(jié)點，刪除p節(jié)點，操作步驟如下：

p->pre->next = p->next;//1
p->next->pre = p->pre;//2
free(p);

示意圖如下

刪除節(jié)點.png

3.循環(huán)鏈表
單循環(huán)鏈表是在單鏈表基礎(chǔ)上，將表頭指針放入鏈表尾部節(jié)點的指針域中，這就構(gòu)成了單循環(huán)鏈表了。單循環(huán)鏈表可以從表中任意一個節(jié)點開始遍歷整個鏈表。
在實際應(yīng)用中，一般使用尾指針代替頭指針來進(jìn)行某種操作，比如，將兩個單循環(huán)鏈表首尾相連。

設(shè)定單循環(huán)鏈表hr1、hr2，它們的尾節(jié)點分別為r1、r2，操作語句如下
r2->next = r1->next;//將第一個鏈表的尾節(jié)點的下一個節(jié)點指針接入到第二個鏈表的尾節(jié)點中
r1->next = hr2->next;//將第二個鏈表的頭節(jié)點的下一個節(jié)點指針接入到第一個鏈表的尾節(jié)點中
free(hr2);//釋放第二個鏈表
r1 = r2;//合并成一個單循環(huán)鏈表，只有一個尾節(jié)點

操作示意圖如下

操作示意圖.png

三、如何選擇存儲結(jié)構(gòu)

通?；谝韵氯c考慮

1.存儲空間

順序表的存儲空間，在運行前必須聲明大小，也就是說，必須設(shè)定一個最大值，如果最大值設(shè)置過大，則會造成資源浪費；如果設(shè)置過小，則容易溢出(這里不考慮擴(kuò)容)。如果需要實現(xiàn)擴(kuò)容，則需要重新創(chuàng)建一個更大的數(shù)組，然后將原數(shù)組中的元素拷貝到新的數(shù)組中，開銷比較大。
鏈表不需要考慮存儲空間大小，但鏈表的存儲密度較低(存儲密度是指一個節(jié)點中數(shù)據(jù)元素所占的存儲單元和整個節(jié)點所占存儲單元之比)。顯然鏈表的存儲密度小于1。

2.運算

順序表中，訪問第i個元素的時間復(fù)雜度為O(1)，而鏈表中訪問第i個元素的時間復(fù)雜度為O((n+1)/2)。所以，頻繁訪問元素，則順序表優(yōu)于鏈表。從插入刪除角度考慮，則鏈表優(yōu)于順序表。

3.運行環(huán)境

順序表比較容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針，相對來說，前者更簡單一點。