算法与数据结构实验报告25323

算法与数据结构实验报告25323.学习帮手.2015-2016学年第二学期《算法与数据结构》课程实验报告专业软件工程学生姓名成晓伟班级软件141学号1410075094实验学时16实验教师徐秀芳信息工程学院算法与数据结构实验报告25323全文共25页，当前为第1页。

算法与数据结构实验报告25323全文共25页，当前为第1页。实验一单链表的基本操作一、实验目的1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。2.掌握线性表的各种物理存储表示和C语言实现。3.掌握单链表的各种主要操作的C语言实现。4.通过实验理解线性表中的单链表存储表示与实现。二、主要仪器及耗材普通计算机三、实验内容与要求1、用C语言编写一个单链表基本操作测试程序。（1）初始化单链表（2）创建单链表（3）求单链表长度（4）输出单链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e的结点，并返回该结点指针（8）删除第i个结点（9）销毁单链表2、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。（2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。（3）主函数实现对基本操作功能的调用。3、主要代码（1）初始化单链表LinkList*InitList(){//创建一个空链表,初始化线性表 LinkList*L; L=(LinkList*)malloc(sizeof(LinkList)); L->next=NULL; returnL;}算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第2页。（2）创建单链表//头插法voidCreateListF(LinkList*L){ LinkList*s; inti=1,a=0; while(1){ printf("输入第%d个元素(0表示终止)",i++); scanf("%d",&a); if(a==0) break; s=(LinkList*)malloc(sizeof(LinkList)); s->data=a; s->next=L->next; L->next=s; }}（3）求链表长度intListLength(LinkList*L){//求链表长度intn=0;LinkList*p=L;while(p->next!=NULL){ p=p->next; n++;}return(n);}（4）在指定位置插入元素intInsertList(LinkList*L,inti,ElemTypee){ LinkList*p=L,*s; intj=0; while(p!=NULL&&j<i-1){ p=p->next; j++; }//找出要插入的位置的前一个位置 if(p==NULL){ return0; }算法与数据结构实验报告25323全文共25页，当前为第3页。算法与数据结构实验报告25323全文共25页，当前为第3页。 s=(LinkList*)malloc(sizeof(LinkList)); s->data=e; s->next=p->next; p->next=s; return1; }}（5）输出链表voidDispList(LinkList*L){//输出链表 LinkList*p=L->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n");}（6）查找链表中指定元素intGetElem(LinkList*L,inti){//查找链表中指定元素 LinkList*p=L; intj=0; while(j<i&&p!=NULL){ j++; p=p->next; } if(p==NULL){ return0; } else{ returnp->data; }}（7）查找值是e的结点并返回该指针LinkList*LocateElem(LinkList*L,ElemTypee){ //查找值是e的结点并返回该指针 inti=1; LinkList*p=L;算法与数据结构实验报告25323全文共25页，当前为第4页。算法与数据结构实验报告25323全文共25页，当前为第4页。 { if(p->data==e)returnp; } if(p==NULL){ returnNULL; }}（8）删除元素intListDelete(LinkList*L,inti,ElemType*e){//删除元素 LinkList*p=L,*q; intj=0; while(p!=NULL&&j<i-1){ p=p->next; j++; }//找到要删除元素地址的前一个地址 if(p==NULL) {return0;}//不能删除 else{ q=p->next; *e=q->data; p->next=q->next; free(q);//删除成功 return1; }}（9）销毁链表voidDestroyList(LinkList*L){//销毁链表 LinkList*pre=L,*p=L->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre);}算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第5页。……main函数：intmain(){ LinkList*L; ElemTypee; inti; L=InitList(); CreateListF(L); DispList(L); printf("输入要查找的元素位置:\n"); scanf("%d",&i); e=GetElem(L,i); printf("%d\n",e); printf("单链表长度为:%d\n",ListLength(L)); printf("输入要删除元素的位置:"); scanf("%d",&i); if(i>ListLength(L)) { printf("超出范围重新输入"); scanf("%d",&i); } if(ListDelete(L,i,&e)==0){ printf("未找到元素\n"); } elseDispList(L); printf("输入插入元素的位置和值:"); scanf("%d%d",&i,&e);InsertList(L,i,e); DispList(L);return0;算法与数据结构实验报告25323全文共25页，当前为第6页。算法与数据结构实验报告25323全文共25页，当前为第6页。4、测试数据及测试结果输入：2356122845输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。2、采用缩进格式，加足够多的注释。3、注意循环条件、边界条件等。4、善于发现问题、分析问题、解决问题，并总结思考。5、对于算法描述及实现完全理解。五、拓展提高1、若L为带头结点的单链表，删除最大值结点2、将两个单链表合并为一个单链表算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第7页。实验二循环链表的基本操作一、实验目的熟练掌握线性表的基本操作在链式循环存储结构上的实现。二、主要仪器及耗材普通计算机三、实验内容1、在上一次单链表基本操作的基础上，修改程序，将其改为单循环链表，并实现相关操作。（1）初始化单循环链表（2）创建单循环链表（3）求单循环链表长度（4）输出单循环链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e的结点，并返回该结点指针（8）删除第i个结点（9）销毁单循环链表2、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。（2）要求用不带头结点的循环链表实现。（3）具体功能测试由主函数实现。3、主要代码（1）初始化单循环链表voidinitLinkList(LinkListL)//初始化循环单链表{ L=(LinkList)malloc(sizeof(LNode)); L->next=L;//创建一个空表}（2）创建单循环链表LinkListcreat(LinkListL)//给循环链表赋值{算法与数据结构实验报告25323全文共25页，当前为第8页。 LinkL算法与数据结构实验报告25323全文共25页，当前为第8页。 intN,i=0; //printf("请输入第%d个值：",++i); while(1) { printf("请输入第%d个值：",++i); scanf("%d",&N);//输入节点的值 if(N==0)//以0为结尾 { break; } if(i==1)//当只有一个节点时 { p=(LinkList)malloc(sizeof(LNode));//给p节点分配内存空间 p->date=N; p->next=NULL; q=p; } else//当节点不为1时 { r=(LinkList)malloc(sizeof(LNode)); r->date=N; r->next=NULL; q->next=r; q=r;// } } if(q!=NULL) { q->next=p;//将尾节点指向头节点完成循环 } L=p; returnL;//返回头指针}（3）打印循环链表voidprint(LinkListL)//打印循环链表{ LinkListp;算法与数据结构实验报告25323全文共25页，当前为第9页。算法与数据结构实验报告25323全文共25页，当前为第9页。 p=L; //printf("**\n"); if(p==NULL)//当链表尾空表时 { printf("这是一个空表\n"); } while(p->next!=L)//只有当p节点不为尾节点是打印节点中的数据域 { //printf("**\n"); printf("%d",p->date); p=p->next; } printf("%d\n",p->date);//打印尾节点中的数据}（4）求链表的长度intlength(LinkListL)//求链表的长度{ LinkListp; //printf("**\n"); intn=1; //printf("**\n"); p=L; //printf("**\n"); while(p->next!=L)//当p节点不为尾节点时计数 { n++; //printf("**\n"); p=p->next; } returnn;//返回链表长度 //printf("%d****\n",n);}（5）删除指定位置的节点LinkListdel(LinkListL,intflag)//删除指定位置的节点{ LinkListp,q; inti;算法与数据结构实验报告25323全文共25页，当前为第10页。算法与数据结构实验报告25323全文共25页，当前为第10页。 q=L->next; //inti=1; if(flag==1)//当删除节点为头结点时 { while(q->next!=L)//让p节点为尾节点 { q=q->next; } L=p->next;//头结点为L->NEXT节点 q->next=L;//让尾节点指向新的头结点 free(p);//释放p } else { for(i=1;i<flag-1;i++)//让p和q节点到达指定位置 { p=p->next; q=q->next; } p->next=q->next; free(q);//删除q节点 } returnL;//返回头指针}（6）查找第i个结点元素的值intsearch1(LinkListL,intflag)//按照节点的位置返回节点中的数据{ LinkListp; inti; p=L; for(i=1;i<flag;i++)//循环找到节点的位置 { p=p->next; } returnp->date;//返回节点的数据}算法与数据结构实验报告25323全文共25页，当前为第11页。（7）查找值为e算法与数据结构实验报告25323全文共25页，当前为第11页。intsearch2(LinkListL,intdata)//按照数据来查找节点的位置{ LinkListp; inti=1; p=L; while(1) { if(p->date==data)//当查找到数据域与查找的数据相同是跳出循环 { break; } else { i++; p=p->next; } } returni;}（8）删除第i个结点LinkListinsert(LinkListL,intfalg,intdata)//指定位置插入元素{ LinkListp,s; inti; p=L; s=(LinkList)malloc(sizeof(LNode)); for(i=1;i<falg;i++)//寻找位置 { p=p->next; } s->date=data;//将data赋值给s节点 s->next=p->next; p->next=s; returnL;}（9）销毁单循环链表LinkListdestroy(LinkListL)//销毁循环链表算法与数据结构实验报告25323全文共25页，当前为第12页。算法与数据结构实验报告25323全文共25页，当前为第12页。 LinkListp,q; p=L->next; while(p!=L) { q=p->next; free(p); p=q; } free(L); L=NULL; returnL;}……main函数：intmain(){ LinkListL=NULL; intm,k,Case,Length,DAT1,flag,P,e; printf("**1.创建一个循环链表**\n"); printf("**2.打印所创建的循环链表**\n"); printf("**3.插入节点**\n"); printf("**4.删除节点**\n"); printf("**5.求循环的长度**\n"); printf("**6.查找第i节点**\n"); printf("**7.查找某个值得节点**\n"); printf("**8.销毁链表**\n"); printf("**9.删除最大节点**\n"); printf("**10.退出程序**\n"); for(;;){ printf("请输入操作的序号\n"); scanf("%d",&Case); switch(Case) { case1:initLinkList(L); L=creat(L); break;算法与数据结构实验报告25323全文共25页，当前为第13页。 case2:print(L);算法与数据结构实验报告25323全文共25页，当前为第13页。 break; case3:printf("请输入需要插入的位置(之后)及其数据\n"); scanf("%d%d",&m,&k); L=insert(L,m,k); print(L); break; case4:printf("请输入需要删除的节点\n"); scanf("%d",&Case); L=del(L,Case); print(L); //printf("%d",Length); break; case5:Length=length(L); printf("循环的长度是%d\n",Length); break; case6:printf("请输入需要查找的节点序号:"); scanf("%d",&flag); DAT1=search1(L,flag); printf("所查找的节点数据为%d\n",DAT1); break; case7:printf("输入需要查找的值\n"); scanf("%d",&e); P=search2(L,e); printf("所查找的位置是%d\n",P); break; case8:L=destroy(L); print(L); break; //case10: case9:exit(0); break; } } return0;}算法与数据结构实验报告25323全文共25页，当前为第14页。算法与数据结构实验报告25323全文共25页，当前为第14页。输入：12345输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。2、采用缩进格式，加足够多的注释。3、注意循环条件、边界条件等。算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第15页。五、拓展提高1、双向链表中间结点P后插入新结点S的算法；2、删除双向链表中间结点P后的结点Q的算法；算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第16页。实验三栈的基本操作及应用一、实验目的1、掌握栈的顺序表示和基本操作实现；2、熟练掌握栈的基本操作；3、会用栈解决一些实际应用；4、掌握十进制数转化为N进制整数的工作原理。二、主要仪器及耗材普通计算机三、实验内容1、栈的基本运算（1）InitStack(SqStack*s)//初始化栈（2）Push(SqStack*s,SElemTypee)//入栈操作（3）pop(SqStack*s,SElemTypee)//出栈操作（4）GetTop(SqStack*s,SElemTypee)//取栈顶元素（5）IsEmpty(SqStack*s)//判断是否为空（6）GetLength(SqStack*s)//求栈的长度2、创建一个长度为100的顺序栈T，每个数据元素的类型为字符型char。编写代码，利用栈的基本运算和顺序栈T，正序输入并存储26个英文字母A—Z，然后逆序输出。3、利用栈的基本运算，写出十进制转化为二进制（八进制呢？十六进制呢？N进制呢？）的具体实现，并输出。4、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。（2）要求用不带头结点的循环链表实现。（3）具体功能测试由主函数实现。5、主要代码（1）初始化栈voidInitStack(sqStack*s)//初始化栈,构造一个空栈{ s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//动态分配存储空间 if(!s->base)算法与数据结构实验报告25323全文共25页，当前为第17页。算法与数据结构实验报告25323全文共25页，当前为第17页。 s->top=s->base;//栈空标记 s->stacksize=STACK_INIT_SIZE;}（2）取栈顶元素intGetTop(sqStack*s,ElemTypee)//取栈顶元素{*(s->top)=e; returne;}（3）元素入栈voidpush(sqStack*s,ElemTypee)//元素入栈{if(s->top-s->base>=s->stacksize) { s->base=(ElemType*)realloc(s->base,(s->stacksize+STACK_INIT_SIZE)*sizeof(ElemType));//栈满,追加存储空间 if(!s->base) exit(0); } *(s->top)=e;//输入元素e s->top++;//栈顶指针++}（4）元素出栈voidpop(sqStack*s,ElemType*e)//出栈{if(s->top==s->base)return;// *e=*--(s->top);}（5）求栈的长度intstacklen(sqStacks)//栈的长度{return(s.top-s.base);}（6）判断是否栈空intstackempty(sqStack*s)//判断是否栈空算法与数据结构实验报告25323全文共25页，当前为第18页。算法与数据结构实验报告25323全文共25页，当前为第18页。if(s->top==s->base) return1;else return0;}（7）十进制转化为八进制voidconversion()//十进制转化为八进制{sqStacks; intn,t; ElemTypee; InitStack(&s); printf("请输入正整数:"); scanf("%d",&n); t=n; while(n) { push(&s,n%8); n=n/8; } printf("十进制%d转化为八进制为:",t); while(!stackempty(&s)) { pop(&s,&e); printf("%d",e); } printf("\n");}（8）二进制转化为十进制voidBintoDec()//二进制转化为十进制{ElemTypech; sqStacks; intlen,i,sum=0; InitStack(&s); printf("请输入二进制数，输入#表示结束！\n");算法与数据结构实验报告25323全文算法与数据结构实验报告25323全文共25页，当前为第19页。 while(ch!='#') { push(&s,ch); scanf("%c",&ch); } getchar();//清除缓冲区 len=stacklen(s);printf("栈的当前容量是:%d\n",len); for(i=0;i<len;i++) { pop(&s,&ch); sum=sum+(ch-48)*pow(2,i); } printf("转化为十进制数是%d\n",sum);}（9）26个字母逆序输出voidAZZA()//字母逆序输出{ElemTypech[26],e; sqStacks; intlen,i; for(i=0;i<26;i++) ch[i]='A'+i; InitStack(&s); for(i=0;i<26;i++) { push(&s,ch[i]); } len=stacklen(s); printf("栈的当前容量是:%d\n",len); while(!stackempty(&s)) { pop(&s,&e); printf("%c",e); } printf("\n");}算法与数据结构实验报告算法与数据结构实验报告25323全文共25页，当前为第20页。……main函数intmain(){AZZA();printf("\n");BintoDec();printf("\n");conversion();return0;}6、测试数据及测试结果输入：1034输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。2、注意栈空和栈满的条件判断。3、进制转换时余数的存储及输出。五、拓展提高*1、输入一个包含’（’和’）’的字符串，检测括号是否匹配（其中括号中能嵌套括号），并输出括号是否匹配的信息（匹配，缺少左括号，缺少右括号）。*2、输入一个整数表达式，计算出其值，然后输出。（学习表达式的后缀形式及后缀表达式的计算方法）算法与数据结构实验报告25323全文共25页，当前为第21页。**3、汉诺塔问题求解。算法与数据结构实验报告25323全文共25页，当前为第21页。实验四队列的基本操作及应用一、实验目的1、会定义顺序队列和链队的结点类型；2、熟练队列的入队和出队代表的实际意义；3、掌握两种存储结构下队列的基本操作：入队、出队和输出队列等；4、熟悉C语言中函数的定义和调用。二、主要仪器及耗材普通计算机三、实验内容1、建立队列并输出2、插入元素后输出队列3、删除元素后输出队列要求：在输入数据的过程中程序做相应的是否继续输入的提示。每个功能用不同函数实现4、实验要求（1）程序中用户可以选择上述基本操作。程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。（2）要求用不带头结点的循环链表实现。（3）具体功能测试由主函数实现。5、主要代码（1）初始化队列/*初始化*/voidInitQueue(sqQueue*&q){ q=(sqQueue*)malloc(sizeof(sqQueue));//动态分配存储空间 q->front=q->rear=0;}/*初始化队列,构造一个空队列*/（2）判断队列是否为空intQueueEmpty(sqQueue*q){ if(q->rear==q->front) return