C++程序設(shè)計(jì)基礎(chǔ)教程-第5章-結(jié)構(gòu)體與簡(jiǎn)單鏈表課件

結(jié)構(gòu)體與簡(jiǎn)單鏈表

《C++程序設(shè)計(jì)基礎(chǔ)教程》第5

章

要拼自己，不要拼爹；要追夢(mèng)，不要追星；要做“學(xué)霸”，不要做“學(xué)渣”。結(jié)構(gòu)體與簡(jiǎn)單鏈表《C++程序設(shè)計(jì)基礎(chǔ)教程》第5章動(dòng)態(tài)空間本章內(nèi)容結(jié)構(gòu)體12第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

結(jié)構(gòu)體是一種導(dǎo)出數(shù)據(jù)類型，它由若干個(gè)數(shù)據(jù)項(xiàng)組成，每個(gè)數(shù)據(jù)項(xiàng)可以是基本數(shù)據(jù)類型，也可以是導(dǎo)出數(shù)據(jù)類型。2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

3340301YangKe85.5

學(xué)號(hào)姓名C++成績(jī)圖5-1學(xué)生基本信息5.1結(jié)構(gòu)體

結(jié)構(gòu)體是一種導(dǎo)出數(shù)據(jù)類型，它由若干個(gè)

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1結(jié)構(gòu)體5.1.1

結(jié)構(gòu)體類型的定義定義一個(gè)結(jié)構(gòu)體類型的一般形式為：

struct結(jié)構(gòu)體名

{成員表列}；

圖5-1學(xué)生基本信息可以定義成如下結(jié)構(gòu)體類型。

structStudent{ intnum；

charname[20]；

floatCPPscore；

}；第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1.2結(jié)構(gòu)體類型的變量一.結(jié)構(gòu)體類型變量的說(shuō)明定義結(jié)構(gòu)體類型的變量，有以下3種方法：

1.先聲明結(jié)構(gòu)體類型再定義變量名 例如：Studentstudent1,student2;第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.12022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/245.1.2結(jié)構(gòu)體類型的變量2.在聲明類型的同時(shí)定義變量

例如：structDay { inthour; intminute; intsecond; }d1,d2;5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量3.直接定義結(jié)構(gòu)體類型變量

例如：

struct { intnum; floatsex; }s1,s2;

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量1.在定義時(shí)進(jìn)行初始化

structStudent { intnum；

charname[20]；

charsex；

floatCPPscore；

}sd1={40301,”YangKe”,’M’,89.5}；5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量2.用對(duì)象流cin進(jìn)行初始化

cin>>sd1.num>>>>sd1.sex;cin>>sd1.CPPscore;3.使用賦值語(yǔ)句進(jìn)行初始化

sd1.num=40301; =”YangKe”;//錯(cuò)誤

sd1.sex=‘M’；

sd1.CPPscore=89.5;

5.1結(jié)構(gòu)體第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量結(jié)構(gòu)體變量的引用應(yīng)遵循的規(guī)則

1.不能將一個(gè)結(jié)構(gòu)體變量作為一個(gè)整體進(jìn)行輸入輸出。 例如：cin>>sd1;//錯(cuò)誤

2.允許將一個(gè)結(jié)構(gòu)體變量直接賦值給另一個(gè)具有相同類型的結(jié)構(gòu)體變量。 例如：studentsd2;sd2=sd1;5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量若有定義：

struct {intnum; charsex; }s1={40301,’M’}; struct { intnum; charsex; }s2；則s2=s1;//wrong，因?yàn)閟1,s2屬于兩個(gè)不同的結(jié)構(gòu)體類型的變量5.1結(jié)構(gòu)體第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第2章C++語(yǔ)言編程基礎(chǔ)第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量5.1結(jié)構(gòu)體注意：結(jié)構(gòu)體成員可以是另一個(gè)結(jié)構(gòu)體類型的變量。

structdate {intmonth;intday;intyear;};structstudent {intnum;charname[20];datebirthday; }student1；第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量5.1結(jié)構(gòu)體

如果某成員本身又是一個(gè)結(jié)構(gòu)體類型，通過(guò)多級(jí)的分量運(yùn)算，對(duì)最低一級(jí)的成員進(jìn)行引用。

格式為：結(jié)構(gòu)體變量.成員.子成員.….最低級(jí)子成員

student1.birthday.day=12;第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量5.1結(jié)構(gòu)體【例5-1】指向結(jié)構(gòu)體變量的指針變量的使用#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章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言

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章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.1結(jié)構(gòu)體5.1.2結(jié)構(gòu)體類型的變量2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言c第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量5.1結(jié)構(gòu)體注意：以下三種形式等價(jià): ①結(jié)構(gòu)體變量.成員名 ②(*p).成員名 ③p->成員名第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

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

