




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
軟件技術(shù)基礎(chǔ)第3講基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(4)內(nèi)容提要2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)2.3線性鏈表 2.3.1線性鏈表的基本概念 2.3.2線性鏈表的運(yùn)算操作 2.3.3鏈?zhǔn)降臈<安僮?2.3.4鏈?zhǔn)降年?duì)列及操作 2.3.5循環(huán)鏈表及運(yùn)算 2.3.6多項(xiàng)式表示與運(yùn)算2.3.5循環(huán)鏈表及其運(yùn)算一,循環(huán)鏈表的概念在線性鏈表運(yùn)算中,存在一個(gè)問(wèn)題:對(duì)于空表和第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮
出現(xiàn)分支語(yǔ)句,增加程序復(fù)雜度
循環(huán)鏈表
2.3.5循環(huán)鏈表及其運(yùn)算一,循環(huán)鏈表的概念循環(huán)鏈表是與單鏈表一樣,是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu),所不同的是,循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn),從而構(gòu)成一個(gè)環(huán)形的鏈。
2.3.5循環(huán)鏈表及其運(yùn)算二,循環(huán)鏈表的特點(diǎn)1)循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn),其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置,指針域指向第一個(gè)元素的節(jié)點(diǎn),循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。2)在建立一個(gè)循環(huán)鏈表時(shí),必須使其最后一個(gè)結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn),而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)。思考:空表、表尾的判定依據(jù)?
2.3.5循環(huán)鏈表及其運(yùn)算二,循環(huán)鏈表的特點(diǎn)空表的判定
頭結(jié)點(diǎn)的指針域是否指向頭結(jié)點(diǎn)。
head->next?=head尾節(jié)點(diǎn)判定
該節(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)。
p->next?=head
2.3.5循環(huán)鏈表及其運(yùn)算二,循環(huán)鏈表的特點(diǎn)空表的判定
頭結(jié)點(diǎn)的指針域是否指向頭結(jié)點(diǎn)。
head->next?=head尾節(jié)點(diǎn)判定
該節(jié)點(diǎn)的指針是否指向頭結(jié)點(diǎn)。
p->next?=head
2.3.5循環(huán)鏈表及其運(yùn)算三,循環(huán)鏈表的優(yōu)點(diǎn)1)給出表中任意結(jié)點(diǎn)的位置,可以訪問(wèn)到表中其他所有的結(jié)點(diǎn)。2)由于表頭結(jié)點(diǎn)的存在,任何情況下循環(huán)鏈表中至少存在一個(gè)結(jié)點(diǎn),使空表和非空表實(shí)現(xiàn)統(tǒng)一。2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算插入
將新結(jié)點(diǎn)插入到指定結(jié)點(diǎn)之后。1)申請(qǐng)新結(jié)點(diǎn)的存儲(chǔ)空間;2.1)指定結(jié)點(diǎn)為頭結(jié)點(diǎn),頭結(jié)點(diǎn)的指針指向新結(jié)點(diǎn),新結(jié)點(diǎn)的指針指向指定結(jié)點(diǎn)。2.2)指定結(jié)點(diǎn)為中間結(jié)點(diǎn),新結(jié)點(diǎn)指針指向指定結(jié)點(diǎn),指定結(jié)點(diǎn)前結(jié)點(diǎn)指針指向新結(jié)點(diǎn)。2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算插入clinkinsertnode(clinkhead,clinkptr,intvalue)
{
clinknew_node;
new_node=(clink)malloc(sizeof(cnode));
if(!new_node)
returnNULL;
new_node->data=value;
new_node->next=NULL;
if(head==NULL)
{
new_node->next=new_node;
returnnew_node;
}2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算插入if(ptr==head->next)
{
/*----情況1:插在第一結(jié)點(diǎn)之前---*/
new_node->next=head->next;
head->next=new_node;
}
else
{
/*-----情況2:插在第一結(jié)點(diǎn)之后-------*/
new_node->next=ptr->next;
ptr->next=new_node;
}
returnhead;
}2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算刪除
刪除循環(huán)鏈表中指定結(jié)點(diǎn)。1)判斷循環(huán)鏈表是否有結(jié)點(diǎn);2)尋找指定結(jié)點(diǎn)的前結(jié)點(diǎn);3)指定結(jié)點(diǎn)前結(jié)點(diǎn)指向的改變。2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算刪除clinkdeletenode(clinkhead,clinkptr){
clinkprevious;
previous=head;
if(head!=head->next)
while(previous->next!=ptr)
previous=previous->next;
previous->next=ptr->next;
}例題2.3.5循環(huán)鏈表及其運(yùn)算四,循環(huán)鏈表的運(yùn)算出隊(duì)DataTypeDeQueue(LinkQueue*Q)
{
DataTypex;
QueueNode*p;
if(QueueEmpty(Q))
Error(“Queueunderflow”);//下溢
p=Q->front->next;
//指向?qū)︻^結(jié)點(diǎn)
x=p->data;
//保存對(duì)頭結(jié)點(diǎn)的數(shù)據(jù)
Q->front->next=p->next;
//將對(duì)頭結(jié)點(diǎn)從鏈上摘下
if(Q->rear==p)
Q->rear=NULL;
free(p);
//釋放被刪隊(duì)頭結(jié)點(diǎn)
returnx;
//返回原隊(duì)頭數(shù)據(jù)
}
內(nèi)容提要2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.2線性表及其順序存儲(chǔ)結(jié)構(gòu)2.3線性鏈表 2.3.1線性鏈表的基本概念 2.3.2線性鏈表的運(yùn)算操作 2.3.3鏈?zhǔn)降臈<安僮?2.3.4鏈?zhǔn)降年?duì)列及操作 2.3.5循環(huán)鏈表及運(yùn)算 2.3.6多項(xiàng)式表示與運(yùn)算2.3.6多項(xiàng)式的表示與計(jì)算一,多項(xiàng)式的存儲(chǔ)問(wèn)題Pn(x)=anxn+an-1xn-1+…+a1x+a0當(dāng)多項(xiàng)式中存在大量0系數(shù)時(shí),太浪費(fèi)存儲(chǔ)空間,為了合理利用存儲(chǔ)空間,可以用鏈?zhǔn)奖韥?lái)表示。
2.3.6多項(xiàng)式的表示與計(jì)算二,多項(xiàng)式的表示
可以采用線性單鏈表或者循環(huán)鏈表方式。
2.3.6多項(xiàng)式的表示與計(jì)算三,多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)
多項(xiàng)式的非零系數(shù)結(jié)點(diǎn)結(jié)構(gòu)的數(shù)據(jù)域包括指數(shù)項(xiàng)和系數(shù)項(xiàng)兩部分;指針域指針指向下一個(gè)非零系數(shù)項(xiàng)。structnode{intexp;//指數(shù)為整型
doublecoef;//系數(shù)為雙精度型
node*next;//指針域};
2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算多項(xiàng)式的運(yùn)算包括多項(xiàng)式鏈表的生成、釋放、多項(xiàng)式的輸出、相加和相乘等。建立空多項(xiàng)式鏈表voidinit_poly(){node*p;p=newnode;//申請(qǐng)一個(gè)表頭結(jié)點(diǎn)
p->exp=-1;p->next=p;head=p;return;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算從鍵盤(pán)輸入多項(xiàng)式鏈表voidcreate_poly(){node*p,*k;inte;doublec;k=head;//記住多項(xiàng)式鏈尾
cout<<“輸入:系數(shù)<空格>指數(shù)。輸入指數(shù)-1結(jié)束!”<<endl;//降冪cin>>c>>e;while(e>=0){p=newnode;//申請(qǐng)一個(gè)新結(jié)點(diǎn)
p->exp=e;p->coef=c;//填入指數(shù)與系數(shù)
p->next=head;//新結(jié)點(diǎn)鏈到臨時(shí)多項(xiàng)式鏈尾
k->next=p;k=p;//記住多項(xiàng)式鏈尾
cin>>c>>e;}return;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算從數(shù)組復(fù)制多項(xiàng)式鏈表voidcreate2_poly(intn,inte[],doublec[]){intk;node*p;for(k=n-1;k>=0;k--) {p=newnode;//申請(qǐng)一個(gè)新結(jié)點(diǎn)
p->coef=c[k];p->exp=e[k];//置系數(shù)與指數(shù)域
p->next=head->next;//新結(jié)點(diǎn)鏈到表頭
head->next=p; }return;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算釋放多項(xiàng)式鏈表voiddel_poly(){node*p,*q;q=head->next;while(q!=head) {p=q->next;deleteq;q=p;}q->next=head;return;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算輸出多項(xiàng)式鏈表voidprt_poly(){node*k;if(head->next==head) cout<<"空表"<<endl;k=head->next;while(k!=head) {cout<<"("<<k->coef<<","<<k->exp<<")"<<endl; k=k->next; }return;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算多項(xiàng)式相加voidadd(Poly&p2,Polyp){node*k,*q,*m,*n;inte;doublec;k=p.head;//記住和多項(xiàng)式鏈尾
m=head->next;n=p2.head->next;while((m->exp!=-1)||(n->exp!=-1)) {if(m->exp==n->exp)//兩個(gè)鏈表當(dāng)前結(jié)點(diǎn)的指數(shù)相等
{c=m->coef+n->coef;//系數(shù)相加
e=m->exp;//復(fù)抄指數(shù)
m=m->next;n=n->next;}elseif(m->exp>n->exp) {c=m->coef;e=m->exp;//復(fù)抄鏈表1中的系數(shù)與指數(shù)值
m=m->next;}2.3.6多項(xiàng)式的表示與計(jì)算四,多項(xiàng)式的運(yùn)算多項(xiàng)式相加
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO/TS 23164:2025 EN Automation systems and integration - Core vocabulary for industrial data
- 【正版授權(quán)】 ISO 7434:2024 EN Fasteners - Slotted set screws with cone point
- 2025年度展覽場(chǎng)地租賃合同保證金與押金繳納細(xì)則
- 2025年涼果蜜餞合作協(xié)議書(shū)
- 2025年度智慧交通樞紐包工施工合同(智能交通系統(tǒng))
- 2025房地產(chǎn)股權(quán)并購(gòu)項(xiàng)目盡職調(diào)查及服務(wù)合同
- 2025年度智能家居標(biāo)準(zhǔn)私房買(mǎi)賣(mài)合同范文
- 增強(qiáng)知識(shí)管理的主管工作計(jì)劃
- 多元化班級(jí)文化的建設(shè)方法計(jì)劃
- 客戶(hù)投訴處理流程的總結(jié)與反思計(jì)劃
- 《2024版CSCO胰腺癌診療指南》更新要點(diǎn)
- 兒童福利機(jī)構(gòu)安全管理規(guī)范
- 鞋類(lèi)制造過(guò)程的節(jié)能與減排
- 第1課 おじぎ 課件高中日語(yǔ)人教版第一冊(cè)-1
- ISO∕IEC 23894-2023 信息技術(shù) -人工智能 - 風(fēng)險(xiǎn)管理指南(雷澤佳譯-2024)
- 事前績(jī)效評(píng)估具體工作實(shí)施方案
- 六年級(jí)下冊(cè)語(yǔ)文第一單元測(cè)試卷 部編版(含答案)
- 2024年湖南高速鐵路職業(yè)技術(shù)學(xué)院?jiǎn)握新殬I(yè)適應(yīng)性測(cè)試題庫(kù)新版
- 《研學(xué)旅行市場(chǎng)營(yíng)銷(xiāo)》課件-研學(xué)旅行市場(chǎng)營(yíng)銷(xiāo)之社群營(yíng)銷(xiāo)
- 醫(yī)學(xué)人體美學(xué)的測(cè)量和評(píng)估
- 艱難梭菌感染動(dòng)物模型的建立及其應(yīng)用評(píng)價(jià)
評(píng)論
0/150
提交評(píng)論