单向链表

此條目没有列出任何参考或来源。 (2011年11月8日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

单向链表（又名单链表、线性链表，英語：singly linked list）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下讀取。

数据结构

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

動態單鏈表（C语言）

單向鏈表的數據结構可以分為兩部分：數據域和指针域，數据域存儲數據，指针域指向下一個儲存節點的地址。

存储结构

/* c2-2.h 线性表的单链表存储结构 */
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

基本操作

/* bo2-2.c 带有头结点的单链表(存储结构由c2-2.h定义)的基本操作(12个),包括算法2.8,2.9,2.10 */
void InitList(LinkList *L)
{	/* 操作结果：构造一个空的线性表L */
	*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
	if(!*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 */
	if(L->next) /* 非空 */
		return FALSE;
	else
		return TRUE;
}

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

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

int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{	/* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */
	/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
	/*           若这样的数据元素不存在，则返回值为0 */
	int i=0;
	LinkList p=L->next;
	while(p)
	{
		i++;
		if(compare(p->data,e)) /* 找到这样的数据元素 */
			return i;
		p=p->next;
	}
	return 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的后继 */
		if(q->data==cur_e)
		{
			*pre_e=p->data;
			return OK;
		}
		p=q; /* p向后移 */
	}
	return 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所指结点有后继 */
	{
		if(p->data==cur_e)
		{
			*next_e=p->next->data;
			return OK;
		}
		p=p->next;
	}
	return INFEASIBLE;
}

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

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

^[1]

静态单链表（C语言）

// 线性表的静态单链表存储结构
#define MAX_SIZE 100 // 链表的最大长度
typedef struct {
    ElemType data; //此處的ElemType可以自由代換（如int/float等）
    int cur;
} component, SLinkList[MAX_SIZE];

// 一个数组只生成一个静态链表的基本操作(11个)
#define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的

void InitList(SLinkList L) {
    // 构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE-1]，其余单元链成
    // 一个备用链表，表头为L的第一个单元L[0]，“0”表示空指针
    int i;
    L[MAX_SIZE - 1].cur = 0; // L的最后一个单元为空链表的表头
    for (i = 0; i < MAX_SIZE - 2; i++) // 将其余单元链接成以L[0]为表头的备用链表
        L[i].cur = i + 1;
    L[MAX_SIZE - 2].cur = 0;
}

void ClearList(SLinkList L) {
    // 初始条件：线性表L已存在。操作结果：将L重置为空表
    int i, j, k;
    i = L[MAX_SIZE - 1].cur; // 链表第一个结点的位置
    L[MAX_SIZE - 1].cur = 0; // 链表空
    k = L[0].cur; // 备用链表第一个结点的位置
    L[0].cur = i; // 把链表的结点连到备用链表的表头
    while (i) { // 没到链表尾
        j = i;
        i = L[i].cur; // 指向下一个元素
    }
    L[j].cur = k; // 备用链表的第一个结点接到链表的尾部
}

Status ListEmpty(SLinkList L) {
    // 若L是空表，返回TRUE；否则返回FALSE
    if (L[MAX_SIZE - 1].cur == 0) // 若为空表
        return TRUE;
    else
        return FALSE;
}

int ListLength(SLinkList L) {
    // 返回L中数据元素个数
    int j = 0, i = L[MAX_SIZE - 1].cur; // i指向第一个元素
    while (i) { // 没到静态链表尾
        i = L[i].cur; // 指向下一个元素
        j++;
    }
    return j;
}

Status GetElem(SLinkList L, int i, ElemType *e) {
    // 用e返回L中第i个元素的值
    int l, k = MAX_SIZE - 1; // k指向表头序号
    if (i < 1 || i > ListLength(L))
        return ERROR;
    for (l = 1; l <= i; l++) // 移动到第i个元素处
        k = L[k].cur;
    *e = L[k].data;
    return OK;
}

int LocateElem(SLinkList L, ElemType e) { // 算法2.13(有改动)
    // 在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的
    // 位序，否则返回0。(与其它LocateElem()的定义不同)
    int i = L[MAX_SIZE - 1].cur; // i指示表中第一个结点
    while (i && L[i].data != e) // 在表中顺链查找(e不能是字符串)
        i = L[i].cur;
    return i;
}

Status PriorElem(SLinkList L, ElemType cur_e, ElemType *pre_e) {
    // 初始条件：线性表L已存在
    // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
    // 否则操作失败，pre_e无定义
    int j, i = L[MAX_SIZE - 1].cur; // i指示链表第一个结点的位置
    do { // 向后移动结点
        j = i;
        i = L[i].cur;
    } while (i && cur_e != L[i].data);
    if (i) { // 找到该元素
        *pre_e = L[j].data;
        return OK;
    }
    return ERROR;
}

Status NextElem(SLinkList L, ElemType cur_e, ElemType *next_e) {
    // 初始条件：线性表L已存在
    // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继
    // 否则操作失败，next_e无定义
    int j, i = LocateElem(L, cur_e); // 在L中查找第一个值为cur_e的元素的位置
    if (i) { // L中存在元素cur_e
        j = L[i].cur; // cur_e的后继的位置
        if (j) { // cur_e有后继
            *next_e = L[j].data;
            return OK; // cur_e元素有后继
        }
    }
    return ERROR; // L不存在cur_e元素，cur_e元素无后继
}

Status ListInsert(SLinkList L, int i, ElemType e) {
    // 在L中第i个元素之前插入新的数据元素e
    int l, j, k = MAX_SIZE - 1; // k指向表头
    if (i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc(L); // 申请新单元
    if (j) { // 申请成功
        L[j].data = e; // 赋值给新单元
        for (l = 1; l < i; l++) // 移动i-1个元素
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

Status ListDelete(SLinkList L, int i, ElemType *e) {
    // 删除在L中第i个数据元素e，并返回其值
    int j, k = MAX_SIZE - 1; // k指向表头
    if (i < 1 || i > ListLength(L))
        return ERROR;
    for (j = 1; j < i; j++) // 移动i-1个元素
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    *e = L[j].data;
    Free(L, j);
    return OK;
}

void ListTraverse(SLinkList L, void(*vi)(ElemType)) {
    // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()
    int i = L[MAX_SIZE - 1].cur; // 指向第一个元素
    while (i) { // 没到静态链表尾
        vi(L[i].data); // 调用vi()
        i = L[i].cur; // 指向下一个元素
    }
    printf("\n");
}

^ 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安电子科技大学出版社. ISBN 9787560611761 （中文）.

分类

[1] 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安电子科技大学出版社. ISBN 9787560611761 （中文）.

[1]

单向链表

数据结构

動態單鏈表（C语言）

存储结构

基本操作

静态单链表（C语言）

Suggest as cover photo

Thank you for helping!

Install Wikiwand

Don't forget to rate us

Tell your friends about Wikiwand!

Enjoying Wikiwand?

Tell your friends and spread the love:

Your preferred languages

All languages

Follow Us

Don't forget to rate us

Our magic isn't perfect

Thank you for helping!

Oh no, there's been an error