簡(jiǎn)單鏈表及其應(yīng)用

鏈表是指將一組同類型數(shù)據(jù)（通常為結(jié)構(gòu)體類型）按其特有的方式連接在一起的一種數(shù)據(jù)結(jié)構(gòu)。鏈表中的元素稱為結(jié)點(diǎn)。每一個(gè)結(jié)點(diǎn)都包含兩類數(shù)據(jù)：一類數(shù)據(jù)稱為結(jié)點(diǎn)的值域，它是描述該結(jié)點(diǎn)所包含的實(shí)際數(shù)據(jù)，可以由多個(gè)不同類型的數(shù)據(jù)構(gòu)成；另一類數(shù)據(jù)稱為鏈域，它用來(lái)存儲(chǔ)與本結(jié)點(diǎn)相鄰的結(jié)點(diǎn)的地址，其作用是將各個(gè)結(jié)點(diǎn)連接在一起，它通常是與結(jié)點(diǎn)同類型的指針。任何一個(gè)鏈表都一個(gè)起始指針，稱為該鏈表的頭指針（head）。鏈表的最后一個(gè)結(jié)點(diǎn)稱為尾結(jié)點(diǎn)，它的鏈域指針不指向任何結(jié)點(diǎn)，通常將它設(shè)置為空指針。特點(diǎn)

每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點(diǎn)可以不連續(xù)存儲(chǔ)表可擴(kuò)充單鏈表(SinglyLinkedList)data

linka0a1a2a3a4head存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)后繼結(jié)點(diǎn)存儲(chǔ)地址頭結(jié)點(diǎn)空指針某單鏈表示意圖如下：頭指針head…………………110hat200………….……130cat135135eat170……….……160matNull165bat130170fat110………………200jat205205lat160………………165headbat

cat

eat

mat

^

…

用C++語(yǔ)言描述的一個(gè)簡(jiǎn)單的單鏈表如下：structnode{intdata;//值域node*next;//鏈域};例.建立一個(gè)簡(jiǎn)單的鏈表，它由3個(gè)學(xué)生數(shù)據(jù)的結(jié)點(diǎn)組成，輸出各結(jié)點(diǎn)中的數(shù)據(jù)。#defineNULL0p=head;structstudentdo{longnum;{cout<<p->num<<p->score;

floatscore;p=p->next;

student*next;}while(p!=NULL);}};voidmain()

{studenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;/*將結(jié)點(diǎn)a的起始地址賦給頭指針head*/a.next=&b;/*將結(jié)點(diǎn)b的起始地址賦給a結(jié)點(diǎn)的next成員*/b.next=&c;c.next=NULL;將結(jié)點(diǎn)設(shè)置為表頭的過(guò)程如下圖所示：pNewhead(b)

加入結(jié)點(diǎn)后head=pNew;pEnd=pNew;pEnd頭結(jié)點(diǎn)加入結(jié)點(diǎn)前

head=0;

pEnd=pNew;pEndheadpNew將結(jié)點(diǎn)加到鏈表末尾的過(guò)程如下圖所示：nextdatanextnext…datadata頭結(jié)點(diǎn)結(jié)點(diǎn)n…新結(jié)點(diǎn)pNewpEndhead(a)加入前pNew=newnode;nextnext…datadata頭結(jié)點(diǎn)結(jié)點(diǎn)n…nextdata結(jié)點(diǎn)n+1head(b)加入后pEnd->next=pNew;pEnd=pNew;pEndpNew鏈表創(chuàng)建結(jié)束next0nextnext…datadata頭結(jié)點(diǎn)結(jié)點(diǎn)n…新結(jié)點(diǎn)pNewpEndhead(a)結(jié)束前pNew=newnode;(b)結(jié)束后pEnd->next=0；deletepNew;next0…datadata頭結(jié)點(diǎn)結(jié)點(diǎn)n…pEndhead.鏈表某個(gè)結(jié)點(diǎn)的訪問(wèn)node*access(node*head,intn)

{ if(head==0)

{cout<<"Listisempty!"<<endl;

return0;}

node*temp;

temp=head;

for(inti=1;i<n;i++)

{if(temp->next==0)

{cout<<“要訪問(wèn)的結(jié)點(diǎn)數(shù)大于鏈表的結(jié)點(diǎn)數(shù).”<<‘\n’;

return0;}

temp=temp->next;

}

returntemp;

}.統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個(gè)數(shù)intnode_count(node*head){node*temp=head;intcount=0;while(temp!=0){count++;temp=temp->next;}returncount;}.訪問(wèn)鏈表尾結(jié)點(diǎn)node*accessTail(node*head){ if(head==0) return0; node*temp=head;while(temp->next!=0)temp=temp->next;returntemp;}

第二種情況：在第一個(gè)結(jié)點(diǎn)前插入

newnode->next=head;head=newnode;（插入前）（插入后）

headnewnodenewnodehead

第三種情況：在鏈表中間插入

newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent

第四種情況：在鏈表末尾插入

tail->next=newnode；

newnode->next=0;

(插入前)(插入后)newnodenewnodetailtailp第二種情況:刪除表中或表尾元素p->next=q->next;deleteq;ai-1ai-1aiaiai+1ai+1q刪除前刪除后.創(chuàng)建有序鏈表所謂有序鏈表，是指鏈表中的結(jié)點(diǎn)按結(jié)點(diǎn)的某個(gè)成員的大小進(jìn)行排列。

將一個(gè)結(jié)點(diǎn)插入到有序鏈表中時(shí)，為了保持有序性，要判斷插入的位置。函數(shù)insert_sort_node(node*&,node*&)。通過(guò)