第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三線性表的鏈?zhǔn)酱鎯?chǔ)

實(shí)驗(yàn)報(bào)告三 線性表的鏈?zhǔn)酱鎯?chǔ)

班級(jí)： 2010XXX 姓名： HoogLe 學(xué)號(hào)： 2010XXXX 專業(yè)： XXXX

2858505197@qq.com

一、實(shí)驗(yàn)?zāi)康模?/p>

（1）掌握單鏈表的基本操作的實(shí)現(xiàn)方法。（2）掌握循環(huán)單鏈表的基本操作實(shí)現(xiàn)。（3）掌握兩有序鏈表的歸并操作算法。

二、實(shí)驗(yàn)內(nèi)容：（請(qǐng)采用模板類及模板函數(shù)實(shí)現(xiàn)）

1、線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作算法實(shí)現(xiàn)

[實(shí)現(xiàn)提示]（同時(shí)可參見(jiàn)教材p64-p73頁(yè)的ADT描述及算法實(shí)現(xiàn)及ppt）函數(shù)、類名稱等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。也可自行對(duì)類中所定義的操作進(jìn)行擴(kuò)展。所加載的庫(kù)函數(shù)或常量定義： #include using namespace std;（1）單鏈表存儲(chǔ)結(jié)構(gòu)類的定義： template class LinkList{ public: LinkList();//初始化帶頭結(jié)點(diǎn)空單鏈表構(gòu)造函數(shù)實(shí)現(xiàn)

LinkList(T a[],int n);//利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn)

~LinkList();int length();//求單鏈表表長(zhǎng)算法

T get(int i);//獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法

int locate(T temp);void insert(int i,T temp);//在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)位置前插入元素e算法

T Delete(int i);//在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法

void print();//遍歷單鏈表元素算法

bool isEmpty();//判單鏈表表空算法

void deleleAll();//刪除鏈表中所有結(jié)點(diǎn)算法（這里不是析構(gòu)函數(shù)，但功能相同）private: Node *head;};（2）初始化帶頭結(jié)點(diǎn)空單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) 輸入：無(wú)

前置條件：無(wú)

動(dòng)作：初始化一個(gè)帶頭結(jié)點(diǎn)的空鏈表 輸出：無(wú)

后置條件：頭指針指向頭結(jié)點(diǎn)。

//初始化帶頭結(jié)點(diǎn)空單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) template LinkList::LinkList(){ head = new Node;head->next = NULL;}

（３）利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) 輸入：已存儲(chǔ)數(shù)據(jù)的數(shù)組及數(shù)組中元素的個(gè)數(shù) 前置條件：無(wú)

動(dòng)作：利用頭插或尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表 輸出：無(wú)

后置條件：頭指針指向頭結(jié)點(diǎn)，且數(shù)組中的元素為鏈表中各結(jié)點(diǎn)的數(shù)據(jù)成員。//利用數(shù)組初始化帶頭結(jié)點(diǎn)的單鏈表構(gòu)造函數(shù)實(shí)現(xiàn) template LinkList::LinkList(T a[],int n){ head=new Node;head->next=NULL;for(int i=0;i *s=new Node;s->data=a[i];s->next=head->next;head->next=s;} }（４）在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)位置前插入元素e算法 輸入：插入位置i，待插入元素e 前置條件：i的值要合法

動(dòng)作：在帶頭結(jié)點(diǎn)的單鏈表中第i個(gè)位置之前插入元素e 輸出：無(wú)

后置條件：?jiǎn)捂湵碇性黾恿艘粋€(gè)結(jié)點(diǎn)

//在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)位置前插入元素e算法 template void LinkList::insert(int i,T temp){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

Node *s = new Node;

s->data = temp;

s->next = p->next;

p->next = s;} }（５）在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法 輸入：刪除第i個(gè)結(jié)點(diǎn)，待存放刪除結(jié)點(diǎn)值變量e 前置條件：?jiǎn)捂湵聿豢眨琲的值要合法

動(dòng)作：在帶頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的值（由e傳出）。輸出：無(wú)

后置條件：?jiǎn)捂湵碇袦p少了一個(gè)結(jié)點(diǎn)

//在帶頭結(jié)點(diǎn)單鏈表中刪除第i個(gè)元素算法 template T LinkList::Delete(int i){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

Node *s = p->next;

T x= s->data;

p->next = s->next;

return x;} }（６）遍歷單鏈表元素算法 輸入：無(wú)

前置條件：?jiǎn)捂湵聿豢?/p>

動(dòng)作：遍歷輸出單鏈表中的各元素。輸出：無(wú)

