文章目录

• • 单链表
  • • 链表的概念及结构
    • 链表的分类
    • 链表的实现
    • • 动态申请一个节点
      • 创建链表
      • 单链表打印
      • 单链表尾插
      • 单链表尾删
      • 单链表头插
      • 单链表头删

单链表

链表的概念及结构

概念：链表是一种物理存储结构上连续、非顺序的存储结构，数据元素的逻辑顺序 是通过链表中的指针链接次序实现的。

注意：

1. 从上图可以看出，链式结构在逻辑上连续的，但是在物理上不一定连续
2. 现实中的节点一般是从堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续的也可能是不连续

链表的分类

实际中链表的结构非常多样，一下情况组合起来就有8中情况：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会用来单独存放数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。另外这种结构在笔试面试中出现很多
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。

链表的实现

动态申请一个节点

SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

创建链表

SListNode* CreateSListNode(int n)
{SListNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; i++){SListNode* newnode = BuySListNode(i);if (phead == NULL){ptail = phead = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}

单链表打印

void SListPrint(SListNode* phead)
{SListNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

单链表尾插

//尾插要想改变原来的，就要传地址
void SListPushBack(SListNode** pplist, SLTDataType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* cur = *pplist;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}

单链表尾删

void SListPopBack(SListNode** pplist)
{assert(*pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* ptail = *pplist;while (ptail->next->next != NULL){ptail = ptail->next;}free(ptail->next);ptail->next = NULL;}
}

单链表头插

void SListPushFront(SListNode** pplist, SLTDataType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}

单链表头删

void SListPopFront(SListNode** pplist)
{assert(*pplist);SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;
}

注意：在C语言的单链表，关于改变链表的数字的函数传递方式，传的都是地址。如果不传地址的话就不能改变链表的数值。

就如这个例子一样：

void swap(int* a, int* b)
{int x = *a;*a = *b;*b = x;
}
void swap1(int a, int b)
{int x = a;a = b;b = x;
}
int main()
{int a = 10;int b = 20;swap1(a, b);printf("a=%d b=%d\n", a, b);swap(&a, &b);printf("a=%d b=%d\n", a, b);
}

运行结果：

对于第二种方法，传递的是地址，这里直接把地址里面的数字改了