Nodem;//錯(cuò)誤

};5.1結(jié)構(gòu)體第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

intn; cin>>n;

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

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

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

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

//動(dòng)態(tài)申請(qǐng)數(shù)組空間

5.2動(dòng)態(tài)空間第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.1new運(yùn)算符例如：char*p1,*p2,*p3;

int*q1,*q2;

p1=newchar;

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

p3=newchar[10];

q1=newint;

q2=newint(123);5.2動(dòng)態(tài)空間第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

//錯(cuò)誤

structnode1 { longintnum; floatCPPscore; }; node1*s2,*s3; s2=newnode1; s3=newnode1={40301,95.5};//錯(cuò)誤5.2動(dòng)態(tài)空間第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/245.2.2delete運(yùn)算符

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

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動(dòng)態(tài)空間第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

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

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

來(lái)釋放。5.2動(dòng)態(tài)空間5.2.2delete運(yùn)算符第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242022/12/24

2022/12/242022/12/24

2022/12/241.數(shù)組---順序存儲(chǔ)結(jié)構(gòu)（在內(nèi)存中按先后順序連續(xù)存放）例如：inta[6]={2,4,6,8,10};5.3簡(jiǎn)單鏈表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ù)組中刪除一個(gè)元素、插入一個(gè)元素??圖5-2順序存儲(chǔ)結(jié)構(gòu)第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2.鏈表---鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（結(jié)點(diǎn)可以在內(nèi)存中間隔存放）5.3簡(jiǎn)單鏈表5.3.1鏈表的概念28………………node4node1

node3

node2前一個(gè)結(jié)點(diǎn)中保存下一個(gè)結(jié)點(diǎn)的地址。鏈表不能通過(guò)指針自增對(duì)其遍歷。鏈表中刪除一個(gè)結(jié)點(diǎn)、插入一個(gè)結(jié)點(diǎn)??圖5-3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

鏈表的定義

鏈表是指將若干個(gè)數(shù)據(jù)項(xiàng)（結(jié)點(diǎn)），按一定的原則（前一個(gè)結(jié)點(diǎn)“指向”下一個(gè)結(jié)點(diǎn)）連接起來(lái)的有序序列。

4.結(jié)點(diǎn)的概念

每個(gè)結(jié)點(diǎn)都是同類型的結(jié)構(gòu)體變量。通常用指向結(jié)點(diǎn)的指針變量來(lái)處理鏈表。5.3簡(jiǎn)單鏈表5.3.1鏈表的概念第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表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章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念315.鏈表的表示---（如下圖所示）314030185.5&4030278.5&403048304030380.5&headnumscorenext圖5-4鏈表的表示2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念32建立鏈表所考慮的問(wèn)題??①第一個(gè)結(jié)點(diǎn)怎樣找?②如何從前一個(gè)結(jié)點(diǎn)找到下一個(gè)結(jié)點(diǎn)③最后一個(gè)結(jié)點(diǎn)的指針項(xiàng)應(yīng)放怎樣的地址？2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念1.鏈表的頭指針

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

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念34

2.鏈表的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)

當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)稱為前驅(qū)結(jié)點(diǎn)，后一個(gè)結(jié)點(diǎn)稱為后繼結(jié)點(diǎn)。如圖5-5所示。正在操作的結(jié)點(diǎn)稱為當(dāng)前結(jié)點(diǎn)。head=p;2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念354030185.5&4030278.5&403048304030380.5&numscorenextp1pp2p1pp2head圖5-5鏈表的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念

p指向的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，

p1指向p的前驅(qū)結(jié)點(diǎn)，

p2指向p的后繼結(jié)點(diǎn)。

p1->next=p；

p->next=p2；

p1->next->next=p2；2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.1鏈表的概念3.鏈表的尾結(jié)點(diǎn)

鏈表的最后一個(gè)結(jié)點(diǎn)（尾結(jié)點(diǎn)）的指針項(xiàng)（next）中保存的值為0（NULL），表示鏈表到此結(jié)束。p2->next=0;第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作結(jié)點(diǎn)的基本操作（1）定義結(jié)構(gòu)體，表示結(jié)點(diǎn)的數(shù)據(jù)類型

structNode{ longintnum; floatscore;Node*next;};2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

Node*p=newNode;（3）通過(guò)指針變量給結(jié)點(diǎn)賦值

intid; cin>>id; p->num=id; cin>>p->score;cout<<p->num<<‘\t’<<p->score;2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作（4）釋放結(jié)點(diǎn)空間

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

