哪个网站可以帮忙做简历,网站建设公司黄页,牛商网网站建设,长沙做搜索引擎的公司文章目录 简介动态顺序表结构体1.头插功能2.头删功能3.尾插功能4.尾删功能5.查找功能6.插入功能6.1 指定位置之#xff08;前#xff09;去插入一个节点6.2 指定位置之#xff08;后#xff09;去插入一个节点 7.删除功能7.1 删除指定位置的数据-时间复杂度O(N)7.2 删除指定… 文章目录 简介动态顺序表结构体1.头插功能2.头删功能3.尾插功能4.尾删功能5.查找功能6.插入功能6.1 指定位置之前去插入一个节点6.2 指定位置之后去插入一个节点 7.删除功能7.1 删除指定位置的数据-时间复杂度O(N)7.2 删除指定位置后一个位置的数据-时间复杂度O(1) 8. 释放链表缓存9. 打印链表的值10.此程序共包含3个文件2个.c文件和1个.h文件10.1 SList.h文件10.2 SList.c文件10.3 test.c文件 简介 本文主要介绍链表的头插、头删、尾插、尾删、查找、插入和删除提供全部的.c和.h文件确保使用者直接复制粘贴到编译器上即可直接运行程序。动态顺序表结构体
typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;1.头插功能 思路是将节点的首地址赋值到新申请节点的next中。/*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead ! NULL);SLTNode* newNode CreatListNode(x);newNode-next *ppHead;*ppHead newNode;return;
}开辟一个新的节点并将要插入的值放心节点对应的data中。/*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode (SLTNode*)malloc(sizeof(SLTNode));if (NULL newNode){printf(CreatListNode malloc fail\n);exit(-1);}newNode-data x;newNode-next NULL;return newNode;
}2.头删功能 思路是将下一个节点的地址赋值到头节点地址上将当前节点free掉。/*头删*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead ! NULL);SLTNode* next (*ppHead)-next;free(*ppHead);*ppHead next;return;
}3.尾插功能 思路是先检查输入*ppHead是否为空不为空就找到链表的尾节点进行新节点的插入。/*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead ! NULL);/*新结点申请空间*/SLTNode* newNode CreatListNode(x);if (*ppHead NULL){*ppHead newNode;}else{/*找到尾结点*/SLTNode* tail *ppHead;while (tail-next ! NULL){tail tail-next;}tail-next newNode;}return;
}4.尾删功能 思路是释放节点时要将下一个节点的地址保存好再释放当前节点。/*尾删*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead ! NULL);/*如果只有一个节点时直接释放此节点*/if ((*ppHead)-next NULL){free(*ppHead);*ppHead NULL;}else/*存在2个及2个以上节点的处理方式*/{SLTNode* tail *ppHead;SLTNode* pre NULL;while (tail-next ! NULL){pre tail;tail tail-next;}pre-next NULL;free(tail);tail NULL;}return;
}5.查找功能 思路是遍历找到节点后返回当前节点的地址找不到就返回NULL。/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead ! NULL);SLTNode* cur pHead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}6.插入功能
6.1 指定位置之前去插入一个节点 此方法是比较笨的方法为了节约资源应该将数据往指定位置的后边插入。/*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead ! NULL);assert(pos ! NULL);SLTNode* newNode CreatListNode(x);if (*ppHead pos)/*pos的位置在第一个位置时*/{newNode-next *ppHead;*ppHead newNode;}else{/*找到pos位置的前一个位置*/SLTNode* posPrev *ppHead;while (posPrev-next ! pos){posPrev posPrev-next;}posPrev-next newNode;newNode-next pos;}return NULL;
}6.2 指定位置之后去插入一个节点 此方法是常用的插入方式时间复杂度是O(1)。/*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos ! NULL);SLTNode* newNode CreatListNode(x);newNode-next pos-next;pos-next newNode;return NULL;
}7.删除功能
7.1 删除指定位置的数据-时间复杂度O(N) 此方法需要记住当前节点前一个的节点地址会多耗费时间资源时间复杂度O(N)。SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead ! NULL);assert(pos ! NULL);/*如果删除的数据是头*/if (*ppHead pos){SListPopFront(ppHead);}else{SLTNode* prev *ppHead;while (prev-next ! pos)/*找到pos前一个节点*/{prev prev-next;}prev-next pos-next;free(pos);pos NULL;}return NULL;
}7.2 删除指定位置后一个位置的数据-时间复杂度O(1) 此方法需要记住当前节点前一个的节点地址会多耗费时间资源时间复杂度O(1)。/*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos-next ! NULL);SLTNode* next pos-next;pos-next next-next;free(next);next NULL;return NULL;
}8. 释放链表缓存 思路将下一个节点的地址先记住然后释放当前节点。再将保存的地址赋值到当前节点循环释放缓存。/*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead ! NULL);SLTNode* cur *ppHead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*ppHead NULL;return NULL;
}9. 打印链表的值
/*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur pHead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}return;
}10.此程序共包含3个文件2个.c文件和1个.h文件
10.1 SList.h文件 文件中包含了函数功能的头文件以及对应的结构体。#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;void SListTPrint(SLTNode *pHead); /*打印链表的值*/
void SListPushBack(SLTNode** ppHead, SLTDateType x); /*插入数据-尾插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x); /*插入数据-头插*/void SListPopBack(SLTNode** ppHead); /*尾删*/
void SListPopFront(SLTNode** ppHead); /*头删*/SLTNode* SListFind(SLTNode* pHead, SLTDateType x); /*查找*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x);/*指定位置插入数据-在pos位置之前去插入一个节点*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x); /*指定位置插入数据-在pos位置之后去插入一个节点*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos); /*删除指定位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos); /*删除指定位置后一个位置的数据*/
SLTNode* SListDestory(SLTNode** ppHead); /*释放链表缓存*/SLTNode* CreatListNode(SLTDateType x); /*创建一个新的节点*/10.2 SList.c文件 文件中包含了功能函数的具体实现方式。#define _CRT_SECURE_NO_WARNINGS
#include SList.h/*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead ! NULL);/*新结点申请空间*/SLTNode* newNode CreatListNode(x);if (*ppHead NULL){*ppHead newNode;}else{/*找到尾结点*/SLTNode* tail *ppHead;while (tail-next ! NULL){tail tail-next;}tail-next newNode;}return;
}/*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead ! NULL);SLTNode* newNode CreatListNode(x);newNode-next *ppHead;*ppHead newNode;return;
}/*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode (SLTNode*)malloc(sizeof(SLTNode));if (NULL newNode){printf(CreatListNode malloc fail\n);exit(-1);}newNode-data x;newNode-next NULL;return newNode;
}/*尾删*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead ! NULL);/*如果只有一个节点时直接释放此节点*/if ((*ppHead)-next NULL){free(*ppHead);*ppHead NULL;}else/*存在2个及2个以上节点的处理方式*/{SLTNode* tail *ppHead;SLTNode* pre NULL;while (tail-next ! NULL){pre tail;tail tail-next;}pre-next NULL;free(tail);tail NULL;}return;
}/*头删*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead ! NULL);SLTNode* next (*ppHead)-next;free(*ppHead);*ppHead next;return;
}/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead ! NULL);SLTNode* cur pHead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}/*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead ! NULL);assert(pos ! NULL);SLTNode* newNode CreatListNode(x);if (*ppHead pos)/*pos的位置在第一个位置时*/{newNode-next *ppHead;*ppHead newNode;}else{/*找到pos位置的前一个位置*/SLTNode* posPrev *ppHead;while (posPrev-next ! pos){posPrev posPrev-next;}posPrev-next newNode;newNode-next pos;}return NULL;
}/*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos ! NULL);SLTNode* newNode CreatListNode(x);newNode-next pos-next;pos-next newNode;return NULL;
}/*删除指定位置的数据--时间复杂度O(N)*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead ! NULL);assert(pos ! NULL);/*如果删除的数据是头*/if (*ppHead pos){SListPopFront(ppHead);}else{SLTNode* prev *ppHead;while (prev-next ! pos)/*找到pos前一个节点*/{prev prev-next;}prev-next pos-next;free(pos);pos NULL;}return NULL;
}/*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos-next ! NULL);SLTNode* next pos-next;pos-next next-next;free(next);next NULL;return NULL;
}/*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead ! NULL);SLTNode* cur *ppHead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*ppHead NULL;return NULL;
}/*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur pHead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}return;
}10.3 test.c文件 用来进行相应功能的测试分别测试尾插、尾删和头插、头删等功能。#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include SList.hvoid Test1()
{SLTNode* SList NULL;/*尾插*/SListPushBack(SList, 1);SListPushBack(SList, 2);SListPushBack(SList, 3);SListPushBack(SList, 4);/*尾删*/SListPopBack(SList);/*打印链表*/SListTPrint(SList);printf(NULL\n);return;
}void Test2()
{SLTNode* SList NULL;/*头插*/SListPushFront(SList, 1);SListPushFront(SList, 2);SListPushFront(SList, 3);/*头删*/SListPopFront(SList);/*打印*/SListTPrint(SList);printf(NULL);return;
}void Test3()
{SLTNode* SList NULL;SLTNode* pos NULL;int i 1;/*尾插*/SListPushBack(SList, 1);SListPushBack(SList, 5);SListPushBack(SList, 2);SListPushBack(SList, 3);SListPushBack(SList, 2);/*查找数字的位置*/pos SListFind(SList, 2);while (pos)/*查找到数据为2的节点的地址*/{printf(第%d个pos节点的:%p-%d\n, i, pos-next, pos-data);if (pos-next){pos SListFind(pos-next, 2);}else/*为空指针时直接跳出循环*/{break;}}/*改变对应节点位置的数据,将5位置前边的位置添加个20*/pos SListFind(SList, 5);if (pos)/*在5的位置之前插入20*/{SListInsert(SList, pos, 20);}pos SListFind(SList, 5);if (pos)/*在5的位置之后插入100*/{SListInsertAfter(pos, 100);}/*打印*/SListTPrint(SList);printf(NULL);return;
}int main()
{Test1();/*尾插尾删*///Test2();/*头插头删*///Test3(); /*指定位置前插入、后插入、寻找指定数据节点的位置*/return 0;
}这里代码大家可以自己拷贝到VS编译器中Test1()Test2()Test3()分别打开注释看一下效果本人亲测过可以直接运行出结果的。
