数据结构实训报告

范文一：数据结构实训报告

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站一、实训目的

《数据结构》实训是信息管理与信息系统专业集中实践性环节之一，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。

题目一:链表操作

一、线性链表的存储结构及算法设计

1、设计目的

(1)掌握线性表的在顺序结构和链式结构实现。

(2)掌握线性表在顺序结构和链式结构上的基本操作。

2、设计内容和要求

利用顺序表链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数)，并能在屏幕上输出操作前后的结果。

3、算法设计

a、线性表的建立

LinkList CreateList_L( )

{

//逆位序输入n个元素的值，建立带表头结点的单链线性表L

LNode *p;

LinkList L;

int i,n;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL; //先建立一个带头结点的单链表

printf("输入要建立链表的元素个数: \n");

scanf("%d",&n);

printf("输入链表元素值:\n");

for(i=n;i>0;i--)

{

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

p=(LinkList)malloc(sizeof(LNode)); //生成新结点

scanf("%d",&p->data); //输入元素值

p->next=L->next;

L->next=p; //插入表头

}

printf("输入的链表元素为:\n");

Output(L);

return L;

}//CreateList_L

b、线性链表的查找

Status GetElem_L(LinkList L)

{

//L为带头节点的单链表的头指针

//当第i个元素存在时。其赋值给e并返回OK，否则返回ERROR

int i,j,e;

LNode *p;

printf("所有的链表元素为:\n");

Output(L);

printf("\n输入要查找的元素位置:\n");

scanf("%d",&i);

p=L->next;

j=1;

while(p&&j

{

//顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;

j++;

}

if(!p||j>i)

{

return ERROR;//第i个元素不存在

printf("查找的元素不存在\n");

}

e=p->data; //取第i个元素

printf("查找的元素为:\n %d",e);

return OK;

}//GetElem_L

c、线性链表的插入

Status ListInsert_L(LinkList &L)

{

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

//在带头结点的单链线性表L中第i个位置之前插入元素e

LNode *p,*s;

int i,j,e;

printf("插入之前的链表元素为:\n");

Output(L);

p=L->next;

j=1;

printf("\n输入要插入元素的位置:\n");

scanf("%d",&i);

printf("输入要插入的元素 e:\n");

scanf("%d",&e);

printf("插入的元素为 e: \n %d\n",e);

while(p&&j

{

p=p->next;

++j;

} //寻找第i-1个结点

if(!p||j>i-1)return ERROR; //i小于1或者大于表长+1

s=(LinkList)malloc(sizeof(LNode)); //生成新结点

s->data=e;

s->next=p->next; //插入L中

p->next=s;

printf("插入之后的元素为:\n");

Output(L);

return OK;

}//LinkInsert_L

d、线性链表的删除

Status ListDelete_L(LinkList&L)

{

//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

int i,j,e;

LNode *p,*q;

printf("输出删除之前的元素:\n");

Output(L);

printf("\n输入要删除的元素位置:\n");

scanf("%d",&i);

p=L;

j=0;

while(p->next&&j

{

//寻找第i个结点，并由p指向其前驱

p=p->next;

++j;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

}

if(!(p->next)||j>i-1)

{

return ERROR; //删除位置不合理q=p->next

printf("删除位置不合理或输入错误");

}

q=p->next;

p->next=q->next; //删除并释放结点

e=q->data;

free(q);

printf("删除之后的元素为:\n");

Output(L);

return OK;

}//ListDelete_L

e、线性链表的逆置

void InvertList_L(LinkList L)

{//链表的逆置

LNode *p,*q,*s;

printf("逆置前的链表元素为:\n");

Output(L);

p=L->next;

q=p->next;

p->next=NULL;

while(q->next!=NULL)

{

s=q->next;

q->next=p;

p=q;

q=s;

}

q->next=p;

L->next=q;

printf("\n逆置后的链表元素为:\n");

Output(L);

}

f、线性链表的输出

void Output(LinkList L) {

LNode *p;

int j;

p=L->next;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

while(p)

{

printf("%d ",p->data);

p=p->next;

++j;

}

g、线性链表的排序

void SortList_L(LinkList L)

{//链表排序

int t;

LNode *p,*q;

printf("排序前的链表元素为:\n");

Output(L);

p=L->next;

q=p->next;

while(q)

{

while(q)

{

if(p->data>=q->data)

{

t=p->data;

p->data=q->data;

q->data=t;

}

q=q->next;

}

p=p->next;

q=p->next;

}

printf("\n由小到大排序后的链表元素为:\n");

Output(L);

}//SortList_L

4、源代码

#include #include #define ERROR 0 //出错 #define OK 1 //正确 typedef int Status; typedef int ElemType; typedef struct LNode

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

{

ElemType data;

struct LNode *next; }LNode,*LinkList;

LinkList L;

void Output(LinkList L) {

LNode *p;

int j;

p=L->next;

while(p)

{

printf("%d ",p->data);

p=p->next;

++j;

}

LinkList CreateList_L() {

//逆位序输入n个元素的值，建立带表头结点的单链线性表L

LNode *p;

LinkList L;

int i,n;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL; //先建立一个带头结点的单链表

printf("输入要建立链表的元素个数: \n");

scanf("%d",&n);

printf("输入链表元素值:\n");

for(i=n;i>0;i--)

{

p=(LinkList)malloc(sizeof(LNode)); //生成新结点

scanf("%d",&p->data); //输入元素值

p->next=L->next;

L->next=p; //插入表头

}

printf("输入的链表元素为:\n");

Output(L);

return L;

}//CreateList_L

Status GetElem_L(LinkList L)

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

{

//L为带头节点的单链表的头指针

//当第i个元素存在时。其赋值给e并返回OK，否则返回ERROR

int i,j,e;

LNode *p;

printf("所有的链表元素为:\n");

Output(L);

printf("\n输入要查找的元素位置:\n");

scanf("%d",&i);

p=L->next;

j=1;

while(p&&j

{

//顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;

j++;

}

if(!p||j>i)

{

return ERROR;//第i个元素不存在

printf("查找的元素不存在\n");

}

e=p->data; //取第i个元素

printf("查找的元素为:\n %d",e);

return OK;

}//GetElem_L

Status ListInsert_L(LinkList &L)

{

//在带头结点的单链线性表L中第i个位置之前插入元素e

LNode *p,*s;

int i,j,e;

printf("插入之前的链表元素为:\n");

Output(L);

p=L->next;

j=1;

printf("\n输入要插入元素的位置:\n");

scanf("%d",&i);

printf("输入要插入的元素 e:\n");

scanf("%d",&e);

printf("插入的元素为 e: \n %d\n",e);

while(p&&j

{

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

p=p->next;

++j;

} //寻找第i-1个结点

if(!p||j>i-1)return ERROR; //i小于1或者大于表长+1

s=(LinkList)malloc(sizeof(LNode)); //生成新结点

s->data=e;

s->next=p->next; //插入L中

p->next=s;

printf("插入之后的元素为:\n");

Output(L);

return OK;

}//LinkInsert_L

Status ListDelete_L(LinkList&L)

{

//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

int i,j,e;

LNode *p,*q;

printf("输出删除之前的元素:\n");

Output(L);

printf("\n输入要删除的元素位置:\n");

scanf("%d",&i);

p=L;

j=0;

while(p->next&&j

{

//寻找第i个结点，并由p指向其前驱

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

{

return ERROR; //删除位置不合理q=p->next

printf("删除位置不合理或输入错误");

}

q=p->next;

p->next=q->next; //删除并释放结点

e=q->data;

free(q);

printf("删除之后的元素为:\n");

Output(L);

return OK;

}//ListDelete_L

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

Status CountList_L(LinkList L)

{//计数

LNode *p;

int i;

i=0;

p=L->next;

while(p)

{

p=p->next;

i++;

}

printf("链表元素个数为:%d",i);

return i;

}

void InvertList_L(LinkList L)

{//链表的逆置

LNode *p,*q,*s;

printf("逆置前的链表元素为:\n");

Output(L);

p=L->next;

q=p->next;

p->next=NULL;

while(q->next!=NULL)

{

s=q->next;

q->next=p;

p=q;

q=s;

}

q->next=p;

L->next=q;

printf("\n逆置后的链表元素为:\n");

Output(L);

}

void SortList_L(LinkList L)

{//链表排序

int t;

LNode *p,*q;

printf("排序前的链表元素为:\n");

Output(L);

p=L->next;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

q=p->next;

while(q)

{

while(q)

{

if(p->data>=q->data)

{

t=p->data;

p->data=q->data;

q->data=t;

}

q=q->next;

}

p=p->next;

q=p->next;

}

printf("\n由小到大排序后的链表元素为:\n");

Output(L);

}//SortList_L

void main()

{

int i;

printf("\n?????????????【请建立链表】?????????????\n");

L=CreateList_L();

Loop:

printf("\n?????????【功能菜单】?????????\n");

printf("? ?\n");

printf("? 1. 建立链表 ?\n");

printf("? 2. 插入元素 ?\n");

printf("? 3. 查找链表元素 ?\n");

printf("? 4. 删除链表元素 ?\n");

printf("? 5. 逆置链表元素 ?\n");

printf("? 6. 链表元素排序 ?\n");

printf("? 7. 输出链表元素 ?\n");

printf("? 8. 计算元素个数 ?\n");

printf("? 0. 退出 ?\n");

printf("? ?\n");

printf("????????????????????????\n");

printf("【选择功能】:");

scanf("%d",&i);

switch(i)

{

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

case 0: break;

case 1: CreateList_L();goto Loop;

case 2: ListInsert_L(L);goto Loop;

case 3: GetElem_L(L);goto Loop;

case 4: ListDelete_L(L);goto Loop;

case 5: InvertList_L(L);goto Loop;

case 6: SortList_L(L);goto Loop;

case 7: Output(L);goto Loop;

case 8: CountList_L(L); goto Loop;

default: printf("\n输入错误，请重新输入\n");goto Loop;

}

题目二:二叉树的基本操作

一、二叉链表存储结构及算法设计

1、设计目的

(1)掌握二叉树的概念和性质;

(2)掌握任意二叉树存储结构;

(3)掌握任意二叉树的基本操作。

2、设计内容和要求

对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构，并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。

3、算法设计

a、二叉树先序遍历

Status PreOrderTraverse(BiTree T)

{//先序遍历二叉树

if(T)

{

printf("%c ",T->data);

PreOrderTraverse(T->Lchild);

PreOrderTraverse(T->Rchild);

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

}

return OK;

}//PreOrderTraverse

b、二叉树中序遍历

Status InOrderTraverse(BiTree T) {//中序遍历二叉树

if(T)

{

InOrderTraverse(T->Lchild);

printf("%c ",T->data);

InOrderTraverse(T->Rchild);

}

return OK;

}

c、二叉树后序遍历

Status PostOrderTravese(BiTree T) {//后序遍历二叉树

if(T!=NULL)

{

PostOrderTravese(T->Lchild);

PostOrderTravese(T->Rchild);

printf("%c ",T->data);

}

return OK;

}

d、二叉树深度

Status BiTreeDepth(BiTree T) { //二叉树深度

int depth=0,depthLeft=0,depthRight=0;

if ( !T)

depth = 0;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

else

{

depthLeft = BiTreeDepth(T->Lchild );

depthRight= BiTreeDepth(T->Rchild );

depth =1+(depthLeft > depthRight ?depthLeft : depthRight);

}

return depth;

}

e、计算叶子数

Status CountLeaf(BiTree T) {//计算叶子数

int num1,num2,num;

num1=0;num2=0;num=0;

if(!T)

return ERROR;

else

{

if(!(T->Lchild)&&!(T->Rchild))

return OK;

num1=CountLeaf(T->Lchild);

num2=CountLeaf(T->Rchild);

}

num=num1+num2;

return num;

}

f、度为1的二叉树结点

Status OneNode(BiTree T)

{ //度为1的二叉树结点

int i=0;

if(T!=NULL)

{

OneNode(T->Lchild);

OneNode(T->Rchild);

if((T->Lchild==NULL&&T->Rchild!=NULL)||(T->Lchild!=NULL&&T->Rchild==NULL))

i++;

return i+1;

}

return OK;

}

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

g、二叉树总结点数

Status CountNumNode(BiTree T) {

int num=0;

if(!T)

{

return ERROR;

}

if (T)

{

CountNumNode(T->Lchild);

CountNumNode(T->Rchild);

}

num=CountNumNode(T->Lchild)+CountNumNode(T->Rchild)+1;

return num;

}

3.源代码

#include

#define ERROR 0 //出错

#define OK 1 //正确

#define OVERFLOW 2 //溢出

typedef char TElemType; typedef int Status;

typedef struct BiTNode

{

TElemType data;

struct BiTNode *Lchild,*Rchild; //左右孩子指针; }BiTNode,*BiTree;

BiTree T;

//***********建立二叉树***************// Status CreateBiTree(BiTree &T) {//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树， //构造二叉链表表示的二叉树T

char ch;

scanf("%c",&ch);

if(ch==' ')T=NULL;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站 else

{

if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch; //生成根结点

CreateBiTree(T->Lchild); //构造左子树

CreateBiTree(T->Rchild); //构造右子树

}

return OK;

}//CreateBiTree

//**************先序遍历二叉树***************// Status PreOrderTraverse(BiTree T) {//先序遍历二叉树

if(T)

{

printf("%c ",T->data);

PreOrderTraverse(T->Lchild);

PreOrderTraverse(T->Rchild);

}

return OK;

}//PreOrderTraverse

//****************中序遍历二叉树********************// Status InOrderTraverse(BiTree T) {//中序遍历二叉树

if(T)

{

InOrderTraverse(T->Lchild);

printf("%c ",T->data);

InOrderTraverse(T->Rchild);

}

return OK;

}

//**********后序遍历二叉树*****************// Status PostOrderTravese(BiTree T) {//后序遍历二叉树

if(T!=NULL)

{

PostOrderTravese(T->Lchild);

PostOrderTravese(T->Rchild);

printf("%c ",T->data);

}

return OK;

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站 }

//******************计算二叉树的深度*****************// Status BiTreeDepth(BiTree T) { //二叉树深度

int depth=0,depthLeft=0,depthRight=0;

if ( !T)

depth = 0;

else

{

depthLeft = BiTreeDepth(T->Lchild );

depthRight= BiTreeDepth(T->Rchild );

depth =1+(depthLeft > depthRight ?depthLeft : depthRight);

}

return depth;

}

//***************计算叶子数**************// Status CountLeaf(BiTree T)

{//计算叶子数

int num1,num2,num;

num1=0;num2=0;num=0;

if(!T)

return ERROR;

else

{

if(!(T->Lchild)&&!(T->Rchild))

return OK;

num1=CountLeaf(T->Lchild);

num2=CountLeaf(T->Rchild);

}

num=num1+num2;

return num;

}

//*************度为1 的二叉树结点****************// Status OneNode(BiTree T)

{ //度为1的二叉树结点

int i=0;

if(T!=NULL)

{

OneNode(T->Lchild);

OneNode(T->Rchild);

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站 if((T->Lchild==NULL&&T->Rchild!=NULL)||(T->Lchild!=NULL&&T->Rchil

d==NULL))

i++;

return i+1;

}

return OK;

}

//*****************计算总结点数***************// Status CountNumNode(BiTree T) {

int num=0;

if(!T)

{

return ERROR;

}

if (T)

{

CountNumNode(T->Lchild);

CountNumNode(T->Rchild);

}

num=CountNumNode(T->Lchild)+CountNumNode(T->Rchild)+1;

return num;

}

//*****************主函数********************// void main()

{

int i;

printf("\n????????????????【请建立二叉树】???????

?????????\n");

printf("请输入要建立的结点\n");

CreateBiTree(T);

Loop:

printf("\n?????????【功能菜单】?????????\n");

printf("? ?\n");

printf("? 1. 建立二叉树 ?\n");

printf("? 2. 先序遍历二叉树 ?\n");

printf("? 3. 中序遍历二叉树 ?\n");

printf("? 4. 后序遍历二叉树 ?\n");

printf("? 5. 二叉树深度 ?\n");

printf("? 6. 二叉树结点数 ?\n");

printf("? 7. 二叉树叶子数 ?\n");

printf("? 8. 二叉树度为1的结点 ?\n");

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站

printf("? 0. 退出 ?\n");

printf("? ?\n");

printf("????????????????????????\n");

printf("【选择功能】:");

scanf("%d",&i);

switch(i)

{

case 0: break;

case 1: CreateBiTree(T);goto Loop;

case 2: PreOrderTraverse(T);goto Loop;

case 3: InOrderTraverse(T);goto Loop;

case 4: PostOrderTravese(T);goto Loop;

case 5: printf("二叉树深度为:\n %d",BiTreeDepth(T));goto Loop;

case 6: printf("二叉树总结点数为:\n %d",CountNumNode(T));goto Loop;

case 7: printf("二叉树叶子数为:\n %d",CountLeaf(T));goto Loop;

case 8: printf("二叉树度为1的结点数为:\n %d",OneNode(T)); goto Loop;

default: printf("\n输入错误，请重新输入:\n");goto Loop;

}

实习总结

紧张的两周数据结构实训很快就过去了，通过这两周的实践学习，不仅使我们巩固了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在这门课程的实际应用上也有了一个提高。

首先这两周的学习，使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。

其次，让我们进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我们数据结构的学习和提高很有益处，并且使我们明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度，第一要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么;第二，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出，在这个过程

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

专业好文档为您整理~谢谢使用~请双击清除页眉页脚~ 更多精彩内容请关注本站中，可确定所需的数据结构的基本类型——线性表、栈、队列、串、数组、广义表、树和二叉树以及图等，然后确定处理过程——算法，通过在编译环境中的编译与调试，可到最终的程序。

最后，在这次的实训过程中，我们深刻的认识到了自己在学习方面的不足之处，我知道我还有太多的基本的思想没有真正的理解，当然我们不会灰心，我们会在以后的日子里努力弥补我们的不足。

从最初的查阅资料到最后的程序的成功运行，两个星期的时间让我们经历了很多，也收获了很多。经过这次课程设计，我们不仅学到了很多知识和技能，更重要的是我们学会了如何运用所学知识去解决实际问题。

总之，两个星期的课程设计让我们受益匪浅。我们深深认识到，数据结构是计算机程序设计的重要理论技术基础，它是计算机科学的核心课程。要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。

参考文献

1.《C++程序设计》,清华大学出版社,

2.《数据结构,C语言版,》,清华大学出版社,

3.《数据结构,C语言版,》,中国铁道出版社,

专业好文档为您整理~谢谢使用~请双击清除页眉页脚

范文二：《数据结构》实训报告

实验一线性表

1. 实验要求

1.1 掌握数据结构中线性表的基本概念。

1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。

1.3 熟练掌握链表的各种操作和应用。

2. 实验内容

2.1 编写一个函数，从一个给定的顺序表A 中删除元素值在x 到y 之间的所有元素，要求以较高效率来实现。

2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作

2.3 设计一个统计选票的算法，输出每个候选人的得票结果。

3. 实验代码

2.1代码：

#include

typedef int elemtype;

#define maxsize 10

int del(int A[],int n,elemtype x,elemtype y)

{

int i=0,k=0;

while(i<>

{if(A[i]>=x&&A[i]<>

k++;

else

A[i-k]=A[i];

i++;

}

return(n-k);

}

void main()

{

int i,j;

int a[maxsize];

printf("输入%d个数:\n",maxsize);

for(i=0;i<>

scanf("%d,",&a[i]);

j=del(a,maxsize,1,3);

printf("输出删除后剩下的数:\n");

for(i=0;i<>

printf("%d "\n,a[i]);

}

2.2代码：

INSERT(L,i,b)。

void Insert(Linklist &L,int i,elemtype x)

{

if(!L)

{

L=(Linklist)malloc(sizeof(Lnode));

(*L).data=x;(*L).next=NULL;

}

else

{

if(i==1)

{

s=(Linklist)malloc(sizeof(Lnode));

s->data=x;s->next=L;L=s;

}

else

{

p=L;j=1;

while(p&&j<>

{j++;p=p->next;}

if(p||j>i-1)

return error;

s=(Linklist)malloc(sizeof(Lnode));

s->data=x;s->next=p->next;p->next=s;

}

2.3代码：

typedef int elemtype

typedef struct linknode

{

elemtype data;

struct linknode *next;

}nodetype;

nodetype *create()

{

elemtype d;

nodetype h=NULL,*s,*t;

int i=1;

printf("建立单链表:\n");

while(1)

{

printf("输入第%d个结点数据域",i);

scanf("%d",&d);

if(d==0)break;

if(i==1)

{

h=(nodetype *)malloc(sizeof(nodetype));

h->data=d;h->next=NULL;t=h;

}

else

{

s=(nodetype *)malloc(sizeof(nodetype));

s->data=d;s->next=NULL;t->next=s;

t=s;

}

i++;

}

return h;

}

void sat(nodetype *h,int a[])

{

nodetype *p=h;

while(p!=NULL)

{

a[p->data]++;

p=p->next;

}

void main()

{

int a[N+1],i;

for(i=0;i<>

a[i]=0;

nodetype *head;

head=create();

sat(head,a);

}

printf("候选人:"); for(i=1;i<=n;i++) printf("%3d",i);="" printf("\n得票数\n");="" for(i=""><=n;i++) printf("%3d",a[i]);="">

4. 实验小结

线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。

实验二栈与队列

1. 实验要求

1.1 了解栈和队列的特性，以便灵活运用。

1.2 熟练掌握栈和有关队列的各种操作和应用。

2. 实验内容

2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算

法判断其中的括号是否匹配。

3. 实验代码

2.1代码：

#include

#define NULL 0

typedef struct list

{

char str;

struct list *next;

}list;

void push(char,list *);

int pop(char.list *);

void deal(char *str);

main(void)

{

char str[20];

printf("\n请输入一个算式:\n");

gets(str);

deal(str);

printf("正确!");

getchar();

return 0;

}

void deal(char *str)

{

list *L;

L=(list *)malloc(sizeof(list));

if(!L)

{

printf("错误!");

exit(-2);

}

L->next=NULL;

while(*str)

{

if(*str=='('||*str=='['||*str=='{')

push(*str,L);

else

if(*str==')'||*str==']'||*str=='}')

if(pop(*str,L))

{puts("错误, 请检查!");

puts("按回车键退出");

getchar();exit(-2);

}

str++;

}

if(L->next)

{

puts("错误, 请检查!");

puts("按任意键退出");

getchar();exit(-2);

}

void push(char c,list *L)

{

list *p;

p=(list *)malloc(sizeof(list));

if(!p)

{

printf("错误!");

exit(-2);

}

p->str=c;

p->next=L->next;

L->next=p;

}

#define check(s) if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L)

{

list *p;

if(L->next==NULL)return 1;

switch(c)

{

case')':check('(') break;

case']':check('[') break;

case'}':check('{') break;

}

return 1;

4. 实验小结

栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。

实验三树

1. 实验要求

1.1 掌握二叉树，二叉树排序数的概念和存储方法。

1.2 掌握二叉树的遍历算法。

1.3 熟练掌握编写实现树的各种运算的算法。

2. 实验内容

2.1 编写程序，求二叉树的结点数和叶子数。

2.2 编写递归算法，求二叉树中以元素值为X 的结点为根的子数的深度。

2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。

3. 实验代码

2.1代码：

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

char ch;

ch=getchar();

if(ch==' ') return(NULL);

else

{

bt=(struct node *)malloc(sizeof(bnode));

bt->data=ch;

bt->lchild=creat();

bt->rchild=creat();

}

return bt;

}

int n=0,n1=0;

void preorder(blink bt)

{

if (bt)

{

n++;

if(bt->lchild==NULL&&bt->rchild==NULL)

n1++;

preorder(bt->lchild);

preorder(bt->rchild);

}

void main()

{

blink root;

root=creat();

preorder(root);

printf("此二叉数的接点数有:%d\n",n);

printf("此二叉数的叶子数有:%d\n",n1);}

2.2代码：

int get_deep(bitree T,int x)

{

if(T->data==x)

{

printf("%d\n",get_deep(T));

exit 1;

}

else

{

if(T->lchild)get_deep(T->lchild,x);

if(T->rchild)get_deep(T->rchild,x);

}

int get_depth(bitree T)

{

if(!T)return 0;

else

{

m=get_depth(T->lchild);

n=get_depth(T->rchild);

return(m>n?m:n)+1;

}

2.3代码：

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

char ch;

ch=getchar();

if(ch==' ') return(NULL);

else

{

bt=(struct node *)malloc(sizeof(bnode));

bt->data=ch;

bt->lchild=creat();

bt->rchild=creat();

}

return bt;

}

void preorder(blink bt)

{

if (bt)

{

printf("%c",bt->data);

preorder(bt->lchild);

preorder(bt->rchild);

}

void inorder(blink bt)

{

if(bt)

{

inorder(bt->lchild);

printf("%c",bt->data);

inorder(bt->rchild);

}

void postorder(blink bt)

{

if(bt)

{

postorder(bt->lchild);

postorder(bt->rchild);

printf("%c",bt->data);

}

int max(int x,int y)

{

if(x>y)

return x;

else

return y;

}

int depth(blink bt)

{

if (bt)

return 1+max(depth(bt->lchild),depth(bt->rchild));

else

}

{ return 0; void main()

blink root;

root=creat(); printf("\n"); printf("按先序排列:");

preorder(root);printf("\n");

printf("按中序排列:");

inorder(root);printf("\n");

printf("按后序排列:");

postorder(root);printf("\n");

} printf("此二叉数的深度是:"); printf("depth=%d\n",depth(root));

4. 实验小结

通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。

实验四图

1. 实验要求

1.1 熟悉图的各种存储方法。

1.2 掌握遍历图的递归和非递归的算法。

1.3 理解图的有关算法。

2. 实验内容

2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。

2.2 以邻接表作存储结构，给出拓扑排序算法的实现。

3. 实验代码

2.1代码：

void mattolist(int a[][],adjlist b[],int n) /*n为图的结点个数*/

{

for(i=0;i

}

2.2代码：

typedef struct vexnode

{

VertexType vertex; int in;/*增加一个入度域*/ ArecNodeTp * fristarc; for(j=n-1;j>=0;j--) if(a[i][j]!=0) {p=(arcnodetp *)malloc(sizeof(arcnodetp));/*产生邻接点*/ p->adjvex=j; p->nextare=b[i].firstare; b[i].firstarc=p; }

}AdjList[vnum];

typedef struct graph

{

AdjList adjlist; int vexnum,arcnum;

}GraphTp;

Top_Sort(GraphTp g)

{

LstackTp *p;/*建立入度为0的顶点栈S*/

int m,i,v;

initStack(S);

} for(i=0;iv printf("%d",v);/*输出v*/ m++; p=g.adjlist[i].fristarc;/*p=图g 中顶点v 的第一个邻接点*/ while(p!=NULL){//p存在 } (g.adjlist[p->adjvex].in)--;/*p的入度--*/ if(g.adjlist[p->adjvex].in==0)/*if(p的入度==0)*/ Push(S,p->adjvex);/*p入S 栈*/ p=p->nextarc;/*p=图g 中的顶点v 的下一个邻接点*/

4. 实验小结

通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。

实验五查找

1. 实验要求

1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。

1.2 能运用线性表的查找方法解决实际问题。

2. 实验内容

2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素

X ，并保持表的有序性。

2.2 根据给定的数据表，先建立索引表，然后进行分块查找。

3. 实验代码

2.1代码：

#include

#define MAXNUM 20

int input(int *);/*输入数据*/

int search(int *,int,int);/*查找插入位置*/

void plug(int *,int,int);/*插入数据*/

void main(void)

{

int data[MAXNUM],m; int insert=1; m=input(data); printf("Input the insert num:"); scanf("%d",data); insert=search(data,1,m);/*返回插入位置*/

plug(data,insert,m);

for(insert=1;insert<=m+1;insert++)>

printf("%3d",*(data+insert));

getch();

}

int input(int *data)

{

int i,m;

printf("\nInput the max num:");

scanf("%d",&m);

printf("input data\n");

for(i=1;i<>

scanf("%d",data+i);

return m;

}

int search(int *data,int low,int high)/*递归查找插入位置*/

{

int mid;

if(low>high) return low;/*没有找到插入数据，返回low*/

else{

}

search(data,low,high);

}

void plug(int *data,int insert,int m)

{

int i;

for(i=m;i>insert;i--)

*(data+i+1)=*(data+i); mid=(low+high)/2; if(*(data+mid)==*data) retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid)<*data) else="" if(*()data+mid)="">*data)

*(data+insert)=*data

}

2.2代码：

#include

#definr N 18 /*元素个数*/

#definr Blocknum 3 /*分块数*/

typedef struct indexterm

{

int key;/*最大关键字*/

int addr;/*块的起始地址*/

}index; /*索引表数据类型*/

index * CreateList(int data[],int n)/*建索引表*/

{

index *p;

int m,j,k;

m=n/BlockNum;/*分为BlockNum 块，每块有m 个元素*/

p=(index *)malloc(BlockNum *sizeof(index));

for(k=0;k<>

}

return p;

}

int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/ {

int low=0,high=m-1,mid,i;

(p+k)->key=dat a[m*k]; (p+k)->addr=m*k; for(j=m*k;j(p+k)->key) (p+k)->key=data[j];/*块的最大关键字*/

int b=n/m;/*每块有b 个元素*/

while(low<=high){>

}

if(low

for(i=(list+low)->addr;i<=(list+low)->adder+b-1&&rectab[i]!=k;i++);

}

return -1;

}

void main()

{

int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; int key;

index *list;

printf("please input key:\n");

scanf("%d",&key);

list=CreateList(record,N);

printf("data postion id %d\n",BlockSearch(list,record,N,BlockNum,key)); } if(i<=(list+low)->addr+b-1) return i; mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1; else return -1;

4. 实验小结

通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。

范文三：数据结构实训报告

山东科技大学泰山科技学院

课程实训说明书

课程：数据结构

系部名称：信息工程系专业班级：

学生姓名：徐志宏＿＿＿

学号：

指导教师：学校: 2015年7月22日

第一章课程设计性质与目的..................................4

第二章设计内容及基本要求............................5

第三章详细设计说明......................................... 11

3.1 项目一............................................................. 7

3.2 项目二............................................................ 16

3.3 项目三.......................................................... 26

第四章实训总结.................................................. .37

附录（参考文献、核心代码）

第一章课程设计性质与目的

链表和顺序表操作的设计目的： 1．掌握线性表的在顺序结构和链式结构实现。 2．掌握线性表在顺序结构和链式结构上的基本操作。

二叉树操作的设计目的： 1．掌握二叉树的概念和性。2. 掌握任意二叉树存储结构。 3．掌握任意二叉树的基本操作。

第二章设计内容及基本要求

一、实验实训的基本要求是：

本实训面向应用，以解决实际问题为主。题目以选用学生相对比较熟悉的为宜，要求通过本实训，理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及物理存储结构，通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。

实训基本步骤：

1. 选题

设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复杂度。应根据题目大小、难度确定是否分组，组内成员人数。

2. 数据结构及算法设计

根据需求分析，选择合理的数据结构及设计相应的算法。

3. 编码

根据已设计的数据结构和算法，编写代码。

4. 测试

按照系统测试的原则、方法和步骤，对系统进行测试。测试中应形成测试报告。

5. 编写实训报告

实训说明书，内容及要求如下：

（1）封面

（2）成绩评定

（3）目录

（4）说明书正文，主要内容包括：

一、设计题目

二、运行环境（软、硬件环境）

三、数据结构及算法设计的思想

四、数据结构及算法设计

五、源代码

六、运行结果分析

七、实习总结（收获及体会）

参考资料：附录（核心代码）。

二、设计内容项目一：顺序表操作

1、设计目的

（1）掌握线性表的在顺序结构上的实现。

（2）掌握线性表在顺序结构上的基本操作

2、设计内容和要求

利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。

项目二：链表操作

1、设计目的

（1）掌握线性表的在链式结构上的实现。

（2）掌握线性表在链式结构上的基本操作

2、设计内容和要求

利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。

项目三：二叉树的基本操作

1、设计目的

（1）掌握二叉树的概念和性质

（2）掌握任意二叉树存储结构。

（3）掌握任意二叉树的基本操作。

2、设计内容和要求

（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。

（2）求二叉树高度、结点数、度为1的结点数和叶子结点数。

第三章详细设计说明

项目一：

顺序表操作：

考查知识点：（1）利用顺序表的插入运算建立顺序表；

（2）实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；

（3）能够在屏幕上输出操作前后的结果。

一、算法

1. 创建：#define LIST_INIT_SIZE 100

#define LISTINCREMENT 20

typedf struct{

Elem Type *elem;

int length;

int listsize;

}SqList;

Status InitList.Sq(SqList&L){

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);

L.lengh=0;

L.listsize=LIST_INIT_SIZE;

return Ok;

}//InitList_Sq

2. 插入:Status ListInsert_Sq(SqList&L,int i,ElemType e){//插入

if(i<1||i>L.length+1)return ERROR;

if(L.length>=L.listsize){

newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]);//q指示插入位置

for(p=&(L.elem[L.length-1);p>=q;--p)*(p+1)=*p;

*q=e

++L.length；

return OK;

}//ListInsert_Sq

3. 删除：Status ListDelete_Sq(SqList &L，nt i,ElemType&e){

if((i<1||(i>L.length))return ERROR;

p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1;//表尾元素的位置

for(++p;p<>

--L.length;//表长减1

return OK;

}//ListDelete_Sq

4. 查找：Int LocateElem_Sq(SqList L，ElemType e，

Status （*compare）（ElemType ，

ElemType ））{

i=1；

p=L.elem;

while(i<>

if(i<=l.length) return="">

else return 0;

}//LocateElem_Sq

二、源代码

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 20

typedef struct { //查找

}SqList; int length; int listsize;

int InitList_Sq(SqList &L) {

L.list = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (!L.list) exit (OVERFLOW); // 存储分配失败

int i,y;

L.length = 0;

L.listsize = LIST_INIT_SIZE;

printf("请输入元素个数:");

scanf("%d",&y); printf("请输入元素:\n"); for(i=0;i

return OK;

} // InitList_Sq

//*****************输出函数******************

void output_Sq(SqList &L)

{

}

//*****************插入*********************

Status ListInsert_Sq(SqList &L){ printf("输出顺序表\n"); for(int i=0;i

int i,e; printf("请输入插入位置i:"); scanf(" %d",&i); if(i < 1="" ||="" i=""> L.length + 1) return ERROR; if(L.length >= L.listsize){ newbase = (ElemType *)realloc(L.list, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.list = newbase; L.listsize += LISTINCREMENT; } q = &(L.list[i-1]); // q指示插入位置 for (p = & (L.list[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置及之后的元素右移

printf("输入插入数值e: "); scanf("%d",&e); *q = e; ++L.length; printf("输出插入之后的顺序表:"); for( i=0;i

} // ListInsert_Sq

//*****************删除*********************

int ListDelete_Sq(SqList &L){

ElemType *p,*q; int i,e;

printf("请输入你要删除的元素位序："); scanf("%d",&i); if ((i < 1)="" ||="" (i=""> L.length)) return ERROR; p = & (L.list[i-1]); e = *p; q = L.list + L.length - 1; // 表尾元素的位置

printf("删除的元素值为: %d\n",e);

for (++p; p <= q;="">

*(p-1) = *p;

--L.length;

for( i=0;i<>

printf("%d ",L.list[i]);

printf("\n");

return OK;

} // ListDelete_Sq

//******************查找********************

Status LocateElem_Sq(SqList L){

int e,i;

printf("请输入你要查找元素的数值:

scanf("%d",&e);

printf("你要查找元素的位序为: ");

for(i=0;i<>

{

if(e==L.list[i])

printf("%d ",i+1);

}

printf("\n");

return 0;

} ");

//************排序（由小到大）*************

void Print_Sq(SqList &L)

{int t;

}

//*****************计数********************

void ListLength_Sq(SqList L){

}

//*****************逆置********************

void inverse_Sq(SqList &L)

{

int t,i; for(i=0;i<=l.length -1;i++)="" {="" t="L.list[i];" l.list[i]="L.list[L.length-i-1];" l.list[l.length-i-1]="t;" }="" printf("输出逆置顺序表\n");="" for(="" i="">L.list[i+1]) {t=L.list[i];L.list[i]=L.list[i+1];L.list[i+1]=t;} printf("输出排序（由小到大）表\n"); for(int i=0;i

} //*****************退出*********************

int Quit_Sq(SqList L)

{

}

//****************主函数********************

void main()

{

SqList L; int i; printf(" 1. 构造 \n"); printf(" 2. 插入 \n"); printf(" 3. 删除 \n"); printf(" 4. 排序 \n"); printf(" 5. 计数 \n"); printf(" 6. 查找 \n"); printf(" 7. 逆置 \n"); printf(" 8. 输出 \n"); printf(" 9. 退出 \n"); for(;;) { printf("Please choose 1 to 9 :\n"); scanf("%d",&i); switch(i) { case 1:InitList_Sq(L);break; case 2:ListInsert_Sq(L); break; exit (0); return 0;

} case 4:Print_Sq(L); break; case 5:ListLength_Sq(L); break; case 6:LocateElem_Sq(L);break; case 7:inverse_Sq(L);break; case 8:output_Sq(L);break; case 9: Quit_Sq(L);break; default:printf("输入有误"); } }

三、操作结果

项目二：

链表操作

考查知识点：（1）利用链表的插入运算建立链表；

（2）实现链表的查找、插入、删除、计数、输出、排序、逆置等运

算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写

成函数）；

（3）能够在屏幕上输出操作前后的结果。

一、算法

1. 创建：

void CreateList_L(LinkList &L){ //逆序输入n 个元素的值，建立带头结点的单链线性表L 。

L=(LinkList)malloc(sizeof(LNode));//生成新的结点

L->next=NULL;

//先建立一个带头结点的单链表

for(i=n;i>0;--i)

{

p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);

p->next = L->next;L->next = p; //插入到表头

}

}//CreateList L

2. 插入：

Status ListInsert_L(LinkList &L,int i ,ElemType e){ //插入 p=L;j=0;

while(p&&j<>

{

p=p->next;

++j;

}

if(!p||j>i)return ERROR；

s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

3. 删除：

Status ListDelete_L(LinkList &L,int &e){ //删除

j=0;

p=L;

while(p->next && j

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

return ERROR;

q=p->next;

p->next=q->next;

e=q->data;

free(q);

return OK;

}//ListDelete_L

4. 查找:

Status GetElem_L(LinkList L,int i , ElemType &e) //查找 {

p=L->next;

j=1;

while(p && j

{

p=p->next;

j++;

}

if(!p||j>1)retun ERROR

e=p->data;

retun OK;

}//GetElem.L

二、源代码

#include

#define OK 1

#define ERROR 0

typedef struct LNode

{

int data;

struct LNode * next;

}LNode, * LinkList;

//逆序输入n 个元素的值，建立带头结点的单链线性表L 。 void CreateList_L(LinkList &L){

int i,x;

LNode *p=NULL;

L=(LinkList)malloc(sizeof(LNode));//生成新的结点

L->next=NULL; //先建立一个带头结点的单链表 printf("请输入结点个数:");

scanf("%d",&x);

printf("请输入各结点元素的值为:");

for(i=x;i>0;--i) //逆序输入x 个元素的值

{

p=(LinkList)malloc(sizeof(LNode));

scanf("%d",&p->data);

p->next = L->next;L->next = p; //插入到表头

}

p=L->next; //将p 指向头结点

//输出已创建的链表

printf("逆序输出链表为:\n");

while(p)

{

printf("%d ",p->data);

p=p->next;

}

//*****************插入*******************

int ListInsert_L(LinkList &L){

LNode *p,*s;

int j=0,e,i;

p=L;

printf("请输入所要插入的位置:");

scanf("%d",&i);

printf("请输入所要插入的数:");

scanf("%d",&e);

while(p&&j<>

{

p=p->next;

++j;

}

if(!p||j>i-1)

printf("输入数据有误, 请输入数值在1 -- x+1之间输入"); s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

p=L ->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("\n");

return OK;

}

//*****************删除********************

int ListDelete_L(LinkList &L,int &e){

LNode *p,*q;

int i,j=0;

p=L;

printf("请输入要删除的第几个结点:");

scanf("%d",&i);

while(p->next && j

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

printf("输入的数值错误或删除位置不合理");

q=p->next;

p->next=q->next;

e=q->data;

free(q);//释放被删除结点

printf("被删除结点的数值为: %d\n",e);

p=L ->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("\n");

return OK;

}

//******************计数********************

void CountList_L(LinkList &L)

{

int i=0;

LNode *p=L->next;

while(p)

{i++;

p=p->next;}

printf("结点个数为:%d\n",i);

}

//*****************查找*******************

int LocateElem_L(LinkList L)

{

LinkList p=L;

int i,j=0;

printf("请输入要查找的数的序号:");

scanf("%d",&i);

while(p && j

{

p=p->next;

j++;

}

if(j!=i||!p)

{

printf("参数i 错或单链表不存在");

return(NULL);

}

printf("你查找的第 %d 个结点的数值为 %d\n",i,p->data); return OK;

}

//*******************排序******************* void SortList_L(LinkList L)

{

int i,j,t,k = 0;

LNode *p = L->next,*q;

while(p)

{

k++;

p=p->next;

}

p=L->next; q=p->next; //初始化

for(i=0;i<>

{

p = L->next;

for(j=0,p;jnext)

{

q = p->next;

if(p->data > q->data) //升序

{

t=p->data;

p->data=q->data;

q->data=t;

}

p=L->next;

printf("输出升序的链表为:\n");

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("\n");

}

//*******************输出***************

void OutputList_L(LinkList L)

{

LNode *p;

p=L->next;

while(p)

{

printf("%5d",p->data);

p=p->next;

}

printf("\n");

}

//*******************逆置****************

int ReverseList_L(LinkList &L)

{

LNode *p ,*q;

p=L->next;

q=p->next;

L->next=NULL;

while(p->next)

{

p->next=L->next;

L->next=p;

p=q;

q=q->next;

}

p->next=L->next;

L->next=p;

printf("逆置后的链表结果为:");

for(p=L->next;p;p=p->next)

printf("%d ",p->data);

printf("\n");

return 0;

}

//***************主函数**************

int main()

{

LinkList L=NULL;

int i,e;

printf("逆序输入创建一个链表并实现下列功能\n");

printf(" 1. 创建 \n");

printf(" 2. 插入 \n");

printf(" 3. 删除 \n");

printf(" 4. 计数 \n");

printf(" 5. 查找 \n");

printf(" 6. 排序 \n");

printf(" 7. 输出 \n");

printf(" 8. 逆置 \n");

for(;;)

{

printf("请在1-8功能中选择一个: ");

scanf("%d",&i);

//************函数调用*************

switch(i)

{

case 1:CreateList_L(L); break;

case 2:ListInsert_L(L); break;

case 3:ListDelete_L(L,e); break;

case 4:CountList_L(L); break;

case 5:LocateElem_L(L); break;

case 6:SortList_L(L); break;

case 7:OutputList_L(L); break;

case 8:ReverseList_L(L); break;

default:printf("输入错误");

}

printf("\n");

return 0;

}

三、操作结果

项目三：

二叉树的操作：

一、考查知识点：1. 对任意给定的二叉树（顶点数自定）建立它的二叉链表存储

结构；

2. 利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、

判栈空）实现二叉树的先序、中序、后序三种遍历，输出

三种遍历的结果。

3. 求二叉树高度、结点数、度为1的结点数和叶子结点数。

二、算法：

1. 创建二叉树：

Status Createbitree(bitree &t) //功能1：构建二叉树的二叉链表

{ scanf(& ch); //按先序遍历建立二叉树 if(ch==’’)

T=NULL;

else

{

if(!(T=(BiTNde)malloc(sizeof(BiTNode))))exit(OVERFLOW); }

T->data=ch;

Createbitree(t->lchild);

Createbitree(t->rchild);

}

Return OK;

}//CreatBiTree

2. 先序遍历： Status PreOrderTraverse(Bitree T,Status（* visit）（TElemType) ）

{//采用二叉链表存储结构，Visit 是对数据元素操作的应用函

数

if(T)

{ if(Visist(T->data))

if (PreOrderTraverse(p->lchild,Visit));

if PreOrderTraverse(p->rchild,Visit));

}

return OK;

return ERROR;

}elese returnOK;

}// PreOrderTraverse

3. 中序遍历：Status InOrderTraverse(Bitree T,Status（* Visit）（TElemType) ）{ InitStack(s);Push (S,T);

While(!StackEmpty(s){

While(GetTop(s,p)&&p)Push(S,p->lchild);

Pop(S,p);

If(!StackEmpty(s)){

Pop(s,p);if (!Visit(p->data))retu ERROR;

Push(S,p->rchild);

}//if

}//While

Retun OK;

}// InOrderTraverse

二、源代码

#include

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

typedef void status;

typedef char BTtype;

typedef char Stype;

typedef struct BTnode {//定义二叉树存储结构

BTtype data;

struct BTnode *lc,*rc;

}BTnode,*BTtree;

typedef struct{//定义栈的存储结构

Stype *base;

Stype *top;

int stacksize;

} Sqstack;

int max(int a,int b){

return a>b?a:b;

}

char Creat(BTtree &t){//创建

char ch;

//printf("按顺序输入二叉树各节点的值：");

scanf("%c",&ch);

if(ch==' ') t=NULL;

else {

if(!(t=(BTtree )malloc(sizeof(BTnode)))){

printf("创建失败。。");

exit(overflow);

}

t->data=ch;

Creat(t->lc);

Creat(t->rc);

}

return ok;

}

char orderx(BTtree &t){//先序

BTtree p=t;

if(p){

printf("%c",p->data);

orderx(p->lc);

orderx(p->rc);

}

return 0;

}

char orderz(BTtree &t){//中序

BTtree p=t;

if(p){

orderz(p->lc);

printf("%c",p->data);

orderz(p->rc);

}

return 0;

}

char orderh(BTtree &t){//后序

BTtree p=t;

if(p){

orderh(p->lc);

orderh(p->rc);

printf("%c",p->data);

}

return 0;

}

int Depth(BTtree t){//求深度

int d,dl,dr;

if(!t) d=0;

else{

dl=Depth(t->lc);

dr=Depth(t->rc);

d=max(dl,dr)+1;

}

return d;

}

int Nodes(BTtree &t){//结点数

int num1,num2;

if(t==NULL)

return 0;

else{

num1=Nodes(t->lc);

num2=Nodes(t->rc);

return (num1+num2+1);

}

void Degree(BTtree t,int &n){//度为1的结点个数

//int n=0;

if(t){

if((t->lc && !t->rc) || (!t->lc && t->rc))

n++;

Degree(t->lc,n);

Degree(t->rc,n);

}

void Leaves(BTtree &t,int &yz){//叶子数

//int yz=0;

if(t){

if((!t->lc) && (!t->rc))

yz++;

Leaves(t->lc,yz);

Leaves(t->rc,yz);

}

//return yz;

}

void Quit(){//退出

exit(0);

}

int main(){

BTtree t;

int yz=0;

int n=0;

int x;//用于case 或if

printf("需先按顺序输入二叉树各节点的值：");

if(Creat(t)) printf("创建成功！\n");

printf("1、先序\n2、中序\n3、后序\n4、求深度\n5、求结点数\n6、

求度为一的结点数\n7、求叶子数\n8、退出\n");

/*for(;;){

printf("请选择1-9：");

scanf("%d",&x);

switch(x){

case 1:printf("按顺序输入二叉树各节点的值："); Creat(t);

printf("创建成功！\n"); break;

case 2:printf("先序遍历二叉树：");

orderx(t);

printf("\n");break;

case 3:printf("中序遍历二叉树：");

orderz(t);

printf("\n");break;

case 4:printf("后序遍历二叉树：");

orderh(t);

printf("\n");break;

case 5:printf("二叉树的深度为：%d\n",Depth(t));break; case 6:printf("二叉树的节点数

为：%d\n",Nodes(t));break;

case 7:Leaves(t,yz);

printf("叶子数为：%d\n",yz);break;

case 8:Degree(t,n);

printf("度为1的节点个数为：%d\n",n);break; case 9:Quit(); break;

default:printf("输入错误");

}

}*/

for(;;){

printf("请选择1-8：");

scanf("%d",&x);

/*if(x=1){

printf("按顺序输入二叉树各节点的值：");

Creat(t); printf("创建成功！\n");

}else*/

if(x==1){

printf("先序遍历二叉树：");

orderx(t);

printf("\n");

}else if(x==2){

printf("中序遍历二叉树：");

orderz(t);

printf("\n");

}else if(x==3){

printf("后序遍历二叉树：");

orderh(t);

printf("\n");

}else if(x==4){

printf("二叉树的深度为：%d\n",Depth(t)); }else if(x==5){

printf("二叉树的节点数为：%d\n",Nodes(t)); }else if(x==6){

Degree(t,n);

printf("度为1的节点个数为：%d\n",n); }else if(x==7){

Leaves(t,yz);

printf("叶子数为：%d\n",yz);

}else if(x==8){

Quit();

}else printf("输入有误。。\n");

}

/*printf("按顺序输入二叉树各节点的值：");

if(Creat(t)) printf("创建成功！\n");

printf("先序遍历二叉树：");

orderx(t);

printf("\n");

printf("中序遍历二叉树：");

orderz(t);

printf("\n");

printf("后序遍历二叉树：");

orderh(t);

printf("\n");

printf("二叉树的深度为：%d\n",Depth(t));

printf("二叉树的节点数为：%d\n",Nodes(t));

Degree(t,n);

printf("度为1的节点个数为：%d\n",n);

Leaves(t,yz);

printf("叶子数为：%d\n",yz);*/

return 0;

}

三、操作结果

第四章实训总结通过这次实训，我把在课本上所学到的理论知识，运用到了实际的编程当中，也让我受益颇深。在这个为期两周的实训中, 我发觉到了自己的弱项和不足项, 也经过努力去克服了它们.

最深刻的总结成一个公式:学了?学会了?会用了，有些东西自己利用所学的地只是远远不能用算法很好的表达出来, 只能借助于书本, 互联网查找资料, 甚至以前老师所给做的笔记才能勉强完成. 有些不足还是.

在开始的时候困难是很大的, 于是乎我并没有急于开工, 我先翻阅书本查找了有关知识点进行温习熟悉, 然后翻阅有关笔记, 上网查找资料. 之后我才开始编写算法, 实现目标这个过程中不免与同学进行交流合作. 这个铺桥的工作完成了. 下面的’’路’’也就好修了.

附录

参考文献：

（1）《C 程序设计（第二版）》，谭浩强编，清华大学出版社，1999

年1月。

（2）《C 语言程序设计题解与上机指导》，谭浩强编，清华大学

出版社，2000年11月。

（3）数据结构C 语言版，严蔚敏，吴伟民编著，清华大学出版

社，1997年4月。

范文四：数据结构实训报告

山东科技大学泰山科技学院

课程实训说明书

课程：数据结构（C

题目：单链表、二叉树

院系：信息工程系

2015年 12月 18 日

专业班级：计算机科学与技术学号：学生姓名：指导教师：

语言版）

一、设计题目············································1 课程设计题一：链表操作 1、设计目的 2、设计内容和要求

课程设计题二：二叉树的基本操作 1、设计目的 2、设计内容和要求

二、运行环境（软、硬件环境）····························1 1、软件环境 2、硬件环境

三、数据结构及算法设计的思想 ··························2 课程设计题一：链表操作

课程设计题二：二叉树的基本操作

四、数据结构及算法设计·································4 课程设计题一：链表操作课程设计题二：二叉树的基本操作

五、源代码 ············································6 课程设计题一：链表操作课程设计题二：二叉树的基本操作

六、运行结果分析 ······································16 课程设计题一：链表操作

1、利用链表的插入运算建立线性链表（头插法） 2、链表的查找 3、链表的插入 4、链表删除 5、链表的计数 6、链表的输出 7、链表的排序 8、链表的逆置

课程设计题二：二叉树的基本操作 1、建立二叉树（先序） 2、二叉树的先序遍历 3、二叉树的中序遍历 4、二叉树的后序遍历 5、求二叉树的高度 6、求二叉树的结点数 7、求二叉树的度为1的结点数 8、求二叉树的叶子结点数

七、实习总结（收获及体会）································22

一、设计目的

课程设计题一：链表操作

1、设计目的

（1）掌握线性表的在顺序结构和链式结构实现。（2）掌握线性表在顺序结构和链式结构上的基本操作。 2、设计内容和要求

（1）利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。

课程设计题二：二叉树的基本操作

1、设计目的

（1）掌握二叉树的概念和性质（2）掌握任意二叉树存储结构。（3）掌握任意二叉树的基本操作。 2、设计内容和要求

（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。（2）求二叉树高度、结点数、度为1的结点数和叶子结点数。

二、运行环境（软、硬件环境）

1、软件环境

Microsoft Visual C++ 6.0 2、硬件环境计算机一台

处理器：Intel(R) Core(TM) i3-4010U CPU @ 1.70GHz 1.70GHz

三、数据结构及算法设计的思想

课程设计题一：链表操作

（1）定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。（因为每个新生成的结点的插入位置在表尾，则算法中必须维持一个始终指向已建立的链表表尾的指针。）

（2）定义一个遍历查找（按序号差值）的算法，通过此算法可以查找到链表中的每一个结点是否存在。（单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 。令指针 p 始终指向线性表中第 j 个数据元素。设单链表的长度为 n ，要查找表中第 i 个结点，仅当 1≤i ≤n 时，i 的值是合法的。）

（3）定义插入结点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以在连链表的任意位置进行插入一个新结点。（在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。因此，在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。）（4）定义删除结点的操作，这个算法用于对链表中某个指定位置的结点的删除工作。（在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。）

（5）定义一个计数的算法，通过此算法可以统计链表中结点的个数。（6）定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。（7）定义一个排序（冒泡排序）的算法，通过此算法对表中元素按照一定顺序进行排列。

（8）定义一个逆置单链表的操作，通过定义此算法，可以逆置输出单链表。（将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点））

课程设计题二：二叉树的基本操作

（1）定义二叉树链表：二叉树的链式存储方式下每个结点包含3个域，分别记录该结点的属性值及左右子树的位置。其左右子树的位置是通过指针方式体现，其中Ichild 是指向该结点左子树的指针，rchild 为指向该结点右子数的指针。

结点结构：

（2）二叉树的创建：根据先序遍历结果建立二叉树，将第一个输入的结点作为二叉树的根结点，后继输入的结点序列是二叉树左右子树先序遍历的结果，由它们生成二叉树的左子数；再接下来输入的结点序列为二叉树右子树先序遍历的结果，应该由它们生成二叉树的右子树。而由二叉树左子树先序遍历的结果生成二叉树的左子树和由二叉树右子树先序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的先序遍历结果生成该二叉树的过程完全相同，只是所处理的对象范围不同，所以可以用递归方式实

现之。使用CreatBitree 建立一颗二叉树时，必须按其先序遍历的顺序输入结点的值，遍历过程中遇到空子树时，必须使用“#”代替。例如：ABC##DE#G##F###

（3）二叉树的先序遍历：首先访问根结点；然后按照先序遍历的方式访问根结点的左子树；再按照先序遍历的方式访问根结点的右子数。

（4）二叉树的中序遍历：首先按照中序遍历的方式访问根结点的左子树；然后访问根结点；最后按照中序遍历的方式访问根结点的右子树。（5）二叉树的后序遍历：首先按照后序遍历的方式访问根结点的左子树；然后按照后序遍历的方式访问根结点的右子树；最后访问根结点。（6）求二叉树的高度：二叉树T ，如果T 为空，则高度为0；否则，其高度为其左子树的高度和右子树的高度的最大值再加1。

（7）求二叉树的结点数：二叉树T ，若T 为空，则T 中所含结点的个数为0；否则，T 中所含结点个数等于左子树中所含结点个数加上右子树中所含结点的个数再加1。

（8）求二叉树度为1的结点数：二叉树T ，若T 为空，则T 中度为1的结点数为0；否则，T 所含度为1的结点数等于左子树不为空右子树为空和左子树为空右子树不为空的结点个数之和。

（9）求二叉树的叶子结点数：求二叉树中叶子结点的个数，即求二叉树的所有结点中左、右子数均为空的结点个数之和。

四、数据结构及算法设计

课程设计题一：链表操作

typedef struct LNode//线性表的单链表存储结构

void CreatList_L(LinkList &L,int n);//头插法建表（逆序建表）

void GetElem_L(LinkList &L);//按序号查值

Status ListInsert_L(LinkList &L,int i,ElemType e);//插入 Status ListDelete_L(LinkList &L,int i,ElemType &e);//删除 void ListLength(LinkList &L);//计数 void PrintList(LinkList &L);//输出 void ListSort(LinkList &L);//冒泡排序 void OpposeList(LinkList &L);//逆置

课程设计题二：二叉树的基本操作

typedef struct BiTNode//------二叉树的二叉链表存储结构---------

Status CreateBiTree(BiTree &T)//建立二叉树的存储结构 —— 二叉链表（先序）。

Status PreOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//先序遍历二叉树基本操作的递归算法在二叉链表上的实现

Status InOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//中序遍历二叉树基本操作的递归算法在二叉链表上的实现

Status PostOrderTraverse (BiTree &T,Status (*Visit)(ElemType e))//后序遍历二叉树基本操作的递归算法在二叉链表上的实现 Status Visit(ElemType e)// 对二叉树中的数据元素访问 int BiTreeDepth(BiTree &T)//求二叉树的高度 int CountNode(BiTree &T)//二叉树的结点数 int NodeOne(BiTree &T)//二叉树中度为1的结点数 int CountLeaf (BiTree &T) //统计二叉树叶子结点

五、源代码

课程设计题一：链表操作

#include #include #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType;

typedef struct LNode{ ElemType data;

struct LNode *next;

}LNode,*LinkList; int i,j,k; LinkList L,p,q,s,r,head;

void CreatList_L(LinkList

&L,int n);//头插法建表（逆序建表）

void GetElem_L(LinkList

&L);//按序号查值

Status ListInsert_L(LinkList

&L,int i,ElemType e);//插入

Status ListDelete_L(LinkList

&L,int i,ElemType &e);//删除

void ListLength(LinkList

&L);//计数

void PrintList(LinkList &L);//

输出

void ListSort(LinkList &L);//冒泡排序

void OpposeList(LinkList

&L);//逆置

void CreatList_L(LinkList &L,int n){//逆位序输入n 个元素的值，建立带表头结点的单链线性表L 。

L=(LinkList)malloc(sizeof(L

Node));

L->next=NULL;

//先建立一个带头结点的单链表 for(i=n;i>0;--i){

p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf("%d",&p->data); //输入元素值

p->next=L->next; //插到表头

L->next=p;

}

}//头插法建表（逆序建表）

void GetElem_L(LinkList &L){//L为带头接点的单链表的头指针。当第i 个元素存在时，其赋值给e 并返回ERROR int i,e; p=L->next;

j=1; //初始化，p 指向第

一个结点，j 为计时器

printf("请输入查找位

置:\n");

scanf("%d",&i);

while(p&&j

后查找，直到p 指向第i 个元素或p 为空 p=p->next; ++j; }

if(!p||j>i)

printf("第%d个元素不存

在!",i); //第i 个元素不存在

e=p->data;

//取第i 个元素

printf("查找结果

为:%d\n",e);

}//按序号查值

Status ListInsert_L(LinkList &L,int i,ElemType e){//在带头接点的单链线性表L 中第i 个位置之前插入元素e p=L; j=0;

printf("请输入插入位

置:\n");

scanf("%d",&i); while(p&&jnext;

++j;

} //

寻找第i-1个结点 if(!p||j>i-1)

return ERROR; //i

小于1或者大于表长加1

s=(LinkList)malloc(sizeof(L

Node)); //生成新结点

printf("请输入插入元

while(p->next&&j<>

素:\n");

scanf("%d",&e);

//寻找第i 个结点，并命令p 指向其前趋

s->data=e; p=p->next;

//插入L 中 s->next=p->next; p->next=s;

printf("插入后的链表为：

\n"); PrintList(L);

return OK; }//插入

Status ListDelete_L(LinkList &L,int i,ElemType &e){//在带头接点的单链线性表L 中，删除第i 个元素，并由e 返回其值 p=L; j=0;

printf("请输入删除元素位

置:\n");

scanf("%d",&i);

++j; }

if(!(p->next)||j>i-1)

return ERROR; //删除位置不合理 q=p->next;

p->next=q->next; //删除并释放结点 e=q->data; free(q);

printf("删除后的链表为：

\n"); PrintList(L);

return OK; }//删除

void ListLength(LinkList &L){ p=L;

int j=0;

//线性链表最后一个结点的

指针为空 while((p->next)!=NULL) { j++; p=p->next;

}

printf("单链表总共有%d个

元素\n",j); printf("\n"); }//计数

void PrintList(LinkList &L) { p=L->next; if(p==NULL)

printf("\n 链表为空!"); else while(p)

{

printf("%d ",p->data); p=p->next; }

printf("\n");

}//输出

void ListSort(LinkList &L)//排序 { int t; int count=0; p=L->next; while(p) {

count++; p=p->next; }

for(i=0;i

p=L->next;

for(j=0;j<>

p->next) {

if(p->data >

p->next->data) { t=p->data;

p->data=p->next->data;

p->next->data=t;

} } }

printf("排序后的链表为：

\n"); p = L->next; while(p)

{

printf("%d ",p->data); p=p->next; }

printf("\n");

}//冒泡排序(升序)

void OpposeList(LinkList &L){ p=L; p=p->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q;

}

printf("逆置后的链表为：\n"); PrintList(L); }//逆置

int main() {

int a,n,e;

printf("************【请先建立单链表】************\n");

printf("请输入元素个数

值:\n"); scanf("%d",&n);

printf("请输入%d个元

素:\n",n); CreatList_L(L,n);

for(;;) {

printf("--------------请选择如下操作码------------\n"); printf("\n");

printf("*****-----------【1】查找------------*****\n");

printf("*****-----------【2】插

入------------*****\n");

printf("*****-----------【3】删

除------------*****\n");

printf("*****-----------【4】计

break; break; break; break; break;

case 3: ListDelete_L(L,i,e);

数------------*****\n");

printf("*****-----------【5】输

case 4: ListLength(L);

出------------*****\n");

printf("*****-----------【6】排

case 5: PrintList(L);

序------------*****\n");

printf("*****-----------【7】逆

case 6: ListSort(L);

置------------*****\n");

printf("******************************************\n"); scanf("%d",&a); switch(a) { break; break;

case 7: OpposeList(L);

default:printf("选择错误!\n");

} } return 0;

case 1: GetElem_L(L);

}

case 2: ListInsert_L(L,i,e);

课程设计题二：二叉树的基本操作

#include #include #define OK 1 #define ERROR 0

#define OVERFLOW 0 typedef char ElemType; typedef int Status; typedef int TElemType;

//------二叉树的二叉链表存储结构---------

typedef struct BiTNode{ TElemType data;

struct BiTNode

*lchild,*rchild; }BiTNode,*BiTree; char ch;

//建立二叉树的存储结构 —— 二叉链表（先序）。 Status CreateBiTree(BiTree &T){ //按先序次序输入二叉树结点的值（一个字符），空格字符表示空树，构造二叉树链表表示的二叉树T 。 scanf("%c",&ch); if(ch=='#') T=NULL; else{

if(!(T=(BiTNode*)malloc(si

zeof(BiTNode)))) exit(OVERFLOW);

T->data=ch;

//生成根结点

CreateBiTree(T->lchild);

//构造左子树

CreateBiTree(T->rchild);

//构造右子树 } return 0;

}

//先序遍历二叉树基本操作的递归算法在二叉链表上的实现 Status PreOrderTraverse (BiTree &T,Status (*Visit)(ElemType e)) {

if(T){ if(!Visit(T->data)) return ERROR;

PreOrderTraverse(T->lchild,Visit); PreOrderTraverse(T->rchild,Visit); }

return OK; }

//中序遍历二叉树基本操作的递归算法在二叉链表上的实现

Status InOrderTraverse (BiTree &T,Status (*Visit)(ElemType e)) {

if(T){

}

Status Visit(ElemType e){

InOrderTraverse(T->lchild,Visit); // 对二叉树中的数据元素访问 if(e=='\0'){ if(!Visit(T->data)) return ERROR;

InOrderTraverse(T->rchild,Visit); }

return OK; }

//后序遍历二叉树基本操作的递归算法在二叉链表上的实现 Status PostOrderTraverse (BiTree &T,Status (*Visit)(ElemType e)) {

if(T){

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit); if(!Visit(T->data)) return ERROR;; }

return OK;

return ERROR; }else{

printf("%c",e); }

return OK; }

//求二叉树的高度

int BiTreeDepth(BiTree &T){ int Depthall,Depthl,Depthr; if (T==NULL) Depthall=0;

else {

Depthl=BiTreeDepth(T->lc

hild);

Depthr=BiTreeDepth(T->rc

hild);

Depthall=(Depthl>Depthr?

Depthl:Depthr)+1;

}

return Depthall;

}

//二叉树的结点数 int CountNode(BiTree &T){ if(T==NULL) return 0; else

return(CountNode(T->lchild)+CountNode(T->rchild)+1); }

//二叉树中度为1的结点数 int NodeOne(BiTree &T){ if(T==NULL) return 0;

else{

if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))

return 1;

else

return(NodeOne(T->lchild)+NodeOne(T->rchild)); }

}

//统计二叉树叶子结点 int CountLeaf (BiTree &T) { if ( T==NULL ) return 0; else{

if ((!T->lchild) && (!T->rchild)) // 无左、右子树 return 1; else

return(CountLeaf

( T->lchild)+CountLeaf ( T->rchild)); }

}

int main() {

BiTree T;

Status(*visit)(ElemType e)=Visit; int a;

printf("************【请先建立二叉树】************\n");

printf("请输入二叉树的元素

(空节点以#号表示):\n"); CreateBiTree(T);

for(;;) {

printf("--------------请选择如下操作码------------\n"); printf("\n");

printf("*****-----------【1】先序遍历------------*****\n");

printf("*****-----------【2】中

序遍历------------*****\n");

printf("*****-----------【3】后

序遍历------------*****\n");

printf("*****-----------【4】求

二叉树的高度------*****\n");

printf("*****-----------【5】二

叉树的结点数 -----*****\n");

printf("*****-----------【6】二

叉树中度为1的结点数-***\n");

printf("*****-----------【7】统

计二叉树叶子结点--*****\n");

printf("**********************************************\n"); scanf("%d",&a); switch(a) {

case 1:

PreOrderTraverse(T,visit); printf("\n"); break;

case 2: InOrderTraverse

(T,visit); printf("\n"); break;

case 3:

PostOrderTraverse (T,visit); printf("\n"); break; case 4: printf("二叉树的高度为：%d\n",BiTreeDepth(T)); break;

case 5: printf("二叉树的

结点数为：%d\n",CountNode(T)); break;

case 6: printf("度为1的

default:printf("选择错

结点数为：%d\n",NodeOne(T)); 误 !\n"); break;

case 7: printf("二叉树的

}

} } return 0;

叶子结点数

为：%d\n",CountLeaf(T)); break;

六、运行结果分析

课程设计题一：链表操作

1、利用链表的插入运算建立线性链表（头插法）

2、链表的查找

3、链表的插入

4、链表删除

5、链表的计数

6、链表的输出

7、链表的排序

8、链表的逆置

课程设计题二：二叉树的基本操作

1、建立二叉树（先序）

2、二叉树的先序遍历

3、二叉树的中序遍历

4、二叉树的后序遍历

5、求二叉树的高度

6、求二叉树的结点数

7、求二叉树的度为1的结点数

8、求二叉树的叶子结点数

七、实习总结（收获及体会）

通过这次实训，我获益匪浅：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

刚开学的时候有很多地方不理解，每次上课都留有很多疑问，但又不能及时的解决，所以遗留的问题越来越多，但是通过本次的上机操作实训，解决了我遗留的问题，在这段时间里，我不断的思考，不断的查找资料，不断的在电脑上调试运行查找错误，利用互联网查找一般会出现的错误，并分析原因，以防自己犯同样的错误。就这样，一步一步地走完这一星期，最终达到了个人目的。

本次实训是关于单链表和二叉树的相关操作，单链表的建立、查找、插入、删除、计数、输出、排序、逆置等运算；二叉树的建立、先序遍历、中序遍历、后序遍历以及求二叉树高度、结点数、度为1的结点数和叶子结点数。这些操作几乎涵盖了单链表和二叉树的全部知识点，可以说这些会了，其他的也就不成问题了。关键就在于决绝这些问题。

通过这一次的实训，不仅加深了对数据结构知识的了解，更复习了以前学习过的C 语言，重新复习了排序等经典算法，而且对于以前不懂得地方，例如主函数与子函数之间的实参，形参之间的传递，并且在二叉树的遍历部分复习了递归算法的使用。

编程时要认真仔细，出现错误要及时找出并改正，遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议。要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。

通过这次实训，让我对一个程序的数据结构有更全面更进一步的认识，但是遗憾的是由于实训时间短，在二叉树这块，全都是用的递归算法，递归算法虽然容易理解，但是它的时间复杂度很糟糕。然而非递归算法虽然不容易理解但是它有它的优点。

实训虽小，但是它带给我的却很多。这次实训出现的问题很多但是都被一一解决，遇到困难一定不要畏缩或者放弃，一定要努力寻找办法去解决，即使希望很渺茫也要尝试，万一要成功了呢！一分耕耘一分收获，这句话永远不会过时。平时多积累，多注意，多听多写多看，只有有足够的知识储备，才能源源不断的释放自己的能量。

附录：

参考资料：《数据结构》（C 语言版）清华大学出版社《数据结构题集》（C 语言版）清华大学出版社《数据结构》（C 语言）（第3版）人民邮电出版社

范文五：数据结构实训报告

学生实训报告

实训名称: 数据结构实训(全国交通咨询模拟)

指导教师:

姓名:

学号:

班级:

日期: 2011 年1月10 日~2011年1月21 日

一、实训项目项目名称:

全国交通咨询模拟

二、实训的目的

1.熟悉图数据结构;

2.掌握图的顺序存储结构—邻接表;

3.掌握最短路径算法

4.上机调试程序,掌握查错、排错使程序能正确运行。三(实训要求

1.每个人独立完成实训项目，相互之间可以交流，不能抄袭 2.实训的成果包括程序代码和报告

3.程序代码要有注释和说明

三、实验的环境:

1.硬件环境: PC机

2.软件环环境:Windows2000 +Visual C++6

四、算法描述:

建立图的数据结构，采用邻接矩阵作为其存储结构。存储以上的全国主要城市的交通信息。通过软件模拟的方法实现:给定出发点和终点，求出它们之间的最短路径，并给出最短路径的线路。五、源程序清单:

#include

#define VEX_NUM 26

#define MAXINT 1000000

typedef struct graph

{

char city[VEX_NUM][10];

int arcs[VEX_NUM][VEX_NUM]; }Mgraph;

void CreatGraph(Mgraph *G,int e); void Dijkstra(Mgraph *Gn, int v0,int path[],int dist[]);

void PutPath(Mgraph *g,int v0,int v1,int p[],int d[]);

int index(char s[],Mgraph *g); void main()

{

Mgraph *g;

int i;

int e;

int v0,v1;

char sr[10],dt[10];

int dist[VEX_NUM];

int path[VEX_NUM];

g=new Mgraph;

CreatGraph(g,30);

printf("输入出发城市和终点城市\n");

getchar();

gets(sr);

v0=index(sr,g);

gets(dt);

v1=index(dt,g);

Dijkstra(g,v0,path,dist);

PutPath(g,v0,v1,path,dist); }

void CreatGraph(Mgraph *G,int e)

{

int i,j,k,cost;

printf("输入城市名称\n");

for(i=0;i

scanf("%s",G->city[i]);

for(i=0;i

for(j=0;j

G->arcs[i][j]=MAXINT;

printf("输入城市之间的距离\n");

for(k=0;k

{

scanf("%d,%d,%d",&i,&j,&cost);

G->arcs[i][j]=cost;

G->arcs[j][i]=cost;

}

void Dijkstra(Mgraph *Gn, int v0,int path[],int dist[])

{

int s[VEX_NUM];

int v;

int w;

int i,j,k;

int min;

for(v=0; v

{

s[v]=0;

dist[v]=Gn->arcs[v0][v];

if(dist[v]

path[v]=v0;

else path[v]=-1;

}

dist[v0]=0;s[v0]=1;

for(i=1;i

{

min=MAXINT;

for(w=0;w

if(!s[w] && dist[w]

{

v=w;

min=dist[w];

}

s[v]=1;

for(j=0;j

if(!s[j] && (min+Gn->arcs[v][j]

{

dist[j]=min+Gn->arcs[v][j];

path[j]=v;

}

void PutPath(Mgraph *g,int v0,int v1,int p[],int d[])

{

int k;

int next;

int top=0;

int st[20];

if(d[v1]

{

st[top++]=v1;

next=p[v1];

while(next!=v0)

{

st[top++]=next;

next=p[next];

}

else

if(v1!=v0)

{

printf("%s->%s:没有路径\n",g->city[v0],g->city[v1]);

return;

}

st[top++]=v0;

while(top)

{

next=st[--top];

if(top!=0)

printf("%s->",g->city[next]);

else

printf("%s\n",g->city[next]);

}

printf("两个城市之间的最短距离为:%d\n",d[v1]);

}

int index(char s[],Mgraph *g) {

int i;

for(i=0;i

if(strcmp(s,g->city[i])==0)

return i;

}

六、运行结果:

七、实验运行情况分析(包括算法、运行结果、运行环境等问题的讨

论)。

转载请注明出处范文大全网 » 数据结构实训报告