【太原理工大学现代科技学院】数字测控实习报告 (2).doc

太原理工大学现代科技学院 数据结构 课程 实验报告 专业班级 计算机科学与技术14-1班学 号 2014101903 姓 名 彭浩 指导教师 邓丽平 装订线 实验名称 单向链表的操作 同组人 专业班级 计科14-1 学号 2014101903 姓名 彭浩 成绩 一、实验目的：1。掌握单向链表的存储特点及其实现；2掌握单向链表的插入、删除算法及其应用算法的程序实现二、实验内容： 1。键盘输入一组元素，建立一个带头结点的单向链表（无序）2遍历单向链表、3在单向链表中删除元素E；4单向链表的逆置5设计一个MAIN（）函数，分别调试上述算法。三、实验环境：Microsoft Visual C+6.04、 主要算法#include#include#include#include#include#includetypedef struct LNodeint data;struct LNode* next;LNode,*Linklist;int count=0,flag=0;Linklist add()/*初始化*/Linklist head,p1,p2;count=0;head=p2=(Linklist)malloc(sizeof(LNode);doflag=0;p1=(Linklist)malloc(sizeof(LNode);p2-next=p1;p1-next=NULL;printf(请输入一个数字:n);scanf(%d,&p1-data);p2=p1;count+;printf(继续输入按: 1 返回按: 0n);scanf(%d,&flag);while(flag=1);printf(你共输入了 %d 个元素.,count);printf(按任意键继续n); getch();return(head);void visit(Linklist head)/*遍历*/int i;Linklist p;p=head-next;for(i=1;idata); p=p-next;printf(按任意键继续n);getch();void Dle(Linklist head)/*删除*/if(!head-next)printf(链表为空!请先输入元素值n);elseint e;Linklist p1,p2;p1=p2=head;printf(请输入一个要删除的元素值:n);scanf(%d,&e);while(p1-data!=e&p1-next!=NULL)p2=p1;p1=p1-next;if(p1-data=e)p2-next=p1-next;free(p1);count-;else printf(无此元素!n);void opp(Linklist head)/*逆置*/Linklist p1,p,q;p=head-next;p1=p-next;p-next=NULL;while(p1-next!=NULL)q=p1;p1=p1-next;q-next=p;p=q;p1-next=q;head-next=p1;printf(逆置后的元素为:n);visit(head);void main()int c;Linklist L;dosystem(cls);printf(#数据结构 实验一 #n);printf(n);printf(输入元素按: 1 遍历按: 2 删除按: 3 逆置按: 4 退出按: 0n);scanf(%d,&c);if(c=1)L=add();continue;else if(c=2)if(count=0)printf(链表为空,请输入元素!n);printf(按任意键继续n);getch(); else printf(元素顺序为:n); visit(L);continue;else if(c=3) if(count=0)printf(链表为空,请输入元素!n);printf(按任意键继续n);getch(); else Dle(L); printf(删除后的元素为:n); visit(L); continue;else if(c=4) if(count=0)printf(链表为空,请输入元素!n);printf(按任意键继续n);getch();else opp(L);continue;else if(c=0)printf( 您已退出, 再见!n);exit(0);while(1);五、实验结果及分析输入元素 ：6 7 8 4 1遍历元素顺序：6 7 8 4 1删除元素值 4 删除元素顺序为 6 8 4 1逆置的元素 1 4 8 6装订线实验名称 栈和队列 同组人 专业班级 计科14-1 学号 2014101903 姓名 彭浩成绩 一、实验目的：1.编程实现进制转化和判断回文。2熟悉站和队列的操作。2、 实验内容实现十进制的转化和回文判断。三、实验环境：Microsoft Visual C+6.0四 主要算法栈的进制转化#include#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define selemtype int#define status int#define ok 1typedef structselemtype * base;selemtype * top;int stacksize;sqstack;status initstack(sqstack &s)s.base=(selemtype *)malloc(STACK_INIT_SIZE * sizeof(selemtype);if(!s.base) exit(0);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return ok;status stackempty(sqstack s)if(s.top=s.base) return 1;return 0;status push(sqstack &s,selemtype e)if(s.top-s.base=s.stacksize)s.base=(selemtype * )realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(selemtype);if(!s.base) exit(0);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return ok;status pop(sqstack &s,selemtype &e)if(s.top=s.base) return 0;e=* -s.top;return ok;void conversion(int N,int M)int e;sqstack s;initstack(s);while(N)push(s,N%M);N=N/M;while(!stackempty(s)if(M10)pop(s,e);if(e9)printf(%c,e+55);elseprintf(%d,e);elsepop(s,e);printf(%d,e);printf(n按任意键继续n);getch();void main()int x,y,flag;dosystem(cls);printf(* 实验二 数制转换 *nnn);printf(进行数制转换 按: 1 退出 按: 0n);scanf(%d,&flag);if(flag)printf(请输入一个十进制的非负数:n);scanf(%d,&x);printf(请输入要将它转换的进制数:n);scanf(%d,&y);printf(十进制的 %d 转化成 %d 进制为: ,x,y);conversion(x,y);while(flag);队列的回文判断#include#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef char QElemType;#define status int#define ok 1int count;typedef struct SElemType * base; SElemType * top; int stacksize;sqstack;status initstack(sqstack &s) s.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!s.base) exit(0); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return ok;status stackempty(sqstack s) if(s.top=s.base) return 1; return 0;status push(sqstack &s,SElemType e) if(s.top-s.base=s.stacksize) s.base=(SElemType * )realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!s.base) exit(0); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; *s.top+=e; return ok; status pop(sqstack &s,SElemType &e) if(s.top=s.base) return 0; e=* -s.top; return ok;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q) /构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front)exit(0); Q.front-next=NULL; return 1;int EnQueue(LinkQueue &Q,QElemType e) /插入元素e为Q的新的队尾元素 QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p)exit(0); p-data=e;p-next=NULL; Q.rear-next=p; Q.rear=p; return 1;int DeQueue(LinkQueue &Q,QElemType &e) /若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR QueuePtr p; if(Q.front=Q.rear)return 0; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p)Q.rear=Q.front; free(p); return 1;void input(sqstack &s,LinkQueue &q) int flag=0; char c; count=0; printf(请输入一串字符,按回车结束输入!n); fflush(stdin);/*清除缓冲*/ while(c=getchar()!=n) push(s,c); EnQueue(q,c); count+; printf(你共输入了 %d 个元素n,count); void check(sqstack &s,LinkQueue &q) char e1,e2; int i,key=0; for(i=1;i=count/2;i+) pop(s,e1); DeQueue(q,e2); if(e1=e2) key+; if(key=count/2) printf(是回文n); printf(n按任意键继续n); getch(); else printf(不是回文n); printf(n按任意键继续n); getch(); void main() int c; do system(cls); printf(# 实验二判断回文 #nn); printf(按1进行输入和判断 按0 退出n); scanf(%d,&c); if(c) sqstack s; LinkQueue q; InitQueue(q); initstack(s); input(s,q); check(s,q); else exit(0); while(c); printf(你已经退出，再见n);5、 实验结果及分析栈 输入十进制的非负数 52 转化为二进制 110100 转化为八进制 64 转化为十六进制 34队列 输入字符串adfgfh 不是回文装订线实验名称 遍历二叉树 同组人 专业班级 计科14-1 学号 2014101903 姓名 彭浩 成绩 一、实验目的：1，掌握遍历二叉树的先序,中序，后序2，掌握叶子结点的算法二 实验内容遍历二叉树的先序,中序，后序递归排序和计算叶子结点。三、实验环境：Microsoft Visual C+6.0四 主要算法#include#include#include#include#include#include #define maxsize 1000typedef char elemtype;typedef struct bitree elemtype data; struct bitree *lchild,*rchild;BiTree,*TBiTree;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define selemtype TBiTree#define status int#define ok 1int count;typedef struct selemtype * base; selemtype * top; int stacksize;sqstack;status initstack(sqstack &s) s.base=(selemtype *)malloc(STACK_INIT_SIZE * sizeof(selemtype); if(!s.base) exit(0); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return ok;status stackempty(sqstack s) if(s.top=s.base) return 1; return 0;status push(sqstack &s,selemtype e) if(s.top-s.base=s.stacksize) s.base=(selemtype * )realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(selemtype); if(!s.base) exit(0); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; *s.top+=e; return ok; status pop(sqstack &s,selemtype &e) if(s.top=s.base) return 0; e=* -s.top; return ok;BiTree *create() BiTree *q100; /定义q数组作为队列存放二叉链表中结点,100为最大容量BiTree *s; /二叉链表中的结点BiTree *root ; /二叉链表的根指针int front=1,rear=0; /定义队列的头、尾指针char ch; /结点的data域值root=NULL;printf(请输入一组字符，按 # 结束n);cinch;while(ch!=#) /输入值为#号,算法结束 s=NULL;if(ch!=,) /输入数据不为逗号,表示不为虚结点,否则为虚结点 s=new BiTree;s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;qrear=s; /新结点或虚结点进队if(rear=1)root=s;count+;else if(s!=NULL)&(qfront!=NULL) if(rear%2=0)qfront-lchild=s;count+; /rear为偶数,s为双亲左孩子elseqfront-rchild=s;count+;/rear为奇数,s为双亲右孩子if(rear%2=1) front+; /出队cinch;return root;int visit(char c)/遍历 printf(%c,c); return 1;int dpreordertraverse(TBiTree t)/递归先序if(t)visit(t-data);dpreordertraverse(t-lchild);dpreordertraverse(t-rchild);return 0;else return 1;int dinordertraverse(TBiTree t)/递归中序if(t)dinordertraverse(t-lchild);visit(t-data);dinordertraverse(t-rchild);return 0;else return 1;int dbackordertraverse(TBiTree t)/递归后序if(t)if (dbackordertraverse(t-lchild)if(dbackordertraverse(t-rchild) if(visit(t-data) return 1;return 0;else return 1;int hI,hr，max；If（T）hI=Tree Depth（T-Ichild）；/求左深度hr=Tree Depth（T-rchild）；/求右深度max=hIhr?hI:hr;/取左右深度最大值Node Nnm =Node Nnm +1；/求节点数If（hI=0&hr=0） leaf=leaf+1；/若左右深度为0，即为叶子Return（max+1）；else return（0）；void main() TBiTree t; int key=0; do system(cls); printf(# 实验三 遍历二叉树 #nn); printf( 按 1 用递归算法遍历 按 0 退出n); scanf(%d,&key); if(key=1) count=0; t=create(); printf(你共输入了 %d 个元素以下是用递归法遍历:n,count); printf(nn递归先序:n); dpreordertraverse(t); printf(nn递归中序:n); dinordertraverse(t); printf(nn递归后序:n); dbackordertraverse(t); printf(nn叶子结点:n); printf(n任意键继续n); getch(); else printf(你已退出，再见!n); exit(0); while(key);五 实验结果及分析递归先序 A B C D E F 递归中序 C B A E D F递归后序