1、线性数据结构
元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的有:数组、栈、队列和线性表。
2、树形结构
结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆。
3、图形结构
在图形结构中,允许多个结点之间相关,称为“多对多”关系。
(1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的有:数组、栈、队列和线性表
(2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆
(3)图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系
1.实现求最大值的函数如下:template
<class
Type>
ListNode
<Type>
*
List
<Type>
::
Max
(
)
{
//在单链表中进行一趟检测,找出具有最大值的结点地址,
如果表空,
返回指针NULL
if
(
first->link
==
NULL
)
return
NULL
//空表,
返回指针NULL
ListNode
<Type>
*
pmax
=
first->link,
p
=
first->link->link
//假定第一个结点中数据具有最大值
while
(
p
!=
NULL
)
{
//循环,
下一个结点存在
if
(
p->data
>
pmax->data
)
pmax
=
p
//指针pmax记忆当前找到的具最大值结点
p
=
p->link
//检测下一个结点
}
return
pmax
}
2.实现从一维数组A[n]建立单链表的函数如下:
template
<class
Type>
void
List
<Type>
::
Create
(
Type
A[
],
int
n
)
{
//根据一维数组A[n]建立一个单链表,使单链表中各元素的次序与A[n]中各元素的次序相同
ListNode<Type>
*
p
first
=
p
=
new
ListNode<Type>
//创建表头结点
for
(
int
i
=
0
i
<
n
i++
)
{
p->link
=
new
ListNode<Type>
(
A[i]
)
//链入一个新结点,
值为A[i]
p
=
p->link
//指针p总指向链中最后一个结点
}
p->link
=
NULL
}
或者采用递归方法实现
template<Type>
void
List<Type>
::
create
(
Type
A[
],
int
n,
int
i,
ListNode<Type>
*&
p
)
{
//私有函数:递归调用建立单链表
if
(
i
==
n
)
p
=
NULL
else
{
p
=
new
ListNode<Type>(
A[i]
)
//建立链表的新结点
create
(
A,
n,
i+1,
p->link
)
//递归返回时p->link中放入下层p的内容
}
}
template<Type>
void
List<Type>
::
create
(
Type
A[
],
int
n
)
{
//外部调用递归过程的共用函数
first
=
current
=
new
ListNode<Type>
//建立表头结点
create
(
A,
n,
0,
first->link
)
//递归建立单链表
}
3,
实现在非递减有序的单链表中删除值相同的多余结点的函数如下:
template
<class
Type>
void
List
<Type>
::
tidyup
(
)
{
ListNode<Type>
*
p
=
first->link,
temp
//检测指针,
初始时指向链表第一个结点
while
(
p
!=
NULL
&&
p->link
!=
NULL
)
//循环检测链表
if
(
p->data
==
p->link->data
)
{
//若相邻结点所包含数据的值相等
temp
=
p->first
p->link
=
temp->link
//为删除后一个值相同的结点重新拉链
delete
temp
//删除后一个值相同的结点
}
else
p
=
p->link
//指针p进到链表下一个结点
}
参考别人的,这题目我才不会做。