数据结构实训报告

实验一 线性表

1. 实验要求

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

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

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

2. 实验内容

2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。

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]<=y)

k++;

else

A[i-k]=A[i];

i++;

}

return(n-k);

2

数据结构实验报告

}

void main()

{

int i,j;

int a[maxsize];

printf(\"输入%d个数:\\n\

for(i=0;iscanf(\"%d,\

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

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

for(i=0;iprintf(\"%d \"\\n,a[i]);

}

3

数据结构实验报告

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)

{

4

数据结构实验报告

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;

}

5

数据结构实验报告

}

}

2.3代码：

typedef int elemtype

typedef struct linknode

{

elemtype data;

struct linknode *next;

}nodetype;

nodetype *create()

{

elemtype d;

nodetype h=NULL,*s,*t;

6

数据结构实验报告

int i=1;

printf(\"建立单链表:\\n\");

while(1)

{

printf(\"输入第%d个结点数据域\

scanf(\"%d\

if(d==0)break;

if(i==1)

{

h=(nodetype *)malloc(sizeof(nodetype));

h->data=d;h->next=NULL;t=h;

}

else

7

数据结构实验报告

{

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)

8

数据结构实验报告

{

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);

9

数据结构实验报告

printf(\"候选人:\");

for(i=1;i<=N;i++) printf(\"%3d\

printf(\"\\n得票数\\n\");

for(i=1;i<=N;i++)

printf(\"%3d\

printf(\"\\n\");

}

4. 实验小结

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

实验二 栈与队列

1. 实验要求

1.1 了解栈和队列的特性，以便灵活运用。

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

10

数据结构实验报告

2. 实验内容

2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。

3. 实验代码

2.1代码：

#include

#include

#include

#define NULL 0

typedef struct list

{

char str;

struct list *next;

}list;

11

数据结构实验报告

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;

}

12

数据结构实验报告

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=='{')

13

数据结构实验报告

push(*str,L);

else

if(*str==')'||*str==']'||*str=='}')

if(pop(*str,L))

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

puts(\"按回车键退出\");

getchar();exit(-2);

}

str++;

}

if(L->next)

{

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

14

数据结构实验报告

puts(\"按任意键退出\");

getchar();exit(-2);

}

}

void push(char c,list *L)

{

list *p;

p=(list *)malloc(sizeof(list));

if(!p)

{

printf(\"错误!\");

exit(-2);

}

15

数据结构实验报告

p->str=c;

p->next=L->next;

L->next=p;

}

#define

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;

16

check(s)

数据结构实验报告

case'}':check('{') break;

}

return 1;

4. 实验小结

栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。

实验三 树

1. 实验要求

1.1 掌握二叉树，二叉树排序数的概念和存储方法。

1.2 掌握二叉树的遍历算法。

1.3 熟练掌握编写实现树的各种运算的算法。

2. 实验内容

2.1 编写程序，求二叉树的结点数和叶子数。

2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。

17

数据结构实验报告

2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。

3. 实验代码

2.1代码：

#include

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

18

数据结构实验报告

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;

19

数据结构实验报告

void preorder(blink bt)

{

if (bt)

{

n++;

if(bt->lchild==NULL&&bt->rchild==NULL)

n1++;

preorder(bt->lchild);

preorder(bt->rchild);

}

}

void main()

{

20

数据结构实验报告

blink root;

root=creat();

preorder(root);

printf(\"此二叉数的接点数有:%d\\n\

printf(\"此二叉数的叶子数有:%d\\n\

2.2代码：

int get_deep(bitree T,int x)

{

if(T->data==x)

{

printf(\"%d\\n\

exit 1;

}

21

数据结构实验报告

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;

22

数据结构实验报告

}

}

2.3代码：

#include

#include

struct node{

char data;

struct node *lchild,*rchild;

}bnode;

typedef struct node *blink;

blink creat()

{

blink bt;

23

数据结构实验报告

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)

24

数据结构实验报告

{

if (bt)

{

printf(\"%c\

preorder(bt->lchild);

preorder(bt->rchild);

}

}

void inorder(blink bt)

{

if(bt)

{

inorder(bt->lchild);

25

数据结构实验报告

printf(\"%c\

inorder(bt->rchild);

}

}

void postorder(blink bt)

{

if(bt)

{

postorder(bt->lchild);

postorder(bt->rchild);

printf(\"%c\

}

}

26

数据结构实验报告

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;

27

数据结构实验报告

}

void main()

{

blink root;

root=creat();

printf(\"\\n\");

printf(\"按先序排列:\");

preorder(root);printf(\"\\n\");

printf(\"按中序排列:\");

inorder(root);printf(\"\\n\");

printf(\"按后序排列:\");

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

printf(\"此二叉数的深度是:\");

28

数据结构实验报告

printf(\"depth=%d\\n\

}

4. 实验小结

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

实验四 图

1. 实验要求

1.1 熟悉图的各种存储方法。

1.2 掌握遍历图的递归和非递归的算法。

1.3 理解图的有关算法。

2. 实验内容

2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。

2.2 以邻接表作存储结构，给出拓扑排序算法的实现。

29

数据结构实验报告

3. 实验代码

2.1代码：

void mattolist(int a[][],adjlist b[],int n) /*n为图的结点个数*/

{

for(i=0;ifor(i=0;ifor(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;

}

30

数据结构实验报告

}

2.2代码：

typedef struct vexnode

{

VertexType vertex;

int in;/*增加一个入度域*/

ArecNodeTp * fristarc;

}AdjList[vnum];

typedef struct graph

{

AdjList adjlist;

int vexnum,arcnum;

}GraphTp;

31

数据结构实验报告

Top_Sort(GraphTp g)

{

LstackTp *p;/*建立入度为0的顶点栈S*/

int m,i,v;

initStack(S);

for(i=0;iif(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*/

m++;

32

数据结构实验报告

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(melse return 1;

}

4. 实验小结

通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。

33

数据结构实验报告

实验五 查找

1. 实验要求

1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。

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

2. 实验内容

2.1 的有序性。

编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表

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

3. 实验代码

2.1代码：

#include

#include

#define MAXNUM 20

int input(int *);/*输入数据*/

34

数据结构实验报告

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\

insert=search(data,1,m);/*返回插入位置*/

plug(data,insert,m);

for(insert=1;insert<=m+1;insert++)/*显示数据*/

printf(\"%3d\

35

数据结构实验报告

getch();

}

int input(int *data)

{

int i,m;

printf(\"\\nInput the max num:\");

scanf(\"%d\

printf(\"input data\\n\");

for(i=1;i<=m;i++)

scanf(\"%d\

return m;

}

int search(int *data,int low,int high)/*递归查找插入位置*/

36

数据结构实验报告

{

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)

{

37

数据结构实验报告

int i;

for(i=m;i>insert;i--)

*(data+i+1)=*(data+i);

*(data+insert)=*data

}

2.2代码：

#include

#include

#include

#definr N 18 #definr Blocknum 3 typedef struct indexterm

{

/*元素个数*/

/*分块数*/

38

数据结构实验报告

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;j39

数据结构实验报告

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;

40

数据结构实验报告

else low=mid+1;

}

if(lowfor(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};

41

数据结构实验报告

int key;

index *list;

printf(\"please input key:\\n\");

scanf(\"%d\

list=CreateList(record,N);

printf(\"data postion id %d\\n\

}

4. 实验小结

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

42