数据结构实验总览

实验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=x;
	p->next=*root;
	*root=p;
}
void _union(LinkList *root1,LinkList *root2)
{
	LNode *p=*root1,*q=*root2;
	LinkList *last=root1;
	while(p)
	{
		while(q&&q->data<=p->data)
		{
			if(q->data<p->data)
			{
				head_insert(last,q->data);
				last=&((*last)->next);
			}
			q=q->next;
		}
		last=&(p->next);
		p=p->next;
	}
	while(q)
	{
		head_insert(last,q->data);
		q=q->next;
	}
}
void show(LinkList p)
{
	while(p)
	{
		printf("%d\n",p->data);
		p=p->next;
	}
}
int main()
{
	LinkList ha=NULL,hb=NULL;
	head_insert(&ha,10);
	head_insert(&ha,5);
	head_insert(&ha,4);
	head_insert(&ha,1);
	head_insert(&hb,8);
	head_insert(&hb,5);
	head_insert(&hb,3);
	head_insert(&hb,2);
	printf("----A----\n");
	show(ha);
	printf("----B----\n");
	show(hb);
	_union(&ha,&hb);
	printf("----A----\n");
	show(ha);
	printf("----B----\n");
	show(hb);

	return 0;
}

实验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=a;
	build(&((*B)->lchild));
	build(&((*B)->rchild));
}

int turn(BiTree B,BiTree b)
{
	int st=1,cnt=0;
	b[++cnt]=*B;
	while(cnt!=st-1)
	{
		BiTNode e=b[st++];
		if(e.lchild!=NULL)
		{
			b[++cnt]=*(e.lchild);
			b[st-1].lchild=(struct BiTNode *)cnt;
		}
		else b[st-1].lchild=(struct BiTNode *)0;
		if(e.rchild!=NULL)
		{
			b[++cnt]=*(e.rchild);
			b[st-1].rchild=(struct BiTNode *)cnt;
		}
		else b[st-1].rchild=(struct BiTNode *)0;
	}
	return cnt;
}
int main()
{
	BiTree B;
	printf("请以中序输入该树：");
	build(&B);
    printf("建树完成\n");
	BiTNode b[20];
	int cnt=turn(B,b);
	printf("转化完成，输出静态数组:\n");
	for(int i=1;i<=cnt;i++)
	{
		printf("%d %c",i,b[i].data);
		if(b[i].lchild)printf(" left:%c/%d",b[(int)(b[i].lchild)].data,(int)(b[i].lchild));
		else printf(" left:NO");
		if(b[i].rchild)printf(" right:%c/%d\n",b[(int)(b[i].rchild)].data,(int)(b[i].rchild));
		else printf(" right:NO\n");
	}
	return 0;
}//ABDG^^H^^^CE^^F^I^^

实验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=i+'A';
		adjlist[i].link=NULL;
	}
	printf("请依次输入结点编码串：");
	getchar();
	for(int i=0;i<n;i++)
	{
		scanf("%c%*c",&c);
		adjlist[i].data=c;
	}
	printf("请输入各条边：");
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		add_edge(a,b);
	}
	dfs_G(n);
	return 0;
}
/*
8 9
A B C D E F G H
0 1
1 3
1 4
4 7
3 7
0 2
2 6
2 5
5 6
*/

实验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==key)
		{
			*p=bt;
			return bt;
		}
		last=bt;
		if(bt->data>key)bt=bt->lchild;
		else bt=bt->rchild;
	}
	*p=last;
	return bt;
}
void insert(BinTree *bt,int key)
{
	BinTree p,q,r;
	q=*bt;
	if(search(q,key,&p)==NULL)
	{
		r=(BinTree)malloc(sizeof(treenode));
		r->data=key;
		r->lchild=r->rchild=NULL;
		if(*bt==NULL)*bt=r;
		else if(key<p->data)p->lchild=r;
		else p->rchild=r;
	}
}
int Bdelete(BinTree *bt,int key)
{
	BinTree f,p,q,s;
	p=*bt;f=NULL;
	while(p&&p->data!=key)
	{
		f=p;
		if(p->data>key)p=p->lchild;
		else p=p->rchild;
	}
	if(p==NULL)return 0;
	if(p->lchild==NULL)
	{
		if(f==NULL)*bt=p->rchild;
		else if(f->lchild==p)f->lchild=p->rchild;
		else f->rchild=p->rchild;
		free(p);
	}
	else 
	{
		q=p;s=p->lchild;
		while(s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		if(q==p)q->lchild=s->lchild;
		else q->rchild=s->lchild;
		p->data=s->data;
		free(s);
		return 1;
	}
	return 0;
}
void show(BinTree root)
{
	if(root)
	{
		show(root->lchild);
		printf("%d ",root->data);
		show(root->rchild);
	}
}
int main()
{
	BinTree b=NULL;
	insert(&b,1);
	insert(&b,6);
	insert(&b,4);
	insert(&b,2);
	insert(&b,5);
	insert(&b,3);
	printf("建树完成-----\n");
	show(b);puts("");
	printf("删除节点3-----\n");
	Bdelete(&b,3);
	show(b);puts("");
	return 0;
}

数据结构实验总览

原文：http://blog.csdn.net/u014569598/article/details/42119391