后置條件：無(wú)

//遍歷單鏈表元素算法 template void LinkList::print(){ Node *p = head->next;while(p){

cout<

data<<“ ”;

p=p->next;} cout<

（７）求單鏈表表長(zhǎng)算法。輸入：無(wú)

前置條件：無(wú)

動(dòng)作：求單鏈表中元素個(gè)數(shù)。輸出：返回元素個(gè)數(shù) 后置條件：無(wú)

//求單鏈表表長(zhǎng)算法 template int LinkList::length(){ Node *p = head;int count = 0;while(p){

p=p->next;

count++;} return--count;}

（８）判單鏈表表空算法 輸入：無(wú)

前置條件：無(wú)

動(dòng)作：判表是否為空。

輸出：為空時(shí)返回１，不為空時(shí)返回0 后置條件：無(wú) //判斷非空

template bool LinkList::isEmpty(){ Node *p = head->next;if(p)return true;else return false;}

（９）獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法 輸入：無(wú)

前置條件：i不空，i合法 動(dòng)作：找到第i個(gè)結(jié)點(diǎn)。

輸出：返回第i個(gè)結(jié)點(diǎn)的元素值。后置條件：無(wú)

//獲得單鏈表中第i個(gè)結(jié)點(diǎn)的值算法 template T LinkList::get(int i){ Node *p = head;int count = 0;while(p&&count

p=p->next;

count++;} if(p==NULL)cout<<“i不合法，越界!”;else{

return p->data;} }

(10)刪除鏈表中所有結(jié)點(diǎn)算法（這里不是析構(gòu)函數(shù)，但功能相同）輸入：無(wú)

前置條件：?jiǎn)捂湵泶嬖?/p>

動(dòng)作：清除單鏈表中所有的結(jié)點(diǎn)。輸出：無(wú)

后置條件：頭指針指向空 //刪除所有元素 template void LinkList::deleleAll(){ Node *p = head;while(p){

Node *t=p;

p=p->next;

t->next=NULL;} }

(11)上機(jī)實(shí)現(xiàn)以上基本操作，寫出main()程序： 參考p72 void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//測(cè)試帶參數(shù)的構(gòu)造函數(shù)（前端插入！）

LinkList list1(a,10);//測(cè)試插入

if(list1.isEmpty()){ cout<<“鏈表不為空!”<

cout<<“鏈表為空!”<

2、參考單鏈表操作定義與實(shí)現(xiàn)，自行完成單循環(huán)鏈表的類的定義與相操作操作算法。template class LinkList{ public: LinkList(T a[],int n);//利用數(shù)組初始化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn)

void insert(int i,T temp);//在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法

T Delete(int i);//在帶頭結(jié)點(diǎn)單循環(huán)鏈表中刪除第i個(gè)元素算法

void print();//遍歷單循環(huán)鏈表元素算法 private: Node *head;int length;};（１）利用數(shù)組初始化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn) 輸入：已存儲(chǔ)數(shù)據(jù)的數(shù)組及數(shù)組中元素的個(gè)數(shù) 前置條件：無(wú)

動(dòng)作：利用頭插或尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單循環(huán)鏈表 輸出：無(wú)

后置條件：頭指針指向頭結(jié)點(diǎn)，且數(shù)組中的元素為鏈表中各結(jié)點(diǎn)的數(shù)據(jù)成員，尾指針指向頭結(jié)點(diǎn)。

//利用數(shù)組初始化帶頭結(jié)點(diǎn)的單循環(huán)鏈表構(gòu)造函數(shù)實(shí)現(xiàn) template LinkList::LinkList(T a[],int n){ head=new Node;head->next= head;length = 0;for(int i=0;i *s=new Node;s->data=a[i];

s->next = head->next;head->next=s;

length++;} }

（２）在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法 輸入：插入位置i，待插入元素e 前置條件：i的值要合法

動(dòng)作：在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中第i個(gè)位置之前插入元素e 輸出：無(wú)

后置條件：?jiǎn)窝h(huán)鏈表中增加了一個(gè)結(jié)點(diǎn)

//在帶頭結(jié)點(diǎn)單循環(huán)鏈表的第i個(gè)位置前插入元素e算法 template void LinkList::insert(int i,T temp){ cout<length< *p = head;int count = 0;if(i>length)cout<<“i不合法，越界!”;else{

while(count

p=p->next;

count++;

}

Node *s = new Node;

s->data = temp;

s->next = p->next;

