計(jì)算機(jī)軟件基礎(chǔ)（MOOC版）課件 第3章 線(xiàn)性表及其存儲(chǔ)結(jié)構(gòu)

第三章

線(xiàn)性表BasicsofComputer

Software12345線(xiàn)性表的基本概念線(xiàn)性表的順序存儲(chǔ)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)堆隊(duì)棧列線(xiàn)

性

表

的

基

本

概

念

與

運(yùn)

算PART 01abcdea,b,c,d,e是數(shù)據(jù)元素，表長(zhǎng)為5線(xiàn)性表的概念線(xiàn)性表的運(yùn)算線(xiàn)性表的定義abcde線(xiàn)性表的概念線(xiàn)性表的運(yùn)算線(xiàn)性表的特點(diǎn)常見(jiàn)線(xiàn)性表有：隊(duì)列、堆棧、字符串、數(shù)組線(xiàn)性表的運(yùn)算線(xiàn)性表的概念

線(xiàn)性表的運(yùn)算線(xiàn)性表的運(yùn)算置空表取前驅(qū)求表長(zhǎng)取后繼插入結(jié)點(diǎn)刪除結(jié)點(diǎn)按值查找提取元素排序運(yùn)算回憶：數(shù)據(jù)的物理結(jié)構(gòu)線(xiàn)性表的概念

線(xiàn)性表的運(yùn)算回顧鏈接存儲(chǔ)表示增加一個(gè)或多個(gè)指針，用于存放和該數(shù)據(jù)元素

有關(guān)的另一個(gè)數(shù)據(jù)元素的地址，可以不占用連續(xù)地址空間。散列存儲(chǔ)表示是一種在數(shù)據(jù)元素的關(guān)鍵碼與存儲(chǔ)位置之間建立確定對(duì)應(yīng)關(guān)系的查找

技術(shù)。順序存儲(chǔ)表示將邏輯上相鄰的數(shù)據(jù)元素存放在內(nèi)存中的相鄰位置中索引存儲(chǔ)表示指除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址線(xiàn)

性

表

的

順

序

存

儲(chǔ)

及

其

運(yùn)

算PART 02定 義：將線(xiàn)性表中的元素相繼存放在一個(gè)

連續(xù)的存儲(chǔ)空間中存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)（如：動(dòng)態(tài)數(shù)組）特 點(diǎn)：邏輯上相鄰的元素，物理次序也相鄰存取方式：隨機(jī)存取順序表的概念順序表的運(yùn)算順序表的應(yīng)用順序表的定義012345678910371354645652175888092LOC(a1)=LOC(a1)LOC(a2)=

LOC(a1)+(2-1)*l：LOC(ai)=

LOC(a1)+(i-1)*la1a2…a

i………ana a+l … a+(i-1)*l

…… …a+(n-1)*lidle順序表的概念順序表的運(yùn)算順序表的應(yīng)用1 2 …順序表的存儲(chǔ)方式i … … … na1a2…a

i………ana a+l … a+(i-1)*l…

… … a+(n-1)*l idle例如：設(shè)順序表的首地址為1000，數(shù)據(jù)類(lèi)型是整型數(shù)，則每個(gè)元素的長(zhǎng)度是2個(gè)字節(jié)，則有：LOC(a5)=LOC(a1)+(5-1)*

2=1000+4*2=1008順序表的概念順序表的運(yùn)算順序表的應(yīng)用1 2 …順序表的存儲(chǔ)方式i … … … nabcd……4datalength#defineListSize

100

//最大允許長(zhǎng)度typedefchar

ListData;typedefstruct

{

ListData

data[listsize];

//存儲(chǔ)空間基址

int

length; //當(dāng)前元素個(gè)數(shù)

}

SeqList; 順序表的類(lèi)型名

SeqList

L；L是變量名順序表的概念順序表的運(yùn)算 順序表的應(yīng)用順序表的類(lèi)型定義012345678910371354645652175data8length設(shè)有定義：SeqList

L；L表的最大長(zhǎng)度為11表的當(dāng)前長(zhǎng)度為8L.data[6]

