基础数据结构:单链表

今天懒洋洋学习了关于基础数据结构有关单链表的相关操作，懒洋洋来这温习一下。

一:单链表的定义

链表定义：用链式存储的线性表统称为链表，即逻辑结构上连续，物理结构上不连续。

链表分类：单链表、双链表、循环链表、静态链表

二:单链表的实现

1:定义结构体

typedef int SLQDataType;//利用typedef将int==SLQDataType
struct SListNode
{SLQDataType data;//定义节点的数据域struct SListNode * next;//定义节点的指针域
};
//重命名结构体
typedef struct SListNode SLNode;

2:初始化单链表

SLNode * phead = NULL;//即直接将头指针置为空。

3:后插法插入元素

划重点:由于我们在定义的变量即phead为一级指针，此时我们要对单链表里面的元素进行改变，即对单链表做出更改，我们要传入一级指针的地址，再利用二级指针进行接受。

    SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);

后插法插入元素代码实现:

(在插入元素的时候，要进行分类，当单链表里面没有元素的时候，我们将为要插入的元素利用malloc库对新的元素进行分配空间，再直接将定义的newNode赋值给*pphead)

//BuySListNode函数实现
SLNode* BuySListNode(SLQDataType x)
{//申请空间SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){printf("申请节点失败\n");return;}newNode->data = x;newNode->next = NULL;return newNode;
}

void SListPushBack(SLNode**pphead, SLQDataType x)
{if (*pphead == NULL){*pphead = BuySListNode(x);}else{//定义一个结构体指针，指向头结点的指针，判断tail->next是否为NULL，要是为NULL的话//将新的结点的地址即赋值给tail->next.再将newNode->next==NULLSLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = BuySListNode(x);}
}

4:后删法删除元素

1:当单链表里面没有元素的时候，直接结束函数；

2:当单链表里面只有一个结点的时候，需要判断if(*pphead->next==NULL)，再释放掉空间；

3:当有一个结点以上时，利用tail->next=NULL，找到末尾的节点，再利用一个指针(2)指向tail的前一个结点，再将前一个结点的next=NULL,释放掉tail的空间)

void SListPopBack(SLNode** pphead)
{//空if (*pphead == NULL){return;}//一个结点else if ((*pphead)->next == NULL){free(*pphead);}//一个以上结点else{//用两个指针进行标记，一个标记下一个是否为NULL//另一个指针标记前一个指针的前一个位置SLNode* tail = *pphead;SLNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}free(tail);tail = NULL;pre->next = NULL;}
}

5:头插法插入元素

我们创建新的结点，将newNode的next指向头结点，再将newNode赋值给*phead;

 void SListPushFront(SLNode**pphead, SLQDataType x)
{SLNode* newNode = BuySListNode(x);newNode->next = *pphead;*pphead = newNode;
}

6:头删法删除元素

1:当单链表里面没有元素的时候，直接结束函数；

2:当单链表里面只有一个结点的时候，需要判断if(*pphead->next==NULL)，再释放掉空间；

3:当有一个结点以上时，创建临时的指针保存头指针所指向的下个结点的地址即next=(*phead)->next，释放掉头指针的空间和地址，再将创建的临时的指针变成头指针，即（*phead）=next;

void SListPopFront(SLNode** pphead)
{if (*pphead == NULL){return;}else if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//先找到下一个结点，用指针保存起来，再释放掉前面SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}

7:查找单链表元素

思路:循环遍历

SLNode* SListFind(SLNode* phead, SLQDataType x)
{{SLNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}
}

8:随机位置插入和删除

void SListInsertAfter(SLNode* ps, SLQDataType x)
{BuySListNode(x)->next = ps->next;ps->next = BuySListNode(x);
}
void SListEraseAfter(SLNode* ps)
{SLNode* next = ps->next;ps->next = next->next;free(ps);
}

9:打印单链表的各个元素

void PrintSList(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d-> ", cur->data);cur = cur->next;}printf("NULL");
}

10:主函数及部分功能实现

#include "SList.h"
void test()
{//将头指针置为空SLNode * phead = NULL;//后插法插入元素SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);//后删法删元素SListPopBack(&phead);//头插法增加元素SListPushFront(&phead, 5);//头删法删除元素SListPopFront(&phead);PrintSList(phead);
}int main()
{test();
}

今天懒洋洋的学习之路就到这了，感谢羊村的各位捧场!!!