p->next = s;} }（３）在帶頭結(jié)點(diǎn)單循環(huán)鏈表中刪除第i個(gè)元素算法 輸入：刪除第i個(gè)結(jié)點(diǎn)，待存放刪除結(jié)點(diǎn)值變量e 前置條件：?jiǎn)窝h(huán)鏈表不空，i的值要合法

動(dòng)作：在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中刪除第i個(gè)結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的值（由e傳出）。輸出：無(wú)

后置條件：?jiǎn)窝h(huán)鏈表中減少了一個(gè)結(jié)點(diǎn)

//在帶頭結(jié)點(diǎn)單循環(huán)鏈表中刪除第i個(gè)元素算法 template T LinkList::Delete(int i){ Node *p = head;int count = 0;

if(i>length)cout<<“i不合法，越界!”<

while(count

p=p->next;

count++;

}

Node *s = p->next;

T x= s->data;

p->next = s->next;

return x;} }

（４）遍歷單循環(huán)鏈表元素算法 輸入：無(wú)

前置條件：?jiǎn)窝h(huán)鏈表不空

動(dòng)作：遍歷輸出單循環(huán)鏈表中的各元素。輸出：無(wú)

后置條件：無(wú)

//遍歷單循環(huán)鏈表元素算法 template void LinkList::print(){ Node *p = head->next;while(p!=head){

cout<

data<<“ ”;

p=p->next;} cout<

(５)上機(jī)實(shí)現(xiàn)以上基本操作，寫出main()程序： void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//測(cè)試帶參數(shù)的構(gòu)造函數(shù)（前端插入?。?/p>

LinkList list1(a,10);list1.print();cout<<“測(cè)試插入”<

３、采用鏈?zhǔn)酱鎯?chǔ)方式，并利用單鏈表類及類中所定義的算法加以實(shí)現(xiàn)線性表La,Lb為非遞減的有序線性表，將其歸并為新線性表Lc，該線性表仍有序（未考慮相同時(shí)刪除一重復(fù)值）的算法。模板函數(shù)：

template void LinkList::addtwo(LinkList La,LinkList Lb){ Node *p1=La.head->next;Node *p2=Lb.head->next;int num=0;while(p1&&p2){

if(p1->data>p2->data)

{

this->insert(++num,p1->data);

p1=p1->next;

}

else{ this->insert(++num,p2->data);

p2=p2->next;

} } if(!p1){

p1=p2;} while(p1){

this->insert(++num,p1->data);

p1=p1->next;}

} void main(){ int a[5]={1,2,5,6,9};int b[5]={0,3,4,7,8};LinkList list1(a,5);LinkList list2(b,5);list1.print();list2.print();LinkList list3;list3.addtwo(list1,list2);list3.print();system(“pause”);} 粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：

選做題：

１、按一元多項(xiàng)式ADT的定義，實(shí)現(xiàn)相關(guān)操作算法： ADT PNode is Data 系數(shù)(coef)指數(shù)(exp)指針域(next):指向下一個(gè)結(jié)點(diǎn) Operation 暫無(wú)

end ADT PNode ADT Polynomial is Data PNode類型的頭指針。Operation

Polynomail 初始化值：無(wú)

動(dòng)作：申請(qǐng)頭結(jié)點(diǎn)，由頭指針指向該頭結(jié)點(diǎn)，并輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式。

DestroyPolyn 輸入：無(wú)

前置條件： 多項(xiàng)式已存在 動(dòng)作：消毀多項(xiàng)式。輸出：無(wú)

后置條件：頭指針指向空

PolyDisplay 輸入：無(wú)

前置條件： 多項(xiàng)式已存在，不為空 動(dòng)作：輸出多項(xiàng)式各項(xiàng)系數(shù)與指數(shù) 輸出：無(wú)

后置條件：無(wú) AddPoly 輸入：另一個(gè)待加的多項(xiàng)式

前置條件：一元多項(xiàng)式pa和pb已存在。動(dòng)作及后置條件：完成多項(xiàng)式相加運(yùn)算，（采用pa=pa+pb形式,并銷毀一元多項(xiàng)式pb）輸出：無(wú)

end ADT Polynomial

２、實(shí)現(xiàn)一元多項(xiàng)式的減法，操作描述如下： SubPoly 輸入：待減的多項(xiàng)式pb 前置條件：一元多項(xiàng)式pa和pb已存在。

動(dòng)作及后置條件：完成多項(xiàng)式減法運(yùn)算，即：pa=pa-pb,并銷毀一元多項(xiàng)式pb。輸出：無(wú)

３、參考P74-P79頁(yè)雙向鏈表的存儲(chǔ)結(jié)構(gòu)定義及算法，編程實(shí)現(xiàn)雙向鏈表的插入算法和刪除算法。

