数据结构实验课教案

数据结构,实验,老师,教案

数据结构教案

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

实验学时：2学时

一．实验目的：

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

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

二．实验内容：

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

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

三．实验重点：

顺序表的建立及操作。

四．实验要求：

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

2．要分别完成建立、插入、删除、查找、修改五种功能。

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

五． 实验器材：

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

六．实验步骤：

顺序表 ：

1．定义头文件和顺序表的存储结构类型等

#define ok 1

#define error 0

#define overflow 0

#define null 0

#include<stdio.h>

#include<stdlib.h>

#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(i<1||i>listlength(*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(i<1||i>l->length)

return error;

p=&(l->elem[i-1]);

*e=*p;

q=l->elem+l->length-1;

for(++p;p<=q;++p)

*(p-1)=*p;

--l->length;

数据结构,实验,老师,教案

return ok;

}

5．编写对顺序表进行查找操作的函数：

status getelem(sqlist l,int i,elemtype *e)

{

if(i<1||i>listlength(l))

return error;

*e=l.elem[i-1];

return ok;

}

6．编写对顺序表进行修改操作的函数：

status locateelem(sqlist l,elemtype e)

{

int i;

for(i=0;i<listlength(l);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<=la_len&&j<=lb_len)

{

getelem(la,i,&ai);

getelem(lb,j,&bj);

if(ai<=bj)

{

listinsert(lc,++k,ai);

++i;

}

else

{

listinsert(lc,++k,bj);

数据结构,实验,老师,教案

++j;

}

}

while(i<=la_len)

{

getelem(la,i++,&ai);

listinsert(lc,++k,ai);

}

while(j<=lb_len)

{

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<l.length;i++)

printf("%d ",l.elem[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<n;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<5;i++)

{

scanf("%d",&a);

listinsert(&la,i+1,a);

}

printf("\ninput list lb");

数据结构,实验,老师,教案

for(i=0;i<7;i++)

{

scanf("%d",&a);

listinsert(&lb,i+1,a);

}

mergelist(la,lb,&lc);

print(la);print(lb);print(lc);

}

数据结构,实验,老师,教案