1、金陵科技學院實驗報告學 生 實 驗 報 告 冊（理工類）課程名稱：算法與數據結構 專業班級：14計算機科學與技術1 學生學號： 1413101001 學生姓名： 王成 所屬院部： 計算機工程 指導教師： 徐永華 20 15 20 16 學年 第 二 學期 金陵科技學院教務處制實驗報告書寫要求實驗報告原則上要求學生手寫，要求書寫工整。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。實驗報告書寫說明實驗報告中一至四項內容為必填項，包括實驗目的和要求；實驗儀器和設備；實驗內容與過程；實驗結果與分析。各院部可根據學科特點和實驗具體要求增加項目。填寫注意事項（1）細

2、致觀察，及時、準確、如實記錄。（2）準確說明，層次清晰。（3）盡量采用專用術語來說明事物。（4）外文、符號、公式要準確，應使用統一規定的名詞和符號。（5）應獨立完成實驗報告的書寫，嚴禁抄襲、復印，一經發現，以零分論處。實驗報告批改說明實驗報告的批改要及時、認真、仔細，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標準由各院部自行制定。實驗報告裝訂要求實驗批改完畢后，任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。實驗項目名稱： 順序表 實驗學時： 2 同組學生姓名： 實驗地點： A101 實驗日期： 4.5 實驗成績：

3、 批改教師： 批改時間： 實驗1 順序表一、實驗目的和要求掌握順序表的定位、插入、刪除等操作。二、實驗儀器和設備Turbo C 2.0三、實驗內容與過程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個順序表，并逐個輸出順序表中所有數據元素的值。編寫主函數測試結果。（2） 編寫順序表定位操作子函數，在順序表中查找是否存在數據元素x。如果存在，返回順序表中和x值相等的第1個數據元素的序號（序號從0開始編號）；如果不存在，返回1。編寫主函數測試結果。（3） 在遞增有序的順序表中插入一個新結點x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第

4、一個大于該新結點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結點x插入到i位置。（4） 刪除順序表中所有等于X的數據元素。2、選做題（5） 已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。程序清單：#include <stdio.h>#define maxsize 32typedef structint datamaxsize;int length;sequenlist;void setup(sequenlist *a)int i;printf(&quo

5、t;要輸入幾個數:n");scanf("%d",&a->length);if(a->length<=maxsize)for(i=0;i<a->length;i+)printf("請輸入數字:n");scanf("%d",&a->datai);elseprintf("溢出n");int locate(sequenlist a,int x)int i;for(i=0;i<a.length;i+)if(a.datai=x)return i;return

6、-1;int insert(sequenlist *a,int x)int i,j;if(a->length=maxsize)printf("溢出");return -1;for(i=0;i<a->length;i+)if(a->datai>x)for(j=a->length-1;j>=i;j-)a->dataj+1=a->dataj;a->datai=x;a->length+;return 1;a->dataa->length=x;a->length+;void Delete(sequen

7、list *a,int x)int i,j;for(i=0,j=0;i<a->length;i+)if(a->datai=x)for(j=i;j<(a->length);j+)a->dataj=a->dataj+1;a->length-;i-;void combine(sequenlist *a,sequenlist *b,sequenlist *c)int i,j;if(a->length+b->length)>maxsize)printf("溢出");elsefor(i=(a->length-1),

8、j=(b->length-1);i>=0|j>=0;)if(a->datai>b->dataj)c->datac->length=a->datai; c->length+; i-; elsec->datac->length=b->dataj; c->length+; j-;main()int i,x;sequenlist a,b,c;c.length=0;setup(&a);for(i=0;i<a.length;i+)printf("%5d",a.datai);printf(&

9、quot;n請輸入要找的數:n");scanf("%d",&x);if(locate(a,x)!=-1)printf("該元素的序號:%dn",locate(a,x);elseprintf("未找到n");printf("請輸入插入的數:n");scanf("%d",&x);insert(&a,x);for(i=0;i<a.length;i+)printf("%5d",a.datai);printf("n輸入要刪除的數:n&q

10、uot;);scanf("%d",&x);Delete(&a,x);for(i=0;i<a.length;i+)printf("%5d",a.datai);printf("n");setup(&b);combine(&a,&b,&c);for(i=0;i<c.length;i+)printf("%5d",c.datai);四、實驗結果與分析（程序運行結果及其分析）五、實驗體會（遇到問題及解決辦法，編程后的心得體會）這次編程總的來說還是很簡單的，但在編程過程

