//=============================================================
//链表具体函数实现部分
//=============================================================
#include "LinkList.h"
#include <malloc.h>
#include "stdafx.h"
void main()
{
//TODO:Just a main to avoid the error
}
//分配一个p指向的值为e的节点，并返回OK；如果分配失败，则error
Status MakeNode( Link &p, ElemType e){
p = ( Link)malloc(sizeof(LNode));
if( !p) return ERROR;
p->data = e;
p->next = NULL;
return OK;
}//The end of MakeNode
//释放p指向的节点
Status FreeLNode( Link &p){
if( !p) return ERROR;//Space does not exist
free( &p);
return OK;
}//end of FreeLNode
//初始化一个已经声明链表L
Status InitList( LinkList &L){
L.head = L.tail = NULL;
L.len = 0;
return OK;
}
//销毁一个链表L
Status DestroyList( LinkList &L){
if( L.len != 0){//if the link list is not empty
Link p = L.head, q = NULL;
for( ; L.len >=0 && p->next != NULL; --L.len){
q = p->next;
L.head = q;
free( &p);
p = q;
}
L.head = L.tail = NULL;
L.len = 0;
free( &p);
free( p);
free( q);
free( &L);
}//end of if
else{//if the link list is empty
L.head = L.tail = NULL;
L.len = 0;
free( &L);
}
return OK;
}//end of DestroyList
//将当前链表L清空，变成一个初始状态的链表
Status ClearList( LinkList &L){
if( L.len != 0){//if the link list is not empty
Link p = L.head, q = NULL;
for( ; L.len >=0 && p->next != NULL; --L.len){
q = p->next;
L.head = q;
free( &p);
p = q;
}
L.head = L.tail = NULL;
L.len = 0;
free( &p);
free( p);
free( q);
}//end of if
else{//if the link list is empty
L.head = L.tail = NULL;
L.len = 0;
}//end of else
return OK;
}
//在头节点位置插入一个新的节点,h指向头，s指向新的节点
Status InsFirst( LinkList &L, Link s){
if( !s) return ERROR;
s->next = L.head;
L.head = s;
return OK;
}
//将头节点删除
Status DelFirst( LinkList &L, Link &q){
if( !L.head) return ERROR;
q = L.head;
L.head = q->next;
return OK;
}
//向链表内插入数据，s以后的一个或若干个节点插入链表的尾部
//并修改链表的tail指针
Status Append( LinkList &L, Link s){
if( !s) return ERROR;//no node at s
L.tail->next = s;
while( s->next){//find the new end at the end of list pointed by s
s = s->next;
}
L.tail = s;
return OK;
}
//删除链表尾节点元素，由q返回
Status Remove( LinkList &L, Link &q){
if( L.len == 0) return ERROR;//the list is empty
Link p = L.head;//a temp pointer used to find the
//node before the tail
while( p->next != L.tail)
p = p->next;//till find the node before the tail
q = p->next;
L.tail = p;
return OK;
}//end of Remove
//将元素插入由p指定的位置的前一个位置,并修改p指向新的节点
Status InsBefore( LinkList &L, Link &p, Link s){
Link q = L.head;//临时指针游标，辅助搜寻指向p的前一个节点
while( q->next != p)
q = q->next;
//一下三步将s的node插入p的前一个位置，即q的位置
s->next = p;
q->next = s;
p = s;
return OK;
}//end of InsBefore
//将元素插入由p指定位置的下一个位置，并修改p指向新节点
Status InsAfter( LinkList &L, Link &p, Link s){
if( !s) return ERROR;//节点指针s无效
//插入节点s
s->next = p->next;
p->next = s;
p = s;
return OK;
}//end of InsAfter
//修改当前指针p指向的元素的数据域的值为e
Status SetCurElm( Link &p, ElemType e){
if( !p) return ERROR;//当前p指针无效
p->data = e;
return OK;
}//end of SetCurElm
//获取当前指针p指向的元素的数据域的值，以e返回
Status GetCurElm( Link &p, ElemType &e){
if( !p) return ERROR;//当前指针p无效
e = p->data;
return OK;
}//end of GetCurElm
//判断当前链表是否空表，以true和false返回结果
Status IsEmpty( LinkList L){
if( L.len == 0) return TRUE;//如果空，则链表长度为0
else return FALSE;
}//end of IsEmpty
//返回链表当中头节点的位置
Position Get_L_Head( LinkList L){
return L.head;
}
//返回链表当中最后一个节点的位置
Position GetLast( LinkList L){
return L.tail;
}
//由当前p指向的位置，查找p的邻接前一个节点的位置
Position PriorPos( LinkList L, Link p){
Link q = L.head;//声明一个临时的指针，用于遍历并定位于p的前躯
while( q->next != p)
q = q->next;
return q;
}
//由当前p指向的位置，查找p的下一个邻接元素的位置
Position NextPos( Link p){
return p->next;
}
//获取当前链表内第i个元素的位置，如果i不存在，则ERROR
Status LocatePos( LinkList L, Link &p, int i){
p = L.head;
int k = 1;//链表的位置是从1开始计算
while( p->next != NULL || k <= i){
p = p->next;
++k;
}
if( p->next == NULL && k < i) return ERROR;//如果计数器未及制定位置
//却已经到了尾部，则不存在指定节点
else return OK;
}
//查找当前链表当中与给定内容e相符的第一个元素的位置,找不到则返回Error
Status LocateElem( LinkList L, ElemType e, Status ( *compare)( ElemType ,ElemType)){
return 0;//需要比较函数，不写了~~
}
//遍历整个链表，如果遍历失败，则返回falsh
Status ListTraverse( LinkList L, Status (*Visit)(LinkList)){
return 0;//需要遍历函数，不写了~~~
}
