数据结构之线性表(五)

2024-07-11 16:58| 来源: 网络整理| 查看: 265

1.单链表(带头结点)的初始化即，构造一个空表，如下图，在这里插入图片描述

算法步骤： 1.生成新结点作头结点，用头指针L指向头结点。2.将头指针的指针域置空。算法描述： Status InitList_L(LinkList& L) { L = new LNode; //在C语言里，为 L=(LinkList)malloc(sizeof(LNode)); L->next = NULL; return OK; }

2.判断链表是否为空

空表：链表中无元素，但头指针和头结点仍然在。在这里插入图片描述

算法思路：判断头结点的指针域是否为空。算法描述： int ListEmpty(LinkList L) //若L为空表，则返回1，否则返回0 { if (L->next) //非空 return 0; else return 1; }

3.单链表的销毁

销毁单链表：在内存中删除，链表销毁后，其头指针和头结点也不会存在。

算法思路：从头节点开始，依次释放所有结点。怎么能让一个指针p指向变量a？做法就是把a的地址赋给指针变量p，即p=&a。这样就定义了一个指向a的指针p。 1.先定义一个指针p，指向当前结点(一开始，p是指向头结点的指针)，即，p=L 在这里插入图片描述

2.让L指向下一个结点，即，L=L->next, 在这里插入图片描述

3.删除当前结点p，即，delete p 4.回到第一步。 5.结束条件为：L=NULL (循环条件为：L!=NULL或L)算法描述： Status DestroyList_L(LinkList& L) //销毁单链表L { Lnode* p; //或LinkList p; while (L) { p = L; //指向当前结点(一开始指向的是头节点) L = L->next; //使L指向下一结点 delete p; //删除当前结点 } }

4.清空单链表

清空单链表：链表在内存中仍然存在(头指针和头结点仍然在)，但链表中无元素。

算法思路：依次释放所有结点，并将头结点指针域设置为空。怎么能让指针p指向首元结点？p=L; //p指向头结点 p=L->next; //p指向首元结点 1.先定义一个指针p，指向当前结点(一开始，p是指向首元结点的指针)，即，p=L->next 在这里插入图片描述

2.在释放当前结点p之前，要先确定好下一结点的位置。所以需要再定义一个指针q，让其指向下一个结点，即，q=p->next。然后再释放p。在这里插入图片描述

3.接下来反复执行p=q;q=q->next。在这里插入图片描述

4.结束条件为：p=NULL (循环条件为：p!=NULL 5.将头结点的指针域设置为空，即L->next=NULL算法描述： Status ClearList_L(LinkList& L) //将L设置为空表 { Lnode *p,*q; //或LinkList p,q; p = L->next; //p指向首元结点 while (p) { q = p->next; //q指向下一个结点 delete p; //删除当前结点 p = q; //将下一结点设置为当前结点 } L->next = NULL; //头结点的指针域置空 return OK; }

5.求单链表的长度

算法思路：从首元结点开始，依次计数所有结点。怎么能让指向当前结点指针p指向下一结点？

p=p->next; //p指向下一个结点，p往后移动一个结点

1.先定义一个指针p，指向当前结点(一开始，p是指向首元结点的指针)，即，p=L->next。 2.若p不为空，则计1，再让p指向下一结点，即，p=p->next。 3.结束条件为：p=NULL (循环条件为：p!=NULL

算法描述：

int ListLength_L(LinkList L) //返回L中数据元素的个数 { Lnode *p; //或LinkList p; p = L->next; //p指向首元结点 i = 0; //计数 while (p) //遍历单链表，统计结点数 { i++; p = p->next; //p指向下一个结点 } return i; }

【本文地址】

数据结构之线性表(五)

数据结构之线性表(五)

今日新闻

推荐新闻