请问数据结构得老师

九阴真肝

．阅读下列算法并回答问题：
（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33(L,8)之后的L[1..8]中的元素值；
（2）简述函数f33的功能。
void f33(int R[], int n)
{
  int x=R[1];
  int low=1, high=n;
  while(low<high)
  {
while(low<high && R[high]>=0)
  high --;
if (low>high)
{
   R[low++]=R[high];
   while (low<high&& R[low]<0)
      low++;
R[high--]=R[low];
   }
  }
  R[low]=x;
}
(1)
(2)

九阴真肝

32．图的邻接矩阵表示描述如下：
#define MaxNum      20      //图的最大顶点数
typedef struct  {
  char vexs[MaxNum];       //字符类型的顶点表
  int edges[MaxNum][MaxNum];     //邻接矩阵
  int n, e;         //图的顶点数和边数
} MGraph;    //图的邻接矩阵结构描述
阅读下列算法，并回答问题：
（1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；
        
（2）简述函数f32的功能；
（3）写出函数f32的时间复杂度。
int f32(MGraph *G, int i)
{
  int d=0,j;
  for(j=0;j<G->n;j++)
  {
if (G->edges[j]) d++;
if (G->edges[j]) d++;
  }
  return d;
}
(1)
(2)
(3)

[此贴子已经被作者于2004-12-18 12:01:03编辑过]

九阴真肝

设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。 （1）写出调用f31(&S)后的S； （2）简述函数f31中第1个循环语句的功能。 void f31 (Stack *S) { Queue Q; Stack T; int i=0; InitQueue(&Q); InitStack(&T); while(!StackEmpty(S)) if ((i=!t)!=0) Push(&T,Pop(S)); else EnQueue(&Q, Pop(S)); while(!StackEmpty(&T)) Push(S,PoP(&T)); while(!QieueEmpty(&Q)) Push(S,DeQueue(&Q)); } (1) (2)

这里主要是这句：if ((i=!t)!=0) Push(&T,Pop(S));IF里边得i=!t不懂

[此贴子已经被作者于2004-12-18 12:04:58编辑过]

九阴真肝

L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L, int c)
{
  LinkList Lc,p,pre;
  pre=L;
  p=     (1)     ;
  Lc=(LinkList) malloc(sizeof(ListNode));
  Lc->next=Lc;
  while(p!=L)
if(p->data>c)
{
pre->next=p->next;
     (2)     ;
Lc->next=p;
p=pre->next;
}
else
{
pre=p;
    (3)     ;
}
  return Lc;
}
(1)
(2)
(3)

南邮人

回去想[em03]

skeleton

第一题的程序好像有点问题：

while(low<high && R[high]>=0) high --; if (low>high) // 这里应该是if(low<high)?

。。。

若如我所说，则函数f33的作用是对数组元素按照由负数到正数排序。

执行完f33(L，8)后，数组L为：{-8，-3，-2，-1，4，2，5，7}

第四题：

(1) p = L->next;

(2) p->next = Lc->next;

(3) p = p->next;

不知道对不对。。。

[此贴子已经被作者于2004-12-18 21:53:41编辑过]

九阴真肝

谢谢，哪位再给看看

小地瓜

第一题同意skeleton的说法，因为如果不修改，根据已知输入的数据，会造成死循环。

[此贴子已经被作者于2004-12-22 13:45:55编辑过]

小地瓜

第二题

（1）（没有具体的值，不知道结果）

（2）功能：计算有向图的边的数目

（3）时间复杂度 O(n)

个人看法，请指正，谢谢！

小地瓜

第三题

没看到有关 t 的定义，瞎猜一下，呵呵。

先假设一个前提：t的值不会在该函数运行的时候改变（因为函数中本身也没有修改t的值）。那么无论t为什么值，i都只是0或者1了。

情况1）t != 0 则 i=0，则通过EnQueue(&Q, Pop(S));语句将栈S的值放入队列Q，然后再从Q转入S，结果就是S中的值顺序与原来的相反了。S=(7,6,5,4,3,2,1)

情况2）t ==0 则 i=1，则通过Push(&T,Pop(S));语句将栈S的值放入栈T，然后再从T转入S，结果同原来的一样，S=(1,2,3,4,5,6,7)所以答案是：

（1）t!=0则S=(7,6,5,4,3,2,1);t=0则S=(1,2,3,4,5,6,7)

（2）第一个循环语句作用，就是选择是否倒置原栈S中的值。

以上个人看法，请指正，谢谢！

[此贴子已经被作者于2004-12-22 13:57:51编辑过]