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

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

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

题目一:链表操作

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

1、设计目的

(1)掌握线性表的在顺序结构和?#35789;?#32467;构实现。

(2)掌握线性表在顺序结构和?#35789;?#32467;构上的基本操作。

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输入要查?#19994;?#20803;素位置: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("查?#19994;?#20803;素不存在n");

}

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

printf("查?#19994;?#20803;素为: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 %dn",e);

while(p&&j {

p=p->next;

++j;

} //寻?#19994;趇-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 {

//寻?#19994;趇个结点,并由p指向其前驱

p=p->next;

++j;

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

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

}

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

{

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

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

}

q=p->next;

p->next=q->next; //删除并?#22836;?#32467;点

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输入要查?#19994;?#20803;素位置: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("查?#19994;?#20803;素不存在n");

}

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

printf("查?#19994;?#20803;素为: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 %dn",e);

while(p&&j {

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

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

p=p->next;

++j;

} //寻?#19994;趇-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 {

//寻?#19994;趇个结点,并由p指向其前驱

p=p->next;

++j;

}

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

{

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

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

}

q=p->next;

p->next=q->next; //删除并?#22836;?#32467;点

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?????????【功能?#35828;ァ?????????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)掌握?#25105;?#20108;叉树存储结构;

(3)掌握?#25105;?#20108;叉树的基本操作。

2、设计内容和要求

对?#25105;?#32473;定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三?#30452;?#21382;,输出三?#30452;?#21382;的结果。

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

#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?????????【功能?#35828;ァ?????????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;

}

}

实习总结

紧张的两周数据结构实训很快就过去了,通过这两周的实践学习,不仅使我们巩固了以前的知识并在此基础上还对数据结构的特点?#36864;?#27861;有了更深的?#31169;猓?#20351;我们在这门课程的实?#35270;?#29992;上也有了一个提高。

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

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

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

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

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

从最初的查阅资?#31995;?#26368;后的程序的成功运行,两个星期的时间让我们经历了很多,?#24425;栈?#20102;很多。经过这次课程设计,我们不仅学到了很多知识和技能,更重要的是我们学会了如何运用所学知?#24230;?#35299;决实际问题。

总之,两个星期?#30446;?#31243;设计让我们受益匪?#22330;?#25105;们深深认识到,数据结构是计算机程序设计的重要理论?#38469;?#22522;础,它是计算机科学的核?#30446;?#31243;。要学好一门学科,没有刻苦钻研的精神是不行的,?#25381;性?#19981;断的尝试中,经历失败,从失败中总结经验,然后再不断的尝试,才能获得成功。

参考文献

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

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

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

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

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

实验一 线性表

1. 实验要求

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

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

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

2. 实验内容

2.1 编写一个函数,从一个给定的顺序表A 中删除元素值在x 到y 之间的所?#24615;?#32032;,要求以较高效?#19990;?#23454;现。

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;iscanf("%d,",&a[i]);

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

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

for(i=0;iprintf("%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;ia[i]=0;

nodetype *head;

head=create();

sat(head,a);

}

printf("候选人:"); for(i=1;i

4. 实验小结

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

实验二 栈与队列

1. 实验要求

1.1 ?#31169;?#26632;和队列的特性,以便灵活运用。

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

2. 实验内容

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

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

3. 实验代码

2.1代码:

#include

#include

#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("按回?#23548;?#36864;出");

getchar();exit(-2);

}

str++;

}

if(L->next)