三、心得體會(huì)：（含上機(jī)中所遇問(wèn)題的解決辦法，所使用到的編程技巧、創(chuàng)新點(diǎn)及編程的心得）

第二篇：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告

課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法分析 實(shí)驗(yàn)名稱：鏈表的實(shí)現(xiàn)與應(yīng)用

實(shí)驗(yàn)日期：2015.01.30 班級(jí)： 數(shù)媒1401 姓名： 范業(yè)嘉 學(xué)號(hào) 1030514108

一、實(shí)驗(yàn)?zāi)康?/p>

掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)與基本操作的實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容與要求

⑴定義線性表的鏈?zhǔn)酱鎯?chǔ)表示；

⑵基于所設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本操作；

⑶編寫一個(gè)主程序?qū)λ鶎?shí)現(xiàn)的線性表進(jìn)行測(cè)試；

⑷線性表的應(yīng)用：①設(shè)線性表L1和L2分別代表集合A和B，試設(shè)計(jì)算法求A和B的并集C，并用

線性表L3代表集合C；②（選做）設(shè)線性表L1和L2中的數(shù)據(jù)元素為整數(shù)，且均已按值非遞減有序排列，試設(shè)計(jì)算法對(duì)L1和L2進(jìn)行合并，用線性表L3保存合并結(jié)果，要求L3中的數(shù)據(jù)元素也按值非遞減有序排列。

⑸設(shè)計(jì)一個(gè)一元多項(xiàng)式計(jì)算器，要求能夠：①輸入并建立多項(xiàng)式；②輸出多項(xiàng)式；③執(zhí)行兩個(gè)多項(xiàng)式相加；④執(zhí)行兩個(gè)多項(xiàng)式相減；⑤（選做）執(zhí)行兩個(gè)多項(xiàng)式相乘。

三、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1.按所用指針的類型、個(gè)數(shù)、方法等的不同，又可分為：

線性鏈表（單鏈表）

靜態(tài)鏈表

循環(huán)鏈表

雙向鏈表

雙向循環(huán)鏈表

2.用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中數(shù)據(jù)元素，用指針來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。

四、算法設(shè)計(jì)

1.定義一個(gè)鏈表

void creatlist(Linklist &L,int n){ int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i

s=(Linklist)malloc(sizeof(Lnode));

scanf(“%d”,&s->data);

s->next=NULL;

p->next=s;

p=s;

/ 8

} } 2.（1）兩個(gè)鏈表的合并

void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc){ Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){

if(pa->data<=pb->data)

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

else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb;free(Lb);}（2）兩個(gè)鏈表的并集

Linklist unionlist(Linklist &La,Linklist &Lb){ Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){

flag=0;

p2=Lb->next;

while(p2)

{

if(p1->data==p2->data)

{

flag=1;

break;

}

p2=p2->next;

}

if(flag==0)

{

s=(Linklist)malloc(sizeof(Lnode));

s->data=p1->data;

q->next=s;

q=s;

}

p1=p1->next;/ 8

}

q->next=Lb->next;return head;

}

3.（1）一元多項(xiàng)式的加法

List addpoly(List pa,List pb)

//一元多項(xiàng)式的加法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){

if(pa->expn>pb->expn)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;

}

else if(pa->expn

expn)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;

}

else

{

n=pa->coef+pb->coef;

if(n!=0)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;/ 8

s->coef=n;

s->next=NULL;

p->next=s;

p=s;

}

pb=pb->next;

pa=pa->next;

} } while(pa!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;} while(pb!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} return pc;}

（2）一元多項(xiàng)式的減法

List subpoly(List pa,List pb)

//一元多項(xiàng)式的減法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){

if(pa->expn>pb->expn)

/ 8

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=pa->coef;

s->next=NULL;

p->next=s;

p=s;

pa=pa->next;} else if(pa->expn

expn){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=-pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} else {

n=pa->coef-pb->coef;

if(n!=0)

{

s=(List)malloc(sizeof(struct Linklist));

s->expn=pa->expn;

s->coef=n;

s->next=NULL;

p->next=s;

p=s;

}

pb=pb->next;

pa=pa->next;} } while(pa!=NULL){ s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;} / 8

while(pb!=NULL){

s=(List)malloc(sizeof(struct Linklist));

s->expn=pb->expn;

s->coef=-pb->coef;

s->next=NULL;

p->next=s;

p=s;

pb=pb->next;} return pc;}（3）一元多項(xiàng)式的乘法

