線性表是一種最簡單的線性結(jié)構(gòu)

線性表是一種最簡單的線性結(jié)構(gòu)第二章線性表學習重點復習結(jié)構(gòu)體定義線性表的特點順序存儲的常用操作鏈表單鏈表循環(huán)鏈表雙向鏈表編寫程序的步驟與方法套路定義一個存儲結(jié)構(gòu)：順序表---動態(tài)數(shù)組（靜態(tài)數(shù)組）定義基于上述結(jié)構(gòu)的基本操作主程序一定有一個定義為上述存儲結(jié)構(gòu)的變量（初始化）實踐和調(diào)用基于此結(jié)構(gòu)的操作（函數(shù)）一定顯示變化的結(jié)果線性結(jié)構(gòu)的基本特征:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)

是一個數(shù)據(jù)元素的有序（次序）集2.3線性表的鏈式存儲

2.3.1

線性表的鏈式存儲—鏈表2.3.2單鏈表基本運算的實現(xiàn)

2.3.3雙鏈表2.3.4循環(huán)鏈表2.3.5靜態(tài)鏈表2.3—1單鏈表概念鏈表的定義空表鏈表的常用操作(回憶)創(chuàng)建鏈表方法:前插入法插入一個元素到鏈表刪除鏈表中一個元素引入帶頭結(jié)點的鏈表2.3.1.線性表的鏈式存儲結(jié)構(gòu)

將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點包含數(shù)據(jù)域和指針域。

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點的地址，最后一個結(jié)點的指針域為空。邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。a1a2an∧a3L…..線性表的鏈式存儲結(jié)構(gòu)可用C語言中的“結(jié)構(gòu)指針”來描述2.3.1線性表的鏈式存儲結(jié)構(gòu)定義帶頭結(jié)點的線性鏈表datanexttypedefstructLNode{intdata;StructLNode*next;}JD;a5a1a2a3a4a6a7a8^H為了編程方便，往往加上一個頭結(jié)點，就象這個樣子a4a1a2a3a5a6a8^a7H為什么加上頭結(jié)點會很方便？寫程序吧！你會有所發(fā)現(xiàn)的……存取第i個元素時，必須先存取前i-1個元素---順序存取H=NULLH->next=NULLLa1a2頭結(jié)點an^…...L空表^空的條件判斷：L->next=NULL;非空的條件：p=L;p->next!=NULL;p=p->next;

以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針頭結(jié)點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針空指針線性表為空表時，頭結(jié)點的指針域為空線性鏈表表示法:2.3.2鏈表的常用操作創(chuàng)建鏈表方法頭插法尾插法遍歷鏈表插入元素到鏈表刪除鏈表中的元素1.如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。2.3.2單鏈表基本運算的實現(xiàn)

1.建立單鏈表

先考慮如何建立單鏈表。假設我們通過一個含有n個數(shù)據(jù)的數(shù)組來建立單鏈表。建立單鏈表的常用方法有如下兩種:(1)頭插法建表該方法從一個空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點,將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:

voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點*/L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點*/s->data=a[i];s->next=L->next; /*將*s插在原開始結(jié)點之前,頭結(jié)點之后*/L->next=s;}}typedefintElem1;typedefint*Elem2;Elem1a=7;Elem2b;int*b;TypedefstructLnode*LinkList;LinkListhead;adcbi=0i=1i=2i=3∧head采用頭插法建立單鏈表的過程heada∧headda∧headcda∧headbcda∧第1步:建頭結(jié)點第2步:i＝0,新建a結(jié)點,插入到頭結(jié)點之后第3步:i＝1,新建d結(jié)點,插入到頭結(jié)點之后第4步:i＝2,新建c結(jié)點,插入到頭結(jié)點之后第5步:i＝3,新建b結(jié)點,插入到頭結(jié)點之后頭插入法生成的過程創(chuàng)建一個結(jié)點為頭結(jié)點L開辟空間L=mallocL->next=NULL插入元素到鏈表的頭部(反復執(zhí)行n次)定位到表的頭headhead->next生成一個新結(jié)點p=malloc插入該元素到原tail后面{p>data=x;P-next=head->next;Head->next=p;}(2)尾插法建表

頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點插到當前鏈表的表尾上,為此必須增加一個尾指針r,使其始終指向當前鏈表的尾結(jié)點。采用尾插法建表的算法如下:bcdai=0i=1i=2i=3head頭結(jié)點adcb∧b采用尾插法建立單鏈表的過程生成鏈表的過程重復準備加入的元素s開辟空間malloc插入在鏈表的尾部tail(r)定位在尾部r插入r->next=s;r=s;尾部的next=NULL生成的過程創(chuàng)建一個結(jié)點為頭結(jié)點L開辟空間L=mallocL->next=NULL插入元素到鏈表的尾部(反復執(zhí)行n次)定位到表的尾巴tail生成一個新結(jié)點p=malloc插入該元素到原tail后面{tail->next=p;p->next=NULL;p->data=x;}

voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建頭結(jié)點*/r=L;/*r始終指向終端結(jié)點,開始時指向頭結(jié)點*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點*/

s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}r->next=NULL; /*終端結(jié)點next域置為NULL*/}例1：逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟：一、建立一個“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；ananan-1四、依次類推，直至輸入a1為止。逆序生成插入an(鏈表L)1)生成一個節(jié)點p2）將P插入到l和l->next然后an-1a1voidCreateList_L(LinkList&L,intn){//逆序輸入n個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表}//CreateList_L算法的時間復雜度為:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一個帶頭結(jié)點的單鏈表for(i=n;i>0;--i){p=newLNode;

scanf(&p->data);//輸入元素值p->next=L->next;L->next=p;//插入}2.插入結(jié)點運算插入運算是將值為x的新結(jié)點插入到單鏈表的第i個結(jié)點的位置上。先在單鏈表中找到第i-1個結(jié)點,再在其后插入新結(jié)點。單鏈表插入結(jié)點的過程如下圖所示。插入結(jié)點示意圖插入位置的查找前提:L為頭結(jié)點，s為等待插入的元素，p代表當前位置，插入s在其后面插入在一個空表中:p->next=s;s->next=NULL插入在一個非空表中插入在頭結(jié)點后面s->next=p->next;p->next=s;插入在中間部位p之后s->next=p->next;p->next=s;插入在鏈表的尾部(p->next==NULL)p->next=s;s->next=p->next∧anaia1a2Pai-1L單鏈表的插入運算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點之后插入新的結(jié)點*/JD*s;/*定義指向結(jié)點類型的指針*/s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點*/

s->data=x;s->next=p->next;p->next=s;returnOK;}∧anaia1a2Pai-1L單鏈表的插入運算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點之后插入新的結(jié)點*/JD*s;/*定義指向結(jié)點類型的指針*/

s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點*/

s->data=x;s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL單鏈表的插入運算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點之后插入新的結(jié)點*/JD*s;/*定義指向結(jié)點類型的指針*/s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL單鏈表的插入運算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點之后插入新的結(jié)點*/JD*s;/*定義指向結(jié)點類型的指針*/s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}S∧anaia1a2Pai-1xL單鏈表的插入運算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點之后插入新的結(jié)點*/JD*s;/*定義指向結(jié)點類型的指針*/s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點*/

s->data=x;s->next=p->next;

