实验报告 1
课程 数据结构 实验名称 顺序表基本操作
专业 计算机科学与技术 年 9 班级_ 月 8日 _ 学号_ _ 实验日期： 2010
第
姓名
页
评分
一、实验目的
1.学会定义线性表的顺序存储类型，实现 C 程序的基本结构，对线性表的一 些基本操作和具体的函数定义。 2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运 算。
二、实验要求
1．预习 C 语言中结构体的定义与基本操作方法。 2．对顺序表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。
三、实验内容
1．编写程序实现顺序表的下列基本操作： (1)初始化顺序表 La。 (2)将 La 置为空表。 (3)销毁 La。 (4)在 La 中插入一个新的元素。 (5)删除 La 中的某一元素。 (6)在 La 中查找某元素， 若找到， 则返回它在 La 中第一次出现的位置， 否则返回 0。 (7)打印输出 La 中的元素值。 2．编写程序完成下面的操作： (1)构造两个顺序线性表 La 和 Lb，其元素都按值非递减顺序排列。 (2)实现归并 La 和 Lb 得到新的顺序表 Lc， Lc 的元素也按值非递减顺 序排列。 (3)假设两个顺序线性表 La 和 Lb 分别表示两个集合 A 和 B，利用 union_Sq 操作实现 A=A∪ B。
-6-
-3-
while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; } void PrintList_Sq(SqList L) { int i; for(i=0;i<L.length;i++) printf("%d ",L.elem[i]); printf("\n"); } int main() { SqList La; int i,n,e; printf("请输入元素个数： \n"); scanf("%d",&n); if(InitList_Sq(La)) { for(i=1;i<=n;i++) { scanf("%d",&e); ListInsert_Sq(La,i,e); } printf("-------------------------------------\n 你输入的元素分别为：\n"); PrintList_Sq(La); printf("-------------------------------------\n"); } else { printf("初始化线性表出错！ \n"); printf("-------------------------------------\n"); } printf("请输入你要插入的元素及插入的位置：\n");//插入元素 scanf("%d%d",&e,&i); if(ListInsert_Sq(La,i,e)) { printf("插入元素后线性表为：\n"); PrintList_Sq(La); printf("-------------------------------------\n"); }
四、实验步骤
一 1. 编 写 头 文 件 。 定 义 数 据 类 型 。 分 别 写 各 个 函 数 如 ListInsern_Sq ， ListDelete_Sq，LocateElem 等函数。 2.编写主函数。 在主函数里构造空的线性表， 然后利用 ListInsert 函数使用户 初始化线性表。然后调用函数操作，操作结果用 PrintList_Sq 打印出线性表的内 容 3.运行程序，完整代码见下：
-2-
return OK; } Status ClearList_Sq(SqList &L) {//清空线性表 L.length=0;//memset(L,0,sizeof(L)); return OK; } Status ListInsert_Sq(SqList &L, int i, ElemType e) {// 在顺序线性表 L 的第 i 个元素之前插入新的元素 e ElemType *p; if (i < 1 || i > L.length+1) return ERROR; if (L.length >= L.listsize) { ElemType *newbase = *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return ERROR; L.elem = newbase; L.listsize += LISTINCREMENT; } ElemType *q = &(L.elem[i-1]); for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p; *q = e; ++L.length; return OK;
-5-
{ printf("线性表已撤销。 \n"); printf("--------------------------------------\n"); } else { printf("线性表清空出错。\n"); printf("--------------------------------------\n"); } return 0; } 二 1.编写头文件。定义数据类型。分别写需要用到的函数。在 Union_Sq 里需要 用的函数有 ListInsert_Sq 和 ListDelete_Sq 和 LocateElem_Sq 函数， 所以这三个函 数需要编写。同样设有 PrintList_Sq 函数来打印操作结果。 2.编写主函数分别使用户输入 La 与 Lb 的各个元素值，操作后用 PrintList_Sq 输出操作结果。 3.运行程序，完整代码见下。 //data struct 实验一 线性表基本操作 2 #include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define YES 1 #define NO 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType ; #define LIST_INIT_SIZE 100 #define LISTINCERMENT 10 typedef struct { ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList &L) {//构造空的顺序表 La L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(Ele mType)); if(!L.elem)exit(OVERFLOelete_Sq(SqList &L, int i, ElemType &e) { // 在顺序线性表 L 中删除第 i 个元素，并用 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; } // ListDelete_Sq Status LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType)) { // 在顺序线性表 L 中查找第 1 个值与 e 满足 compare()的元素的位序 int i; ElemType *p; i = 1; p = L.elem;
-4-
else { printf("输入位置有错！ \n"); printf("-------------------------------------\n"); }/**/ printf("请输入你要删除的元素的位置：\n");//删除元素 scanf("%d",&i); if(ListDelete_Sq(La,i,e)) { printf("你删除的元素为： %d,删除元素后线性表为：\n",e); PrintList_Sq(La); printf("-------------------------------------\n"); } else { printf("输入位置有错！ \n"); printf("-------------------------------------\n"); } printf("请输入你要查找的元素：\n");//查找元素 scanf("%d",&e); if(i=LocateElem_Sq(La,e,cmp)) { printf("你要查找的元素在第 %d 个位置。\n",i); printf("-------------------------------------\n"); } else { printf("找不到这个元素： \n"); printf("-------------------------------------\n"); } if(ClearList_Sq(La))//清空线性表 { printf("线性表已清空。 \n"); printf("--------------------------------------\n"); } else { printf("线性表清空出错。 \n"); printf("--------------------------------------\n"); } if(Destroy_Sq(La))//撤销线性表