数据结构实验教案

实验一 线性表的实验

一、实验目的及要求

1、掌握用Visual C++6.0调试顺序表的基本方法。

2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。

3、掌握用Visual C++6.0上机调试单链表的基本方法。

4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现。 5、进一步掌握循环单链表的插入、删除、查找算法的实现。 二、实验学时

4学时 三、实验任务

任务一：用顺序表实现通讯录管理

1、 构建通讯录的顺序表并输出检验。 2、 增加插入记录的功能并输出检验。 3、增加按学号查找的功能并运行验证。 4、增加删除记录的功能并运行验证。 任务二：用链表实现通讯录管理

1、构建通讯录的链表并输出检验 2、增加插入记录的功能并输出检验。 3、增加按学号查找的功能并运行验证。 4、增加删除记录的功能并运行验证。 四、实验重点、难点

1、 在顺序表中移动元素。

2、 在顺序表中找到正确的插入位置。

3、 在单链表中寻找到第i-1个结点并用指针p指示。 4、 比较两个单链表的节点数据大小。 五、操作内容与要求

任务一：用顺序表实现通讯录管理

1、构建如表1所示的顺序表并输出检验，实现表1。 2、增加插入记录的功能并输出检验，实现表2。 3、增加按学号查找的功能并运行验证。 4、增加删除记录的功能并运行验证。

表1 学号 姓名 性别 手机号码 QQ号 2013001 张珊 女 13800001919 34578 表2 2013002 李思 女 13910121978 8796532 2013003 陈琪 女 13789450012 3789123 2013004 王强 男 13634567856 6543783 2013005 赵括 男 13534408976 5679 2013006 刘刚 男 13386543211 98315 注意：用结构化程序设计的方法实现即（其中的）把单一功能设计成一个独立的函数。如构建顺序表设计成一个函数，同样插入、查找、删除、输出也设计成独立的函数。 任务二：用链表实现通讯录管理

1、构建通讯录的链表并输出检验，实现表1。 2、增加插入记录的功能并输出检验，实现表2。

3、增加按学号查找的功能并运行验证。 4、增加删除记录的功能并运行验证。

实验解答参考：

1、要完成此功能，先要考虑数据类型，再给出构建顺序表的函数及输出的函数，然后可以写出主函数了。

参考代码如下： #include #include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{

char xuehao[14];//学号 char name[20]; //姓名 int sex; //性别 char tel[14]; //联系电话 char qq[12]; //QQ号 }ElemType;

typedef struct{

ElemType *elem;//顺序表的存储空间基址，相当于一个一维的数组名 int length;//表的实际元素个数，即表的长度 int listsize;//最大可存储的元素个数，表的长度的上限 }SqList;

void InitSeqList(SqList &L) {

char flag; int i,n;

ElemType *p;

L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0;

L.listsize=LIST_INIT_SIZE;

printf(\是否输入初始数据？（Y/N）\ scanf(\

if(flag=='N'||flag=='n') return; printf(\请输入初始化数据的个数:\

- 1 -

scanf(\

if(n>L.listsize) {printf(\数据太多，不足以存储！\ p=L.elem; L.length=n;

for(i=0;i

printf(\请输入第%d个数据(学号 姓名 性别（0或1） 联系电话 QQ号)：\\n\

scanf(\ p++; }

return; }

void PrintSeqList(SqList &L) {

int i;

printf(\学号 姓名 性别 联系电话 QQ号\\n\ for(i=0;i

printf(\

if(L.elem[i].sex) printf(\男 \女 \ printf(\ } }

int main() {

SqList L; InitSeqList(L); PrintSeqList(L); return 0; }

2、增加下面的函数并适当调整main函数。

int InsertSeqList(SqList &L,int i,ElemType &e) {

int j;

ElemType *q,*p;

if(L.length+1>L.listsize ) {printf(\表满，失败！\ if(i<1||i>L.length+1) {printf(\插入位置错误，失败！\

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p) {

- 2 -

strcpy((p+1)->xuehao,p->xuehao); strcpy((p+1)->name ,p->name); (p+1)->sex=p->sex ;

strcpy((p+1)->tel,p->tel); strcpy((p+1)->qq,p->qq); }

strcpy(q->xuehao,e.xuehao); strcpy(q->name ,e.name); q->sex=e.sex ;

strcpy(q->tel,e.tel); strcpy(q->qq,e.qq);

L.length++;

return 1; }

主函数也要作修改如下： int main() {

int i;

ElemType e; SqList L;

InitSeqList(L); PrintSeqList(L); i=2;

printf(\请输入要插入的数据(学号 姓名 性别（0或1） 联系电话 QQ号)：\\n\

scanf(\ InsertSeqList(L,i,e); PrintSeqList(L); }

3、增加下面的函数并适当调整main函数。

int LocateList(SqList &L,char *x) {

int i=0;

while(i

if(i

printf(\学号 姓名 性别 联系电话 QQ号\\n\ printf(\

if(L.elem[i].sex) printf(\男 \女 \

- 3 -

printf(\ return i+1; }

return 0; }

4、增加下面的函数并适当调整main函数。 int DeleteList(SqList &L,int i) {

int j;

if(L.length ==0) {printf(\表空，删除失败！\\n\ if(i<1||i>L.length) {printf(\删除位置错，失败！\\n\ for(j=i;j<=L.length -1;j++) {

strcpy(L.elem[j-1].xuehao ,L.elem [j].xuehao ); strcpy(L.elem [j-1].name ,L.elem [j].name ); L.elem [j-1].sex =L.elem [j].sex ;

strcpy(L.elem [j-1].tel ,L.elem [j].tel ); strcpy(L.elem [j-1].qq ,L.elem [j].qq );

}

L.length --; return 1; }

任务二：

1、要完成此实验，要考虑4点：数据类型如何定义？链表结点的类型具体如何定义？如何建立链表？如何输出链表以便验证？ #include #include #include

typedef struct{

char xuehao[14];//学号 char name[20]; //姓名 int sex; //性别 char tel[14]; //联系电话 char qq[12]; //QQ号 }ElemType;

- 4 -

本文来源：https://www.bwwdw.com/article/cey5.html