使用四种编程语言实现单链表的增删查改
本文接着上一篇文章~
本篇文章仅仅只是为了实现,所以很多地方就不使用条件判断了~
线性表的基本实现和概念C语言
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int data;
struct node* next;
}*Node;
Node head;
void init() {
head = (Node)malloc(sizeof(Node));
head->next = NULL;
head->data = NULL;
}
void add(int data) {
Node temp = (Node)malloc(sizeof(Node));
temp->data = data;
temp->next = head->next;
head->next = temp;
}
void toString() {
//定义一个变量替代遍历,防止破坏原链表的数据
Node temp = head->next;
while (temp != NULL) {
//判断是不是到了最后,如果是最后就省去->
if (temp->next != NULL) {
printf("%d->",temp->data);
}
else {
printf("%d",temp->data);
}
temp = temp->next;
}
}
Node get(int index) {
int i;
Node temp = head->next;
for (i = 0; i <= index; i++) {
temp = temp->next;
}
return temp;
}
void del(int index) {
int i = 0;
Node front, rear;
//调用查找方法找到它
front = get(index);
//开始删除
rear = front->next;
front->next = front->next->next;
}
void replace(int index,int data) {
Node temp = get(index);
temp->data = data;
}
//开始测试
int main(int argc,char *argv[]) {
Node temp;
//先初始化一下单链表
init();
//新增
add(1); add(2); add(3); add(4); add(5); add(6); add(7);
//遍历
toString();
//查找
temp = get(3); printf("\n%d\n",temp->data);
//修改
replace(3, 9); toString();
//删除
del(4); printf("\n"); toString();
return 0;
}
C++语言
#include<iostream>
using namespace std;
//结点
template<class T>
class Node {
public:
T data;
Node<T>* next;
};
//链表操作
template<class T>
class LinkList {
private:
Node<T> *head = new Node<T>();
public:
//清理垃圾
~LinkList() {
delete head;
}
void add(int data) {
Node<T>*temp = new Node<T>();
temp->data = data;
temp->next = head->next;
head->next = temp;
}
void toString() {
//定义一个变量替代遍历,防止破坏原链表的数据
Node<T> *temp = head->next;
while (temp != NULL) {
//判断是不是到了最后,如果是最后就省去->
if (temp->next != NULL) {
printf("%d->", temp->data);
}
else {
printf("%d", temp->data);
}
temp = temp->next;
}
}
Node<T>*get(int index) {
int i;
Node<T>*temp = head->next;
for (i = 0; i <= index; i++) {
temp = temp->next;
}
return temp;
}
void del(int index) {
int i = 0;
Node<T>*front, *rear;
//调用查找方法找到它
front = get(index);
//开始删除
rear = front->next;
front->next = front->next->next;
delete rear;
}
void replace(int index, int data) {
Node<T>*temp = get(index);
temp->data = data;
}
};
int main(int argc,char*argv[]) {
LinkList<int>list;
//增加
for(int i = 1; i < 10; i++)
list.add(i);
//遍历
list.toString(); cout << endl;
//删除
list.del(5); list.toString(); cout << endl;
//修改
list.replace(2, 666); list.toString();
}
Java语言
public class Test {
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
//添加
for(int i = 1; i < 10; i++)
list.add(i);
//遍历
System.out.println(list.toString());
//删除
list.remove(5);
System.out.println(list.toString());
//修改
list.replace(3,999);
System.out.println(list.toString());
}
}
class SingleLinkedList{
private Node head = new Node(); //头节点
public String toString() {
StringBuilder stringBuilder = new StringBuilder("[");
Node p = head.next;
while(p != null){
//看看是不是到了最后
if(p.next != null){
stringBuilder.append(p.data + "->");
}else{
stringBuilder.append(p.data);
}
p = p.next;
}
stringBuilder.append("]");
return stringBuilder.toString();
}
//这里换一种思路,省的代码都一样。。。
public void add(Object object) {
//先让p指向头节点
Node p = head;
//将p移动到最后一个结点
while(p.next != null){
p = p.next;
}
//添加元素
p.next = new Node(object);
}
//删除
public void remove(int index) {
要删除的前一个结点
Node prev = (Node) getNode(index - 1);
//当前要删除的结点
Node currNode = prev.next;
Node nextNode = currNode.next;
prev.next = nextNode;
currNode.next = null;
}
//查找
public Object getNode(int index) {
// 指向了第一个结点
Node p=head.next;
for (int i = 0; i <index ; i++) {
p=p.next;
}
// 返回的是p结点
return p;
}
//修改
public void replace(int index,Object data){
Node temp = (Node)getNode(index);
temp.data = data;
}
//将Node作为单链表的内部类来使用
class Node {
Object data;//存储是数据
Node next;//指向下个节点的指针
public Node() {
}
public Node(Object data) {
this.data = data;
}
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
}
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
}
Python语言
class Node():
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __str__(self):
return 'Node:{}'.format(self.value)
class LinkedList():
def __init__(self):
self.root = Node()
# 记录有多少元素
self.size = 0
# 增加新数据时，将新数据的地址与谁关联
self.next = None
#新增
def append(self, value):
node = Node(value)
# 判断是否已经有数据
if not self.next: # 如果没有节点时
# 将新节点挂到root后面
self.root.next = node
else:
# 将新节点挂到最后一个节点上
self.next.next = node
self.next = node
self.size += 1
def append_first(self, value):
node = Node(value)
if not self.next:
self.root.next = node
self.next = node
else:
# 获取原来root后面的那个节点
temp = self.root.next
# 将新的节点挂到root上
self.root.next = node
# 新的节点的下一个节点是原来的root后的节点
node.next = temp
self.size += 1
def __iter__(self):
current = self.root.next
if current:
while current is not self.next:
yield current
current = current.next
yield current
def find(self, value):
for n in self.__iter__():
if n.value == value:
return n
def find_count(self, value):
count = 0
for n in self.__iter__():
if n.value == value:
count += 1
return count
def remove(self, value):
temp = self.root
for n in self.__iter__():
# 判断节点的值与要删除的值是否相等
if n.value == value:
# 查看是不是最后一个节点
if n == self.next:
# 更新倒数第二节点的关系
temp.next == None
# 更新最后一个节点为原倒数第二个节点
self.next = temp
temp.next = n.next
del n
self.size -= 1
return True
temp = n
def remove_all(self, value):
temp = self.root
for n in self.__iter__():
if n.value == value:
if n == self.next:
temp.next == None
self.next = temp
temp.next = n.next
del n
self.size -= 1
continue
temp = n
if __name__ == "__main__":
link = LinkedList()
link.append('姜子牙')
link.append('姬昌')
link.append('姬发')
link.append('雷震子')
link.append('商纣王')
link.append('商纣王')
link.append('杨戬')
link.append('商纣王')
link.append('通天教主')
link.append_first('申公豹')
link.append_first('商纣王')
print('-----删除之前------')
for v in link:
print(v)
link.remove_all('商纣王')
print('-----删除之后------')
for v in link:
print(v)