//訪(fǎng)問(wèn)第7個(gè)，即6號(hào)元素

21L.length

//表長(zhǎng)L.data[L.length]

//順序表的下一個(gè)空位置，即8號(hào)位置順序表的概念順序表的運(yùn)算順序表的應(yīng)用順序表的引用初始化

voidInitList(SeqList

L){

L.length=

0;

}8012345678910371354645652175datalengthL0順序表的概念

順序表的運(yùn)算順序表的應(yīng)用順序表的初始化順序表的概念

順序表的運(yùn)算順序表的應(yīng)用順序表的查找

intFind(SeqListL,ListDatax

)

{int

i=0;

while(i<L.length&&

L.data[i]!=x)

i++;

if(i<L.length)return

i;

elsereturn

-1;

}i

1-1

0順序表的概念

順序表的運(yùn)算順序表的應(yīng)用按值查找算法順序表基本運(yùn)算——求表的長(zhǎng)度

intLength(SeqListL

)

{

return

L.length;

}順序表的概念

順序表的運(yùn)算順序表的應(yīng)用求表長(zhǎng)算法012345678910371354645652175data8lengthL在順序表L中提取第i個(gè)元素的值

ListDataGetData(SeqList&L,inti

)

{if

(i>=1&&i<=L.length)

return

L.data[i-1];

else

{

printf

(“參數(shù)

i不合理！\n”);

returnnull}

}

順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素算法（提取函數(shù)）012345678910371354645652175data8lengthL順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素的前驅(qū)操作listdataNext(SeqList&L,ListData

x)

{inti=

Find(L,x);

if(i>=0&&i<L.length-1

)

returnL.data[i+1];else

return

null;

}順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素的后繼操作插入操作(i號(hào)位置插入x)for

( j=L.length;j>i;j--

)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return

