本文针对数据结构基础系列网络课程(2)：线性表的实践项目。
【项目 – 单链表算法】（程序中利用了已经实现的单链表算法，头文件LinkList.h及其中函数的实现见单链表算法库）
1、设计一个算法，，将一个带头结点的数据域依次为a1，a2，…，an（n≥3）的单链表的所有结点逆置，即第一个结点的数据域变为an，…，最后一个结点的数据域为a1。实现这个算法，并完成测试。 [参考解答] （程序中利用了已经实现的单链表算法，头文件LinkList.h及其中函数的实现见单链表算法库）
void Reverse(LinkList *&L){LinkList *p=L->next,*q;L->next=NULL;while (p!=NULL)//扫描所有的结点{q=p->next;//让q指向*p结点的下一个结点p->next=L->next; //总是将*p结点作为第一个数据结点L->next=p;p=q;//让p指向下一个结点}}int main(){LinkList *L;ElemType a[]= {1,3,5,7, 2,4,8,10};CreateListR(L,a,8);printf(“L:”);DispList(L);Reverse(L);printf(“逆置后L： “);DispList(L);DestroyList(L);return 0;}
2、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m、n，请设计算法将L2连接到L1的后面。实现这个算法，完成测试，并分析这个算法的复杂度。 [参考解答] （程序中利用了已经实现的单链表算法，头文件LinkList.h及其中函数的实现见单链表算法库）
void Link(LinkList *&L1, LinkList *&L2){LinkList *p = L1;while(p->next != NULL) //找到L1的尾节点p = p->next;p->next = L2->next; //将L2的首个数据节点连接到L1的尾节点后free(L2); //释放掉已经无用的L2的头节点}int main(){LinkList *A, *B;int i;ElemType a[]= {1,3,2,9};ElemType b[]= {0,4,7,6,5,8};InitList(A);for(i=3; i>=0; i–)ListInsert(A, 1, a[i]);InitList(B);for(i=5; i>=0; i–)ListInsert(B, 1, b[i]);Link(A, B);printf(“A:”);DispList(A);DestroyList(A);return 0;}
算法复杂度为O(m)，只需要由L1的头节点找到其尾节点即可，与L1的长度相关，与L2的长度n无关。
3、设计一个算法，判断单链表L是否是递增的。实现这个算法，并完成测试。 [参考解答] （程序中利用了已经实现的单链表算法，头文件LinkList.h及其中函数的实现见单链表算法库）
bool increase(LinkList *L){LinkList *p = L->next, *q; //p指向第1个数据节点if(p != NULL){while(p->next != NULL){q = p->next; //q是p的后继if (q->data > p->data) //只要是递增的，就继续考察其后继p = q;elsereturn false; //只要有一个不是后继大于前驱，便不是递增}}return true;}int main(){LinkList *A, *B;int i;ElemType a[]= {1, 3, 2, 9};ElemType b[]= {0, 4, 5 ,6, 7, 8};InitList(A);for(i=3; i>=0; i–)ListInsert(A, 1, a[i]);InitList(B);for(i=5; i>=0; i–)ListInsert(B, 1, b[i]);printf(“A: %c\n”, increase(A)?’Y’:’N’);printf(“B: %c\n”, increase(B)?’Y’:’N’);DestroyList(A);DestroyList(B);return 0;}
奋斗令我们的生活充满生机，责任让我们的生命充满意义！
