单链表的实现
首先创建头文件
#pragma #include<stdio.h> #include<assert.h> #include<stdlib.h>
//定义数据类型 typedef int SLDataType; //创建单链表 typedef struct SLinkListNode { SLDataType data; struct SLinkListNode* next; }SLNode;
以下是所需要实现的函数接口
//不会改变头指针，传一级指针 //可能改变头指针，传二级指针 // //创建结点 SLNode* BuySLNode(SLDataType x); //打印 void SListPrint(SLNode* phead); //尾插 void SListPushBack(SLNode** pphead, SLDataType x); //头插 void SListPushFront(SLNode** pphead, SLDataType x); //尾删 void SListPopBack(SLNode** pphead); //头删 void SListPopFront(SLNode** pphead); //在pos前插入x void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x); //找到x的位置并返回 SLNode* SListFind(SLNode* phead, SLDataType x); //删除pos位置的值 void SListErase(SLNode** pphead, SLNode* pos);
接下来是函数的实现
#include"SLinkList.h" //创建新结点 SLNode* BuySLNode(SLDataType x) { SLNode* newnode = (SLDataType*)malloc(sizeof(SLDataType)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } //打印 void SListPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //尾插 void SListPushBack(SLNode** pphead, SLDataType x) { SLNode* newnode = BuySLNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点的指针 SLNode* tail = *pphead; while (tail->next) { tail = tail->next; } // 尾节点，链接新节点 tail->next = newnode; } } //头插 void SListPushFront(SLNode** pphead, SLDataType x) { SLNode* newnode = BuySLNode(x); newnode->next = *pphead; *pphead = newnode; } //尾删 void SListPopBack(SLNode** pphead) { if (*pphead == NULL) { return; } else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLNode* prev = NULL; SLNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } } //头删 void SListPopFront(SLNode** pphead) { SLNode* next = (*pphead)->next; free(*pphead); *pphead = next; } //在pos前插入x void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else { SLNode* newnode = BuySLNode(x); SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } } //找到x的位置并返回 SLNode* SListFind(SLNode* phead, SLDataType x) { SLNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //删除pos位置的值 void SListErase(SLNode** pphead, SLNode* pos) { if (pos == *pphead) { SListPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
