数据结构实验课教案_数据结构实验顺序表

2020-02-27 教案模板下载本文

数据结构实验课教案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验顺序表”。

数据结构教案

实验一：线性表的顺序表示与实现

实验学时：2学时

一．实验目的：

1．掌握线性表的顺序存储结构；

2．掌握在顺序表上进行的插入、删除、查找、修改等操作。

二．实验内容：

1．分别建立顺序表，并输入初始数据；

2．对顺序表分别编写插入、删除、查找、修改等函数。

三．实验重点：

顺序表的建立及操作。

四．实验要求：

1．用C语言编写程序源代码；

2．要分别完成建立、插入、删除、查找、修改五种功能。3．源程序必须编译调试成功，独立完成。

五．实验器材：

一个装有C语言编译环境的计算机。

六．实验步骤：

顺序表：

1．定义头文件和顺序表的存储结构类型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include #include #define list_init_size 100 #define listincrement 10 typedef int elemtype;typedef int status;typedef struct{ elemtype *elem;int length;int listsize;}sqlist;2．编写构造空顺序表的函数 status listinit(sqlist *l){ l->elem=(elemtype *)malloc(list_init_size*sizeof(elemtype));if(!l->elem)

return overflow;l->length=0;l->listsize=list_init_size;return ok;}

3．编写对顺序表进行插入操作的函数： status listinsert(sqlist *l,int i,elemtype e){ elemtype *newbase,*q,*p;if(ilistlength(*l)+1)

return error;if(l->length==l->listsize)

{ newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype));

if(!newbase)

return overflow;

l->listsize+=listincrement;

} q=&(l->elem[i-1]);for(p=&(l->elem[l->length])-1;p>=q;--p)

*(p+1)=*p;*q=e;++l->length;return ok;}

4．编写对顺序表进行删除操作的函数：

