西安电子科技大学 自考数据结构 实验报告.doc

数据结构实践考核报告专业: 计算机及应用 准考证号: 姓名: 考点: 西安电子科技大学考试时间: 2009-5-25一、 实验目的上机考核实践考核检测对数据结构该课程掌握的程度，消化课程内容，加深理解数据结构的基础概念、基本理论和基本方法。二、 实验环境1. 硬件：CPU P4 2.4G内存：256M硬盘：40.G2. 软件： VC+三、 实验考核内容单元一:线形数据结构上的基本运算描述及实现。（1）顺序表上基本算法的运算描述及实现。#define ListSize 100typedef int DataType;typedef structDataType dataListSize;int length;SepList;void Set(SepList *L)L-length=0;void InsertList(SepList *L,DataType x,int i)int j;if(iL-length+1) Error(position error); if(L-length=ListSize) Error(overflow); for(j=L-length-1;i=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-length+; void Covers(SepList *L)int i;DataType temp;for(i=0;ilength/2;i+)temp=L-datai;L-datai=L-dataL-length-i-1;L-dataL-length-i-1=temp;void Out(SepList *L)int i;for(i=0;idatai);main()int x,i,y=0;char ch=ASeqlist *L;set(L);while(y!=5)printf(choice num:n 1:is create list:n 2:is insert list:n)printf( 3:is delete list:n 4:is Covers list:n);printf( 5:is end:n);scanf(%d,&y);if(y=1)printf(creat a list and input init data:)scanf(%d,&y);L-length=x;for(i=0;idatai=x;printf(list is:);Out(L);printf(n);else if(y=2)printf(input data insert and position i:);scanf(%d,&x); scanf(%d,&i);InsertList(L,x,i);Out(L);printf(n);else if (y=3)printf(input delete position:);scanf(%d,&x);DeleteList(L,x);Out(L);printf(n);else if (y=4)printf(convers is:);Convers(L);Out(L);else if (y=5) exit(0);scanf(%d,&y);（2）单链表上基本算法的运算描述及实现。#include stdio.h#include stdlib.h#define null 0struct stu char data; struct stu *next; ;main() /*主函数*/int x,x1; char ch; struct stu *head,*p,*s,*q,*h,*z; printf(现在开始建立链表.请输入字符:n); /*开始建立链表*/ head=(struct stu *)malloc(sizeof(struct stu); p=head; p-next=null; ch=getchar(); while(ch!=n) s=(struct stu *)malloc(sizeof(struct stu); s-data=ch; p-next=s; p=s; p-next=null; ch=getchar(); /*建立后输出*/ printf(建立后的链表为:n ); p=head; output(p-next); p=head;aa: printf(n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * * *n);printf(* *n);printf(* *n); printf(* 1.插入 2.删除 *n);printf(* *n);printf(* *n); printf(* 3.逆转 4输出 *n);printf(* *n); printf(* *n);printf(* 其它:退出 *n);printf(* *n);printf(* *n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * * *n);printf(n);printf( 请输入您想做的操作的序号:);scanf(%d,&x); /*switch函数*/ switch(x) case 1: printf(请输入你要插入的字符和位置:n); scanf(%s%d,&ch,&x1); insert(p,ch,x1); /*调用insert函数*/ goto aa;break; case 2: printf(请输入你要删除的字符: ); goto aa;scanf(%s,&ch);delete(p,ch);/*调用delete函数*/ break; case 3: printf(逆转后的链表为: ); coverse(p); /*调用coverse函数*/ goto aa; break; case 4: printf(输出后的链表为:); goto aa;output(p-next);break; default:exit() ; /*调用output函数*/ printf(t谢谢使用!n); /*主函数结束*/ insert(struct stu *p,char ch1,int x) /*insert函数*/ int i,j,k; struct stu *q,*h,*s; q=p-next; h=p; i=2; j=1;while(q) q=q-next; j+; /*j为链表的长度*/q=p-next; if(x=j+1)printf(插入位置有错,原链表为:n); else while(x=j+1&inext;h=h-next;i+;s=(struct stu *)malloc(sizeof(struct stu);s-data=ch1;h-next=s;s-next=q; output(p-next); /*输出插入后的链表*/ /*insert函数结束*/ delete(struct stu *p,char ch) /*delete函数开始*/ int k; struct stu *q; q=p; k=0; while(q) while(q-next-data=ch) q-next=q-next-next; q=q-next; k=1; printf(删除后的链表为:); if(k=0)printf(没有找到你要删除的字符!n); output(p-next); /*delete函数结束*/ coverse(struct stu *p) /*coverse函数开始*/ struct stu *q,*head1,*s; q=p-next; head1=null; while(q) s=(struct stu *)malloc(sizeof(struct stu); s-data=q-data; s-next=head1; head1=s; q=q-next; q=head1; output(q); /*coverse函数结束*/ /*output函数开始*/ output(struct stu *p) if(p=null) printf(链表为空n); while(p) printf(%c,p-data); p=p-next; /*output函数结束*/ 实验结果：现在开始建立链表.请输入字符:asdfgh建立后的链表为: asdfgh* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1.插入 2.删除 * * * 3.逆转 4.输出 * * * 其它:退出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:1请输入你要插入的字符和位置:x 2axsdfgh * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1.插入 2.删除 * * * 3.逆转 4.输出 * * * 其它:退出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:2请输入你要删除的字符: x删除后的链表为:asdfgh * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1.插入 2.删除 * * * 3.逆转 4.输出 * * * 其它:退出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:3逆转后的链表为: hgfdsa* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1.插入 2.删除 * * * 3.逆转 4.输出 * * * 其它:退出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:4输出后的链表为:asdfgh* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1.插入 2.删除 * * * 3.逆转 4.输出 * * * 其它:退出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:5谢谢使用!Press any key to continue单元二:栈与队列结构上的基本算法描述及实现。（1） 链栈上的基本算法描述及实现#include stdio.h#include stdlib.hdefine null 0struct stacknode char data; struct stacknode *next; node;main()char x,ch;int i;struct stacknode *top,*s,*q;printf(现在开始建立链栈.请输入字符:n);top=(struct stacknode * )malloc(sizeof(struct stacknode);top=null;q=top;x=getchar();while(x!=n) s=(struct stacknode * )malloc(sizeof(struct stacknode); s-next=top; s-data=x; top=s; x=getchar();q=top; printf(建立后的链栈为: ); display(q);aa:printf(n);printf( * * * * * * * * * * 链栈基本算法实现 * * * * * * * * * *n);printf( * *n);printf( * 1. 加 入 2. 删 除 *n);printf( * 3. 查 看 4. 显 示 *n);printf( * 其它:退 出 *n);printf( * *n);printf( * * * * * * * * * * * * * * * * * * * * * * * * * * * * n);printf(n);printf( 请输入您想做的操作的序号:);scanf(%d,&i);switch(i) case 1:printf(请输入你要加入的字符:n); scanf(%s,&ch); enstack(q,ch);goto aa; printf(t谢谢使用!); break; case 2: if (stackempty(q) printf(栈空,不能删除!); else printf(删除的元素为: %cn,destack(q); printf(删除后的栈为:); display(q-next);goto aa; printf(t谢谢使用!); break; case 3: if (stackempty(q) printf(栈空,没有元素!); else printf(查看后栈顶元素为: %c,q-data); printf(t谢谢使用!);goto aa; break; case 4: printf(建好的队列显示为: ); display(q);goto aa; printf(t谢谢使用!); break; default: printf(t谢谢使用!); printf(n); /* 主程序结束 */enstack(struct stacknode *q,char x) /*加入过程*/struct stacknode *p; p=(struct stacknode *)malloc(sizeof(struct stacknode); p-data=x; p-next=q; q=p; printf(加入后链栈为:); display(q);int stackempty(struct stacknode *q) /*判栈空*/return q=null; destack(struct stacknode *q)/*删除函数*/ struct stacknode *p; p=q; return q-data; q=q-next;display(struct stacknode *q) /*显示过程*/ struct stacknode *p; p=q; if(stackempty(p) printf(栈空,没元素!); else while(p) printf(%c,p-data); p=p-next; 实验结果：现在开始建立链栈.请输入字符:asdfgh建立后的链栈为: hgfdsa* * * * * * * * * * 链栈基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:1请输入你要加入的字符:x加入后链栈为:xhgfdsa * * * * * * * * * * 链栈基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:2删除的元素为: a删除后的栈为:xhgfds * * * * * * * * * * 链栈基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:3查看后栈顶元素为: x * * * * * * * * * * 链栈基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:4建好的队列显示为: xhgfds * * * * * * * * * * 链栈基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:5谢谢使用!Press any key to continue（2）链队列上的基本算法描述及实现。#include stdio.h#include stdlib.h#define null 0struct queuenode char data; struct queuenode *next; node;main()char x,ch;int i;struct queuenode *head,*s,*front,*rear,*q;printf(现在开始建立链队列.请输入字符:n);head=(struct queuenode * )malloc(sizeof(struct queuenode);q=rear=front=head;x=getchar();while(x!=n) s=(struct queuenode * )malloc(sizeof(struct queuenode); s-data=x; rear-next=s; rear=s; rear-next=null; x=getchar(); printf(建立后的链队列为: ); display(q-next);aa:printf(n);printf( * * * * * * * * * 链队列基本算法实现 * * * * * * * * * *n);printf( * *n);printf( * 1. 加 入 2. 删 除 *n);printf( * 3. 查 看 4. 显 示 *n);printf( * 其它:退 出 *n);printf( * *n);printf( * * * * * * * * * * * * * * * * * * * * * * * * * * * * n);printf(n);printf( 请输入您想做的操作的序号:);scanf(%d,&i);switch(i) case 1:printf(请输入你要加入的字符:n); scanf(%s,&ch); enqueue(q,rear,ch);goto aa; printf(t谢谢使用!); break; case 2: if (queueempty(q) printf(队空,不能删除!); else printf(删除后的元素为: %cn,dequeue(q-next,rear); printf(删除后的队列为:); display(q-next-next);goto aa; printf(t谢谢使用!); break; case 3: if (queueempty(q) printf(队空,没有队头!); else printf(查看后队头元素为: %c,q-next-data);goto aa; printf(t谢谢使用!); break; case 4: printf(建好的队列显示为: ); display(q-next);goto aa; printf(t谢谢使用!); break; default: printf(t谢谢使用!); printf(n); /* 主程序结束 */enqueue(struct queuenode *q,struct queuenode *r,char x) /*加入过程*/struct queuenode *p; p=(struct queuenode *)malloc(sizeof(struct queuenode); p-data=x; p-next=null; if(r=null) q=r=p; else r-next=p; r=p; printf(加入后链队列为:); display(q-next);int queueempty(struct queuenode *q) /*判队空*/return q=null; dequeue(struct queuenode *q,struct queuenode *r)/*删除函数*/ char y; struct queuenode *p; p=q; return q-data; q=q-next; if(r=p) r=null; free(p);display(struct queuenode *q) /*显示过程*/ struct queuenode *p; p=q; if(queueempty(p) printf(队空,没元素!); else while(p) printf(%c,p-data);p=p-next; 实验结果：现在开始建立链队列.请输入字符:asdfgh建立后的链队列为: asdfgh * * * * * * * * * 链队列基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:1请输入你要加入的字符:x加入后链队列为:asdfghx * * * * * * * * * 链队列基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:2删除后的元素为: a删除后的队列为:sdfghx * * * * * * * * * 链队列基本算法实现 * * * * * * * * * * * * * 1. 加 入 2. 删 除 * * 3. 查 看 4. 显 示 * * 其它:退 出 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *请输入您想做的操作的序号:3查看后队头元素为: a * * * * * * * * * 链队列基本算法实现 * * * * * * * * * * * * * 1. 加 入 2.