1;}else {§intInsert(SeqList&L,ListDatax,inti

)if(i<0||i>L.length||L.length==

ListSize)return0; //插入失敗//移動(dòng)數(shù)據(jù)//插入成功順序表的概念

順序表的運(yùn)算順序表的應(yīng)用插入操作插入時(shí)，數(shù)據(jù)平均移動(dòng)次數(shù)AMN在各表項(xiàng)插入概率相等時(shí)，有：Pi是在i號(hào)位置上插入元素的概率,我們假設(shè)是等概率情況Ci是在i號(hào)位置上插入元素時(shí)所需要的移動(dòng)次數(shù)插入操作(i號(hào)位置插入x)順序表的概念

順序表的運(yùn)算順序表的應(yīng)用插入操作的算法分析int Delete(SeqList&L,ListDatax

){inti=Find(L,

x);if(i>=0

)//在表中查找

x//在表中找到

x{for(intj=i;j<L.length;j++)L.data[j]=L.data[j+1];L.length--

;//成功刪除return1;}return

0;

//表中沒(méi)有

x}順序表的概念

順序表的運(yùn)算刪除指定元素x順序表的應(yīng)用刪除算法刪除時(shí)，平均移動(dòng)次數(shù)AMN在各位置刪除概率相等時(shí)，有：Pi是在刪除i號(hào)位置上的元素的概率,我們假設(shè)是等概率情況Ci是在刪除i號(hào)位置上的元素時(shí)所需要的移動(dòng)次數(shù)順序表的概念

順序表的運(yùn)算順序表的應(yīng)用刪除算法算法分析順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊優(yōu)點(diǎn) 缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充設(shè)：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}則：A=A∪B={1，2，3，4，5，7，9，10}={1，3，4，5，7，10，2，9}={2，4，7，9，1，3，5，10}看：A=A∪B={1，3，4，5，7，10，2，9}=A+(B-A)結(jié)論：A和B的并集中，A中的所有元素屬于他們的并集B中除去屬于A的剩余元素同樣屬于他們的并集因此：只要以A為基礎(chǔ)，從B中依次取出所有元素，在A中查詢(xún)，如果沒(méi)找到就將該元素插入到A中順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“并”運(yùn)算//在B中取一元素//在A中查找它//未找到，則插入到A尾部{intx=GetData(B,i

);intk=Find(A,

x);if(k==-1

)Insert(A,x,

A.length)}}算法思路：以A為基礎(chǔ)，從B中依次取出所有元素，在A中查詢(xún)，如果沒(méi)找到就將該元素插入到A中voidUnion(SeqList&A,SeqList&B

){ for(inti=0;i<B.lenggth;i++

)順序表的概念順序表的運(yùn)算

順序表的應(yīng)用

集合的“并”運(yùn)算設(shè)：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}則：A=A∩B={4，7}因此：只要以A為基礎(chǔ)，從A中依次取出所有元素，在B中查詢(xún)，如果沒(méi)找到就將該元素從A中刪除順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算voidIntersection(SeqList&A,SeqList&B

){inti=

0;while(i<A.length

){//在A中取一元素//在B中查找它//未找到在A中刪除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);elsei++;}}順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算（一）voidIntersection(SeqList&A,SeqList&B

){inti=A.length-1;while(i>=0A.length

){//在A中取一元素//在B中查找它//未找到在A中刪除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);i++;}}大家可以分析一下交集的方法1和方法2有什么不同？為什么不用for循環(huán)？順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算（二）線(xiàn)

性

表

的

鏈

式

存

儲(chǔ)

及

其

運(yùn)

算PART 03單鏈表雙向鏈表循環(huán)鏈表靜態(tài)鏈表鏈表：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)表示1定義：用一組地址任意的存儲(chǔ)單元存放線(xiàn)性表中的數(shù)據(jù)元素。鏈表：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)表示1每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成，它包括兩個(gè)域:數(shù)據(jù)域（Data）和

指針域（next）存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特 點(diǎn)：存儲(chǔ)單元可以不連續(xù)。存取方式：按順序存取。Nodedata

next線(xiàn)性鏈表的結(jié)點(diǎn)結(jié)構(gòu)1typedefintListData;

//定義數(shù)據(jù)類(lèi)型typedefstructnode

//鏈表結(jié)點(diǎn)

{

ListData

data; //結(jié)點(diǎn)數(shù)據(jù)域

structnode*next;

//結(jié)點(diǎn)鏈域}

ListNode;Typedef

ListNode

*

LinkList;

//鏈表頭指針LinkListhead，p,q;

//鏈表頭指針Nodedata nextListNode是類(lèi)型名線(xiàn)性鏈表的類(lèi)型定義1為使運(yùn)算簡(jiǎn)單，可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前另加一個(gè)結(jié)點(diǎn)，稱(chēng)之為頭結(jié)點(diǎn)。后面的鏈表操作均是帶頭結(jié)點(diǎn)的單鏈表….

FBAhead頭結(jié)點(diǎn) 第一結(jié)點(diǎn)設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空鏈表與非空鏈表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。帶頭結(jié)點(diǎn)的單鏈表1

952headPp->data;p->next;p->next->data;q->next=nil;p=p->next;q//得到元素值2//2和5之間的指針//得到元素值5p->next->next->data; //得到元素9//最后一個(gè)結(jié)點(diǎn)的指針?lè)至恐每?/指針后移一個(gè)節(jié)點(diǎn)單鏈表的引用1情況1headabc ^單鏈表的插入操作情況1：在第一個(gè)結(jié)點(diǎn)前插入情況2：中間插入情況3：插入到鏈表尾部情況3情況2newnodea bc ^Newnode->next=p->next;p->next=newnode;Phead第一種情況：在第一個(gè)結(jié)點(diǎn)前插入單鏈表的插入操作第二種情況：在鏈表中間插入單鏈表的插入操作第三種情況：在鏈表尾部插入單鏈表的插入操作1.移動(dòng)指針P向后移動(dòng)，指向下一個(gè)結(jié)點(diǎn)：

p=p->next;2.用指針動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)構(gòu)體空間：malloc函數(shù)的格式：(類(lèi)型

*)

malloc(size）；q=(ListNode*)malloc(sizeof(ListNode));q->data=x;3.在移動(dòng)指針P之后，插入新結(jié)點(diǎn)的操作：q->next=p->next;p->next=q;準(zhǔn)備知識(shí)(在head鏈表第

i

個(gè)結(jié)點(diǎn)處插入新元素

x)intInsert(LinkList*head,inti,int

x)

{

p=head;

k=0;

while(p!=nil&&

k<i-1)

{

p=p->next;

k++;

}

//找第

i-1個(gè)結(jié)點(diǎn)

if(p==nil)

//終止插入

{

printf(“無(wú)效的插入位置!\n”);

return0;

}

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//創(chuàng)建新結(jié)點(diǎn)

q->next=p->next;

//完成插入

p->next=q;

Return1;}

單鏈表插入算法一//完成插入

q->next=p->next;

p->next=q;

}

插入算法2(在有序鏈表head中插入元素x)Insertsort(LinkList*head,int

x)

{

p=head;

while

(p

-

>

n

e

x

t

！

=

n

i

l

&

&

p

-

>

n

e

x

t

-

>

d

a

t

a

<

=

x

)

p=p->next;

//為x結(jié)點(diǎn)定位

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//創(chuàng)建新結(jié)點(diǎn)單鏈表插入算法二單鏈表的刪除操作（刪除P之后的結(jié)點(diǎn)）單鏈表的刪除操作intDelete(head,x){p=head;

while(p->next!=nil&&

p->next->data!=x)

p=p->next;

if(p->next==nil

)

{printf(“鏈表中沒(méi)有要?jiǎng)h除的元素”)；

return0；}

q=p->next;

p->next=q->next;

free(q);

Return

1}刪除元素值為x的結(jié)點(diǎn)單鏈表的刪除算法前插法建立單鏈表建立空鏈表從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。設(shè)輸入順序?yàn)椋?、5、2LinkListcreateListF