{

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

puts("按?#25105;?#38190;退出");

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 的结点为根的子数的深?#21462;?/p>

2.3 编写程序,实现二叉树的先序,中序,后序遍历,并求其深?#21462;?/p>

3. 实验代码

2.1代码:

#include

#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("此二叉数的接点数有:%dn",n);

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

2.2代码:

int get_deep(bitree T,int x)

{

if(T->data==x)

{

printf("%dn",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

#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("?#26149;?#24207;排列:");

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

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

4. 实验小结

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

实验四 图

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;ifor(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. 实验小结

通过本章学习实验,对?#21152;?#20102;具体的认识。图?#24425;?#19968;种非线性的数据结构,这种结构有着广泛的应用,一切具有关?#26723;?#38382;题都可以用图来表示。

实验五 查找

1. 实验要求

1.1 掌?#36134;?#24207;查找、二分法查找、分块查找和哈希表查?#19994;?#31639;法。

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

2. 实验内容

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

X ,并保持表的有序性。

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

3. 实验代码

2.1代码:

#include

#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

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

getch();

}

int input(int *data)

{

int i,m;

printf("nInput the max num:");

scanf("%d",&m);

printf("input datan");

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;/*没有?#19994;讲?#20837;数据,返回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;/*?#19994;讲?#20837;数据,返回mid*/ else if(*(data+mid)*data)

*(data+insert)=*data

}

2.2代码:

#include

#include

#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

}

if(lowfor(i=(list+low)->addr;iadder+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 %dn",BlockSearch(list,record,N,BlockNum,key)); } if(iaddr+b-1) return i; mid=(low+high)/2; if((list+mid)->key>=k) high=mid+1; else low=mid+1; else return -1;

4. 实验小结

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

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

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

课程实训说明书

课程: 数据结构

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

学生姓名: 徐志宏 ___

学 号:

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

目录

第一章 课程设计性?#35270;?#30446;的..................................4

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

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

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

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

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

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

附录 (参考文献、核心代码)

第一章 课程设计性?#35270;?#30446;的

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

链表?#36864;?#24207;表操作的设计目的: 1.掌握线性表的在顺序结构和?#35789;?#32467;构实现。 2.掌握线性表在顺序结构和?#35789;?#32467;构上的基本操作。

二叉树操作的设计目的: 1.掌握二叉树的概念和性。2. 掌握?#25105;?#20108;叉树存储结构。 3.掌握?#25105;?#20108;叉树的基本操作。

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

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

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

实训基本步骤:

1. 选题

设计?#30446;?#39064;尽量结合教学、科研的实际课题,规模、大小?#23454;保?#20855;有一定复杂?#21462;?#24212;根据题目大小、难度?#33539;?#26159;否分组,组内成员人数。

2. 数据结构及算法设计

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

3. 编码

根据已设计的数据结构?#36864;?#27861;,编写代码。

4. 测试

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

5. 编写实训报告

实训说明书,内容及要求如下:

(1) 封面

(2) 成绩评定

(3) 目录

(4) 说明书正文,主要内容包括:

一、 设计题目

二、 运?#35874;?#22659;(软、?#24067;?#29615;境)

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

四、 数据结构及算法设计

五、 源代码

六、 运行结果分析

七、 实习总结(收获及体会)

参考资料:附录(核心代码)。

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

1、设计目的

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

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

2、设计内容和要求

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

项目二:链表操作

1、设计目的

(1)掌握线性表的在?#35789;?#32467;构上的实现。

(2)掌握线性表在?#35789;?#32467;构上的基本操作

2、设计内容和要求

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

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

1、设计目的

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

(2)掌握?#25105;?#20108;叉树存储结构。

(3)掌握?#25105;?#20108;叉树的基本操作。

2、设计内容和要求

(1)对?#25105;?#32473;定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三?#30452;?#21382;,输出三?#30452;?#21382;的结果。

(2) 求二叉树高?#21462;?#32467;点数、度为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(iL.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((iL.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

else return 0;

}//LocateElem_Sq

二、源代码

#include

#include

#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;ireturn 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 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; // 插入位?#30473;?#20043;后的元素右移

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 L.length)) return ERROR; p = & (L.list[i-1]); e = *p; q = L.list + L.length - 1; // 表尾元素的位置

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

for (++p; p

*(p-1) = *p;

--L.length;

for( i=0;iprintf("%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;iL.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 && jp=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

#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 && jp=p->next;

++j;

}

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

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

q=p->next;

p->next=q->next;

e=q->data;

free(q);//?#22836;?#34987;删除结点

printf("被删除结点的数值为: %dn",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("结点个数为:%dn",i);

}

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

int LocateElem_L(LinkList L)

{

LinkList p=L;

int i,j=0;

printf("请输入要查?#19994;?#25968;的序号:");

scanf("%d",&i);

while(p && j

{

p=p->next;

j++;

}

if(j!=i||!p)

{

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

return(NULL);

}

printf("你查?#19994;?#31532; %d 个结点的数值为 %dn",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. 对?#25105;?#32473;定的二叉树(顶点数自定)建立它的二叉链表存储

结构;

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

判栈空)实现二叉树的先序、中序、后序三?#30452;?#21382;,输出

三?#30452;?#21382;的结果。

3. 求二叉树高?#21462;?#32467;点数、度为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

#include

#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("二叉树的深度为:%dn",Depth(t));break; case 6:printf("二叉树的节点数

为:%dn",Nodes(t));break;

case 7:Leaves(t,yz);

printf("叶子数为:%dn",yz);break;

case 8:Degree(t,n);

printf("度为1的节点个数为:%dn",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("二叉树的深度为:%dn",Depth(t)); }else if(x==5){

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

Degree(t,n);

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

Leaves(t,yz);

printf("叶子数为:%dn",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("二叉树的深度为:%dn",Depth(t));

printf("二叉树的节点数为:%dn",Nodes(t));

Degree(t,n);

printf("度为1的节点个数为:%dn",n);

Leaves(t,yz);

printf("叶子数为:%dn",yz);*/

return 0;

}

三、操作结果

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

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

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

附录

参考文?#31069;?/p>

(1)《C 程序设计(第二版)》,?#27867;?#24378;编,清华大学出版社,1999

年1月。

(2)《C 语言程序设计题解与上机指导》,?#27867;?#24378;编,清华大学

出版社,2000年11月。

(3)数据结构C 语言版,严?#24471;簦?#21556;伟民编著,清华大学出版

社,1997年4月。

范文?#27169;?#25968;据结构实训报告

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

课程实训说明书

课程:数据结构(C

题目:单链表、二叉树

院 系: 信 息 工 程 系

2015年 12月 18 日

专业班级: 计算机科学与?#38469;?学 号: 学生姓名: 指导教师:

语言版)

目录

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

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

二、运?#35874;?#22659;(软、?#24067;?#29615;境)····························1 1、软件环境 2、?#24067;?#29615;境

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

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

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

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

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

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

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

七、实习总结(收获及体会)································22

一、设计目的

课程设计题一:链表操作

1、设计目的

(1)掌握线性表的在顺序结构和?#35789;?#32467;构实现。 (2)掌握线性表在顺序结构和?#35789;?#32467;构上的基本操作。 2、设计内容和要求

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

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

1、 设计目的

(1)掌握二叉树的概念和性质 (2)掌握?#25105;?#20108;叉树存储结构。 (3)掌握?#25105;?#20108;叉树的基本操作。 2、设计内容和要求

(1)对?#25105;?#32473;定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三?#30452;?#21382;,输出三?#30452;?#21382;的结果。 (2)求二叉树高?#21462;?#32467;点数、度为1的结点数和叶子结点数。

二、 运?#35874;?#22659;(软、?#24067;?#29615;境)

1、软件环境

Microsoft Visual C++ 6.0 2、?#24067;?#29615;境 计算机一台

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

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

课程设计题一:链表操作

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

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

(3)定义插入结点的算法,通过定义这个算法,并结合这查找前驱和后继的算法便可以在连链表的?#25105;?#20301;置进行插入一个新结点。(在链表中插入结点只需要修改指针。但同时,若要在第 i 个结点之前插入元素,修改的是第 i-1 个结点的指针。因此,在单链表中第 i 个结点之前进行插入的基本操作为:?#19994;?#32447;性表中第i-1个结点,然后修改其指向后继的指针。) (4)定义删除结点的操作,这个算法用于对链表?#24515;?#20010;指定位置的结点的删除工作。(在单链表中删除第 i 个结点的基本操作为:?#19994;?#32447;性表中第i-1个结点,修改其指向后继的指针。)

(5)定义一个计数的算法,通过此算法可以统?#23631;?#34920;中结点的个数。 (6)定义输出链表的算法,通过对第一步已经定义好的创建链表函数的调用,在这一步通过调用输出链表的函数算法来实现对链表的输出操作。 (7)定义一个排序(冒泡排序)的算法,通过此算法对表?#24615;?#32032;按照一定顺序进?#20449;帕小?/p>

(8)定义一个逆置单链表的操作,通过定义此算法,可以逆置输出单链表。(将原链表中的头结点和第一个元素结点断开(令其指针域为空),先构成一个新?#30446;?#34920;,然后将原链表中各结点,从第一个结点起,?#26469;?#25554;入这个新表的头部(即令每个插入的结点成为新的第一个元素结点))

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

(1)定义二叉树链表:二叉树的?#35789;?#23384;储方式下每个结点包含3个域,?#30452;?#35760;录该结点的属性?#23548;?#24038;右子树的位置。其左右子树的位置是通过指针方式体现,其中Ichild 是指向该结点左子树的指针,rchild 为指向该结点右子数的指针。

结点结构:

(2)二叉树的创建:根据先序遍历结果建立二叉树,将第一个输入的结点作为二叉树的根结点,后继输入的结点序列是二叉树左右子树先序遍历的结果,?#20260;?#20204;生成二叉树的左子数;再接下?#35789;?#20837;的结点序列为二叉树右子树先序遍历的结果,应该?#20260;?#20204;生成二叉树的右子树。而由二叉树左子树先序遍历的结果生成二叉树的左子树和由二叉树右子树先序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的先序遍历结果生成该二叉树的过程完全相同,只是所处理的对象范围不同,所以可以用递归方式实

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

(3)二叉树的先序遍历:首先访问根结点;然后按照先序遍历的方式访问根结点的左子树;再按照先序遍历的方式访问根结点的右子数。

(4)二叉树的中序遍历:首先按照中序遍历的方式访问根结点的左子树;然后访问根结点;最后按照中序遍历的方式访问根结点的右子树。 (5)二叉树的后序遍历:首先按照后序遍历的方式访问根结点的左子树;然后按照后序遍历的方式访问根结点的右子树;最后访问根结点。 (6)求二叉树的高度:二叉树T ,如果T 为空,则高度为0?#29615;?#21017;,其高度为其左子树的高度和右子树的高度的最大值再加1。

(7)求二叉树的结点数:二叉树T ,若T 为空,则T 中所含结点的个数为0?#29615;?#21017;,T 中所含结点个数等于左子树中所含结点个数加上右子树中所含结点的个数再加1。

(8)求二叉树度为1的结点数:二叉树T ,若T 为空,则T 中度为1的结点数为0?#29615;?#21017;,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为带?#26041;?#28857;的单链表的头指针。当第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("查找结果

为:%dn",e);

}//按序号查值

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

printf("请输入插入位

置:n");

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

++j;

} //

寻?#19994;趇-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);

//寻?#19994;趇 个结点,并命令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){//在带?#26041;?#28857;的单链线性表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; //删除并?#22836;?#32467;点 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;jp->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==' 跳跳猫猫援彩金