链表逆序操作笔试的时候真的不要写的太多， 上次还来了个递归实现链表逆序。
就当利用这个题复习下单链表的常用操作了， 下面的单链表（ADT）参考了《数据结构和算法分析---C语言描述》中的写法， 稍有改动。
增加了一些自己觉得会经常用到的函数。链表的主要操作在 linklist.h 文件中， 链表函数的实现主要在 linklist.c 文件中。 test_linklist.c 是一个简单的测试用例。
下面再具体看看链表逆序函数的实现(非递归) ：
在函数ReverseList()当中， 定义了4个指针，
1. pReversedList 指向反转以后的链表头 。
2. pNode指向的是当前要反转的结点
3. pPrev是指向的是要反转结点（pNode）的前一个结点（也就是已经反转好的链表的尾结点）
4. pNext指向的是pNode的下一个结点。主要通过下面几条语句进行反转， 直到链表尾为止。
pNode->Next = pPrev;
pPrev = pNode;
pNode = pNext;
pNext = pNode->Next;
/* linklist.h */
/***********************************************************/ /* Copyright (C) SA14226214, USTC, 2014-2015 */ /* */ /* FILE NAME : linklist.h */ /* PRINCIPAL AUTHOR : GaoZhipeng */ /* SUBSYSTEM NAME : LinkList */ /* MODULE NAME : LinkList */ /* LANGUAGE : C */ /* TARGET ENVIRONMENT : ANY */ /* DATE OF FIRST RELEASE : 2015/04/13 */ /* DESCRIPTION : This is a linklist program */ /***********************************************************/ /* *Revision log: * *Ceated by GaoZhipeng, 2015/04/13 * */ #ifndef LINK_LIST_H #define LINK_LIST_H #define ElementType char #define boolean int #define true 1 #define false 0 typedef struct Node { ElementType Element; struct Node *Next; }Node; //typedef struct Node; typedef struct Node *PtrToNode; /*List是一个固定的链表，Position是链表中的位置可以移动 */ typedef PtrToNode List; typedef PtrToNode Position; List MakeEmpty(List L); int IsEmpty(List L); int IsLast(Position P, List L); Position Find(ElementType X, List L); //按照元素和位置查找 Position FindPreviousElement(ElementType X, List L); Position FindPreviousPosition(int K, List L); //插入删除操作 void DeleteByElement(ElementType X, List L); Position DeleteByPosition(int i, List L); Position InsertByPosition(ElementType X, int i, List L); List CreateListR(); void PrintList(List L); void DeleteList(List L); /*链表逆序*/ List ReverseList(List L); List ReverseList_DG(List L); //Position Header(List L); //Position First(List L); //Posttion Advance(Position P); //ElementType Retrieve(Position P); #endif
/* linklist.c */
/***********************************************************/ /* Copyright (C) SA14226214, USTC, 2014-2015 */ /* */ /* FILE NAME : linklist.c */ /* PRINCIPAL AUTHOR : GaoZhipeng */ /* SUBSYSTEM NAME : LinkList */ /* MODULE NAME : LinkList */ /* LANGUAGE : C */ /* TARGET ENVIRONMENT : ANY */ /* DATE OF FIRST RELEASE : 2015/04/13 */ /* DESCRIPTION : This is a linklist program */ /***********************************************************/ /* *Revision log: * *Ceated by GaoZhipeng, 2015/04/13 * */ #include<stdio.h> #include<malloc.h> #include"linklist.h" List MakeEmpty(List L) { List P = L; P->Next = NULL; return P; } boolean IsEmpty(List L) { Position P = L; if(P->Next == NULL) { return true; } else return false; } boolean IsLast(Position P, List L) { Position p = P; if(p->Next == NULL) { return true; } else { return false; } } Position Find(ElementType X, List L) { Position p = L->Next; while(p != NULL && p->Element != X) { p = p->Next; } return p; } /*按照值查找*/ Position FindPreviousElement(ElementType X, List L) { Position p = L; while(p->Next != NULL && p->Element != X) { p = p->Next; } return p; } /*按照序号查找*/ Position FindPreviousPosition(int K, List L) { Position P = L; int i = 1; while(P != NULL && i<K ) { P = P->Next; i++; } if(i == K) return P; else return NULL; } /*按照节点的值删除*/ void DeleteByElement(ElementType X, List L) { Position P, TmpCell; P = FindPreviousElement(X, L); if( !IsLast(P, L) ) { TmpCell = P->Next; P->Next = TmpCell->Next; free(TmpCell); } } /*删除第i个节点, i从1开始*/ Position DeleteByPosition(int i, List L) { Position P, TmpCell; if(i==1) { TmpCell = L; if(L != NULL) L = L->Next; else return NULL; free(TmpCell); return L; } P = FindPreviousPosition(i-1, L); if(P==NULL) { printf("第%d个节点不存在", i-1); } else if(P->Next == NULL) { printf("第%d个节点不存在", i); } else { TmpCell = P->Next; P->Next = TmpCell->Next; free(TmpCell); return P; } } /*插入到第i个位置，i从1开始*/ Position InsertByPosition(ElementType X, int i, List L) { Position P, TmpCell; if( i==1 ) { TmpCell = (Position)malloc(sizeof(Node)); TmpCell->Element = X; TmpCell->Next= L; return TmpCell; } P = FindPreviousPosition(i-1, L); if(P == NULL) { printf("第%d个节点不存在", i-1); return NULL; } else { TmpCell = (List)malloc(sizeof(Node)); TmpCell->Element = X; TmpCell->Next = P->Next; P->Next = TmpCell; return TmpCell; } } /*删除整表*/ void DeleteList(List L) { Position P, Tmp; P = L->Next; L->Next = NULL; while(P != NULL) { Tmp = P->Next; free(P); P = Tmp; } } /*尾插法建表*/ List CreateListR() { List Head, TmpCell, P; ElementType Tmp; Head = (List)malloc(sizeof(Node)); P = Head; //假定输入以'$'符号结束 Tmp = getchar(); P->Element = Tmp; Tmp = getchar(); while(Tmp != '$') { TmpCell = (Position)malloc(sizeof(Node)); TmpCell->Element = Tmp; P->Next = TmpCell; P = TmpCell; Tmp = getchar(); } P->Next = NULL; return Head; } void PrintList(List L) { Position P = L; while(P != NULL) { printf("%c", P->Element); if( !IsLast(P, L) ) { printf("---->"); } P = P->Next; } printf(" "); } /*链表逆序(非递归实现)*/ List ReverseList(List L) { List ReverseList = NULL; Position pNode = L; Position pPre = NULL; Position pNext ; while(pNode != NULL) { pNext = pNode->Next; if(pNext == NULL) { ReverseList = pNode; } pNode->Next = pPre; pPre = pNode; pNode = pNext; } return ReverseList; } /*链表逆序递归实现*/ List ReverseList_DG(Position Head) { /*结束的条件:链表为空或者链表最后一个节点*/ if(Head==NULL || Head->Next == NULL) { return Head; } Position NewHead = ReverseList_DG(Head->Next); Head->Next->Next = Head; Head->Next = NULL; return NewHead; }
/* test_linklist.c */
/***********************************************************/ /* Copyright (C) SA14226214, USTC, 2014-2015 */ /* */ /* FILE NAME : test_linklist.c */ /* PRINCIPAL AUTHOR : GaoZhipeng */ /* SUBSYSTEM NAME : LinkList */ /* MODULE NAME : LinkList */ /* LANGUAGE : C */ /* TARGET ENVIRONMENT : ANY */ /* DATE OF FIRST RELEASE : 2015/04/13 */ /* DESCRIPTION : This is a linklist program */ /***********************************************************/ /* *Revision log: * *Ceated by GaoZhipeng, 2015/04/13 * */ #include<stdio.h> #include"linklist.h" #define MaxData 65535 int main() { ElementType Num; List L, R1, R2; printf("输入链表（字符），以'$'符号结束 "); L = CreateListR(); PrintList(L); /*测试插入操作*/ InsertByPosition('a', 7, L); PrintList(L); /*测试删除操作*/ DeleteByPosition(7, L); PrintList(L); /*测试逆序操作*/ R1 = ReverseList(L); PrintList(R1); /*测试递归逆序*/ R2 = ReverseList_DG(R1); PrintList(R2); }
/* makefile */
#this is a makefile all : test test : test.o linklist.o gcc $^ -o $@ test.o : test_linklist.c linklist.c linklist.h gcc -c test_linklist.c -o test.o linklist.o : linklist.c linklist.h gcc -c linklist.c -o linklist.o clean : -rm test *.o .PHONY: clean
执行make，运行的结果如下所示 ：
