数据结构实验题目（C语言）
·
目录
实验一：单列表的插入和删除
实验目的
（1）深入理解线性表的基本概念，掌握线性表的逻辑结构和链式存储结构。
（2）深入理解单链表的基本概念和简单程序设计方法。
（3）提高实际动手进行程序设计的能力，掌握单链表的基本算法及相关的操作应用。
实验要求
建立一个数据域定义为整数值的单链表，在链表中不允许有重复的数值。根据输入的数值，先
找到相应的结点，然后将其删除。
实验主要步骤
1、分析、理解给出的示例程序。
2、调试程序，并设计输入数据(如:12, 36, 43, 56, 67, 71, 85, 98,#)，测试程序的如下功能:
不允许重复数值的插入;
根据输入的数值，找到相应的结点并删除。
3、分析应用程序的运行情况。
4、修改程序:
(1)增加插入结点的功能。
(2)将建立链表的方法改为头插入法。
实验代码
#include"stdio.h"
#include"strine.h"
#include"stdlib.h"
typedef struct node//定义结点
{
int data; //结点的数据域为整数值
struct node *next://结点的指针域
}ListNode;
typedef ListNode * LinkList; //自定义LinkList单链表类型
LinkList CreatListRl( ); //函数，用尾插入法建立带头结点的单链表
LmkList CreatList(void); //函数，用头插入法建立带头结点的单链表
ListNode *LocateNode( ); //函数，按值查找结点
void DeleteList( ); //函数，删除指定值的结点
void printlist( ); //函数，打印链表中的所有值
void DeleteAll( ); //函数，删除所有结点，释放内存
ListNode*AddNode( ); //修改程序:增加节点。用头插法，返回头指针
//=========主函数=================
void main( )
{
char num[5];
int dt;
LinkList head;
head=CreatList( ); //用头插入法建立单链表，返回头指针
printlist(head); //遍历链表输出其值
printf(" Delete node(y/n):”); //输入”y”或”n”去选择是否删除结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0)
{
printf("Please input Delete data:");
scanf("%d",&dt); //输入要删除的数值
DeleteList(head,dt);
printlist(head);
}
printf(" Add node ?(y/n):”); //输入”y”或''n"去选择是否增加结点
scant("%s",num);
if(strcmp(num."y')==O”strcmp(num,"Y"om )
{
head=AddNode(head);
}
printlist(head);
DeleteAll(head); //删除所有结点，释放内存
}
//========用尾插入法建立带头结点的单链表==========
LinkList CreatListR 1(void)
{
Int dt;
LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点
ListNode *s,*r,*pp,
r=head;
r->next=NULL;
printf(“Input 0 to end ”); ///输入”0”代表输入结束
printf("\n Please input Node_data:");
scanf("%d",&dt); //输入各结点的字符串
while(dt!=0)
{
pp=LocateNode(head, dt); //按值查找结点，返回结点指针
if(pp=NULL) //没有重复的字符串，插入到链表中
{
s=(ListNode *)malloc(sizeof(ListNode));
s->data=dt;
r->next=s;
r=s;
r->next=NULL;
}
Printf("Input 0 to end”);
printf("Please input Node data:");
scanf("%d”, &dt);
}
return head; //返回头指针
}
//============用头插入法建立带头结点的单链表==========
LinkList CreatList(void)
{
Int dt;
LinkList head, p;
head=(LinkList)malloc(sizeof(ListNode));
head->next=NULL;
while(1)
{
Printf("Input 0 to end”);
Printf("Please input Node-data:");
scanf("%d",&dt);
if(dt!=0)
{
if(LocateNode(head, dt)==NULL)
{
p=(LinkList)malloc(sizeof(ListNode));
p->data=dt;
p->next=head-next;
head->next=p;
}
}
else
break
}
return head
}
//=======按值查找结点，找到则返回该结点的位置，否则返回NULL
ListNode *LocateNode(LinkList head; int key)
{
ListNode *p=head->next; //从首元结点比较
While（p!=NULL && p->data!=key) //直到p为NULL或p->data为key止
p=p->next; //扫描下一个结点
return p; //若p=NULL则查找失败，否则p指向找到的值为key的结点
}
//============修改程序:增加节点================
ListNode *AddNode(LinkList head)
{
Int dt;
ListNode *s, *pp;
printf(" \n Please input a New Nodees data:");
scanf("%d", &dt); //输入结点的数值
pp=LocateNode(head,dt); //按值查找结点，返回结点指针
printf("ok! \n");
if(pp==NULL) //没有重复的字符串，插入到链表中
{
s=(ListNode *)malloc(sizeof(ListNode));
s->data=dt;
printf(“ok! \n");
s->next=head->next;
head->next=s;
}
return head;
}
//=======删除带头结点的单链表中的指定结点===============
void DeleteList(LinkList head, int key)
{
ListNode *p, *r, *q=head;
p=LocateNode(head, key); //按key值查找结点的
if(p==NULL) //若没有找到结点，退出
{
Printf("position error");
exit(0);
}
while(q->next!=p) //P为要删除的结点，q为p的前结点
q=q->next;
r=q->next;
q->next=r->next;
free(r);//释放结点
}
//============打印链表===============
void printlist(LinkList head)
{
ListNode *p=head->next; //从首元结点打印
while(p)
{
printf("%d, ",p->data);
p= p->next;
}
printf("\n");
}
//============删除所有结点，释放空间==========
void DeleteAll(LinkList head)
{
ListNode *p=head, *r;
while(p->next)
{
r=p->next;
free(p);
p=r;
}
free(p);
}
实验二：二叉树操作设计和实现
实验目的
（1）深入理解二叉树的基本概念和程序设计方法。
（2）深入理解二叉树的建立方法和遍历方法。
（3）提高实际动手进行程序设计的能力。
实验要求
采用二又链表作为存储结构。
（1）遍历二叉树方法应包括前序、中序、后序和层序方法。
（2）遍历二叉树方法同时，编写求二叉树叶结点个数的函数。
实验内容
（1）定义二叉链存储结构。
（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树）。
（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。
（4）编写测试主函数并上机运行。打印出运行结果，并结合程序运行结果进行分析。
实验主要步骤
1、分析、理解程序。
2、调试程序，设计一棵二又树，输入完全二又树的先序序列，用#代表虚结点(空指针)， 如AB#CD##E##F#GH###，建立二又树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点个数。
实验代码
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild, *rchild;
}BinTNode; //自定义二又树的结点类型
typedef BinTNode *BinTree; //定义二又树的指针
int NodeNum, leaf; //NodeNum为结点数，leaf为叶子数
//=========基于先序遍历算法创建二又树===============
//======要求输入先序序列，其中加入虚结点”#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==’#’)
return(NULL); //读入#，返回空指针
else
{
T= (BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//============NLR先序遍历===============
void Preorder(BinTree T)
{
If(T)
{
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//============LNR中序遍历==============
void Inorde(BinTree T)
{
if(T)
{
Inorde(T->lchild); //中序遍历左子树
printf("%c',T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN后序遍历============
void Postorder(BinTree T)
{
if(T)
{
Postorder(T->lchild); //后序遍历左子树
Postorder(T >rchild): //后序遍历右子树
printf("%C",T->data); //访问结点
}
}
//===========采用后序遍历求二又树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T)
{
int hl, hr, max;
if(T)
{
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //左右深度的最大值
NodeNum=NodeNum+1: //求结点数
if(hl==0 && hr==0)
leaf=leaf十1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//========利用”先进先出” (FIFO)队列，按层次遍历二叉树============
void Levelorder(BinTree T)
{
int front=0, rear=1;
BinTNode *cq[Max], *p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
Front=(front+l)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL)
{
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL)
{
rear=(rear+l)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//===============数叶子节点个数=============
int countleaf(BinTree T)
{
int hl.hr:
if(T)
{
hl=countleaf(T->lchild);
hr=countleaf(T->rchild);
if(hl==0 && hr==0) //若左右深度为0，即为叶子。
retum(1);
else return hl+hr;
}
else return 0;
}
//==========主函数===============
void main()
{
BinTree root;
char i;
int depth;
printf("\n");
printf("Creat Bin Tree; Input preorder:"); //输入完全二又树的先序序列，
//用#代表虚结点，如ABD####CE##F# #
root=CreatBinTree(); //创建二叉树，返回根结点
do //从菜单中选择遍历方式，输入序号。
{
printf("\t********** select ************\n");
printf("\t l: Preorder Traversal\n");
printf("\t 2: Iorder Traversal\n");
printf("\t 3: Postorder traversal\n");
printf("\t 4: PostTreeDepth, Node number, Leaf number\n");
printf(“\t 5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t 0: Exit\n" );
printf(“\t *******************************\n”);
fflush(stdin);
scanf("%c”, &i); //输入菜单序号(0-5 )
switch (i-'0')
{
case 1: printf("Print Bin tree Preorder:”);
Preorder(root); //先序遍历
Break;
case 2: printf("Print Bin Tree Inorder:”);
Inorde式root); //中序遍历
Break;
case 3: printf("Print Bin Tree Postorder:”)
Postorder(root); //后序遍历
Break;
case 4:
depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth %d BinTree Node number %d",depth,NodeNum);
printf(" BinTree Leaf number %d",countleaf(root));
break;
case 5: printf("Leve Print Bin Tree:”);
Levelorder(root); //按层次遍历
Break;
default: exit(1);
}
printf(" `,n" );
}while(i!=0);
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)