()

{

head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空鏈表

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新結(jié)點(diǎn)

q->next=head->next;

//插入到頭節(jié)點(diǎn)之后

head->next=q;

scanf(“%d”,&x);

}

returnhead;}前插法建立單鏈表算法每次將新結(jié)點(diǎn)加在鏈表的表尾；尾指針rear

,總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；后插法建立單鏈表LinkListcreateListR

(){head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空鏈表

rear=head;

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新結(jié)點(diǎn)//插入到頭節(jié)點(diǎn)之后

rear->next=q;

rear=q;

scanf(“%d”,&x);

}

rear->next=

nil;

returnhead;}后插法建立單鏈表算法單鏈表的輸出output(head);//讓移動(dòng)指針指向第一個(gè)結(jié)點(diǎn){p=head->next；while

(p!=nil){printf(“%5d”,p->data);p=p->next; //指針后移}}intLength(LinkList

head)

{

p=head->next;count=0;

while(p!=NULL

)

{

count++;

p=p->next;

}

return

count;}計(jì)算單鏈表長(zhǎng)度單鏈表的清空刪去除結(jié)點(diǎn)外的所有結(jié)點(diǎn)voidmakeEmpty(LinkListhead

)

{

ListNode

*q;

while

(head->next!=nil)

{

q=head->next;

head->next=q->next;

free(q);

//釋放

}

}ListNode*Find(LinkListhead,ListDatavalue

)

{

//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)p=head->next; //指針

p

指示第一個(gè)結(jié)點(diǎn)while(p!=nil&&

p->data!=value)

p=p->next;

return

p;

}問(wèn)題：如果在有序鏈表中進(jìn)行查找，該如何修改，以提高效率？單鏈表的按值查找ListNode*Locate(LinkListhead,int

i){//返回表中第i個(gè)元素的地址

if(i<0)return

nil;

p=head;

k=0;

while(p!=nil&&k<i

)

{p=p->link;

k++;

} //找第

i

個(gè)結(jié)點(diǎn)

if

(k==i)

return

p;

//返回第

i

個(gè)結(jié)點(diǎn)地址

elsereturn

nil;

}單鏈表的按序號(hào)查找循環(huán)鏈表特點(diǎn):最后一個(gè)結(jié)點(diǎn)的

