数据结构 用C语言描述 课后答案(2)

第二章 线性表

课堂习题

1、在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？若可以，其时间复杂度各为多少？

【解答】

在单链表中，由于无法找到结点*P的直接前驱的位置，所以无法删除该结点； 在双链表中，结点*P的前驱位置是P->PRIOR；因此可直接将*P删除掉，其时间复杂度为O(1);

在单循环链表中,可从P结点依次扫描到其前驱结点,故也能删除掉该结点,其时间复杂度为O(N)。

2、下述算法的功能是什么？

LINKLIST DEMO(LINKLIST L)其中L为带头指针的单链表 { LISTNODE *Q，*P； IF (L&&L->NEXT) {

Q=L;L=L->NEXT;P=L;

WHILE(P->NEXT) P=P->NEXT; P->NEXT=Q;Q->NEXT=NULL; }

RETURN L }

【解答】

当L是空链表或仅有一个结点时，L不变；

当L有两个或两个以上结点时，将第一个结点移至链表最后，关指针指向原第二个结点。

3、试分别用顺序表和单链表作为存储结构，实现线性表的就地逆置。

【解答】

顺序表 VOID REVERSELIST(SQLIST *L) {DATATYPE T; INT I,J;

FOR(I=0;I<=L->LENGTH/2-1;I++) {J=L->LENGTH-1-I;

T=L->ELEM[I];

L->ELEM[I]=L->ELEM[J]; L->ELEM[J]=T; } }

单链表 VOID REVERSELIST(LINKLIST *L) {LNODE *P,*Q; P=L->NEXT;

L->NEXT=NULL; WHILE(P)

{Q=P->NEXT;

P->NEXT=L->NEXT; L->NEXT=P; P=Q; } }

4、设顺序表L是一个递增有序表，试写一算法将X插入到L中，并使得L仍是一个有序表。

【解答】

VOID INSERTSOR(SQLIST *L,DATATYPE X) {INT I;

IF (L->LENGTH>=LISTSIZE) RETURN ERROR; I=L->LENGTH-1;

WHILE(I>=0&&L->DATA[I]>X) {L->ELEM[I+1]=L->ELEM[I];I--;} L->ELEM[I+1]=X; L->LENGTH++; }

5、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为M和N，试写一算法将两个链表连接在一起，请分析算法的时间复杂度。

【解答】

LINKLIST CONNECT(LINKLIST L1,LINKLIST L2,INT M,INT N) {LISTNODE *P,*Q; INT K; IF(M>N)

{K=N;P=L2;Q=L1;} ELSE

{K=M;P=L2;Q=L2;} WHILE(K>0)

{P=P->NEXT;K--;} P->NEXT=Q->NEXT; FREE(Q);

IF (M>N) RETURN L2; ELSE RETURN L1; }

6、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值各不相同。

【解答】

VOID DELSAMENODE(LINKLIST L) {LISTNODE *P,*Q,*R; P=L->NEXT; WHILE(P) {Q=P;

R=Q->NEXT; WHILE(R)

{IF R->DATA==P->DATA

{Q->NEXT=R->NEXT;R=Q->NEXT;} ELSE

{Q=R;R=R->NEXT;} }

P=P->NEXT; } }

7、假设在长度大于1的单循环链表中，既无头结点也无头指针，S为指向表中某个结点的指针，试编写算法删除结点*S的直接前驱结点。

【解答】

VOID DELETEFNODE(LISTNODE *S) {LISTNODE *P,*Q; P=S;

WHILE(P->NEXT!=S) {Q=P;P=P->NEXT;} Q->NEXT=S; FREE(P);

}

8、狐狸逮兔子问题

围绕着山顶有10个圆形排列的洞,狐狸要吃兔子,兔子说:\可以,但必须找到我,我就藏身于这10个洞中,你先到1号洞找,第二次隔1个洞,(即3号洞)找,第三次就隔2个洞(即6号洞找),以后如此类推,次数不限.\但狐狸从早到晚进进出出了1000次,仍没有找到兔子,问兔子究竟藏在哪个洞里?

【解答】

#include \#include \#define OK 1

#define OVERFLOW -2

#define LIST_INIT_SIZE 10 typedef int status; typedef int elemtype; typedef struct

{ elemtype *elem; int length; int listsize; } sqlist;

status initlist_sq(sqlist *l) {

l->elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype)); if(!(l->elem)) return OVERFLOW; l->length=0;

l->listsize=LIST_INIT_SIZE; return OK; }

status rabbit(sqlist *l) {

int i,current=0;

for(i=0;ielem[i]=1; l->elem[0]=0;

for(i=2;i<=1000;i++) {

current=(current+i)%LIST_INIT_SIZE; l->elem[current]=0; }

printf(\

for (i=0;i

if(l->elem[i]==1) printf(\ \ return OK; }

main() {

sqlist l;

initlist_sq(&l); rabbit(&l); getch(); }

9、约瑟夫问题

设有N个人围坐在圆桌周围,现从某个位置M(1<=M<=N)上的人开始报数,报数到K的人就站出来,下一个人,即原来的第K+1个位置上的人,又从1开始报数,再报到K的人站出来,依此重复下去,直到全部的人都站出来为止.试设计一个程序求出出列的序列.

【解答】

#include \#include \#define NULL 0 #define OK 1 #define ERROR 0 #define overflow -2 typedef int status; typedef int elemtype; typedef struct cnode {

elemtype data; struct cnode *next; } cnode; cnode *joseph;

status create_clist(cnode *clist,int n) {

cnode *p,*q; int i;

clist=null;

for (i=n;i>=1;i--)