p->next=s;returnOK;}ai-1a1aiai+1Lpvoidlbsc(JD*p)/*刪除p指針指向結(jié)點的后一個結(jié)點*/{JD*q;if(p->next!=NULL)p->next=p->next->next;{q=p->next;/*q指向p的后繼結(jié)點*/p->next=q->next;/*修改p結(jié)點的指針域*/free(q);/*刪除并釋放結(jié)點*/}}3.單鏈表的刪除運算刪除結(jié)點示意圖ai-1a1aiai+1Lpvoidlbsc(JD*p)/*刪除p指針指向結(jié)點的后一個結(jié)點*/{JD*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點*/p->next=q->next;/*修改p結(jié)點的指針域*/

free(q);/*刪除并釋放結(jié)點*/}}單鏈表的刪除運算4.線性鏈表的查找操作：設無表頭結(jié)點的線性鏈表的頭指針為h,沿著鏈表的開始往后找結(jié)點x，若找到，則返回該結(jié)點在鏈表中的位置，否則返回空地址。JD*lbcz(JD*h,intx){JD*p;p=h;while(p!=NULL&&p->data!=x)p=p->next;return(p);}4.線性表基本運算實現(xiàn)(1)初始化線性表InitList(L)該運算建立一個空的單鏈表,即創(chuàng)建一個頭結(jié)點。

voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點*/ L->next=NULL;}(2)銷毀線性表DestroyList(L)釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點的空間。voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=NULL) {free(p); p=q;q=p->next; } free(p);}

(3)判線性表是否為空表ListEmpty(L)若單鏈表L沒有數(shù)據(jù)結(jié)點,則返回真,否則返回假。

intListEmpty(LinkList*L){ return(L->next==NULL);}

(4)求線性表的長度ListLength(L)返回單鏈表L中數(shù)據(jù)結(jié)點的個數(shù)。

intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=NULL) {i++; p=p->next; } return(i);}(5)輸出線性表DispList(L)逐一掃描單鏈表L的每個數(shù)據(jù)結(jié)點,并顯示各結(jié)點的data域值。

voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}(6)求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e)思路：在單鏈表L中從頭開始找到第i個結(jié)點,若存在第i個數(shù)據(jù)結(jié)點,則將其data域值賦給變量e。

intGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p=L; while(j<i&&p!=NULL) {j++; p=p->next; } if(p==NULL)return0;/*不存在第i個數(shù)據(jù)結(jié)點*/ else /*存在第i個數(shù)據(jù)結(jié)點*/ {e=p->data; return1; }}(7)按元素值查找LocateElem(L,e)

思路：在單鏈表L中從頭開始找第1個值域與e相等的結(jié)點,若存在這樣的結(jié)點,則返回位置,否則返回0。intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next;intn=1; while(p!=NULL&&p->data!=e) {p=p->next;n++;} if(p==NULL)return(0); elsereturn(n);}(8)插入數(shù)據(jù)元素ListInsert(&L,i,e)

思路：先在單鏈表L中找到第i-1個結(jié)點*p,若存在這樣的結(jié)點,將值為e的結(jié)點*s插入到其后。intListInsert(LinkList*&L,inti,ElemTypee){intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/*查找第i-1個結(jié)點*/{j++; p=p->next;}

if(p==NULL)return0;/*未找到位序為i-1的結(jié)點*/

else /*找到位序為i-1的結(jié)點*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建新結(jié)點*s*/ s->data=e; s->next=p->next;/*將*s插入到*p之后*/ p->next=s; return1; }}(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e)思路：先在單鏈表L中找到第i-1個結(jié)點*p,若存在這樣的結(jié)點,且也存在后繼結(jié)點,則刪除該后繼結(jié)點。intListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; while(j<i-1&&p!=NULL)/*查找第i-1個結(jié)點*/ {j++; p=p->next; } if(p==NULL)return0;/*未找到位序為i-1的結(jié)點*/ else /*找到位序為i-1的結(jié)點*p*/ {q=p->next; /*q指向要刪除的結(jié)點*/ if(q==NULL)return0; /*若不存在第i個結(jié)點,返回0*/ p->next=q->next; /*從單鏈表中刪除*q結(jié)點*/ free(q); /*釋放*q結(jié)點*/ return1; }}兩個有序鏈表的合并的算法拿兩個指針指向兩個鏈表的第一個元素設pa—Lapb—LbLc首先是一個空表（思想是創(chuàng)建Lc）{選取插入的元素(小的元素)插入到lc}將剩余的元素鏈在pc后面(if(pc==pa)if(pa!=NULL)pc->next=pa;if(pb!=NULL)pc->next=pb;鏈表操作的基本掌握定義鏈表的存儲結(jié)構(gòu)創(chuàng)建一個鏈表（頭插入法尾插入法）輸入鏈表、查找鏈表的指定元素在指定位置刪除、插入元素

例2.5設C={a1,b1,a2,b2,…,an,bn}為一線性表,采用帶頭結(jié)點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}

