数据结构习题答案

4.设计一个算法，它通过一趟遍历在单链表中确定值最大的结点。 Linklist *locatmax(Linklist *L) {Linklist *p,*q;elemtype max; P=L->next;q=p;max=q->data; While(p)

{if(p->data>max) {q=p;max=q->data;} P=p->next; }

Return q; }

6.设有一个线性表L=（a1,a2,…,an），试分别在顺序表和单链表两种存储表示方式下，各设计一个将线性表L逆置的算法，要求不重新开辟存储空间。所谓逆置是指将线性表中的元素次序颠倒过来，即成为L’=(an,an-1,…,a1)。 顺序表：

#define maxlength 10 typedef int elemtype typedef struct

{elemtype list[maxlength]; int length; }sqlist;

void inverselist (sqlist *L ) {int i,j,n=L->length; elemtype t;

for(i=0;ilist[i];

{L->list[i]=L->list[n-1-i]; L->list[n-1-i]=t; }

单链表：

Status(Linklist *L) {Linklist *p,*q;

P=L->next;L->next=null; While(p)

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

12.设有一个单循环链表，其表长大于1且表中既无表头结点又无表头指针。已

知P为指向表中某结点的指针，试编写在该循环链表中删除指针P所指指点的前驱结点的算法。

Status Deleteprior(Linklist *P) {Linklist *s; if(p->next==p) {free(p);P=null;}

for(s=p;s->next->next!=p;s=s->next) q=s->next; s->next=p; free(q); return OK; }

22.试写一个算法，它借助栈逆置一个单链表。 Void reverse (Linklist *L) {Linklist *p=L->next; liststack s; Initstack (&s); While(p)

{push (&s,p->data);p=p->next;} P=L->next;

while(stackempty(s)==o) {pop(s,e);p->data=e; P=p->data;} }

23.试写一个算法，它借助栈判断一个算法表达式中的圆括号是否配对。 int match (char *p) {int i;Linkstack s; Initstack (&s);

for(i=0;i{if(p[i]==’(’)push(&s,p[i]); if(p[i]==’)’)

if(!stackempty(s))pop(&s); else return o;}

if (stackempty(s))return 1 ; else return 0;}

27.假设用一个单循环链表来实现对列（称作循环链队列），该队列只设一个队尾指针而不设队头指针，请设计该循环链队列的插入和删除算法。 typedef int elemtype; typedef struct node {elemtype data; struct node *next;

}Linknode;

typedef struct {Linknode *rear; }Linkqueue; Linkqueue *q;

void insertqueue (Linkqueue *q,elemtype x) {Linknode *p;

p=(linknode*)molloc(sizeof(Linknode)); p->data=x;

p->next=q->rear->next; q->rear->next=p; q->rear=p;}

status Deletnode (Linkqueue *q) {if (q->rear->next==q->rear) return error;

p=q->rear->next->next; if(p!=q->rear)

{q->rear->next=p->next; free(p);}

else{s=q->rear->next; q=rear->next=p->next; free(p);q=rear=s;} return OK;}