欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

链表的概念及常用操作

程序员文章站 2022-06-09 15:59:09
...
  • 链表是一种物理存储单元上非连续的存储结构,由一系列节点(链表中的每一个元素成为节点)组成,节点可以在运行时动态生成,节点和节点之间通过指针链接。
  • 每个节点包括两个部分,一部分存储数据元素的数据域,另一部分时存储下一节点地址的指针域。
  • 链表分类
    • 带头节点 不带头节点
    • 单向链表 双向链表 循环链表
    • 静态链表 动态链表
  • 案例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;
}
相关标签: C link