说明
- 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
- 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
- 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。
2.17 试写一算法
在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，
并和在带头结点的动态单链表上实现相同操作的算法进行比较。
解：
注意涉及空表和首元结点的操作。
#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 INSERT(LinkedList *pL,int i,Link b){// 在无头结点链表L的第i个元素之前插入元素bLink p;// 若要初始化链表，用其他函数来完成if(NULL==pL||NULL==b||i<1) return INFEASIBLE;// 保证i值大于等于1才处理，并且链表长度在i>1时如果少于i-1也不可插入if(i==1){b->next=*pL;*pL=b; //插入到链表头部}else{p=*pL;i--;while(p&&--i) p=p->next;if(p){b->next=p->next;p->next=b; //插入到第i个位置}else return ERROR; //当链表元素个数少于i-1}return OK;
}Status rand_test_list_insert(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);if(len>0){p=NULL;if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;printf("Insert rand %d before i(i>=1):",p->data);scanf("%d",&i);result=INSERT(pL,i,p);if(result==OK){printf("\nInsert success, after insert:\n");print_list(*pL);}else if(result==ERROR){printf("\nERROR (pos %d) greater than (1 + %d(len of list))\n",i,len);return result;}else{printf("\nDo not support...\n");return result;}}return OK;
}int main(){LinkedList La;La=NULL;if(OK==rand_test_list_insert(&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 INSERT(LinkList *pL,int i,Link b){// 在有头结点的链表L的第i个元素之前插入元素bLink p;// 若要初始化链表，用其他函数来完成if(NULL==pL||NULL==b||i<1) return INFEASIBLE;// 保证i值大于等于1才处理，并且链表长度在i>1时如果少于i-1也不可插入// 由于有头结点，不必单独考虑当i==1时插入到首元前的情况p=pL->head;while(p&&--i) p=p->next;if(p){b->next=p->next;p->next=b; //插入到第i个位置if(!i) pL->tail=b;(pL->len)++;}else return ERROR; //当链表元素个数少于i-1return OK;
}Status rand_test_insert(){LinkList La;Status result;// 在测试范围内，随机初始化链表int i,c;Link p;time_t t;if(ERROR==InitList(&La)) 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(&La,p)) return ERROR;}print_list(La);if(La.len>0){p=NULL;if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;printf("Insert rand %d before i(i>=1):",p->data);scanf("%d",&i);result=INSERT(&La,i,p);if(result==OK){printf("\nInsert success, after insert:\n");print_list(La);}else if(result==ERROR){printf("\nERROR (pos %d) greater than (1 + %d(len of list))\n",i,La.len);return result;}else{printf("\nDo not support...\n");return result;}}if(OK==DestroyList(&La)) printf("\nFree La success\n");return OK;
}int main(){rand_test_insert();return 0;
}