void mulpolyn(polynomail pa,polynomail pb,polynomail &pc){

LNode *p,*q,*s,*hc;p=pa->next;q=pb->next;hc=pc;while(p!=NULL){

while(q!=NULL)

{

s=(polynomail)malloc(sizeof(LNode));

hc->next=s;

hc=hc->next;

hc->coef=q->coef*p->coef;

hc->expn=q->expn+p->expn;

q=q->next;

}

p=p->next;

q=pb->next;} hc->next=NULL;}

/ 8

五、測(cè)試結(jié)果

2.3.7 / 8

六、心得體會(huì)（包括對(duì)于本次實(shí)驗(yàn)的小結(jié)，實(shí)驗(yàn)過(guò)程中碰到的問(wèn)題等）

1.首先書(shū)上給的鏈表輸入是倒序的，寫的時(shí)候想都沒(méi)想就抄上去了，結(jié)果運(yùn)行時(shí)發(fā)現(xiàn)問(wèn)題，可是上網(wǎng)百度依然沒(méi)有把問(wèn)題解決，導(dǎo)致最后輸出鏈表倒序的，并且鏈表的合并并集依舊是倒序的。

2.當(dāng)寫一元多項(xiàng)式的加減時(shí)，前提是弄清楚各種情況，系數(shù)相同時(shí)就相加減，系數(shù)不同就保留原有多項(xiàng)式；當(dāng)系數(shù)相加減為0時(shí)，就free這個(gè)節(jié)點(diǎn)。在做減法時(shí)，我考慮到了減數(shù)與被減數(shù)之間的關(guān)系。

3.在做多項(xiàng)式時(shí)，我準(zhǔn)備按照書(shū)上的算法一個(gè)一個(gè)寫小函數(shù)，結(jié)果到最后發(fā)現(xiàn)寫不下去了，就去問(wèn)問(wèn)同學(xué)和上網(wǎng)看看，結(jié)果感覺(jué)寫這個(gè)數(shù)據(jù)結(jié)構(gòu)的程序其實(shí)不必想麻煩了，只是指針，數(shù)組的高級(jí)運(yùn)用。

/ 8

第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二線性表的順序存儲(chǔ)

實(shí)驗(yàn)報(bào)告二 線性表的順序存儲(chǔ)

班級(jí)： 2010XXX 姓名： HoogLe 學(xué)號(hào)： 2010XXXX 專業(yè)： XXXX

2858505197@qq.com

一、實(shí)驗(yàn)?zāi)康模?/p>

（1）掌握順序表的基本操作的實(shí)現(xiàn)方法。

（2）應(yīng)用順序表的基本算法實(shí)現(xiàn)集合A=AUB算法。

（3）應(yīng)用順序表的基本算法實(shí)現(xiàn)兩有序順序表的歸并算法。

二、實(shí)驗(yàn)內(nèi)容：

1、線性表順序存儲(chǔ)結(jié)構(gòu)的基本操作算法實(shí)現(xiàn)（要求采用類模板實(shí)現(xiàn)）

[實(shí)現(xiàn)提示]（同時(shí)可參見(jiàn)教材p5822-p60頁(yè)算法、ppt）函數(shù)、類名稱等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。庫(kù)函數(shù)載和常量定義：（代碼）#include using namespace std;const int MaxSize=100;

（1）順序表存儲(chǔ)結(jié)構(gòu)的定義(類的聲明)：（代碼）

template //定義模板類SeqList class SeqList { public: SeqList();//無(wú)參構(gòu)造函數(shù)

SeqList(datatype a[ ], int n);//有參構(gòu)造函數(shù) ~SeqList(){};//析構(gòu)函數(shù)為空 int Length();//求線性表的長(zhǎng)度

datatype Get(int i);//按位查找，取線性表的第i個(gè)元素 int Locate(datatype item);//查找元素item void Insert(int i, datatype item);//在第i個(gè)位置插入元素item datatype Delete(int i);//刪除線性表的第i個(gè)元素 void display();//遍歷線性表，按序號(hào)依次輸出各元素 private: datatype data[MaxSize];//存放數(shù)據(jù)元素的數(shù)組 int length;//線性表的長(zhǎng)度 };

（2）初始化順序表算法實(shí)現(xiàn)（不帶參數(shù)的構(gòu)造函數(shù)）/* *輸 入：無(wú)

*前置條件：順序表不存在 *功 能：構(gòu)建一個(gè)順序表 *輸 出：無(wú)

*后置條件：表長(zhǎng)為0 */ 實(shí)現(xiàn)代碼：

template SeqList:: SeqList(){ length=0;}

（3）順序表的建立算法（帶參數(shù)的構(gòu)造函數(shù)）