11、中一定要考慮邊界條件，以免出現數據溢出。實驗項目名稱： 單鏈表 實驗學時： 2 同組學生姓名： 實驗地點： A101 實驗日期： 2016.4.12 實驗成績： 批改教師： 批改時間： 實驗2 單鏈表一、實驗目的和要求1、實驗目的掌握單鏈表的定位、插入、刪除等操作。2、實驗要求（1）注意鏈表的空間是動態分配的，某結點不用之后要及時進行物理刪除，以便釋放其內存空間。（2）鏈表不能實現直接定位，一定注意指針的保存，防止丟失。二、實驗儀器和設備Turbo C 2.0三、實驗內容與過程（含程序清單及流程圖）1、必做題（1） 編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數據元素。（2） 在遞增有序的單

12、鏈表中插入一個新結點x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進行插入操作；從第一個結點開始找到第一個大于該新結點值的結點即為插入位置；然后在找到的此結點之前插入新結點；注意保留插入位置之前結點的指針才能完成插入操作。（3） 編寫實現帶頭結點單鏈表就地逆置的子函數，并編寫主函數測試結果。2、選做題已知指針LA和LB分別指向兩個無頭結點單鏈表的首元結點。要求編一算法實現，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單：#include <stdio.h>typedef struct nodeint data;struct no

