第一篇：21-葛義杰 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)冊(cè)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊(cè)

課程名稱：

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

所屬院部：

（理工類）

算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級(jí)：15計(jì)算機(jī)科學(xué)與技術(shù)（單）

1513902021 學(xué)生姓名： 葛義杰

計(jì)算機(jī)工程學(xué)院 指導(dǎo)教師： 章海鷗

2016 ——2017 學(xué)年 第 1 學(xué)期

金陵科技學(xué)院教務(wù)處制

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告書寫要求

實(shí)驗(yàn)報(bào)告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點(diǎn)需打印的，要遵照以下字體、字號(hào)、間距等的具體要求。紙張一律采用A4的紙張。

實(shí)驗(yàn)報(bào)告書寫說(shuō)明

實(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)容與過(guò)程；實(shí)驗(yàn)結(jié)果與分析。各院部可根據(jù)學(xué)科特點(diǎn)和實(shí)驗(yàn)具體要求增加項(xiàng)目。

填寫注意事項(xiàng)

（1）細(xì)致觀察，及時(shí)、準(zhǔn)確、如實(shí)記錄。（2）準(zhǔn)確說(shuō)明，層次清晰。

（3）盡量采用專用術(shù)語(yǔ)來(lái)說(shuō)明事物。

（4）外文、符號(hào)、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號(hào)。（5）應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。

實(shí)驗(yàn)報(bào)告批改說(shuō)明

實(shí)驗(yàn)報(bào)告的批改要及時(shí)、認(rèn)真、仔細(xì)，一律用紅色筆批改。實(shí)驗(yàn)報(bào)告的批改成績(jī)采用百分制，具體評(píng)分標(biāo)準(zhǔn)由各院部自行制定。

實(shí)驗(yàn)報(bào)告裝訂要求

實(shí)驗(yàn)批改完畢后，任課老師將每門課程的每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)報(bào)告以自然班為單位、按學(xué)號(hào)升序排列，裝訂成冊(cè)，并附上一份該門課程的實(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)1 順序表

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

掌握順序表的定位、插入、刪除等操作。

二、實(shí)驗(yàn)儀器和設(shè)備

VC6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測(cè)試結(jié)果。

（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號(hào)（序號(hào)從0開始編號(hào)）；如果不存在，返回－1。編寫主函數(shù)測(cè)試結(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è)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。

程序清單：

1.#include #define maxsize 20 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;

void CreateList(sequenlist *L,int n){int i;printf(“please input n numbersn”);for(i=0;i

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{ scanf(“%d”,&L->data[i]);(*L).last=n;} }

void PrintList(sequenlist *L,int n){int i;printf(“the sequenlist isn”);for(i=0;idata[i]);} main(){ int i,x;int n=10;sequenlist L;CreateList(&L,n);PrintList(&L,n);getchar();getchar();} 2.#include #define maxsize 100 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;

void CreateList(sequenlist *L,int n){int i;printf(“請(qǐng)你輸入數(shù)據(jù)元素：n”);for(i=0;i(*L).last)return-1;else return i;}

main(){ int i,x,a;int n;sequenlist L;L.last=0;printf(“請(qǐng)你輸入順序表的長(zhǎng)度:n n=”);scanf(“%d”,&n);CreateList(&L,n);//調(diào)用順序表的建立函數(shù)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

// PrintList(&L,n);//調(diào)用順序表的 打印輸出函數(shù) // printf(“n”);printf(“請(qǐng)輸入要查找的數(shù)據(jù)元素X：nx=”);scanf(“%d”,&x);a=Seek(&L,x);if(a==-1)printf(“沒(méi)有找到你所要找的數(shù)據(jù)元素！”);else {printf(“你所要查找的數(shù)據(jù)元素位置是：”);printf(“%d”,a);} getchar();getchar();} 3.#include #define maxsize 20 typedef int datatype;typedef

struct{ datatype data[maxsize];int last;}sequenlist;

void CreateList(sequenlist *L,int n){int i;printf(“請(qǐng)你輸入數(shù)據(jù)元素：n”);for(i=0;i

{

scanf(“%d”,&(*L).data[i]);

}(*L).last=n-1;}

InsertaInteger(sequenlist *L,int c){

int i,j,m;

for(i=0;i<(*L).last;i++)

{

if(c<=(*L).data[i])

{m=i;break;}

}

(*L).last++;

for(j=(*L).last;j>=m;j--)

{

(*L).data[j+1]=(*L).data[j];

(*L).data[m]=c;

}

(*L).last++;

for(i=0;i<(*L).last;i++)

printf(“%d

”,(*L).data[i]);

}

main(){ int i,x;int a,c,n;sequenlist L;L.last=0;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

printf(“請(qǐng)你輸入順序表的長(zhǎng)度:n n=”);scanf(“%d”,&n);CreateList(&L,n);//調(diào)用順序表的建立函數(shù)

printf(“n請(qǐng)輸入你要插入的數(shù)據(jù)元素C：”);scanf(“%d”,&c);InsertaInteger(&L,c);getchar();getchar();} 4.#include #define maxsize 100 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;void CreateList(sequenlist *L,int n){int i;printf(“請(qǐng)你輸入數(shù)據(jù)元素：n”);for(i=0;i(*L).last)return-1;else return i;} void Deleate(sequenlist *L,int x){int i,j=0;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

i=Get(&L,x);if(i==-1)printf(“你所要?jiǎng)h除的元素不存在”);else { while(i<(*L).last+1){if((*L).data[i]==x){(*L).data[i]=(*L).data[i+1];i--;(*L).last--;} i++;} } for(i=0;i<(*L).last+1;i++)printf(“%d ”,(*L).data[i]);} main(){ int i,x,a,m;int n;sequenlist L;L.last=0;printf(“請(qǐng)你輸入順序表的長(zhǎng)度:n n=”);scanf(“%d”,&n);CreateList(&L,n);//調(diào)用順序表的建立函數(shù) printf(“n”);printf(“請(qǐng)你輸入要?jiǎng)h除的數(shù)據(jù)元素m：”);scanf(“%d”,&m);Deleate(&L,m);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

getchar();getchar();}

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1.2.3.4.金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）編程要求我們有足夠的耐心，細(xì)細(xì)推敲。越著急可能就越無(wú)法得到我們想要的結(jié)果，遇到不會(huì)的問(wèn)題要多多請(qǐng)教，知識(shí)是在實(shí)踐與向別人請(qǐng)教的過(guò)程中積累的，所以問(wèn)是至關(guā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)成績(jī)： 批改教師： 批改時(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）注意鏈表的空間是動(dòng)態(tài)分配的，某結(jié)點(diǎn)不用之后要及時(shí)進(jìn)行物理刪除，以便釋放其內(nèi)存空間。

（2）鏈表不能實(shí)現(xiàn)直接定位，一定注意指針的保存，防止丟失。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

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ù)測(cè)試結(jié)果。

2、選做題

已知指針LA和LB分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)單鏈表的首元結(jié)點(diǎn)。要求編一算法實(shí)現(xiàn)，從表LA中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表LB中第j個(gè)元素之前。

