线性表的顺序存储结构是逻辑地址和物理地址都连续，而链式存储结构是逻辑地址连续，但物理地址不一定连续，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了插入和删除元素的效率。本文主要讲一下单链表。
单链表的逆序输出不同于反转单链表，逆序输出并不会改变单链表本身的顺序，所以直接使用递归实现：
/* * 单链表的逆序输出 */ void PrintListReversely(LinkList L, void (*visit)(ElemType)) { if(L != NULL) { PrintListReversely(L->next, visit); visit(L->data); } }
#include <stdio.h> #include <stdlib.h> typedef int ElemType; struct LNode { ElemType data; struct LNode *next; }; LNode *ReverseList(LNode *pL) { LNode *pReversedNode = NULL; LNode *pNode = pL; LNode *pPrevNode = NULL; while(pNode != NULL) { LNode *pTempNode = pNode->next; if(pTempNode == NULL) pReversedNode = pNode; pNode->next = pPrevNode; pPrevNode = pNode; pNode = pTempNode; } return pReversedNode; } LNode *CreatList() { LNode *pL = NULL; for(int i = 1; i < 10; i++) { LNode * L = (LNode *)malloc(sizeof(LNode)); L->data = i; L->next = pL; pL = L; } return pL; } void ShowList(LNode *pL) { while( pL != NULL) { printf("%d ", pL->data); pL = pL->next; } printf("\n"); } int main() { LNode *pL = CreatList(); ShowList(pL); pL = ReverseList(pL); ShowList(pL); }
原来我是想在原来的单链表上做反转的，但是因为原本的单链表初始化时会带有头结点，所以在逆序时会有一点小问题，干脆就另写一个了，下面贴出单链表的一些基本操作（最后的逆序和反转有一点小问题）：
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; typedef int Status; /* * 存储结构 */ typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; /* * 初始化单链表 */ LinkList InitList() { LinkList L; L = (LinkList) malloc(sizeof(LNode)); if (L == NULL) { exit(OVERFLOW); } L->next = NULL; } /* * 摧毁单链表 */ void DestroyList(LinkList *L) { LinkList temp; while (*L) { temp = (*L)->next; free(*L); *L = temp; } } /* * 清空单链表 */ void ClearList(LinkList L) { LinkList p = L->next; L->next = NULL; DestroyList(&p); } /* * 判断是否为空 */ Status isEmpty(LinkList L) { if (L->next) { return FALSE; } else { return TRUE; } } /* * 获取长度 */ int GetLength(LinkList L) { int i = 0; LinkList p = L->next; while (p) { i++; p = p->next; } return i; } /* * 根据位置获取元素 */ Status GetElem(LinkList L, int i, ElemType *e) { int j = 1; LinkList p = L->next; while (p && j < i) { j++; p = p->next; } if (!p || j > i) { return ERROR; } *e = p->data; return OK; } /* * 比较两个元素是否相等 */ Status compare(ElemType e1, ElemType e2) { if (e1 == e2) { return 0; } else if (e1 < e2) { return -1; } else { return 1; } } /* * 查找指定元素的位置 */ int FindElem(LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)) { int i = 0; LinkList p = L->next; while (p) { i++; if (!compare(p->data, e)) { return i; } p = p->next; } return 0; } /* * 获取前驱元素 */ Status PreElem(LinkList L, ElemType cur_e, ElemType *pre_e) { LinkList q, p = L->next; while (p->next) { q = p->next; if (q->data == cur_e) { *pre_e = p->data; return OK; } p = q; } return ERROR; } /* * 获取后继元素 */ Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { LinkList p = L->next; while (p->next) { if (p->data == cur_e) { *next_e = p->next->data; return OK; } p = p->next; } return ERROR; } /* * 插入元素 */ Status InsertElem(LinkList L, int i, ElemType e) { int j = 0; LinkList s, p = L; while (p && j < i - 1) { j++; p = p->next; } if (p == NULL) { printf("Position Error"); return ERROR; } s = (LinkList) malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return OK; } /* * 删除元素 */ Status DeleteElem(LinkList L, int i, ElemType *e) { int j = 0; LinkList q, p = L; while (p->next && j < i - 1) { j++; p = p->next; } if (p == NULL || p->next == NULL || j > i - 1) { printf("Position Error"); return ERROR; } q = p->next; p->next = q->next; *e = q->data; free(q); return OK; } /* * 访问元素 */ void visit(ElemType e) { printf("%d ", e); } /* * 遍历单链表 */ void TraverseList(LinkList L, void (*visit)(ElemType)) { LinkList p = L->next; while (p) { visit(p->data); p = p->next; } } /* * 单链表的逆序输出 */ void PrintListReversely(LinkList L, void (*visit)(ElemType)) { if(L != NULL) { PrintListReversely(L->next, visit); visit(L->data); } } /* * 单链表的反转 */ LNode *ReverseList(LNode *pL) { LNode *pReversedNode = NULL; LNode *pNode = pL; LNode *pPrevNode = NULL; while(pNode != NULL) { LNode *pTempNode = pNode->next; if(pTempNode == NULL) pReversedNode = pNode; pNode->next = pPrevNode; pPrevNode = pNode; pNode = pTempNode; } return pReversedNode; }
