学生姓名 学号：
班级： xx大学。
目录。一、程序题目和要求 3
二、逻辑设计与详细设计 3
三、结果测试与算法分析 14
四、程序有待改进的地方 22
五、本次实习的收获和建议 22
一。 程序题目和要求。
二。 本次课设工完成三个程序的编写和调试，分别以三个工程保存，分别是：线性链表基本操作的实现、表达式求解问题、二叉树的遍历、线索及应用。
1、 线性链表基本操作的实现。
问题描述] 线性链表的插入、删除、遍历等操作的实现。
基本要求] 要求生成线性表时，可以键盘上读取元素。
2、 表达式求解问题。
问题描述]设计一个程序，求解算术表达式。
基本要求] 以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。
3、 二叉树的遍历、线索及应用。
问题描述] 建立二叉树，并输出二叉树的先序，中序和后序遍历序列，以及二叉树的叶子数。
基本要求] 要求根据读取的元素建立二叉树，能输出各种遍历。
二、逻辑设计与详细说明。
1、线性链表基本操作的实现。
线性表的操作是数据结构的基本操作之一，程序结构比较简单，程序主要为算法部分。
1.1、概要设计：
抽象数据类型线性表的定义如下：
adt list
数据关系：rl=
基本操作；intlist(&l)
操作结果：构造一个空的线性表l。
destroylist(&l)
初始条件：线性表l已存在。
操作结果：销毁线性表l.
clearlist(&l)
操作结果：将l重置为空表。
listempty(l)
操作结果：若l为空表，则返回true，否则返回false。
listlength(l)
操作结果：返回l中数据元素的个数。
getelem(l,i,&e)
操作结果：用e返回l中第i个数据元素的值。
locateelem(l,e,compare())
操作结果：返回l中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.
priorelem(l,cur_e,&pre_e)
操作结果：若cur_e是l的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
nextelem(l,cure_e,&next_e)
操作结果：若cure_e是l的数据元素，且不是第一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
listinsert(&l,i,e)
操作结果：在l中第i个位置之前插入新的数据元素e,l的长度加1.
listdelet(&l,i,&e)
操作结果：删除l的第i个数据元素，并用e返回其值，l的长度减1.
listtr**erse(l,visit())
操作结果：依次对l的每个数据元素调用函数visit(),一旦visit()失败，则操作失败。
adt list
1）.创建单链表。
基本思路：首先创建结构体，里面包含一个数据域和一个指针域：
typedef char elemtype;
typedef struct lnode
elemtype data;
struct lnode *next;
linklis首先开辟一个头结点（以head为例），定义指针p指向head->next,对p->data赋值，然后将p指向p->next，以此类推，结束标志是p->next==null。
2）. 分别以头插法和尾插法建立线性表，头插法即将元素插入两元素之间，依次往后进行，将首地址a[i]赋给s->data，然后s->next指向l->next，最后将s赋给l->next
linklist *s;int i;
l=(linklist *)malloc(sizeof(linklist));
l->next=null;
for(i=0;i
if(p==null)
return 0;
else5）.插入元素。
对单链表进行遍历的同时进行比较，找到要插入的位置，并修改对应结点的指针域指向。
int listinsert(linklist *&l,int i,elemtype e)
if(p==null)return 0;
else4）.删除元素。
对单链表进行遍历的同时进行比较，找到要删除的位置，并修改对应结点的指针域指向。
int listdelete(linklist *&l,int i,elemtype &e)
if(p==null)
return 0;
else2、 表达式求解问题。
表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈的应用之一，本次设计采用的是酸腐优先法。
2.1栈的抽象数据类型定义。
adt stack
数据关系：r1＝
约定an 端为栈顶，a1 端为栈底。
基本操作：initstack(&s)
操作结果：构造一个空栈s。
destroystack(&s)
初始条件：栈s已存在。
操作结果：栈s被销毁。
clearstack(&s)
初始条件：栈s已存在。
操作结果：将s清为空栈。
stackempty(s)
初始条件：栈s已存在。
操作结果：若栈s为空栈，则返回true，否则fale。
stacklength(s)
初始条件：栈s已存在。
操作结果：返回s的元素个数，即栈的长度。
gettop(s, &e)
初始条件：栈s已存在且非空。
操作结果：用e返回s的栈顶元素。
push(&s, e)
初始条件：栈s已存在。
操作结果：插入元素e为新的栈顶元素。
pop(&s, &e)
初始条件：栈s已存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值。
stacktr**erse(s, visit( )
初始条件：栈 s 已存在且非空，visit( )为元素的访问函数。
操作结果：从栈底到栈顶依次对s的每个元素调用函数visit( )一旦visit( )失败，则操作失败。
adt stack
1）.构建空栈。
只允许在一端插入和删除的线性表。
允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，让栈底等于栈顶。
pstack initstack(pstack stack)
stack->top = stack->base;
return stack;
2). 插入c为栈顶元素。
void push(pstack stack, char c)//插入元素c为新的栈顶元素。
stack->top++;
*stack->top = c;
3）判断是否为运算符。
输入字符后，对字符依次进行判断是否都为运算符，若不是，则输出“请输入正确的运算符”
int isoperator(char c)//判断是否是运算符。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...