第一篇：数据结构精品案例
实验四
一． 实验题目
请编写算法，要求：（1）交换二叉树中每一个结点的左、右孩子；
（2）求二叉树的高度；
（3）输出二叉树的所有终端结点。
二． 需求分析
此算法采用二叉树的二叉链表存储结构。先生成一棵以i为根结点的数据域信息，以二叉树lchild和rchild为左子树和右子树的二叉树。这里采取二叉树的前序遍历输入和中序遍历输出。交换二叉树的左右孩子，并输出新二叉树。计算二叉树的深度。所有函数中都要用到递归过程。
三． 详细设计
二叉树的二叉链表存储表示可描述为： typedef struct BiTNode {
char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;定义两个指向二叉树链表结点结构的指针类型：BiTree T,F;生成一棵二叉树：T=create();用中序遍历法输出二叉树的所有结点：output(T);定义整型变量a来表示二叉树的深度：a=depth(T);输出二叉树的所有终端结点：print(T);交换二叉树中每一个结点的左、右孩子并输出新二叉树：F=change(T);
output(F);
四． 调试分析
能顺利通过
五． 使用说明
按先序遍历法输入二叉树的结点，回车后将以中序遍历法输出所有结点及二叉树的深度和交换每个结点左右孩子后所得到的新二叉树。
六． 测试数据及测试结果
七． 源代码
#include
typedef struct BiTNode {
char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;
BiTree create(){ BiTree T;char i;i=getchar();if(i=='#')T=NULL;else {
T=(BiTree)malloc(sizeof(BiTNode));
T->data=i;T->lchild=create();T->rchild=create();} return(T);}
void output(BiTree T)
{
if(T!=NULL)
{
output(T->lchild);
printf(“%ct”,T->data);
output(T->rchild);
}
}
BiTree change(BiTree T){
BiTree p;if(T!=NULL)
{ if((T->lchild!=NULL)||(T->rchild!=NULL))
{
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
}
change(T->lchild);
change(T->rchild);
}
return(T);}
int depth(BiTree T){
int dl,dr,d;
if(T==NULL)d=0;
else
{
dl=depth(T->lchild);
dr=depth(T->rchild);
if(dl>dr)
d=dl+1;
else
d=dr+1;
}
return(d);}
void print(BiTree T){ if(T!=NULL){
if((T->lchild==NULL)&&(T->rchild==NULL))
printf(“%ct”,T->data);
else
{ print(T->lchild);
print(T->rchild);
}
} }
main(){ int a;BiTree T,F;T=create();printf(“the outputn”);output(T);a=depth(T);printf(“nthe depth of BiTree is:%d”,a);
printf(“nthe leaves of BiTree:n”);print(T);
F=change(T);
printf(“nthe result of BiTree changing:n”);output(F);}
after
第二篇：数据结构实验报告
注意：实验结束后提交一份实验报告电子文档
电子文档命名为“学号+姓名”，如：E01214058宋思怡
《数据结构》实验报告
（一）学号：姓名：专业年级：
实验名称：线性表
实验日期：2014年4月14日
实验目的：
1、熟悉线性表的定义及其顺序和链式存储结构；
2、熟练掌握线性表在顺序存储结构上实现基本操作的方法；
3、熟练掌握在各种链表结构中实现线性表基本操作的方法；
4、掌握用 C/C++语言调试程序的基本方法。
实验内容：
一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化顺序表L；
（2）依次在L尾部插入元素-1,21,13,24,8；
（3）输出顺序表L；
（4）输出顺序表L长度；
（5）判断顺序表L是否为空；
（6）输出顺序表L的第3个元素；
（7）输出元素24的位置；
（8）在L的第4个元素前插入元素0；
（9）输出顺序表L；
（10）删除L的第5个元素；
（11）输出顺序表L。
源代码
调试分析（给出运行结果界面）
二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
„„„„
„„„„
小结或讨论:
（1）实验中遇到的问题和解决方法
（2）实验中没有解决的问题
（3）体会和提高
第三篇：数据结构实验报告
南京信息工程大学实验（实习）报告
实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍
系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700
3实验一顺序表的基本操作及C语言实现
【实验目的】
1、顺序表的基本操作及 C 语言实现
【实验要求】
1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。
2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。
【实验内容】
1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作；
2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重
复的元素），并求这样的两个集合的并。
【实验结果】
[实验数据、结果、遇到的问题及解决]
一． Status InsertOrderList(SqList &va,ElemType x)
{
}
二． Status DeleteK(SqList &a,int i,int k)
{//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 课 程 设 计 任 务 书 信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目： 迷宫求解、一元多项式 课程设计主要参考资料： 数据结构（C语言版）严蔚敏、吴伟民 编著 数据结构题集（C语言版）严蔚敏、吴伟民、米宁 编著 数据结构课件 三、设计应解决下列各主要问题： 1.实现迷宫的路径求解，并输出最终路径，标记走过却未选择的路径和最终选择的路径 2.对一元多项式实现加法，减法，乘法，求导的计算，并按指数由大到小排序输出 四、课程设计相关附件（如：图纸、软件等）： 五、命题发出日期：2011-3-15 设计应完成日期： 2010-6-20 设计指导教师（签章）： 系主任（签章）： 指导教师对课程设计的评语 指导教师（签章）： 年 月 日 山东科技大学学生课程设计 课程设计1 迷宫问题 一、需求分析： 1.2.3.4.以二维数组Maze[][]表示迷宫 用户输入迷宫的数据：构建迷宫，行数m，列数n 迷宫的入口位置和出口位置可由用户随时设定 若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。 5.本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数做小量修改，便可求得全部路径。 二、概要设计： 抽象数据类型线性表的定义如下： ⒈ 设计栈的抽象数据类型定义： ADT Stack { 数据对象：D={ai:|ai∈PositionSet,i=1„n,n≥0} 数据关系：R1={ Push(&S,e)Pop(&S,e) 返回其值 }ADT Stack； ⒉ 迷宫的抽象数据类型定义： ADT Maze{ 数据对象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0} 数据关系：R={ROW.COL} Row={ 第1页 操作结果 构造一个空栈，完成栈用e返回栈S的栈顶元将新的元素e压入栈顶 删除栈顶元素，并用eInitStack(&S) 山东科技大学学生课程设计 Col={ 基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件：已知目前迷宫状态, 传过起始位置，和终止位置 操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }ADT MAZE 三、详细设计： #include typedef int Status; typedef struct { int r;int c;}PostType;//坐标位置 迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号 PostType seat;//通道块的当前坐标位置 int di;//通道块指向下一通道块的方向 }SElemType;//栈元素的类型 typedef struct { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的最大容量 }Stack;//栈的类型 第2页 山东科技大学学生课程设计 Status InitStack(Stack &S)//初始化栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit(OVERFLOW);//存储分配失败;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStack Status StackEmpty(Stack S)//判断栈是否为空,如果为空返回TRUE,否则返回FALSE { if(S.top==S.base) return TRUE; return FALSE;}//StackEmpty Status Push(Stack &S,SElemType e)//插入元素为e的栈顶元素 { if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT;} *S.top++=e;return OK;}//Push Status Pop(Stack &S,SElemType &e)//删除栈顶元素存入e { if(S.top==S.base) return ERROR;e=*--S.top; 第3页 山东科技大学学生课程设计 return OK;}//Pop Status DestroyStack(Stack &S)//销毁栈 { free(S.base);S.top=S.base;return OK;}//DestroyStack //maze.cpp #define MAXLEN 20//迷宫包括外墙最大行列数目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType; //迷宫类型 Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE int m,n,i,j,k=1; printf(“输入迷口的行数和列数: ”); scanf(“%d%d”,&maze.r,&maze.c);//迷宫行和列数 for(i=0;i<=maze.c+1;i++){//迷宫行外墙 maze.adr[0][i]='#'; maze.adr[maze.r+1][i]='#'; }//for for(i=0;i<=maze.r+1;i++){//迷宫列外墙 maze.adr[i][0]='#'; maze.adr[i][maze.c+1]='#'; } for(i=1;i<=maze.r;i++) for(j=1;j<=maze.c;j++) maze.adr[i][j]=' ';//初始化迷宫 printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k); scanf(“%d%d”,&m,&n); k++; while(m!=0) { if(m>maze.r || n>maze.c)//越界 第4页 山东科技大学学生课程设计 exit(ERROR); maze.adr[m][n]='#';//迷宫障碍用'#'标记 printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k); scanf(“%d%d”,&m,&n); k++; } return OK;}//InitMaze Status Pass(MazeType maze,PostType curpos){ //当前位置可通则返回TURE,否则返回FALSE if(maze.adr[curpos.r][curpos.c]==' ')//可通 return TRUE; else return FALSE;}//Pass Status FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S maze.adr[curpos.r][curpos.c]='*';//“*”表示可通 return OK;}//FootPrint PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i){ //1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1;break; case 2 : cpos.r+=1;break; case 3 : cpos.c-=1;break; case 4 : cpos.r-=1;break; default: exit(ERROR); } return cpos;}//Nextpos Status MarkPrint(MazeType &maze,PostType curpos){ //曾走过但不是通路标记并返回OK 第5页 山东科技大学学生课程设计 maze.adr[curpos.r][curpos.c]='@';//“@”表示曾走过但不通 return OK;}//MarkPrint void PrintMaze(MazeType &maze)//将最后标记好的迷宫输出 { int i,j;printf(“n输出迷宫的路径:n”);for(i=0;i<=maze.c+1;i++) printf(“%4d”,i);//输出列数 printf(“n”);for(i=0;i<=maze.r+1;i++){ printf(“%d”,i);//输出行数 for(j=0;j<=maze.c+1;j++) printf(“%4c”,maze.adr[i][j]);//输出迷宫 printf(“n”);} }//PrintMaze Status MazePath(MazeType &maze,PostType start,PostType end)//若迷宫从入口start到end的通道则求得一条存放在栈中 { Stack S;//初始化栈 PostType curpos;int curstep;SElemType e;InitStack(S);curpos=start;curstep=1;do { if(Pass(maze,curpos))//当前位置可通过而未曾走过留下足迹 { FootPrint(maze,curpos); e.ord=curstep;e.seat=curpos;e.di=1; Push(S,e);//加入栈路径中 if(curpos.r==end.r && curpos.c==end.c)//到达出口返回TRUE { 第6页 山东科技大学学生课程设计 if(!DestroyStack(S)) exit(OVERFLOW); else return TRUE; } else { curpos=NextPos(curpos,1);//下一位置是当前位置 curstep++;//探索下一步 } }//if else//当前位置不能通过 { if(!StackEmpty(S)) { Pop(S,e);//提取前一位置 while(e.di==4 &&!StackEmpty(S))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过 { MarkPrint(maze,e.seat); Pop(S,e); } if(e.di<4)//换下一个方向探索 设定当前位置为该新方向上的邻位 { e.di++; Push(S,e); curpos=NextPos(e.seat,e.di); } }//if } }while(!StackEmpty(S));if(!DestroyStack(S)) exit(ERROR);else return FALSE;}//MazePath int main(){ MazeType maze;PostType start,end;char c; 第7页 山东科技大学学生课程设计 do { printf(“**********迷宫求解**********n”); if(!InitMaze(maze)) { printf(“n 初始化迷宫失败！!”); exit(ERROR); } do { printf(“n请输入入口的坐标:”); scanf(“%d%d”,&start.r,&start.c);//输入入口坐标 if(start.r>maze.r || start.c>maze.c) printf(“n输入错误,请重新输入入口的坐标！n”); continue; } while(start.r>maze.r || start.c>maze.c); do { printf(“n请输入出口的坐标:”);//输入出口的坐标 scanf(“%d%d”,&end.r,&end.c); if(end.r>maze.r || end.c>maze.c) printf(“n输入错误,请重新输入出口坐标！n”); continue; } while(end.r>maze.r || end.c>maze.c); if(!MazePath(maze,start,end)) printf(“n不能找到一条路径！!n”); else PrintMaze(maze);//输出迷宫 printf(“是否要继续?(y/n):”); scanf(“%s”,&c);} while(c=='y' || c=='Y');}。测试结果： 第8页 四、山东科技大学学生课程设计 课程设计2 一元多项式 一、需求分析： 第9页 山东科技大学学生课程设计 1.2.3.首先定义一个结构体，其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域； 然后一一罗列每个在主程序中用到的函数，并一一实现； 最后在主程序中主要完成用户的输入和相关函数的调用。 二、概要设计： void insert(PLOYList *head,PLOYList *input) //查找位置插入新链节的函数，且让输入的多项式呈降序排列 PLOYList *creat(char ch)//输入多项式 PLOYList *add(PLOYList *head,PLOYList *pre)//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式相乘 PLOYList *der(PLOYList *head)//多项式求导 void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 void start()//用户选择界面 三、详细设计： #include //定义节点类型 { float coef; //多项式的系数 int expn; //多项式的指数 struct node * next;//结点指针域 }PLOYList;void insert(PLOYList *head,PLOYList *input) //查找位置插入新链节的函数，且让输入的多项式呈降序排列 { PLOYList *pre,*now; int signal=0; pre=head; 第10页 山东科技大学学生课程设计 if(pre->next==NULL){pre->next=input;} //如果只有一个头结点，则把新结点直接连在后面 else { now=pre->next;//如果不是只有一个头结点，则设置now指针 while(signal==0) { if(input->expn < now->expn) { if(now->next==NULL) { now->next=input; signal=1; } else { pre=now; now=pre->next;//始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面 } } else if(input->expn > now->expn) { input->next=now; pre->next=input; signal=1; }//若新结点中指数比最后一个结点即now中的指数大，则插入now之前 else//若指数相等则需合并为一个结点，若相加后指数为0则释放该结点 { now->coef=now->coef+input->coef; signal=1; free(input); if(now->coef==0) { pre->next=now->next; free(now); } }//else } //while 第11页 山东科技大学学生课程设计 }//else }//void PLOYList *creat(char ch) //输入多项式 { PLOYList *head,*input; float x; int y; head=(PLOYList *)malloc(sizeof(PLOYList)); //创建链表头 head->next=NULL; scanf(“%f %d”,&x,&y);//实现用户输入的第一个项，包括其指数和系数 while(x!=0) { input=(PLOYList *)malloc(sizeof(PLOYList));//创建新链节 input->coef=x; input->expn=y; input->next=NULL; insert(head,input);//每输入一项就将其排序，是的链表中多项式呈降序排列 scanf(“%f %d”,&x,&y); } return head;} PLOYList *add(PLOYList *head,PLOYList *pre) //多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 { PLOYList *input; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1;//若该链表为空，则无需进行加法运算，跳出循环 else { pre=pre->next; input=(PLOYList *)malloc(sizeof(PLOYList)); 第12页 山东科技大学学生课程设计 input->coef=pre->coef; input->expn=pre->expn; input->next=NULL; insert(head,input);// 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x) } } return head;} PLOYList *sub(PLOYList *head,PLOYList *pre)//多项式相减 { PLOYList *input; int flag=0; while(flag==0) { if(pre->next==NULL) flag=1; else { pre=pre->next; input=(PLOYList *)malloc(sizeof(PLOYList)); input->coef=0-pre->coef;//将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法 input->expn=pre->expn; input->next=NULL; insert(head,input); } } return head;} PLOYList *mul(PLOYList *head,PLOYList *pre)//多项式项乘 { PLOYList *hf,*pf,*qa,*qb; qa = head-> next; qb = pre-> next;//定义指针指向表头后一个元素，即链表中第一个元素 hf =(PLOYList *)malloc(sizeof(PLOYList));//新创建一个结点，当做表头 hf-> next = NULL;for(;qa;qa = qa-> next) 第13页 山东科技大学学生课程设计 { for(qb = pre-> next;qb;qb= qb-> next)//用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并 { pf =(PLOYList *)malloc(sizeof(PLOYList)); pf-> coef = qa-> coef * qb-> coef;//系数相乘 pf-> expn = qa-> expn + qb-> expn;//指数相加 pf-> next = NULL; insert(hf,pf); } } return hf;} PLOYList *der(PLOYList *head)//多项式求导 { PLOYList *p;p = head-> next;while(p){ p-> coef = p-> coef * p-> expn; p-> expn = p-> expn--; p = p-> next;} return head;}//将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导 void print(PLOYList *fun)//输出多项式，fun指要输出的多项式链表的表头 { PLOYList *printing; int flag=0; printing=fun->next; if(fun->next==NULL)//若为空表，则无需输出 { printf(“0n”); return; } while(flag==0) { 第14页 山东科技大学学生课程设计 if(printing->coef>0&&fun->next!=printing) printf(“+”); if(printing->coef==1); else if(printing->coef==-1) printf(“-”); else printf(“%f”,printing->coef); if(printing->expn!=0)printf(“x^%d”,printing->expn); else if((printing->coef==1)||(printing->coef==-1)) printf(“1”); if(printing->next==NULL) flag=1; else printing=printing->next; } printf(“n”);} void start()//用户选择界面 { printf(“ #n”); printf(“ 用户选择界面 n”); printf(“ ************************************n”); printf(“ * *n”); printf(“ * 1.两个一元多项式相加 *n”); printf(“ * 2.两个一元多项式相减 *n”); printf(“ * 3.两个一元多项式相乘 *n”); printf(“ * 4.对一个一个一元多项式求导 *n”); printf(“ * 0.退出系统 *n”); printf(“ * *n”); printf(“ ************************************n”); printf(“ n”); printf(“ 注释：输入多项式格式（可无序）：系数1 指数1 系数2 指数2 „„，并以0 0 结束：n”); printf(“ n”); printf(“ 请选择操作: ”);} int main(){ PLOYList *f,*g,*pf,*hf,*p; 第15页 山东科技大学学生课程设计 int sign=-1; start(); while(sign!=0) { scanf(“%d”,&sign); switch(sign) { case 0: break; case 1://多项式相加 { printf(“ 你选择的操作是多项式相加:n”); printf(“ 请输入第一个多项式f(x)：”); f=creat('f'); printf(“ 第一个多项式为：f(x)=”); print(f); printf(“ 请输入第二个多项式g(x)：”); g=creat('g'); printf(“ 第二个多项式为：g(x)=”); print(g); printf(“ 结果为：F(x)=f(x)+g(x)=”); f=add(f,g); print(f); printf(“nn”); printf(“ 继续请选择相应操作，退出请按0.break; } case 2://多项式相减 { printf(” 你选择的操作是多项式相减:n“); printf(” 请输入第一个多项式f(x)：“); f=creat('f'); printf(” 第一个多项式为：f(x)=“); print(f); printf(” 请输入第二个多项式g(x)：“); g=creat('g'); printf(” 第二个多项式为：g(x)=“); print(g); printf(” 结果为：F(x)=f(x)-g(x)=“); f=sub(f,g); print(f); ”);第16页 山东科技大学学生课程设计 printf(“nn”); printf(“ 继续请选择相应操作，退出请按0.”); break; } case 3://多项式相乘 { printf(“ 你选择的操作是多项式相乘:n”); printf(“ 请输入第一个多项式f(x)：”); f=creat('f'); printf(“ 第一个多项式为：f(x)=”); print(f); printf(“ 请输入第二个多项式g(x)：”); g=creat('g'); printf(“ 第二个多项式为：g(x)=”); print(g); printf(“ 结果为：F(x)=f(x)* g(x)=”); pf=mul(f,g); print(pf); printf(“nn”); printf(“ 继续请选择相应操作，退出请按0.”); break; } case 4://多项式求导 { printf(“您选择的是对一个一元多项式求导：n”); printf(“请输入一个一元多项式：”); f = creat('f'); printf(“这个多项式为：f(x)= ”); print(f); printf(“求导结果为：F(x)=f'(x)= ”); f=der(f); print(f); printf(“nn”); printf(“ 继续请选择相应操作，退出请按0.”); break; } }//swith }//while }//void 四、测试结果： 第17页 山东科技大学学生课程设计 第18页 实验报告4 排序 一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验要求及内容 要求编写的程序所能实现的功能包括： 1、从键盘输入要排序的一组元素的总个数 2、从键盘依次输入要排序的元素值 3、对输入的元素进行快速排序 4、对输入的元素进行折半插入排序 三、实验代码及相关注释 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的结构体 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的结构体 int Partition(SqList &L, int low, int high) //1 寻找基准 { L.r[0]=L.r[low];//子表的第一个记录作基准对象 int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： （一个程序，调试运行一次，可多次进行不同序列的不同排序）第四篇：数据结构课程设计
第五篇：数据结构实验报告
点击咨询 