13. (编程题) 带头结点的单链表的结点定义为： typedef int DataType; typedef struct Node { DataType data; struct Node* next; }Node; 函数int Locate(Node *first,DataType x)的功能是查找单链表中值为x的结点的序号，并返回此序号,找不到，返回0。 int Locate(Node *first,DataType x) { Node *p = fi

函数实现部分缺失，以下是函数的完整实现：

int Locate(Node *first, DataType x)
{
    Node *p = first->next;
    int i = 1;  //结点序号从1开始
    while(p != NULL)
    {
        if(p->data == x)
        {
            return i;  //找到结点，返回其序号
        }
        p = p->next;
        i++;
    }
    return 0;  //未找到结点，返回0
}

该函数的实现比较简单，使用一个指针 p 遍历链表，查找值为 x 的结点。如果找到了该结点，则返回其序号（从1开始），否则继续遍历。需要注意的是，该链表带头结点，因此第一个结点实际上是头结点的下一个结点，所以在遍历链表时需要从 first->next 开始。

相关问题

六、算法设计题 1. 假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 编写算法，删除线性表中最小元素(假设最小值唯一存在)。 2. 试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。

1. 删除线性表中最小元素的算法实现如下：

void deleteMin(LinkList &L) {
    LinkNode *p = L->next, *pre = L, *minp = p, *minpre = pre;
    while (p != NULL) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    delete minp;
}

算法思路：使用两个指针分别指向当前最小值和最小值的前驱节点，遍历链表找到最小值，然后删除最小值节点。

2. 邻接矩阵存储结构上实现删除一条边操作的算法实现如下：

void deleteArc(MatrixGraph &G, int v, int w) {
    if (v < 0 || v >= G.vexNum || w < 0 || w >= G.vexNum) {
        return;
    }
    if (G.arcs[v][w] != 0) {
        G.arcs[v][w] = 0;
        G.arcNum--;
    }
    if (G.kind == UDG || G.kind == UDN) {
        G.arcs[w][v] = 0;
        G.arcNum--;
    }
}

算法思路：先判断待删除边的两个顶点是否合法，再判断该边是否存在。如果存在，则将该边的权值置为0，同时图的边数减1。对于无向图和带权图，还需要将对称位置的值也置为0。

用c语言的伪代码假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ DataType data; struct node *next }LinkNode, *LinkList; 编写算法，将有序表A和有序表B归并为新的有序表C。

算法如下：

1. 初始化指针pA和pB分别指向有序表A和B的第一个结点，指针pC指向新的有序表C的头结点。

2. 如果pA和pB都不为空，则比较pA和pB结点中的数据大小，将较小的结点插入到新的有序表C中，并将指针pC指向新插入的结点。

3. 如果pA为空，则将pB剩余的结点插入到新的有序表C中。

4. 如果pB为空，则将pA剩余的结点插入到新的有序表C中。

5. 返回新的有序表C的头结点。

伪代码如下：

LinkList MergeList(LinkList A, LinkList B)
{
LinkList C = (LinkList)malloc(sizeof(LinkNode)); // 新的有序表C的头结点
LinkList pA = A->next, pB = B->next, pC = C; // 初始化指针

while(pA && pB)
{
if(pA->data <= pB->data)
{
pC->next = pA;
pA = pA->next;
}
else
{
pC->next = pB;
pB = pB->next;
}
pC = pC->next;
}

if(pA)
pC->next = pA;
else
pC->next = pB;

return C;
}