wap手机网站开发软件,可以做片头的网站,软件工程师的工作内容,电子商务网站建设与管理考试例题无头单向非循环链表的建立 前言——什么链表链表形象图链表分类 一、Single_linked_list.h头文件的建立二、Single_linked_list.c功能函数的定义Single_linked_list_test.c主函数的定义四、代码运行测试五、Single_linked_list完整代码演示#xff1a;总结 前言——什么链表 链… 无头单向非循环链表的建立 前言——什么链表链表形象图链表分类 一、Single_linked_list.h头文件的建立二、Single_linked_list.c功能函数的定义Single_linked_list_test.c主函数的定义四、代码运行测试五、Single_linked_list完整代码演示总结 前言——什么链表 链表的概念及结构概念 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 链表形象图
链表具体表现是怎么样的呢让我们通过下面的图片来了解一下 形象一点形容呢那就像一个车厢相互链接的火车这样好记住多了吧 注意 . 从上图可看出链式结构在逻辑上是连续的但在物理上不一定连续 . 现实中的结点一般是都是从堆上申请来的 . 从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 链表分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 单向或者双向 带头或者不带头 循环或者非循环
虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 无头单向非循环链表
带头双向循环链表 今天我们要实现的是无头单向非循环链表让我们跟随下面的步骤来建立单链表吧
一、Single_linked_list.h头文件的建立 1.头文件的声明 #pragma once
#includestdio.h
#includestdlib.h
#includeassert.h2.单链表的接口实现 typedef int SLTDataType;//类型重命名
//单链表接口定义
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;3.打印函数以及创建结点函数的声明 //打印
void SLTPrint(SLTNode* phead);
//创建结点
SLTNode* BuySListNode(SLTDataType x);4.尾插、头插函数的声明 //尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);5.尾删头删函数的声明 //尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);6.查找函数的声明 SLTNode* SLTFind(SLTNode* phead, SLTDataType x);7.定点pos前后插入函数的声明 // 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode** pphead,SLTNode* pos, SLTDataType x);8.定点删除pos或删除pos后一位结点的函数的声明 // 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);二、Single_linked_list.c功能函数的定义 1.头文件的声明 #include Single_linked_list.h2.打印函数以及创建结点函数的定义 //打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur)//cur!NULL为真{printf(%d , cur-data);cur cur-next;}printf(NULL\n);//打印尾结点的next结点NULL
}//创建结点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//创建一个新结点if (newnode NULL)//创建失败返回错误结束程序{perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;//将新结点的next结点置为NULLreturn newnode;
}3.尾插、头插函数的定义 //尾插
//传入结构体指针用二级指针接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);//调用函数创建新结点//两种情况 头结点为空时和头结点不为空时if (*pphead NULL){// 改变的结构体的指针所以要用二级指针*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL)//遍历链表到尾结点{tail tail-next;}// 改变的结构体用结构体的指针即可tail-next newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;// 改变的结构体的指针所以要用二级指针*pphead newnode;
}4.尾删头删函数的定义 //尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);//判断*pphead是否为空//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else//一个以上节点{SLTNode* tail *pphead;while (tail-next-next)//遍历链表到尾结点{tail tail-next;}free(tail-next);tail-next NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);//判断*pphead是否为空SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
}当然尾删不只一种方法另一种方法就是
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tailPrev NULL;//设置一个前驱结点方便置空SLTNode* tail *pphead;while (tail-next){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}
}5.查找函数的定义 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur phead;while (cur ! NULLcur-data ! x ) {cur cur-next;}if (cur NULL) {printf(未查找到有效结点\n);exit(-1);}return cur;
}6.定点pos前后插入函数的定义 // 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {SLTNode* newnode BuySListNode(x);SLTNode* curPrev *pphead;SLTNode* cur SLTFind(curPrev,pos-data);if (curPrev cur) {newnode-next *pphead;*pphead newnode;}else {while (curPrev-next ! cur) {curPrev curPrev-next;}newnode-next cur;curPrev-next newnode;}
}// 在pos以后插入x
void SLTInsertAfter(SLTNode** pphead,SLTNode* pos, SLTDataType x) {SLTNode* newnode BuySListNode(x);SLTNode* temp *pphead;SLTNode* cur SLTFind(temp, pos-data);newnode-next cur-next;cur-next newnode;
}7.定点删除pos或删除pos后一位结点的函数的定义 // 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos) {SLTNode* temp *pphead;SLTNode* curPrev *pphead;SLTNode* cur SLTFind(temp, pos-data);if (curPrev cur) {temp cur-next;free(cur);cur temp;}else {while (curPrev-next ! cur) {curPrev curPrev-next;}curPrev-next cur-next;free(cur);cur NULL;}
}// 删除pos的后一个位置
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {SLTNode* temp *pphead;SLTNode* cur SLTFind(temp, pos-data);if (cur-next NULL) {return;}else {temp cur-next;cur-next temp-next;free(temp);temp NULL;}
}Single_linked_list_test.c主函数的定义 1.头文件的声明 #include Single_linked_list.h2.测试调用函数的定义 void TestSList() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);SLTNode* pos BuySListNode(3);SLTInsert(plist,pos, 6);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTInsertAfter(plist, pos, 7);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(6);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(7);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(1);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);
}3.主函数的定义 int main()
{TestSList();return 0;
}四、代码运行测试
示例一
void TestSList2()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);
}运行结果 示例二
void TestSList3()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);}运行结果 示例三
void TestSList5() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTNode* pos BuySListNode(3);SLTInsert(plist,pos, 6);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTInsertAfter(plist, pos, 7);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(6);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(7);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(1);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);
}运行结果
五、Single_linked_list完整代码演示
Single_linked_list.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;//类型重命名
//单链表接口定义
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);
//创建结点
SLTNode* BuySListNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 在pos以后插入x
void SLTInsertAfter(SLTNode** pphead,SLTNode* pos, SLTDataType x);// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);Single_linked_list.c
#include Single_linked_list.h//打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur)//cur!NULL为真{printf(%d , cur-data);cur cur-next;}printf(NULL\n);//打印尾结点的next结点NULL
}//创建结点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//创建一个新结点if (newnode NULL)//创建失败返回错误结束程序{perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;//将新结点的next结点置为NULLreturn newnode;
}//尾插
//传入结构体指针用二级指针接收
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);//调用函数创建新结点//两种情况 头结点为空时和头结点不为空时if (*pphead NULL){// 改变的结构体的指针所以要用二级指针*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL)//遍历链表到尾结点{tail tail-next;}// 改变的结构体用结构体的指针即可tail-next newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;// 改变的结构体的指针所以要用二级指针*pphead newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);//判断*pphead是否为空//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else//一个以上节点{SLTNode* tail *pphead;while (tail-next-next)//遍历链表到尾结点{tail tail-next;}free(tail-next);tail-next NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);//判断*pphead是否为空SLTNode* newhead (*pphead)-next;free(*pphead);*pphead newhead;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur phead;while (cur ! NULLcur-data ! x ) {cur cur-next;}if (cur NULL) {printf(未查找到有效结点\n);exit(-1);}return cur;
}// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {SLTNode* newnode BuySListNode(x);SLTNode* curPrev *pphead;SLTNode* cur SLTFind(curPrev,pos-data);if (curPrev cur) {newnode-next *pphead;*pphead newnode;}else {while (curPrev-next ! cur) {curPrev curPrev-next;}newnode-next cur;curPrev-next newnode;}
}// 在pos以后插入x
void SLTInsertAfter(SLTNode** pphead,SLTNode* pos, SLTDataType x) {SLTNode* newnode BuySListNode(x);SLTNode* temp *pphead;SLTNode* cur SLTFind(temp, pos-data);newnode-next cur-next;cur-next newnode;
}// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos) {SLTNode* temp *pphead;SLTNode* curPrev *pphead;SLTNode* cur SLTFind(temp, pos-data);if (curPrev cur) {temp cur-next;free(cur);cur temp;}else {while (curPrev-next ! cur) {curPrev curPrev-next;}curPrev-next cur-next;free(cur);cur NULL;}
}// 删除pos的后一个位置
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) {SLTNode* temp *pphead;SLTNode* cur SLTFind(temp, pos-data);if (cur-next NULL) {return;}else {temp cur-next;cur-next temp-next;free(temp);temp NULL;}
}Single_linked_list_test.c
void TestSList() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTNode* pos BuySListNode(3);SLTInsert(plist,pos, 6);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTInsertAfter(plist, pos, 7);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(6);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(7);SLTErase(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(3);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);pos BuySListNode(1);SLTEraseAfter(plist, pos);free(pos);pos NULL;SLTPrint(plist);
}int main()
{TestSList();return 0;
}总结
无头单项非循环链表是链表的初始内容 有点难度但是不多记住指针与多级指针之间的关系 我相信大家也一定可以写出比我更好的代码
