計算機程序設(shè)計基礎(chǔ)課件：鏈表

鏈表本章內(nèi)容第一節(jié)鏈表概述第二節(jié)建立鏈表(擴展)第三節(jié)插入鏈表結(jié)點(擴展)第四節(jié)刪除鏈表結(jié)點(擴展)第一節(jié)鏈表概述鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以在程序中動態(tài)分配內(nèi)存，而且不需要連續(xù)的內(nèi)存空間，內(nèi)存利用率高。由于不需要像數(shù)組一樣移動其他的元素，在鏈表中插入或刪除元素更方便快速。一、鏈表的概念鏈表中的元素稱為結(jié)點，每個結(jié)點包含兩部分內(nèi)容：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放結(jié)點要存儲的數(shù)據(jù)，指針域存放指向下一個結(jié)點的指針，通過這些指針就可以將各個結(jié)點連接成為一個鏈表。鏈表有一個頭指針變量，它的值是鏈表第一個結(jié)點的地址，用來指向鏈表的第一個結(jié)點。鏈表的最后一個結(jié)點稱為尾結(jié)點，指針域中的值為nullptr。鏈表的結(jié)點可以定義為以下的結(jié)構(gòu)體類型：structnode{

數(shù)據(jù)類型1成員名1;//數(shù)據(jù)域

數(shù)據(jù)類型2成員名2;……node*next;//指針域};node是結(jié)構(gòu)體類型名稱，用來表示結(jié)點，成員next是結(jié)構(gòu)體指針變量，指向node類型的結(jié)構(gòu)體變量，也就是指向下一個結(jié)點。二、鏈表常用運算符1、new運算符new運算符的格式為：

new數(shù)據(jù)類型根據(jù)new后面數(shù)據(jù)類型的字節(jié)數(shù)來申請分配內(nèi)存空間，然后返回該類型的指針。

int*p=newint;申請分配存放整型數(shù)據(jù)的內(nèi)存空間，分配成功后返回該內(nèi)存空間的地址，即指針，并將指針賦值給變量p。2、delete運算符delete運算符的格式為：

delete指針變量釋放使用new運算符分配的內(nèi)存空間。

deletep;釋放指針變量p所指向的內(nèi)存空間，p的值是前面使用new運算符分配的內(nèi)存空間地址。delete運算符一般與new運算符配對使用。一、建立鏈表第二節(jié)建立鏈表建立鏈表就是依次增加鏈表結(jié)點的過程，逐個為結(jié)點申請內(nèi)存，存放結(jié)點數(shù)據(jù)，然后建立結(jié)點之間的鏈接關(guān)系。程序段12-1

structnode { intnum; charname[20]; node*next; }; node*head,*tail,*p; inti;

head=nullptr;//鏈表頭指針變量head tail=nullptr;//鏈表尾指針變量tail for(i=0;i<3;i++) {

p=newnode;//建立新結(jié)點，p指向新結(jié)點

cout<<"輸入學(xué)生信息："<<endl; cout<<"學(xué)號：";cin>>p->num; cin.get(); cout<<"姓名：";cin.get(p->name,20); p->next=nullptr; if(head==nullptr)//若鏈表為空，將頭指針指向新結(jié)點

head=p; else//若鏈表不為空，將新結(jié)點鏈接到鏈表尾部

tail->next=p; tail=p;//將尾指針指向新結(jié)點

}程序段12-1

p=head; cout<<"三個學(xué)生信息："<<endl; while(p!=nullptr)//輸出鏈表的數(shù)據(jù)

{

cout<<p->num<<','<<p->name<<endl; p=p->next; }然后判斷鏈表是否為空，即新結(jié)點是否為第一個結(jié)點，如果是第一個結(jié)點，執(zhí)行head=p;和tail=p;語句，將head和tail都指向新結(jié)點。接著將輸入的數(shù)據(jù)存放到新結(jié)點的相應(yīng)成員中，再用p->next=nullptr;語句把新結(jié)點的next成員賦值為nullptr。建立第一個結(jié)點時，首先用new為結(jié)點申請內(nèi)存空間，將分配到的內(nèi)存空間地址賦值給結(jié)構(gòu)體指針變量p，使p指向新結(jié)點。接著輸入數(shù)據(jù)到新結(jié)點的相應(yīng)成員中,把新結(jié)點的next成員賦值為nullptr。建立第二個結(jié)點時，同樣先為結(jié)點申請內(nèi)存空間，將p指向新結(jié)點。然后判斷鏈表是否為空，此時鏈表已經(jīng)有結(jié)點不為空，所以執(zhí)行tail->next=p;和tail=p;語句，tail的next成員即為第一個結(jié)點的next成員，tail->next=p;使第一個結(jié)點的next成員指向新結(jié)點，tail=p;使tail也指向新結(jié)點。建立第三個結(jié)點的步驟與建立第二個結(jié)點的步驟相同，依然是p指向新結(jié)點，前一個結(jié)點的next成員指向新結(jié)點，tail也指向新結(jié)點。至此，包含三個結(jié)點的鏈表建立過程結(jié)束。二、遍歷鏈表

