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

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

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

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

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

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

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

deletep;釋放指針變量p所指向的內(nèi)存空間，p的值是前面使用new運(yùn)算符分配的內(nèi)存空間地址。delete運(yùn)算符一般與new運(yùn)算符配對(duì)使用。一、建立鏈表第二節(jié)建立鏈表建立鏈表就是依次增加鏈表結(jié)點(diǎn)的過(guò)程，逐個(gè)為結(jié)點(diǎn)申請(qǐng)內(nèi)存，存放結(jié)點(diǎn)數(shù)據(jù)，然后建立結(jié)點(diǎn)之間的鏈接關(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é)點(diǎn)，p指向新結(jié)點(diǎn)

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

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

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

}程序段12-1

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

{

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

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

{ 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é)號(hào)和成績(jī)："; cin>>inum>>iscore; ph=insert(head,inum,iscore); cout<<"所有學(xué)生的學(xué)號(hào)和成績(jī)："<<endl; while(ph!=nullptr)//遍歷鏈表，輸出所有數(shù)據(jù)

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

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

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

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