数据结构单链表 C

亦凉 2022-04-22 09:34 259阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

// ------SingleLinkedList.h------// Implement Single Linked List.// Time complexities of find an element, insert an element, remove an element, copy a single linked list and clear single linked list are all O(n).// Decrease the dependencies between member functions as far as possible when design the class.#ifndef SINGLELINKEDLIST_H#define SINGLELINKEDLIST_Htemplate<class T>struct Node{
          T data; Node<T> *next;};template<class T>class SingleLinkedList{
         public: SingleLinkedList(); SingleLinkedList(const SingleLinkedList<T> &pList); ~SingleLinkedList(); SingleLinkedList<T>& operator=(const SingleLinkedList<T> &pList); void insert_head(const T &element);  // Insert before the head of list. void insert_tail(const T &element);  // Insert at the tail of list. bool first(T &element);  // Get the data of the first node. inline bool getNext(T &element);  // Get the data of the next node. bool find(const T &element);  // Find data. bool retrieve(T &element);  // Retrieve data. bool replace(const T &newElement);  // Change data. bool remove(T &element); bool isEmpty() const; void makeEmpty();private: Node<T> *head; Node<T> *current; inline void deepCopy(const SingleLinkedList<T> &original);};#endif

// ------SingleLinkedList.cpp------#include "SingleLinkedList.h"template<class T>SingleLinkedList<T>::SingleLinkedList(){ head = current = NULL;}template<class T>SingleLinkedList<T>::SingleLinkedList(const SingleLinkedList<T> &pList){ deepCopy(pList);}template<class T>SingleLinkedList<T>::~SingleLinkedList(){ makeEmpty();}template<class T>SingleLinkedList<T>& SingleLinkedList<T>::operator =(const SingleLinkedList<T> &pList){ if(this == &pList) {  return this; } makeEmpty(); deepCopy(pList); return this;}// Insert (T &element) at the head of list.template<class T>void SingleLinkedList<T>::insert_head(const T &element){ current = NULL; Node<T> *newNode = new Node<T>; newNode->data = element; newNode->next = head; head = newNode;}// Insert at the tail of list.template<class T>void SingleLinkedList<T>::insert_tail(const T &element){ current = NULL; Node<T> *newNode = new Node<T>; newNode->data = element; newNode->next = NULL; Node<T> *temp; T item; if(head == NULL) {  head = newNode;  temp = head;  return; } temp = head; while(temp->next != NULL) {  temp = temp->next; } temp->next = newNode;}// Put the first node into element, and set the position of the first node current.template<class T>bool SingleLinkedList<T>::first(T &element){ if(head == NULL) {  return false; } current = head; element = head->data; return true;}// Put the node (current->next) into element, and set current to the next node.template<class T>bool SingleLinkedList<T>::getNext(T &element){ if(current == NULL) {  return false; } if(current->next == NULL) {  current = NULL;  return false; } element = current->next->data; current = current->next; return true;}// True if element found; otherwise, false. Current is set in getNext().template<class T>bool SingleLinkedList<T>::find(const T &element){ T item; if(!first(item)) {  return false; } do {  if(item == element)  {   return true;  } }while(getNext(item)); return false;}template<class T>bool SingleLinkedList<T>::retrieve(T &element){ if(!find(element)) {  return false; } element = current->data; return true;}template<class T>bool SingleLinkedList<T>::replace(const T &newElement){ if(current == NULL) {  return false; } current->data = newElement; return true;}template<class T>bool SingleLinkedList<T>::remove(T &element){ current = NULL; if(head == NULL) {  return false; } Node<T> *ptr = head; if(head->data == element) {  element = head->data;  head = ptr->next;  delete ptr;  return true; } while(ptr->next != NULL) {  if(ptr->next->data == element)  {   Node<T> *tempptr = ptr->next;   element = tempptr->data;   ptr->next = tempptr->next;   delete tempptr;   return true;  }  ptr = ptr->next; } return false;}template<class T>bool SingleLinkedList<T>::isEmpty() const{ return head == NULL;}template<class T>void SingleLinkedList<T>::makeEmpty(){ while(head != NULL) {  current = head;  head = head->next;  delete current; } current = NULL;}template<class T>void SingleLinkedList<T>::deepCopy(const SingleLinkedList<T> &original){ head = current = NULL; if(original.head == NULL) {  return; } Node<T> *copyptr = head = new Node<T>; Node<T> *originalptr = original.head; copyptr->data = originalptr->data; if(originalptr == original.current) {  current = copyptr; } while(originalptr->next != NULL) {  copyptr->next = new Node<T>;  originalptr = originalptr->next;  copyptr = copyptr->next;  copyptr->data = originalptr->data;  if(originalptr == original.current)  {   current = copyptr;  } } copyptr->next = NULL;}

// ------Entry Point------#include <iostream>#include "SingleLinkedList.cpp"#include <string>using namespace std;void main(){ string str[6] = {
        "Hello","World","Welcome","To","Beijing"}; // Initialize single linked list. SingleLinkedList<string> strLL; for(int ix=0;ix<5;++ix) {  strLL.insert_tail(str[ix]); } cout << "Traverse single linked list: "; string element; if(strLL.first(element)) {  cout << element << " "; } while(strLL.getNext(element)) {  cout << element << " "; } cout << endl; SingleLinkedList<string> strLL2(strLL); // Invoke constructor SingleLinkedList<string> strLL3 = strLL; // Overload operator "=" strLL2.first(element); cout << "element = " << element << endl; strLL3.first(element); cout << "element = " << element <<endl; if(strLL2.find(str[3])) {  cout << "str[3] = " << str[3] << endl; } if(strLL3.retrieve(str[2])) {  cout << "str[2] = " << str[2] << endl; } if(strLL.remove(str[1])) {  strLL.first(element);  cout << "element after remove is " << element << endl; } if(strLL.isEmpty()) {  cout << "List is Empty!" << endl; } strLL.makeEmpty(); strLL2.makeEmpty(); strLL3.makeEmpty();}// Output:/*Traverse single linked list: Hello World Welcome To Beijingelement = Helloelement = Hellostr[3] = Tostr[2] = Welcomeelement after remove is Hello*/

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220422/9f80c75d523b4db8b5c24c11dc55c55d.png