谷歌网站统计,重庆有哪些互联网大厂,广州市企业网站建设平台,用cms织梦做网站图文教程C实现链表 众所周知#xff0c;C/C语言实现的链表是由一个一个的结点构成#xff0c;每个结点分为数据域和指针域#xff0c;指针域中存储了其后继结点的地址#xff0c;通过地址来访问下一个结点。
链表是一系列节点串联形成的数据结构#xff0c;链表存储有序的元素集合…C实现链表 众所周知C/C语言实现的链表是由一个一个的结点构成每个结点分为数据域和指针域指针域中存储了其后继结点的地址通过地址来访问下一个结点。
链表是一系列节点串联形成的数据结构链表存储有序的元素集合链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的部分和一个指向下一个元素的链接部分组成。因此链表增删非首尾元素时不需要移动元素只需要更改链接部分的值即可。 本文仅以单链表为例介绍。
单链表每个节点的结构如下 单链表只有一个指向其他节点的变量也就是在这种类型的数据结构中任何两个数据元素之间只有一个链接参见下图 链表的操作包括了创建、删除、插入、输出等。
创建就是空间的分配将头、尾指针及链表结点个数等初始化。删除和插入根据被操作元素的位置可以细分为头删除插入尾删除插入中间删除插入。
插入操作
头插入实际上是增加一个新节点然后把新增加的结点指针指向原来头指针指向的元素再把头指针指向新增的节点。 尾插入也是增加一个新节点该节点指针置为null然后把原尾结点指针指向新增加的节点最后把尾指针指向新增加的节点即可。 中间插入稍复杂首先增加一个节点然后新增节点的指针指向插入位置的后一个节点把插入位置的前一个节点指针指向新插入节点即可。 删除操作
删除头元素时先将头指针指向下一个节点然后把原头结点的指针置空即可。 删除尾元素时首先找到链表倒数第2个元素然后把尾指针指向这个元素接着把原倒数第2个元素的指针置空。 删除中间元素相对复杂一些首先将要删除的节点的前一个节点指针指向要删除的节点的下一个节点然后把要删除节点的指针置空。 上面提到是单链表最基本的操作除此之外还有其它操作不多说了。下面给出代码示例。本文介绍两种实现方法一、使用指针自定义实现二、使用C STL标准模板库中的list容器实现。 一、使用指针自定义实现
先看一个简单点的示例源码 // 插入
// 将x插入到以head为头节点的pos位置上
void insert(node* head, int pos, int x){node *phead;for(int i0;ipos-1;i){//比如要插到第三个位置从0开始的话就是下标为2前一个下标为1 pp-next;// 1 3-1 }node* qnew node;q-datax;q-nextp-next;p-nextq;
} //删除
//删除所有值为x的数
void del(node* head, int x){node* p head-next;node* prehead;while(p!NULL){if(p-datax){pre-nextp-next;delete(p);ppre-next;}else{prep;pp-next;}}
}//查找
//查找链表中有几个x返回count值
int search(node *head, int x){int count0;node *phead-next;while(p!NULL){if(p-datax){count;}pp-next; } return count;
} //排序
//冒泡排序
void sort(node *head){for(node *temphead-next;temp-next!NULL;temptemp-next){for(node *phead-next;p-next!NULL;pp-next){if(p-data p-next-data){int tp-data;p-datap-next-data;p-next-datat;}}}
} int main(){int array[5]{6,3,9,1,2};node* Lcreate(array); //返回头节点L //insert(L, 3, 8); //插入后结果为6,3,8,9,12 //del(L, 9); //删除后结果为6,3,1,2 int y9; int xsearch(L, y);cout查找到 x 个yendl;//sort(L); //排序 //遍历打印 LL-next; //头节点L是没有数据域的下个结点才有 while(L ! NULL){coutL-data ;LL-next;} return 0;
}运行输出 再给出一个较完善的示例源码如下
// 单链表.cpp: #includeiostream
using namespace std;typedef int DataType;
#define Node ElemType//构建一个节点类
class Node
{
public:int data; //数据域Node * next; //指针域
};//构建一个单链表类
class LinkList
{
public:LinkList(); //构建一个单链表;~LinkList(); //销毁一个单链表;void CreateLinkList(int n); //创建一个单链表void TravalLinkList(); //遍历线性表int GetLength(); //获取线性表长度bool IsEmpty(); //判断单链表是否为空ElemType * Find(DataType data); //查找节点void InsertElemAtEnd(DataType data); //在尾部插入指定的元素void InsertElemAtIndex(DataType data,int n); //在指定位置插入指定元素void InsertElemAtHead(DataType data); //在头部插入指定元素void DeleteElemAtEnd(); //在尾部删除元素void DeleteAll(); //删除所有数据void DeleteElemAtPoint(DataType data); //删除指定的数据void DeleteElemAtHead(); //在头部删除节点
private:ElemType * head; //头结点
};//初始化单链表
LinkList::LinkList()
{head new ElemType; head-data 0; //将头结点的数据域定义为0head-next NULL; //头结点的下一个定义为NULL
} //销毁单链表
LinkList::~LinkList()
{delete head; //删除头结点
} //创建一个单链表
void LinkList::CreateLinkList(int n)
{ElemType *pnew, *ptemp;ptemp head;if (n 0) { //当输入的值有误时处理异常cout 输入的节点个数有误 endl; }for (int i 0; i n;i) { //将值一个一个插入单链表中pnew new ElemType;cout 请输入第 i 1 个值: ;cin pnew-data;pnew-next NULL; //新节点的下一个地址为NULLptemp-next pnew; //当前结点的下一个地址设为新节点ptemp pnew; //将当前结点设为新节点}
}//遍历单链表
void LinkList::TravalLinkList()
{if (head NULL || head-next NULL) {cout 链表为空表 endl;}ElemType *p head; //另指针指向头结点while (p-next ! NULL) //当指针的下一个地址不为空时循环输出p的数据域{p p-next; //p指向p的下一个地址cout p-data ;}
}//获取单链表的长度
int LinkList::GetLength()
{int count 0; //定义count计数ElemType *p head-next; //定义p指向头结点while (p ! NULL) //当指针的下一个地址不为空时count1{count; p p-next; //p指向p的下一个地址}return count; //返回count的数据
}//判断单链表是否为空
bool LinkList::IsEmpty()
{if (head-next NULL) { return true;}return false;
}//查找节点
ElemType * LinkList::Find(DataType data)
{ElemType * p head;if (p NULL) { //当为空表时报异常cout 此链表为空链表 endl;return NULL;}else{while (p-next ! NULL) //循环每一个节点{if (p-data data) {return p; //返回指针域}p p-next;}if (p-data data) { return p; }return NULL; //未查询到结果}
}//在尾部插入指定的元素
void LinkList::InsertElemAtEnd(DataType data)
{ElemType * newNode new ElemType; //定义一个Node结点指针newNodenewNode-next NULL; //定义newNode的数据域和指针域newNode-data data;ElemType * p head; //定义指针p指向头结点if (head NULL) { //当头结点为空时设置newNode为头结点head newNode;}else //循环知道最后一个节点将newNode放置在最后{while (p-next ! NULL){p p-next;}p-next newNode;}
}//在指定位置插入指定元素
void LinkList::InsertElemAtIndex(DataType data,int n)
{if (n1 || nGetLength()) //输入有误报异常cout 输入的值错误 endl;else{ElemType * ptemp new ElemType; //创建一个新的节点ptemp-data data; //定义数据域ElemType * p head; //创建一个指针指向头结点int i 1;while (n i) //遍历到指定的位置{p p-next;i;}ptemp-next p-next; //将新节点插入到指定位置p-next ptemp;}
}//在头部插入指定元素
void LinkList::InsertElemAtHead(DataType data)
{ElemType * newNode new ElemType; //定义一个Node结点指针newNodenewNode-data data;ElemType * p head; //定义指针p指向头结点if (head NULL) { //当头结点为空时设置newNode为头结点head newNode;}newNode-next p-next; //将新节点插入到指定位置p-next newNode;
}//在尾部删除元素
void LinkList::DeleteElemAtEnd()
{ElemType * p head; //创建一个指针指向头结点ElemType * ptemp NULL; //创建一个占位节点if (p-next NULL) { //判断链表是否为空cout 单链表空 endl;}else{while (p-next ! NULL) //循环到尾部的前一个{ptemp p; //将ptemp指向尾部的前一个节点p p-next; //p指向最后一个节点}delete p; //删除尾部节点p NULL;ptemp-next NULL;}
}//删除所有数据
void LinkList::DeleteAll()
{ElemType * p head-next;ElemType * ptemp new ElemType;while (p ! NULL) //在头结点的下一个节点逐个删除节点{ptemp p;p p-next;head-next p;ptemp-next NULL;delete ptemp;}head-next NULL; //头结点的下一个节点指向NULL
}//删除指定的数据
void LinkList::DeleteElemAtPoint(DataType data)
{ElemType * ptemp Find(data); //查找到指定数据的节点位置if (ptemp head-next) { //判断是不是头结点的下一个节点如果是就从头部删了它DeleteElemAtHead();}else{ElemType * p head; //p指向头结点while (p-next ! ptemp) //p循环到指定位置的前一个节点{p p-next;}p-next ptemp-next; //删除指定位置的节点delete ptemp;ptemp NULL; }}//在头部删除节点
void LinkList::DeleteElemAtHead()
{ElemType * p head;if (p NULL || p-next NULL) { //判断是否为空表报异常cout 该链表为空表 endl;}else{ElemType * ptemp NULL; //创建一个占位节点p p-next;ptemp p-next; //将头结点的下下个节点指向占位节点delete p; //删除头结点的下一个节点p NULL;head-next ptemp; //头结点的指针更换}
}//测试函数
int main()
{LinkList l;int i;cout 1.创建单链表(整数类型数据) 2.遍历单链表 3.获取单链表的长度 4.判断单链表是否为空 \n;cout 5.获取节点 6.在尾部插入指定元素 7.在指定位置插入指定元素 8.在头部插入指定元素\n;cout 9.在尾部删除元素 10.删除所有元素 11.删除指定元素 12.在头部删除元素 0.退出 endl;cout -------- endl;do{cout 请输入要执行的操作: ;cin i;switch (i){case 1:int n;cout 请输入单链表的长度: ;cin n;l.CreateLinkList(n);break;case 2:l.TravalLinkList();break;case 3:cout 该单链表的长度为 l.GetLength() endl;break;case 4:if (l.IsEmpty() 1)cout 该单链表是空表 endl;else{cout 该单链表不是空表 endl;}break;case 5:DataType data;cout 请输入要获取节点的值: ;cin data;cout 该节点的值为 l.Find(data)-data endl;break;case 6:DataType endData;cout 请输入要在尾部插入的值: ;cin endData;l.InsertElemAtEnd(endData);break;case 7:DataType pointData;int index;cout 请输入要插入的数据: ;cin pointData;cout 请输入要插入数据的位置: ;cin index;l.InsertElemAtIndex(pointData, index);break;case 8:DataType headData;cout 请输入要在头部插入的值: ;cin headData;l.InsertElemAtHead(headData);break;case 9:l.DeleteElemAtEnd();break;case 10:l.DeleteAll();break;case 11:DataType pointDeleteData;cout 请输入要删除的数据: ;cin pointDeleteData;l.DeleteElemAtPoint(pointDeleteData);break;case 12:l.DeleteElemAtHead();break;default:break;}}while (i ! 0);system(pause);return 0;
}运行结果 二、使用C STL标准模板库中的list容器实现
C STL标准模板库是一套功能强大的 C 模板类提供了通用的模板类和函数这些模板类和函数可以实现多种流行和常用的算法和数据结构如向量、链表、队列、栈。
STL list 容器又称双向链表容器即该容器的底层是以双向链表的形式实现的。
std::list_C中文网
要用list容器必须声明请头文件#include list。
Dev C 5.11及其之前的版本默认是不支持c11新标准的解决方案也很简单在菜单栏点开Tools - Compile Options添加编译指令-stdc11即可参见下图 下面给出示例源码 #include iostream
#include list
using namespace std;
int main(){listint l;coutlist的大小:l.size()endl;//list的大小:0for (int i0; i10; i)l.push_back(i); //尾部插入元素 尾插法coutlist的大小:l.size()endl;//list的大小:10listint::iterator it l.begin();while(it!l.end()){cout*it ;it;}cout endl;//0 1 2 3 4 5 6 7 8 9//list不能随机访问容器中的值即不能it5这样的操作。只能一个一个的走即ititl.begin();it;it;it;l.insert(it, 100); //100插入在链表第4个位置for (listint::iterator it l.begin(); it ! l.end(); it)cout*it ;coutendl;//0 1 2 100 3 4 5 6 7 8 9l.clear(); coutlist的大小:l.size()endl;//list的大小:0for (int i0; i10; i)l.push_front(i); //尾部插入元素 尾插法coutlist的大小:l.size()endl;//list的大小:10for(listint::iterator itl.begin(); it!l.end(); it)cout*it ;coutendl; //9 8 7 6 5 4 3 2 1 0listint::iterator it1 l.begin();listint::iterator it2 l.begin();it2;it2;it2;//要想删除一个区间段。只能用指针一步一步的指向那个末尾位置不能直接l.begin()3l.erase(it1, it2); //删掉的是区间[it1,it2) for (listint::iterator itl.begin(); it!l.end(); it)cout*it ;coutendl;//6 5 4 3 2 1 0l.insert(l.begin(), 100);l.insert(l.begin(), 100);l.insert(l.begin(), 100);l.erase(l.begin()); //删除该位置的元素for (listint::iterator itl.begin(); it!l.end(); it)cout*it ;coutendl;//100 100 6 5 4 3 2 1 0cout链表中的第一个元素l.front()endl; //链表中的第一个元素100cout链表中的最后一个元素l.back()endl; //链表中的最后一个元素0l.remove(100); //移除所有100元素的值 removefor (listint::iterator itl.begin(); it!l.end(); it)cout*it ;coutendl;//6 5 4 3 2 1 0
}运行之