程序清單：

1.#include #include typedef struct node { int data;struct node *next;}linklist;

linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=NULL;r=NULL;printf(“請(qǐng)輸入單鏈表的數(shù)據(jù)元素：n”);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

scanf(“%d”,&a);while(a!=-1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;if(head==NULL)head=s;else r->next=s;r=s;scanf(“%d”,&a);} if(r!=NULL)r->next=NULL;return head;}

void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }

main(){linklist *p;p=CREATLINKLISTR();printf(“n”);printf(“你所輸入的單鏈表為：n”);PRINTLINKLIST(p);getchar();getchar();} 2.#include #include typedef struct node { int data;struct node *next;}linklist;

linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=NULL;r=NULL;printf(“請(qǐng)輸入單鏈表的數(shù)據(jù)元素(輸入時(shí)數(shù)據(jù)元素遞增)：n”);scanf(“%d”,&a);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

while(a!=-1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;if(head==NULL)head=s;else r->next=s;r=s;scanf(“%d”,&a);} if(r!=NULL)r->next=NULL;return head;}

void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }

linklist *Insert(linklist *head,int x){linklist *s,*q;s=(linklist*)malloc(sizeof(linklist));s->data=x;q=head;if(q->data>x){ s->next=q;head=s;} else while(q!=NULL){ if(q->next->data>x){ s->next=q->next;q->next=s;break;}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

q=q->next;} q=head;

PRINTLINKLIST(q);}

main(){linklist *p;int x;p=CREATLINKLISTR();printf(“你所建立的單鏈表為：n”);PRINTLINKLIST(p);printf(“n”);printf(“請(qǐng)輸入在以上有序遞增的單鏈表中插入數(shù)據(jù)x：n”);scanf(“%d”,&x);Insert(p,x);getchar();getchar();} 3.#include typedef struct node { int data;struct node *next;}linklist;

linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=(linklist*)malloc(sizeof(linklist));r=head;printf(“請(qǐng)輸入單鏈表中的數(shù)據(jù)元素n”);scanf(“%d”,&a);while(a!=1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;r->next=s;r=s;scanf(“%d”,&a);} r->next=NULL;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

return head;}

void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }

linklist *InverseLinklist(linklist *q){linklist *p,*head;p=head->next;if(p!=NULL){ p=p->next;head->next->next=NULL;} while(p!=NULL){ q=p->next;p->next=head->next;head->next=p;p=q;} printf(“n單鏈表被逆置后為n”);PRINTLINKLIST(head->next);} int main(){linklist *p;p=CREATLINKLISTR();// PRINTLINKLIST(p->next);InverseLinklist(p);getchar();getchar();}

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

1金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

2.3.五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

鏈表的空間是動(dòng)態(tài)分配的，某結(jié)點(diǎn)不用之后要及時(shí)進(jìn)行物理刪除，以便釋放其內(nèi)存空間。鏈表不能實(shí)現(xià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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)3 堆棧和隊(duì)列

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

（1）掌握應(yīng)用棧解決問(wèn)題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。

（3）掌握隊(duì)列的存儲(chǔ)結(jié)構(gòu)及基本操作實(shí)現(xiàn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）判斷一個(gè)算術(shù)表達(dá)式中開括號(hào)和閉括號(hào)是否配對(duì)。（2）測(cè)試“漢諾塔”問(wèn)題。

（3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個(gè)算法判別讀入的一個(gè)以’@’為結(jié)束符的字符序列是否是“回文”。

2、選做題

在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)輸出受限的雙端循環(huán)隊(duì)列的入列和出列算法。設(shè)每個(gè)元素表示一個(gè)待處理的作業(yè)，元素值表示作業(yè)的預(yù)計(jì)時(shí)間。入隊(duì)列采取簡(jiǎn)化的短作業(yè)優(yōu)先原則，若一個(gè)新提交的作業(yè)的預(yù)計(jì)執(zhí)行時(shí)間小于隊(duì)頭和隊(duì)尾作業(yè)的平均時(shí)間，則插入在隊(duì)頭，否則插入在隊(duì)尾。程序清單：

1． 判斷一個(gè)算術(shù)表達(dá)式中開括號(hào)和閉括號(hào)是否配對(duì)。#include #include typedef char datatype;#define maxsize 64 typedef struct {

datatype data[maxsize];int top;} seqstack;

int match(char exp[],int n){ char st[maxsize];//éè??ò?????￡?ó?à′′?·?é¨?è±í′?ê??Dμ?à¨o?

int top=-1,i=0,tag=1;while(i

if(exp[i]=='('||exp[i]=='['||exp[i]=='{')//ó?μ?'(''[''{',?ò????è??? {

top++;

st[top]=exp[i];

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

}

if(exp[i]==')')//ó?μ?')',è????￥ê?'(',?ò?ìD?′|àí￡?·??òò?2?????·μ??

if(st[top]=='(')top--;

else tag=0;

if(exp[i]==']')

if(st[top]=='[')top--;

else tag=0;

if(exp[i]=='}')

if(st[top]=='{')top--;

else tag=0;

i++;} if(top>=0)tag=0;//è???2???￡??ò2????? return tag;}

main(){ int tag,i;char exp[7]={'(','+','(','2','-','4',')'};

printf(“??ê?è?ò?????ê?±í′?ê?￡on”);

for(i=0;i<7;i++)

exp[i]=getchar();tag=match(exp,7);if(tag)

printf(“??ê?±í′?ê??Dμ??aà¨o?oí±?à¨o??????￡”);else

printf(“??ê?±í′?ê??Dμ??aà¨o?oí±?à¨o?2?????￡?”);getchar();getchar();}

2．#include

void move(char x,char z){printf(“%c-->”,x);printf(“%cn”,z);}

