/----------线性表的单链表基本操作的算法实现------------
//我给链表设置了一个头结点,虽然它的数据域毫无意义,但它作为一个指针却意义非凡! //它的作用我们在下面的例程中可以领教 LinkList InitList(void) //构造一个空的线性表 { LNode Head; Head = (LNode)malloc(sizeof(struct Node)); //为链表的头结点分配空间 if(!Head) { printf("Out of space!"); return NULL; } Head->next = NULL; return Head;//返回头结点 } void DestroyList(LinkList *L)//初始条件：线性表L已存在。 操作结果：销毁线性表L。 { LNode Head, P; if(*L)//若线性表L已存在 { Head = *L; P = Head->next; while(!P) //把链表中除头结点外的所有结点释放 { free(Head); Head = P; P = Head->next; } free(Head); //释放头结点 } } LinkList MakeEmpty(LinkList L)//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 { LNode Head, P; Head = *L; P = Head->next; while(!P)//把链表中除头结点外的所有结点释放 { free(Head); Head = P; P = Head->next; } return (Head); //返回头结点 } int IsEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 { return L->next == NULL; } int ListLength(LinkList L)//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 { LNode P = L->next; int num = 0; while(P) //累积线性表L结点的个数 { num++; P = P->next; } return num; //返回线性表L结点的个数 } //初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。 LNode IsLast(LinkList L) { LNode P = L->next; if(P) { while(P->next) //遍历线性表L P = P->next; } return P; //返回线性表L的最后一个结点，若为空表则返回NULL } LNode NewLNode(ElemType X)//构造一个数据域为X的新结点 { LNode S; S = (LNode)malloc(sizeof(struct Node))//为新结点分配空间 if(!S) { printf("Out of space!"); return NULL; } S->data = X; S->next = NULL; return S;//返回新结点 } //线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 LNode FindPrefious(ElemType X, LinkList L) { LNode P = L; while(P->next && P->next->data != X)//遍历链表寻找值为X的结点 P = P->next; if(!P->next) //如果找不到值为X的结点,返回NULL return NULL; else //若找到则返回该结点的前驱P return P; } void ListDelete(LNode Pre)//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 { LNode P = Pre->next; Pre->next = P->next; free(P); } //初始条件：线性表L中结点P已找到，新结点S已构造。。操作结果：在该结点之前插入新结点X。 void ListInsert(LNode Pre, LNode S) { S->next = Pre->next; Pre->next = S; }
评论