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进到链表下一个结点
}
参考别人的，这题目我才不会做。
栈先进后出，队列先进先出，队列的顺序等价于栈的出栈顺序。写了个简单的验证程序，初始的出栈顺序必须无误
#include <iostream>using std::cout
// iStack元素值有序，简化了编程，否则就要借助于下标的有序性
// 'g'作为一个额外的标记，取到此值时，表示所有元素都已入栈
char iStack[] = { 'a','b', 'c', 'd', 'e', 'f', 'g' }
char oStack[] = { 'b','d', 'f', 'e', 'c', 'a' }
int no = 1
// sp用于指示iStack未入栈的元素
int sp = 0
char Top()
{
return iStack[sp]
}
// ch及之前元素入栈
void Push(char ch)
{
char cc = Top()
while (cc <= ch)
{
printf("(%2d) Push: \t%c\n", no++, cc)
sp++
cc = Top()
}
}
void Pop(char ch)
{
if (ch >= Top()) // 当前要出栈的元素未入栈
Push(ch)
printf("(%2d) Pop: \t\t%c\n", no++, ch)
}
int main()
{
int count = 0
int len = sizeof(oStack)
//1
printf("入栈顺序：\n")
for (int i = 0 i < len i++)
printf("%c ", iStack[i])
printf("\n")
//2
printf("出栈顺序：\n")
for (int i = 0 i < len i++)
printf("%c ", oStack[i])
printf("\n\n")
//3
printf("出入栈操作：\n")
while (count < len)
{
Pop(oStack[count])
count++
}
return 0
}
