/*void TheSame (LNpde &p1, ElemType x) {
if(p1->next->data != x) free(p1); else
TheSame (p1->next, x) ; } */
Status DeleteX_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值为x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {
if( NULL == L->next ) return 0; int i = 0,k;
LinkList p1,p2,p3; p1 = L; p2 = p1;
p1 = p2->next;
while(p1->next != NULL) {
if(p1->data == x) {
if(p1->next == NULL) { p2->next = NULL; free(p1) ; i++;
// p2 = p1;
// p1 = p2->next; } else {
p3 = p2;
p2->next = p1->next; free(p1);
p1 = p2->next; i++;
if(p2->data == x) {
p2 = p3;
p1 = p2->next; }
} } else {
p2 = p1;
p1 = p2->next; } }
if(p1->next == NULL&&p1->data == x) {p2->next = NULL; free(p1) ; i++; }
return i; }
//71****************************************************************** /**********
【题目】试写一算法，删除带头结点单链表中所有值 小于x的元素，并释放被删结点空间。 单链表类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; **********/
Status DeleteSome_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值小于x的元素， */ /* 并释放被删结点空间，返回实际删除的元素个数。*/ {
if( NULL == L->next ) return 0; int i = 0,k;
LinkList p1,p2,p3; p1 = L; p2 = p1;
p1 = p2->next;
while(p1->next != NULL) {
if(p1->data < x) {
if(p1->next == NULL) {
p2->next = NULL; free(p1) ; i++;
// p2 = p1;
// p1 = p2->next; } else {
p3 = p2;
p2->next = p1->next; free(p1);
p1 = p2->next; i++;
if(p2->data < x) {
p2 = p3;
p1 = p2->next; } } } else {
p2 = p1;
p1 = p2->next; } }
if(p1->next == NULL&&p1->data < x) {p2->next = NULL; free(p1) ; i++; }
return i; }
//00******************************************************************
第5章
/*03********************************************************************/
/**********
【题目】试以顺序表L的L.rcd[L.length+1]作为监视哨， 改写教材5.2节中给出的升序直接插入排序算法。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key;
... } RcdType; typedef struct {
RcdType rcd[MAXSIZE+1]; // r[0]闲置 int length; } RcdSqList; **********/
void InsertSort(RcdSqList &L) {
int i,j;
for(i = 1;i if(L.rcd[i+1].key L.rcd[L.length+1] = L.rcd[i+1]; j =i+1; do{ j--; L.rcd[j+1] = L.rcd[j]; }while(L.rcd[L.length+1].key < L.rcd[j-1].key); L.rcd[j] = L.rcd[L.length+1]; } } /*06********************************************************************/ /********** 【题目】如下所述，改写教材1.5节的冒泡排序算法： 将算法中用以起控制作用的布尔变量change改为一个整型 变量，指示每一趟排序中进行交换的最后一个记录的位置， 并以它作为下一趟起泡排序循环终止的控制值。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType; typedef struct { RcdType rcd[MAXSIZE+1]; // r[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,change,j,k; for(i = L.length,change = 0;i>1;i--) { change = i; for(j = 1;j if(GT(L.rcd[j],L.rcd[j+1])) { Swap(L.rcd[j],L.rcd[j+1]); k++; change = j+1; } } while(L.rcd[change].key == L.rcd[change-1].key) { //用while来跳过那些相同关键字 change = change - 1; } i = change; if(k == 0) i = 1; //当有一次比较没有交换时使i= 1结束操作 k=0; } } /**23*********************************************************************/ /********** 【题目】已知记录序列L.rcd[1..L.length]中的关键 字各不相同，可按如下所述实现计数排序：另设数组 c[1..n]，对每个记录a[i]， 统计序列中关键字比它 小的记录个数存于c[i]，则c[i]=0的记录必为关键字 最小的记录，然后依c[i]值的大小对序列中记录进行 重新排列。试编写算法实现上述排序方法。 顺序表的类型RcdSqList定义如下： typedef struct { KeyType key; ... } RcdType; typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; } RcdSqList; **********/