外贸网站响应式快速网站轻松排名
本节主要介绍单链表的简单算法实现。
本文部分ppt、视频截图来自:[青岛大学-王卓老师的个人空间-王卓老师个人主页-哔哩哔哩视频]
1. 单链表简单算法 ☆
- 单链表的初始化(带头结点)
即构造一个如下图所示的空表
【算法步骤】
- 生成新结点作为头结点,用头指针L指向头结点。
- 将头结点的指针域置空。
【算法描述】
Status InitList_L(LinkList &L){L = new LNode; //或L=(LinkList) malloc (sizeof(LNode));L -> next = NULL; //指针域置空return OK;
}
- 判断链表是否为空
空表:链表中无元素,称为空链表(头指针和头结点仍然在)
【算法思路】
判断头结点的指针域是否为空
【算法:判断链表是否为空】
int ListEmpty(LinkList L){//若L为空表,则返回1,否则返回0if(L->next) //非空return 0;elsereturn 1;
}
- 单链表的销毁
链表销毁后不存在。
【算法思路】
从头指针开始,一次释放所有结点。
【算法:销毁单链表L】
Status DestroyList_L(LinkList &L){ //销毁单链表LLnode *p; //或LinkList p;while(L){p = L;L = L -> next;delete p;}return OK;
}
- 清空链表
链表仍然存在,但链表中无元素,称为空链表(头指针和头结点仍然存在)
【算法思路】
依次释放所有结点,并将头结点指针域设置为空。
【算法:清空链表L】
Status ClearList(LinkList &L){ //将L重置为空表Lnode *p,*q; //或LinkList p,q;p = L-> next;while(p){ //没到表尾q = p -> next;delete p;p = q;}L -> next = NULL; //头结点指针域为空return OK;
}
- 求链表的表长
【算法思路】
从首元结点开始,依次计数所有结点。若是非空结点,表长加1。
【算法:求单链表L的表长】
int ListLength_L(LinkList L){ //返回L中数据元素的个数LinkList p;p = L -> next; //p指向第一个结点i = 0;while(p){ //遍历单链表,统计结点数i++; p = p -> next; //最后一个结点的下一结点指针域为空,循环结束}return i;
}