当前位置：首页 > news >正文

数据结构之线性表（3）

news 来源：原创 2024/9/29 17:25:18

数据结构之线性表（3）

上文我们了解了线性表的静动态存储的相关操作，此篇我们对线性表中链表的相关操作探讨。
在进行链表的相关操作时，我们先来理解单链表是什么？

1.链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
在这里插入图片描述

//单链表的结点定义
struct SeqListNode
{datatype data;struct SLNode * next;
};
typedef struct SeqListNode SLNode;

在这里插入图片描述

单链表的基本操作：

1.头插

//头插
void SLNpushfront(SLNode** pphead,datatype x)
{//1.不存在其他结点if (*pphead == NULL){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;*pphead = newnode;}else{//2.存在其他结点SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));tmp->data = x;tmp->next = *pphead;*pphead = tmp;}
}

2.尾插

//尾插
void SLNpushback(SLNode** pphead, datatype x)
{//1.不存在其他结点if (*pphead == NULL){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;*pphead = newnode;}else{//2.存在其他结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));tail->next = newnode;newnode->data = x;newnode->next = NULL;}
}

3.头删

//头删
void SLNpopfront(SLNode** pphead)
{//1.链表中0个结点，无法删除if (*pphead == NULL){printf("链表中没有结点，无法删除\n");exit(-1);}//2.链表中只有一个结点if ((*pphead)->next == NULL){free(*pphead);(*pphead) = NULL;}//3.链表中有一个以上结点SLNode* tmp = (*pphead)->next;free(*pphead);(*pphead) = NULL;*pphead = tmp;
}

4.尾删

//尾删
void SLNpopback(SLNode** pphead)
{//1.链表中0个结点if (*pphead ==NULL){printf("链表中没有结点，无法删除\n");exit(-1);}//2.链表中只有一个结点,就类似于只有一个结点的头删if ((*pphead)->next ==NULL){free(*pphead);(*pphead) = NULL;}//3.链表中有一个以上结点SLNode* prev = NULL;SLNode* tail = (*pphead);while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;
}

5.打印

//打印
void SLNprintf(SLNode* pphead)
{while (pphead){printf("%d ", pphead->data);pphead = pphead->next;}
}

6.查找

//查找
SLNode* SLNfind(SLNode* phead, datatype x)
{SLNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

7.指定位置插入

//指定位置插入
void SLNinsert(SLNode** pphead, SLNode* pos, datatype x)
{if (pos == *pphead){SLNpushfront(pphead, x);//若pos==*pphead，就等同于头插}else{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

7.指定位置删除

void SLNdeleate(SLNode** pphead, SLNode* pos)
{if (pos == *pphead){SLNpopfront(pphead);//若pos==*pphead，就等同于头删}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
//单链表结点的定义
struct SeqListNode
{datatype data;struct SLNode* next;
};
typedef struct SeqListNode SLNode;
//头插
void SLNpushfront(SLNode** pphead,datatype x)
{//1.不存在其他结点if (*pphead == NULL){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;*pphead = newnode;}else{//2.存在其他结点SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));tmp->data = x;tmp->next = *pphead;*pphead = tmp;}
}
//尾插
void SLNpushback(SLNode** pphead, datatype x)
{//1.不存在其他结点if (*pphead == NULL){SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;*pphead = newnode;}else{//2.存在其他结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));tail->next = newnode;newnode->data = x;newnode->next = NULL;}
}
//头删
void SLNpopfront(SLNode** pphead)
{//1.0个结点，无法删除if (*pphead == NULL){printf("链表中没有结点，无法删除\n");exit(-1);}//2.链表中只有一个结点if ((*pphead)->next == NULL){free(*pphead);(*pphead) = NULL;}//3.链表中有一个以上结点SLNode* tmp = (*pphead)->next;free(*pphead);(*pphead) = NULL;*pphead = tmp;
}
//尾删
void SLNpopback(SLNode** pphead)
{//1.链表中0个结点if (*pphead ==NULL){printf("链表中没有结点，无法删除\n");exit(-1);}//2.链表中只有一个结点,就类似于只有一个结点的头删if ((*pphead)->next ==NULL){free(*pphead);(*pphead) = NULL;}//3.链表中有一个以上结点SLNode* prev = NULL;SLNode* tail = (*pphead);while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;
}
//打印
void SLNprintf(SLNode* pphead)
{while (pphead){printf("%d ", pphead->data);pphead = pphead->next;}
}
//指定位置插入
void SLNinsert(SLNode** pphead, SLNode* pos, datatype x)
{if (pos == *pphead){SLNpushfront(pphead, x);}else{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));newnode->data = x;newnode->next = NULL;SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
//指定位置删除
void SLNdeleate(SLNode** pphead, SLNode* pos)
{if (pos == *pphead){SLNpopfront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}
//查找
SLNode* SLNfind(SLNode* phead, datatype x)
{SLNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
int main()
{SLNode* plist = NULL;SLNpushfront(&plist, 1);SLNpushfront(&plist, 2);SLNpushfront(&plist, 3);SLNpushback(&plist, 4);SLNpushback(&plist, 5);SLNpushback(&plist, 6);SLNpushback(&plist, 7);SLNpopfront(&plist);SLNpopback(&plist);SLNprintf(plist);return 0;
}