带不带头结点的差别就是,在插入和删除操作中,不带头结点的链表需要考虑两种情况:1、插入(删除)在头结点。2、在其他位置。
6.4
//L是给定单链表,函数FindKth要返回链式表的第K个元素。如果该元素不存在,则返回ERROR。
ElementType FindKth(List L, int K)
{
int i = 0;
while (L != NULL)
{
if (i+1 == K)
return L->Data;
i++;
L=L->Next;
}
return ERROR;
}
6.5
//返回线性表中首次出现X的位置。若找不到则返回ERROR;
Position Find(List L, ElementType X)
{
while (L != NULL)
{
if (L->Data == X)
return L;
L = L->Next;
}
return ERROR;
}
//将X插入在位置P指向的结点之前,返回链表的表头。如果参数P指向非法位置,则打印“Wrong Position for Insertion”,返回ERROR;
List Insert(List L, ElementType X, Position P)
{
List node = (List)malloc(sizeof(struct LNode));
node->Data = X;
node->Next = NULL;
List q = L;
if (P == L)
{
node->Next = q;
return node;
}
while (q != NULL)
{
if (q->Next == P)
{
List temp=q->Next;
q->Next = node;
node->Next = temp;
return L;
}
q=q->Next;
}
printf("Wrong Position for Insertion\n");
return ERROR;
}
//将位置P的元素删除并返回链表的表头。若参数P指向非法位置,则打印“Wrong Position for Deletion”并返回ERROR。
List Delete(List L, Position P)
{
if (L == P)
{
L = L->Next;
return L;
}
List q = L;
while (q != NULL)
{
if(q->Next==P){
List temp=q->Next->Next;
q->Next=temp;
return L;
}
q=q->Next;
}
printf("Wrong Position for Deletion\n");
return ERROR;
}
6.6
//创建并返回一个空的线性表;
List MakeEmpty()
{
List L = (List)malloc(sizeof(struct LNode));
L->Data = NULL;
L->Next = NULL;
return L;
}
//返回线性表中首次出现X的位置。若找不到则返回ERROR;
Position Find(List L, ElementType X)
{
L = L->Next;
while (L != NULL)
{
if (L->Data == X)
return L;
L = L->Next;
}
return ERROR;
}
//将X插入在位置P指向的结点之前,返回true。如果参数P指向非法位置,则打印“Wrong Position for Insertion”,返回false;
bool Insert(List L, ElementType X, Position P)
{
List node = (List)malloc(sizeof(struct LNode));
node->Data = X;
node->Next = NULL;
List q = L;
while (q != NULL)
{
if (q->Next == P)
{
List temp = q->Next;
q->Next = node;
node->Next = temp;
return true;
}
q = q->Next;
}
printf("Wrong Position for Insertion\n");
return false;
}
//将位置P的元素删除并返回true。若参数P指向非法位置,则打印“Wrong Position for Deletion”并返回false。
bool Delete(List L, Position P)
{
List q = L;
while (q != NULL)
{
if (q->Next == P)
{
List temp = q->Next->Next;
q->Next = temp;
return true;
}
q = q->Next;
}
printf("Wrong Position for Deletion\n");
return false;
}