当前位置：首页 > news >正文

链表：C++实现

news 2025/8/20 15:54:19

引言：

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组，链表具有动态性和灵活性，可以高效地进行插入和删除操作，但是查找操作的时间复杂度较高。在C++中，我们可以通过定义一个节点结构体和一个链表类来实现链表。

技术实现：

首先，我们定义一个节点结构体Node，包含一个数据元素data和一个指向下一个节点的指针next。这里使用了模板typename Element，表示可以存储任意类型的数据元素。

template<typename Element>
struct Node
{Element data;Node<Element>* next;
};

接下来，我们定义一个链表类LinkList，包含一些常用的操作函数。构造函数LinkList()用于创建一个空链表，构造函数LinkList(Element a[], int n)用于创建一个包含n个元素的链表，析构函数~LinkList()用于释放链表的内存空间。getlenth()函数用于获取链表的长度，getItem(int i)函数用于获取链表中第i个元素，locate(Element x)函数用于查找元素x在链表中的位置，insert(int i, Element x)函数用于在链表中第i个位置插入元素x，remove(int i)函数用于删除链表中第i个元素，empty()函数用于判断链表是否为空，printList()函数用于打印链表中所有元素。

template<typename Element>
class LinkList
{
public:LinkList();LinkList(Element a[], int n);~LinkList();int getlenth();Element getItem(int i);int locate(Element x);void insert(int i, Element x);Element remove(int i);bool empty();void printList();
private:Node<Element>* head;
};

在LinkList类的实现中，我们需要注意一些细节。首先，在构造函数LinkList()中，我们需要将头指针head初始化为空指针。在构造函数LinkList(Element a[], int n)中，我们需要依次创建n个节点，并将它们连接起来。在析构函数~LinkList()中，我们需要依次删除所有节点，并释放它们的内存空间。在insert(int i, Element x)函数中，我们需要先找到第i-1个节点，然后插入新节点，并将它的next指针指向第i个节点。在remove(int i)函数中，我们需要先找到第i-1个节点，然后将它的next指针指向第i+1个节点，并删除第i个节点。

template<typename Element>
LinkList<Element>::LinkList() {head = new Node<Element>;head->next = nullptr;
}//头插法初始化
template<typename Element>
LinkList<Element>::LinkList(Element a[], int n) {head->next = nullptr;for (int i = 0; i < n; i++) {LinkList s;s->data = a[i];s->next = head->next;head->next = s;}
}template<typename Element>
LinkList<Element>::~LinkList() {while (head->next != nullptr) {Element* p = head->next;head->next = p->next;delete p;}
}template<typename Element>
int LinkList<Element>::getlenth() {int count = 0;LinkList* p = head->next;while (p != nullptr) {count++;p = p->next;}return count;
}template<typename Element>
Element LinkList<Element>::getItem(int i) {int j = 0;LinkList* p = head->next;while (j < i) {j++;p = p->next;if (p == nullptr) {printf( "不存在\n");break;}}return p->data;
}template<typename Element>
int LinkList<Element>::locate(Element x) {LinkList* p = head->next;int j = 0;while (p != nullptr) {j++;p = p->next;if (p ->data== x) {return j;}}}template<typename Element>
void LinkList<Element>::insert(int i, Element x) {LinkList* p = head;int j = 0;while (p != nullptr && j < i - 1) {p = p->next;j++;}if (p == nullptr) printf("插入位置异常\n");else {LinkList s;s->data = x;s->next = p->next;p->next = s;}
}template<typename Element>
Element LinkList<Element>::remove(int i) {LinkList p = head;int j = 0;while (p != nullptr && j < i - 1) {p = p->next;j++;}if (p == nullptr || p->next == nullptr) {printf( "删除位置异常\n");}else {LinkList q = p->next;int x = q->data;p->next = q->next;delete q;return x;}
}template<typename Element>
bool LinkList<Element>::empty() {return head->next == nullptr;
}template<typename Element>
void LinkList<Element>::printList() {LinkList p = head->next;while (p != nullptr ) {printf("%d ", p->data);p = p->next;}printf( "\n");
}

最后，我们可以在主函数中进行链表的测试。例如，创建一个包含5个元素的链表，插入一个元素，删除一个元素，并打印链表中所有元素。

int main()
{int a[] = { 1, 2, 3, 4, 5 };LinkList<int> list(a, 5);list.printList(); // 1 2 3 4 5list.insert(3, 6);list.printList(); // 1 2 6 3 4 5list.remove(4);list.printList(); // 1 2 6 4 5return 0;
}