链表（单链表、双链表、循环链表、静态链表）入门

目录

单链表
什么是单链表？
代码界说单链表
初始化单链表
单链表的插入与删除
双链表
循环链表
静态链表
界说
 静态链表的插入

---

单链表

什么是单链表？

顺序表中每个结点只存放数据元素，而单链表中每个节点除了要存放数据元素之外，还要存储指向下一个结点的指针。
单链表与顺序表相比，优点是不要求大片的一连空间，改变容量方便，缺点是不可随机存取，要耗费一定空间存放指针。
代码界说单链表

两种方法一样

1. typedef struct LNode {//定义单链表结点类型
2.         ElemType data;//每个节点存放一个数据元素
3.         struct LNode* next;//指针指向下一个节点
4. }LNode, * LinkList;

复制代码

1. struct LNode {
2.         ElemType data;
3.         struct LNode* next;
4. };
5. typedef struct LNode LNode;
6. typedef struct LNode* LinkList;

复制代码

要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个结点
初始化单链表

不带头结点

1. typedef struct LNode {//定义单链表结点类型
2.         ElemType data;//每个节点存放一个数据元素
3.         struct LNode* next;//指针指向下一个节点
4. }LNode, * LinkList;
5. bool InitList(LinkList& L) {        L = NULL;//空表，暂时没有任何节点        return true;}void test() {        LinkList L;//声明一个指向单链表的指针        InitList(L);//初始化一个空表}

复制代码

带头结点

1. //定义单链表结点类型
2. typedef struct LNode {
3.         ElemType data;
4.         struct LNode* next;
5. }LNode, * LinkList;
6. //初始化单链表（带头结点）
7. bool InitList(LinkList& L) {
8.         L = (LNode*)malloc(sizeof(LNode));
9.         if (L == NULL)return false;
10.         L->next = NULL;
11.         return true;
12. }

复制代码

单链表的插入与删除

插入

1. Status ListInsert(LinkList* L, int i, ElemType e) {
2.         int j;
3.         LinkList p, s;
4.         p = *L;
5.         j = 1;
6.         //寻找第i个结点
7.         while (p && j < i) {
8.                 p = p->next;
9.                 ++j;
10.         }
11.         if (!p || j > i)return ERROR;
12.         s = (LinkList)malloc(sizeof(Node));
13.         s->data = e;
14.         s->next = p->next;
15.         p->next = s;
16.         return OK;
17. }

复制代码

删除

1. Status ListInsert(LinkList* L, int i, ElemType *e) {
2.         int j;
3.         LinkList p, q;
4.         p = *L;
5.         j = 1;
6.         while (p->next && j < i) {//遍历寻找第i个元素
7.                 p = p->next;
8.                 ++j;
9.         }
10.         if (!(p->next) || j > i)return ERROR;
11.         q = p->next;
12.         p->next = q->next;
13.         *e = q->data;
14.         free(q);
15.         return OK;
16. }

复制代码

双链表

单链表的每个结点都有指向后继的指针域，如今再加上一个指向前驱的指针域，这样的链表称为双链表。

1. typedef struct DulNode {
2.         ElemType data;
3.         struct DuLNode* prior;//直接前驱指针
4.         struct DuLNode* next;//直接后继指针
5. }DulNode, * DuLinkList;

复制代码

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,使整个单链表形成—个环，此时这个环叫循环链表。
在循环的判定上，单链表是判定p->next是否为空，循环链表是判定p->next是否等于头节点。
用尾指针来表示循环链表时，查找开始节点和终端节点都很方便。
如归并两个循环链表，它们的尾指针分别是rearA和rearB

1. p = rearA->next;//保存A表的头节点
2. rearA->next = rearB->next->next;//将本是指向B表的第一个节点（不是头节点）赋值给rearA->next
3. q = rearB->next;
4. rearB->next = p;
5. free(q);

复制代码

静态链表

界说

用数组代替指针描述单链表，这种链表叫静态链表。
为了方便插入数据，通常会把数组创建得大一些。

1. #define MAXSIZE 1000
2. //静态链表
3. typedef struct {
4.         ElemType date;
5.         int cur;
6. }Component, StaticLinkList[MAXSIZE];

复制代码

 静态链表的插入

在动态链表中，结点的申请和开释分别借用malloc()和free()两个函数来实现。在静态链表中，我们需要自己实现这两个函数。

1. //若备用空间链表非空，则返回分配的结点下标，否则返回0
2. int Malloc_SSL(StaticLinkList space) {
3.         int i = space[0].cur;//当前数组第一个元素的cur存的值就是返回的第一个备用空间的下标
4.         if (space[0].cur) {//由于要拿出一个分量来使用，所以要把下一个分量用来做备用
5.                 space[0].cur = space[i].cur;
6.         }
7.         return i;
8. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。