next指針不為nil，而是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，就可搜尋所有結(jié)點(diǎn)的地址存儲(chǔ)結(jié)構(gòu):鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)an-1heada1a0head(空表)(非空表)帶表頭結(jié)點(diǎn)的循環(huán)鏈表循環(huán)鏈表的插入、刪除、查詢(xún)等操作和相應(yīng)的單鏈表的操作基本相同。區(qū)別：在判斷尾結(jié)點(diǎn)時(shí)的條件不同。單

鏈

表：p->next==nil循環(huán)鏈表：p->next==head循環(huán)鏈表q->next=p->next;p->next=q;q=p->next;p->next=q->next;free(q);循環(huán)鏈表的插入循環(huán)鏈表的刪除雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)：指向直接前驅(qū)指向直接后繼非空表空表headhead雙向循環(huán)鏈表typedefintListData;typedefstruct

dnode

{

ListNode

data;

structdnode*prior,

*next;

}

DblNode;typedefDblNode*

DblList;

雙向循環(huán)鏈表的定義voidCreateDblList(DblList

head)

{

head=(DblNode*)malloc(sizeof(

DblNode));

head->prior=head;

head->next=head;

//表頭結(jié)點(diǎn)的鏈指針指向自己}head建立空的雙向循環(huán)鏈表intLength(DblList

head)

{

DblNode*p=

head->next;

intcount=

0;

while(p!=

head)

{p=p->next;count++;

}

return

count;}

head31 482515計(jì)算雙向循環(huán)鏈表長(zhǎng)度q->prior=

p;q->next=

p->next;p->next=

q;q->next->prior=

q;在結(jié)點(diǎn)

*p

后插入q結(jié)點(diǎn)head314815pheadp31482515q25q雙向循環(huán)鏈表的插入（非空表）在結(jié)點(diǎn)

*p

后插入q結(jié)點(diǎn)q->prior=

p;q->next =

p->next;p->next =

q;q->next->prior=

q;qfirst25firstp p同樣的4條指令對(duì)空表來(lái)說(shuō)同樣適用雙向循環(huán)鏈表的插入（空表）Insertsort(DblListhead,int

x)

{

p=head;

while(p->next=nil&&

p->next->data<=x)

p=p->next;

//為x結(jié)點(diǎn)定位

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//創(chuàng)建新結(jié)點(diǎn)

q->prior=

p;

q->next=p->next;

p->next=q;

p->next->prior

=

q;

//完成插入}雙向循環(huán)鏈表的插入算法head314815p例如：刪除48：p->next->prior=p->prior;p->prior->next=p->next;free(p);雙向循環(huán)鏈表的刪除操作first31p例如：刪除31p->next->prior=p->prior;p->prior->next=

p->next;雙向循環(huán)鏈表的刪除操作刪除最后一個(gè)結(jié)點(diǎn)（1）存儲(chǔ)分配的方式u

順序表的存儲(chǔ)空間是靜態(tài)分配的u

鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的（2）存儲(chǔ)密度u

順序表的存儲(chǔ)密度

=

1u

鏈表的存儲(chǔ)密度

<

1注：存儲(chǔ)密度=

結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量順序表與鏈表的比較基于空間的比較n 存取方式u

順序表可以隨機(jī)存取，也可以順序存取u

鏈表是順序存取的n 插入/刪除時(shí)移動(dòng)元素個(gè)數(shù)u

順序表平均需要移動(dòng)近一半元素u

鏈表不需要移動(dòng)元素，只需要修改指針順序表與鏈表的比較基于時(shí)間的比較有序鏈表的歸并有序鏈表的歸并LinkList

meger(ha,hb)

//將ha、hb兩個(gè)有序鏈表歸并為hc有序鏈表{LinkList

*pa,*pb,*pc;

pa=ha->next;

pb=hb->next;

pc=ha;

while

(pa!=nil&&pb!=nil)

if

(pa->data<pb->data)

{pc->next=pa;pc=pa;

pa=pa->next;}

else

{pc->next=pb;pc=pb;

pb=pb->next;}

if(pb！=nil)

pc->next=pb;

else

pc->next=pa;

free(hb);

return

ha;

}在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域有2個(gè)，分別是coef（系數(shù)）和exp（指數(shù)）。Coef exp nexttypedefstruct

