C++程序設計基礎教程-第5章-結構體與簡單鏈表課件

結構體與簡單鏈表

《C++程序設計基礎教程》第5

章

要拼自己，不要拼爹；要追夢，不要追星；要做“學霸”，不要做“學渣”。結構體與簡單鏈表《C++程序設計基礎教程》第5章動態(tài)空間本章內(nèi)容結構體12第5章結構體與簡單鏈表

2022/12/24簡單鏈表3共用體4動態(tài)空間本章內(nèi)容結構體12第5章結構體與簡單鏈表2025.1結構體

結構體是一種導出數(shù)據(jù)類型，它由若干個數(shù)據(jù)項組成，每個數(shù)據(jù)項可以是基本數(shù)據(jù)類型，也可以是導出數(shù)據(jù)類型。2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

3340301YangKe85.5

學號姓名C++成績圖5-1學生基本信息5.1結構體

結構體是一種導出數(shù)據(jù)類型，它由若干個

2022/12/24第1章

初識C++程序設計語言5.1結構體5.1.1

結構體類型的定義定義一個結構體類型的一般形式為：

struct結構體名

{成員表列}；

圖5-1學生基本信息可以定義成如下結構體類型。

structStudent{ intnum；

charname[20]；

floatCPPscore；

}；第5章結構體與簡單鏈表

2022/12/16第1章初識C++程序設計語言5.1

2022/12/24第1章

初識C++程序設計語言5.1.2結構體類型的變量一.結構體類型變量的說明定義結構體類型的變量，有以下3種方法：

1.先聲明結構體類型再定義變量名 例如：Studentstudent1,student2;第5章結構體與簡單鏈表

5.1結構體2022/12/16第1章初識C++程序設計語言5.12022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/245.1.2結構體類型的變量2.在聲明類型的同時定義變量

例如：structDay { inthour; intminute; intsecond; }d1,d2;5.1結構體2022/12/16第1章初識C++程序設計語言第5章

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

2022/12/245.1.2結構體類型的變量3.直接定義結構體類型變量

例如：

struct { intnum; floatsex; }s1,s2;

5.1結構體在定義了結構體類型的變量后，系統(tǒng)會為它分配內(nèi)存單元。其所占存儲空間的大小為各個成員所占內(nèi)存單元之和。2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量二、結構體類型變量的初始化結構體變量是一個整體，要訪問其數(shù)據(jù)成員，要用成員運算符“．”指定該成員屬于哪個變量。對結構體變量進行初始化，有以下三種方法：5.1結構體2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量1.在定義時進行初始化

structStudent { intnum；

charname[20]；

charsex；

floatCPPscore；

}sd1={40301,”YangKe”,’M’,89.5}；5.1結構體2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量2.用對象流cin進行初始化

cin>>sd1.num>>>>sd1.sex;cin>>sd1.CPPscore;3.使用賦值語句進行初始化

sd1.num=40301; =”YangKe”;//錯誤

sd1.sex=‘M’；

sd1.CPPscore=89.5;

5.1結構體第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量結構體變量的引用應遵循的規(guī)則

1.不能將一個結構體變量作為一個整體進行輸入輸出。 例如：cin>>sd1;//錯誤

2.允許將一個結構體變量直接賦值給另一個具有相同類型的結構體變量。 例如：studentsd2;sd2=sd1;5.1結構體2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量若有定義：

struct {intnum; charsex; }s1={40301,’M’}; struct { intnum; charsex; }s2；則s2=s1;//wrong，因為s1,s2屬于兩個不同的結構體類型的變量5.1結構體第1章初識C++程序設計語言第5章結構體與簡單鏈表第2章C++語言編程基礎第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體3.對成員變量可以像普通變量一樣進行各種運算（依成員變量的類型而定）。例如：chara[20];strcpy(a,); sd1.CPPscore++;第2章C++語言編程基礎第1章初識C++程序設計語言第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體注意：結構體成員可以是另一個結構體類型的變量。

structdate {intmonth;intday;intyear;};structstudent {intnum;charname[20];datebirthday; }student1；第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體

