軟件技術與基礎

軟件技術基礎第3講基本數據結構及其運算（4）內容提要2.1數據結構的基本概念2.2線性表及其順序存儲結構2.3線性鏈表 2.3.1線性鏈表的基本概念 2.3.2線性鏈表的運算操作 2.3.3鏈式的棧及操作 2.3.4鏈式的隊列及操作 2.3.5循環(huán)鏈表及運算 2.3.6多項式表示與運算2.3.5循環(huán)鏈表及其運算一，循環(huán)鏈表的概念在線性鏈表運算中，存在一個問題：對于空表和第一個結點的處理必須單獨考慮

出現分支語句，增加程序復雜度

循環(huán)鏈表

2.3.5循環(huán)鏈表及其運算一，循環(huán)鏈表的概念循環(huán)鏈表是與單鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環(huán)鏈表的最后一個結點的指針是指向該循環(huán)鏈表的第一個結點或者表頭結點，從而構成一個環(huán)形的鏈。

2.3.5循環(huán)鏈表及其運算二，循環(huán)鏈表的特點1）循環(huán)鏈表中增加一個表頭結點，其數據域為任意或根據需要來設置，指針域指向第一個元素的節(jié)點，循環(huán)鏈表的頭指針指向表頭結點。2）在建立一個循環(huán)鏈表時，必須使其最后一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個結點后插入一個新的結點。思考：空表、表尾的判定依據？

2.3.5循環(huán)鏈表及其運算二，循環(huán)鏈表的特點空表的判定

頭結點的指針域是否指向頭結點。

head->next?=head尾節(jié)點判定

該節(jié)點的指針是否指向頭結點。

p->next?=head

2.3.5循環(huán)鏈表及其運算二，循環(huán)鏈表的特點空表的判定

頭結點的指針域是否指向頭結點。

head->next?=head尾節(jié)點判定

該節(jié)點的指針是否指向頭結點。

p->next?=head

2.3.5循環(huán)鏈表及其運算三，循環(huán)鏈表的優(yōu)點1）給出表中任意結點的位置，可以訪問到表中其他所有的結點。2）由于表頭結點的存在，任何情況下循環(huán)鏈表中至少存在一個結點，使空表和非空表實現統(tǒng)一。2.3.5循環(huán)鏈表及其運算四，循環(huán)鏈表的運算插入

將新結點插入到指定結點之后。1）申請新結點的存儲空間；2.1）指定結點為頭結點，頭結點的指針指向新結點，新結點的指針指向指定結點。2.2）指定結點為中間結點，新結點指針指向指定結點，指定結點前結點指針指向新結點。2.3.5循環(huán)鏈表及其運算四，循環(huá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)鏈表及其運算四，循環(huán)鏈表的運算插入if(ptr==head->next)

{

/*----情況1：插在第一結點之前---*/

new_node->next=head->next;

head->next=new_node;

}

else

{

/*-----情況2：插在第一結點之后-------*/

new_node->next=ptr->next;

ptr->next=new_node;

}

returnhead;

}2.3.5循環(huán)鏈表及其運算四，循環(huán)鏈表的運算刪除

刪除循環(huán)鏈表中指定結點。1）判斷循環(huán)鏈表是否有結點；2）尋找指定結點的前結點；3）指定結點前結點指向的改變。2.3.5循環(huán)鏈表及其運算四，循環(huá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)鏈表及其運算四，循環(huán)鏈表的運算出隊DataTypeDeQueue(LinkQueue*Q)

{

DataTypex;

QueueNode*p;

if(QueueEmpty(Q))

Error(“Queueunderflow”);//下溢

p=Q->front->next;

//指向對頭結點

x=p->data;

//保存對頭結點的數據

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

//將對頭結點從鏈上摘下

if(Q->rear==p)

Q->rear=NULL;

free(p);

//釋放被刪隊頭結點

returnx;

//返回原隊頭數據

}

內容提要2.1數據結構的基本概念2.2線性表及其順序存儲結構2.3線性鏈表 2.3.1線性鏈表的基本概念 2.3.2線性鏈表的運算操作 2.3.3鏈式的棧及操作 2.3.4鏈式的隊列及操作 2.3.5循環(huán)鏈表及運算 2.3.6多項式表示與運算2.3.6多項式的表示與計算一，多項式的存儲問題Pn(x)=anxn+an-1xn-1+…+a1x+a0當多項式中存在大量0系數時，太浪費存儲空間，為了合理利用存儲空間，可以用鏈式表來表示。

2.3.6多項式的表示與計算二，多項式的表示

可以采用線性單鏈表或者循環(huán)鏈表方式。

2.3.6多項式的表示與計算三，多項式的結點結構

多項式的非零系數結點結構的數據域包括指數項和系數項兩部分；指針域指針指向下一個非零系數項。structnode{intexp;//指數為整型

doublecoef;//系數為雙精度型

node*next;//指針域};

2.3.6多項式的表示與計算四，多項式的運算多項式的運算包括多項式鏈表的生成、釋放、多項式的輸出、相加和相乘等。建立空多項式鏈表voidinit_poly(){node*p;p=newnode;//申請一個表頭結點

p->exp=-1;p->next=p;head=p;return;}2.3.6多項式的表示與計算四，多項式的運算從鍵盤輸入多項式鏈表voidcreate_poly(){node*p,*k;inte;doublec;k=head;//記住多項式鏈尾

cout<<“輸入:系數<空格>指數。輸入指數-1結束！”<<endl;//降冪cin>>c>>e;while(e>=0){p=newnode;//申請一個新結點

p->exp=e;p->coef=c;//填入指數與系數

p->next=head;//新結點鏈到臨時多項式鏈尾

k->next=p;k=p;//記住多項式鏈尾

cin>>c>>e;}return;}2.3.6多項式的表示與計算四，多項式的運算從數組復制多項式鏈表voidcreate2_poly(intn,inte[],doublec[]){intk;node*p;for(k=n-1;k>=0;k--) {p=newnode;//申請一個新結點

p->coef=c[k];p->exp=e[k];//置系數與指數域

p->next=head->next;//新結點鏈到表頭

head->next=p; }return;}2.3.6多項式的表示與計算四，多項式的運算釋放多項式鏈表voiddel_poly(){node*p,*q;q=head->next;while(q!=head) {p=q->next;deleteq;q=p;}q->next=head;return;}2.3.6多項式的表示與計算四，多項式的運算輸出多項式鏈表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多項式的表示與計算四，多項式的運算多項式相加voidadd(Poly&p2,Polyp){node*k,*q,*m,*n;inte;doublec;k=p.head;//記住和多項式鏈尾

m=head->next;n=p2.head->next;while((m->exp!=-1)||(n->exp!=-1)) {if(m->exp==n->exp)//兩個鏈表當前結點的指數相等

{c=m->coef+n->coef;//系數相加

e=m->exp;//復抄指數

m=m->next;n=n->next;}elseif(m->exp>n->exp) {c=m->coef;e=m->exp;//復抄鏈表1中的系數與指數值

m=m->next;}2.3.6多項式的表示與計算四，多項式的運算多項式相加