2016广工AnyView数据结构 第1-5章答案

Li->next=p->next; p->next=NULL; return OK; }

/**********

【题目】试写一算法，在带头结点单链表删除第i元素 起的所有元素。

带头结点单链表的类型定义为： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; **********/

Status Cut_L(LinkList L, int i)

/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/ /* 若参数不合理，则返回ERROR。 */ {

int count= 0;

LinkList p= L, pt;

while(p!=NULL&&count

p=p->next; //P指向第i-1号元素 count++; }

if(i<=0||p==NULL||count>i-1||p->next==NULL) {

return ERROR; //查错 }

if(i==1) {

free(L->next); L->next=NULL; return OK; }

pt=p->next; //pt指向将第i号元素 p->next=NULL; while(pt!=NULL) {

p=pt->next; free(pt); pt=p; }

return OK;

}

/**********

【题目】试写一算法，删除带头结点单链表中所有值 为x的元素，并释放被删结点空间。 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; **********/

Status DeleteX_L(LinkList L, ElemType x)

/* 删除带头结点单链表L中所有值为x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {

int count= 0;

LinkList p= L->next, pf=L, q; while(p!=NULL) { if(p->data==x) { q=p; p=p->next; free(q); pf->next=p; count++; } else {

pf=p;

p=p->next; } }

return count; }

/**********

【题目】试写一算法，删除带头结点单链表中所有值 小于x的元素，并释放被删结点空间。 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next;

} LNode, *LinkList; **********/

Status DeleteSome_L(LinkList L, ElemType x)

/* 删除带头结点单链表L中所有值小于x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {

int count= 0;

LinkList p= L->next, pf=L, q; while(p!=NULL) {

if(p->data

p=p->next; free(q); pf->next=p; count++; } else { pf=p;

p=p->next; } }

return count; }

/**********

【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨， 改写教材3.2节中给出的升序直接插入排序算法。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType;

typedef struct {

RcdType rcd[MAXSIZE+1]; // rcd[0]闲置 int length; } RcdSqList; **********/

void InsertSort(RcdSqList &L) {

int i,j;

for(i=0;i

if(L.rcd[i+1].key

L.rcd[L.length+1].key=L.rcd[i+1].key; j=i+1;

do{ j--; L.rcd[j+1].key=L.rcd[j].key;

}while(L.rcd[L.length+1].key

L.rcd[j].key=L.rcd[L.length+1].key; //L.rcd[L.length+1] 需移到左边那个数（位置为[j]），判别条件为其需大于rcd[j-1]

} //即当 L.rcd[L.length+1].key > L.rcd[j-1].key 时终止 while() }

/**********

【题目】如下所述，改写教材1.3.2节例1-10的冒泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型 变量，指示每一趟排序中进行交换的最后一个记录的位置， 并以它作为下一趟起泡排序循环终止的控制值。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType;

typedef struct {

RcdType rcd[MAXSIZE+1]; // rcd[0]闲置 int length; } RcdSqList; **********/

void BubbleSort(RcdSqList &L)

/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/ /* Status LT(RedType a, RedType b); 比较：\ */ /* Status GT(RedType a, RedType b); 比较：\ */ /* void Swap(RedType &a, RedType &b); 交换 */ {

int i = L.length-1; int change=i,j;

for(;(i>=1)&&change;i--){ change = 0; for(j=1;j<=i;j++){

if(GT(L.rcd[j],L.rcd[j+1])){ Swap(L.rcd[j],L.rcd[j+1]);