存儲(chǔ)密度 = （結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量）/（結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量）

2.1鏈表結(jié)構(gòu)定義

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

鏈表完整結(jié)構(gòu)：（頭指針/頭結(jié)點(diǎn)）+（首元結(jié)點(diǎn)）+NULL

typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;
//這里定義用到了遞歸

鏈表初始化:

int Initial_LinkList(LinkList &L){
    L=new LNode;
    if(!L){return -1;}
    L.next=NULL;
    return 0;
}

int main(){
    LinkList L;
    Initial_LinkList(L);
}

說明：函數(shù)傳參什么時(shí)候使用指針的引用？
一般來說，用指針做參數(shù)，表示把變量的地址傳遞給子函數(shù)，子函數(shù)只能修改指針?biāo)缸兞康闹担⒉荒苄薷闹羔樀闹赶?。如果想用修改指針的指向，就要用指針的指針，或者指針的引用。指針引用的典型例子?/p>

• 場(chǎng)景一：
  主函數(shù)中定義了指針但并未申請(qǐng)空間（野指針），要將指針做參數(shù)傳給子函數(shù)，在子函數(shù)中申請(qǐng)空間，這時(shí)候一定要用指針的引用（因?yàn)橹羔標(biāo)傅倪@塊內(nèi)存發(fā)生了改變，或者說指針的指向發(fā)生了改變）。
• 場(chǎng)景二：
  鏈表做參數(shù)時(shí)，在遍歷，查找操作子函數(shù)時(shí)，鏈表不會(huì)發(fā)生改變，那就用頭結(jié)點(diǎn)的指針做參數(shù)就可以了。但是在增加，修改，刪除這種操作時(shí)，鏈表頭結(jié)點(diǎn)指針?biāo)傅倪@塊內(nèi)存會(huì)發(fā)生改變，也就是指針的指向可能會(huì)發(fā)生改變，這種情況下就要頭指針的引用。同樣在二叉樹和圖的子函數(shù)中如果修改二叉樹和圖，那就要用指針的引用。
• 實(shí)在搞不清楚，就記?。?用引用總是沒有問題的。

2.2銷毀鏈表

int Destroy_LinkList(LinkList &L){
    LNode *p;
    while(L){
        p=L;
        L=L->next;
        delete p;
    }
}

2.3清空鏈表

順序表清空只要length歸零，這是因?yàn)轫樞虮砩珊笞畲箝L(zhǎng)度是一定的，所以只要將標(biāo)記位歸零即可。鏈表的長(zhǎng)度是靈活的，所以清空需要釋放除頭結(jié)點(diǎn)以外其他結(jié)點(diǎn)的內(nèi)存。

int Clear_LinkList(LinkList &L){
   LinkList p,q;
   p=L->next;   //跳過頭結(jié)點(diǎn)
   while(p)       //判斷是否到表尾 
      {  q=p->next; delete p; p=q;   }  //釋放后續(xù)結(jié)點(diǎn)內(nèi)存空間
   L->next=NULL;   //頭結(jié)點(diǎn)指針域置為空 
   return OK;
 }

2.4取值

int Get_LinkList(LinkList L,int n){
    LNode *p=L;int i=0;
    while(p&&i<n){
        i++;
        p=p->next;
    }
    if(!p||i>=n){
        return -1;
    }else{
        return p->data;
    }

說明：
1、順序表的遍歷條件是for (i=0;i< L.length;i++)，鏈表的遍歷條件是while(p){p=p->next;}
2、鏈表的長(zhǎng)度是未知的，所以在做查找、取值、插入、刪除時(shí)都可能超出序號(hào)范圍，且不能預(yù)先判斷，要在遍歷過程中設(shè)置判斷條件。

2.5循環(huán)列表

循環(huán)列表與單列表區(qū)別是：從循環(huán)鏈表任何一個(gè)結(jié)點(diǎn)都可以找到其他所有結(jié)點(diǎn)，而單鏈表做不到。循環(huán)列表可看成周長(zhǎng)變化的環(huán)，初始化L->next=L，遍歷結(jié)束條件p!=L。循環(huán)列表可以有頭結(jié)點(diǎn)或沒有，操作上會(huì)有區(qū)別。

2.6雙向鏈表

雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域。雙向循環(huán)鏈表是一種特殊情況。

2.7作業(yè)

作業(yè)1：將兩個(gè)遞增有序鏈表A、B合并為一個(gè)遞增有序鏈表C，要求不另外占用其他存儲(chǔ)空間，不允許有重復(fù)元素。

/*
思路：
1、C頭指針等于A的頭指針,p用來保存C的尾結(jié)點(diǎn)，初始位置在Lc ；p=Lc=La; 
2、比較A、B首元結(jié)點(diǎn)pa、pb的大小，如果pa小，將Lc的next指向pa，pa向下一個(gè)結(jié)點(diǎn)；
    if (pa->data<pb->data){p->next=pa;p=pa;pa=pa->next;}
3、如果pb小，將Lc的next指向pb，pb向下一個(gè)結(jié)點(diǎn)；
    if(pa->data>pb->data){p->next=pb;p=pb;pb=pb->next;}
4、如果pa、pb相等，將Lc的next指向pa，pa向下一個(gè)結(jié)點(diǎn)，刪除pb；
    if(pa->data=pb->data){p->next=pa;p=pa;pa=pa->next;del=pb;pb=pb->next;delete del;}
5、循環(huán)上述2、3、4直到pa或pb等于NULL（鏈尾）；while(pa&&pb){}
6、再把A或B剩下的部分接到C的后面；
    p->next=pa?pa:pb;
7、刪除B的頭結(jié)點(diǎn)；delete Lb； 
*/
void MergeLinkList(LinkList &La,LinkList &Lb,LinkList &Lc){
    LNode *p,*pa=La->next,*pb=Lb->next,*del;
    p=Lc=La;
    while(pa&&pb){
        if (pa->data<pb->data){
            p->next=pa;
            p=pa;
            pa=pa->next;
        }else if (pa->data>pb->data){
            p->next=pb;
            p=pb;
            pb=pb->next;
        }else{
            p->next=pa;
            p=pa;
            pa=pa->next;
            del=pb;
            pb=pb->next;
            delete del;
        }
    }
    
    p->next=pa?pa:pb;
    delete Lb; 
}

作業(yè)2：設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表La中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲(chǔ)空間。

int Invert_LinkList(LinkList &L){
    LNode *s1,*s2,*p=L,*r;
    if(p->next){
        r=s1=p=p->next;
     }else{return -1;}
    if(p->next){
        s2=p=p->next;
    }else{return -1;}
    p=p->next;
    while(p){
        s2->next=s1;
        s1=s2;
        s2=p;
        p=p->next;
    }
    s2->next=s1;
    L->next=s2;
    r->next=NULL;
    return 0;
}

作業(yè)3：已知長(zhǎng)度為n線性表采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一個(gè)算法刪除線性表中所有值為item的元素。

void RemoveElem(Sqlist &L){
    int item;
    printf("請(qǐng)輸入要?jiǎng)h除的元素：\n");
    scanf("%d",&item);
    
    int n=L.length;
    int j=0;
    for(int i=0;i<n;i++){
        if(L.head[i]!=item){L.head[j]=L.head[i];j++;}
    }
    L.length=j;
}

易錯(cuò)點(diǎn)：
條件語句經(jīng)常把判斷條件“==”寫成“=”。