for(node*p=head;p->next!=0;p=p->next);//p指向尾結(jié)點(diǎn)第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作41

（2）查找具有指定值的結(jié)點(diǎn)（例如學(xué)號(hào)為num）③遍歷時(shí)，保持p1指向p2的前驅(qū)結(jié)點(diǎn):

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

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作（3）刪除具有指定值的結(jié)點(diǎn)（例如學(xué)號(hào)為num）①鏈表是空表（無(wú)結(jié)點(diǎn)可刪）head==NULL②要?jiǎng)h除的是第一個(gè)結(jié)點(diǎn)（p2指向要?jiǎng)h的結(jié)點(diǎn)）p2=head;head=head->next;deletep2;

③要?jiǎng)h除的是中間結(jié)點(diǎn)p1->next=p2->next;deletep2;p1->next=p2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作43numscorenext4030185.5&4030278.5&403048304030380.5&headp1p2p第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作④要?jiǎng)h除的是鏈表的尾結(jié)點(diǎn)p1->next=0; deletep2;⑤鏈表中找不到要?jiǎng)h除的結(jié)點(diǎn)2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作45（4）在有序鏈表中插入一個(gè)結(jié)點(diǎn)（p指向插入的結(jié)點(diǎn)）

①鏈表是空表，則插入的結(jié)點(diǎn)做首結(jié)點(diǎn)(head==0）

p->next=0；head=p；

②鏈表不是空表，要插入的結(jié)點(diǎn)做首結(jié)點(diǎn)

p->next=head；head=p；2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作4030185.5p14030278.5p2403048304030380.5&p1numscorenextheadp2

③在兩結(jié)點(diǎn)之間，正常插入結(jié)點(diǎn)（在p1、p2之間插入p）4030595.5pp1->next=p;

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

p1->next=p;

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.2鏈表的基本操作47

④要插入的結(jié)點(diǎn)做鏈表的尾結(jié)點(diǎn)p2->next=p; p->next=0；2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用48鏈表的應(yīng)用包括鏈表的建立與輸出、鏈表結(jié)點(diǎn)空間的釋放、在鏈表中刪除具有指定值的結(jié)點(diǎn)以及插入一個(gè)結(jié)點(diǎn)等。

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

（1）定義并輸入學(xué)號(hào)；numscorenext4030185.5head4030278.5ppendppp4030380.540304830

&&（2）分配動(dòng)態(tài)結(jié)點(diǎn)空間p，并對(duì)學(xué)號(hào)賦值、輸入成績(jī)；（3）若p是首結(jié)點(diǎn)，指針head和pend都指向該結(jié)點(diǎn)；否則，把p鏈接到pend的后面，并把p作為當(dāng)前尾結(jié)點(diǎn)；pendpppendppendp->next=0;//pend->next=0;第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

else{}（4）重新輸入學(xué)號(hào)；cin>>id;

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用51

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

while(id!=0){

p=newNode;//p指向新建立的結(jié)點(diǎn)

p->num=id;

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

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

//pend指向p的前驅(qū)結(jié)點(diǎn)

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

returnhead;}2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用2.輸出鏈表（1）用頭指針head遍歷鏈表

（2）遍歷過(guò)程中輸出head所指向的數(shù)據(jù)項(xiàng)（3）定義輸出函數(shù)head=NULLcout<<head->num;cout<<head->score;head=head->next;第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表53numscore

next4030185.5&4030278.5&403048304030380.5&voidprint(Node*head)；headheadheadhead5.3.3鏈表的應(yīng)用第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用voidprint(Node*head){ while(head!=NULL) { cout<<head->num<<'\t';cout<<head->score; head=head->next; } cout<<'\n';}第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用5555

3.釋放鏈表

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

主函數(shù)的編寫:

#include<iostream>

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

//輸出鏈表上各個(gè)結(jié)點(diǎn)的值

voidrelease(Node*head);

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

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

4.對(duì)鏈表的刪除操作刪除鏈表中具有指定值的一個(gè)結(jié)點(diǎn)時(shí)有以下幾種情況：

①鏈表是空表（無(wú)結(jié)點(diǎn)）； ②要?jiǎng)h的是第一個(gè)結(jié)點(diǎn)；③要?jiǎng)h的是中間的一個(gè)結(jié)點(diǎn)；④要?jiǎng)h的是最后一個(gè)結(jié)點(diǎn) ⑤鏈表中找不到要?jiǎng)h除的結(jié)點(diǎn)。

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

p2=head; head=head->next; deletep2; }第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

