单向链表:list-c单向链表构建立表代码

/*@file listtest.c */
/*单链表构造表list*/
/*mingGW编译OK*/
# "allhead.h"
# "list.h"
# "fun.h"

void
{
LinkList L;
ElemType e,e0;
Status i;
j,k;
InitList(&L);
for(j=1;j<=5;j)
i=ListInsert(L,1,j);
prf("1.L表头依次插入1～5后:L=");
ListTraverse(L,pr); /* 依次对元素pr输出元素值 */
i=ListEmpty(L);
prf("2.L是否空:i=%d(1:是 0:否)\n",i);
ClearList(L);
prf("3.L清空后:L=");
ListTraverse(L,pr);
i=ListEmpty(L);
prf("5.L是否空:i=%d(1:是 0:否)\n",i);
for(j=1;j<=10;j)
ListInsert(L,j,j);
prf("6.L表尾依次插入1～10后:L=");
ListTraverse(L,pr);
GetElem(L,5,&e);
prf("7.L第5个元素值为:%d\n",e);
for(j=0;j<=1;j)
{
k=LocateElem(L,j,equal);
(k)
prf("8.L第%d个元素值为%d\n",k,j);

prf("8.L没有值为%d元素\n",j);
}
for(j=1;j<=2;j) /* 测试头两个数据 */
{
GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
i=PriorElem(L,e0,&e); /* 求e0前驱 */
(iINFEASIBLE)
prf("9.L元素%d无前驱\n",e0);

prf("9.L元素%d前驱为:%d\n",e0,e);
}
for(j=ListLength(L)-1;j<=ListLength(L);j) /* 最后两个数据 */
{
GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
i=NextElem(L,e0,&e); /* 求e0后继 */
(iINFEASIBLE)
prf("10.L元素%d无后继\n",e0);

prf("10.L元素%d后继为:%d\n",e0,e);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(L,j,&e); /* 删除第j个数据 */
(iERROR)
prf("11.L删除第%d个元素失败\n",j);

prf("11.L删除第%d个元素成功其值为:%d\n",j,e);
}
prf("12.L依次输出L元素:");
ListTraverse(L,pr);
DestroyList(&L);
prf("13.L销毁L后:L=%u\n",L);
}

/**************************************************************/

# "fun.h"

# "fun.h"

省略它们内容详见

http://blog.csdn.net/chinayaosir/archive/2008/09/20/2956091.aspx

/**************************************************************/

/*@file list.h*/
typedef ElemType;

typedef struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* 另种定义LinkList思路方法 */

/* bo2-2.c 带有头结点单链表(存储结构由c2-2.h定义)基本操作(12个),包括算法2.8,2.9,2.10 */
void InitList(LinkList *L)
{ /* 操作结果:构造个空线性表L */
*L=(LinkList)malloc((struct LNode)); /* 产生头结点并使L指向此头结点 */
(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */
}

void DestroyList(LinkList *L)
{ /* 条件:线性表L已存在操作结果:销毁线性表L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
}

void ClearList(LinkList L) /* 不改变L */
{ /* 条件:线性表L已存在操作结果:将L重置为空表 */
LinkList p,q;
p=L->next; /* p指向第个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* 头结点指针域为空 */
}

Status ListEmpty(LinkList L)
{ /* 条件:线性表L已存在操作结果:若L为空表则返回TRUE否则返回FALSE */
(L->next) /* 非空 */
FALSE;

TRUE;
}

ListLength(LinkList L)
{ /* 条件:线性表L已存在操作结果:返回L中数据元素个数 */
i=0;
LinkList p=L->next; /* p指向第个结点 */
while(p) /* 没到表尾 */
{
i;
p=p->next;
}
i;
}

Status GetElem(LinkList L, i,ElemType *e) /* 算法2.8 */
{ /* L为带头结点单链表头指针当第i个元素存在时其值赋给e并返回OK否则返回ERROR */
j=1; /* j为计数器 */
LinkList p=L->next; /* p指向第个结点 */
while(p&&j<i) /* 顺指针向后查找直到p指向第i个元素或p为空 */
{
p=p->next;
j;
}
(!p||j>i) /* 第i个元素不存在 */
ERROR;
*e=p->data; /* 取第i个元素 */
OK;
}

LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 条件: 线性表L已存在compare是数据元素判定(满足为1否则为0) */
/* 操作结果: 返回L中第1个和e满足关系compare数据元素位序 */
/* 若这样数据元素不存在则返回值为0 */
i=0;
LinkList p=L->next;
while(p)
{
i;
(compare(p->data,e)) /* 找到这样数据元素 */


i;
p=p->next;
}
0;
}

Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L数据元素且不是第个则用pre_e返回它前驱 */
/* 返回OK；否则操作失败pre_e无定义返回INFEASIBLE */
LinkList q,p=L->next; /* p指向第个结点 */
while(p->next) /* p所指结点有后继 */
{
q=p->next; /* q为p后继 */
(q->datacur_e)
{
*pre_e=p->data;
OK;
}
p=q; /* p向后移 */
}
INFEASIBLE;
}

Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 条件:线性表L已存在 */
/* 操作结果:若cur_e是L数据元素且不是最后个则用next_e返回它后继 */
/* 返回OK;否则操作失败next_e无定义返回INFEASIBLE */
LinkList p=L->next; /* p指向第个结点 */
while(p->next) /* p所指结点有后继 */
{
(p->datacur_e)
{
*next_e=p->next->data;
OK;
}
p=p->next;
}
INFEASIBLE;
}

Status ListInsert(LinkList L, i,ElemType e) /* 算法2.9不改变L */
{ /* 在带头结点单链线性表L中第i个位置的前插入元素e */
j=0;
LinkList p=L,s;
while(p&&j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j;
}
(!p||j>i-1) /* i小于1或者大于表长 */
ERROR;
s=(LinkList)malloc((struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
OK;
}

Status ListDelete(LinkList L, i,ElemType *e) /* 算法2.10不改变L */
{ /* 在带头结点单链线性表L中删除第i个元素并由e返回其值 */
j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* 寻找第i个结点并令p指向其前岖 */
{
p=p->next;
j;
}
(!p->next||j>i-1) /* 删除位置不合理 */
ERROR;
q=p->next; /* 删除并释放结点 */
p->next=q->next;
*e=q->data;
free(q);
OK;
}

void ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi形参类型为ElemType和bo2-1.c中相应形参类型ElemType&区别 */
{ /* 条件:线性表L已存在操作结果:依次对L每个数据元素vi */
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
prf("\n");
}

延伸阅读

• 2009-8-16-- 双向链表:net中的游标链表和普通链表对GC的影响
• 2009-1-9-- vc单向链表:C#如何实现单向链表
• 2009-8-16-- 双向链表:C#使用双链表来实现模拟IE前进后退功能
• 2008-12-6-- 遍历链表:单向链表的插入、查找和遍历方法