锐客网

  1. 首页 > it技术 > >

c++|单链表的增删改查操作（代码完整）

c++单链表

说明：由于vc6对模板类的支持不友好，所以使用了 测试使用了 int 类型。
优点：
1.克服了顺序表的缺点，动态存储分配来存储线性表。链接存储结构
【c++|单链表的增删改查操作（代码完整）】2.插入和删除元素，只需要修改指针，不需要移动元素。
缺点：
1.指针的结构性开销
2.存取表中的任一元素不方便，只能顺序存取。（必须从头指针开始访问）

头文件：函数的声明

#include #include using namespace std; struct Node { int data; Node *next; }; class CLinkList { public: CLinkList(); //无参数的构造函数 virtual ~CLinkList(); CLinkList(int a[], int n); //有参析构函数，建立只有头结点的空链表 int Length(); //求单链表的长度 int Get(int i); //按位查找，在单链表中查找第I个结点的元素值 int Locate(int x); //按值查找，在单链表中查找值x的元素序号 int Insert(int i, int x); //插入操作，在第I个位置插入元素值为x的结点 int Delete(int i); //删除查找，在单链表中删除第I个结点 void Modify(int i, int x); //修改操作，修改第I个 void PrintList(); //遍历操作，按序号依次输出元素 private: Node *first; //单链表的头指针 };


.cpp文件
#include "LinkList.h" #include #include //使用setw 需要include iomanip //使用NULL需要include windows CLinkList::CLinkList() { first = new Node; //生成头节点 first->next = NULL; //头节点的指针域置空 }CLinkList::~CLinkList() { while(first != NULL)//释放单链表的每一个结点的存储空间 { Node *q = first; //暂存被删除结点 first = first->next; //first指向被释放的节点的下一个节点 delete q; } }//头插法：新节点插在头节点的后面 CLinkList::CLinkList(int a[], int n) { first = new Node; //生成头节点 first->next = NULL; //头节点的指针域置空 for (int i = 0; i < n; i++) { Node *s = new Node; //为数组每个元素建立一个节点 s->data = https://www.it610.com/article/a[i]; s->next = first->next; //将结点s插入到头节点之后 first->next = s; } }//尾插法：新节点插在头节点的后面 //CLinkList::CLinkList(int a[], int n) //{ // Node int first = new Node; //生成头节点 // Node r = first; //尾指针初始化// for (int i = 0; i < n; i++) { //Node s = new Node; //为数组每个元素建立一个节点 //s->data = https://www.it610.com/article/a[i]; //r->next = s; //将结点s插入到尾节点之后 //r = s; // } // r->next = NULL; //单链表建立完毕，将终端节点的指针域置空 //}//打印链表的值 //时间复杂度O（n） void CLinkList::PrintList() { Node *p; p = first->next; //工作指针初始化 if (!p) cout<<"单链表为空"; while(p!= NULL) { coutnext; //工作指针后移，不能p++ } }//链表长度 int CLinkList::Length() { Node *p; p = first->next; //工作指针初始化 int count = 0; while(p!= NULL) { coutnext; //工作指针后移，不能p++ count++; } return count; }//按序号查找 //平均时间性能为O(N)，为顺序存取结构 int CLinkList::Get(int i) { Node *p; p = first->next; //工作指针初始化 int count = 1; while(p!= NULL && count < i) { p = p->next; //工作指针后移，不能p++ count++; } if (p == NULL) throw "位置错误"; else return p->data; }//按值查找 int CLinkList::Locate(int x) { Node *p; p = first->next; //工作指针初始化 int count = 1; while(p!= NULL) { if (p->data =https://www.it610.com/article/= x) return count; //查找成功，结束并返回序号 p = p->next; //工作指针后移，不能p++ count++; } return 0; //退出循环表明查找失败 }//插入操作 //找到要插入位置的前一个位置 //把前一个位置的next 给 新结点的next //把前一个位置的next 指向新结点 int CLinkList::Insert(int i, int x) { Node *p; p = first->next; //工作指针初始化 int count = 0; while(p!= NULL && count < i - 1) //查找第i个结点 { p = p->next; //工作指针后移，不能p++ count++; } if (p == NULL) throw "位置错误"; else { Node *s = new Node; s->data = https://www.it610.com/article/x; //申请一个新结点 s->next = p->next; p->next = s; //将结点s插入到节点p之后 } return 0; //退出循环表明查找失败 }//删除操作 int CLinkList::Delete(int i) { Node *p; p = first->next; //工作指针初始化 int count = 0; while(p!= NULL && count < i - 1) //查找第i个结点 { p = p->next; //工作指针后移，不能p++ count++; } if (p == NULL || p->next == NULL) throw "位置错误"; //节点P不存在或后继节点不存在 else { Node *q = p->next; //暂存 int x = q->data; p->next = q->next; //摘链 delete q; return x; } }

测试
#include #include using namespace std; #include "LinkList.h" int main() { int a[7] = {1, 2, 3, 4, 5, 6, 7}; cout<<"单链表的初始化"<

c++|单链表的增删改查操作（代码完整）
文章图片

    推荐阅读


    上一篇：android面试准备|四大组件的工作原理《Android开发艺术探索》笔记

    下一篇：微信小程序 异步阻塞（Promise、resolve，await，then）