静态链表是使用数组来表示链表,因为使用数组来存放数据,所以是静态的,又因为使用数据元素的下标来模单链表指针,所以又称链表,综合上述两点,称作静态链表。
这是一个假链表。
在具体实现时,建立一个头结点,并建立两个指针,first和avail,将表中数据元素链成一个数据链,将空闲元素链成一个空链。first指向头结点,头结点指向第一个数据结点, avail批向空链。用下面在顺序表的基础上,将静态链表的类定义给大家参考。实现时可以更变更高效代码。
请参考课本图2-27图。
1.定义数组元素类型
- const int max Maxsize=100 //定义一个数组最大长度
- template <class DataType>
- struct Node
- {
- DataType data;
- int next ; //存放下一个元素的下标
- };
2.声明一个静态链表类
- emplate <class DataType>
- class static_LinkList
- {
- public:
- static_LinkList( ); //构造函数,含空静态链表
- static_LinkList(DataType a[ ],int n); //构造函数,建立有n个元素的静态链表
- ~static_LinkList( ); //析构函数
- void PrintList( ); //遍历操作,按序号依次输出各元素
- private:
- Node<DataType> data[MaxSize]; //存放数据元素的数组
- int first; // 指向静态链表头指针
- int avail; // 指向空链指针
- };
3.定义构造函数
无参构造函数:
- template <class DataType>
- static_LinkList<DataType> :: static_LinkList( )
- {
- first=0; ///初始化头指针
- avail=1; //初始化空闲链指针
- data[0].next=-1; //头结点无后续结点
- for(int i=1;i<maxsize-1;i++)
- data[i].next=i+1; //初始化空闲链
- data[maxsize-1]=-1; //置空闲链结束标志
- }
有参构造函数:
还有删除、插入、访问、查找等操作大家自己写代码,并实例验证。祝大家成功。
- template <class DataType>
- static_LinkList<DataType> ::static_LinkList(DataType a[ ],int n)
- { int s;
- if(n>MaxSize|| n<=0)throw"error"
- first=0;
- data[0].next=avail=1;
- for(int i=0;i<maxsize-1;i++)
- data[i].next=i+1; //先将数组置为闲链 这部分也可以在后面,但只将存放数据后的空链相连
- data[maxsize-1]=-1; //置空闲链结束标志
- for(int i=0;i<n;i++) >
- { s=avail;
- data[s].data=a[i];
- avail=data[avail].next;
- }
- data[s].next=-1;
- }