void Hanoi(int n,char x, char y,char z){ if(n==1)move(x,z);else {Hanoi(n-1,x,z,y);move(x,z);Hanoi(n-1,y,x,z);} }

main(){ int m;printf(“請(qǐng)你輸入A上面的碟子總數(shù)”);scanf(“%d”,&m);Hanoi(m,'A','B','C');getchar();getchar();}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

3．#include #include typedef struct { char data[10];int top;}seqstack;main(){int i;char a[9],b[9];int m;seqstack *s;s=(seqstack*)malloc(sizeof(seqstack));s->top=-1;printf(“請(qǐng)你輸入8位的a字符串：n”);for(i=0;i<9;i++)scanf(“%c”,&a[i]);i=0;while(a[i]!='!'){ s->top++;s->data[s->top]=a[i];i++;} //printf(“%d ”,i);i=7;while(s->top>=0){ b[i]=s->data[s->top];s->top--;i--;} b[8]='!';m=strcmp(a,b);//printf(“%d”,m);if(m==1)printf(“你所輸入的字符串為回文！”);else printf(“你所輸入的字符串不是回文！”);getchar();getchar();}

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）．

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

2．3．

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

鏈棧則沒(méi)有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動(dòng)的一頭自由地增加鏈環(huán)(結(jié)點(diǎn))而不會(huì)溢出，鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要在頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)4 串

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

掌握串的存儲(chǔ)及應(yīng)用。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）編寫輸出字符串s中值等于字符ch的第一個(gè)字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。

（2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。

解題思路：可以將第一題程序改進(jìn)成一個(gè)子函數(shù)，在本題中循環(huán)調(diào)用。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編程刪除串s從位置i開始長(zhǎng)度為k的子串。

2、選做題

假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實(shí)現(xiàn)將串S插入到串T中某個(gè)字符之后，若串T中不存在這個(gè)字符，則將串S聯(lián)接在串T的末尾。

提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計(jì)為從鍵盤輸入。程序清單：

1．#include #include

int seekfirst(char a[],char x){int i;for(i=0;i

main(){int location;char ch;char s[50];gets(s);scanf(“%c”,&ch);location=seekfirst(s,ch);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

printf(“%d”,location);getchar();getchar();} 2．

#include #include

void seeklocation(char a[],char x){int i;for(i=0;i

main(){ char ch;char s[50];gets(s);scanf(“%c”,&ch);seeklocation(s,ch);getchar();getchar();} 3．

#include #include #include typedef struct linknode {char data;struct linknode *next;}linkstring;void DeleateSmallString(linkstring *head,int i,int k){linkstring *p,*h,*f;int m=1,n=1;p=head;while(p!=NULL){p=p->next;if(m==i-1){ h=p->next;break;

} m++;} while(h!=NULL){ h=h->next;n++;

if(n==k)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

break;

}

p->next=h->next;f=head->next;while(f!=NULL){ printf(“%c”,f->data);f=f->next;

}

} main(){char ch;int i,k;linkstring *s,*head,*r,*q;

head=(linkstring*)malloc(sizeof(linkstring));r=head;ch=getchar();while(ch!='n'){ s=(linkstring *)malloc(sizeof(linkstring));s->data=ch;r->next=s;r=s;ch=getchar();

} r->next=NULL;q=head;printf(“輸入位置和長(zhǎng)度”);scanf(“%d%d”,&i,&k);printf(“%d %dn”,i,k);DeleateSmallString(q,i,k);

getchar();getchar();

}

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1．

2．金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

3．五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

在串順序存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為字符序列的復(fù)制串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集 ；在基本操作上差別很大，線性表的基本操作大多數(shù)以單個(gè)元素作為操作對(duì)象，而串的基本操作通常以 串的整體 作為操作對(duì)象。兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且各個(gè)對(duì)應(yīng)位置的字符都相等。空串是指 不含任何字符的串，空格串是指僅含空格字符的串。

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)5 二叉樹

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

（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問(wèn)題的方法。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）建立一棵二叉樹。對(duì)此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。

（2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點(diǎn)總數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。

2、選做題

已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲(chǔ)結(jié)點(diǎn)的值。試編寫算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹的二叉鏈表。

解題思路：根據(jù)完全二叉樹順序存儲(chǔ)的性質(zhì)來(lái)確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹順序存儲(chǔ)的一個(gè)重要性質(zhì)為，第i個(gè)結(jié)點(diǎn)的左孩子是編號(hào)為2i的結(jié)點(diǎn)，第i個(gè)結(jié)點(diǎn)的右孩子是編號(hào)為2i+1的結(jié)點(diǎn)。程序清單：

1．#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;int m=0;//二叉樹的建立函數(shù)

bitree *creattree()//建立二叉樹，函數(shù)返回指向根的指針 {bitree *Q[maxsize];//隊(duì)列Q為bitree指針類型的數(shù)組 char ch;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

int front,rear;//隊(duì)頭隊(duì)尾指針 bitree *root,*s;root=NULL;//置空二叉樹 front=1;rear=0;//置空隊(duì)列

ch=getchar();//輸入第一個(gè)字符

while(ch!='n')//不是結(jié)束符的時(shí)候重復(fù)做 { s=NULL;if(ch!='@')//空格表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新的結(jié)點(diǎn) { s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;//新結(jié)點(diǎn)地址入隊(duì)

if(rear==1)root=s;//結(jié)點(diǎn) else {if(s&&Q[front])//是虛結(jié)點(diǎn)

if(rear%2==0)Q[front]->lchild=s;//rear是左孩子 else Q[front]->rchild=s;//孩子已處理完畢，出隊(duì)列

if(rear%2==1)front++;} ch=getchar();// } return root;//} //前序遍歷二叉樹并計(jì)算二叉樹的葉結(jié)點(diǎn)個(gè)數(shù) void leaf(bitree *T){ if(T){ if(T->lchild==NULL&&T->rchild==NULL)m++;leaf(T->lchild);leaf(T->rchild);

將虛結(jié)點(diǎn)指針NULL或輸入第一個(gè)結(jié)點(diǎn)為根孩子和雙親結(jié)點(diǎn)均不為偶數(shù)，新結(jié)點(diǎn)結(jié)點(diǎn)*Q[front]的兩個(gè)輸入下一個(gè)字符 返回頭指針 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

} } //主函數(shù) void main(){ bitree *L;printf(“建立的二叉樹為：n”);L=creattree();leaf(L);printf(“二叉樹葉節(jié)點(diǎn)個(gè)數(shù)為：n”);printf(“%d”,m);getchar();getchar();} 2．

