第2次实验_单链表的定义及基本操作.doc

附件2： 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级：软件二班 学号：090202021008 姓名：陈英有 指导教师 钱锋 成绩 实验题目 单链表的定义及基本操作 实验时间 一、实验目的、意义 （1）理解线性表中带头结点单链表的定义和逻辑图表示方法。 （2）熟练掌握单链表的插入，删除和查询算法的设计与实现。 （3）理解循环链表和双链表的特点和基本运算。 （4）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 二、实验内容及要求 说明1：本次实验中的链表结构均为带头结点的单链表。 说明2: 学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： 建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。（参见教材19页） 三、实验所涉及的知识点 结构体定义，typedef，指针使用的部分知识。引用机制，实参与形参，C语言中地址与指针，指针的传递动态分配内存，define，强制类型转换，表存储结构及其首址，指针。 在创建单链表时，总寻找到返回表的方法，所以在算法ListInser（）；中加入返回值，用FOR语句来输出表。 五、实验结果及分析 六、总结与体会 （调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。） 七、程序清单(包含注释) #include stdio.h #include malloc.h #include stdlib.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; int InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(struct LNode)); if(!(*L)) exit(OVERFLOW); (*L)-next = NULL; return TRUE; } int DestroyList(LinkList *L) { LinkList q; // 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放 while( *L ) { q = (*L)-next; free( *L ); //释放 *L = q; } return TRUE; } //将L重置为空表 int ClearList( LinkList L ) { LinkList p, q; p = L-next; // p指向第一个结点 while( p ) // 没到表尾则继续循环 { q = p-next; free( p ); //释放空间 p = q; } L-next = NULL; // 头结点指针域为空，链表成了一个空表 return TRUE; } // 若L为空表则返回1， // 否则返回0。 int ListEmpty(LinkList L) { if( L-next ) // 非空 return ERROR; else return TRUE; } // 返回L中数据元素个数。 int ListLength(LinkList L) { int i = 0; LinkList p = L-next; // p指向第一个结点 while(p) // 没到表尾，则继续循环 { i++; p=p-next; } return i; } // L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并 // 返回1,否则返回0。 int GetElem(LinkList L,int i,ElemType *e) {