六、算法设计题 1. 假设以带头结点的单链表表示线性表,单链表的类型定义如下: typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 编写算法,删除线性表中最小元素(假设最小值唯一存在)。 2. 试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w) ,即删除一条边的操作。
时间: 2024-03-21 07:39:59 浏览: 27
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。