数据结构—算法——期末考查.doc

1、链表
统计结点数
算法
int ListLength_L( LinkList L )
{
// L 为链表的头指针,本函数返回 L 所指链表的长度
p=L; k=0;
while ( p ) {
k++; p=p->next; // k 计非空结点数
}//while
return k;
} // ListLength_L
查找
算法
LNode* LocateElem_L( LinkList L, ElemType e )
{
// 在 L 所指的链表中查找第一个值和 e 相等的数据元素,若存在,则返回
// 它在链表中的位置,即指向该数据元素所在结点的指针;否则返回 NULL
p=L;
while ( p && p->data != e ) p=p->next;
return p;
} // LocateElem_L
插入
算法
void ListInsert_L( LinkList &L, Lnode* p, Lnode* s )
{
// 指针 p 指向 L 为头指针的链表中某个结点,将 s 结点插入到 p 结点之前
if (p == L) { // 将 s 结点插入在链表的第一个结点之前
s->next = L; L = s;
}//if
else {
q = L;
while (q->next != p ) q = q->next; // 查找 p 的前驱结点 q
q->next = s; s->next = p; // 在链表中 q 结点之后插入 s 结点
}//else
} // ListInsert_L
删除
算法
void ListDelete_L( LinkList &L, Lnode* p, ElemType &e ) {
// p指向L为头指针的链表中某个结点,从链表中删除该结点并由e返回其元素
if (p == L) { // 删除链表中第一个结点,修改链表头指针
L = p->next;
}//if
else {
q = L;
while (q->next != p ) q = q->next; // 查找 p 的前驱结点 q
q->next = p->next ; // 修改 q 结点的指针域
}//else
e = p->data; delete p; // 返回被删结点的数据元素,并释放结点空间
}// ListDelete_L
2、顺序表
创建
算法
void InitList_Sq( SqList &L, int maxsize = LIST_INIT_SIZE,
int incresize = LISTINCREMENT )
{
// 构造一个最大容量为 maxsize 的顺序表 L
= new ElemType [maxsize];
// 为顺序表分配一个最大容量为 maxsize 的数组空间
= 0; // 顺序表中当前所含元素个数为 0
= maxsize; // 该顺序表可以容纳 maxsize 个数