就只给出算法了:
//在用邻接表方式存储的无向图g中,删除边(i,j)
{p=g[i].firstarc
pre=null
//删顶点i
的边结点(i,j),pre是前驱指针
while
(p)
if
(p->adjvex==j)
{if(pre==null)g[i].firstarc=p->nextelse
pre->next=p->nextfree(p)}//释放结点空间。
else
{pre=p
p=p->next}
//沿链表继续查找
p=g[j].firstarc
pre=null
//删顶点j
的边结点(j,i)
while
(p)
if
(p->adjvex==i)
{if(pre==null)g[j].firstarc=p->nextelse
pre->next=p->nextfree(p)}//释放结点空间。
else
{pre=p
p=p->next}
//沿链表继续查找
}//
DeletEdge
算法讨论:
算法中假定给的i,j
均存在,否则应检查其合法性。若未给顶点编号,而给出顶点信息,则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
栈先进后出,队列先进先出,队列的顺序等价于栈的出栈顺序。写了个简单的验证程序,初始的出栈顺序必须无误
#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
}