#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;

//二叉樹的建立函數(shù)

bitree *creattree()//建立二叉樹，函數(shù)返回指向根的指針 {bitree *Q[maxsize];//隊(duì)列Q為bitree指針類型的數(shù)組 char ch;int front,rear;//隊(duì)頭隊(duì)尾指針 bitree *root,*s;root=NULL;//置空二叉樹 front=1;rear=0;//置空隊(duì)列 ch=getchar();//輸入第一個(gè)字符

while(ch!='n')//不是結(jié)束符的時(shí)候重復(fù)做

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{ s=NULL;if(ch!='@')//空格表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新的結(jié)點(diǎn) { s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;//新結(jié)點(diǎn)地址入隊(duì)

if(rear==1)root=s;//結(jié)點(diǎn) else {if(s&&Q[front])//是虛結(jié)點(diǎn)

if(rear%2==0)Q[front]->lchild=s;//rear是左孩子 else Q[front]->rchild=s;//孩子已處理完畢，出隊(duì)列 if(rear%2==1)front++;} ch=getchar();// } return root;//}

將虛結(jié)點(diǎn)指針NULL或輸入第一個(gè)結(jié)點(diǎn)為根孩子和雙親結(jié)點(diǎn)均不為偶數(shù)，新結(jié)點(diǎn)結(jié)點(diǎn)*Q[front]的兩個(gè)輸入下一個(gè)字符 返回頭指針 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

//二叉樹的深度函數(shù) int high(bitree *T){int m,n;if(T==NULL)return 0;else m=high(T->lchild);n=high(T->rchild);return((m>n?m:n)+1);} //主函數(shù) void main(){int m;bitree *L;printf(“建立的二叉樹為：n”);L=creattree();m=high(L);printf(“二叉樹的高度為：n”);printf(“%d”,m);getchar();getchar();} 3．。

#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

struct node *lchild,*rchild;}bitree;int m=0;//二叉樹的建立函數(shù)

bitree *creattree()//建立二叉樹，函數(shù)返回指向根的指針 {bitree *Q[maxsize];//隊(duì)列Q為bitree指針類型的數(shù)組 char ch;int front,rear;//隊(duì)頭隊(duì)尾指針 bitree *root,*s;root=NULL;//置空二叉樹 front=1;rear=0;//置空隊(duì)列 ch=getchar();//輸入第一個(gè)字符

while(ch!='n')//不是結(jié)束符的時(shí)候重復(fù)做 { s=NULL;if(ch!='@')//空格表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新的結(jié)點(diǎn) { s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;//將虛結(jié)點(diǎn)指針NULL或新結(jié)點(diǎn)地址入隊(duì)

if(rear==1)root=s;//輸入第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn) else

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{if(s&&Q[front])//孩子和雙親結(jié)點(diǎn)均不是虛結(jié)點(diǎn)

if(rear%2==0)Q[front]->lchild=s;//rear為偶數(shù)，新結(jié)點(diǎn)是左孩子 else Q[front]->rchild=s;//結(jié)點(diǎn)*Q[front]的兩個(gè)孩子已處理完畢，出隊(duì)列 if(rear%2==1)front++;} ch=getchar();// } return root;//} //求二叉樹的節(jié)點(diǎn)的總數(shù) int sum(bitree *T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild==NULL&&T->rchild==NULL)return 1;else { num1=sum(T->lchild);num2=sum(T->rchild);return(num1+num2+1);} } main(){int m;

輸入下一個(gè)字符 返回頭指針 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

bitree *L;printf(“建立的二叉樹為：n”);L=creattree();m=sum(L);printf(“二叉樹的結(jié)點(diǎn)總數(shù)為：n”);printf(“%d”,m);getchar();getchar();} 4．

#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;

//二叉樹的建立函數(shù)

bitree *creattree()//{bitree *Q[maxsize];// char ch;int front,rear;// bitree *root,*s;root=NULL;// front=1;rear=0;// ch=getchar();// while(ch!='n')//建立二叉樹，函數(shù)返回指向根的指針隊(duì)列Q為bitree指針類型的數(shù)組 隊(duì)頭隊(duì)尾指針 置空二叉樹 置空隊(duì)列 輸入第一個(gè)字符

不是結(jié)束符的時(shí)候重復(fù)做

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{ s=NULL;if(ch!='@')//空格表示虛結(jié)點(diǎn)，不是虛結(jié)點(diǎn)時(shí)建立新的結(jié)點(diǎn) { s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;//新結(jié)點(diǎn)地址入隊(duì)

if(rear==1)root=s;//結(jié)點(diǎn) else {if(s&&Q[front])//是虛結(jié)點(diǎn)

if(rear%2==0)Q[front]->lchild=s;//rear是左孩子 else Q[front]->rchild=s;//孩子已處理完畢，出隊(duì)列 if(rear%2==1)front++;} ch=getchar();// } return root;//}

將虛結(jié)點(diǎn)指針NULL或輸入第一個(gè)結(jié)點(diǎn)為根孩子和雙親結(jié)點(diǎn)均不為偶數(shù)，新結(jié)點(diǎn)結(jié)點(diǎn)*Q[front]的兩個(gè)輸入下一個(gè)字符 返回頭指針 金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

//二叉樹的深度函數(shù) int high(bitree *T){int m,n;if(T==NULL)return 0;else m=high(T->lchild);n=high(T->rchild);return((m>n?m:n)+1);} //主函數(shù) main(){int m;bitree *L;printf(“建立的二叉樹為：n”);L=creattree();m=high(L);printf(“二叉樹的高度為：n”);printf(“%d”,m);getchar();getchar();}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）1．

2．金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

3．。

4．。

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

樹是常用的數(shù)據(jù)結(jié)構(gòu)。通過(guò)實(shí)驗(yàn)加深了我對(duì)樹的遍歷的認(rèn)識(shí)，鞏固了課本中所學(xué)的關(guān)于樹的基本算法。按要求完成了實(shí)驗(yàn)內(nèi)容。通過(guò)實(shí)驗(yàn)，有如下幾點(diǎn)收獲和體會(huì)：

1、通過(guò)實(shí)驗(yàn)還提高了一點(diǎn)改錯(cuò)能力，對(duì)于一些常見問(wèn)題加深了印象。

2、編程需要細(xì)心，有時(shí)一個(gè)不注意小錯(cuò)誤就能引出大問(wèn)題。編程也需要規(guī)范，不僅為了他人能看得懂程序，也為了方便自己以后程序的更改與進(jìn)一步的完善。

3、程序由算法和數(shù)據(jù)結(jié)構(gòu)組成，一個(gè)好的程序不僅算法重要，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)也很重要。4.二叉樹的先序、中序與后序的輸出都用了遞歸算法。而且用起來(lái)并不復(fù)雜，這使我更進(jìn)一步學(xué)習(xí)理解了函數(shù)的遞歸調(diào)用并得到靈活的運(yùn)用。經(jīng)過(guò)本次實(shí)驗(yàn)基本上解決的一些所遇到的問(wèn)題，我對(duì)二叉樹的結(jié)構(gòu)等有了較為深入的理解。我會(huì)繼續(xù)我的興趣編寫程序的，相信在越來(lái)越多的嘗試之后，自己會(huì)不斷進(jì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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)6 圖

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

