从实际应用角度出发重新定义线性链表及其基本操作。
/**********************************************
具有实际意义的线性链表
by Rowandjj
2014/4/6
***********************************************/
#include<IOSTREAM>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int ElemType;
/*节点类型定义*/
typedef struct _NODE_
{
ElemType data;
struct _NODE_ *next;
}Node,*Link;
/*链表类型定义*/
typedef struct _LINKEDLIST_
{
Link pHead,pTail;//头指针和尾指针
int len;//链表长度
}LinkedList;
/*操作定义*/
int MakeNode(Link &p,ElemType e);
void FreeNode(Link &p);
int InitList(LinkedList &L);
int DestroyList(LinkedList &L);
int ClearList(LinkedList &L);
int InsFirst(LinkedList &L,Link h,Link s);//h指向头节点，将节点s插入到第一个节点之前
int DelFirst(LinkedList &L,Link h,Link &q);//h指向头节点，删除链表中的第一个节点并以q返回
int Append(LinkedList &L,Link s);//将s所指向的一串节点指向链接到链表最后一个节点上
int Remove(LinkedList &L,Link &q);//删除尾节点并以q返回
int InsBefore(LinkedList &L,Link &p,Link s);//将s所指向节点插入到p节点之前
Link PriorPos(LinkedList L,Link p);//返回节点p前驱
int InsAfter(LinkedList &L,Link &p,Link s);//将s所指节点插入到p之后
int SetCurElem(Link &p,ElemType e);//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
ElemType getCurElem(Link p);//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
int ListEmpty(LinkedList L);
int ListLength(LinkedList L);
Link GetHead(LinkedList L);
Link GetLast(LinkedList L);
Link NextPos(Link p);
int LocatePos(LinkedList L,int i,Link &p);//返回p指示线性链表L中第i个结点的位置，并返回OK，i值不合法时返回ERROR,i=0为头结点
Link LocateElem(LinkedList L,ElemType e,int(*compare)(ElemType,ElemType));//返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置，若不存在这样的元素，则返回NULL
int ListTraverse(LinkedList L,void(*visit)(ElemType));//依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
int LocateElemP(LinkedList L,ElemType e,Link &q,int(*compare)(ElemType,ElemType));/* 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中 */
/* 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数 */
/* compare()取值>0的元素的前驱的位置。并返回FALSE。（用于一元多项式） */
int OrderInsert(LinkedList &L,ElemType e,int (*comp)(ElemType,ElemType));
/* 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式） */
int compare(ElemType e1,ElemType e2);
void visit(ElemType e);
int main()
{
return 0;
}
int MakeNode(Link &p,ElemType e)
{
p = (Link)malloc(sizeof(Node));
if(!p)
{
exit(OVERFLOW);
}
p->data = e;
return OK;
}
void FreeNode(Link &p)
{
free(p);
p = NULL;
return;
}
int InitList(LinkedList &L)
{
Link p;
p = (Link)malloc(sizeof(Node));
if(!p)
{
exit(OVERFLOW);
}
L.pHead = L.pTail = p;
L.len = 0;
return OK;
}
int DestroyList(LinkedList &L)
{
ClearList(L);
FreeNode(L.pHead);
L.pTail = NULL;
L.len = 0;
return OK;
}
int ClearList(LinkedList &L)
{
Link p,q;
if(L.pTail != L.pHead)
{
p = q = L.pHead->next;
L.pHead->next = NULL;
while(p != L.pTail)
{
p = q->next;
free(q);
q = p;
}
free(q);
L.pTail = L.pHead;
L.len = 0;
}
return OK;
}
int InsFirst(LinkedList &L,Link h,Link s)
{
s->next = h->next;
h->next = s;
if(L.pTail == h)
{
L.pTail = h->next;
}
L.len++;
return OK;
}
int DelFirst(LinkedList &L,Link h,Link &q)
{
q = h->next;
if(q)
{
h->next = q->next;
if(!h->next)
{
L.pTail = h;
}
L.len--;
return OK;
}
else
{
return ERROR;
}
}
int Append(LinkedList &L,Link s)
{
L.pTail->next = s;
int i = 1;
while(s->next)
{
i++;
s = s->next;
}
L.len+=i;
L.pTail = s;
return OK;
}
int Remove(LinkedList &L,Link &q)
{
Link p = L.pHead;
if(L.len == 0)//空表
{
q = NULL;
return ERROR;
}
while(p->next != L.pTail)
{
p = p->next;
}
q = L.pTail;//这里不需要free掉remove的节点
p->next = NULL;
L.pTail = p;
L.len--;
return OK;
}
Link PriorPos(LinkedList L,Link p)//已知p为L中的节点
{
Link q;
q = L.pHead->next;
if(q==p)//无前驱
{
return NULL;
}
else
{
while(q->next != p)
{
q = q->next;
}
return q;
}
}
int InsBefore(LinkedList &L,Link &p,Link s)
{
Link q;
q = PriorPos(L,p);
if(!q)
{
q = L.pHead;
}
s->next = p;
q->next = s;
p = s;//修改指针p指向新插入的节点
L.len++;
return OK;
}
int InsAfter(LinkedList &L,Link &p,Link s)
{
if(p == L.pTail)
{
L.pTail = s;
}
s->next = p->next;
p->next = s;
p = s;
L.len++;
return OK;
}
int SetCurElem(Link &p,ElemType e)
{
p->data = e;
return OK;
}
ElemType getCurElem(Link p)
{
return p->data;
}
int ListEmpty(LinkedList L)
{
return L.len ? false : true;
}
int ListLength(LinkedList L)
{
return L.len;
}
Link GetHead(LinkedList L)
{
return L.pHead;
}
Link GetLast(LinkedList L)
{
return L.pTail;
}
Link NextPos(Link p)
{
return p->next;
}
int LocatePos(LinkedList L,int i,Link &p)
{
int j;
if(i<0 || i>L.len)
{
return ERROR;
}
else
{
p = L.pHead;
for(j = 1; j <= i; j++)
{
p = p->next;
}
return OK;
}
}
Link LocateElem(LinkedList L,ElemType e,int(*compare)(ElemType,ElemType))
{
Link p = L.pHead;
do
{
p = p->next;
} while (p && !(compare(p->data,e)));
return p;
}
int ListTraverse(LinkedList L,void(*visit)(ElemType))
{
Link p = L.pHead;
for(int i = 0; i < L.len; i++)
{
visit(p->data);
p = p->next;
}
cout<<endl;
return OK;
}
int LocateElemP(LinkedList L,ElemType e,Link &q,int(*compare)(ElemType,ElemType))
{
Link p = L.pHead,pp;
do
{
pp = p;
p = p->next;
} while (p && compare(p->data,e)<0);
if(!p || compare(p->data,e)>0)
{
q = pp;
return ERROR;
}
else
{
q = p;
return OK;
}
}
int OrderInsert(LinkedList &L,ElemType e,int (*comp)(ElemType,ElemType))
{
Link o,p,q;
q = L.pHead;
p = q->next;
while(p&&comp(p->data,e)<0) /* p不是表尾且元素值小于e */
{
q=p;
p=p->next;
}
o = (Link)malloc(sizeof(Node));
if(!o)
{
exit(OVERFLOW);
}
o->data = e;
q->next = o;
o->next = p;
L.len++;
if(!p)
{
L.pTail = o;
}
return OK;
}
int compare(ElemType e1,ElemType e2)
{
return e1 == e2;
}
void visit(ElemType e)
{
cout<<e<<" ";
}一个 Wordpress 前端 bug 的折腾过程及感悟,布布扣,bubuko.com
原文：http://blog.csdn.net/dragonszy/article/details/23024823