实 验 报 告
实验课程： 数据结构
实验项目： 实验
专 业： 计算机科学与技术
姓 名： **
学 号： ***
指导教师： **
实验时间： 20**-12-7
重庆工学院计算机学院
数据结构实验报告
实验一 线性表
1. 实验要求
掌握数据结构中线性表的基本概念。
熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。
熟练掌握链表的各种操作和应用。
2. 实验内容
编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。
#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]＜=y)
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]);
}
试写一个算法，在无头结点的动态单链表上实现线性表插入操作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;
}
}
}
生成两个多项式PA和PB，求他们的和，输出“和多项式”。 typedef struct node
{int exp;
float coef;
struct node *next;
}polynode;
polynode *polyadd(polynode *pa,polynode *pb)
{
polynode *p,*q,*pre,*r;
float x;
p=pa-＞next;
q=pb-＞next;
pre=pa;
while((p!=NULL)&&(q!=NULL))
if(p-＞exp＞q-＞exp)
{
r=q-＞next;
q-＞next=p;
pre-＞next=q;
pre=q;
q=r;
}
else
if(p-＞exp==q-＞exp)
{
x=p-＞coef+q-＞coef;
if(x!=0)
{p-＞coef=x;
s=p;
}
else
{pre-＞next=p-＞next;
free(p);
}
p=pre-＞next;
r=p;
q=q-＞next;
free(r);
}
else
if(p-＞expexp)
{
pre=p;
p=p-＞next;
}
if(q!=NULL)
pre-＞next=q;
free(pb);
}
设计一个统计选票的算法，输出每个候选人的得票结果。 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=1;i＜=N;i++)
printf("%3d",a[i]);
printf("\n");
}
3. 实验心得体会
线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。
实验二 栈与队列
1. 实验要求
了解栈和队列的特性，以便灵活运用。 熟练掌握栈和有关队列的各种操作和应用。
2. 实验内容
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("按回车键退出");
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;
实验三 树
1. 实验要求
掌握二叉树，二叉树排序数的概念和存储方法。 掌握二叉树的遍历算法。
熟练掌握编写实现树的各种运算的算法。
2. 实验内容
编写程序，求二叉树的结点数和叶子数。 #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("此二叉数的接点数有:%d\n",n);
printf("此二叉数的叶子数有:%d\n",n1);
}
编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。
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;
}
}
编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。
#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("按后序排列:");
postorder(root);printf("\n");
printf("此二叉数的深度是:");
printf("depth=%d\n",depth(root));
}
3. 实验心得体会
通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。
实验四 建立二叉树并线索化
#include
#include
#define len sizeof(struct node)
#define null 0
typedef struct node{
int data;
int ltag,rtag;
struct node *lchild,*rchild;
}Treenode;
Treenode *pre=null;
Treenode *creat(){
Treenode *bt;
int n;
scanf("%d",&n);
if(n!=0){
bt=(Treenode *)malloc(len);
bt-＞data=n;bt-＞ltag=0;bt-＞rtag=0;
bt-＞lchild=creat();
bt-＞rchild=creat();
}
else bt=null;
return bt;
}
void preorder1(Treenode *t){
if(t!=null){
printf("%4d",t-＞data);
preorder1(t-＞lchild);
preorder1(t-＞rchild);
}
}
void preorder2(Treenode *t){
if(t!=null) {
preorder2(t-＞lchild);
printf("%4d",t-＞data);
preorder2(t-＞rchild);
}
}
void preorder3(Treenode *t){
if(t!=null){
preorder3(t-＞lchild);
preorder3(t-＞rchild);
printf("%4d",t-＞data);
}
}
void InThread(Treenode *T){
Treenode *p;
p=T;
if(p){
InThread(p-＞lchild);
if(!p-＞lchild){ p-＞ltag=1;
p-＞lchild=pre;
}
if(!pre-＞rchild){ pre-＞rtag=1;
pre-＞rchild=p;
}
pre=p;
InThread(p-＞rchild);
}
}
Treenode *inorderthreading(Treenode *T) /*中序线索化二叉树*/
{
Treenode *Thre; /*Thre为头结点的指针*/
Thre=(Treenode *)malloc(sizeof(Treenode));
Thre-＞lchild=T;
Thre-＞rchild=Thre;
pre=Thre;
InThread(T);
pre-＞rtag=1;
pre-＞rchild=Thre;
Thre-＞rchild=pre;
return Thre;
}
void InThrTravel(Treenode *Thre) /*中序遍历二叉树*/
{
Treenode *p;
p=Thre-＞lchild;
while(p!=Thre){ /*指针回指向头结点时结束*/ while(p-＞ltag==0)
p=p-＞lchild;
printf("%4d",p-＞data);
while(p-＞rtag==1 && p-＞rchild!=Thre){
p=p-＞rchild;
printf("%4d",p-＞data);
}
p=p-＞rchild;
}printf("\n");
}
void main()
{
Treenode *tree;
int i;
printf("建立二叉树:\n");
tree=creat();
printf("请选择遍历二叉树的方法:\n\n1.先根序遍历.\n2.中根序遍历.\n3.后根序遍历.\n");
scanf("%d",&i);
while(i＞3 && i＜1){
scanf("%d",&i);
}
switch(i)
{
case 1:preorder1(tree);break;
case 2:preorder2(tree);break;
case 3:preorder3(tree);break;
} } printf("\n中根序线索遍历:\n"); tree=inorderthreading(tree); InThrTravel(tree);
实验五 哈夫曼树和哈夫曼编码
#include
#include
#define null 0
#define n 4
#define m 2*n-1 /*树中结点数*/
typedef struct
{
int weight; /*权值*/
int parent,llink,rlink;
}node;
typedef struct
{
int start;
char bits[n+1];
}codetype;
typedef struct
{
char c;
codetype code;
}element;
node tree[m+1]; /*下标取1到m,0作为空指针标志*/
void inithafumantree(node tree[])
{
int i;
for(i=0;i＜=m;i++) {
tree[i].parent=0;
tree[i].llink=0;
tree[i].rlink=0;
}
}
void inputweight(node tree[])
{
int i;
printf("请输入各结点的权值:\n");
for(i=1;i＜=n;i++) {
printf("第%d个结点的权值:",i);
scanf("%d",&tree[i].weight);
}
}
void select(int pre,int *min1,int *min2)
{
int i;
*min1=*min2 = 0;
for(i=1;i
if(tree[i].parent==0) {
if(tree[*min1].weight＞= tree[i].weight) {
*min2 = *min1; *min1 = i;
}
else if(tree[*min2].weight＞tree[i].weight) *min2=i; }
}
}
void sethuftree(node tree[m+1]){
int i,x1,x2;
printf("构造哈夫曼树.\n\n");
inithafumantree(tree);
inputweight(tree);
for(i=n+1;i＜=m;i++){
select(i-1,&x1,&x2);
tree[x1].parent=i;
tree[x2].parent=i;
tree[i].llink=x1;
tree[i].rlink=x2;
tree[i].weight=tree[x1].weight+tree[x2].weight;
}
}
void encode(node tree[],element table[]){
int i,s,f;
codetype c;
for(i=1;i＜=n;i++){
table[i].c=tree[i].weight;
c.start=n+1;s=i;
while(f=tree[s].parent)
{ c.bits[--c.start]= (s==tree[f].llink)?'0':'1';s=f;} table[i].code=c;
}
}
void main(){
int i;
element table[n+1];
sethuftree(tree);
encode(tree,table);
printf("\n输出Huffman编码\n");
for(i=1;i＜=n;i++) {
printf("\n %c :",table[i].c);
puts(table[i].code.bits);
}
}
实验六 建立图并遍历
#include
#include
#define MAX 1000
#define MAXN 100
typedef struct{
char vexs[MAXN];
int edges[MAXN][MAXN];
int n,e;
}MGraph;
void createmgraph(MGraph *g) {
int i,j,k,w ; char Node='a';
printf("\nPlease input n:"); scanf("%d",&g-＞n); printf("Please input e:");
scanf("%d",&g-＞e);
for(j=0;jn;j++) g-＞vexs[j]=Node++;
for(i=0;in;i++)
for(j=0;jn;j++)
if(i==j) g-＞edges[i][j]=0;
else g-＞edges[i][j]=MAX;
for(k=0;ke;k++) {
printf("Input i,j,w:(eg. 0,1,5)\n"); scanf("%d,%d,%d",&i,&j,&w);
g-＞edges[i][j]=w;
}
printf("\nThe graph is: \n\n");
printf("\t ");
for(k=0;kn;k++) {
printf("%3c",g-＞vexs[k]);
if(k==g-＞n-1) printf("\n\n");
}
for(i=0;in;i++){
printf("\t%c ",g-＞vexs[i]);
for(j=0;jn;j++)
if(g-＞edges[i][j]==MAX) printf("%3c",MAX-923); else printf("%3d",g-＞edges[i][j]);
printf("\n");
}
}
void main() {
MGraph *g;
g=(MGraph *)malloc(sizeof(MGraph));
createmgraph(g);
getchar();
}
实验七 图
1. 实验要求 熟悉图的各种存储方法。 掌握遍历图的递归和非递归的算法。 理解图的有关算法。
2. 实验内容 写出将一个无向图的邻接矩阵转换成邻接表的算法。
void mattolist(int a[][],adjlist b[],int n) /*n为图的结点个数*/
{
for(i=0;i
for(i=0;i
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;
}
}
以邻接表作存储结构，给出拓扑排序算法的实现。
typedef struct vexnode
{
VertexType vertex;
int in;/*增加一个入度域*/
ArecNodeTp * fristarc;
}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;i
if(g.adjlist[i].in==0)/*if(w的入度==0)*/
push(S,&v);/*w入S栈*/
m=0;
whlie(!EmptyStack(S)){
Pop(S,&v)//S出栈-＞v
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的下一个邻接点*/ }
}
if(m
else return 1;
}
实验八：二叉树排序树的建立及操作
#include
#include
#define NULL 0
#define maxsize 100
typedef struct node
{ int data;
struct node *left,*right;
}dnode;
int n=0;
void sort(dnode *t,int c)//将c插入到二叉排序树中
{ dnode *p;
if(c＞=t-＞data)
if(t-＞right==NULL)
{ p=(dnode *)malloc(sizeof(dnode));
p-＞data=c;
p-＞left=NULL;p-＞right=NULL;
t-＞right=p;
}
else sort(t-＞right,c);
if(cdata)
if(t-＞left==NULL)
{ p=(dnode *)malloc(sizeof(dnode));
p-＞data=c; p-＞left=NULL;p-＞right=NULL;t-＞left=p; }
else sort(t-＞left,c);
}
dnode *creat(){
dnode *ht;int x;
ht=(dnode *)malloc(sizeof(dnode));
printf("创建二叉排序树 (以0结束输入):");
scanf("%d",&x);
ht-＞data=x; n++;ht-＞left=NULL;ht-＞right=NULL;
scanf("%d",&x);
while(x＞0){
sort(ht,x);n++;
scanf("%d",&x);
}
return ht;
}
int find(dnode *b,int x,dnode *a[])
{ dnode *stack[maxsize],*p;
int top;
a[1]=NULL;
if(b!=NULL){ top=1;stack[top]=b;
while(top＞0){
p=stack[top];top--;
if(p-＞left-＞data==x || p-＞right-＞data==x) a[1]=p; if(p-＞data==x) {a[0]=p;return 1;}
if(p-＞right!=NULL) { top++;stack[top]=p-＞right;} if(p-＞left!=NULL) { top++;stack[top]=p-＞left;} }
}
a[0]=p;
}
dnode *delet(dnode *t){
dnode *p,*q,*s,*f,*a[2];
int flag=0,x;
p=(dnode *)malloc(sizeof(dnode));
f=(dnode *)malloc(sizeof(dnode));
printf("请输入要删除的结点:");
scanf("%d",&x);find(t,x,a);p=a[0];f=a[1];
if(p==NULL){printf("NO FIND!\n");exit(0);}
if(p-＞left==NULL) s=p-＞right;
else if(t-＞right=NULL) s=p-＞left;
else{ q=p;s=p-＞left;
while(s-＞right!=NULL)
{q=s;s=s-＞right;}
if(q==p) q-＞left=s-＞left;
else q-＞right=s-＞left;
p-＞data=s-＞data;free(s);flag=1;
}
if(flag==0){ if(f==NULL) t=s;
else if(f-＞left==p) f-＞left=s;
else f-＞right=s;
}
return t;
}
void inorder(dnode *t){
if(t!=NULL) { inorder(t-＞left);printf("%4d",t-＞data); inorder(t-＞right);
}
}
void main(){
dnode *h;h=creat();
printf("中序遍历二叉排序树:");
inorder(h);printf("\n");
h=delet(h);
inorder(h);printf("\n");}
实验九 查找
1. 实验要求 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。 能运用线性表的查找方法解决实际问题。
2. 实验内容 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。
#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＜=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＜=m;i++)
scanf("%d",data+i);
return m;
}
/**********************************************************/
int search(int *data,int low,int high)/*递归查找插入位置*/
{
int mid;
if(low＞high) return low;/*没有找到插入数据，返回low*/
else{
mid=(low+high)/2;
if(*(data+mid)==*data) retun mid;/*找到插入数据，返回mid*/
else if(*(data+mid)＜*data)
else if(*()data+mid)＞*data)
}
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); *(data+insert)=*data }
根据给定的数据表，先建立索引表，然后进行分块查找。
#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
(p+k)-＞key=dat a[m*k];
(p+k)-＞addr=m*k;
for(j=m*k;j
if(data[j]＞(p+k)-＞key)
(p+k)-＞key=data[j];/*块的最大关键字*/
}
return p;
}
int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/
{
int low=0,high=m-1,mid,i;
int b=n/m;/*每块有b个元素*/
while(low＜=high){/*块间折半查找*/
mid=(low+high)/2;
if((list+mid)-＞key＞=k)
high=mid+1;
else low=mid+1;
}
if(low
for(i=(list+low)-＞addr;i＜=(list+low)-＞adder+b-1&&rectab[i]!=k;i++);
if(i＜=(list+low)-＞addr+b-1)
return i;
else return -1;
}
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));
}
3. 实验心得体会
通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中
可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。