else{ p2=p1=head; while(p2->num!=data&&p2->next!=NULL)//查找要?jiǎng)h除的結(jié)點(diǎn)

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

} elsecout<<“沒有找到要?jiǎng)h除的結(jié)點(diǎn)!\n”;//第⑤種情況}returnhead;}2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用6161

5.對(duì)鏈表的插入操作將一個(gè)具有值的結(jié)點(diǎn)插入到一個(gè)有序鏈表中有以下幾種情況：

①該鏈表是空表，則插入的結(jié)點(diǎn)做為第一個(gè)結(jié)點(diǎn)；②要插入的結(jié)點(diǎn)做鏈表的第一個(gè)結(jié)點(diǎn)；③在兩結(jié)點(diǎn)之間，正常插入結(jié)點(diǎn)；④要插入的結(jié)點(diǎn)是尾結(jié)點(diǎn)。

第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

編寫函數(shù)，將一個(gè)結(jié)點(diǎn)插入有序鏈表，插入后鏈表依舊按照學(xué)生學(xué)號(hào)升序排列。

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章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表2022/12/24

5.3簡(jiǎn)單鏈表5.3.3鏈表的應(yīng)用

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章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/165.3簡(jiǎn)單鏈表5.3.3鏈表的

2022/12/24

5.4共用體第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

2022/12/24

5.4.1共用體類型第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

union共用體類型名

{成員表列}； 如：

unionSS { intnum；

charname[20]；

floatCPPscore；

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/162022/12/16第1章初識(shí)C+2022/12/24

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

union { intnum; floatsex; }s1,s2;

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

一般格式為：

共用體變量名．成員名

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.4.4共用體類型變量的特點(diǎn)5.4共用體

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.4共用體5.4.4共用體類型變量的特點(diǎn)

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

2022/12/162022/12/16第1章初識(shí)C+2022/12/24

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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章初識(shí)C+2022/12/24

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.5程序舉例練習(xí):已有兩個(gè)鏈表h1和h2，結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下：structstudent{ charname[20]; //姓名

floatscore; //成績(jī)

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

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

（1）){//查找結(jié)點(diǎn)

if(!p)break; //本輪查找已到h1的尾結(jié)點(diǎn)

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本章結(jié)束第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

本章結(jié)束第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)結(jié)構(gòu)體與簡(jiǎn)單鏈表

《C++程序設(shè)計(jì)基礎(chǔ)教程》第5

章

要拼自己，不要拼爹；要追夢(mèng)，不要追星；要做“學(xué)霸”，不要做“學(xué)渣”。結(jié)構(gòu)體與簡(jiǎn)單鏈表《C++程序設(shè)計(jì)基礎(chǔ)教程》第5章動(dòng)態(tài)空間本章內(nèi)容結(jié)構(gòu)體12第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

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

結(jié)構(gòu)體是一種導(dǎo)出數(shù)據(jù)類型，它由若干個(gè)數(shù)據(jù)項(xiàng)組成，每個(gè)數(shù)據(jù)項(xiàng)可以是基本數(shù)據(jù)類型，也可以是導(dǎo)出數(shù)據(jù)類型。2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

898940301YangKe85.5

學(xué)號(hào)姓名C++成績(jī)圖5-1學(xué)生基本信息5.1結(jié)構(gòu)體

結(jié)構(gòu)體是一種導(dǎo)出數(shù)據(jù)類型，它由若干個(gè)

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1結(jié)構(gòu)體5.1.1

結(jié)構(gòu)體類型的定義定義一個(gè)結(jié)構(gòu)體類型的一般形式為：

struct結(jié)構(gòu)體名

{成員表列}；

圖5-1學(xué)生基本信息可以定義成如下結(jié)構(gòu)體類型。

structStudent{ intnum；

charname[20]；

floatCPPscore；

}；第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.1.2結(jié)構(gòu)體類型的變量一.結(jié)構(gòu)體類型變量的說(shuō)明定義結(jié)構(gòu)體類型的變量，有以下3種方法：

1.先聲明結(jié)構(gòu)體類型再定義變量名 例如：Studentstudent1,student2;第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言5.12022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/245.1.2結(jié)構(gòu)體類型的變量2.在聲明類型的同時(shí)定義變量

例如：structDay { inthour; intminute; intsecond; }d1,d2;5.1結(jié)構(gòu)體2022/12/16第1章初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章

2022/12/24第1章

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/24

2022/12/245.1.2結(jié)構(gòu)體類型的變量3.直接定義結(jié)構(gòu)體類型變量

例如：

struct { intnum; floatsex; }s1,s2;

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

初識(shí)C++程序設(shè)計(jì)語(yǔ)言第5章結(jié)構(gòu)體與簡(jiǎn)單鏈表

2022/12/242