前言

編程語言赡勘，相當(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ù)的欣喧，又因?yàn)閕nt型占4個字節(jié)。*是指針運(yùn)算符梯找，&是取址運(yùn)算符唆阿，它倆是互為相反的。具體可以看*運(yùn)算符與&運(yùn)算符

分析步驟
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.插入刪除操作時屑埋，效率比較低

這是因?yàn)樵诓迦牒荔荨h除時，需要移動大量的數(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ù)钙勃。
具體實(shí)現(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é)點(diǎn)占用的內(nèi)存空間不是預(yù)先分配的，而是運(yùn)行時系統(tǒng)根據(jù)需求生成的矾湃。
每個節(jié)點(diǎn)包含元素數(shù)值外亡脑，還包含下一個節(jié)點(diǎn)的地址，如果是雙向鏈表邀跃，還包含上一個節(jié)點(diǎn)的地址霉咨。

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

由于鏈表在插入刪除時坞嘀，不需要大量移動數(shù)據(jù)元素躯护。又因?yàn)槭莿討B(tài)存儲結(jié)構(gòu)，不需要預(yù)先定義大小丽涩，可根據(jù)需求申請或釋放節(jié)點(diǎn)棺滞。如果在某個節(jié)點(diǎn)p之后插入新的節(jié)點(diǎn)s裁蚁，則時間復(fù)雜度為O(1)。如果在某個節(jié)點(diǎn)p之前插入新的節(jié)點(diǎn)s继准，則需要從第一個節(jié)點(diǎn)開始遍歷找到新節(jié)點(diǎn)s的直接前驅(qū)節(jié)點(diǎn)p枉证，時間復(fù)雜度為O(n)，有一種更好的實(shí)現(xiàn)方式移必，直接將新的節(jié)點(diǎn)s插入到節(jié)點(diǎn)p之后室谚，然后交換節(jié)點(diǎn)p于節(jié)點(diǎn)s的數(shù)值，這樣的操作時間復(fù)雜度為O(1)崔泵。

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

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

//頭文件
@interface WLPoly : NSObject

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

@property (nonatomic,strong) WLPoly *nextNode;

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

@end


//實(shí)現(xiàn)
//多項(xiàng)式的相加
+(void)addPoly:(WLPoly *)poly1 poly2:(WLPoly *)poly2{
    WLPoly *p = poly1.nextNode;//多項(xiàng)式1的相加指針變量
    WLPoly *q = poly2.nextNode;//多項(xiàng)式2的相加指針變量
    WLPoly *r = poly1;//
    WLPoly *pc = poly1;//
    
    while (p != nil && q != nil) {
        //多項(xiàng)式的指數(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é)點(diǎn)的后繼節(jié)點(diǎn)肮帐，但是無法找出他的前趨節(jié)點(diǎn)，這是單鏈表的缺點(diǎn)边器。
在雙向鏈表中泪姨，每個節(jié)點(diǎn)中，除了數(shù)據(jù)字段外饰抒，還包含了兩個指針肮砾，一個直線該節(jié)點(diǎn)的前趨節(jié)點(diǎn)，一個指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)袋坑。有兩個好處：一個是可以從頭和尾搜索某個節(jié)點(diǎn)仗处。二是如果某一條鏈?zhǔn)Я耍€可以利用另一條鏈修復(fù)整個鏈表枣宫。
(1)插入一個新的節(jié)點(diǎn)
設(shè)p是雙向鏈表中的一個節(jié)點(diǎn)婆誓，pre代表前趨節(jié)點(diǎn)，next代表后繼節(jié)點(diǎn)也颤，s指向值為x的新的節(jié)點(diǎn)洋幻。操作步驟如下：

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

示意圖如下

插入新節(jié)點(diǎn).png

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

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

示意圖如下

刪除節(jié)點(diǎn).png

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

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

操作示意圖如下

操作示意圖.png

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

通潮陕螅基于以下三點(diǎn)考慮

1.存儲空間

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

2.運(yùn)算

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

3.運(yùn)行環(huán)境

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