如果某成員本身又是一個結構體類型，通過多級的分量運算，對最低一級的成員進行引用。

格式為：結構體變量.成員.子成員.….最低級子成員

student1.birthday.day=12;第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體指向結構體變量的指針一個結構體變量的指針就是給該結構體變量所分配內(nèi)存段的起始地址?？梢远x一個指針變量，用來指向一個結構體變量。此時該指針變量的值就是結構體變量的起始地址。

第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體【例5-1】指向結構體變量的指針變量的使用#include“iostream”#include“string”usingnamespacestd;intmain(){ structStu {intnum; charname[20]; floatscore; };

Stustu_1;Stu*p;p=&stu_1; stu_1.num=11401;strcpy(stu_1.name,”LiNing”);stu_1.score=79.5;第1章初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24第1章

初識C++程序設計語言

cout<<“NO:”<<stu_1.num<<’\t’<<stu_1.name;cout<<’\t’<<stu_1.score<<endl;

cout<<“NO:”<<(*p).num<<’\t’<<(*p).name<<’\t’;cout<<(*p).score<<endl;

cout<<“NO:”<<p->num<<’\t’<<p->name<<‘\t’;cout<<p->score<<endl;return0;}

第5章結構體與簡單鏈表

5.1結構體5.1.2結構體類型的變量2022/12/16第1章初識C++程序設計語言c第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量5.1結構體注意：以下三種形式等價: ①結構體變量.成員名 ②(*p).成員名 ③p->成員名第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結構體類型的變量注意：結構體的成員不能是自身的結構體變量，但可以是指向自身的結構體類型的指針變量。 例如：

structNode { longintnum; floatscore; Node*next;//next是指向node的指針變量

Nodem;//錯誤

};5.1結構體第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.1new運算符如下數(shù)組的定義就是錯誤的。

intn; cin>>n;

floata[n];通過new運算符動態(tài)申請空間。運算符new的運算結果是動態(tài)申請空間的首地址?？梢远x一個指針變量來保存該地址。動態(tài)創(chuàng)建的變量本身沒有名字，通過指針來間接操作。5.2動態(tài)空間第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.1new運算符用new運算符動態(tài)申請空間的格式有3種：①pointer=newtype;//pointer是指針變量

//type可以是整型、字符型和結構體類型等②pointer=newtype(value);

//type只能是基本數(shù)據(jù)類型

//value為所分配內(nèi)存空間的初始化值③pointer=newtype[表達式]

//動態(tài)申請數(shù)組空間

5.2動態(tài)空間第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.1new運算符例如：char*p1,*p2,*p3;

int*q1,*q2;

p1=newchar;

p2=newchar(‘a(chǎn)’);

p3=newchar[10];

q1=newint;

q2=newint(123);5.2動態(tài)空間第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.1new運算符int*s1;s1=newint[10](1,2,3,4,5,6,7,8);

//錯誤

structnode1 { longintnum; floatCPPscore; }; node1*s2,*s3; s2=newnode1; s3=newnode1={40301,95.5};//錯誤5.2動態(tài)空間第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.2delete運算符

系統(tǒng)不會自動釋放動態(tài)分配的內(nèi)存空間，因此在使用完后應釋放掉。如：

char*p1,*p2,*p3;

deletep1;//p1=newchar;

delete[]p2;

//p2=newchar[10];

delete[5*10]p3;//p3=newchar[5*10];

deletes2;//s2=newnode1;5.2動態(tài)空間第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/24練習：（09秋）基本概念題:

程序中使用new運算符動態(tài)分配的內(nèi)存空間，必須用

來釋放。5.2動態(tài)空間5.2.2delete運算符第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/241.數(shù)組---順序存儲結構（在內(nèi)存中按先后順序連續(xù)存放）例如：inta[6]={2,4,6,8,10};5.3簡單鏈表5.3.1鏈表的概念27……2468100……ppppppa[0]a[1]a[2]a[3]a[4]a[5]用指針輸出數(shù)組元素：

