《数据结构C语言版 线性表的单链表存储结构表示和实现》由会员分享，可在线阅读，更多相关《数据结构C语言版 线性表的单链表存储结构表示和实现（20页珍藏版）》请在金锄头文库上搜索。
1、 .#include #include #include /*数据结构C语言版 线性表的单链表存储结构表示和实现P28-31 编译环境：Dev-C+ 4.9.9.2日期：2011年2月10日 */typedef int ElemType;/ 线性表的单链表存储结构 typedef struct LNodeElemType data;/数据域struct LNode *next;/指针域LNode, *LinkList;/ typedef struct LNode *LinkList; / 另一种定义LinkList的方法 / 构造一个空的线性表L int InitList(LinkList *
2、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;/ 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释
3、放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为空表（根据头结
4、点L-next来判断，为空则是空表），则返回1，/ 否则返回0。int ListEmpty(LinkList L) if( L-next )/ 非空 return 0;elsereturn 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
5、,int i,ElemType *e)int j = 1;/ j为计数器 LinkList p=L-next;/ p指向第一个结点 while(p&jnext;j+; if(!p|ji) / 第i个元素不存在 return 0;*e = p-data; / 取第i个元素 return 1;/ 返回L中第1个与e满足关系compare()的数据元素的位序。/ 若这样的数据元素不存在,则返回值为0int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0;LinkList p=L-next;while(
6、p)/将链表的每一个元素进行对比i+;if(compare(p-data,e) / 找到这样的数据元素 return i;p=p-next;return 0;/ 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,/ 返回1;否则操作失败,pre_e无定义,返回-1int PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) LinkList q, p=L-next;/ p指向第一个结点 while(p-next)/ p所指结点有后继 q=p-next; / q为p的后继 if(q-data=cur_e)*pre_e=p-d
7、ata;return 1;p=q; / p向后移 return -1;/ 若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， / 返回1;否则操作失败，next_e无定义，返回-1 int NextElem(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L-next; / p指向第一个结点 while(p-next) / p所指结点有后继 if(p-data=cur_e)*next_e=p-next-data;return 1;p=p-next;return -1;/算法2.9 P30/在带头结点的单链线性表
8、L中第i个位置之前插入元素eint ListInsert(LinkList *L,int i,ElemType e) int j=0;LinkList p=*L,s;while(p & jnext;j+;if(!p | ji-1) / i小于1或者大于表长 return 0;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点 s-data=e; / 插入L中 s-next=p-next;p-next=s;return 1;/ 算法2.10 P30/ 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值int ListDelete(LinkLi
9、st *L, int i,ElemType *e)int j = 0;LinkList p=*L,q;while(p-next&jnext;j+;if(!p-next|ji-1) / 删除位置不合理 return 0;q=p-next; / 删除并释放结点 p-next=q-next;*e=q-data;free(q);return 1;/ 依次对L的每个数据元素调用函数vi()int ListTraverse(LinkList L,void(*vi)(ElemType)LinkList p=L-next;/对所有元素调用函数viwhile(p)vi(p-data);p=p-next;prin
10、tf(n);return 1;/ 在按非降序排列的线性表L中按非降序插入新的数据元素e void InsertAscend(LinkList L,ElemType e) LinkList q=L, p=L-next;while(p&ep-data)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ 按非升序排列的线性表L中按非升序插入新的数据元素e void InsertDescend(LinkList L,ElemType e) LinkList q=
11、L,p=L-next;while(p&edata)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ L的头部插入新的数据元素e,作为链表的第一个元素 int HeadInsert(LinkList L,ElemType e)LinkList s;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点 s-data=e; / 给结点赋值 s-next=L-next; / 插在表头 L-next=s;return
12、1;/ 在L的尾部插入新的数据元素e,作为链表的最后一个元素 int EndInsert(LinkList L,ElemType e) LinkList p=L;while(p-next) / 使p指向表尾元素 p=p-next;p-next=(LinkList)malloc(sizeof(struct LNode); / 在表尾生成新结点 p-next-data=e; / 给新结点赋值 p-next-next=NULL; / 表尾 return 1;/ 删除L的第一个数据元素，并由e返回其值 int DeleteFirst(LinkList L,ElemType *e)LinkList p=L-next;if(p)*e=p-data;L-next=p-next;free(p);return 1;elsereturn 0;/ 删除L的最后一个数据元素，并用e返回其值int DeleteTail(LinkList L,ElemType *e)LinkList p=L,q;if(!p-next
