軟件技術(shù)與基礎(chǔ)

軟件技術(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è)問題：對于空表和第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮

出現(xiàn)分支語句，增加程序復(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ù)需要來設(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)的位置，可以訪問到表中其他所有的結(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）申請新結(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;

//保存對頭結(jié)點(diǎn)的數(shù)據(jù)

Q->front->next=p->next;

//將對頭結(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ǔ)問題Pn(x)=anxn+an-1xn-1+…+a1x+a0當(dāng)多項(xiàng)式中存在大量0系數(shù)時(shí)，太浪費(fèi)存儲(chǔ)空間，為了合理利用存儲(chǔ)空間，可以用鏈?zhǔn)奖韥肀硎尽?/p>

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;//申請一個(gè)表頭結(jié)點(diǎn)

p->exp=-1;p->next=p;head=p;return;}2.3.6多項(xiàng)式的表示與計(jì)算四，多項(xiàng)式的運(yù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;//申請一個(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;//申請一個(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)式相加