/* *輸 入：順序表信息的數(shù)組形式a[],順序表長(zhǎng)度n *前置條件：順序表不存在

*功 能：將數(shù)組a[]中元素建為長(zhǎng)度為n的順序表 *輸 出：無(wú)

*后置條件：構(gòu)建一個(gè)順序表 */ 實(shí)現(xiàn)代碼：

template SeqList:: SeqList(datatype a[], int n){ if(n>MaxSize){

cout<<“數(shù)組元素個(gè)數(shù)不合法”<

data[i]=a[i];length=n;}（4）在順序表的第i個(gè)位置前插入元素e算法 /* *輸 入：插入元素e,插入位置i *前置條件：順序表存在，i要合法

*功 能：將元素e插入到順序表中位置i處 *輸 出：無(wú)

*后置條件：順序表插入新元素，表長(zhǎng)加1 */ 實(shí)現(xiàn)代碼：

template void SeqList::Insert(int i, datatype item){ int j;if(length>=MaxSize){

cout<<“溢出”<length+1){

cout<<“i不合法！”<=i;j--)

data[j]=data[j-1];data[i-1]=item;length++;}（5）刪除線性表中第i個(gè)元素算法 /* *輸 入：要?jiǎng)h除元素位置i *前置條件：順序表存在,i要合法

*功 能：刪除順序表中位置為i的元素 *輸 出：無(wú)

*后置條件： 順序表冊(cè)除了一個(gè)元素，表長(zhǎng)減1 */ 實(shí)現(xiàn)代碼：

template datatype SeqList::Delete(int i){ int item,j;if(length==0){

cout<<“表為空,無(wú)法刪除元素!”<length){

cout<<“i不合法!”<

for(j=i;j

data[j-1]=data[j];//注意數(shù)組下標(biāo)從0記

length--;return item;}（6）遍歷線性表元素算法 /* *輸 入：無(wú)

*前置條件：順序表存在 *功 能：順序表遍歷 *輸 出：輸出所有元素 *后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template void SeqList::display(){ if(length==0){

cout<<“表為空，無(wú)法輸出!”<

cout<

（7）獲得線性表長(zhǎng)度算法 /* *輸 入：無(wú)

*前置條件：順序表存在 *功 能：輸出順序表長(zhǎng)度 *輸 出：順序表長(zhǎng)度 *后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template int SeqList::Length(){ return Length;}

（8）在順序線性表中查找e值，返回該元素的位序算法 /* *輸 入：查詢?cè)刂礶 *前置條件：順序表存在

*功 能：按值查找值的元素并輸出位置 *輸 出：查詢?cè)氐奈恢?*后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template int SeqList::Locate(datatype item){ for(int i=0;i

//下標(biāo)為i的元素等于item，返回其序號(hào)i+1

return 0;//查找失敗 }

（9）獲得順序線性表第i個(gè)元素的值 /* *輸 入：查詢?cè)匚恢胕 *前置條件：順序表存在，i要合法

*功 能：按位查找位置為i的元素并輸出值 *輸 出：查詢?cè)氐闹?*后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template datatype SeqList::Get(int i){ if(i<0||i>length){

cout<<“i不合法!”<

（10）判表空算法 /* *輸 入：無(wú) *前置條件：無(wú)

*功 能：判表是否為空

*輸 出：為空返回1，不為空返回0 *后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template bool SeqList::Empty(){ if(length==0){

return 1;} else {

return 0;} }

(11)求直接前驅(qū)結(jié)點(diǎn)算法 /* *輸 入：要查找的元素e，待存放前驅(qū)結(jié)點(diǎn)值e1

*前置條件：無(wú)

*功 能：查找該元素的所在位置，獲得其前驅(qū)所在位置。*輸 出：返回其前驅(qū)結(jié)點(diǎn)的位序。*后置條件：e1值為前驅(qū)結(jié)點(diǎn)的值 */ 實(shí)現(xiàn)代碼：

template int SeqList::Pre(datatype item){ int k=Locate(item)-1;if(k>0)

return k;else {

cout<<“無(wú)前驅(qū)結(jié)點(diǎn)！”<

return 0;} }(12)求直接后繼結(jié)點(diǎn)算法 /* *輸 入：要查找的元素e，待存放后繼結(jié)點(diǎn)值e1 *前置條件：無(wú)

*功 能：查找該元素的所在位置，獲得其后繼所在位置。*輸 出：返回其后繼結(jié)點(diǎn)的位序。*后置條件：e1值為后繼結(jié)點(diǎn)的值 */ 實(shí)現(xiàn)代碼：

template int SeqList::Suc(datatype item){ int k=Locate(item)+1;if(k>length){

cout<<“無(wú)后繼結(jié)點(diǎn)!”<

return k;} }

上機(jī)實(shí)現(xiàn)以上基本操作，寫出main()程序： void main(){ SeqList Seq;//創(chuàng)建

if(Seq.Empty()){

cout<<“線性表為空!”<

} Seq.Insert(1,1);Seq.Insert(2,2);Seq.Insert(3,3);Seq.Insert(4,4);Seq.Insert(5,5);//插入元素操作

cout<<“輸出插入的五個(gè)元素:”<

cout<

cout<<“2是第”<

cout<<“第五個(gè)元素是:”<

cout<<“線性表的長(zhǎng)度為:”<

Seq.Delete(3);//刪除元素

cout<<“刪除第三個(gè)元素后的線性表為:”<

cout<

cout<<“元素2前驅(qū)結(jié)點(diǎn)的數(shù)值為：”<

cout<<“元素4后繼結(jié)點(diǎn)的位置為：”<

cout<<“元素4后繼結(jié)點(diǎn)的數(shù)值為：”<

要求對(duì)每個(gè)算法都加以測(cè)試，判斷是否正確；并測(cè)試不同類型數(shù)據(jù)的操作。粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：

2、用以上基本操作算法，實(shí)現(xiàn)A=AUB算法。（利用函數(shù)模板實(shí)現(xiàn)）/* *輸 入：集合A,集合B *前置條件：無(wú)

*功 能：實(shí)現(xiàn)A=AUB *輸 出：無(wú)

*后置條件：A中添加了B中的元素。*/

實(shí)現(xiàn)代碼：

template SeqList SeqList::Add(SeqList& item){ if(item.Empty())

return *this;else {

int k=item.Length();

int num=this->Length();

for(int i=1;i<=k;i++)

{

for(int j=0;j

if(data[j]==item.Get(i))

{

break;

}

else if(num-1==j&&data[num-1]!=item.Get(i))

{

this->Insert(++num,item.Get(i));

}

}

return *this;} } void main(){ SeqList A,B;cout<<“A∪B的結(jié)果是:”<

B.Insert(1,2);B.Insert(2,6);B.Insert(3,1);B.Insert(4,8);B.Insert(5,9);//插入集合B中元素

A.Add(B);A.display();cout<

3、對(duì)以上順序表類中的基本操作算法適當(dāng)加以補(bǔ)充，實(shí)現(xiàn)向一個(gè)有序的（非遞減）的順序表中插入數(shù)據(jù)元素e算法。/* *輸 入：插入元素e *前置條件：順序表已有序

*功 能：將元素e插入到順序表中適當(dāng)?shù)奈恢?，使順序表依然有?*輸 出： 無(wú)

*后置條件：有序順序表插入了新元素，且表長(zhǎng)加1。*/ 實(shí)現(xiàn)代碼：

template void SeqList::orderInsert(datatype item){ int num=this->Length();for(int i=0;i

if((data[i]item))

{

for(int k=num;k>i;k--)

data[k]=data[k-1];

data[i+1]=item;

length++;

break;

}

if(data[i]>item)

{

for(int k=num;k>i;k--)

data[k]=data[k-1];

data[i]=item;

length++;

break;

} } } void main(){ SeqList A,B;A.Insert(1,3);A.Insert(2,5);A.Insert(3,6);A.Insert(4,8);A.Insert(5,10);//插入順序表

cout<<“原順序表為:”<

cout<

cout<<“插入新元素后的順序表為:”<

4、算法實(shí)現(xiàn)：La,Lb為非遞減的有序線性表，將其歸并為L(zhǎng)c，該線性表仍有序（未考慮相同時(shí)刪除一重復(fù)值）（利用函數(shù)類板實(shí)現(xiàn)）MergeList： /* *輸 入：有序線性表La,有序線性表Lb *前置條件：順序表已有序

*功 能：將兩線性表歸并，不去掉相同元素 *輸 出： 返回一個(gè)新的有序線性表Lc *后置條件：無(wú) */ 實(shí)現(xiàn)代碼：

template SeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2){ int num=Seq2.Length();for(int i=0;i<=num;i++){

Seq1.orderInsert(Seq2.Get(i));} return Seq1;} void main(){ SeqList La,Lb,Lc;La.Insert(1,2);La.Insert(2,4);La.Insert(3,6);La.Insert(4,8);//插入La cout<<“La中元素為:”<

cout<<“合并后的Lc為:”<

cout<

粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：

三、心得體會(huì)：（含上機(jī)中所遇問(wèn)題的解決辦法，所使用到的編程技巧、創(chuàng)新點(diǎn)及編程的心得）

第四篇：數(shù)據(jù)結(jié)構(gòu)線性表實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告

課程名：數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)名：線性表及其操作 姓名： 班級(jí)： 學(xué)號(hào)：

撰寫時(shí)間：2014.09.24

一 實(shí)驗(yàn)?zāi)康呐c要求

1.掌握線性表的實(shí)現(xiàn)

2.掌握線性表的基本操作的實(shí)現(xiàn)

二 實(shí)驗(yàn)內(nèi)容

? 分別完成線性表的順序表示及鏈?zhǔn)奖硎?/p>

? 在兩種表示上, 分別實(shí)現(xiàn)一些線性表的操作, 至少應(yīng)該包括 – 在第i個(gè)位置插入一個(gè)元素 – 刪除第i個(gè)元素 – 返回線性表長(zhǎng)

– 返回第i個(gè)元素的值

三 實(shí)驗(yàn)結(jié)果與分析

#include #include //---------線性表鏈?zhǔn)奖硎?----------struct V//聲明一個(gè)結(jié)構(gòu)體類型struct V { int value;struct V * next;//定義結(jié)構(gòu)體變量 };void PrintLink(struct V*p)//定義一個(gè)結(jié)構(gòu)體指針 { while(p!=NULL)//只要指針指向的變量不為NULL；就會(huì)一直循環(huán)鏈表指向下一個(gè)結(jié)構(gòu)體

{

printf(“%d, ”,(*p).value);

p=(*p).next;//指針指向下一個(gè)結(jié)構(gòu)體

} printf(“n”);} void Link(){

struct V*head;head=(struct V*)malloc(sizeof(struct V));//開(kāi)辟一個(gè)長(zhǎng)度為size的內(nèi)存

(*head).value=-100;//表頭為-100(*head).next=NULL;printf(“------------線性表鏈?zhǔn)奖硎?-----------n”);

int i,n=10;struct V*p=head;printf(“10個(gè)數(shù)據(jù):n”);for(i=0;i

(*p).next=(struct V*)malloc(sizeof(struct V));

p=(*p).next;

(*p).value=2*i;

(*p).next=NULL;} PrintLink(head);//調(diào)用PrintLink函數(shù)

printf(“刪除第四個(gè)數(shù)據(jù):n”);int k=4;p=head;for(i=1;i

p=(*p).next;} struct V*temp=(*p).next;//k表示插入和刪除的位置

(*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十個(gè)數(shù)據(jù):n”);

k=10;p=head;for(i=1;i

p=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);}

//---------線性表順序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------輸出數(shù)組元素------------printf(“-------------線性表順序表示---------n”);for(i=0;i

a[i]=i;} printf(“數(shù)組元素為:n”);for(i=0;i

printf(“%3d”,a[i]);} printf(“n”);//--------插入一個(gè)數(shù)組元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i

if(i

{

b[i]=a[i];

}

else if(i==k)

{b[i]=j;}

else

{b[i]=a[i-1];} } printf(“輸出插入一個(gè)元素的數(shù)組:n”);for(i=0;i

{

if(i

{c[i]=a[i];}

else

{c[i]=a[i+1];} } printf(“輸出刪除一個(gè)元素的數(shù)組:n”);for(i=0;i

printf(“數(shù)組元素為:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k位置插入一個(gè)元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);

} int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;}

圖1：實(shí)驗(yàn)結(jié)果截圖

實(shí)驗(yàn)分析：已在程序中按規(guī)定格式標(biāo)注。

第五篇：福州大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-線性表

數(shù)據(jù)結(jié)構(gòu)原理實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：

姓名：

線性表

一、問(wèn)題描述 1.實(shí)現(xiàn)ADT表

2.設(shè)表的Reverse運(yùn)算將表中元素的次序反轉(zhuǎn)。擴(kuò)充用數(shù)組實(shí)現(xiàn)表的結(jié)構(gòu)List，增加函數(shù)Reverse(L)，將表L中元素的次序反轉(zhuǎn)，并要求就地實(shí)現(xiàn)Reverse運(yùn)算。

二、算法描述

從i=0開(kāi)始，將表中第N個(gè)元素與N-i-1個(gè)元素調(diào)換即可

三、核心代碼

void ReverseList(List L){

ListItem tmp;int i;for(i=0;in/2;i++){

} tmp = L->table[i];L->table[i] = L->table[L->n-1-i];L->table[L->n-1-i] = tmp;}

四、運(yùn)行結(jié)果