算法与数据结构实验指导书1.doc

数理学院实验指导书实验一 单链表及其应用【实验目的】1. 学会定义线性表的链式存储类型，C程序的基本结构、单链表类型和线性表相关运算的函数定义.2. 掌握单链表的基本运算的实现方法；3. 体会C语言实现数据结构的方法和过程，掌握C程序的编辑，调试和运行过程.【实验内容】1. 用C程序实现单链表类型，包括定义和各种基本运算的实现，并在此基础上设计一个主程序（测试程序），完成线性表的一些基本运算。请根据下面给出的程序，完成这次实验：其中CreateLinkListFromArray和InsertLinkList两个函数的实现代码没有给出，请同学们在理解代码的前提下独立设计并实现。/*Common.h*/#define OK 1 /状态，成功#define FAILURE 0 /状态，未成功#define ERROR -1 /状态，失败#define OVERFLOW 1 /溢出typedef int Status;/*LinkList.h*/#include #include #include common.htypedef int ElemType;/结点struct Node ElemType data; struct Node *next; ; /单链表typedef struct Node *LinkListPtr,LinkList;/*构造一个空的线性表*/LinkList *CreateLinkList();/*从数组构造一个单链表*/LinkList *CreateLinkListFromArray(ElemType e, int n);/*销毁线性表*/void DestroyLinkList(LinkList *L);/*求表长*/int LengthLinkList(LinkList *L);/*在链表中查询第一个满足判定条件的数据 元素，若存在，返回它的位序，否则返回 0*/LinkList *LocateLinkList(LinkList *L, ElemType x, Status (*compare)(ElemType, ElemType);/*取第i个数据元素*/LinkList *LGetLinkList(LinkList *L, int i);/*在链表L的第 i 个元素之前插入新的元素e,i 的合法范围为 1iL.length+1*/Status InsertLinkList(LinkList *L, ElemType x, int i);/*删除链表L的第 i 个元素，返回第i 个元素e,i 的合法范围为 1iL.length+1*/Status DeleteLinkList(LinkList *L, int i, ElemType *e) ;/*重置线性表为空*/void ClearLinkList(LinkList *L); /*遍历*/void TraverseLinkList(LinkList *L, void (*visit)(ElemType);/*LinkList.c*/#include #include #include common.h#include LinkList.h/*构造一个空的线性表*/LinkList *CreateLinkList()LinkList *head;/*head为头结点指针*/head=(LinkList *)malloc(sizeof(LinkList);if(head=NULL)exit(OVERFLOW);head-next=NULL; return head;/*从数组构造一个单链表*/LinkList *CreateLinkList(ElemType e, int n)/*销毁线性表*/void DestroyLinkList(LinkList *L)LinkList* p;LinkList* l;p=L;while(p!=NULL)l=p-next;free(p);p=l; /*求表长*/int LengthLinkList(LinkList *L)LinkList *P=L-next; int j=0;while(P!=NULL)j+;P=P-next; return j; /*返回表长*/*在链表中查询第一个满足判定条件的数据 元素，若存在，返回它的位序，否则返回 0*/LinkList *LocateLinkList(LinkList *L, ElemType x, Status (*compare)(ElemType, ElemType)LinkList *P; P=L-next; while(P!=NULL)&(*compare)(P-data,x)!=OK) P=P-next;return P; /*返回找到的结点位置或NULL*/*取第i个数据元素*/LinkList *GetLinkList(LinkList *L, int i)LinkList *P; int j=0;P=L; while(jnext!=NULL) P=P-next; j+;if(j=i)return P; elsereturn NULL;/*在链表L的第 i 个元素之前插入新的元素e,i 的合法范围为 1iL.length+1*/Status InsertLinkList(LinkList *L, ElemType x, int i)/*删除链表L的第 i 个元素，返回第i 个元素e,i 的合法范围为 1iL.length+1*/Status DeleteLinkList(LinkList *L, int i, ElemType *e) LinkList *P;LinkList *S;P=GetLinkList(L,i-1);/*查找第i-1个结点*/if(P=NULL|P-next=NULL)printf(第i-1个元素不存在，参数i 有错n);return ERROR;S=P-next;P-next=S-next;(*e) = S-data;free (S);S=NULL;return OK; /*重置线性表为空*/void ClearLinkList(LinkList *L)LinkList* p;LinkList* l;p=L-next;while(p!=NULL)l=L-next;free(p);p=l;L-next=NULL;/*遍历*/void TraverseLinkList(LinkList *L, void (*visit)(ElemType)LinkList* p;p=L-next;while(p!=NULL)(*visit)(p-data);p=p-next;2. 利用你设计的单链表完成教材P71的上机练习2的第3题【实验安排】课时安排：2学时【实验提示】1. 实验流程根据单链表的C语言实现范例编辑源程序，注意编写的规范和体会实现的方法；设计一个主程序实现单链表类型的测试（包括测试用例的选择）。测试用