数据结构作业答案

第二章

3. 头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 5.

#define OK 1

#define ERROR 0

Int LDel(Seqlist *L,int i,int k) { int j;

if(i<1||(i+k)>(L->last+2))

{ printf(“输入的i，k值不合法”); return ERROR; }

if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else

{for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } }

7.（1）void reverse(SeqList L)

{

int i,j,tmp;

for(i=0, j=L.last; i

tmp=a[i]; a[i]=a[j]; a[j]=tmp; } }

(2) void reverse(LinkList L)//原地置换

{

LinkList old_head, new_head, temp;

new_head =NULL; old_head=L-> next;

while ( old_head ) {

temp= old_head-> next; old_head-> next= new_head; new_head= old_head; old_head= temp; }

L-> next= new_head; return( L ) }

8.

#include\#include\ struct list

{

int data;

struct list *next; };

void unionlist() {

struct list *head,*p;

int i=0;

p1=head1; p2=head2;

head=p=(struct list*)malloc(sizeof(struct list)); p->data=0; while(p1 && p2) {

if(p1->data<=p2->data) {

p->next=p1; p=p1; p1=p1->next; } else

{

p->next=p2; p=p2; p2=p2->next; }

}

p->next=p1?p1:p2; free(head1); free(head2); }

12. typedef struct node

{ int power; ∥幂

float coef; ∥系数 ElemType other; ∥其他信息 struct node *next; ∥指向后继的指针 } PNode,*PolyLinkedList; void PolyDis(PolyLinkedList poly)

∥将poly表示的多项式链表分解为各含奇次幂或偶次幂项的两个循环链表 { PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode)); ∥poly2表示只含奇次幂的多项式

r2=poly2; ∥r2是只含奇次幂的多项式链表的尾指针

r1=poly; ∥r1是只含偶次幂的多项式链表当前结点的前驱结点的指针 p=poly->next; ∥链表带头结点，p指向第一个元素 while(p!=poly)

if(p->power % 2)∥处理奇次幂 { r=p->next; ∥暂存后继

r2->next=p; ∥结点链入奇次幂链表

r2=p; ∥尾指针后移

p=r; ∥恢复当前待处理结点 }

else ∥处理偶次幂

{ r1->next=p; r1=p; p=p->next; }

r->next=poly2; r1->next=poly; ∥构成循环链表 }∥PolyDis

13. void BinAdd( LinkList L ) {

Node *q, *r, *temp, *s ; q = L->next; r=L; while( q!=NULL )

{ if ( q->data ==0) r=q; q = q-> next; } if ( r! =L) r->data=1; else {

temp= r-> next; s=( Node*) malloc( sizeof( Node)); s->data=1; s-> next= temp; r-> next=s; r=s; }

r= r-> next;

while( r!=NULL )

{ r->data=0; r= r-> next; }

}

第三章

3. 栈有顺序栈和链栈两种存储结构。

在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。 在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。 5. #include

#include #include #define OK 1

#define ERROR 0

#define OVERFLOW 0 typedef struct N0de { int data;

struct N0de *next; } N0de,*QueuePtr;

typedef struct { QueuePtr rear; } LinkQueue;

int InintQueue(LinkQueue &Q)

{ Q.rear=(QueuePtr)malloc(sizeof(N0de)); if(!Q.rear) return(OVERFLOW); Q.rear->next=Q.rear; return OK; }

int EnQueue(LinkQueue &Q,int e) { QueuePtr p;

p=(QueuePtr)malloc(sizeof(N0de)); p->data=e;

p->next=Q.rear->next; Q.rear->next=p; Q.rear=p;