基于C/C++语言数据结构之线性表（二）

小灰灰 2022-07-16 10:43 180阅读 0赞

## 链表： ##

## 链表的创建与使用： ##

### 插入元素： ###

![20161015194148214][]

### 删除元素： ###

![20161015194202308][]

### 实现链表： ###

#include<iostream>
    // 请在下面实现结点类 Node
    class Node {
    	public:
    		int data;//每节火车车厢人数
    		Node* next;//指向下一节点
    		Node(int _data) {
    			data=_data;
    			next=NULL;
    		}
    };
    
    
    // 请在下面实现链表类 LinkedList
    class LinkedList {
    	private:
    		Node* head;
    	public:
    		LinkedList() {
    			head=NULL;
    		}
    		~LinkedList() {
    			Node* current_node=head;
    			while(current_node!=NULL) {
    				Node* delete_node=current_node;
    				current_node=current_node->next;
    				delete delete_node;
    			}
    
    
    		}
    };
    int main() {
    	LinkedList linkedlist;
    	return 0;
    }

### 实现插入方法 insert ###

void insert(Node *node, int index) {
    	if (head == NULL) {
    		//链表为空 直接插入
    		if (index != 0) {//链表为空 但是不是差到第一个元素
    			return;
    		}
    		head = node;
    		return;
    	}
    	if (index == 0) {//插入到第一个元素 作为头节点
    		node->next = head;
    		head = node;
    		return;
    	}
    	Node *current_node = head;
    	int count = 0;
    	while (current_node->next != NULL && count < index - 1) {
    		//后移 移动到目标位置
    		current_node = current_node->next;
    		count++;
    	}
    	if (count == index - 1) {
    		//找到位置进行插入
    		node->next = current_node->next;
    		current_node->next = node;
    	}
    }

###    实现输出方法 output ###

void output() {
    
    
    	if(head==NULL) {
    		return;
    	}
    	Node* current_node=head;
    	while(current_node!=NULL) {
    		// 循环输出
    		cout<<current_node->data<<" ";
    		current_node=current_node->next;
    
    
    	}
    	cout<<endl;
    }

###    实现删除结点方法 delete\_node ###

void delete_node(int index) {
    	if(head==NULL) {
    		return;
    
    
    	}
    	Node* current_node=head;
    	int count=0;
    	if(index==0) {
    		head=head->next;
    		delete current_node;
    		return;
    	}
    	while(current_node->next!= NULL && count<index-1) {
    		current_node=current_node->next;
    		count++;
    	}
    	if(count==index-1 && current_node->next!=NULL) {
    		Node* delete_node=current_node->next;
    		current_node->next=delete_node->next;
    		delete delete_node;
    	}
    }

### 实现链表的反转方法 reverse ###

void reverse() {
    	if(head==NULL) {
    		return;
    	}
    	Node *next_node, *current_node;
    	current_node=head->next;
    	head->next=NULL;
    	while(current_node!=NULL) {
    		next_node=current_node->next;
    		current_node->next=head;
    		head=current_node;
    		current_node=next_node;
    	}
    }

## 循环链表： ##

首先我们来了解 循环链表，相比单链表，循环链表不同的是它将最后一个结点的指针指向了头结点，这样的结构使得链表更加灵活方便。循环链表里没有空指针，所以在判断结束条件时，不再是判断指针是否为空，而是判断指针是否等于某固定指针。另外，在单链表里，一个节点只能访问到它后面的结点，而在循环链表里它可以访问到所有的结点。  
![Center][]

## 双向链表： ##

接下来我们来学习 双向链表，双向链表也叫双链表。单链表里的指针域只记录了结点的下一个结点，也就是后继结点，而双向链表的指针域还记录了结点的上一个结点，也就是前驱结点。有了这样的结构，我们可以从头结点遍历到尾结点，也可以从尾结点遍历到头结点了。  
![Center 1][]  
  
单链表插入元素操作改写为

### 循环列表的插入操作： ###