for(inti=0,*p=a;i<5;i++)cout<<*p++;數(shù)組中刪除一個元素、插入一個元素??圖5-2順序存儲結構第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2.鏈表---鏈式存儲結構（結點可以在內(nèi)存中間隔存放）5.3簡單鏈表5.3.1鏈表的概念28………………node4node1

node3

node2前一個結點中保存下一個結點的地址。鏈表不能通過指針自增對其遍歷。鏈表中刪除一個結點、插入一個結點??圖5-3鏈式存儲結構第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

鏈表的定義

鏈表是指將若干個數(shù)據(jù)項（結點），按一定的原則（前一個結點“指向”下一個結點）連接起來的有序序列。

4.結點的概念

每個結點都是同類型的結構體變量。通常用指向結點的指針變量來處理鏈表。5.3簡單鏈表5.3.1鏈表的概念第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念30structnode{longintnum;floatscore;node*next;};node*p1=newnode;nodenode2;node*p2=newnode;p1->num=40301;p1->score=85.5;p1->next=&node2;p1->next=p2;第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念315.鏈表的表示---（如下圖所示）314030185.5&4030278.5&403048304030380.5&headnumscorenext圖5-4鏈表的表示2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念32建立鏈表所考慮的問題??①第一個結點怎樣找?②如何從前一個結點找到下一個結點③最后一個結點的指針項應放怎樣的地址？2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念1.鏈表的頭指針

鏈表的操作總是從第一個結點（首結點）逐個結點往后進行的。通常用指針變量（head）存放首結點地址（首地址）。node*p=newnode;node*head=0;p->num=40301;p->score=85.5;

2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念34

2.鏈表的前驅(qū)結點和后繼結點

當前結點的前一個結點稱為前驅(qū)結點，后一個結點稱為后繼結點。如圖5-5所示。正在操作的結點稱為當前結點。head=p;2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念354030185.5&4030278.5&403048304030380.5&numscorenextp1pp2p1pp2head圖5-5鏈表的前驅(qū)結點和后繼結點第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念

p指向的結點為當前結點，

p1指向p的前驅(qū)結點，

p2指向p的后繼結點。

p1->next=p；

p->next=p2；

p1->next->next=p2；2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.1鏈表的概念3.鏈表的尾結點

鏈表的最后一個結點（尾結點）的指針項（next）中保存的值為0（NULL），表示鏈表到此結束。p2->next=0;第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作結點的基本操作（1）定義結構體，表示結點的數(shù)據(jù)類型

structNode{ longintnum; floatscore;Node*next;};2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作（2）用new申請動態(tài)空間，并定義指針變量指向該空間

Node*p=newNode;（3）通過指針變量給結點賦值

intid; cin>>id; p->num=id; cin>>p->score;cout<<p->num<<‘\t’<<p->score;2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

5.3簡單鏈表5.3.2鏈表的基本操作（4）釋放結點空間

deletep;2.操作鏈表的基本語句（1）遍歷鏈表

for(node*p=head;p->next!=0;p=p->next);//p指向尾結點第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作41

（2）查找具有指定值的結點（例如學號為num）③遍歷時，保持p1指向p2的前驅(qū)結點:

p1=p2;p2=p2->next；循環(huán)條件①②可合并：

while(p2->num!=num&&p2->next!=NULL)①以指針p2遍歷鏈表，至鏈尾（循環(huán)條件p2->next!=0）；②遍歷過程中，若找到結點（p2->num==num），查找結束（循環(huán)終止）；2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作（3）刪除具有指定值的結點（例如學號為num）①鏈表是空表（無結點可刪）head==NULL②要刪除的是第一個結點（p2指向要刪的結點）p2=head;head=head->next;deletep2;

③要刪除的是中間結點p1->next=p2->next;deletep2;p1->next=p2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作43numscorenext4030185.5&4030278.5&403048304030380.5&headp1p2p第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作④要刪除的是鏈表的尾結點p1->next=0; deletep2;⑤鏈表中找不到要刪除的結點2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作45（4）在有序鏈表中插入一個結點（p指向插入的結點）