（1）熟練掌握?qǐng)D的基本概念、構(gòu)造及其存儲(chǔ)結(jié)構(gòu)。

（2）熟練掌握對(duì)圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）構(gòu)造一個(gè)無(wú)向圖（用鄰接矩陣表示存儲(chǔ)結(jié)構(gòu)）。

（2）對(duì)上面所構(gòu)造的無(wú)向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。

2、選做題

采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無(wú)向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長(zhǎng)度為k的簡(jiǎn)單路徑的算法。簡(jiǎn)單路徑是指其頂點(diǎn)序列中不含有重復(fù)頂點(diǎn)的路徑。提示：兩個(gè)頂點(diǎn)及k值均作為參數(shù)給出。程序清單：

(1)#include #include typedef int datatype;#define maxsize 1024 #define n 100 typedef char VEXTYPE;typedef int ADJTYPE;typedef struct { VEXTYPE vexs[n];ADJTYPE arcs[n][n];int num;}GRAPH;

void GraphInit(GRAPH *L){ L->num=0;}

int GraphVexs(GRAPH *L){ return(L->num);}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

void GraphCreate(GRAPH *L){ int i,j;GraphInit(L);printf(“請(qǐng)輸入頂點(diǎn)數(shù)目：n”);scanf(“%d”,&L->num);printf(“請(qǐng)輸入各頂點(diǎn)的信息：n”);for(i=0;inum;i++){

fflush(stdin);

scanf(“%c”,&L->vexs[i]);} printf(“請(qǐng)輸入邊權(quán)矩陣的信息：n”);for(i=0;inum;i++){

for(j=0;jnum;j++)

{

scanf(“%d”,&L->arcs[i][j]);

} } printf(“圖已經(jīng)創(chuàng)建完畢！”);}

