链表 - 源码之家

一、链表

1.链表即为线性表的链式存储结构，逻辑上相邻的元素在物理上不相邻。

2.通过指针来实现元素之间的逻辑关系，一个链表由数据域和指针域构成。

3.相对于顺序表，链表不能实现随机存储，查找元素需要从头开始遍历；但是链表在对元素进行插入和删除操作时，不需要移动元素，并且不需要分配连续的储存空间。

二、链表的实现

链表是一种递归的数据结构，要么为空，要么指向下一个结点。定义一个结点的结构体，结构体包含一个数据值和一个指向下一个结点的指针：

struct LNode 
{    int val;    
     LNode *next;
};

实现简单的增删查改（C++）：

#include<iostream>

using namespace std;

//链表结点结构体定义
struct LNode {
   int val;
   LNode *next;
   //默认构造函数
   LNode():val(0),next(nullptr){}
   //接受一个参数的构造函数
   LNode(int x) :val(x), next(nullptr) {}
};

//创建链表，生成头结点
void create(LNode *l)
{
l->val = 0;
l->next = nullptr;
}

//在表头插入元素
void insert(LNode *l,int e)
{
   LNode *q = new LNode(e);
   q->next = l->next;
   l->next = q;
}

//删除表头元素
void erase(LNode *l, int &e)
{
   if (l->next)
   {
       e = l->next->val;
       l->next = l->next->next;
   }
   else
       cout << "表为空！" << endl;
}

//遍历打印链表元素
void traverse(LNode *l)
{
   LNode *q = l;
   while (q->next)
   {
       cout << q->next->val << " ";
       q = q->next;
   }
   cout << endl;
}

//链表长度
int length(LNode *l)
{
   LNode *q = l;
   int i = 0;
   while (q->next)
   {
       ++i;
       q = q->next;
   }
   return i;
}

//查找第i个元素的值
int find_ith(LNode *l, int i)
{
   int j = 0;
   LNode *q = l;
   while (q->next&&j != i - 1)
   {
       q = q->next;
       ++j;
   }
   if (!q->next)
       return -1;
   return q->next->val;
}

//替换第i个元素的值
void change_ith(LNode *l, int i,int e)
{
   int j = 0;
   LNode *q = l;
   while (q->next&&j != i - 1)
   {
       q = q->next;
       ++j;
   }
   if (!q->next||j>=i)
       cout << "元素不存在！" << endl;
   q->next->val = e;
}

//功能展示：
int main()
{
   LNode *l = new LNode(); //创建头结点
   create(l);
   int e = 0;
   insert(l, 2);
   insert(l, 3);
   insert(l, 4);
   insert(l, 5);
   cout << "链表元素为： " << endl;
   traverse(l);
   erase(l, e);9
   cout << "删除元素为： "<<e << endl;
   cout << "链表元素为： " << endl;
   traverse(l);
   cout << "链表长度为： " << endl;
   cout << length(l) << endl;
   cout << "第2个元素为： "<<find_ith(l, 2) << endl;
   change_ith(l, 2, 5); //替换第二个元素值
   cout << "链表元素为： " << endl;
   traverse(l);
   return 0;
}

程序运行结果：

链表

一、链表

二、链表的实现

相关推荐