单向链表结构图（单向链表有什么特征）

大家好，我是讯享网，很高兴认识大家。

//—————-单链表的存储结构——————–

typedef struct LNode

{

} LNode, *LinkList; // LinkList 为指向结构体 LNode 的指针类型

（2）为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList 与 LNode，两者本质上是等价的。通常习惯上用 LinkList 定义单链表，强调定义的是某个单链表的头指针；用 LNode 定义指向单链表中任意结点的指针变量。例如，若定义 LinkList L，则 L 为单链表的头指针，若定义 LNode* p，则 p 为指向单链表中某个结点的指针，用 p 代表该结点。当然也可以使用定义 LinkList p，这种定义形式完全等价于 LNode p。

（4）注意区分指针变量和结点变量两个不同的概念，若定义 LinkList p 或 LNode* p，则 p 为指向某个结点的指针变量，表示该结点的地址；而 p 为对应的结点变量，表示该结点的名称。

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。

—————————-此处省略一张图————————–

下面对首元结点、头结点、头指针三个容易混淆的概念加以说明。

（1）首元结点是指链表中存储第一个数据元素 a1 的结点。

（2）头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可以存放该线性表的长度。

（3）头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

链表增加头结点的作用如下。

（1）便于首元结点的处理

增加了头结点后，首元结点的地址保存在头结点（即其“前驱”结点）的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。

（2）便于空表和非空表的统一处理

当链表不设头结点时，假设 L 为单链表的头指针，它应该指向首元结点，则当单链表为长度 n 为 0 的空表时，L 指针为空（判定空表的条件可记为：L == NULL）。

增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。若为空表，则头结点的指针域为空（判定空表的条件可记为：L->next == NULL）。

#include <stdio.h>

#include <stdlib.h>

typedef struct LNode

{

int data;

struct LNode next;

} LNode, *LinkList; // LinkList 为指向结构体 LNode 的指针类型

void CreateList_H(LinkList *L, int n);

void CreateList_R(LinkList *L, int n);

void TraverseList(LinkList L);

void ReverseList(LinkList L);

void FreeList(LinkList L);

int GetElem(LinkList L, int i, int e);

int ListInsert(LinkList *L, int i, int e);

int ListDelete(LinkList L, int i);

int main()

{

LinkList L;

L = NULL;

int n;

printf(“请输入链表的长度：”);

scanf(“%d”, &n);

CreateList_R(&L, n);

TraverseList(L);

// ReverseList(L);

// TraverseList(L);

// int flag, i, e;

// while (1)

// {

// printf(“请输入要取值的结点序号（输入负数退出）：”);

// scanf(“%d”, &i);

// if (i < 0) break;

// flag = GetElem(L, i, &e);

// if (flag) printf(“指定的序号不合法 ”);

// else printf(“对应结点的值为：%d ”, e);

// }

// int flag, i, e;

// while (1)

// {

// printf(“请输入插入位置：”);

// scanf(“%d”, &i);

// if (i < 0) break;

// printf(“请输入插入的值：”);

// scanf(“%d”, &e);

// flag = ListInsert(&L, i, e);

// if (flag) break;

// TraverseList(L);

// }

int flag, i;

while (1)

{

讯享网

printf(“请输入要删除结点的序号：”);

scanf(“%d”, &i);

if (i < 1) break;

flag = ListDelete(&L, i);

if (flag) break;

TraverseList(L);

}

FreeList(&L);

return 0;

}

void TraverseList(LinkList L)

{

LNode p;

p = L->next;

while (p)

{

printf(“->%d”, p->data);

p = p->next;

}

printf(“ ”);

}

void FreeList(LinkList *L)

{

LNode *p, *tmp;

p = *L;

while (p != NULL)

{

tmp = p;

p = p->next;

free(tmp);

}

*L = NULL;

tmp = NULL;

}

void CreateList_H(LinkList *L, int n) // 指向指针的指针

{

L = (LNode)malloc(sizeof(LNode));

if (*L == NULL)

{

printf(“内存分配失败 ”);

exit(1);

}

(L)->next = NULL;

LNode p;

for (int i = 1; i <= n; i++)

{

p = (LNode*)malloc(sizeof(LNode));

if (p == NULL)

{

printf(“内存分配失败 ”);

exit(1);

}

printf(“请输入第%d个结点的值：”, i);

scanf(“%d”, &p->data);

p->next = (*L)->next;

(*L)->next = p;

}

void CreateList_R(LinkList *L, int n)

{

L = (LNode)malloc(sizeof(LNode));

if (*L == NULL)

{

printf(“内存分配失败 ”);

exit(1);

}

(*L)->next = NULL;

LNode *r, *p;

r = L;

for (int i = 1; i <= n; i++)

{

p = (LNode)malloc(sizeof(LNode));

if (p == NULL)

{

printf(“内存分配失败 ”);

exit(1);

}

printf(“请输入第%d个结点的值：”, i);

scanf(“%d”, &p->data);

p->next = NULL;

r->next = p;

r = p;

}

void ReverseList(LinkList L)

{

LNode *cur, *pre, tmp;

cur = NULL;

pre = L->next;

while (pre)

{

tmp = pre->next;

pre->next = cur;

cur = pre;

pre = tmp;

}

L->next = cur;

}

int GetElem(LinkList L, int i, int e)

{

LNode *p;

p = L->next;

int j = 1;

while (p && j < i)

{

p = p->next;

j++;

}

if (p == NULL || j > i)

{

return 1;

}

*e = p->data;

return 0;

}

int ListInsert(LinkList L, int i, int e)

{ // 在带头结点的单链表 L 中第 i 个位置插入值为 e 的新结点

LNode p = L;

int j = 0;

while (p && (j < i - 1)) // 查找第 i - 1 个结点，p 指向该结点

{

p = p->next;

j++;

}

if (p == NULL || j > i - 1) return 1;

LNode s;

s = (LNode)malloc(sizeof(LNode));

s->data = e;

s->next = p->next;

p->next = s;

return 0;

}

int ListDelete(LinkList L, int i)

{ // 在带头结点的单链表 L 中，删除第 i 个元素

LNode* p;

p = L;

int j = 0;

while (p->next && (j < i - 1)) // 查找第 i - 1 个结点，p 指向该结点

{

p = p->next; j++;

}

if (!p->next || (j > i - 1)) return 1;

LNode q;

q = p->next;

p->next = q->next;

free(q);

return 0;

}

单向链表结构图（单向链表有什么特征）

相关推荐