链表的概念及常用操作

• 链表是一种物理存储单元上非连续的存储结构，由一系列节点（链表中的每一个元素成为节点）组成，节点可以在运行时动态生成，节点和节点之间通过指针链接。
• 每个节点包括两个部分，一部分存储数据元素的数据域，另一部分时存储下一节点地址的指针域。
• 链表分类
  
  • 带头节点 不带头节点
  • 单向链表 双向链表 循环链表
  • 静态链表 动态链表
• 案例1 单向链表的建立、遍历、插入、删除操纵

---

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct Node
{
int data;
struct Node *next;
}SList;

/*创建链表*/
SList *SList_Create()
{
SList *pHead;
SList *pM;
SList *pCurrent;
int num;

/*创建头节点并初始化*/
pHead = (SList *)malloc(sizeof(SList));
if (pHead == NULL)
{
    return NULL;
}
pHead->data = 0;
pHead->next = NULL;
pCurrent = pHead;

printf("input a num:");
scanf("%d",&num);
while (num != -1)
{
    //创建业务节点
    pM = (SList *)malloc(sizeof(SList));
    if (pM == NULL)
    {
        return NULL;
    }
    pM->data = num;
    pM->next = NULL;

    pCurrent->next = pM;
    pCurrent = pM;

    printf("input a num:");
    scanf("%d", &num);
}
return pHead;
}
//遍历链表
void SList_Print(SList *head)
{
SList *pCurrent = NULL;
if (head != NULL && head->next != NULL)
{
    pCurrent = head->next;
}
while (pCurrent != NULL)
{
    printf("%d  ",pCurrent->data);
    pCurrent = pCurrent->next;
}
printf("\n");
return ;
}

//插入节点
int  SList_Insert(SList *head,int Num)
{
SList *pPre;
SList *pCurrent;
SList *pM;

int ret = 0;
if (head == NULL)
{
    ret = -1;
    printf("link is NULL.\n");
}
pPre = head; 
pCurrent = head->next;
while (pCurrent != NULL)
{
    if (pCurrent->data <= Num)
    {
        pCurrent = pCurrent->next;
        pPre = pPre->next;
    }
    else
        break;
}

pM = (SList *)malloc(sizeof(SList));
pM->data = Num;
pM->next = pCurrent;
pPre->next = pM;

return 0;
}

//删除节点
int  SList_Delete(SList *head, int Num)
{
SList *pCurrent;
SList *pPre;

int ret = 0;
if (head == NULL)
{
    ret = -1;
    printf("link is NULL.\n");
}

pCurrent = head->next;
pPre = head;

while (pCurrent != NULL)
{
    if (pCurrent->data != Num)
    {
        pPre = pPre->next;
        pCurrent = pCurrent->next;
    }
    else
    {
        pPre->next = pCurrent->next;
        free(pCurrent);
        pCurrent = NULL;
        break;
    }
}
return 0;
}

//链表反转
SList *SList_revers(SList *head)
{
SList *pCurrent;
SList *pPre;
SList *pNext;
SList *pM;

int ret = 0;
if (head == NULL)
{
    ret = -1;
    printf("link is NULL.\n");
}

pCurrent = head->next;
pPre = NULL;
while (pCurrent != NULL)
{
    pNext = pCurrent->next;
    pCurrent->next = pPre;
    pPre = pCurrent;
    pCurrent = pNext;
}
pM = (SList *)malloc(sizeof(SList));
if (pM == NULL)
{
    return NULL;
}
pM->data = 0;
pM->next = pPre;
return pM;
}

//销毁链表
int SList_Destroy(SList *head)
{
SList* pCurrent;
int ret = 0;
if (head == NULL)
{
    ret = -1;
    printf("link is NULL.\n");
    return ret;
}

while (head != NULL)
{
    pCurrent = head->next;
    free(head);
    head = pCurrent;
}

return 0;
}

int main()
{

SList *head = NULL;
int x = 10;
int y = 5;
int ret = 0;
head = SList_Create();
if (head == NULL)
{
    ret = -1;
    printf("SList_Createn erro.\n");
    return ret;
}
SList_Print(head);
printf("插入节点前：");
SList_Print(head);
SList_Insert(head, x);
printf("插入节点后：");
SList_Print(head);
SList_Delete(head, y);
printf("删除节点后：");
SList_Print(head);

head = SList_revers(head);
printf("反转后：");

SList_Destroy(head);
return 0;
}