链表概念,以及基本操作C语言实现
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
1. 单向、双向
2. 带头、不带头
3. 循环、非循环
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
头文件,里面给出了链表的定义以及基本操作函数的声明
typedef int SDataType;typedef struct SListNode
{SDataType _data;struct SListNode* _pNext;
}Node;// 给一个链表结构
typedef struct SList
{Node* _pHead;
}SList;// 链表的初始化
void SListInit(SList* pl);// 在链表中尾插值为data的节点
void SListPushBack(SList* pl, SDataType data);// 删除链表最后一个节点
void SListPopBack(SList* pl);// 在链表第一个元素前插入值为data的节点
void SListPushFront(SList* pl, SDataType data);// 删除链表中第一个节点
void SListPopFront(SList* pl);// 在链表pos位置后插入置为data的节点
void SListInsertAfter(SList *pl, Node* pos, SDataType data);// 删除链表中的pos后面的节点
void SListEraseAfter(SList* pl, Node* pos);// 在链表中查找值为data的节点,找到返回该节点的地址,否则返回空
Node* SListFind(SList* pl, SDataType data);// 销毁链表
void SListDestroy(SList* pl);// 获取链表中有效节点的个数
int SListSize(SList* pl);// 检测链表是否为空
int SListEmpty(SList* pl);// 获取链表的第一个节点
Node* SListFront(SList* pl);// 获取链表的第二个节点
Node* SListBack(SList* pl);// 删除链表中第一个值为data的节点
void SListRemove(SList* pl, SDataType data);// 删除链表中所有值为data的节点
void SListRemoveAll(SList* pl, SDataType data);
函数定义
#include <stdio.h>
#include <stdlib.h>
#include "slist.h"
#include <assert.h>// 链表的初始化
void SListInit(SList* pl)
{assert(pl != NULL);pl->_pHead = NULL;
}// 在链表中尾插值为data的节点
void SListPushBack(SList* pl, SDataType data)
{ assert(pl != NULL);Node *node = (Node *)malloc(sizeof(Node));node->_data = data;node->_pNext = NULL;//如果没有节点if (pl->_pHead == NULL){pl->_pHead = node;return;}//链表中至少有一个节点,找到最后一个节点Node *cur = pl->_pHead;while (cur->_pNext != NULL){cur = cur->_pNext;}cur->_pNext = node;
}// 删除链表最后一个节点
void SListPopBack(SList* pl)
{assert(pl != NULL);assert(pl->_pHead != NULL); //判断链表中至少有一个节点//如果只有一个节点if (pl->_pHead->_pNext == NULL){free(pl->_pHead);pl->_pHead = NULL;return;}//不止一个节点Node *cur = pl->_pHead;while (cur->_pNext->_pNext != NULL){cur = cur->_pNext;}free(cur->_pNext);cur->_pNext = NULL;
}// 在链表第一个元素前插入值为data的节点
void SListPushFront(SList* pl, SDataType data)
{Node *node = (Node *)malloc(sizeof(Node));node->_data = data;node->_pNext = pl->_pHead;pl->_pHead = node;
}// 删除链表中第一个节点
void SListPopFront(SList* pl)
{assert(pl != NULL);assert(pl->_pHead != NULL);//需要先记录头节点的下一个节点,然后释放头节点//再把头节点绑定为刚才记录的头节点的下一个节点Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;
}// 在链表pos位置后插入值为data的节点
void SListInsertAfter(SList *pl, Node* pos, SDataType data)
{assert(pl != NULL);Node *node = (Node*)malloc(sizeof(Node));node->_data = data;node->_pNext = pos->_pNext;pos->_pNext = node;
}// 删除链表中的pos后面的节点
void SListEraseAfter(SList* pl, Node* pos)
{assert(pl != NULL);Node *cur = pos->_pNext;pos->_pNext = pos->_pNext->_pNext;free(cur);
}// 在链表中查找值为data的节点,找到返回该节点的地址,否则返回空
Node* SListFind(SList* pl, SDataType data)
{assert(pl != NULL);Node *cur = pl->_pHead;while (cur != NULL){if (cur->_data == data){return cur;}cur = cur->_pNext;}return NULL;
}// 销毁链表
void SListDestroy(SList* pl)
{Node *cur = pl->_pHead;Node *next;for (cur; cur->_pNext != NULL; cur = next){next = cur->_pNext;free(cur);}pl->_pHead = NULL;
}// 获取链表中有效节点的个数
int SListSize(SList* pl)
{Node *cur = pl->_pHead;int size = 0;while (cur != NULL){size += 1;cur = cur->_pNext;}return size;
}// 检测链表是否为空
int SListEmpty(SList* pl)
{assert(pl != NULL);if (pl->_pHead == NULL){return 1;}return 0;
}// 获取链表的第一个节点
Node* SListFront(SList* pl)
{assert(pl != NULL);return pl->_pHead;
}// 获取链表的第二个节点
Node* SListBack(SList* pl)
{assert(pl != NULL);return pl->_pHead->_pNext;
}// 删除链表中第一个值为data的节点
void SListRemove(SList* pl, SDataType data)
{assert(pl != NULL);//为空if (pl->_pHead == NULL){return;}//为头节点if (pl->_pHead->_data == data){Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;return;}//不是头节点Node *cur = pl->_pHead;while (cur != NULL){if (cur->_pNext->_data==data){Node *next = cur->_pNext->_pNext;free(cur->_pNext);cur->_pNext = next;return;}cur = cur->_pNext;}
}// 删除链表中所有值为data的节点
void SListRemoveAll(SList* pl, SDataType data)
{assert(pl != NULL);//为空if (pl->_pHead == NULL){return;}//为第一个节点if (pl->_pHead->_data == data){Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;}//不是第一一个节点Node *cur = pl->_pHead;while (cur->_pNext != NULL){if (cur->_pNext->_data == data){Node *next = cur->_pNext->_pNext;free(cur->_pNext);cur->_pNext = next;}cur = cur->_pNext;}
}//打印函数
void Pri(SList* pl)
{assert(pl != NULL);Node *cur = pl->_pHead;while (cur != NULL){printf("%d %p\n", cur->_data, cur);cur = cur->_pNext;}printf("\n");return;
}
下面是测试的main函数
int main()
{SList list;SListInit(&list);//尾插SListPushBack(&list, 1);SListPushBack(&list, 2);SListPushBack(&list, 3);// 1 2 3printf("尾插后:\n");Pri(&list);//头插SListPushFront(&list, 30);SListPushFront(&list, 20);SListPushFront(&list, 10);// 10 20 30 1 2 3printf("头插后:\n");Pri(&list);//寻找值为30的节点Node *pos = SListFind(&list, 30);printf("%d %p\n",pos->_data, pos);printf("寻找值为30的节点:\n");printf("\n");//在pos处插入值为100的节点SListInsertAfter(&list, pos, 100);// 10 20 30 100 1 2 3printf("在pos处插入值为100的节点后:\n");Pri(&list);//删除pos处的节点SListEraseAfter(&list, pos);// 10 20 30 1 2 3printf("删除pos处的节点后:\n");Pri(&list);//头删SListPopFront(&list);// 20 30 1 2 3printf("头删后:\n");Pri(&list);//尾删SListPopBack(&list);// 20 30 1 2printf("尾删后:\n");Pri(&list);//删除第一个值为2的节点SListRemove(&list, 2);// 20 30 1printf("删除链表中第一个值为2的节点后:\n");Pri(&list);//获取链表中的有效元素个数printf("链表中有效元素个数为:%d\n",SListSize(&list));printf("\n");//判断链表是否为空,为空返回 1,不为空返回 0if (SListEmpty(&list) == 1){printf("链表为空\n");printf("\n");}else{printf("链表不为空\n");printf("\n");}//获取链表头节点printf("链表的头节点为:%d %p\n", SListFront(&list)->_data, SListFront(&list));printf("\n");//获取链表第二个节点printf("链表的第二个节点为:%d %p\n", SListBack(&list)->_data, SListBack(&list));printf("\n");//头插SListPushFront(&list, 30);SListPushFront(&list, 20);SListPushFront(&list, 30);SListPushFront(&list, 10);//删除链表中第一个值为30的节点SListRemove(&list, 30);// 10 20 30 20 30 1printf("删除链表中第一个值为30的节点后:\n");Pri(&list);//删除链表中所有值为30的节点SListRemoveAll(&list, 30);// 10 20 20 1printf("删除链表中所有值为30的节点后:\n");Pri(&list);//销毁链表SListDestroy(&list);//销毁后判断链表是否为空,为空返回 1,不为空返回 0if (SListEmpty(&list) == 1){printf("链表为空\n");}elseprintf("链表不为空\n");system("pause");return 0;
}
链表概念,以及基本操作C语言实现
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
1. 单向、双向
2. 带头、不带头
3. 循环、非循环
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
头文件,里面给出了链表的定义以及基本操作函数的声明
typedef int SDataType;typedef struct SListNode
{SDataType _data;struct SListNode* _pNext;
}Node;// 给一个链表结构
typedef struct SList
{Node* _pHead;
}SList;// 链表的初始化
void SListInit(SList* pl);// 在链表中尾插值为data的节点
void SListPushBack(SList* pl, SDataType data);// 删除链表最后一个节点
void SListPopBack(SList* pl);// 在链表第一个元素前插入值为data的节点
void SListPushFront(SList* pl, SDataType data);// 删除链表中第一个节点
void SListPopFront(SList* pl);// 在链表pos位置后插入置为data的节点
void SListInsertAfter(SList *pl, Node* pos, SDataType data);// 删除链表中的pos后面的节点
void SListEraseAfter(SList* pl, Node* pos);// 在链表中查找值为data的节点,找到返回该节点的地址,否则返回空
Node* SListFind(SList* pl, SDataType data);// 销毁链表
void SListDestroy(SList* pl);// 获取链表中有效节点的个数
int SListSize(SList* pl);// 检测链表是否为空
int SListEmpty(SList* pl);// 获取链表的第一个节点
Node* SListFront(SList* pl);// 获取链表的第二个节点
Node* SListBack(SList* pl);// 删除链表中第一个值为data的节点
void SListRemove(SList* pl, SDataType data);// 删除链表中所有值为data的节点
void SListRemoveAll(SList* pl, SDataType data);
函数定义
#include <stdio.h>
#include <stdlib.h>
#include "slist.h"
#include <assert.h>// 链表的初始化
void SListInit(SList* pl)
{assert(pl != NULL);pl->_pHead = NULL;
}// 在链表中尾插值为data的节点
void SListPushBack(SList* pl, SDataType data)
{ assert(pl != NULL);Node *node = (Node *)malloc(sizeof(Node));node->_data = data;node->_pNext = NULL;//如果没有节点if (pl->_pHead == NULL){pl->_pHead = node;return;}//链表中至少有一个节点,找到最后一个节点Node *cur = pl->_pHead;while (cur->_pNext != NULL){cur = cur->_pNext;}cur->_pNext = node;
}// 删除链表最后一个节点
void SListPopBack(SList* pl)
{assert(pl != NULL);assert(pl->_pHead != NULL); //判断链表中至少有一个节点//如果只有一个节点if (pl->_pHead->_pNext == NULL){free(pl->_pHead);pl->_pHead = NULL;return;}//不止一个节点Node *cur = pl->_pHead;while (cur->_pNext->_pNext != NULL){cur = cur->_pNext;}free(cur->_pNext);cur->_pNext = NULL;
}// 在链表第一个元素前插入值为data的节点
void SListPushFront(SList* pl, SDataType data)
{Node *node = (Node *)malloc(sizeof(Node));node->_data = data;node->_pNext = pl->_pHead;pl->_pHead = node;
}// 删除链表中第一个节点
void SListPopFront(SList* pl)
{assert(pl != NULL);assert(pl->_pHead != NULL);//需要先记录头节点的下一个节点,然后释放头节点//再把头节点绑定为刚才记录的头节点的下一个节点Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;
}// 在链表pos位置后插入值为data的节点
void SListInsertAfter(SList *pl, Node* pos, SDataType data)
{assert(pl != NULL);Node *node = (Node*)malloc(sizeof(Node));node->_data = data;node->_pNext = pos->_pNext;pos->_pNext = node;
}// 删除链表中的pos后面的节点
void SListEraseAfter(SList* pl, Node* pos)
{assert(pl != NULL);Node *cur = pos->_pNext;pos->_pNext = pos->_pNext->_pNext;free(cur);
}// 在链表中查找值为data的节点,找到返回该节点的地址,否则返回空
Node* SListFind(SList* pl, SDataType data)
{assert(pl != NULL);Node *cur = pl->_pHead;while (cur != NULL){if (cur->_data == data){return cur;}cur = cur->_pNext;}return NULL;
}// 销毁链表
void SListDestroy(SList* pl)
{Node *cur = pl->_pHead;Node *next;for (cur; cur->_pNext != NULL; cur = next){next = cur->_pNext;free(cur);}pl->_pHead = NULL;
}// 获取链表中有效节点的个数
int SListSize(SList* pl)
{Node *cur = pl->_pHead;int size = 0;while (cur != NULL){size += 1;cur = cur->_pNext;}return size;
}// 检测链表是否为空
int SListEmpty(SList* pl)
{assert(pl != NULL);if (pl->_pHead == NULL){return 1;}return 0;
}// 获取链表的第一个节点
Node* SListFront(SList* pl)
{assert(pl != NULL);return pl->_pHead;
}// 获取链表的第二个节点
Node* SListBack(SList* pl)
{assert(pl != NULL);return pl->_pHead->_pNext;
}// 删除链表中第一个值为data的节点
void SListRemove(SList* pl, SDataType data)
{assert(pl != NULL);//为空if (pl->_pHead == NULL){return;}//为头节点if (pl->_pHead->_data == data){Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;return;}//不是头节点Node *cur = pl->_pHead;while (cur != NULL){if (cur->_pNext->_data==data){Node *next = cur->_pNext->_pNext;free(cur->_pNext);cur->_pNext = next;return;}cur = cur->_pNext;}
}// 删除链表中所有值为data的节点
void SListRemoveAll(SList* pl, SDataType data)
{assert(pl != NULL);//为空if (pl->_pHead == NULL){return;}//为第一个节点if (pl->_pHead->_data == data){Node *cur = pl->_pHead->_pNext;free(pl->_pHead);pl->_pHead = cur;}//不是第一一个节点Node *cur = pl->_pHead;while (cur->_pNext != NULL){if (cur->_pNext->_data == data){Node *next = cur->_pNext->_pNext;free(cur->_pNext);cur->_pNext = next;}cur = cur->_pNext;}
}//打印函数
void Pri(SList* pl)
{assert(pl != NULL);Node *cur = pl->_pHead;while (cur != NULL){printf("%d %p\n", cur->_data, cur);cur = cur->_pNext;}printf("\n");return;
}
下面是测试的main函数
int main()
{SList list;SListInit(&list);//尾插SListPushBack(&list, 1);SListPushBack(&list, 2);SListPushBack(&list, 3);// 1 2 3printf("尾插后:\n");Pri(&list);//头插SListPushFront(&list, 30);SListPushFront(&list, 20);SListPushFront(&list, 10);// 10 20 30 1 2 3printf("头插后:\n");Pri(&list);//寻找值为30的节点Node *pos = SListFind(&list, 30);printf("%d %p\n",pos->_data, pos);printf("寻找值为30的节点:\n");printf("\n");//在pos处插入值为100的节点SListInsertAfter(&list, pos, 100);// 10 20 30 100 1 2 3printf("在pos处插入值为100的节点后:\n");Pri(&list);//删除pos处的节点SListEraseAfter(&list, pos);// 10 20 30 1 2 3printf("删除pos处的节点后:\n");Pri(&list);//头删SListPopFront(&list);// 20 30 1 2 3printf("头删后:\n");Pri(&list);//尾删SListPopBack(&list);// 20 30 1 2printf("尾删后:\n");Pri(&list);//删除第一个值为2的节点SListRemove(&list, 2);// 20 30 1printf("删除链表中第一个值为2的节点后:\n");Pri(&list);//获取链表中的有效元素个数printf("链表中有效元素个数为:%d\n",SListSize(&list));printf("\n");//判断链表是否为空,为空返回 1,不为空返回 0if (SListEmpty(&list) == 1){printf("链表为空\n");printf("\n");}else{printf("链表不为空\n");printf("\n");}//获取链表头节点printf("链表的头节点为:%d %p\n", SListFront(&list)->_data, SListFront(&list));printf("\n");//获取链表第二个节点printf("链表的第二个节点为:%d %p\n", SListBack(&list)->_data, SListBack(&list));printf("\n");//头插SListPushFront(&list, 30);SListPushFront(&list, 20);SListPushFront(&list, 30);SListPushFront(&list, 10);//删除链表中第一个值为30的节点SListRemove(&list, 30);// 10 20 30 20 30 1printf("删除链表中第一个值为30的节点后:\n");Pri(&list);//删除链表中所有值为30的节点SListRemoveAll(&list, 30);// 10 20 20 1printf("删除链表中所有值为30的节点后:\n");Pri(&list);//销毁链表SListDestroy(&list);//销毁后判断链表是否为空,为空返回 1,不为空返回 0if (SListEmpty(&list) == 1){printf("链表为空\n");}elseprintf("链表不为空\n");system("pause");return 0;
}