讨论小课堂和习题解答

{int i=0;Lnode *p;

P=L->next;

While(p&&p->dada!=x){i++;p=p->next;} If(!p)return 0; Else return I;

}

7．写一个算法将一单链表逆置。要求操作在原链表上进行。 答：void reverse (LinkList L) { p=L->next; L->next=NULL; while (p)

{ q=p->next; p->next=L->next; L->next=p; p=q; }

}

8．在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法。 答：void insert_x(Linklist L,Datatype x)

/*在递增有序的单链表L中插入值为x的元素，使得插入后L仍然有序*/ {Lnode *p,*q,*r; P=L;q=p->next;

While(q&&q->dada<=x) {p=q;q=q->next;}

R=(Lnode *)malloc(Lnode); r->dada=x; r->next=q; p->next=r;

}

9．写一算法将值为B的结点插在链表中值为a的结点之后。如果值为a的结点不存在，则插在表尾。

答: void Insert_LinkList( LinkList L, DataType a, DataType B)

{ /* 在值为a 的结点后插入值为B的结点，表中若无a则B接在表尾 */ LinkList p,q,s ;

s=( LinkList)malloc(sizeof(struct node)); s->data=B; s->next=NULL; q=L; p=L->next;

while( p!=NULL && p->data!=a ) { q=p; p=p->next; } if(p){s->next=p->next;p->next=s;} }

else{ s->next=q->next;q->next=s;}

10．试用循环链表为存储结构，写一个约瑟夫(Josephu)问题的算法。约瑟夫问题是：有N个人围成一圈，从第i个人开始从1报数，数到m时，此人就出列。下一个人重新从1开始报数，再数到m时，以一个人出列。直到所有的人全部出列。按出列的先后得到一个新的序列。例如，N=5， i=1, m=3 时新的序列应为：3, 1, 5, 2, 4。 答：

typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ struct node *next; /* 指针域 */ }JOS;

void outs(JOS *h, int m) { int i; JOS *q=h, *p;

printf(―\\n ―);

while (q->next!=q)

{ for(i=1;inext;} /* 报数到第m个人 */ printf(―m‖,q->num); /* 输出第m个人的编号 */ p->next=q->next; free(q); /* 第m个人出列 */ q=p->next; }

printf(―m \\n‖,q->num); /* 输出最后一个结点的编号值 */ free(q);

} /* outs */

11. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。 答：void unit(Linklist A,Linklist B,Linklist C) {Lnode *p,*q,*r,*s;

P=A->next;q=>next;C=A;r=C; While(p&&q)

{if(p->dada<=q->dada){r=p;p=p->next;}

Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;}

}

If(!p)r->next=q;free(B) }

讨论小课堂 3

【参考内容】

1. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。

2. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？

【答案】

1、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

3. 简述顺序存储队列的“假溢出”现象的避免方法及怎样判定队列满和空的条件。 【答案】：

3、设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。

4.假设有如下图所示的列车调度系统，约定两侧铁道均为单向行驶，入口处有N节硬席或软席车厢（程序中可分别用H和S表示）等待调度，试编写算法，输出对这N节车厢进行调度的操作序列，要求所有的软席车厢被调整到硬席车厢之前。

? 【参考答案】： ? void trains(char *elem) ? {int i,k; ? k=0;

? for(i=0;i

? if(elem[i]==‘S’) //软席车厢S ? { push(); ? pop(); ? } ? else ? {push();

? k++}

? while(k>0){pop();k--;} ? }

5.对于一个具有N个单元（N>>2）的循环队列，若从进入第一个元素开始每隔T1个时间单位进入下一个元素，同时从进入第一个元素开始，每隔T2（T2>T1）个时间单位处理完一个元素并令其出队，试编写一个算法，求出在第几个元素进队时将发生溢出。

? 【分析】

? 时刻t: 0 1 2 3 4 5 6 7 8 9 ? 个数： 1 1 2 1 2 2 3-2 2 3 2 ? 放取： + + - + + - + -

? 时刻t: 10 11 12 13 ? 个数： 3 3 4-3 …… ? 放取： + + - …… ?

? N=2

? 先放后取： 6时刻，放了4次，3个为溢出 ? 放取同时： 8时刻，放了5次，3个为溢出

如果同一时刻先放后取： int main( )

{ int y=1,i=0, n, m, front=0,rear=1; cin>>n; cin>>t1;cin>>t2; m=n+2; if (t1>=t2) cout<<\ else{

while((rear+1)%m!=front) { i++;

if (i%t1==0) {rear=(rear+1 )%m; y++; } if (i%t1==0&&(rear+1)%m==front) break; if (i%t2==0) {front=(front+1 )%m; } }

cout<

习题3

1.假定有编号为A、B、C、D的四辆列车，自右向左顺序开进一个栈式结构的站台，

如图3.16所示。可以通过栈来编组然后开出站台。请写出列车开出站台的顺序有几种？写出每一种可能的序列。如果有n辆列车进行编组呢？如何编程？

注：每一辆列车由站台向左开出时，均可进栈、出栈开出站台，但不允许出栈后回退。