13、de *next;linklist;linklist *create()int i;linklist *head,*p,*r;head=(linklist*)malloc(sizeof(linklist);r=head;printf("輸入幾個數據:n");scanf("%d",&head->data);for(i=0;i<head->data;i+)printf("請輸入數據:n");p=(linklist*)malloc(sizeof(linklist);scanf("%d",&

14、;p->data);r->next=p;r=p;r->next=NULL;return head;void display(linklist *head) linklist *p;p=head->next;doprintf("%4d",p->data);p=p->next;while(p);printf("n");void sort(linklist *head)linklist *p,*q;int x;for(p=head->next;p->next!=NULL;p=p->next)for(q=p-

15、>next;q!=NULL;q=q->next)if(p->data>q->data)x=p->data;p->data=q->data;q->data=x;void insert(linklist *head)int x;linklist *p,*r;printf("輸入要插入的數:n");scanf("%d",&x);r=(linklist*)malloc(sizeof(linklist);r->data=x;p=head->next;while(p->data<x

16、&&p->next!=NULL)p=p->next;if(p->next=NULL)p->next=r;r->next=NULL;else r->next=p->next; p->next=r;head->data+;void ni(linklist *head)linklist *p,*r;int i,j,n;r=head->next;j=head->data;while(j>head->data /2) p=head; i=0; while(p->next!=NULL&&i&

17、lt;j) p=p->next; i+; n=p->data; p->data=r->data; r->data=n; j-; r=r->next;main()linklist *head;head=create();display(head);sort(head);printf("輸出排序后的:n");display(head);insert(head);display(head);ni(head);display(head);四、實驗結果與分析（程序運行結果及其分析）五、實驗體會（遇到問題及解決辦法，編程后的心得體會）在這次試驗中，我

18、學會了單鏈表的建立，插入，刪除等基本操作。剛開始時，由于對單鏈表的操作不是很熟悉出現了很多錯誤，但在翻閱書本后還是一一解決了。單鏈表比起數組，它的插入，刪除等操作要更簡便，不會浪費存儲空間。實驗項目名稱： 堆棧和隊列 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 實驗3 堆棧和隊列一、實驗目的和要求（1）掌握應用棧解決問題的方法。（2）掌握利用棧進行表達式求和的算法。（3）掌握隊列的存儲結構及基本操作實現，并能在相應的應用問題中正確選用它們。二、實驗儀器和設備Turbo C 2.0三、實驗內容與過程（含程序清單及流程圖）1、必做題（1） 判斷一個算

19、術表達式中開括號和閉括號是否配對。（2） 測試“漢諾塔”問題。（3） 假設稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以為結束符的字符序列是否是“回文”。2、選做題在順序存儲結構上實現輸出受限的雙端循環隊列的入列和出列算法。設每個元素表示一個待處理的作業，元素值表示作業的預計時間。入隊列采取簡化的短作業優先原則，若一個新提交的作業的預計執行時間小于隊頭和隊尾作業的平均時間，則插入在隊頭，否則插入在隊尾。程序清單：#include <stdio.h> #define maxsize 160 typedef struct int top; char datamax

20、size; Stack;void Push(Stack *s, char ch) if (maxsize - 1 = s->top) printf("棧空間已滿!"); return; else +s->top; s->datas->top = ch; char Pop(Stack *s) char ch; if (-1 = s->top) printf("空棧!"); return '0' else ch = s->datas->top; -s->top; return ch; int m

21、ain() int i = 0; Stack s; char chmaxsize; gets(ch); s.top=-1; if (ch = NULL | *ch = '0') printf("匹配n"); while (chi != '0') if (chi = '(') Push(&s,chi); else if (chi = ')') if (s.top = -1) printf("不匹配n");exit(0); else Pop(&s); i+; if (s.top

22、!= -1) printf("不匹配n"); else printf("匹配n"); 1.（2）#include<stdio.h>int i;void move(int n,char a,char c) printf("第%d步：將%d號盤子%c->%cn",i+,n,a,c);void hanno(int n,char a,char b,char c)if(n=1)move(1,a,c);elsehanno(n-1,a,c,b);move(n,a,c);hanno(n-1,b,a,c);main()int n;ch

23、ar a,b,c;printf("請輸入要移動的盤子數n");scanf("%d",&n);a='A'b='B'c='C'hanno(n,a,b,c);1.（3）#include<stdio.h>#include<string.h>char s100;int huiwen(char s)int i,j=0;char b100;for(i=0;si!=''i+);for(i=i-1;i>=0;i-)bj=si;j+;j=0;for(i=0;si!='

24、;'i+) if(si!=bj) return 0; j+;return 1;main()while(1)printf("請輸入字符直到n");gets(s);if(huiwen(s)printf("是回文n");elseprintf("不是回文n");2.#include<stdio.h>#define maxsize 100typedef struct duilieint amaxsize;int head;int rear;dui;dui *s;void init(dui *s)s->head=maxs

25、ize-1;s->rear=maxsize-1;s->as->head=0;s->as->rear=0;void setup(dui *s,int x)if(x<(s->as->head+s->as->rear)/2)s->head=(s->head-)%maxsize;s->as->head=x;elses->rear=(s->rear+)%maxsize;s->as->rear=x;void display(dui *s)printf("s隊為：");while(

26、s->head=s->rear) printf("%-3d",s->as->head); s->head=(s->head+)%maxsize;main()int x;while(1)printf("請輸入x直到0n");scanf("%d",&x);setup(s,x);if(x=0)break;if(s->head!=(s->rear+1)%maxsize)printf("隊滿n");display(s);四、實驗結果與分析（程序運行結果及其分析）1.(1

27、) 1.(2)1.(3)2.五、實驗體會（遇到問題及解決辦法，編程后的心得體會）棧和隊列是操作受限的單鏈表，在許多實際問題，運用棧和隊列會有效地使解題的思路更加清晰。實驗項目名稱： 串 實驗學時： 2 同組學生姓名： 實驗地點： A101 實驗日期： 2016.4.26 實驗成績： 批改教師： 批改時間： 實驗4 串一、實驗目的和要求掌握串的存儲及應用。二、實驗儀器和設備Turbo C 2.0三、實驗內容與過程（含程序清單及流程圖）1、必做題（1） 編寫輸出字符串s中值等于字符ch的第一個字符的函數，并用主函數測試結果。（2） 編寫輸出字符串s中值等于字符ch的所有字符的函數，并用主函數測試結

28、果。解題思路：可以將第一題程序改進成一個子函數，在本題中循環調用。（3） 設字符串采用單字符的鏈式存儲結構，編程刪除串s從位置i開始長度為k的子串。2、選做題假設以鏈結構表示串，編寫算法實現將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯接在串T的末尾。提示：為提高程序的通用性，插入位置字符應設計為從鍵盤輸入。程序清單：#include<stdio.h>#define maxsize 128void search(char a,char ch)int i;for(i=0;ai!='0'i+)if(ch=ai)printf("找到字符:%c

29、 位置:%dn",ai,i+1);exit(0);printf("沒找到n");main()char amaxsize,ch;printf("請輸入字符串sn");gets(a);printf("請輸入要查找的字符chn");scanf("%c",&ch);search(a,ch);1.（2）#include<stdio.h>#define maxsize 128void search(char a,char ch)int i,j=0;for(i=0;ai!='0'i+

30、)if(ch=ai)printf("找到字符:%c 位置:%dn",ai,i+1);j+;if(j=0)printf("未找到");main()char amaxsize,ch;printf("請輸入字符串sn");gets(a);printf("請輸入要查找的字符chn");scanf("%c",&ch);search(a,ch);1.（3）#include<stdio.h>#include<string.h>typedef struct chuanlianch

31、ar c;struct chuanlian *next;chuan;chuan *s;chuan *setup(chuan *s)chuan *head=NULL;chuan *rear=NULL;char ch;printf("請輸入字符ch直到$n");ch=getchar();while(ch!='$') s=malloc(sizeof(chuan); s->c=ch; if(head=NULL) head=s; else rear->next=s; rear=s; ch=getchar();if(rear!=NULL)rear->n

32、ext=NULL;return head;void delet(chuan *chu,int i,int k)int j;chuan *p;chuan *t;if(chu=NULL)printf("空串無法刪除n");exit(0);p=chu;for(j=1;j<i-1;j+)if(p->next=NULL&&j<i-1)printf("無法找到第%d位置n",i);exit(0);p=p->next;t=p->next;for(j=1;j<k+1;j+)if(p->next=NULL&

33、&j<k+1)printf("串長度太小，無法刪除%d個元素n",k);exit(0);t=t->next;p->next=t;void display(chuan *chu) chuan *p;p=chu;if(chu=NULL)printf("空串n");exit(0);printf("%c",p->c);while(p->next!=NULL)p=p->next;printf("%c",p->c);main()int i,k;chuan *head;head=

34、setup(s);printf("請輸入要刪除字符的位置in");scanf("%d",&i);printf("請輸入要刪除字符的個數kn");scanf("%d",&k);delet(head,i,k);display(head);free(head);free(s);2.#include<stdio.h>#include<string.h>typedef struct chuanlianchar c;struct chuanlian *next;chuan;chuan *

35、s,*t;chuan *setup(chuan *chu)chuan *head=NULL;chuan *rear=NULL;char ch;printf("請輸入字符ch直到$n");ch=getchar();while(ch!='$') chu=malloc(sizeof(chuan); chu->c=ch; if(head=NULL) head=chu; else rear->next=chu; rear=chu; ch=getchar();if(rear!=NULL)rear->next=NULL;return head;void

36、insert(chuan *s1,chuan *s2,char x)chuan *p;chuan *q;p=s1;if(s1=NULL)printf("t是空串n");exit(0);if(s2=NULL)printf("s是空串n");exit(0);while(p->next!=NULL)if(p->c=x)break;p=p->next;if(p->next=NULL)p->next=s2;elseq=s2;while(q->next!=NULL)q=q->next;q->next=p->nex

37、t;p->next=s2;void display(chuan *chu) chuan *p;p=chu;if(chu=NULL)printf("空串n");exit(0);printf("%c",p->c);while(p->next!=NULL)p=p->next;printf("%c",p->c);main()char x,c;printf("建立單鏈串tn");t=setup(t); c=getchar();printf("建立單鏈串sn");s=setup

38、(s); c=getchar();printf("請輸入要在什么字符后插入n"); x=getchar();insert(t,s,x);display(t);四、實驗結果與分析（程序運行結果及其分析）1.（1）1.(2)1.(3)2.五、實驗體會（遇到問題及解決辦法，編程后的心得體會）再利用順序存儲時一定要注意字符串以0結尾，防止溢出。實驗項目名稱： 二叉樹 實驗學時： 2 同組學生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 實驗5 二叉樹一、實驗目的和要求（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應用二叉樹遞歸遍歷思想解決問題的方

39、法。二、實驗儀器和設備Turbo C 2.0三、實驗內容與過程（含程序清單及流程圖）1、必做題（1） 建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。（2） 在第一題基礎上，求二叉樹中葉結點的個數。（3） 在第一題基礎上，求二叉樹中結點總數。（4） 在第一題基礎上，求二叉樹的深度。2、選做題已知一棵完全二叉樹存于順序表sa中，sa.elem1sa.last存儲結點的值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。解題思路：根據完全二叉樹順序存儲的性質來確定二叉樹的父子關系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構造方法進行建立。完全二叉樹順序存儲的一個重要性質

40、為，第i個結點的左孩子是編號為2i的結點，第i個結點的右孩子是編號為2i+1的結點。程序清單：1.#include<stdio.h>#include<math.h>#include<malloc.h>int LEAF=0,JIEDIAN=0,DEPTH=0;typedef struct bitreechar data;struct bitree *lc,*rc;bitree,*tree;tree createtree() tree t;char x; scanf(" %c",&x); if(x='*') t=NUL

41、L; else t=(tree)malloc(sizeof(bitree); t->data=x; printf("請輸入%c結點的左孩子結點(若沒有，請輸入 *)",t->data); t->lc=createtree(); printf("請輸入%c結點的右孩子結點(若沒有，請輸入 *)",t->data); t->rc=createtree(); return t; void qianxu(tree t)if(t)printf("%c",t->data); qianxu(t->lc);

42、qianxu(t->rc);void zhongxu(tree t)if(t)zhongxu(t->lc);printf("%c",t->data); zhongxu(t->rc);void houxu(tree t)if(t) houxu(t->lc); houxu(t->rc);printf("%c",t->data);void jiedian(tree t)if(t)JIEDIAN+; jiedian(t->lc); jiedian(t->rc);void leaf(tree t)if(t)if

43、(t->lc=NULL&&t->rc=NULL)LEAF+; leaf(t->lc); leaf(t->rc);main()tree root;printf("根節點：");root=createtree();printf("前序遍歷：");qianxu(root);printf("n");printf("中序遍歷：");zhongxu(root);printf("n");printf("后序遍歷：");houxu(root);prin

44、tf("n");jiedian(root);leaf(root); DEPTH=(int)(log(JIEDIAN)/log(2)+1);printf("葉子節點數：%dn節點數：%dn深度：%dn",LEAF,JIEDIAN,DEPTH);2.#include<stdio.h>#include<math.h>#define maxsize 100#define datatype chartypedef struct shunxudatatype datamaxsize;int len;shunxu;typedef struct

45、bitreedatatype data;struct bitree *lc,*rc;tree;tree *qmaxsize;shunxu s;void createshunxu()char c;int i=0;c=getchar();s.len=0;while(c!='#') s.datai=c; s.len+; i+; c=getchar();s.datai='#'s.len+;tree *createtree()int i=0;int front,rear;tree *root,*s1;root=NULL;front=1;rear=0;while(s.datai!='#')s1=NULL;if(s.datai!='')s1=malloc(sizeof(tree);s1->data=s.datai;s1->lc=NULL;s1->rc=NULL;rear+;qrear=s1;if(rear=1)root=s1;elseif(s1&&qfront)if(rear%2=0)qfront->lc=s1;elseqfront->rc=s1;if(rear%2=1)front+;i+;return root;void qianxu(tree *t)if(