建立一个单向链表，实现查找、删除、插入功能

建立一个单向链表，实现查找、删除、插入功能

建立一个单向链表，实现查找、删除、插入功能

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、链表是什么？
• 二、建立步骤
• • 1.建立结点类
  • 2.建立链表类
  • 3.测试主函数
• 总结

前言

一、链表是什么？
二、建立步骤
1.建立结点类
2.建立链表类
3.测试主函数

一、链表是什么？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。结点是链表的基本组成单元，而结点中存储的内容，顾名思义就是内容。而结点中的指针，则是链接每个结点，使之成为链表的关键。

二、建立步骤

1.建立结点类

代码如下：

class Link
{
public:int element;Link* next = NULL;
};//结点类

2.建立链表类

class List
{int num;Link* head;//头指针Link* curr;//当前指针Link* last;//尾指针
public:List(){num = 0;head =curr=last= NULL;}~List(){num = 0;while (head){curr = head;head = head->next;delete curr;}}Link* MoveLast()//返回尾指针{curr= head; for(int i=0;i<num-1;i++)curr = curr->next;last = curr;return last;}Link* FindKth(int k){if (k > num || k < 1)cout << "wrong site."<<endl;else{curr = head;for (int i = 0; i < k-1; i++)curr = curr->next;return curr;}}Link* Find(int x){while (curr != NULL && curr->element != x)curr = curr->next;if (curr->element == x)return curr;elsecout << "wrong element."<<endl;}void Append(Link* PtrL)//从尾部加结点{if (head == NULL)head = PtrL;else{curr = MoveLast();curr->next = PtrL;}num++;}void Append(int x)//从尾部加结点(重载）{if (head == NULL){head = new Link;head->element = x;num++;}else{curr = MoveLast();Link* PtrL = new Link;PtrL->element =x;curr->next = PtrL;num++;}}void Insert(int k, Link* PtrL)//从任意位置加结点{if (k<1 || k>num + 1)cout << "wrong site."<<endl;else if (k == 1){PtrL->next = head->next;head = PtrL;num++;}else{curr = FindKth(k-1);PtrL->next = curr->next;curr->next = PtrL;num++;}}void Insert(int k, int x)//从任意位置加结点（重载）{if (k<1 || k>num + 1)cout << "wrong site."<<endl;else if (k == 1){Link* PtrL = new Link;PtrL->element = x;PtrL->next = head;head = PtrL;num++;}else{Link* PtrL = new Link;PtrL->element = x;curr = FindKth(k - 1);PtrL->next = curr->next;curr->next = PtrL;num++;}}void Delete(int k){int i = 1;curr = head;if (k<1 || k>num)cout << "wrong site."<<endl;else if (k == 1){if (head != NULL){head = curr->next;delete curr;num--;}elsecout << "empty." << endl;}else{curr = FindKth(k-1);curr->next = curr->next->next;delete curr;num--;}}void Print(){curr = head;if (head == NULL)cout << "empty";else{while (curr != NULL){cout << curr->element << 't';curr = curr->next;}cout << endl << "The length is " << num << endl;}}};//链表类

3.测试主函数

int main()//测试主函数
{List list1;for (int i = 1; i < 6; i++){Link *link=new Link;link->element = i;list1.Append(link);}//list1.Delete(4);//测试Delete//cout<<list1.FindKth(2)->element<<endl;//测试FindKth//cout << list1.Find(5) << endl;//测试Find//int x;//cin >> x;//list1.Append(x);//测试Append//Link* link = new Link;//link->element = 24;//int k;//cin >> k;//list1.Insert(k, link);//测试Insertint k, x;cin >> k >> x;list1.Insert(k, x);list1.Print();return 0;
}

总结

本文章展示了简单的单向链表的建立，尤其要注意到在删除和插入操作中指针的连接顺序（千万不可以随意更改），要明白其背后的道理。由于建立结点时候需要new开辟空间，为了防止内存的流失，一定要在析构函数中delete掉。

我是刚刚学习数据结构与算法，这是我的第一篇CSDN博客，以后也会不定期地更新，如果有错误，希望大家指出！谢谢大家！