pnode{

int

coef，exp;

structpnode*

next;

}PolyNode;typedefPolyNode

*Polylist多項(xiàng)式的相加1 0-10

62 8714

^418

^15

14418

^AH=

1-10x6+2x8+7x14BH=

-x4+10x6-3x10+8x14+4x18AHBHCH-1

4 10

6 -3

10 8

14（a）兩個(gè)相加的多項(xiàng)式1 0 -1

4 2 8 -310（b）兩個(gè)多項(xiàng)式相加的結(jié)果多項(xiàng)式的相加polylistPolynomialAdd(Polylist

ah,bh){

Term*pa,*pb,*pc,

*p;

pa=ah->next;

pb=bh->next;

pc=ah;

deletebh;多項(xiàng)式的相加多項(xiàng)式的相加while(pa!=nil&&pb!=nil

)

if(pa→exp==pb→exp)

//冪相同

{tcoef=pa→coef+pb→coef;

if

(tcoef==0

//系數(shù)相加為0

{p=pa;pa=pa->next;

free(p);

p=pb;pb=pb->next;

free(p);

}

else

//系數(shù)相加不為0

{pa→coef=tcoef;

pc→next=pa;

pc=pa;

pa=pa→next;

p=pb;pb=pb→next;

free(p);

}

}多項(xiàng)式的相加

elseif

(pa→exp<pb→exp)

{

pc→next=pa;

pc=pa;

pa=pa→next;

}

elseif

(pa→exp>pb→exp)

{

pc→next=pb;

pc=pb;

pb=pb→next;

}if(pb==nil)

pc→next=pa;

else

pc→next=pb;

}

堆棧PART 04定義:是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。棧頂(top):允許插入和刪除的一端，則另一端稱(chēng)為棧底(bottom)特點(diǎn)：后進(jìn)先出

(LIFO)堆棧及其應(yīng)用實(shí)現(xiàn)程序調(diào)用，子程序嵌套調(diào)用和遞歸調(diào)用對(duì)于“中斷”技術(shù)，堆棧更是不可缺少的，保存“斷點(diǎn)”和“現(xiàn)場(chǎng)”堆棧在計(jì)算機(jī)中的作用020304050601堆棧的主要操作StackEmpty(S)判棧空StackFull(S)

判棧滿(mǎn)POP（S）

出棧GetTop（S）取棧頂元素順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素指針top指向棧頂元素在順序棧中的下一個(gè)位置base為棧底指針，指向棧底的位置。鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，利用鏈表來(lái)存儲(chǔ)堆棧的數(shù)據(jù)元素。堆棧的表示和實(shí)現(xiàn)空棧topbottom

aa

進(jìn)棧top

bottomb

進(jìn)棧

b

abottomtopa

b

c e

d bottomtope

d

c

b

af

進(jìn)棧溢出bottomtopbottomtop

d

c

b

ae

出棧c,d,e分別進(jìn)棧棧滿(mǎn)棧滿(mǎn)順序棧的常見(jiàn)操作}

SeqStack；……datatoplength改為top#defineSTACK_SIZE100；typedef

struct

//順序棧定義{int

data[STACK_SIZE];

inttop;

//棧頂指針length改為top順序棧的類(lèi)型表示§堆棧的初始化voidInitStack(SeqStack

*S)

{ S.top=0;

}

n 順序表的初始化

voidInitList(SeqList

L)

{L.length=0;

}順序棧的基本運(yùn)算判棧空intStackEmpty(SeqStack

*S)

{

if(S.top==0

)

return

1

//判棧空,空則返回1

else

return

0;

//否則返回0}判順序表空intListEmpty(SeqList

L)

{

if(L.length==0

)

return

1

else

return

0;

}順序?；具\(yùn)算——判棧空intStackFull(SeqStack

*S)