void GraphOut(GRAPH L){ int i,j;printf(“n圖的頂點(diǎn)數(shù)目為：%d”,L.num);printf(“n圖的各頂點(diǎn)的信息為：n”);for(i=0;i

for(j=0;j

{

printf(“%6d”,L.arcs[i][j]);

}

printf(“n”);} printf(“圖已經(jīng)輸出完畢！”);}

void main(){ GRAPH tu;GraphCreate(&tu);GraphOut(tu);system(“pause”);getchar();}(2)#include #include typedef int datatype;#define maxsize 1024

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

#define n 100 typedef char VEXTYPE;typedef int ADJTYPE;typedef struct { VEXTYPE vexs[n];ADJTYPE arcs[n][n];int num;}GRAPH;

void GraphInit(GRAPH *L){ L->num=0;}

int GraphVexs(GRAPH *L){ return(L->num);}

void GraphCreate(GRAPH *L){ int i,j;GraphInit(L);printf(“請(qǐng)輸入頂點(diǎn)數(shù)目：n”);scanf(“%d”,&L->num);printf(“請(qǐng)輸入各頂點(diǎn)的信息：n”);for(i=0;inum;i++){

fflush(stdin);

scanf(“%c”,&L->vexs[i]);} printf(“請(qǐng)輸入邊權(quán)矩陣的信息：n”);for(i=0;inum;i++){

for(j=0;jnum;j++)

{

scanf(“%d”,&L->arcs[i][j]);

} } printf(“圖已經(jīng)創(chuàng)建完畢！”);}

void GraphOut(GRAPH L){ int i,j;printf(“n圖的頂點(diǎn)數(shù)目為：%d”,L.num);printf(“n圖的各頂點(diǎn)的信息為：n”);for(i=0;i

for(j=0;j

{

printf(“%6d”,L.arcs[i][j]);

}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

printf(“n”);} printf(“圖已經(jīng)輸出完畢！”);}

void DFS(GRAPH g,int qidian,int mark[]){ int v1;mark[qidian]=1;printf(“%6c”,g.vexs[qidian]);for(v1=0;v1

mark[v]=0;} for(v=qidian;v

v1=v%g.num;

if(mark[v1]==0)

DFS(g,v1,mark);} } typedef int DATATYPE;typedef struct { DATATYPE data[maxsize];int front,rear;} SEQQUEUE;void QueueInit(SEQQUEUE *sq){ sq->front=0;sq->rear=0;} int QueueIsEmpty(SEQQUEUE sq){ if(sq.rear==sq.front)return(1);else return(0);} int QueueFront(SEQQUEUE sq,DATATYPE *e){ if(QueueIsEmpty(sq)){

printf(“queue is empty!n”);

return 0;}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

else {

*e=sq.data[(sq.front)];

return 1;} } int QueueIn(SEQQUEUE *sq,DATATYPE x){ if(sq->front==(sq->rear+1)%maxsize){

printf(“queue is full!n”);

return 0;} else {

sq->data[sq->rear]=x;

sq->rear=(sq->rear+1)%maxsize;

return(1);} } int QueueOut(SEQQUEUE *sq){ if(QueueIsEmpty(*sq)){

printf(“queue is empty!n”);

return 0;} else {

sq->front=(sq->front+1)%maxsize;

return 1;} } void BFS(GRAPH g,int v,int mark[]){ int v1,v2;SEQQUEUE q;QueueInit(&q);QueueIn(&q,v);mark[v]=1;printf(“%6c”,g.vexs[v]);while(QueueIsEmpty(q)==0){

QueueFront(q,&v1);

QueueOut(&q);

for(v2=0;v2

{

if(g.arcs[v1][v2]!=0&&mark[v2]==0)

{

QueueIn(&q,v2);

mark[v2]=1;

printf(“%6c”,g.vexs[v2]);

}

} } } void GraphBFS(GRAPH g){

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

int qidian,v,v1,mark[maxsize];printf(“n廣度優(yōu)先遍歷：”);printf(“n請(qǐng)輸入起點(diǎn)的下標(biāo)：”);scanf(“%d”,&qidian);for(v=0;v

mark[v]=0;} for(v=qidian;v

v1=v%g.num;

if(mark[v1]==0)

BFS(g,v1,mark);} }

void main(){ GRAPH tu;GraphCreate(&tu);GraphOut(tu);GraphDFS(tu);GraphBFS(tu);system(“pause”);getchar();}

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

1．金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

2．五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

這次的圖的操作實(shí)驗(yàn)，與樹的操作類似，但又比樹復(fù)雜，包含更多的存儲(chǔ)結(jié)構(gòu)和遍歷方法的操作，而且圖的遍歷需要沿著弧進(jìn)行，以便輸出弧上的信息。本實(shí)驗(yàn)中圖的亢奮采用鄰接表的存儲(chǔ)結(jié)構(gòu)，在輸入圖的信息時(shí)，首先要畫出圖的鄰接表信息。圖有兩種遍歷的形式，一種為深度優(yōu)先搜索，一種為廣度優(yōu)先搜索。由于能力有限，沒(méi)有能實(shí)現(xiàn)圖的深度非遞歸優(yōu)先搜索。本次實(shí)驗(yàn)基本完成了圖的操作，也學(xué)到了很多關(guān)于圖的知識(shí)和算法。

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

第二篇：算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)冊(cè)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊(cè)

課程名稱：

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

所屬院部：

（理工類）

算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級(jí)： 14計(jì)單（2）

1413201007 學(xué)生姓名： 毛卓

計(jì)算機(jī)工程學(xué)院 指導(dǎo)教師： 章海鷗 16 ——20 17 學(xué)年 第 二 學(xué)期

金陵科技學(xué)院教務(wù)處制

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告書寫要求

實(shí)驗(yàn)報(bào)告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點(diǎn)需打印的，要遵照以下字體、字號(hào)、間距等的具體要求。紙張一律采用A4的紙張。

實(shí)驗(yàn)報(bào)告書寫說(shuō)明

實(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)容與過(guò)程；實(shí)驗(yàn)結(jié)果與分析。各院部可根據(jù)學(xué)科特點(diǎn)和實(shí)驗(yàn)具體要求增加項(xiàng)目。

填寫注意事項(xiàng)

（1）細(xì)致觀察，及時(shí)、準(zhǔn)確、如實(shí)記錄。（2）準(zhǔn)確說(shuō)明，層次清晰。

（3）盡量采用專用術(shù)語(yǔ)來(lái)說(shuō)明事物。

（4）外文、符號(hào)、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號(hào)。（5）應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。

實(shí)驗(yàn)報(bào)告批改說(shuō)明

實(shí)驗(yàn)報(bào)告的批改要及時(shí)、認(rèn)真、仔細(xì)，一律用紅色筆批改。實(shí)驗(yàn)報(bào)告的批改成績(jī)采用百分制，具體評(píng)分標(biāo)準(zhǔn)由各院部自行制定。

實(shí)驗(yàn)報(bào)告裝訂要求

實(shí)驗(yàn)批改完畢后，任課老師將每門課程的每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)報(bào)告以自然班為單位、按學(xué)號(hào)升序排列，裝訂成冊(cè)，并附上一份該門課程的實(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)1 順序表

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

掌握順序表的定位、插入、刪除等操作。

二、實(shí)驗(yàn)儀器和設(shè)備

VC6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測(cè)試結(jié)果。

（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號(hào)（序號(hào)從0開始編號(hào)）；如果不存在，返回－1。編寫主函數(shù)測(cè)試結(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è)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。

程序清單：

（1）:/*編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。*/ #include typedef int datatype;#define maxsize 1024 typedef struct { datatype data[maxsize];int last;

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

}sequenlist;void main(){ sequenlist L;int i,n;printf(“請(qǐng)輸入元素個(gè)數(shù)：”);scanf(“%d”,&n);printf(“n請(qǐng)輸入元素：”);for(i=0;i

如果不存在，返回－1。*/ #include typedef int datatype;#define maxsize 1024 typedef struct { datatype data[maxsize];int last;}sequenlist;

int fun(sequenlist L,int x,int n){

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

} int i;for(i=0;i

} int i,n,y;int x;

printf(“請(qǐng)輸入元素個(gè)數(shù)：”);scanf(“%d”,&n);printf(“n請(qǐng)輸入元素：”);for(i=0;i

printf(“n請(qǐng)輸入要查找的數(shù)據(jù)元素：”);scanf(“%d”,&x);y=fun(L,x,n);if(y==-1)else printf(“n數(shù)據(jù)元素 %d 所在的位置為 %d n”,x,y);printf(“n所要查找的數(shù)據(jù)元素不存在。n”);(3): /*在遞增有序的順序表中插入一個(gè)新結(jié)點(diǎn)x，保持順序表的有序性。

解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；

從第一個(gè)元素開始找到第一個(gè)大于該新結(jié)點(diǎn)值x的元素位置i即為插入位置；

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

然后將從表尾開始依次將元素后移一個(gè)位置直至元素i；最后將新結(jié)點(diǎn)x插入到i位置。*/ #define maxsize 100 typedef struct{

int data[maxsize];

int last;}sequenlist;main(){

int i,x,j;

sequenlist l={{1,3,5,6,7,9},5};

printf(“n插入元素前的數(shù)據(jù)為:”);

for(i=0;i<=l.last;i++)

printf(“%2d”,l.data[i]);

printf(“n請(qǐng)輸入要插入的元素:”);

scanf(“%d”,&x);

for(i=1;i<=l.last;i++)

if(l.data[i-1]>x)break;

if(i>l.last)

{

l.data [l.last +1]=x;

}

else

{

for(j=l.last;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x;

}

l.last++;

printf(“插入元素后的數(shù)據(jù)為:n”);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

for(j=0;j<=l.last;j++)

printf(“%3d”,l.data[j]);

printf(“n”);}(4): /*刪除順序表中所有等于X的數(shù)據(jù)元素。*/ #define maxsize 100 typedef struct{

int data[maxsize];

int last;}sequenlist;main(){

int i,j,x=0,k=0;

sequenlist L={{1,3,5,7,2,4,6,8,2,9},9};

printf(“n原數(shù)據(jù)為:”);

for(i=0;i<=L.last;i++)printf(“%3d”,L.data[i]);

printf(“n請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):”);

scanf(“%d”,&x);

for(i=1;i<=L.last+1;i++)

if(L.data[i-1]==x){

for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j];

L.last--;

i--;

k=1;

}

if(k==1){

printf(“刪除后的數(shù)據(jù)為:n”);

for(j=0;j<=L.last;j++)printf(“%3d”,L.data[j]);

}

else printf(“Not found!n”);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

printf(“n”);}

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）（1）結(jié)果： 請(qǐng)輸入元素個(gè)數(shù)：5

