《算法与数据结构实验--14计统一--1413101001--王成.doc》由会员分享，可在线阅读，更多相关《算法与数据结构实验--14计统一--1413101001--王成.doc（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date算法与数据结构实验-14计统一-1413101001-王成金 陵 科 技 学 院学 生 实 验 报 告 册（理工类）课程名称：算法与数据结构 专业班级：14计算机科学与技术1 学生学号： 1413101001 学生姓名： 王成 所属院部： 计算机工程 指导教师： 徐永华 20 15 20 16 学年 第 二 学期 金陵科技学院教务处制实验报告书写要求实验报告原则上要求
2、学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。实验报告书写说明实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。填写注意事项（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。（3）尽量采用专用术语来说明事物。（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。实验报告批改说明实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百
3、分制，具体评分标准由各院部自行制定。实验报告装订要求实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。-实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： A101 实验日期： 4.5 实验成绩： 批改教师： 批改时间： 实验1 顺序表一、实验目的和要求掌握顺序表的定位、插入、删除等操作。二、实验仪器和设备Turbo C 2.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。（2） 编写顺序表定位操作子函数，在
4、顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回1。编写主函数测试结果。（3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。（4） 删除顺序表中所有等于X的数据元素。2、选做题（5） 已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同
5、的元素）。程序清单：#include #define maxsize 32typedef structint datamaxsize;int length;sequenlist;void setup(sequenlist *a)int i;printf(要输入几个数:n);scanf(%d,&a-length);if(a-length=maxsize)for(i=0;ilength;i+)printf(请输入数字:n);scanf(%d,&a-datai);elseprintf(溢出n);int locate(sequenlist a,int x)int i;for(i=0;ilength=m
6、axsize)printf(溢出);return -1;for(i=0;ilength;i+)if(a-dataix)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(sequenlist *a,int x)int i,j;for(i=0,j=0;ilength;i+)if(a-datai=x)for(j=i;jlength);j+)a-dataj=a-dataj+1;a-length-;i-;void combine(seq
7、uenlist *a,sequenlist *b,sequenlist *c)int i,j;if(a-length+b-length)maxsize)printf(溢出);elsefor(i=(a-length-1),j=(b-length-1);i=0|j=0;)if(a-dataib-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;ia.leng
8、th;i+)printf(%5d,a.datai);printf(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;ia.length;i+)printf(%5d,a.datai);printf(n输入要删除的数:n);scanf(%d,&x);Delete(&a,x);for(i=0;ia.length;i+)printf(%5d,a.datai);print
9、f(n);setup(&b);combine(&a,&b,&c);for(i=0;ic.length;i+)printf(%5d,c.datai);四、实验结果与分析（程序运行结果及其分析）五、实验体会（遇到问题及解决办法，编程后的心得体会）这次编程总的来说还是很简单的，但在编程过程中一定要考虑边界条件，以免出现数据溢出。实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： A101 实验日期： 2016.4.12 实验成绩： 批改教师： 批改时间： 实验2 单链表一、实验目的和要求1、实验目的掌握单链表的定位、插入、删除等操作。2、实验要求（1）注意链表的空间是动态分配的，某结
10、点不用之后要及时进行物理删除，以便释放其内存空间。（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。二、实验仪器和设备Turbo C 2.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2） 在递增有序的单链表中插入一个新结点x，保持单链表的有序性。解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。（3） 编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。2、选做题已知
11、指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单：#include typedef struct nodeint data;struct node *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;idata;i+)printf(请
12、输入数据:n);p=(linklist*)malloc(sizeof(linklist);scanf(%d,&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-next;q
13、!=NULL;q=q-next)if(p-dataq-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-datanext!=NULL)p=p-next;if(p-next=NULL)p-next=r;r-next=NULL;else r-next=p-next; p-next=r;he
14、ad-data+;void ni(linklist *head)linklist *p,*r;int i,j,n;r=head-next;j=head-data;while(jhead-data /2) p=head; i=0; while(p-next!=NULL&inext; 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);dis
15、play(head);ni(head);display(head);四、实验结果与分析（程序运行结果及其分析）五、实验体会（遇到问题及解决办法，编程后的心得体会）在这次试验中，我学会了单链表的建立，插入，删除等基本操作。刚开始时，由于对单链表的操作不是很熟悉出现了很多错误，但在翻阅书本后还是一一解决了。单链表比起数组，它的插入，删除等操作要更简便，不会浪费存储空间。实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 实验3 堆栈和队列一、实验目的和要求（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。（3）
16、掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。二、实验仪器和设备Turbo C 2.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 判断一个算术表达式中开括号和闭括号是否配对。（2） 测试“汉诺塔”问题。（3） 假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。2、选做题在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在
17、队尾。程序清单：#include #define maxsize 160 typedef struct int top; char datamaxsize; 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 c
18、h; int main() 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 != -1) printf(不匹配n); else printf(匹配n); 1.（2）#includeint i;void mo
19、ve(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;char a,b,c;printf(请输入要移动的盘子数n);scanf(%d,&n);a=A;b=B;c=C;hanno(n,a,b,c);1.（3）#include#includechar s100;int huiwen(char s)in
20、t 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!=;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#define maxsize 100typedef struct duilieint amaxsize;int head;int rear;dui;dui *s;void init(d
21、ui *s)s-head=maxsize-1;s-rear=maxsize-1;s-as-head=0;s-as-rear=0;void setup(dui *s,int x)if(xas-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(s-head=s-rear) printf(%-3d,s-as-head); s-head=(s-head+)%maxsize;main()
22、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) 1.(2)1.(3)2.五、实验体会（遇到问题及解决办法，编程后的心得体会）栈和队列是操作受限的单链表，在许多实际问题，运用栈和队列会有效地使解题的思路更加清晰。实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： A101 实验日期： 2016.4.26 实验成绩： 批改教师： 批改时间：
23、实验4 串一、实验目的和要求掌握串的存储及应用。二、实验仪器和设备Turbo C 2.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。（2） 编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3） 设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。2、选做题假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。提示：为提高程序的通用性，插入位置字
24、符应设计为从键盘输入。程序清单：#include#define maxsize 128void search(char a,char ch)int i;for(i=0;ai!=0;i+)if(ch=ai)printf(找到字符:%c 位置:%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#define maxsize 128void search(char a,
25、char ch)int i,j=0;for(i=0;ai!=0;i+)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#includetypedef struct chuanlianchar c;struct chuanlian *next;chuan;chuan *s;chuan *setup(chuan
26、 *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-next=NULL;return head;void delet(chuan *chu,int i,int k)int j;chuan *p;chuan *t;if(chu=NULL)prin
27、tf(空串无法删除n);exit(0);p=chu;for(j=1;jnext=NULL&jnext;t=p-next;for(j=1;jnext=NULL&jnext;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=setup(s);printf(请输入要删除字符的位置in);scanf(%d,&i);p
28、rintf(请输入要删除字符的个数kn);scanf(%d,&k);delet(head,i,k);display(head);free(head);free(s);2.#include#includetypedef struct chuanlianchar c;struct chuanlian *next;chuan;chuan *s,*t;chuan *setup(chuan *chu)chuan *head=NULL;chuan *rear=NULL;char ch;printf(请输入字符ch直到$n);ch=getchar();while(ch!=$) chu=malloc(size
29、of(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 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;
30、if(p-next=NULL)p-next=s2;elseq=s2;while(q-next!=NULL)q=q-next;q-next=p-next;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(s); c
31、=getchar();printf(请输入要在什么字符后插入n); x=getchar();insert(t,s,x);display(t);四、实验结果与分析（程序运行结果及其分析）1.（1）1.(2)1.(3)2.五、实验体会（遇到问题及解决办法，编程后的心得体会）再利用顺序存储时一定要注意字符串以0结尾，防止溢出。实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 实验5 二叉树一、实验目的和要求（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。二、实验仪器和设备Turbo C
32、 2.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。（2） 在第一题基础上，求二叉树中叶结点的个数。（3） 在第一题基础上，求二叉树中结点总数。（4） 在第一题基础上，求二叉树的深度。2、选做题已知一棵完全二叉树存于顺序表sa中，sa.elem1sa.last存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的
33、结点，第i个结点的右孩子是编号为2i+1的结点。程序清单：1.#include#include#includeint 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=NULL; 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); qianxu(t-rc);void zhongxu(tree t)if(t)