首页 > 代码库 > 数据结构实验总览
数据结构实验总览
实验1链表的插入和删除
【实验目的】
1、 了解单链表、循环链表和双链表的基本知识；
2、 掌握算法思想和数据结构的描述；
3、 掌握链表的插入、删除的相关语句及基本方法。
【实验步骤与要求】
1、 实验前的准备
（1） 了解C语言的基本概念；
（2） 了解C语言的基本段落。
2、 上机操作
（1） 了解链表的基本知识；
（2） 掌握算法思想和数据结构的描述；
（3） 掌握链表的插入、删除的相关语句及基本方法。
【实验内容】
设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。
【方法说明】
先定义结构体：
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
源代码1.1：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void head_insert(LinkList *root,int x)
{
LNode *p=(LNode*)malloc(sizeof(LNode));
p->data=http://www.mamicode.com/x;>
实验2 一元多项式相加
【实验目的】
1、了解链式存储结构的基本知识；
2、掌握算法思想和数据结构的描述；
3、结合一元多项式相加的运算规则。
【实验步骤与要求】
1、实验前的准备
（1）了解C语言的基本概念；
（2）了解C语言的基本段落。
2、上机操作
（1）了解链式存储结构的基本知识；
（2）掌握算法思想和数据结构的描述；
（3）掌握一元多项式相加的运算规则。
【实验内容】
结合书上第41页的例子，采用链式存储结构，讲两个线性链表表示的一元多项式相加，并输出。
【方法说明】
根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。
代码2.1：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct{
int a,k;
}ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void head_insert(LinkList *root,ElemType e)
{
LNode *p=(LNode*)malloc(sizeof LNode);
p->data.a=e.a;
p->data.k=e.k;
p->next=*root;
*root=p;
}
void head_insert(LinkList *root,int a,int b)
{
LNode *p=(LNode*)malloc(sizeof LNode);
p->data.a=a;
p->data.k=b;
p->next=*root;
*root=p;
}
void tail_insert(LinkList *root,ElemType e)
{
LNode *last=*root,*p=(LNode*)malloc(sizeof LNode);
p->data.a=e.a;
p->data.k=e.k;
p->next=NULL;
if(last==NULL)
{
(*root)=p;
return ;
}
while(last->next)
{
last=last->next;
}
last->next=p;
}
void _add(LinkList *root,LinkList *root1,LinkList *root2)
{
for(LNode *p=*root1,*q=*root2;p!=NULL||q!=NULL;)
{
if(q==NULL)
{
tail_insert(root,p->data);
p=p->next;
}
else if(p==NULL)
{
tail_insert(root,q->data);
q=q->next;
}
else
{
if(p->data.a<q->data.a)
{
tail_insert(root,p->data);
p=p->next;
}
else if(p->data.a==q->data.a)
{
if(p->data.k+q->data.k!=0)
{
ElemType e=p->data;e.k+=q->data.k;
tail_insert(root,e);
}
p=p->next;
q=q->next;
}
else
{
tail_insert(root,q->data);
q=q->next;
}
}
}
}
void show(LinkList p)
{
while(p)
{
printf("%d %d\n",p->data);
p=p->next;
}
}
int main()
{
LinkList ha=NULL,hb=NULL;
head_insert(&ha,10,1);
head_insert(&ha,5,1);
head_insert(&ha,4,1);
head_insert(&ha,1,1);
head_insert(&hb,8,1);
head_insert(&hb,5,1);
head_insert(&hb,4,-1);
head_insert(&hb,3,1);
head_insert(&hb,2,1);
printf("----A----\n");
show(ha);
printf("----B----\n");
show(hb);
LinkList hc=NULL;
_add(&hc,&ha,&hb);
printf("----C----\n");
show(hc);
return 0;
}
实验3 二叉树的遍历
【实验目的】
1、 了解二叉树的前序和中序序列排列；
2、 将C语言同二叉树的数据结构联系起来；
3、 掌握生成的二叉树的链表结构；
4、 掌握如何按层次输出二叉树的所有结点；
5、 掌握如何将动态二叉树转换为静态二叉链表。
【实验内容要求】
1、实验前的准备
（1）了解二叉树的基本概念；
（2）了解二叉树的基本结构。
2、上机操作
（3）了解二叉树的前序和中序序列排列；
（4） 将C语言同二叉树的数据结构联系起来；
（5） 掌握生成的二叉树的链表结构；
（6） 掌握如何按层次输出二叉树的所有结点；
（7） 掌握如何将动态二叉树转换为静态二叉链表。
【实验内容】
创建一个二叉树，对这棵动态二叉树进行分析，将其用静态二叉链表表示。二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。lchild和rdhild分别用于存储左右孩子的下标。
【方法说明】
先定义结构体：
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
此树中序遍历为：ABDG^^H^^^CE^^F^I^^
代码3.1：
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int cnt;
void build(BiTree *B)
{
char a;
scanf("%c",&a);
if(a=='^')
{
*B=NULL;
return ;
}
*B=(BiTNode*)malloc(sizeof(BiTNode));
(*B)->data=http://www.mamicode.com/a;>
实验4 无向图的深度优先搜索
【实验目的】
1、 了解图的定义、特点，区分无向图和有向图的概念；
2、 了解图的数据结构和搜索方法；
3、 掌握无向图的邻接矩阵、邻接表的表示方法；
4、 写出无向图的深度优先搜索程序。
【实验内容要求】
1、 了解图的定义、特点，区分无向图和有向图的概念；
2、 了解图的数据结构和搜索方法；
3、 掌握无向图的邻接矩阵、邻接表的表示方法；
4、 写出无向图的深度优先搜索程序。
【实验内容】
设无向图G有n个点e条边，写一算法建立G的邻接多表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。
【方法说明】
邻接表定义：
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define max 30
typedef struct edgenode{
int adjvex;
char info;
struct edgenode *next;
};
typedef struct vexnode{
char data;
struct edgenode *link;
}adjlist[max];
邻接矩阵定义：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 10
typedef struct vertex{
int num;
char data;
};
typedef struct graph{
struct vertex vexs[max];
int edges[max][max];
}adjmax;
代码4.1：
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define max 30
struct edgenode{
int adjvex;
struct edgenode *next;
};
struct vexnode{
char data;
struct edgenode *link;
}adjlist[max];
bool visit[max];
void add_edge(int a,int b)
{
edgenode *p=(edgenode *)malloc(sizeof(edgenode));
p->adjvex=b;
p->next=adjlist[a].link;
adjlist[a].link=p;
}
void dfs(int root)
{
visit[root]=1;
printf("%d %c\n",root,adjlist[root].data);
for(edgenode *e=adjlist[root].link;e!=NULL;e=e->next)
{
if(!visit[e->adjvex])dfs(e->adjvex);
}
}
void dfs_G(int n)
{
printf("dfs顺序:\n");
for(int i=0;i<n;i++)
visit[i]=0;
for(int i=0;i<n;i++)
if(!visit[i])dfs(i);
}
int main()
{
int n,m,a,b;char c;
printf("请输入结点数，边数：");
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
adjlist[i].data=http://www.mamicode.com/i+'A';>
实验5结合二叉树的二叉排序树设计
【实验目的】
1、 了解二叉排序树的定义，并结合二叉树的数据结构；
2、 掌握二叉排序树的排序方法。
【实验内容要求】
1、 了解二叉排序树的定义，并结合二叉树的数据结构；
2、 掌握二叉排序树的排序方法。
【实验内容】
二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。
【方法说明】
二叉排序树的定义：
#include<stdio.h>
#include<stdlib.h>
#define num 10
struct treenode{
int data;
struct treenode *lchild,*rchild;
};
代码5.1：
#include<stdio.h>
#include<stdlib.h>
#define num 10
typedef struct treenode{
int data;
struct treenode *lchild,*rchild;
}node,*BinTree;
BinTree search(BinTree t,int key,BinTree *p)
{
BinTree last,bt;
last=t;
bt=t;
while(bt)
{
if(bt->data=http://www.mamicode.com/=key)>
数据结构实验总览