数据结构C语言版线性表的单链表存储结构表示和实现.doc

. . . . #include stdio.h #include malloc.h #include stdlib.h /* 数据结构C语言版 线性表的单链表存储结构表示和实现 P28-31 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */ typedef int ElemType; // 线性表的单链表存储结构 typedef struct LNode { ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList; // typedef struct LNode *LinkList; // 另一种定义LinkList的方法 // 构造一个空的线性表L int InitList(LinkList *L) { /* 产生头结点L,并使L指向此头结点，头节点的数据域为空，不放数据的。 void * malloc(size_t) 这里对返回值进行强制类型转换了，返回值是指向空类型的指针类型。 */ (*L) = (LinkList)malloc( sizeof(struct LNode) ); if( !(*L) ) exit(0); // 存储分配失败 (*L)-next = NULL; // 指针域为空 return 1; } // 销毁线性表L，将包括头结点在内的所有元素释放其存储空间。 int DestroyList(LinkList *L) { LinkList q; // 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放 while( *L ) { q = (*L)-next; free( *L ); //释放 *L = q; } return 1; } /* 将L重置为空表，即将链表中除头结点外的所有元素释放其存 储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变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 1; } // 若L为空表（根据头结点L-next来判断，为空则是空表），则返回1， // 否则返回0。 int ListEmpty(LinkList L) { if( L-next ) // 非空 return 0; else return 1; } // 返回L中数据元素个数。 int ListLength(LinkList L) { int i = 0; LinkList p = L-next; // p指向第一个结点 while(p) // 没到表尾，则继续循环 { i++; p=p-next; } return i; } // 算法2.8 P29 // L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并 // 返回1,否则返回0。 int GetElem(LinkList L,int i,ElemType *e) { int j = 1; // j为计数器 LinkList p=L-next; // p指向第一个结点 while(pji) // 顺指针向后查找,直到p指向第i个元素或p为空 { p=p-next; j++; } if(!p||ji) // 第i个元素不存在 return 0; *e = p-data; // 取第i个元素 return 1; } // 返回L中第1个与e满足关系compare()的数据元素的位序。 // 若这样的数据元素不存在,则返回值为0 int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType)) { int i=0; LinkList p=L-next; while(p) //将链表的每一个元素进行对比 { i++; if(compare(p-data,e)) // 找到这样的数据元素 return i; p=p-next; } return 0; } // 若cur_e是L的