实验指导书(赵).doc

实验一 线性表的基本操作及应用 一、实验目的 1．通过实际操作掌握定义线性表的顺序存储类型，熟悉线性表的基本操作的算法实现(具体的函数定义)，掌握单链表的结点类型的定义及单链表的基本操作算法实现(具体的函数定义)。 2．顺序存储和链式存储的应用。 二、实验要求 1．认真阅读和掌握所给的程序。 2．上机运行程序，并对程序进行分析。 3．完成自编程序，并上机调试运行。 三、实验内容 1．建立顺序表，及其基本操作（包括查找、插入、删除等），并且用数据进行测试。 （1）建立工程 启动Visual C++，选择“文件|新建”弹出如图1所示的对话框，选择Project选项卡中的Win32 Console Application选项，在Project name文本框中输入工程的名字“SeqList”，在Location中输入工程存放的路径，如“D:\数据结构实验\SeqList”。设置如图1所示。然后选择“OK按钮”，弹出如图2所示对话框，单击“Finish”按钮弹出如图3所示对话框，单击“OK”按钮，则创建工程成功，界面如图4所示。 图1 选择新建弹出的对话框 图2 图3 图4 （2）创建common.h头文件 选择“文件|新建”弹出如图5所示的对话框，选择“Files”选项卡中的“C/C++ Header File”，在“File”文本框中输入头文件的名字“common”，如图5所示。选择“OK”按钮。头文件中包含文件包含命令和宏定义，在“common.h”中输入如下内容： #include stdio.h #include stdlib.h #include malloc.h #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 图5 （3）创建“seqlist.h”头文件 “seqlist.h”头文件中主要包含了顺序表的定义以及基本操作。创建方法与创建“common.h”文件相同。“seqlist.h”文件内容如下： #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; int Locate(SeqList L, ElemType e) { int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i=L.last)(L.elem[i]!=e)) /*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/ i++; if (i=L.last) return(i+1); /*若找到值为e的元素，则返回其序号*/ else return(-1); /*若没找到，则返回空序号*/ } /*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L-last+1，i的合法取值范围是 1≤i≤L-last+2 */ int InsList(SeqList *L,int i,ElemType e) { int k; if((i1) || (iL-last+2)) /*首先判断插入位置是否合法*/ { printf(插入位置i值不合法); return(ERROR); } if(L-last= MAXSIZE-1) { printf(表已满无法插入); return(ERROR); } for(k=L-last;k=i-1;k--) /*为插入元素而移动位置*/ L-elem[k+1]=L-elem[k]; L-elem[i-1]=e; /*在C语言数组中，第i个元素的下标为i-1*/ L-last++; return(OK); } int DelList(SeqList *L,int i,ElemType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */ { int k; if((i1)||(iL-last+1)) { printf(删除位置不合法!); return(ERROR); } *e = L-elem[i-1]; /* 将删除的元素存放到e所指向的变量中*/ for(k=i; k=L-last; k++) L-e