status listdelete(sqlist *l,int i,elemtype *e){ elemtype *p,*q;if(il->length)

return error;p=&(l->elem[i-1]);*e=*p;q=l->elem+l->length-1;for(++p;p

*(p-1)=*p;--l->length;return ok;}

5．编写对顺序表进行查找操作的函数： status getelem(sqlist l,int i,elemtype *e){ if(ilistlength(l))return error;*e=l.elem[i-1];return ok;}

6．编写对顺序表进行修改操作的函数： status locateelem(sqlist l,elemtype e){ int i;for(i=0;i

if(l.elem[i]==e)

return i+1;return 0;} 7．编写实现两个线性表的归并操作的函数 void mergelist(sqlist la,sqlist lb,sqlist *lc){ int i,j,k;int la_len,lb_len;elemtype ai,bj;i=j=1;k=0;listinit(lc);la_len=listlength(la);lb_len=listlength(lb);while(i

{

listinsert(lc,++k,ai);

++i;

} else

{

listinsert(lc,++k,bj);

++j;

} } while(i

while(j

{ getelem(lb,j++,&bj);listinsert(lc,++k,bj);

} }

8．销毁线性表、清空线性表、判空、求表长等 status destroylist(sqlist *l){ if(l->elem)free(l->elem),l->elem=null;return ok;}

status clearlist(sqlist *l){ l->length=0;return ok;}

status listempty(sqlist l){ return(l.length==0);}

status listlength(sqlist l){ return l.length;}

9．打印线性表void print(sqlist l){ int i;printf(“nlist: ”);for(i=0;i

10．编写主函数 void main(){ int i;int n;elemtype a;sqlist l,la,lb,lc;clrscr();listinit(&l);listinit(&la);listinit(&lb);

printf(“please input list number”);scanf(“%d”,&n);printf(“n”);for(i=0;i

scanf(“%d”,&a);

listinsert(&l,i+1,a);} print(l);printf(“nlist length:%d”,listlength(l));

getelem(l,4,&a);printf(“ngetelem(l,4,&a),%d”,a);

listdelete(&l,3,&a);printf(“nlistdelete(&l,3,&a),%d”,a);print(l);

printf(“ninput list la”);

for(i=0;i

scanf(“%d”,&a);

listinsert(&la,i+1,a);} printf(“ninput list lb”);for(i=0;i

scanf(“%d”,&a);

listinsert(&lb,i+1,a);} mergelist(la,lb,&lc);print(la);print(lb);print(lc);}

实验二：链表

实验学时：2学时

一．实验目的：

11．掌握单、双向链表的存储结构；

12．掌握在单、双向链表上进行的插入、删除、查找、修改等操作。

二．实验内容：

4．分别建立单、双向链表，并输入初始数据；

5．对两种单、双向链表分别编写插入、删除、查找、修改等函数。

三．实验重点：

单向链表的建立及操作。

四．实验要求：

1．用C语言编写程序源代码；

2．要分别完成建立、插入、删除、查找、修改五种功能。6．源程序必须编译调试成功，独立完成。

五．实验器材：

一个装有C语言编译环境的计算机。

六．实验步骤：

单链表：

1．定义头文件和单链表的结构体类型 #include #include typedef struct LNode {

int data;

struct LNode *next;}LNode, *LinkList;

2．编写构造单链表的函数

void InitList_L(LinkList L){ LinkList p,q;int i,b,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);do { scanf(“%d”,&b);q=(LinkList)malloc(sizeof(LNode));q->data=b;p->next=q;p=p->next;j+=1;} while(b!=-1);p->next=NULL;p=L;for(i=1;inext;printf(“%dn”,p->data);} }

13．编写对单链表进行插入操作的函数： void ListInsert_L(LinkList L,int r,int e){ LinkList p,s;

int q=1,i,j=0;

p=L;

while(q>=1&&q

{

p=p->next;

++q;

} s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

p=L;while(p->next!=NULL)

{

p=p->next;

j+=1;

} p=L;

printf(“插入一个新结点后的链表为：n”);

for(i=1;i

{

p=p->next;

printf(“%dn”,p->data);

}

printf(“插入一个新结点后链表结点的个数为:%dn”,j-1);

printf(“***************************************n”);}

14．编写对单链表进行删除操作的函数： void ListDelete_L(LinkList L,int r){ LinkList p,s;int q=1,i,e;p=L;if(rk){ printf(“删除的位置不正确n”);printf(“***************************************n”);} else { while(q>=1&&qnext;++q;} s=p->next;p->next=s->next;e=s->data;k=k-1;printf(“删除的结点的值为：%dn”,e);printf(“删除一个结点后的链表为：n”);p=L;for(i=1;inext;printf(“%dn”,p->data);} printf(“删除一个结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} }

15．编写对单链表进行查找操作的函数： void GetElem_L(LinkList L,int r){ LinkList p;int q=1,e;p=L;if(rk){ printf(“第%d个元素不存在n”,r);printf(“***************************************n”);} else { while(q>=1&&qnext;q++;} e=p->data;printf(“第%d个元素的值为:n%dn”,r,e);printf(“***************************************n”);} }

16．编写对单链表进行修改操作的函数： void UpdateElem_L(LinkList L,int r){ LinkList p;int q=1,n,i;p=L;if(rk)

{

printf(“第%d个元素不存在n”,r);

printf(“***************************************n”);} else {

while(q>=1&&q

{

p=p->next;

q++;

}

printf(“请输入修改后该结点的值：n”);

scanf(“%d”,&n);

printf(“***************************************n”);

p->data=n;

printf(“修改第%d个元素的值后链表为：n”,r);

p=L;

for(i=1;i

{

p=p->next;

printf(“%dn”,p->data);

}

printf(“***************************************n”);} }

17．编写主函数 void main(){ int m,n=0;LinkList l;l=(LinkList)malloc(sizeof(LNode));InitList_L(l);while(n!=-1){ printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”);printf(“***************************************n”);scanf(“%d”,&n);printf(“***************************************n”);switch(n){ case 1: printf(“请输入在第几个结点之前插入新结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListInsert_L(l,m);break;case 2: printf(“请输入删除第几个结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListDelete_L(l,m);break;case 3: printf(“请输入查找第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);GetElem_L(l,m);break;case 4: printf(“请输入修改第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);UpdateElem_L(l,m);break;} } printf(“操作结束!n”);}

双向链表

1．定义头文件和双向链表的结构体类型 #include #include typedef struct DuLNode { int data;struct DuLNode *prior;struct DuLNode *next;}DuLNode, *DuLinkList;

2．编写构造双向链表的函数

void InitList_DuL(DuLinkList L){ DuLinkList p,q;int i,b=0,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);while(b!=-1){ scanf(“%d”,&b);q=(DuLinkList)malloc(sizeof(DuLNode));q->data=b;p->next=q;q->prior=p;p=p->next;j+=1;} k=j-1;p->next=NULL;p=L;printf(“***************************************n”);printf(“创建的双向链表为：n”);for(i=1;inext;printf(“%dn”,p->data);} printf(“该链表的结点个数为:%dn”,k);printf(“***************************************n”);}

3．对双向链表进行插入操作的函数

void ListInsert_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,n;p=L;if(rk){ printf(“插入的位置不正确!n”);printf(“***************************************n”);} else { while(q>=1&&qnext;q++;} s=(DuLinkList)malloc(sizeof(DuLNode));printf(“请输入插入的结点的值：n”);scanf(“%d”,&n);printf(“***************************************n”);s->data=n;s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;k=k+1;p=L;printf(“插入一个新结点后的链表为：n”);for(i=1;inext;printf(“%dn”,p->data);} printf(“插入一个新结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} }

7．写对双向链表进行删除操作的函数 void ListDelete_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,e;p=L;if(rk)

{

printf(“删除的位置不正确n”);

printf(“***************************************n”);} else {

while(q>=1&&q

{

p=p->next;

++q;

}

s=p->next;

p->next=s->next;

s->next->prior=p;

e=s->data;

k=k-1;

printf(“删除的结点的值为：%dn”,e);

printf(“删除一个结点后的链表为：n”);

p=L;

for(i=1;i

{

p=p->next;

printf(“%dn”,p->data);

}

printf(“删除一个结点后链表结点的个数为:%dn”,k);

printf(“***************************************n”);} }

8．编写对双向链表进行查找操作的函数void GetElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,e;p=L;if(rk)

{

printf(“第%d个元素不存在n”,r);

printf(“***************************************n”);} else {

while(q>=1&&q

{

p=p->next;

q++;

}

e=p->data;

printf(“第%d个元素的值为:n%dn”,r,e);

printf(“***************************************n”);} }

9．编写对双向链表进行修改操作的函数 void UpdateElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,n,i;p=L;if(rk)

{

printf(“第%d个元素不存在n”,r);

printf(“***************************************n”);} else {

while(q>=1&&q

{

p=p->next;

q++;

}

printf(“请输入修改后该结点的值：n”);

scanf(“%d”,&n);

printf(“***************************************n”);

p->data=n;

printf(“修改第%d个元素的值后链表为：n”,r);

p=L;

for(i=1;i

{

p=p->next;

printf(“%dn”,p->data);

}

printf(“***************************************n”);} }

10．编写主函数 void main(){ int m,n=0;DuLinkList l;l=(DuLinkList)malloc(sizeof(DuLNode));InitList_DuL(l);while(n!=-1){

printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”);

printf(“***************************************n”);

scanf(“%d”,&n);

printf(“***************************************n”);

switch(n)

{

case 1:

printf(“请输入在第几个结点之前插入新结点：n”);

scanf(“%d”,&m);

printf(“***************************************n”);

ListInsert_DuL(l,m);

break;

case 2:

printf(“请输入删除第几个结点：n”);

scanf(“%d”,&m);

printf(“***************************************n”);

ListDelete_DuL(l,m);

break;

case 3:

printf(“请输入查找第几个结点的值：n”);

scanf(“%d”,&m);

printf(“***************************************n”);

GetElem_DuL(l,m);

break;

case 4:

printf(“请输入修改第几个结点的值：n”);

scanf(“%d”,&m);

printf(“***************************************n”);

UpdateElem_DuL(l,m);

break;

} } printf(“操作结束!n”);}实验三：栈、队列

实验学时：2学时

一．实验目的：

1．掌握栈、队列的存储结构；

2．掌握在栈、队列上进行的各种操作。

二．实验内容：

1．编写模拟Hanoi塔函数计算的程序，掌握栈在递归中的作用； 2．编写循环队列的进队、出队、初始化等函数。（2选1）

三．实验重点：

对栈、队列的存储结构的理解。

四．实验难点：

循环队列操作函数的编写。

五．实验要求：

1．用C语言编写程序源代码；

2．源程序必须编译调试成功，独立完成。

六．实验器材：

一个装有C语言编译环境的计算机。

七．实验步骤：

Hanoi塔程序的编写 1．定义头文件： #include

2．编写move函数： void move(char x,char y){

printf(“%c-->%cn”,x,y);}

3．编写Hanoi塔函数：

void hanoi(int n,char a,char b,char c){

if(n==1)

move(a,c);

else

{

hanoi(n-1,a,c,b);

move(a,c);

hanoi(n-1,b,a,c);

} }

4．编写主函数： void main(){ int m;printf(“请输入需要移动的盘子数：n”);scanf(“%d”,&m);printf(“%d个盘子通过B从A移动到C的过程如下：n”,m);hanoi(m,'A','B','C');}

循环队列操作函数的编写

1．定义头文件和结构体类型等：

#include #include #define MAXQSIZE 10 typedef struct { int *base;//存储空间的起始地址，即数组的首地址，即数组名

int front;//顺序存储，即地址，所以用下标表示元素，front是第一个元

//的下标

int rear;//rear是最后一个元素的下标 }SqQueue;

2．编写初始化函数： int InitQueue(SqQueue &Q){

Q.base=(int*)malloc(MAXQSIZE*sizeof(int));if(!Q.base)

return 0;

else

{

Q.front=0;

Q.rear=0;

return 1;

} } 3．编写进队函数：

void EnQueue(SqQueue &Q,char e){

if((Q.rear+1)%MAXQSIZE==Q.front)

printf(“队列满”);else

{

Q.base[Q.rear]=e;//Q.base表示数组的地址也即数组名；Q.rear表示引用结//构体类型变量Q中的一个成员rear ,也即是数组中下标为rear的元素

Q.rear=(Q.rear+1)%MAXQSIZE;

} }

4．编写出队函数：

void DeQueue(SqQueue &Q){

char e;if(Q.front==Q.rear)

printf(“队列空n”);else {

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

} }

5．编写显示功能函数： void Display(SqQueue Q){ int i;

if(Q.front==Q.rear)

printf(“队列空n”);else

{

i=Q.front;

printf(“队列中的元素如下:”);

{

printf(“%c”,Q.base[i]);

i=(i+1)%MAXQSIZE;

}

while(i!=Q.rear);

} } 6．编写主函数： void main(){

SqQueue Q;

char r;

int i=0;

InitQueue(Q);

while(i!=-1)

{ printf(“请选择对队列进行何种操作:n 输入1表示进行入队操作n 输入2表示进行出队操作n 输入-1表示不进行任何操作n”);

printf(“********************************************n”);

scanf(“%d”,&i);

printf(“********************************************n”);

switch(i)

{

case 1:

printf(“请输入要入队的元素的值,输入#表示结束:n”);

printf(“****************************************n”);

scanf(“%c”,&r);

while(r!='#')

{

EnQueue(Q,r);

scanf(“%c”,&r);

}

printf(“****************************************n”);

Display(Q);

printf(“****************************************n”);

break;

case 2:

DeQueue(Q);

Display(Q);

break;

} } } 实验四：树

实验学时：2学时

一．实验目的：

1．掌握二叉树的存储结构；

2．掌握在二叉树上进行的各种操作。

二．实验内容与基本要求：

1．编写二叉树的各种操作函数，包括建立、初始化、添加、删除、查找等；

2．编写对二叉树进行三种遍历的函数；

3．编写8皇后的模拟计算程序。

(3选2)

三．实验重点：

二叉树的各种操作及遍历的函数。

四．实验难点：

二叉树的三种遍历函数的编写。

五．实验器材：

一个装有C语言编译环境的计算机。

六．实验步骤：

1．建立、初始化二叉树；

struct tree

//声明树的结构 {

struct tree *left;

int data;

struct tree *right;};typedef struct tree treenode;typedef treenode *b_tree;

//声明二叉树链表

//插入二叉树的节点

b_tree insert_node(b_tree root,int node){

b_tree newnode;

b_tree currentnode;

b_tree parentnode;

newnode=(b_tree)malloc(sizeof(treenode));

//建立新节点的内存空间

newnode->data=node;

newnode->right=NULL;

newnode->left=NULL;if(root=NULL)

return newnode;

else

{

currentnode=root;

while(currentnode!=NULL)

{

parentnode=currentnode;

if(currentnode->data>node)

currentnode=currentnode->left;

else

currentnode=currentnode->right;

}

if(parentnode->data>node)

parentnode->left=newnode;

else parentnode->right=newnode;

return root;} }

// 建立二叉树

b_tree create_btree(int *data,int len){

b_tree root=NULL;

int i;

for(i=0;i

root=insert_node(root,data[i]);//调用insert_node函数，参数为空指针

//root和数组中元素data[i]，//insert_node函数的返回值赋给

//create_btree函数中定义root，并作为 //create_btree函数的返回值返回

return root;//返回值为root }

2．编写对二叉树进行的各种操作的函数，包括、添加、删除、查找等；

3．编写对二叉树进行三种遍历的函数； //二叉树先序遍历

void preorder(b_tree point){

if(point!=NULL)

{

preorder(point->left);//递归

printf(“%d”,point->data);

preorder(point->right);//递归 } }

//二叉树中序遍历

void inorder(b_tree point){

if(point!=NULL)

{

inorder(point->left);//递归

printf(“%d”,point->data);

inorder(point->right);//递归

} }

//二叉树后序遍历

void postorder(b_tree point){

if(point!=NULL)

{

postorder(point->left);//递归

printf(“%d”,point->data);

postorder(point->right);//递归

} }

//主程序 void main(){

b_tree root=NULL;

int index;

int value;

int nodelist[20];

printf(“n please input the elements of binary tree(exit for 0):n”);

index=0;

//读取数值存到数组中

scanf(“%d”,&value);

while(value!=0)

{

nodelist[index]=value;

index=index+1;

scanf(“%d”,&value);

}

//建立二叉树

root=create_btree(nodelist,index);//主函数调用创建函数，参数为数组名和

//长度，创建函数的返回值(返回的本身

//是root)赋给主函数中定义root，并作//为参数传给inorder函数

//先序遍历二叉树

printf(“nThe preorder traversal result is :”);

preorder(root);//主函数调用inorder函数

printf(“n”);//中序遍历二叉树

printf(“nThe inorder traversal result is :”);

inorder(root);//主函数调用inorder函数

printf(“n”);//后序遍历二叉树

printf(“nThe postorder traversal result is :”);

postorder(root);//主函数调用inorder函数

printf(“n”);}

4．编写8皇后的模拟计算程序。实验五：图

实验学时：2学时

一．实验目的：

1．掌握图的存储结构；

2．掌握在图上进行的各种操作。

二．实验内容与基本要求：

1．编写图的各种操作函数，包括建立、初始化、添加、删除、查找等； 2．编写建立最小生成树的程序； 3．编写计算两点间最短路径的程序。（3选2）

三．实验重点：

掌握图的存储结构

四．实验难点：

编写计算两点间最短路径的程序

五．实验器材：

一个装有C语言编译环境的计算机。

六．实验步骤

计算两点间最短路径： 1．义头文件等 #include #define vex 3//定义结点的个数

#define max 10000//设定一个极大值

2．编写主函数 void main(){ int D[vex][vex][vex];//定义一个三维数组，用来一次一次的迭代，按

//FLOYD算法求出结点之间的最短路径

int arcs[vex][vex]={0,4,11,6,0,2,3,max,0};//邻接矩阵

int i,j,k;

for(i=0;i

//空间进行初始化

for(k=0;k

for(i=0;i

for(j=0;j

if(D[k-1][i][j]

D[k][i][j]=D[k-1][i][j];else

D[k][i][j]=D[k-1][i][k]+D[k-1][k][j];//求出每次迭代最小

//值，最后一次即为两个顶点之间的最短路径

printf(“图的邻接矩阵为:n”);for(i=0;i

for(j=0;j

{

printf(“%d

”,arcs[i][j]);

}

printf(“nn”);

}//打印邻接矩阵 printf(“n”);

printf(“表示各点间最短路径的矩阵为:n”);

for(i=0;i

{

for(j=0;j

{

printf(“%d

”,D[vex-1][i][j]);

}

printf(“nn”);

} }实验六：排序

实验学时：2学时

一．实验目的：

1．掌握二叉查找树的性质及其相关的应用；

2．掌握插入排序、快速排序、选择排序、归并排序、基数排序的算法实现。

二．实验内容与基本要求：

1．编写二叉查找树的生成及应用程序；

2．编写插入排序、快速排序、选择排序、归并排序、基数排序的程序。

三．实验重点：

掌握各种排序算法的思想

四．实验器材：

一个装有C语言编译环境的计算机。

五．实验步骤

插入排序：

#include #define N 10 void main(){ int i,j,k,t,a[N];

printf(“Please input %d numbers:n”,N);for(i=0;i

for(j=i-2;t

printf(“%d

”,a[i]);printf(“n”);}

快速排序：#include #define N 10 void quickSort(int a[10],int i, int j){ int A=a[0];while(i=A && i

while(a[i]0)

quickSort(a,0,i-1);if(i+1

quickSort(&a[i+1],i+1,9);}

void main(){

int i,j,a[N];

printf(“Please input %d numbers:n”,N);for(i=0;i

printf(“%d ”,a[i]);printf(“n”);}

冒泡排序：

#include void main(){

int a[10];int i,j,t;

printf(“input 10 numbers :n”);for(i=0;ia[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf(“the sorted numbers:n”);for(i=0;i

选择排序：

#include #define N 10 void main(){

int i,j,k,t,a[N];

printf(“Please input %d numbers:n”,N);

for(i=0;i

scanf(“%d”,&a[i]);

for(i=0;i

for(j=i;j

if(a[j]

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

k=a[i];

a[i]=a[j];

a[j]=k;}

printf(“the sorted numbers:n”);

for(i=0;i

printf(“%d ”,a[i]);

printf(“n”);} 30

相关专题数据结构实验顺序表数据结构课教案数据结构实验顺序表数据结构课教案

[教案模板]相关推荐

[教案模板]热门文章