請(qǐng)輸入元素：1 2 3 4 5

元素輸出：1 2 3 4 5（2）結(jié)果： 請(qǐng)輸入元素個(gè)數(shù)：5

請(qǐng)輸入元素：1 2 3 4 5

請(qǐng)輸入要查找的數(shù)據(jù)元素：5

數(shù)據(jù)元素5所在的位置為 4（3）結(jié)果：插入數(shù)據(jù)前的元素為：1 3 5 6 7 9

請(qǐng)輸入要插入的元素為：10

插入元素后的數(shù)據(jù)為:

5 6 7 9 10（4）結(jié)果：原數(shù)據(jù)為：1 3 5 7 2 4 6 8 2 9

請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)為：7

刪除后的數(shù)據(jù)為： 3 5 2 4 6 8 2 9

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(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）注意鏈表的空間是動(dòng)態(tài)分配的，某結(jié)點(diǎn)不用之后要及時(shí)進(jìn)行物理刪除，以便釋放其內(nèi)存空間。

（2）鏈表不能實(shí)現(xiàn)直接定位，一定注意指針的保存，防止丟失。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

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ù)測(cè)試結(jié)果。

2、選做題

已知指針LA和LB分別指向兩個(gè)無(wú)頭結(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)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)3 堆棧和隊(duì)列

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

（1）掌握應(yīng)用棧解決問(wèn)題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。

（3）掌握隊(duì)列的存儲(chǔ)結(jié)構(gòu)及基本操作實(shí)現(xiàn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）判斷一個(gè)算術(shù)表達(dá)式中開括號(hào)和閉括號(hào)是否配對(duì)。（2）測(cè)試“漢諾塔”問(wèn)題。

（3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個(gè)算法判別讀入的一個(gè)以’@’為結(jié)束符的字符序列是否是“回文”。

2、選做題

在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)輸出受限的雙端循環(huán)隊(duì)列的入列和出列算法。設(shè)每個(gè)元素表示一個(gè)待處理的作業(yè)，元素值表示作業(yè)的預(yù)計(jì)時(shí)間。入隊(duì)列采取簡(jiǎn)化的短作業(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)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)4 串

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

掌握串的存儲(chǔ)及應(yīng)用。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）編寫輸出字符串s中值等于字符ch的第一個(gè)字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。

（2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測(cè)試結(jié)果。

解題思路：可以將第一題程序改進(jìn)成一個(gè)子函數(shù)，在本題中循環(huán)調(diào)用。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編程刪除串s從位置i開始長(zhǎng)度為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)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)5 二叉樹

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

（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問(wèn)題的方法。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）建立一棵二叉樹。對(duì)此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。

（2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點(diǎn)總數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。

2、選做題

已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲(chǔ)結(jié)點(diǎn)的值。試編寫算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹的二叉鏈表。

解題思路：根據(jù)完全二叉樹順序存儲(chǔ)的性質(zhì)來(lái)確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹順序存儲(chǔ)的一個(gè)重要性質(zhì)為，第i個(gè)結(jié)點(diǎn)的左孩子是編號(hào)為2i的結(jié)點(diǎn)，第i個(gè)結(jié)點(diǎn)的右孩子是編號(hào)為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)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(shí)間：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)6 圖

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

（1）熟練掌握?qǐng)D的基本概念、構(gòu)造及其存儲(chǔ)結(jié)構(gòu)。

（2）熟練掌握對(duì)圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）構(gòu)造一個(gè)無(wú)向圖（用鄰接矩陣表示存儲(chǔ)結(jié)構(gòu)）。

（2）對(duì)上面所構(gòu)造的無(wú)向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。

2、選做題

采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無(wú)向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長(zhǎng)度為k的簡(jiǎn)單路徑的算法。簡(jiǎn)單路徑是指其頂點(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)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(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è)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

用隨機(jī)數(shù)產(chǎn)生100000個(gè)待排序數(shù)據(jù)元素的關(guān)鍵字值。測(cè)試下列各排序函數(shù)的機(jī)器實(shí)際執(zhí)行時(shí)間（至少測(cè)試兩個(gè)）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序和基于鏈?zhǔn)疥?duì)列的基數(shù)排序。

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)告

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

金陵科技學(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)成績(jī)： 批改教師： 批改時(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è)備

Visual C++6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）在一個(gè)遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。

2、選做題

（2）構(gòu)造一個(gè)哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設(shè)計(jì)一個(gè)測(cè)試程序進(jìn)行測(cè)試。

提示：構(gòu)造哈希表只是完成查找的第一步，大家應(yīng)該掌握在哈希表上進(jìn)行查找的過(guò)程，可以試著編程序?qū)崿F(xiàn)。程序清單：

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

第三篇：算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)冊(cè)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 冊(cè)

課程名稱：

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

所屬院部：

（理工類）

算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級(jí)：

學(xué)生姓名：

指導(dǎo)教師： 14 ——20 15 學(xué)年 第 二 學(xué)期

金陵科技學(xué)院教務(wù)處制

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告書寫要求

實(shí)驗(yàn)報(bào)告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點(diǎn)需打印的，要遵照以下字體、字號(hào)、間距等的具體要求。紙張一律采用A4的紙張。

實(shí)驗(yàn)報(bào)告書寫說(shuō)明

實(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)容與過(guò)程；實(shí)驗(yàn)結(jié)果與分析。各院部可根據(jù)學(xué)科特點(diǎn)和實(shí)驗(yàn)具體要求增加項(xiàng)目。

填寫注意事項(xiàng)