p=head; while(p!=nullptr) { cout<<p->num<<','<<p->name<<endl; p=p->next; }鏈表的結(jié)點在內(nèi)存中一般是不連續(xù)的，因此不能像數(shù)組一樣進行隨機訪問，只能從第一個結(jié)點開始依次訪問各結(jié)點。在鏈表中插入新的結(jié)點時，首先要確定結(jié)點插入到鏈表的位置，然后根據(jù)不同的位置進行相應(yīng)的操作。插入結(jié)點的位置一般有以下幾種情況：第三節(jié)插入結(jié)點（1）新結(jié)點插入到鏈表第一個結(jié)點前面，成為鏈表的第一個結(jié)點。（2）新結(jié)點插入到鏈表中間某個結(jié)點后面。（3）新結(jié)點插入到鏈表末尾，成為鏈表的尾結(jié)點。程序段12-2structnode{ intnum; floatscore; node*next;};node*createlist()//建立鏈表的函數(shù){ node*head,*tail,*p; inti; head=nullptr; tail=nullptr; cout<<"輸入三個學(xué)生的信息："<<endl; for(i=0;i<3;i++) { p=newnode; cout<<"學(xué)號：";cin>>p->num; cout<<"成績：";cin>>p->score; p->next=nullptr; if(head==nullptr) head=p; else tail->next=p; tail=p; } returnhead;}程序段12-2node*insert(node*head,intinum,floatiscore)//插入結(jié)點的函數(shù){ node*p,*pre,*inode; inode=newnode; inode->num=inum; inode->score=iscore; p=head; pre=head; while(p!=nullptr&&p->score<iscore)//查找插入位置

{ pre=p; p=p->next; } if(head==p)//插入到第一個結(jié)點前面

{ inode->next=head; head=inode; } elseif(p!=nullptr&&p->score>iscore)//插入到鏈表中間

{ pre->next=inode; inode->next=p; }

程序段12-2 elseif(p==nullptr)//插入到鏈表末尾

{ pre->next=inode; inode->next=nullptr; } returnhead;}intmain(){ node*head,*ph; intinum; floatiscore; head=createlist(); cout<<"輸入要添加學(xué)生的學(xué)號和成績："; cin>>inum>>iscore; ph=insert(head,inum,iscore); cout<<"所有學(xué)生的學(xué)號和成績："<<endl; while(ph!=nullptr)//遍歷鏈表，輸出所有數(shù)據(jù)

{ cout<<ph->num<<','<<ph->score<<endl; ph=ph->next; } return0;}1、在鏈表頭插入新結(jié)點if(head==p) { inode->next=head; head=inode; }如果要插入的新結(jié)點的成績值比鏈表第一個結(jié)點的成績小，那么上面的while語句就不會執(zhí)行，p還是指向第一個結(jié)點，即p與head相等，要執(zhí)行的是下面的語句：新結(jié)點要插入到鏈表第一個結(jié)點之前，因此將head的值賦給指向新結(jié)點的inode的next成員，使新結(jié)點的next指向鏈表第一個結(jié)點，然后將inode的值賦給head，使head指向新結(jié)點。2、在鏈表中間插入新結(jié)點elseif(p!=nullptr&&p->score>iscore) { pre->next=inode; inode->next=p; }如果要插入的新結(jié)點在鏈表中間的某個位置，要執(zhí)行的是下面的語句：p指向的是要插入新結(jié)點的下一個結(jié)點，pre指向的是要插入結(jié)點的前一個結(jié)點。然后執(zhí)行pre->next=inode;語句，使pre所指向結(jié)點的next指向新結(jié)點，再執(zhí)行inode->next=p;語句，使新結(jié)點的next指向p所指的結(jié)點。3、在鏈表尾插入新結(jié)點elseif(p==nullptr) { pre->next=inode; inode->next=nullptr; }如果p指向的是nullptr，則要插入的新結(jié)點在鏈表末尾，執(zhí)行的是下面的語句：pre指向的是鏈表的最后一個結(jié)點。然后執(zhí)行pre->next=inode;語句，使pre所指向結(jié)點（即最后一個結(jié)點）的next指向新結(jié)點，再執(zhí)行inode->next=nullptr;語句，使新結(jié)點的next值為nullptr。刪除鏈表中的結(jié)點時，首先要確定刪除結(jié)點的位置，然后根據(jù)不同的位置進行相應(yīng)的操作。要刪除結(jié)點的位置一般有以下幾種情況：第四節(jié)刪除結(jié)點（1）刪除鏈表第一個結(jié)點。（2）刪除鏈表中間某個結(jié)點。（3）刪除鏈表的尾結(jié)點。程序段12-3structnode{ intnum; floatscore; node*next;};node*createlist(){ node*head,*tail,*p; inti; head=nullptr; tail=nullptr; cout<<"輸入四個學(xué)生的信息："<<endl; for(i=0;i<4;i++) { p=newnode; cout<<"學(xué)號：";cin>>p->num; cout<<"成績：";cin>>p->score; p->next=nullptr; if(head==nullptr) head=p; else tail->next=p; tail=p; } returnhead;}程序段12-3node*deletenode(node*head,intinum)//刪除鏈表結(jié)點的函數(shù){ node*p,*pre; p=head; pre=head; while(p!=nullptr&&p->num!=inum) { pre=p; p=p->next; } if(head==p)//刪除鏈表的第一個結(jié)點

head=p->next; elseif(p!=nullptr&&p->num==inum)//刪除鏈表中間的結(jié)點

pre->next=p->next; elseif(p==nullptr)//刪除鏈表的最后一個結(jié)點

pre->next=nullptr; deletep; returnhead;}程序段12-3intmain(){node*head,*ph; intinum; floatiscore; head=createlist(); cout<<"輸入要刪除學(xué)生的學(xué)號："; cin>>inum; ph=deletenode(head,inum); cout<<"所有學(xué)生的學(xué)號和成績："<<endl; while(ph!=nullptr) { cout<<ph->num<<','<<ph->score<<