C++簡單鏈表及其應(yīng)用課件

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

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

每個元素(表項)由結(jié)點(Node)構(gòu)成。線性結(jié)構(gòu)

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

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

cat

eat

mat

^

…

用C++語言描述的一個簡單的單鏈表如下：structnode{intdata;//值域node*next;//鏈域};例.建立一個簡單的鏈表，它由3個學(xué)生數(shù)據(jù)的結(jié)點組成，輸出各結(jié)點中的數(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é)點a的起始地址賦給頭指針head*/a.next=&b;/*將結(jié)點b的起始地址賦給a結(jié)點的next成員*/b.next=&c;c.next=NULL;將結(jié)點設(shè)置為表頭的過程如下圖所示：pNewhead(b)

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

head=0;

pEnd=pNew;pEndheadpNew將結(jié)點加到鏈表末尾的過程如下圖所示：nextdatanextnext…datadata頭結(jié)點結(jié)點n…新結(jié)點pNewpEndhead(a)加入前pNew=newnode;nextnext…datadata頭結(jié)點結(jié)點n…nextdata結(jié)點n+1head(b)加入后pEnd->next=pNew;pEnd=pNew;pEndpNew鏈表創(chuàng)建結(jié)束next0nextnext…datadata頭結(jié)點結(jié)點n…新結(jié)點pNewpEndhead(a)結(jié)束前pNew=newnode;(b)結(jié)束后pEnd->next=0；deletepNew;next0…datadata頭結(jié)點結(jié)點n…pEndhead.鏈表某個結(jié)點的訪問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<<“要訪問的結(jié)點數(shù)大于鏈表的結(jié)點數(shù).”<<‘\n’;

return0;}

temp=temp->next;

}

returntemp;

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

第二種情況：在第一個結(jié)點前插入

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é)點按結(jié)點的某個成員的大小進(jìn)行排列。

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