第一篇：實(shí)驗(yàn)一線性表的創(chuàng)建與訪問算法設(shè)計(jì)
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
四、編譯程序：
#include
typedef char ElemType;typedef struct LNode
//定義單鏈表結(jié)點(diǎn)類型 {
ElemType data;
struct LNode *next;}LinkList;
LinkList *CreatlinkR(LinkList *L)
//用尾插法建立帶頭結(jié)點(diǎn)的單鏈表 {
LinkList *s, *r;char ch;r =(LinkList *)malloc(sizeof(LinkList));
//創(chuàng)建頭結(jié)點(diǎn)
L = r;s = r;r->next = NULL;printf(“單鏈表元素值為單個(gè)字符, 連續(xù)輸入，$為結(jié)束字符:”);while((ch = getchar())!= '$'){
r =(LinkList *)malloc(sizeof(LinkList));
//創(chuàng)建新結(jié)點(diǎn)
r->data = ch;
r->next = NULL;
s->next = r;
s = r;
} r->next=NULL;
//終端結(jié)點(diǎn)
return(L);}
void Sort(LinkList *h)
//單鏈表元素排序 { LinkList *p=h->next,*q,*t;
if(p!=NULL){
t=p->next;
p->next=NULL;
p=t;
while(p!=NULL)
{
t=p->next;
q=h;
第 頁
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
while(q->next!=NULL&&q->next->data
data)
q=q->next;
//在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q
p->next=q->next;
//將*p插到*q之后
q->next=p;
p=t;
} } }
void DispList(LinkList *L)
//輸出單鏈表L {
LinkList *p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);
p=p->next;} }
LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)
{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;while(pa!=NULL&&pb!=NULL){
if(pa->data
data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
tc->next=s;
tc=s;
pb=pb->next;
}
else
{
第 頁
//求兩有序集合的并集 //復(fù)制結(jié)點(diǎn)
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
//重復(fù)元素只復(fù)制一個(gè)
pb=pb->next;
} } if(pb!=NULL)
//復(fù)制余下結(jié)點(diǎn)
pa=pb;while(pa!=NULL){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
} tc->next=NULL;return(Lc);}
LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)
//求兩有序集合的交集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(pb!=NULL&&pb->data==pa->data)
//若pa結(jié)點(diǎn)值在pb中
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;}
tc->next=NULL;return(Lc);
第 頁
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
}
LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)
//求兩有序集合的差集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(!(pb!=NULL&&pb->data==pa->data))
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;} tc->next=NULL;return(Lc);}
void main(){
LinkList *La,*Lb,*Lc;
int num=0,loop,j;loop=1;La=CreatlinkR(La);Lb=CreatlinkR(Lb);Sort(La);Sort(Lb);
printf(“有序集合A＝{ ”);
DispList(La);
printf(“}n”);
printf(“有序集合B＝{ ”);
DispList(Lb);printf(“}n”);while(loop){
printf(“請選擇您要執(zhí)行的操作：1.求并集
scanf(”%d“,&j);printf(”n%d“,j);
第 頁
//若pa結(jié)點(diǎn)值不在pb中 2.求交集
3.求差集n”);
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
if(j>=1&&j<=3)
switch(j)
{
case 1: Lc=Union(La,La,Lc);
printf(“集合A與集合B的并集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 2: Lc=InsterSect(La,Lb,Lc);
printf(“集合A與集合B的交集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 3: Lc=Subs(La,Lb,Lc);
printf(“集合A與集合B的差集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
} printf(“0.結(jié)束
1.繼續(xù)n”);scanf(“%d”,&loop);printf(“n”);} }
五、運(yùn)行結(jié)果：
1．輸入兩個(gè)無序集合，排序后輸出：
第 頁
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
2．求集合的并集：
3．選1繼續(xù)：
第 頁
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
4．求集合的交集：
5．求集合的差集：
第 頁
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
6．選0結(jié)束：
第 頁
第二篇：二叉樹的創(chuàng)建與訪問算法設(shè)計(jì)
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
實(shí) 驗(yàn) 報(bào) 告
課程名稱： 數(shù)據(jù)結(jié)構(gòu)（C語言版）實(shí)驗(yàn)名稱： 二叉樹的創(chuàng)建與訪問算法設(shè)計(jì) 實(shí)驗(yàn)類型： 驗(yàn)證性□ 綜合性□ 設(shè)計(jì)性□ 實(shí)驗(yàn)室名稱： c機(jī)房 班級：xxxxxxxxx 學(xué)號： xxxxxxxxxxxxxxx 姓名： xxx 組別： 同組人：
成績：
實(shí)驗(yàn)日期： 2011年 6月
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
預(yù)習(xí)報(bào)告成績： 指導(dǎo)教師審核（簽名）： 2011年 月 日
預(yù)習(xí)報(bào)告
一.實(shí)驗(yàn)?zāi)康?/p>
本實(shí)驗(yàn)以二叉樹的創(chuàng)建與訪問算法設(shè)計(jì)作為實(shí)驗(yàn)內(nèi)容，掌握樹型結(jié)構(gòu)的實(shí)現(xiàn)方法，培養(yǎng)解決負(fù)責(zé)問題的能力。
二.實(shí)驗(yàn)內(nèi)容
1、編寫生成二叉樹的函數(shù)，二叉樹的元素從鍵盤輸入；
2、編寫在二叉樹中插入元素的函數(shù)；
3、編寫在二叉樹中刪除元素的函數(shù)；
4、編寫遍歷并輸出二叉樹的函數(shù)。
方案一采用遞歸算法實(shí)現(xiàn)二叉樹遍歷算法。方案二采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷算法。三.實(shí)驗(yàn)要求
1、掌握樹型結(jié)構(gòu)的機(jī)器內(nèi)表示；
2、掌握樹型結(jié)構(gòu)之上的算法設(shè)計(jì)與實(shí)現(xiàn)；
3、列表對比分析兩種數(shù)據(jù)結(jié)構(gòu)的相應(yīng)操作的時(shí)間復(fù)雜度、空間復(fù)雜度，闡明產(chǎn)生差異的原因。四.問題描述
從鍵盤輸入二叉樹的元素，建立二叉樹，實(shí)現(xiàn)二叉樹的遍歷算法。
五.基本要求
實(shí)現(xiàn)以下基本操作：
（1）從鍵盤輸入二叉樹的元素，建立二叉樹。（2）實(shí)現(xiàn)二叉樹的先序遍歷算法。
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
實(shí)驗(yàn)報(bào)告成績： 指導(dǎo)教師審核（簽名）： 2011年 月 日
實(shí)驗(yàn)報(bào)告
一 程序清單
#include “stdio.h” #include “string.h” #include
typedef struct BiTNode{ char data;
struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();if(ch=='#')T=NULL;else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))printf(“Error!”);T->data=ch;
T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}
return T;}
int Depth(BiTree T){
int dep=0,depl,depr;if(!T)dep=0;else {
depl=Depth(T->lchild);depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);}
return dep;}
void main(){ BiTree T;int dep;printf(“請輸入您要?jiǎng)?chuàng)建的二叉樹！!n
'#'表示空元素！n”);T=Create(T);
printf(“nn您要求的二叉樹的深度：”);dep=Depth(T);
printf(“%dnn”,dep);} }
內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院
二 測試結(jié)果
三 調(diào)試程序出現(xiàn)的問題及解決的方法
編程中出現(xiàn)很多的編譯錯(cuò)誤，主要采用對每個(gè)函數(shù)調(diào)試，設(shè)斷點(diǎn)，運(yùn)用自己的程序中，讓我更好的掌握了遞歸算法。四 實(shí)驗(yàn)心得體會
通過這次試驗(yàn)，讓我鞏固了鏈?zhǔn)酱鎯Y(jié)構(gòu)和遞歸算法的使用，用模塊化思路設(shè)計(jì)程序，編寫程序要小心謹(jǐn)慎，要細(xì)化到每個(gè)函數(shù)，通過多次調(diào)試，才使得整個(gè)程序正確運(yùn)行，達(dá)到預(yù)期結(jié)果。
第三篇：算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)
金陵科技學(xué)院實(shí)驗(yàn)報(bào)告
學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊
課程名稱：
學(xué)生學(xué)號：
所屬院部：
（理工類）
算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級： 13網(wǎng)絡(luò)工程
1305106009 學(xué)生姓名： 陳韜
網(wǎng)絡(luò)與通信工程學(xué)院 指導(dǎo)教師： 沈奇 14 ——20 15 學(xué)年 第 1 學(xué)期
金陵科技學(xué)院教務(wù)處制
金陵科技學(xué)院實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)報(bào)告書寫要求
實(shí)驗(yàn)報(bào)告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點(diǎn)需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。
實(shí)驗(yàn)報(bào)告書寫說明
實(shí)驗(yàn)報(bào)告中一至四項(xiàng)內(nèi)容為必填項(xiàng)，包括實(shí)驗(yàn)?zāi)康暮鸵?；?shí)驗(yàn)儀器和設(shè)備；實(shí)驗(yàn)內(nèi)容與過程；實(shí)驗(yàn)結(jié)果與分析。各院部可根據(jù)學(xué)科特點(diǎn)和實(shí)驗(yàn)具體要求增加項(xiàng)目。
填寫注意事項(xiàng)
（1）細(xì)致觀察，及時(shí)、準(zhǔn)確、如實(shí)記錄。（2）準(zhǔn)確說明，層次清晰。
（3）盡量采用專用術(shù)語來說明事物。
（4）外文、符號、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號。（5）應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。
實(shí)驗(yàn)報(bào)告批改說明
實(shí)驗(yàn)報(bào)告的批改要及時(shí)、認(rèn)真、仔細(xì)，一律用紅色筆批改。實(shí)驗(yàn)報(bào)告的批改成績采用百分制，具體評分標(biāo)準(zhǔn)由各院部自行制定。
實(shí)驗(yàn)報(bào)告裝訂要求
實(shí)驗(yàn)批改完畢后，任課老師將每門課程的每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)報(bào)告以自然班為單位、按學(xué)號升序排列，裝訂成冊，并附上一份該門課程的實(shí)驗(yàn)大綱。
金陵科技學(xué)院實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)項(xiàng)目名稱： 順序表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間：
金陵科技學(xué)院實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)1 順序表
一、實(shí)驗(yàn)?zāi)康暮鸵?/p>
掌握順序表的定位、插入、刪除等操作。
二、實(shí)驗(yàn)儀器和設(shè)備
Turbo C 2.0/ Visual C++
三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖）
1、必做題
（1）編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。
（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。編寫主函數(shù)測試結(jié)果。（3）在遞增有序的順序表中插入一個(gè)新結(jié)點(diǎn)x，保持順序表的有序性。
解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；從第一個(gè)元素開始找到第一個(gè)大于該新結(jié)點(diǎn)值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個(gè)位置直至元素i；最后將新結(jié)點(diǎn)x插入到i位置。
（4）刪除順序表中所有等于X的數(shù)據(jù)元素。
2、選做題
（5）已知兩個(gè)順序表A和B按元素值遞增有序排列，要求寫一算法實(shí)現(xiàn)將A和B歸并成一個(gè)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。
程序清單：
#include
金陵科技學(xué)院實(shí)驗(yàn)報(bào)告
} sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 單鏈表 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)2 單鏈表 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> 1、實(shí)驗(yàn)?zāi)康?/p> 掌握單鏈表的定位、插入、刪除等操作。 2、實(shí)驗(yàn)要求 （1）注意鏈表的空間是動態(tài)分配的，某結(jié)點(diǎn)不用之后要及時(shí)進(jìn)行物理刪除，以便釋放其內(nèi)存空間。 （2）鏈表不能實(shí)現(xiàn)直接定位，一定注意指針的保存，防止丟失。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個(gè)單鏈表，并逐個(gè)輸出單鏈表中所有數(shù)據(jù)元素。（2）在遞增有序的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，保持單鏈表的有序性。 解題思路：首先查找插入的位置然后進(jìn)行插入操作；從第一個(gè)結(jié)點(diǎn)開始找到第一個(gè)大于該新結(jié)點(diǎn)值的結(jié)點(diǎn)即為插入位置；然后在找到的此結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；注意保留插入位置之前結(jié)點(diǎn)的指針才能完成插入操作。 （3）編寫實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。 2、選做題 已知指針LA和LB分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表的首元結(jié)點(diǎn)。要求編一算法實(shí)現(xiàn)，從表LA中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表LB中第j個(gè)元素之前。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 堆棧和隊(duì)列 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)3 堆棧和隊(duì)列 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。 （3）掌握隊(duì)列的存儲結(jié)構(gòu)及基本操作實(shí)現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）判斷一個(gè)算術(shù)表達(dá)式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。 （3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個(gè)算法判別讀入的一個(gè)以’@’為結(jié)束符的字符序列是否是“回文”。 2、選做題 在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)輸出受限的雙端循環(huán)隊(duì)列的入列和出列算法。設(shè)每個(gè)元素表示一個(gè)待處理的作業(yè)，元素值表示作業(yè)的預(yù)計(jì)時(shí)間。入隊(duì)列采取簡化的短作業(yè)優(yōu)先原則，若一個(gè)新提交的作業(yè)的預(yù)計(jì)執(zhí)行時(shí)間小于隊(duì)頭和隊(duì)尾作業(yè)的平均時(shí)間，則插入在隊(duì)頭，否則插入在隊(duì)尾。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 串 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)4 串 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> 掌握串的存儲及應(yīng)用。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫輸出字符串s中值等于字符ch的第一個(gè)字符的函數(shù)，并用主函數(shù)測試結(jié)果。 （2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。 解題思路：可以將第一題程序改進(jìn)成一個(gè)子函數(shù)，在本題中循環(huán)調(diào)用。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實(shí)現(xiàn)將串S插入到串T中某個(gè)字符之后，若串T中不存在這個(gè)字符，則將串S聯(lián)接在串T的末尾。 提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計(jì)為從鍵盤輸入。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 二叉樹 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)5 二叉樹 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）建立一棵二叉樹。對此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 （2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點(diǎn)總數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結(jié)點(diǎn)的值。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。 解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹順序存儲的一個(gè)重要性質(zhì)為，第i個(gè)結(jié)點(diǎn)的左孩子是編號為2i的結(jié)點(diǎn)，第i個(gè)結(jié)點(diǎn)的右孩子是編號為2i+1的結(jié)點(diǎn)。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 圖 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)6 圖 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）熟練掌握圖的基本概念、構(gòu)造及其存儲結(jié)構(gòu)。 （2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）構(gòu)造一個(gè)無向圖（用鄰接矩陣表示存儲結(jié)構(gòu)）。 （2）對上面所構(gòu)造的無向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。 2、選做題 采用鄰接表存儲結(jié)構(gòu)，編寫一個(gè)判別無向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點(diǎn)序列中不含有重復(fù)頂點(diǎn)的路徑。提示：兩個(gè)頂點(diǎn)及k值均作為參數(shù)給出。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 排序 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)7 排序 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。 （2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點(diǎn)。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 用隨機(jī)數(shù)產(chǎn)生100000個(gè)待排序數(shù)據(jù)元素的關(guān)鍵字值。測試下列各排序函數(shù)的機(jī)器實(shí)際執(zhí)行時(shí)間（至少測試兩個(gè)）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。 2、選做題 假設(shè)含n個(gè)記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v…w]，令number[i]統(tǒng)計(jì)關(guān)鍵字為整數(shù)i的紀(jì)錄個(gè)數(shù)，然后按number重排序列以達(dá)到有序。試編寫算法實(shí)現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點(diǎn)。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)項(xiàng)目名稱： 查找 實(shí)驗(yàn)學(xué)時(shí)： 2 同組學(xué)生姓名： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)日期： 實(shí)驗(yàn)成績： 批改教師： 批改時(shí)間： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)8 查找 一、實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設(shè)計(jì)。 二、實(shí)驗(yàn)儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實(shí)驗(yàn)內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）在一個(gè)遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。 2、選做題 （2）構(gòu)造一個(gè)哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設(shè)計(jì)一個(gè)測試程序進(jìn)行測試。 提示：構(gòu)造哈希表只是完成查找的第一步，大家應(yīng)該掌握在哈希表上進(jìn)行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單： 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 實(shí)驗(yàn)1 遞歸與分治 一、實(shí)驗(yàn)?zāi)康模?/p> 利用C/C++/JAVA等程序設(shè)計(jì)語言，實(shí)現(xiàn)本章節(jié)中分治算法、遞歸，漢諾塔問題/二分搜索算法/合并排序/快速排序等經(jīng)典算法。通過本實(shí)驗(yàn)章節(jié)掌握遞歸、分治算法的設(shè)計(jì)思想及實(shí)現(xiàn)技巧，加深對課程知識的理解。 二、實(shí)驗(yàn)學(xué)時(shí)：2 三、實(shí)驗(yàn)任務(wù)： 利用高級程序設(shè)計(jì)語言，編程實(shí)現(xiàn)以下問題： 1）遞歸：排列問題，漢諾塔問題； 2）分治：遞歸實(shí)現(xiàn)的合并排序及非遞歸的自然合并排序； 四、實(shí)驗(yàn)要求 1，設(shè)計(jì)過程 理解課本中源代碼或偽代碼的思想，結(jié)合流程圖等工具描述實(shí)驗(yàn)任務(wù)的設(shè)計(jì)過程，并獨(dú)自完成代碼編寫、調(diào)試及測試過程。2，代碼及注釋 提交包含完整源代碼及關(guān)鍵代碼注釋的實(shí)驗(yàn)報(bào)告。3，運(yùn)行效果圖及測試數(shù)據(jù) 實(shí)驗(yàn)報(bào)告中應(yīng)有能體現(xiàn)源代碼正確編譯、運(yùn)行的實(shí)驗(yàn)運(yùn)行效果圖及多組測試數(shù)據(jù)集。 4，心得體會 將實(shí)驗(yàn)過程中所遇到的問題以及解決問題的方式、方法以及調(diào)試過程加以概括，并總結(jié)該實(shí)驗(yàn)過程中的收獲。 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 算法分析與設(shè)計(jì) 實(shí)驗(yàn)指導(dǎo)書 于洪 編寫 2011年8月 目 錄 實(shí)驗(yàn)一實(shí)驗(yàn)二實(shí)驗(yàn)三實(shí)驗(yàn)四附錄1 附錄2 排序問題求解…………………………..…..………3 背包問題求解…………………………..…………..5 最短路徑問題求解………………..………………..8 N-皇后問題求解…………………………………..10關(guān)于文件的操作……………………………….….12 關(guān)于如何統(tǒng)計(jì)運(yùn)算時(shí)間…………………………..13 實(shí)驗(yàn)一 排序問題求解 實(shí)驗(yàn)?zāi)康?/p> 1）以排序（分類）問題為例，掌握分治法的基本設(shè)計(jì)策略。2）熟練掌握一般插入排序算法的實(shí)現(xiàn)； 3）熟練掌握快速排序算法的實(shí)現(xiàn)； 4)理解常見的算法經(jīng)驗(yàn)分析方法； 實(shí)驗(yàn)環(huán)境 計(jì)算機(jī)、C語言程序設(shè)計(jì)環(huán)境 實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)。實(shí)驗(yàn)內(nèi)容與步驟 1.生成實(shí)驗(yàn)數(shù)據(jù).要求：編寫一個(gè)函數(shù)datagenetare，生成2000個(gè)在區(qū)間[1,10000]上的隨機(jī)整數(shù)，并將這些數(shù)輸出到外部文件data.txt中。這些數(shù)作為后面算法的實(shí)驗(yàn)數(shù)據(jù)。2.實(shí)現(xiàn)直接插入排序算法.要求：實(shí)現(xiàn)insertionsort算法。 算法的輸入是data.txt； 輸出記錄為文件：resultsIS.txt；同時(shí)記錄運(yùn)行時(shí)間為TimeIS。直接插入算法思想： Procedure insertionsort(A,n) A(0)=-? for j=2 to n do item=A(j);i=j-1 while item repeat End insertionsort 3.實(shí)現(xiàn)快速排序算法.要求：實(shí)現(xiàn)QuickSort 算法。 算法的輸入是data.txt； 輸出記錄為文件：resultsQS.txt；同時(shí)記錄運(yùn)行時(shí)間為TimeQS。 快速排序算法思想： Procedure QuickSort（p,q） integer p,q；global n,A(1:n) if p< q then j ← q+1 call Partition(p, j) call QuickSort(p, j-1) call QuickSort(j+1, q) end if end QuickSort 實(shí)驗(yàn)報(bào)告： 實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容： 用A(m)劃分集合A的函數(shù)： Procedure partition(m,p) integer m,p, I;global A(m:p-1)v=A(m);I=m Loop loop I=I+1 until A(I)>=v repeat loop p=p-1 until A(p)<=v repeat if I then call interchange(A(i), A(p)) Else exit Endif Repeat A(m)=A(p);A(p)=v End partition（1）題目； （2）2個(gè)算法的基本思想描述；（3）算法理論分析（參考教材）； （4）程序流程圖； （5）給出data.txt、resultsIS.txt、resultsQS.txt三個(gè)文件任選其一的清單； TimeIS、TimeQS的記錄結(jié)果； （6）實(shí)驗(yàn)分析；以表或者圖的形式給出這2個(gè)算法的經(jīng)驗(yàn)對比分析結(jié)果；并和理論分析結(jié)論進(jìn)行對比。 （7）說明本次調(diào)試實(shí)驗(yàn)的心得體會、經(jīng)驗(yàn)等。如果程序未通過，應(yīng)分析其原因。 實(shí)驗(yàn)二 背包問題求解 實(shí)驗(yàn)?zāi)康?/p> 1）以背包問題為例，掌握貪心法的基本設(shè)計(jì)策略。 2）熟練掌握各種貪心策略情況下的背包問題的算法并實(shí)現(xiàn)；其中：量度標(biāo)準(zhǔn)分別取：效益增量P、物品重量w、P/w比值； 3)分析實(shí)驗(yàn)結(jié)果來驗(yàn)證理解貪心法中目標(biāo)函數(shù)設(shè)計(jì)的重要性。 實(shí)驗(yàn)環(huán)境 計(jì)算機(jī)、C語言程序設(shè)計(jì)環(huán)境 實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)。 實(shí)驗(yàn)內(nèi)容與步驟 1.理解需要求解背包問題.（1）背包問題的描述：已知有n種物品和一個(gè)可容納M重量的背包，每種物品i的重量為益，這里，0?xi?1wi。假定將物品i的一部分 xi放入背包就會得到 pixi的效，pi?0。顯然，由于背包容量是M，因此，要求所有選中要裝入背包的物品總重量不得超過M.。如果這n件物品的總重量不超過M，則把所有物品裝入背包自然獲得最大效益?，F(xiàn)需解決的問題是，在這些物品重量的和大于M的情況下，該如何裝包，使得得到更大的效益值。由以上敘述，可將這個(gè)問題形式表述如下： 極 大 化目標(biāo)函數(shù) 約束條件 ?1?i?npixi ?w1?i?nixi?M 0?xi?1,pi?0,wi?0,1?i?n（2）用貪心策略求解背包問題 首先需確定最優(yōu)的量度標(biāo)準(zhǔn)。這里考慮三種策略： 策略1：按物品價(jià)值p降序裝包，策略2：按物品重w升序裝包 策略3：按物品價(jià)值與重量比值p/w的降序裝包 （3）分別以上面三種策略分別求以下情況背包問題的解： n=7，M=15，（p1,?,p7）=（10，5，15，7，6，18，3）（w1,?,w7）=（2，3，5，7，1，4，1）。以策略3為例的背包問題的貪心算法描述： procedure GREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分別含有按P（i）/W（i）≥P（i+1）/ W（i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。// real P(1：n)，W（1：n）,X（1：n），M，cu； integer i，n;X?0 //將解向量初始化為零 cu?M //cu是背包剩余容量 for i?1 to n do if W(i)>cu then exit endif X(i)?1 cu?cu-W(i)repeat if i≤n then X(i)?cu/W(i)endif end GREEDY-KNAPSACK 2.以策略1作為量度標(biāo)準(zhǔn)求解要求問題，記錄解向量為X1、目標(biāo)函數(shù)的值fp1（即最后裝好包后背包的效益值 ?1?i?n、背包的重量fw1； pixi）3.以策略2作為量度標(biāo)準(zhǔn)求解要求問題，記錄解向量為X21、目標(biāo)函數(shù)的值fp2（即最后裝好包后背包的效益值 ?1?i?n、背包的重量fw2； pixi）4.以策略3作為量度標(biāo)準(zhǔn)求解要求問題，記錄解向量為X3、目標(biāo)函數(shù)的值fp3即最后裝好包后背包的效益值實(shí)驗(yàn)報(bào)告： 實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容： ?1?i?n、背包的重量fw3； pixi）（1）題目； （2）算法的基本思想描述；（3）程序流程圖； （4）給出3個(gè)程序任意之一的程序清單； （5）實(shí)驗(yàn)分析；通過實(shí)驗(yàn)結(jié)果對比分析說明哪種策略好。 （6）說明本次調(diào)試實(shí)驗(yàn)的心得體會、經(jīng)驗(yàn)等。如果程序未通過，應(yīng)分析其原因。 Tips： 1.解向量的表示。需要注意：因?yàn)樗惴ㄖ猩婕暗脚判?，如何保證各種物品的原始命名（如果以第幾種，即序號，來命名物品）關(guān)系需要考慮。 #define MAX 200 typedef struct Solution //定義的解向量 { int x[MAX];表示該號物品放了多少在背包里，這里0?xi? 1int order[MAX];表示物品的序號，相當(dāng)于其名字 }Solution;Solution X;所以，初始化時(shí)，為： for(i=0;i { X.order[i]=i; X.x[i]=0; } 2.主要函數(shù)： void GreedyKnapsack(float profit[],float weight[],float x[],int m, int n){ float cu; int i; cu=float(m); for(i=0;i { x[i]=0; } for(i=0;i { if(weight[i]>cu) break; x[i]=1; cu=cu-weight[i]; } if(i { x[i]=cu/weight[i]; } } 實(shí)驗(yàn)三 最短路徑問題求解 實(shí)驗(yàn)?zāi)康模?/p> 1）以最短路徑問題為例，掌握動態(tài)規(guī)劃的基本設(shè)計(jì)策略； 2）掌握dijkstra貪心法求解最短路徑問題并實(shí)現(xiàn)； 3）掌握動態(tài)規(guī)劃方法Floyd算法求解最短路徑問題并實(shí)現(xiàn)； 3）分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)環(huán)境 計(jì)算機(jī)、C語言程序設(shè)計(jì)環(huán)境 實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)。實(shí)驗(yàn)內(nèi)容與步驟 1.以下圖作為輸入，利用dijkstra貪心法獲取由結(jié)點(diǎn)1到其余結(jié)點(diǎn)最短路徑長度，輸出保存到外部文件dijkstra－output1.txt 3 4 5 2 1 2.然后改寫你的程序，求得所有各點(diǎn)之間的最短距離;輸出保存到文件dijkstra－output2.txt.3.以上圖作為輸入，利用Floyd算法求得所有各點(diǎn)直接的最短距離;輸出保存到文件floyd－output1.txt.實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容： （1）題目； （2）寫出算法設(shè)計(jì)思想； （3）程序清單；（4）運(yùn)行的結(jié)果； （5）對運(yùn)行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗(yàn)。如果程序未通過，應(yīng)分析其原因。 Tips: 主要函數(shù) void dijkstra::algorithm()//算法函數(shù) { initialize();int count=0;int i;int u;while(count u=minimum(); set[++count]=u; mark[u]=1; for(i=1;i<=num_of_vertices;i++) { if(graph[u][i]>0) { if(mark[i]!=1) { if(pathestimate[i]>pathestimate[u]+graph[u][i]) { pathestimate[i]=pathestimate[u]+graph[u][i]; predecessor[i]=u; } } }} }} //-------------float graph[maxsize][maxsize];//成本矩陣，鄰接矩陣 //floyd algorithm for(k = 0;k < n;k ++) { // graph[i][j] = min {graph[i][j]}, graph[i][k] + graph[k][j] for(i = 0;i < n;i ++) //每次找到最優(yōu)的路徑代替原來的路徑 for(j = 0;j < n;j ++) if(graph[i][j] > graph[i][k] + graph[k][j])//狀態(tài)轉(zhuǎn)換條件 { graph[i][j] = graph[i][k] + graph[k][j];//狀態(tài)轉(zhuǎn)換方程 } } 實(shí)驗(yàn)四：N-皇后問題求解 實(shí)驗(yàn)?zāi)康模?/p> 1）以Q-皇后問題為例，掌握回溯法的基本設(shè)計(jì)策略。2）掌握回溯法解決Q-皇后問題的算法并實(shí)現(xiàn)； 3）分析實(shí)驗(yàn)結(jié)果。 實(shí)驗(yàn)環(huán)境 計(jì)算機(jī)、C語言程序設(shè)計(jì)環(huán)境 實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)。 實(shí)驗(yàn)內(nèi)容與步驟 1.用回溯法求解N-Queen，參考教材算法思想，并實(shí)現(xiàn)你的算法。要求：用鍵盤輸入N；輸出此時(shí)解的個(gè)數(shù)，并統(tǒng)計(jì)運(yùn)算時(shí)間。2.給出N=4,5,6時(shí)，N-Queen解的個(gè)數(shù)。 3.嘗試增大N，觀察運(yùn)行情況；并理解該算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容： （1）題目； （2）寫出算法設(shè)計(jì)思想； （3）運(yùn)行的結(jié)果； （4）對運(yùn)行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗(yàn)。（5）如果程序未通過，應(yīng)分析其原因。 Tips: 主要函數(shù)等 while(k>0)//對所有行執(zhí)行以下語句 { X[k] = X[k]+1;//移到下一列 while(X[k]<=n &&!PLACE(k)) { X[k] = X[k]+1;//移到下一列，再判斷 } if(X[k] <= n)//找到一個(gè)位置 { if(k==n)//一個(gè)完整的解 { //print printf(“the soution is:n”); for(t=1;t<=n;t++) printf(“%3d”,X[t]); printf(“n”); count +=1; } else {k=k+1;X[k]=0;} //轉(zhuǎn)向下一行 } else k=k-1;//回溯 } printf(“n the number of the solutions is %d n”, count); bool PLACE(int k){ i=1;while(i if(X[i]==X[k] || abs(X[i]-X[k])==abs(i-k)) return false; i=i+1;} return true;} 附錄1關(guān)于文件的操作 以背包問題為例： 1，例如外部文件為knapsack-input.txt： 2, 讀入文件的操作： FILE* fp; /* Open for read(will fail if file “knapsack-input.txt” does not exist)*/ if((fp = fopen(“knapsack-input.txt”, “r”))== NULL) printf(“The file 'knapsack-input.txt' was not openedn”); else printf(“The file 'knapsack-input.txt' was openedn”); //讀輸入文件，寫n,M,p[MAX],w[MAX] fscanf(fp,“n=%dn”,&n); fscanf(fp,“M=%dn”,&M); for(i=0;i for(i=0;i fscanf(fp,“%f”,&weight[i]);fscanf(fp,“n”); /* Close stream */ if(fclose(fp)) printf(“The file 'knapsack-input.txt' was not closedn”);附錄2關(guān)于如何統(tǒng)計(jì)運(yùn)算時(shí)間 #include “time.h” …….//----start time-----設(shè)置計(jì)時(shí)開始 double duration; clock_t finish, start;start = clock(); …… //----finish time-----設(shè)置計(jì)時(shí)結(jié)束 finish = clock(); duration =(double)(finish-start)/ CLOCKS_PER_SEC; printf(“nThe CPU time is %2.6f seconds:n”, duration); // 統(tǒng)計(jì)時(shí)間duration第四篇：算法設(shè)計(jì)與分析 實(shí)驗(yàn)指導(dǎo)書1
第五篇：《算法分析與設(shè)計(jì)》實(shí)驗(yàn)指導(dǎo)書-
點(diǎn)擊咨詢 