《数据结构》静态链表类的定义参考代码

前端之家收集整理的这篇文章主要介绍了《数据结构》静态链表类的定义参考代码前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

静态链表是使用数组来表示链表,因为使用数组来存放数据,所以是静态的,又因为使用数据元素的下标来模单链表指针,所以又称链表,综合上述两点,称作静态链表。

这是一个假链表。

在具体实现时,建立一个头结点,并建立两个指针,first和avail,将表中数据元素链成一个数据链,将空闲元素链成一个空链。first指向头结点,头结点指向第一个数据结点, avail批向空链。用下面在顺序表的基础上,将静态链表的类定义给大家参考。实现时可以更变更高效代码

请参考课本图2-27图。

1.定义数组元素类型


  1. const int max Maxsize=100 //定义一个数组最大长度
  2. template <class DataType>
  3. struct Node
  4. {
  5. DataType data;
  6. int next ; //存放下一个元素的下标
  7. };

2.声明一个静态链表类
  1. emplate <class DataType>
  2. class static_LinkList
  3. {
  4. public:
  5. static_LinkList( ); //构造函数,含空静态链表
  6. static_LinkList(DataType a[ ],int n); //构造函数,建立有n个元素的静态链表
  7. ~static_LinkList( ); //析构函数
  8. void PrintList( ); //遍历操作,按序号依次输出各元素
  9. private:
  10. Node<DataType> data[MaxSize]; //存放数据元素的数组
  11. int first; // 指向静态链表头指针
  12. int avail; // 指向空链指针
  13. };

  1.  
3.定义构造函数

无参构造函数

  1. template <class DataType>
  2. static_LinkList<DataType> :: static_LinkList( )
  3. {
  4. first=0; ///初始化头指针
  5. avail=1; //初始化空闲链指针
  6. data[0].next=-1; //头结点无后续结点
  7. for(int i=1;i<maxsize-1;i++)
  8. data[i].next=i+1; //初始化空闲链
  9. data[maxsize-1]=-1; //置空闲链结束标志
  10. }

有参构造函数

  1. template <class DataType>
  2. static_LinkList<DataType> ::static_LinkList(DataType a[ ],int n)
  3. { int s;
  4. if(n>MaxSize|| n<=0)throw"error"
  5. first=0;
  6. data[0].next=avail=1;
  7. for(int i=0;i<maxsize-1;i++)
  8. data[i].next=i+1; //先将数组置为闲链 这部分也可以在后面,但只将存放数据后的空链相连
  9. data[maxsize-1]=-1; //置空闲链结束标志
  10. for(int i=0;i<n;i++) >
  11. { s=avail;
  12. data[s].data=a[i];
  13. avail=data[avail].next;
  14. }
  15. data[s].next=-1;
  16. }
还有删除、插入、访问、查找等操作大家自己写代码,并实例验证。祝大家成功。

猜你在找的数据结构相关文章