说明
- 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
- 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
- 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。
2.18 试写一算法
在无头结点的动态单链表上实现线性表操作DELETE(L,i)，
并和在带头结点的动态单链表上实现相同操作的算法进行比较。
解：
注意涉及空表和首元结点的操作。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;#define MAX_TEST_LENGTH 20
#define MAX_TEST_ELEM 1000
typedef int ElemType;typedef struct SLNode{ // 结点类型ElemType data;struct LNode *next;
} LNode, *Link, *LinkedList;Status MakeNode(Link *pp,ElemType e){// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR*pp=(Link)malloc(sizeof(LNode));if(!*pp) return ERROR;(*pp)->data=e;(*pp)->next=NULL;return OK;
}void FreeNode(Link p){// 释放p所指结点if(NULL!=p){free(p);}
}Status DestroyClearedList(LinkedList *pL){// 将线性表L重置为空表，并释放无头结点原链表的结点空间Link p;if(NULL==pL) return ERROR;p=*pL;while(p){*pL=p->next;//printf("free [%lld]=%d\n",(long long)p,p->data);FreeNode(p);p=*pL;}*pL=NULL;return OK;
}void print_list(LinkedList L){// 显示无头结点链表的内容int c=0;while(L){printf("->[%d].%d",c++,L->data);L=L->next;}printf("\n");
}int ListLen(LinkedList L){// 计算无头结点链表长int c=0;while(L){++c;L=L->next;}return c;
}Status InsFirst(LinkedList *pL,Link s){// 已知线性链表的头指针，将s所指结点链接成新的首元if(NULL==pL||NULL==s) return ERROR;s->next=*pL;*pL=s;return OK;
}Status DELETE(LinkedList *pL,int i){//在无头结点链表L中删除第i个元素Link p,q;if(NULL==pL||i<1) return INFEASIBLE;// 保证i值大于等于1才处理，并且链表长度达不到i无法删除// 本应该事先遍历无头结点的链表找到表长，以限制无法删除的可能// 但事实上可以先假设i值符合要求，并可以在查找第i个元素过程中积累一部分对表长的计算，// 如果表长相对i很短，表尾为空先于i减为0结束循环，在计算出表长的同时也可以免于删除，// 此时已发现删除不可能并结束任务，于是在删除操作中就不需要表长了，// 还要考虑i在表长范围内已完成删除任务之后，此时也没有必要返回删除后的新表长，// 虽然仍有剩余表尾没有计算，但已经失去了计算表长的意义，因为表长可能非常长以致没有计算的必要if(i==1){ // 删除第一个元素*pL=(*pL)->next;}else{ // 找到欲删结点的前驱，当i==2时，从首元开始，不用移动指针就可找到p=*pL;i-=2; // i>=2保证i-=2后i>=0以下i--在首次使用其值时不可能为负值while(p&&i--) p=p->next;if(p&&p->next){// 由于事先对i进行了处理，p不可能指向表中最后元素？不是的，// i==3时，若表长只有2，i==1进入循环，i--，下次循环被i==0结束前p指向表尾，// 此时在表长>=3时才可以在循环结束后正确删除第三个元素，// 而由于i主导了循环的结束，此时表长不仅不能计算出来，竟然还不知道作为前驱后面已经没有可删的元素// 由于这种情况尚有一个特征即NULL!=p && NULL==p->next，// 所以可以选择当p其实是一个前驱的时候，p&&p->next才进行删除，其余情况返回不可删的出错提示// 注意删除之后，一定记得释放被删的结点q=p->next;p->next=q->next;FreeNode(q);}else return ERROR;}return OK;
}//DELETEStatus rand_test_list_delete(LinkedList *pL){// 在测试范围内，随机初始化无头结点链表int i,len,c;Status result;Link p;time_t t;srand((unsigned)time(&t)); // 初始化随机数发生器c=rand()%MAX_TEST_LENGTH;while(c--){p=NULL;if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;if(ERROR==InsFirst(pL,p)) return ERROR;}print_list(*pL);len=ListLen(*pL);while(len>0){printf("Delete the i(th)(i>=1) element:");scanf("%d",&i);result=DELETE(pL,i);if(result==OK){printf("\nDelete success, after delete:\n");print_list(*pL);}else if(result==ERROR){printf("\nERROR (pos %d) greater than (%d(len of list))\n",i,len);return result;}else{printf("\nDo not support...\n");return result;}len=ListLen(*pL);}return OK;
}int main(){LinkedList La;La=NULL;if(OK==rand_test_list_delete(&La))printf("Any more?\n");if(OK==DestroyClearedList(&La)) printf("Free La success\n");return 0;
}
如果在带头结点的动态单链表上实现相同操作，头部无需做特殊处理，注意对表长和表尾指向的维护。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;#define MAX_TEST_LENGTH 20
#define MAX_TEST_ELEM 1000
typedef int ElemType;typedef struct SLNode{ // 结点类型ElemType data;struct LNode *next;
} LNode, *Link;typedef struct{ // 链表类型Link head,tail; // 分别指向线性链表中的头结点和最后一个结点int len; // 指示线性链表中数据元素的个数
} LinkList;Status MakeNode(Link *pp,ElemType e){// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR*pp=(Link)malloc(sizeof(LNode));if(!*pp) return ERROR;(*pp)->data=e;(*pp)->next=NULL;return OK;
}void FreeNode(Link p){// 释放p所指结点if(NULL!=p){//printf("\nvalue of adddress:%lld\n",(long long)p);free(p);}
}Status InitList(LinkList *pL){// 构造一个空的线性链表LLink p;if(ERROR==MakeNode(&p,0)) return ERROR;(*pL).head=p;(*pL).tail=NULL;(*pL).len=0;return OK;
}Status ClearList(LinkList *pL){// 将线性表L重置为空表，并释放原链表的结点空间Link p;if(NULL==pL) return ERROR;if(NULL!=(*pL).head) p=((*pL).head)->next;while(p){((*pL).head)->next=p->next;printf("free [%lld]=%d\n",(long long)p,p->data);FreeNode(p);p=((*pL).head)->next;}(*pL).tail=NULL;(*pL).len=0;return OK;
}Status DestroyList(LinkList *pL){// 销毁线性链表Lif(ERROR==ClearList(pL)) return ERROR;if(NULL!=(*pL).head) FreeNode((*pL).head);(*pL).head=NULL;return OK;
}void print_list(LinkList L){// 显示链表的内容int c=0;Link p=(L.head)->next;while(p){printf("->[%d].%d",++c,p->data);p=p->next;}printf("\n%d elements\n",L.len);
}Status InsFirst(LinkList *pL,Link s){// 已知线性链表的头结点，将s所指结点插入到第一个结点之前// 线性链表的尾指针没有变化，线性链表的元素个数加1Link p;if(NULL==pL||NULL==s) return ERROR;p=(*pL).head;s->next=p->next;if(NULL==p->next) (*pL).tail=s; // 插入前链表为空时，记录表尾p->next=s;(*pL).len+=1;return OK;
}Status InsLast(LinkList *pL,Link s){// 已知线性链表的尾结点，将s所指结点插入到最后结点之后// 尾指针发生变化，若非空，线性链表的头结点指针域没有变化，线性链表的元素个数加1// 注意这里提供s的时候，需要先从较短链表中复制一份再传进来if(NULL==pL||NULL==s) return ERROR;if(NULL==pL->head->next){pL->head->next=s;}else{pL->tail->next=s;}pL->tail=s;pL->len+=1;return OK;
}//InsLastStatus DELETE(LinkList *pL,int i){Link p,q;if(NULL==pL||i<1||i>pL->len) return INFEASIBLE;p=pL->head;i-=1; // i>=1时i-=1后，i>=0while(p&&i--) p=p->next;if(p&&p->next){q=p->next;p->next=q->next;FreeNode(q);if(NULL==p->next) pL->tail=p; //testing(pL->len)--;}else return ERROR; //testingreturn OK;
}Status rand_test_delete(LinkList *pL){Status result;// 在测试范围内，随机初始化链表int i,c;Link p;time_t t;if(ERROR==InitList(pL)) return ERROR;srand((unsigned)time(&t)); // 初始化随机数发生器c=rand()%MAX_TEST_LENGTH;while(c--){p=NULL;if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;if(ERROR==InsFirst(pL,p)) return ERROR;}print_list(*pL);while(pL->len>0){printf("Delete the i(th)(i>=1) element:");scanf("%d",&i);result=DELETE(pL,i);if(result==OK){printf("\nDelete success, after delete:\n");print_list(*pL);}else if(result==ERROR){printf("\nERROR or can not be reached\n");return result;}else{printf("\nDo not support...\n");return result;}}return OK;
}int main(){LinkList La;if(OK==rand_test_delete(&La))printf("Any more?\n");// 注意，这里的重要改动，// 上一篇文章由于测试有误事先返回，而无法释放的情况必须考虑if(OK==DestroyList(&La)) printf("\nFree La success\n");return 0;
}
这里必须强调的是，上一篇文章由于测试有误事先返回，而无法释放的情况必须考虑，
定义有头结点的单链表和销毁单链表应该统一拿到main函数中处理，防止出错处理事先返回后，不能释放动态开辟的空间。