（1）細(xì)致觀察，及時(shí)、準(zhǔn)確、如實(shí)記錄。（2）準(zhǔn)確說(shuō)明，層次清晰。

（3）盡量采用專用術(shù)語(yǔ)來(lái)說(shuō)明事物。

（4）外文、符號(hào)、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號(hào)。（5）應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。

實(shí)驗(yàn)報(bào)告批改說(shuō)明

實(shí)驗(yàn)報(bào)告的批改要及時(shí)、認(rèn)真、仔細(xì)，一律用紅色筆批改。實(shí)驗(yàn)報(bào)告的批改成績(jī)采用百分制，具體評(píng)分標(biāo)準(zhǔn)由各院部自行制定。

實(shí)驗(yàn)報(bào)告裝訂要求

實(shí)驗(yàn)批改完畢后，任課老師將每門課程的每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)報(bào)告以自然班為單位、按學(xué)號(hào)升序排列，裝訂成冊(cè)，并附上一份該門課程的實(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)成績(jī)： 批改教師： 批改時(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

三、實(shí)驗(yàn)內(nèi)容與過(guò)程（含程序清單及流程圖）

1、必做題

（1）編寫程序建立一個(gè)順序表，并逐個(gè)輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測(cè)試結(jié)果。

（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個(gè)數(shù)據(jù)元素的序號(hào)（序號(hào)從0開始編號(hào)）；如果不存在，返回－1。編寫主函數(shù)測(cè)試結(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è)按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。

程序清單：

1、(1)#include #include #define maxsize 100 typedef int datatype;typedef struct {

datatype a[maxsize];

int size;}sequence_list;sequence_list mylist;void display(sequence_list slt)

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{

int i;

if(slt.size==0)

printf(“n 順表表是空的”);

else

for(i=0;i

printf(“%5d”,slt.a[i]);} void init(sequence_list *slt){

slt->size=0;} void main(){ int i,number;init(&mylist);printf(“順序表是空的請(qǐng)建立順序表！”);printf(“n”);printf(“請(qǐng)輸入順序表中的元素個(gè)數(shù)！n”);scanf(“%d”,&number);mylist.size=number;for(i=0;i

scanf(“%d”,&mylist.a[i]);}

}(2)#include #include #define maxsize 100 typedef int datatype;typedef struct {

datatype a[maxsize];

int size;}sequence_list;sequence_list mylist;void display(sequence_list slt){

int i;display(mylist);printf(“n”);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

if(slt.size==0)

printf(“n 順表表是空的”);

else

for(i=0;i

printf(“%5d”,slt.a[i]);} void init(sequence_list *slt){

slt->size=0;} int find(sequence_list *slt,int x){ int i,a;for(i=0;isize;i++){

if(x==slt->a[i])

{

a=i;

break;

} } if(i!=slt->size)

return a;

else

return-1;} void main(){ int i,number,a,b;init(&mylist);printf(“順序表是空的請(qǐng)建立順序表！”);printf(“n”);printf(“請(qǐng)輸入順序表中的元素個(gè)數(shù)！n”);scanf(“%d”,&number);mylist.size=number;for(i=0;i

scanf(“%d”,&mylist.a[i]);} display(mylist);printf(“n”);printf(“輸入要查找的數(shù)：”);scanf(“%d”,&a);b=find(&mylist,a);

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

} if(b!=-1){ printf(“順序表的下標(biāo)為：%dn”,b);} else printf(“can not be found!”);(3)#include #include #define maxsize 100 typedef int datatype;typedef struct { datatype a[maxsize];int size;}sequence_list;sequence_list mylist;void display(sequence_list slt){ int i;if(slt.size==0)printf(“n 順表表是空的”);else for(i=0;isize=0;} void sort(sequence_list *slt){ int i,j,temp;//交換法排序

for(i=0;isize;i++){

for(j=i+1;jsize;j++)

{

if(slt->a[i]>slt->a[j])

{

temp=slt->a[i];

slt->a[i]=slt->a[j];

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

slt->a[j]=temp;

}

} } } void append(sequence_list *slt,int x){ slt->a[slt->size]=x;slt->size++;sort(&mylist);} void main(){ int i,number,x;init(&mylist);printf(“順序表是空的請(qǐng)建立順序表！”);printf(“n”);printf(“請(qǐng)輸入順序表中的元素個(gè)數(shù)！n”);scanf(“%d”,&number);mylist.size=number;for(i=0;i

scanf(“%d”,&mylist.a[i]);} display(mylist);sort(&mylist);printf(“n”);display(mylist);printf(“n”);printf(“輸入要插入的元素：”);printf(“n”);scanf(“%d”,&x);append(&mylist,x);display(mylist);printf(“n”);}(4)#include #include #define maxsize 100

typedef int datatype;typedef struct

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

{ datatype a[maxsize];int size;}sequence_list;sequence_list mylist;void display(sequence_list slt){ int i;if(slt.size == 0)

printf(“n 順表表是空的”);else for(i = 0;i

printf(“%5d”, slt.a[i]);} void init(sequence_list *slt){ slt->size = 0;} void sort(sequence_list *slt){ int i, j, temp;//交換法排序

for(i = 0;isize;i++){

for(j = i + 1;jsize;j++)

{

if(slt->a[i]>slt->a[j])

{

temp = slt->a[i];

slt->a[i] = slt->a[j];

slt->a[j] = temp;

}

} } } void del(sequence_list *slt, int x){ int m[maxsize];int i, n = 0, j, a = 0;for(i = 0;isize;i++){

if(slt->a[i]!= x)

{

金陵科技學(xué)院實(shí)驗(yàn)報(bào)告

m[n++] = slt->a[i];

}

else a++;

} slt->size = slt->size1, from, to, denpend_on);//先將初始塔的前n-1個(gè)盤子借助目的塔移動(dòng)到借用塔上

move(n, from, to);//將剩下的一個(gè)盤子移動(dòng)到目的塔上

hanoi(n1);} int IsPalindrome(char * str){ int len = StrLen(str);int i = 0;for(;i

if(str[i]!= str[len1])return 0;} return 1;} void main(){ char * str =(char *)malloc(INIT_SIZE * sizeof(char));char ch;int i = 0;//字符串當(dāng)前字符數(shù)

int len = INIT_SIZE;//字符串空間大小

while(ch = getchar()){ // 循環(huán)錄入字符串

if(ch == '@'){ ///如果按回車鍵,則結(jié)束

str[i] = '