①鏈表是空表，則插入的結點做首結點(head==0）

p->next=0；head=p；

②鏈表不是空表，要插入的結點做首結點

p->next=head；head=p；2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作4030185.5p14030278.5p2403048304030380.5&p1numscorenextheadp2

③在兩結點之間，正常插入結點（在p1、p2之間插入p）4030595.5pp1->next=p;

p->next=p2;或p->next=p1->next;

p1->next=p;

2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.2鏈表的基本操作47

④要插入的結點做鏈表的尾結點p2->next=p; p->next=0；2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用48鏈表的應用包括鏈表的建立與輸出、鏈表結點空間的釋放、在鏈表中刪除具有指定值的結點以及插入一個結點等。

1.建立一條無序鏈表鏈表創(chuàng)建的基本思路是：2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

（1）定義并輸入學號；numscorenext4030185.5head4030278.5ppendppp4030380.540304830

&&（2）分配動態(tài)結點空間p，并對學號賦值、輸入成績；（3）若p是首結點，指針head和pend都指向該結點；否則，把p鏈接到pend的后面，并把p作為當前尾結點；pendpppendppendp->next=0;//pend->next=0;第1章初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用50intid; cin>>id;p=newNode;p->num=id;cin>>p->score;if(head==0){head=p;pend=p;}

else{}（4）重新輸入學號；cin>>id;

（5）只要學號不為0，就重復（2）~（4）步驟（循環(huán))；while(id!=0){}pend->next=p;pend=p;（6）循環(huán)結束（結點全部產(chǎn)生）后，給尾結點加上結束標記。2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用51

Node*create(){ Node*head=0,*p,*pend;intid;cin>>id;

while(id!=0){

p=newNode;//p指向新建立的結點

p->num=id;

cin>>p->score; if(head==0){head=p;pend=p;}

else{pend->next=p;pend=p;}

//pend指向p的前驅(qū)結點

cin>>id;} p->next=0;鏈表建立的函數(shù)如下：

returnhead;}2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用2.輸出鏈表（1）用頭指針head遍歷鏈表

（2）遍歷過程中輸出head所指向的數(shù)據(jù)項（3）定義輸出函數(shù)head=NULLcout<<head->num;cout<<head->score;head=head->next;第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表53numscore

next4030185.5&4030278.5&403048304030380.5&voidprint(Node*head)；headheadheadhead5.3.3鏈表的應用第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用voidprint(Node*head){ while(head!=NULL) { cout<<head->num<<'\t';cout<<head->score; head=head->next; } cout<<'\n';}第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用5555

3.釋放鏈表

建立的鏈表是動態(tài)鏈表，組成鏈表的每個結點的內(nèi)存單元都是通過new運算符動態(tài)申請空間的。因此在對鏈表操作完畢后，動態(tài)申請的空間要釋放掉，以便于對內(nèi)存進行有效的管理。第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

voidrelease(Node*head){if(head==0){cout<<”鏈表為空!\n”;return;} Node*p;while(head){p=head; head=head->next;deletep; }cout<<"結點空間釋放完畢!";}2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

主函數(shù)的編寫:

#include<iostream>