{if(S.Top==STACK_SIZE

)

return

1

//判棧滿(mǎn),滿(mǎn)則返回1else

return

0;

//否則返回0}順序?；具\(yùn)算——判棧滿(mǎn)intPush(SeqStackS,StackData

x)

{if(StackFull(S)

)return0;//失敗else：a4a3a2a1a0top{

(S.data[S.top])=x;

(S.top)++;Return

1}}Insert(SeqListS,ListDatax,int

S.length)

順序棧的入棧算法intpop(SeqStackS

){if

(StackEmpty(S))

returnerror;else

{(S.top)--;

return(S.data[s.top]);

}}：a5a4a3a2a1a0topBase順序棧的出棧intGettop(SeqStack

S)

{if(StackEmpty(S)

)

returnerror;else

return

(S.data[s.top-1]);}GetData

(

SeqList

S,

int

S.length-1

);//順序表的取最后一個(gè)元素取棧頂元素定義：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，利用鏈表來(lái)存儲(chǔ)堆棧的數(shù)據(jù)元素。a3a2a1

^棧底top棧頂…...ai…topaia3a2a1 ^棧的鏈?zhǔn)酱鎯?chǔ)——鏈棧typedefint

StackData;typedefstruct

Snode{ListData data;struct

Snode *

next;}

StackNode;Typedef

StackNode *LinkStack;

//鏈表頭指針LinkStack top，p,q; //鏈表頭指針Snodedatanext//定義數(shù)據(jù)類(lèi)型//鏈表結(jié)點(diǎn)//結(jié)點(diǎn)數(shù)據(jù)域//結(jié)點(diǎn)鏈域StackNode是類(lèi)型名…topaia3a2a3 ^鏈棧的類(lèi)型表示voidInitStack(LinkStack

S)

{

top=nil

;

}

鏈棧的初始化intStackEmpty(SeqStack

top){if(top==nil

)return

1

//判?？?空則返回1elsereturn

0;

//否則返回0}判棧滿(mǎn)—只要內(nèi)存最夠大，就不需要鏈棧判?？読nt

push(LinkStack top,int

e){q=(Lstack)malloc(sizeof(lnode));q->data=e;q->next=top;top=q;return1；}qtopbcd ^ae鏈棧的入棧intpop(LinkStack

top){if(top==nil)return

null;else{x=top->data;q=top;top=top->next;free(q);return

x；}}tope^cdq鏈棧的出棧設(shè)入棧順序?yàn)?，2，3，4問(wèn)：將4個(gè)元素全部出棧的情況下，可以得到哪些出棧順序？即：從1到4的共24種排列組合中，哪些組合是可以得到的？提示：并不要求4個(gè)元素全部入棧之后才能出棧趣味練習(xí)隊(duì) 列PART 05定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線(xiàn)性表。§在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱(chēng)為隊(duì)頭(front)?！焯攸c(diǎn)：先進(jìn)先出

(FIFO)出隊(duì)隊(duì)尾a1 , a2 , a3 , a4 , …………an-1

, an隊(duì) 列 示意

圖隊(duì)頭先進(jìn)

先出FIFO入隊(duì)隊(duì)列隊(duì)列的主要運(yùn)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)順序隊(duì)列循環(huán)隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和棧一樣，用順序結(jié)構(gòu)表示隊(duì)列是一種簡(jiǎn)單的方法，通常用一維數(shù)組實(shí)現(xiàn)。用MaxSize表示隊(duì)列允許的最大容量，在隊(duì)的兩端設(shè)置兩個(gè)整型變量作指針，front為頭指針，rear為尾指針。data……frontrear順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)#defineMaxSize 100；typedefintQueueDatatypedef

struct{ QueueDatadata[MaxSize];int front,rear;}Queue；data……frontrear順序隊(duì)列的類(lèi)型表示rearfront6543210e7e6e5e4e3e2e1空隊(duì)列：隊(duì)空的條件是front=rear=-1e1、e2、e3、e4分別入隊(duì)e1、e2出隊(duì)e5、e