首页 > 其他分享 >链表

链表

时间:2023-11-09 19:47:34浏览次数:43  
标签:head next 链表 phead link data 节点

链表



单链表插入一个节点的伪代码算法:

  1. 创建一个新节点newNode,将要插入的数据data存储在newNode中
  2. 如果链表为空,则将newNode设为头节点,并将next指向NULL
  3. 如果链表不为空,则将newNode插入到链表的末尾
  4. 遍历链表,找到最后一个节点lastNode
  5. 将lastNode的next指向newNode
  6. 将newNode的next指向NULL

单链表删除一个节点的伪代码算法:

  1. 如果链表为空,则返回
  2. 如果要删除的节点是头节点,则将头节点指向下一个节点
  3. 如果要删除的节点不是头节点,则遍历链表,找到要删除的节点
  4. 将要删除节点的前一个节点preNode的next指向要删除节点的下一个节点nextNode
  5. 释放要删除的节点的内存空间


c++代码实现

c++中实现单链表,可能涉及指针和节点,以及类似Find Node()、printlist()等一系列c++函数来实现。

#include<iostream>
#include<cstdlib>
using namespace std;

class list{
	public:
		int data;
		class list *next;
};
typedef class list node;
typedef node *link;

link FindNode(link head,int position_data){
	link phead;
	phead = head;
	while(phead != NULL){
		if(phead->data == position_data)return phead;
		phead = phead->next;
	}
	return phead;
}

link InsertNode(link head,int position_data,int data){
	link phead = new node;
	phead = FindNode(head,position_data);
	link insertnode = new node;
	if(!insertnode) return NULL;
	insertnode->data = data;
	insertnode->next = NULL;
	if(phead == NULL){  //插入第一个节点
		insertnode->next = head;
		return insertnode;
	} 
	else if(phead->next == NULL) phead->next = insertnode;  //插入最后一个节点
	else{  //插入中间节点 
		insertnode->next = phead->next;
		phead->next = insertnode;
	}
	return head; 
}

link DeleteNode(link head,int position_data){
	link top = head;  //保留头指针 
	link phead = FindNode(head,position_data);
	if(head == phead){  //删除头结点 
		head = head->next;
		delete phead;
	}
	else{
		while(top->next != phead) top = top->next;
		if(phead->next == NULL){  //删除尾结点 
			top->next = NULL;
			delete phead;
		}
		else{
			top->next = phead->next;
			delete phead;
		} 
	}
	return head;
}

link CreateList(int a[],int n){
	link head,phead,newnode;
	phead = new node;
	if(!phead) return NULL;
	phead->data = a[0];
	head = phead;
	for(int i = 1;i<n;i++){
		newnode = new node;
		newnode->data = a[i];
		newnode->next = NULL;
		phead->next = newnode;
		phead = phead->next;
	}
	return head;
}

 void PrintList(link head){
	link phead = new node;
	phead = head;
	cout<<"链表元素如下: "<<endl;
	while(phead!=NULL){
		cout<<phead->data<<"->";
		head = phead;
		phead = phead->next;  //phead按序往后遍历整个链表
		if(!phead) cout<<"NULL"<<endl;
	}
}

int main(){
	int position_data,data;
	link head,phead;
	int n;
	cout<<"请输入初始链表元素个数: "<<endl;
	cin>>n;
	int a[n];
	cout<<"请依次输入链表元素: ";
	for(int i = 0;i<n;i++) cin>>a[i];
	head = CreateList(a,n);
	PrintList(head);
	cout<<"请输入预插入位置之前的元素和要插入的元素(例:5 8): ";
	cin>>position_data>>data;
	head = InsertNode(head,position_data,data);
	cout<<"插入之后的";
	PrintList(head); 
	cout<<"请输入想删除的链表元素: ";
	cin>>position_data;
	head = DeleteNode(head,position_data);
	cout<<"删除之后的";
	PrintList(head);
	return 0;
}

标签:head,next,链表,phead,link,data,节点
From: https://www.cnblogs.com/raymongillichmks/p/17818504.html

相关文章

  • 实验:C SOCKET 多线程服务端链表分组实现聊天室
    目录......
  • [左神面试指南] 链表[下]篇
    CDxxx两个单链表相交的一系列问题⭐剑指offer链表篇JZ52两个链表的第一个公共结点剑指offer链表篇JZ23链表中环的入口结点publicNodegetIntersectNode(Nodehead1,Nodehead2){if(head1==null||head2==null)returnnull;Nodeloo......
  • 03-链表
    3.链表3.1单向链表和双向链表单项:有一个next,双向:last,next3.2删除链表的倒数第n个结点1.题目https://leetcode.cn/problems/SLwz0R/给定一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]输入:head=[1],n=1......
  • [左神面试指南] 链表[上]篇
    CD48打印两个有序链表的公共部分/*归并*/publicclassCD48_1{publicstaticclassListNode{publicintval;publicListNodenext=null;publicListNode(intval){this.val=val;}pub......
  • 2008秋-计算机软件基础-单链表练习(1)
    /*--------------------------------------------------------设有一个单链表,头结点为head,为递增有序,写一个完整程序,将其改为递减有序。----------------------------------------------------------*/#include<stdio.h>#include<stdlib.h>//定义结点structnodetype......
  • 2008秋-计算机软件基础-单链表完整示例
    /*---------------------------------------------------------Title:CompletedSimpleLinkedListAuthor:EmanLeeDate:Oct22,2008Fuction:OperationonLinkedStoredLinearList.Thisisacompletedsimplesample.Itisrelatedto......
  • 2008秋季-线性表的链式存储(仅单链表)
    /*---------------------------------------------------------Title:单链表Date:September1,2008Fuction:单链表的初始化,创建,插入,删除,查找结点。参考PPT讲稿或者教材2.2.4节.(p56-63)----------------------------------------------------------*/#inclu......
  • 一文搞懂双链表
    前言前面有很详细的讲过线性表(顺序表和链表),当时讲的链表以单链表为主,但在实际应用中双链表有很多应用场景,例如大家熟知的LinkedList。双链表与单链表区别单链表和双链表都是线性表的链式实现,它们的主要区别在于节点结构。单链表的节点包含数据字段data和一个指向下一个节......
  • 数据结构-链表2
    1、静态链表这个给我的感觉就是数组加了索引,它的目的就是要融合顺序表和链表的优点,能够快速的访问元素,也能快速的增加或删除元素。整个的组成如图所示,第一列的数据是位置,第二列是数据2、双向链表双向链表概念是区别于单链表而言的,就是多了一个前驱,组成示意图如下所示:常见结......
  • 三元组存以及十字链表的创建
    1#define_CRT_SECURE_NO_WARNINGS2#include<iostream>3#include<fstream>4#define_CRT_SECURE_NO_WARNINGS5usingnamespacestd;67structTripleArray8{9introw;//行10intcol;//列11intval;//值12};......