本文共 4999 字，大约阅读时间需要 16 分钟。

线性表的顺序存储结构是逻辑地址和物理地址都连续，而链式存储结构是逻辑地址连续，但物理地址不一定连续，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了插入和删除元素的效率。本文主要讲一下单链表。

单链表的逆序输出

单链表的逆序输出不同于反转单链表，逆序输出并不会改变单链表本身的顺序，所以直接使用递归实现：

/* * 单链表的逆序输出 */void PrintListReversely(LinkList L, void (*visit)(ElemType))  {        if(L != NULL)    {              PrintListReversely(L->next, visit);        visit(L->data);    }}

反转单链表

#include 
   
    #include 
    
     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 
   
    #include 
    
     #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef 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;}
    
   

转载地址：https://blog.csdn.net/huzhiyuan0000000/article/details/74979259 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！