#include<iostream>
    using std::cin;
    class Node {
    	public:
    		int data;
    		Node* next;
    		Node(int _data) {
    			data = _data;
    			next = NULL;
    		}
    };
    class LinkedList {
    	private:
    		Node* head;
    	public:
    		LinkedList() {
    			head = NULL;
    		}
    		~LinkedList() {
    			if(head==NULL) {
    				return;
    			}
    
    
    			Node *current_node = head->next;
    			head->next=NULL;
    			while (current_node != NULL) {
    				Node *delete_node = current_node;
    				current_node = current_node->next;
    				delete delete_node;
    			}
    		}
    		void insert(Node *node, int index) {
    			if (head == NULL) {
    				if (index != 0) {
    					return;
    				}
    				head = node;
    				head->next=head;
    				return;
    			}
    			if (index == 0) {
    				node->next = head->next;
    				head->next = node;
    				return;
    			}
    			Node *current_node = head->next;
    			int count = 0;
    			while (current_node!=head && count < index - 1) {
    				current_node = current_node->next;
    				count++;
    			}
    			if (count == index - 1) {
    				node->next = current_node->next;
    				current_node->next = node;
    			}
    			if(node==head->next) {
    				head=node;
    			}
    		}
    };
    int main() {
    	LinkedList linkedlist;
    	int n,m;
    	cin>>n>>m;
    	for(int i=1; i<=n; i++) {
    		Node* node=new Node(i);
    		linkedlist.insert(node,i-1);
    	}
    	return 0;
    }

### 循环删除链表元素： ###

#include<iostream>
    using std::cin;
    using std::cout;
    using std::endl;
    class Node {
    	public:
    		int data;
    		Node* next;
    		Node(int _data) {
    			data = _data;
    			next = NULL;
    		}
    };
    class LinkedList {
    	private:
    		Node* head;
    	public:
    		LinkedList() {
    			head = NULL;
    		}
    		~LinkedList() {
    			if (head == NULL) {
    				return;
    			}
    			Node *current_node = head->next;
    			head->next = NULL;
    			while (current_node != NULL) {
    				Node *delete_node = current_node;
    				current_node = current_node->next;
    				delete delete_node;
    			}
    		}
    		void insert(Node *node, int index) {
    			if (head == NULL) {
    				if (index != 0) {
    					return;
    				}
    				head = node;
    				head->next = head;
    				return;
    			}
    			if (index == 0) {
    				node->next = head->next;
    				head->next = node;
    				return;
    			}
    			Node *current_node = head->next;
    			int count = 0;
    			while (current_node != head && count < index - 1) {
    				current_node = current_node->next;
    				count++;
    			}
    			if (count == index - 1) {
    				node->next = current_node->next;
    				current_node->next = node;
    			}
    			if (node == head->next) {
    				head = node;
    			}
    		}
    		// 请在下面实现输出方法 output_josephus
    		void output_josephus(int m) {
    			Node* current_node=head;
    			head=NULL;
    			while(current_node->next!=current_node) {
    				for(int i=1; i<m; i++) {
    					current_node=current_node->next;
    
    
    				}
    				cout<<current_node->next->data<<" ";
    				Node* delete_node=current_node->next;
    				current_node->next=current_node->next->next;
    				delete delete_node;
    
    
    			}
    			cout<<current_node->data<<endl;
    			delete current_node;
    		}
    
    
    };
    int main() {
    	LinkedList linkedlist;
    	int n, m;
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) {
    		Node *node = new Node(i);
    		linkedlist.insert(node, i - 1);
    	}
    	linkedlist.output_josephus(m);
    	return 0;
    }

## 版权说明 ##

发表日期：2016年10月15日   
本文链接：[http://blog.csdn.net/qq\_26816591/article/details/52824794][http_blog.csdn.net_qq_26816591_article_details_52824794]

来源：CSDN   
更多内容：基于C/C++语言数据结构之线性表（一）

编译运行环境：dev-c++

[20161015194148214]: /images/20220716/569284aaa98647cb9a3068f6da20cae2.png
[20161015194202308]: /images/20220716/e4f00fbd944c4ad585430151e8f0f085.png
[Center]: /images/20220716/4514903ede8a48e5bed71bd87cda1500.png
[Center 1]: /images/20220716/9954e211b15e451fbf1783311cc64b68.png
[http_blog.csdn.net_qq_26816591_article_details_52824794]: http://blog.csdn.net/qq_26816591/article/details/52824794