usingnamespacestd;structNode{ longintnum;floatscore;Node*next;};voidmain(){Node*create();//建立單向鏈表voidprint(Node*head);

//輸出鏈表上各個結點的值

voidrelease(Node*head);

//釋放鏈表的結點空間Node*head;head=create();print(head);release(head);return0;}

2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

4.對鏈表的刪除操作刪除鏈表中具有指定值的一個結點時有以下幾種情況：

①鏈表是空表（無結點）； ②要刪的是第一個結點；③要刪的是中間的一個結點；④要刪的是最后一個結點 ⑤鏈表中找不到要刪除的結點。

2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用編寫函數(shù)，刪除鏈表上具有指定值的一個結點。Node*Delete_one_Node(Node*head,intdata){ Node*p1,*p2; if(head==NULL)//第①種情況

{ cout<<"無結點可刪!\n"; returnNULL;} if(head->num==data){//第②種情況

p2=head; head=head->next; deletep2; }第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

else{ p2=p1=head; while(p2->num!=data&&p2->next!=NULL)//查找要刪除的結點

{p1=p2; p2=p2->next;} if(p2->num==data) { p1->next=p2->next; deletep2;//第③④種情況

} elsecout<<“沒有找到要刪除的結點!\n”;//第⑤種情況}returnhead;}2022/12/16第1章初識C++程序設計語言第5章第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用6161

5.對鏈表的插入操作將一個具有值的結點插入到一個有序鏈表中有以下幾種情況：

①該鏈表是空表，則插入的結點做為第一個結點；②要插入的結點做鏈表的第一個結點；③在兩結點之間，正常插入結點；④要插入的結點是尾結點。

第1章初識C++程序設計語言第5章結構體與簡單鏈表第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.3簡單鏈表5.3.3鏈表的應用

編寫函數(shù)，將一個結點插入有序鏈表，插入后鏈表依舊按照學生學號升序排列。

Node*Insert(Node*head,Node*p){ Node*p1,*p2; if(head==0)//第①種情況

{ head=p; p->next=0; returnhead; } if(head->num>=p->num)//第②種情況

{ p->next=head; head=p; returnhead;}第1章初識C++程序設計語言第5章結構體與簡單鏈表2022/12/24

5.3簡單鏈表5.3.3鏈表的應用

p2=p1=head; while(p2->next&&p2->num<p->num){ p1=p2;p2=p2->next;}//p1指向p2的前驅(qū)

if(p2->num<p->num)//第④種情況

{ p2->next=p; p->next=0; } else//第③種情況

{ p->next=p2; p1->next=p; } returnhead;}第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/165.3簡單鏈表5.3.3鏈表的

2022/12/24

5.4共用體第1章

初識C++程序設計語言第5章結構體與簡單鏈表

共用體是一種構造數(shù)據(jù)類型，它是使幾種不同類型的變量存放到同一個地址開始的內(nèi)存單元中。

具有這種存儲特性的變量稱為共用體類型的變量。2022/12/165.4共用體第1章初識C++2022/12/24

2022/12/24

5.4.1共用體類型第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4共用體定義一個共用體類型的一般形式為：

union共用體類型名

{成員表列}； 如：

unionSS { intnum；

charname[20]；

floatCPPscore；

}；2022/12/162022/12/165.4.1共用體2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4.2共用體類型變量的定義5.4共用體一.變量定義定義共用體類型的變量，有以下3種方法：

1.先聲明共用體類型再定義變量名

例如：SSs1,s2;2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4.2共用體類型變量的定義5.4共用體2.在聲明類型的同時定義變量 例如：unionDay { inthour; intminute; intsecond; }d1,d2;

2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4.2共用體類型變量的定義5.4共用體3.直接定義共用體類型變量例如：

union { intnum; floatsex; }s1,s2;

注意：共用體類型的變量所占存儲空間的大小由所占空間最大的那個成員決定。2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4.3共用體類型變量的引用5.4共用體

一般格式為：

共用體變量名．成員名

例如：已經(jīng)定義了共用體SS類型的變量s1，則s1.num，，s1.score分別表示s1變量中3個成員?？梢詫ψ兞縮1的各個數(shù)據(jù)成員賦值。2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4.4共用體類型變量的特點5.4共用體

（1）共用體類型變量的存儲空間在每一瞬時只能存放其中一個成員，而不是同時存放幾個成員。即起作用的成員是最后一次存放的成員。（2）共用體類型變量的地址和它的各成員的地址都是同一地址。（3）不能在定義共用體類型變量的同時對它初始化。相同類型的共用體變量可相互賦值。2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.4共用體5.4.4共用體類型變量的特點

（4）不能將共用體類型變量作為函數(shù)的參數(shù)，也不能將函數(shù)返回值類型定義為共用體類型?？梢允褂弥赶蚬灿皿w類型變量的指針。（5）共用體類型可以出現(xiàn)在結構體類型定義中，也可定義共用體數(shù)組，反之，結構體也可以出現(xiàn)在共用體類型定義中。2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例【例5-2】編寫一個程序?qū)⒁粋€鏈表按逆序排列，即將鏈頭當鏈尾，鏈尾當鏈頭。結點的數(shù)據(jù)結構如下：structNode{ intdata; Node*next;};

算法：首先建立一個單向鏈表，頭指針head指向首結點。該鏈表沒有排序。將鏈表的鏈頭當鏈尾，鏈尾當鏈頭，則鏈表的首結點的指針項next域應該賦值為NULL，頭指針head指向尾結點，原鏈表的某個結點的前驅(qū)結點在逆序后成為后繼結點。定義指針變量p指向第2個結點，指針變量q指向第3個結點，head指向首結點，則執(zhí)行p->next=head;后，第2個結點就成為第1個結點的前驅(qū)結點。依次類推，直到處理到尾結點。

2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};Node*create(){Node*head=0;//頭指針Node*p;inta;

cout<<"請輸入數(shù)據(jù)(為零表示結束輸入):"; cin>>a; while(a!=0){p=newNode; p->data=a; p->next=head; head=p;cin>>a;} returnhead;}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例Node*invert(Node*head){Node*p,*q;p=head->next;//指針變量p指向第二個結點，即取下首結點后，需處理的鏈表的開始位置if(p!=NULL){ head->next=NULL;//首結點做為尾結點 do{q=p->next; p->next=head; head=p; p=q; }while(p!=NULL);//尾結點處理完畢，循環(huán)結束} returnhead;}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例voidprint(Node*head){if(head==0){cout<<"鏈表為空!\n";return;}Node*p=head;cout<<“鏈表上各個結點的值為：\n”;while(p!=0){ cout<<p->data<<'\t'; p=p->next;}}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例voidrelease(Node*head){if(head==0){ cout<<"鏈表為空!\n";return;}Node*p;while(head){ p=head; head=head->next; deletep;}cout<<"\n結點空間釋放完畢!\n";}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例intmain(){ Node*head; head=create(); print(head); head=invert(head); cout<<"\n逆序后"; print(head); release(head);}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例【例5-3】設已建立一個單向鏈表，定義一個函數(shù)將該鏈表中相鄰的兩個結點合并成一個結點。即將第一個結點的數(shù)據(jù)項與第二個結點的合并，第三個結點的與第四個結點的合并，依此類推。若鏈表上結點個數(shù)為奇數(shù)，則尾結點不合并，直接作為合并后新鏈表上的最后一個結點。結點的數(shù)據(jù)結構如下：

structnode { intdata; node*next; };voidmerge(node*h);2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例算法：初始時，使指針變量p1指向鏈表的首結點，p2指向它的后繼結點。將p1所指向結點的data值與p2所指向結點的data值相加。保存在p1所指向結點的data成員項中。p1指向第三個結點，p2指向它的后繼結點，即第四個結點。兩結點的data值相加。依此類推，直至p2為空。2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例voidmerge(node*h){ node*p1,*p2; if(h->next==NULL||h==NULL) return; p1=h; p2=h->next; while(p2) { p1->data+=p2->data; p1->next=p2->next; deletep2; p1=p1->next; if(p1!=NULL) p2=p1->next; elsep2=NULL; }}2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例【例5-4】設已建立一個單向鏈表，指針head指向該鏈表的首結點。定義一個函數(shù)將head所指向鏈表上各結點的數(shù)據(jù)按data值升序排序。請完善sort函數(shù)。結點的數(shù)據(jù)結構如下：structnode{ intdata; node*next;};2022/12/162022/12/16第1章初識C+2022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例算法：初始時，使指針變量p指向該鏈表的首結點，從p之后的所有結點中找出data值最小的結點，讓p1指向該結點。將p指向結點的data值與p1指向結點的data值進行交換。讓p指向下一個結點，依此類推，直至p指向鏈表的最后一個結點為止。最后，函數(shù)返回已排好序的鏈表的頭指針。2022/12/162022/12/16第1章初識C+2022/12/242022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例node*sort(node*h){ node*p=h,*p1,*p2; if(p==NULL)

(1); while(p->next!=NULL) { p1=p; p2=p->next; while(p2!=NULL) { if(p2->data<p1->data)

(2); p2=p2->next; }8383

if(p!=p1) { intt; t=p->data; p->data=p1->data; p1->data=t; }

(3); } returnh;}（1）returnh;（2）p1=p2;（3）p=p->next;2022/12/162022/12/162022/12/12022/12/242022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例練習:已有兩個鏈表h1和h2，結點數(shù)據(jù)結構如下：structstudent{ charname[20]; //姓名

floatscore; //成績

student*next;};函數(shù)dele()實現(xiàn)從鏈表h1中刪除與鏈表h2中姓名相同的結點（設鏈表皆是沒有重復結點的非空鏈表，且鏈表h2中一定有與鏈表h1中姓名相同的結點）。算法思想是：h2中的每個結點與h1中所有的結點比較，找到姓名相同的結點后，從h1中刪除該結點。請完善函數(shù)。2022/12/162022/12/162022/12/12022/12/242022/12/24

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

5.5程序舉例8585student*dele(student*h1,student*h2){ student*p,*q; while(h2){ p=h1; while(

（1）){//查找結點

if(!p)break; //本輪查找已到h1的尾結點

q=p; p=p->next; } if(p==h1)

（2）; elseif(p)

（3）; deletep;

（4）; } returnh1;}（1）p!=NULL&&(strcmp(h2->name,p->name)!=0)（2）h1=h1->next（3）q->next=p->next（4）h2=h2->next2022/12/162022/12/162022/12/1本章結束第1章

初識C++程序設計語言第5章結構體與簡單鏈表

本章結束第1章初識C++程序設計語言第5章結構體與簡結構體與簡單鏈表

《C++程序設計基礎教程》第5

章

要拼自己，不要拼爹；要追夢，不要追星；要做“學霸”，不要做“學渣”。結構體與簡單鏈表《C++程序設計基礎教程》第5章動態(tài)空間本章內(nèi)容結構體12第5章結構體與簡單鏈表

2022/12/24簡單鏈表3共用體4動態(tài)空間本章內(nèi)容結構體12第5章結構體與簡單鏈表2025.1結構體

結構體是一種導出數(shù)據(jù)類型，它由若干個數(shù)據(jù)項組成，每個數(shù)據(jù)項可以是基本數(shù)據(jù)類型，也可以是導出數(shù)據(jù)類型。2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

898940301YangKe85.5

學號姓名C++成績圖5-1學生基本信息5.1結構體

結構體是一種導出數(shù)據(jù)類型，它由若干個

2022/12/24第1章

初識C++程序設計語言5.1結構體5.1.1

結構體類型的定義定義一個結構體類型的一般形式為：

struct結構體名

{成員表列}；

圖5-1學生基本信息可以定義成如下結構體類型。

structStudent{ intnum；

charname[20]；

floatCPPscore；

}；第5章結構體與簡單鏈表

2022/12/16第1章初識C++程序設計語言5.1

2022/12/24第1章

初識C++程序設計語言5.1.2結構體類型的變量一.結構體類型變量的說明定義結構體類型的變量，有以下3種方法：

1.先聲明結構體類型再定義變量名 例如：Studentstudent1,student2;第5章結構體與簡單鏈表

5.1結構體2022/12/16第1章初識C++程序設計語言5.12022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/245.1.2結構體類型的變量2.在聲明類型的同時定義變量

例如：structDay { inthour; intminute; intsecond; }d1,d2;5.1結構體2022/12/16第1章初識C++程序設計語言第5章

2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/24

2022/12/245.1.2結構體類型的變量3.直接定義結構體類型變量

例如：

struct { intnum; floatsex; }s1,s2;

5.1結構體在定義了結構體類型的變量后，系統(tǒng)會為它分配內(nèi)存單元。其所占存儲空間的大小為各個成員所占內(nèi)存單元之和。2022/12/16第1章初識C++程序設計語言第5章2022/12/24第1章

初識C++程序設計語言第5章結構體與簡單鏈表

2022/12/242