数据结构c++单链表整表删除与顺序存储的对比

太过爱你忘了你带给我的痛 2023-10-03 13:57 6阅读 0赞

## **一.单链表整表删除的算法思路如下:** ##

**1.声明结点p和q;  
2.将第一个结点赋值给p，下一结点赋值给q;  
3.循环执行释放p和将q赋值给p的操作;**

template<typename DataType>
    LinkList<DataType>::~LinkList()
    {
        
       Node<DataType>*p=frist;
       while (first != nullptr)
       {
        
          first = first->next;
          delete p;     //c语言中使用free释放p
          p=first;
       }
    };

## 二.单链表结构与顺序存储结构优缺点 ##

**·我们分别从存储分配方式、时间性能、空间性能三方面来做对比。**  
**存储分配方式:**  
1.顺序存储结构用一段连续的存储单元依次存储线性  
表的数据元素。  
2.单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。  
**时间性能:  
查找**  
1.顺序存储结构0(1)  
2.单链表0(n)  
**插入和删除**  
1.顺序存储结构需要平均移动表长一半的元素,时间为0(n)  
2.单链表在计算出某位置的指针后,插入和删除时间仅为0(1)  
**空间性能:**  
1.顺序存储结构需要预分配存储空间,分大了，容易造成空间浪费，分小了，容易发生溢出。  
2.单链表不需要分配存储空间，只要有就可以分配,  
元素个数也不受限制。  
**综上所述对比,我们得出一些经验性的结论:**  
1.若线性表需要频繁查找，很少进行插入和删除操作时,宜采用顺序存储结构。  
2.若需要频繁插入和删除时,宜采用单链表结构。  
**举例**  
1.比如说游戏开发中,对于用户注册的个人信息,除了注册时插入数据外,绝大多数情况都是读取,所以应该考虑用顺序存储结构。  
2.而游戏中的玩家的武器或者装备列表,随着玩家的游戏过程中，可能会随时增加或删除,此时再用顺序存储就不太合适了,单链表结构就可以大展拳脚了。  
3.当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间的大小问题。  
4.而如果事先知道线性表的大致长度,比如一年12个月,一周就是星期一至星期日共七天,这种用顺序存储结构效率会高很多。  
**总之,线性表的顺序存储结构和单链表结构各有其优缺点,不能简单的说哪个好,哪个不好,需要根据实际情况,来综合平衡采用哪种数据结构更能满足和达到需求和性能。**