《算法与数据结构》实验指导书量定义和常用系统函数原型声明的文件pubuse.h"代码复用，不需另行建立。2．建立一个单链表类型定义的头文件，如取名为：linklistDef.h，以后凡使用该文件定义的类型，就只需使用包含语句#include“linklistDef.h"即可。3.关于实验内容要完成的操作，一般都以独立的算法出现，建立一个单链表的基本算法文件，将各种不同算法组合在一个文件之中，存储为一个头文件如取名为：linklistAlgo.h，后凡涉及到要使用本文件中的单链表算法，一定要在你的文件的前面加上一条#include“linklistAlgo.h”即可，实现的算法函数，如Listlnit_Link、Listlnsert_Link、ListDelete_Link、ListTraverse_Link、PriorElem_Link、NextElem_LinkGetElem_Link，MergeList_Link等;4.还应包含一个main函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为linklistUse.cpp)。四、基本实验的参考程序（一）线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）(I)文件1：pubuse.h是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文件。#include<string.h>#include<ctype. h>#include<malloc. h>/*malloc(等*//*INT_MAX等*/#include<limits.h>/* EOF(=^Z或 F6),NULL */#include<stdio.h>* atoi */#include<stdlib.h>#include<io.h>/*eofO *//* floorO,ceilO,absO */#include<math.h>#include<process. h>/* exitO *//*函数结果状态代码*/#defineTRUE1#defineFALSEO#defineOK1#defineERRORO#define INFEASIBLE-1/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*11
《算法与数据结构》实验指导书 11 量定义和常用系统函数原型声明的文件“pubuse.h”代码复用，不需另行建立。 2．建立一个单链表类型定义的头文件，如取名为：linklistDef.h，以后凡使用该文件定义的类型，就 只需使用包含语句#include “linklistDef.h”即可。 3．关于实验内容要完成的操作，一般都以独立的算法出现，建立一个单链表的基本算法文件,将各种 不同算法组合在一个文件之中，存储为一个头文件如取名为：linklistAlgo.h，后凡涉及到要使用本文件中 的单链表算法，一定要在你的文件的前面加上一条#include “linklistAlgo.h” 即可，实现的算法函数，如 ListInit_Link、ListInsert_Link、ListDelete_Link、 ListTraverse_Link、PriorElem_Link、NextElem_Link、 GetElem_Link、MergeList_Link 等； 4．还应包含一个 main 函数，作为整个程序的执行入口处，定义测试的数据，完成各种算法的调用执 行，对算法的执行过程和结果进行判断和输出控制，存储为一个源文件（如取名为 linklistUse. cpp）。 四、基本实验的参考程序 四、基本实验的参考程序 四、基本实验的参考程序 四、基本实验的参考程序 （一）线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表） (1) 文件 1： pubuse. pubuse. pubuse. pubuse. h 是公共使用的常量定义和系统函数调用声明，以后每个实验中几乎都涉及到此文 件。 #include<string. h> #include<ctype. h> #include<malloc. h> /* malloc()等 */ #include<limits. h> /* INT_MAX 等 */ #include<stdio. h> /* EOF(=^Z 或 F6),NULL */ #include<stdlib. h> /* atoi() */ #include<io. h> /* eof() */ #include<math. h> /* floor(),ceil(),abs() */ #include<process. h> /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因为在 math. h 中已定义 OVERFLOW 的值为 3,故去掉此行 */
《算法与数据结构》实验指导书/*Status是函数的类型,其值是函数结果状态代码，如OK等*typedef int Status;/*Boolean是布尔类型,其值是TRUE或FALSE*typedef int Boolean;(2）文件2：seqlistDef.h进行线性表的动态分配顺序存储结构的表示#defineLISTINIT_SIZE1O/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedef struct1ElemType*elem；/*存储空间基址*/int length;/*当前长度*/int listsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*SqList;(3)文件3：seqlistAlgo.h进行线性表顺序存储结构的基本实验算法定义Status Listlnit Sq(SqList &L)/*算法2.3*/（/*操作结果：构造一个空的顺序线性表*L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(IL. elem)exit(OVERFLOW)：/*存储分配失败*/L.length=0；/*空表长度为0*/L.listsize=LISTINIT_SIZE；/*初始存储容量*returnOK;3Status Listlnsert_Sq(SqList &L,int i,ElemType e)/*算法2.4*/（/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1*//*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/ElemType *newbase,*q,*p;if(i<1i>L.length+1)/*i值不合法*/return ERROR:if(L.length>=L.listsize)/*当前存储空间已满，增加分配*/newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType);if(Inewbase)12
《算法与数据结构》实验指导书 12 typedef int Status； /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */ typedef int Boolean； /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */ (2) 文件 2：seqlistDef. seqlistDef. seqlistDef. seqlistDef. h 进行线性表的动态分配顺序存储结构的表示 #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct { ElemType *elem； /* 存储空间基址 */ int length； /* 当前长度 */ int listsize； /* 当前分配的存储容量(以 sizeof(ElemType)为单位) */ }SqList }SqList }SqList }SqList； (3)文件 3：seqlistAlgo. seqlistAlgo. seqlistAlgo. seqlistAlgo. h 进行线性表顺序存储结构的基本实验算法定义 Status ListInit_Sq(SqList &L) /* 算法 2. 3 */ { /* 操作结果：构造一个空的顺序线性表 */ L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))； if(!L. elem) exit(OVERFLOW)； /* 存储分配失败 */ L. length=0； /* 空表长度为 0 */ L. listsize=LIST_INIT_SIZE； /* 初始存储容量 */ return OK； } Status ListInsert_Sq(SqList &L,int i,ElemType e) /* 算法 2. 4 */ { /* 初始条件：顺序线性表 L 已存在，1≤i≤ListLength(L)+1 */ /* 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */ ElemType *newbase,*q,*p； if(i<1||i>L. length+1) /* i 值不合法 */ return ERROR； if(L. length>=L. listsize) /* 当前存储空间已满,增加分配 */ { newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType))； if(!newbase)
《算法与数据结构》实验指导书/*存储分配失败*/exit(OVERFLOW);/*新基址*/L.elem=newbase:L.listsize+=LISTINCREMENT：/*增加存储容量*//*q为插入位置*/q=L. elem+i-1;for(p=L.elem+L.length-1；p>=q；-p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=e;/*插入e*/++L. length;/*表长增1*/returnOK;3/*算法2.5*StatusListDelete_Sq(SqList&L,int i,ElemType*e)（/*初始条件：顺序线性表L已存在，1≤i≤ListLength(L）*/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/ElemType *p,*q:/*i值不合法*/if(i<1li>L. length)return ERROR;/*p为被删除元素的位置*/p=L. elem+i-l:*e=*p;/*被删除元素的值赋给e*//*表尾元素的位置*/q=L. elem+L. length-1;*被删除元素之后的元素左移*for(++p; p<=q; ++p)*(p-1)=*p;L. length--;/*表长减1*/return OK;3StatusListReverse_Sq(SqList&L)（/*初始条件：顺序线性表L已存在*//*操作结果：依次对L的数据元素成对交换*/ElemTypet;13
《算法与数据结构》实验指导书 13 exit(OVERFLOW)； /* 存储分配失败 */ L. elem=newbase； /* 新基址 */ L. listsize+=LISTINCREMENT； /* 增加存储容量 */ } q=L. elem+i-1； /* q 为插入位置 */ for(p=L. elem+L. length-1；p>=q；-p) /* 插入位置及之后的元素右移 */ *(p+1)=*p； *q=e； /* 插入 e */ ++L. length； /* 表长增 1 */ return OK； } Status ListDelete_Sq(SqList &L,int i,ElemType *e) /* 算法 2. 5 */ { /* 初始条件：顺序线性表 L 已存在，1≤i≤ListLength(L) */ /* 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 */ ElemType *p,*q； if(i<1||i>L. length) /* i 值不合法 */ return ERROR； p=L. elem+i-1； /* p 为被删除元素的位置 */ *e=*p； /* 被删除元素的值赋给 e */ q=L. elem+L. length-1； /* 表尾元素的位置 */ for(++p；p<=q；++p) /* 被删除元素之后的元素左移 */ *(p-1)=*p； L. length-； /* 表长减 1 */ return OK； } Status ListReverse_Sq(SqList &L) { /* 初始条件：顺序线性表 L 已存在 */ /* 操作结果：依次对 L 的数据元素成对交换*/ ElemType t；
《算法与数据结构》实验指导书inti;for(i=0; <L. length/2; i++)(t-L.elem[i];L.elem[i]-L. elem[L. length-i-]];L.elem[L, length-i-1]]-t;printf("\n");returnOK;3Status ListPrint Sq(SqList L)（/*初始条件：顺序线性表L已存在*//*操作结果：依次对L的数据元素输出*/int i;printf("\n");for(i=0; i<L. length; i++)printf("%d", L,elem[];return OK;3/*还有一些算法，同学们自己补充完整*(4)文件4:seqlistUse.cpp进行线性表顺序存储结构的基本算法验证/*实现通用常量的定义，常用系统函数的声明*/#include"pubuse.h"/*实现一组整数的操作,将int型特定义为通用的ElemType类型名*/typedef int ElemType;#include"seqlistDef. h"/*采用线性表的动态分配顺序存储结构定义*/#include"seqlistAlgo.h"/*采用顺序表的基本算法定义*/void mainOSqList L;Status i;intj;ElemTypet;/*首先一定要初始化顺序表*/i=Listlnit_ Sq(L):14
《算法与数据结构》实验指导书 14 int i； for(i=0；i<L. length/2；i++) {t=L. elem[i]； L. elem[i]= L. elem[L. length-i-1]； L. elem[L. length-i-1]=t； } printf("\n")； return OK； } Status ListPrint_Sq(SqList L) { /* 初始条件：顺序线性表 L 已存在 */ /* 操作结果：依次对 L 的数据元素输出*/ int i； printf("\n")； for(i=0；i<L. length；i++) printf("%d ", L. elem[i])； return OK； } /* 还有一些算法，同学们自己补充完整 */ (4)文件 4：seqlistUse. seqlistUse. seqlistUse. seqlistUse. cpp 进行线性表顺序存储结构的基本算法验证 #include"pubuse. h" /* 实现通用常量的定义，常用系统函数的声明 */ typedef int ElemType； /*实现一组整数的操作,将 int 型特定义为通用的 ElemType 类型名*/ #include"seqlistDef. h" /* 采用线性表的动态分配顺序存储结构定义 */ #include"seqlistAlgo. h" /* 采用顺序表的基本算法定义 */ void main() { SqList L； Status i； int j； ElemType t； /* 首先一定要初始化顺序表 */ i=ListInit_Sq(L)；
《算法与数据结构》实验指导书if(i-=1)/*创建空表L成功*/for(j=1；j<=5；j++)/*在表L中插入5个元素，每个元素的值分别为2，4，6，8，10*/i=Listlnsert_Sq(Lj,2*j);ListPrint_Sq(L)；/*检验一下插入的结果，输出表L的内容*/Listlnsert_Sq(L,2,20)；/*随机指定插入点位置，假设在第二个元素前插入新的元素，其值为20*ListDelete_Sq(L,4,&t)：/*随机指定删除点位置，假设对第四个元素进行删除*printf("nTheDeletedvalueis%d",t)：/*检验一下删除点元素的值*ListPrint_Sq(L)；/*检验一下插入和删除后的结果，输出表La的内容*/ListReverse_Sq(L)；/*将顺序表La的所有元素进行逆序*/ListPrint_Sq(L)：/*检验一下逆序的结果，输出表L的内容*/3（二）线性表的链式存储结构的定义及其基本操作的参考程序（链表）1．文件linklistDef.h是线性表的单链表存储结构的定义struct LNodetElemType data;struct LNode *next;1;typedefstructLNode*LinkList；/*另一种定义LinkList的方法*/2.文件linklistAlgo.h是单链表的基本算法描述/*以下的算法均是针对带表头结点的单链表*/Status Listlnit_Link(LinkList &L)（/*操作结果：构造一个空的线性表L*/L=(LinkList)malloc(sizeof(structLNode)；/*产生头结点,并使L指向此头结点*/if(!L)/*存储分配失败*/exit(OVERFLOW):L->next-NULL；/*指针域为空*/returnOK;315
《算法与数据结构》实验指导书 15 if(i==1) /* 创建空表 L 成功 */ for(j=1；j<=5；j++) /* 在表 L 中插入 5 个元素，每个元素的值分别为 2，4，6，8，10 */ i=ListInsert_Sq(L,j,2*j)； ListPrint_Sq(L)； /*检验一下插入的结果，输出表 L 的内容 */ ListInsert_Sq(L,2,20)；/* 随机指定插入点位置，假设在第二个元素前插入新的元素，其值为 20 */ ListDelete_Sq(L,4,&t)；/* 随机指定删除点位置，假设对第四个元素进行删除 */ printf("\n The Deleted value is %d",t)；/* 检验一下删除点元素的值 */ ListPrint_Sq(L)；/* 检验一下插入和删除后的结果，输出表 La 的内容 */ ListReverse_Sq(L)；/* 将顺序表 La 的所有元素进行逆序 */ ListPrint_Sq(L)；/* 检验一下逆序的结果，输出表 L 的内容 */ } （二）线性表的链式存储结构的定义及其基本操作的参考程序（链表） （二）线性表的链式存储结构的定义及其基本操作的参考程序（链表） （二）线性表的链式存储结构的定义及其基本操作的参考程序（链表） （二）线性表的链式存储结构的定义及其基本操作的参考程序（链表） 1． 文件 linklistDef.h 是线性表的单链表存储结构的定义 struct LNode { ElemType data； struct LNode *next； }； typedef struct LNode *LinkList； /* 另一种定义 LinkList 的方法 */ 2． 文件 linklistAlgo.h 是单链表的基本算法描述 /* 以下的算法均是针对带表头结点的单链表 */ Status ListInit_Link(LinkList &L) { /* 操作结果：构造一个空的线性表 L */ L=(LinkList)malloc(sizeof(struct LNode))； /* 产生头结点,并使 L 指向此头结点 */ if(!L) /* 存储分配失败 */ exit(OVERFLOW)； L->next=NULL； /* 指针域为空 */ return OK； }