解:設拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放。先建立兩個頭結(jié)點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾,用p指針掃描單鏈表hc,將當前結(jié)點*p鏈到ha未尾,p沿next域下移一個結(jié)點,若不為空,則當前結(jié)點*p鏈到hb未尾,p沿next域下移一個結(jié)點,如此這樣,直到p為空。最后將兩個尾結(jié)點的next域置空。對應算法如下:voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc; /*ha的頭結(jié)點利用hc的頭結(jié)點*/ra=ha;/*ra始終指向ha的末尾結(jié)點*/hb=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建hb頭結(jié)點*/rb=hb;/*rb始終指向hb的末尾結(jié)點*/while(p!=NULL){ra->next=p;ra=p;/*將*p鏈到ha單鏈表未尾*/p=p->next;if(p!=NULL){rb->next=p;rb=p; /*將*p鏈到hb單鏈表未尾*/p=p->next;}}ra->next=rb->next=NULL;/*兩個尾結(jié)點的next域置空*/}

本算法實際上是采用尾插法建立兩個新表。所以,尾插法建表算法是很多類似習題的基礎！

例2.6有一個帶頭結(jié)點的單鏈表head,其ElemType類型為char,設計一個算法使其元素遞增有序。解:若原單鏈表中有一個或以上的數(shù)據(jù)結(jié)點,先構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表(只含一個數(shù)據(jù)結(jié)點的單鏈表一定是有序表)。掃描原單鏈表余下的結(jié)點*p(直到p==NULL為止),在有序表中通過比較找插入*p的前驅(qū)結(jié)點*q,然后將*p插入到*q之后(這里實際上采用的是直接插入排序方法)。

鏈表排序的思想從頭開始掃描原鏈表到尾部將第一元素放在一張單獨鏈表中將原鏈表中所有元素逐一和頭比較,小的插入在其前面插入比較的過程中篩選出小的元素來voidSort(LinkList*&head){ LinkList*p=head->next,*q,*r; if(p!=NULL)/*head有一個或以上的數(shù)據(jù)結(jié)點*/ {r=p->next;/*r保存*p結(jié)點后繼結(jié)點的指針*/ p->next=NULL;/*構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結(jié)點后繼結(jié)點的指針*/

q=head; while(q->next!=NULL&&q->next->data<p->data) q=q->next;/*在有序表中找插入*p的前驅(qū)結(jié)點*q*/p->next=q->next; /*將*p插入到*q之后*/ q->next=p; p=r; /*掃描原單鏈表余下的結(jié)點*/}}}鏈式存儲結(jié)構(gòu)的特點插入、刪除靈活方便，不需要移動結(jié)點，只要改變結(jié)點中指針域的值即可。適合于線性表是動態(tài)變化的,不進行頻繁查找操作、但經(jīng)常進行插入刪除時使用。

鏈表的查找只能從頭指針開始順序查找。鏈表實驗內(nèi)容假設帶頭結(jié)點的單鏈表是遞增有序的，設計算法在其中插入一個值為x的結(jié)點，并保持其遞增特性。設計算法以刪除鏈表中值為x的元素結(jié)點。設計算法將兩個遞增有序的帶頭結(jié)點的單鏈表A、B合并為一個遞增有序的帶頭結(jié)點的單鏈表，并要求算法的時間復雜度為兩個表長之和的數(shù)量級。設計算法將帶頭結(jié)點的雙循環(huán)鏈表L就地