链表相关代码

链表相关代码"/>

链表相关代码

NodeList.h

//
//  NodeList.hpp
//  FirstP
//
//  Created by 赫赫 on 2023/10/31.
//  链表相关代码：单链表、循环单链表、静态链表#ifndef NodeList_hpp
#define NodeList_hpp
#define MaxSize 10//定义静态链表最大长度#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;#endif /* NodeList_hpp */typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;
//LinkList L;声明一个指向单链表第一个节点的指针
//LNode *L;声明一个指针，指向单链表的第一个节点//初始化单链表(带头结点)
bool initList(LinkList &L);//初始化单链表(不带头结点)
bool initListNoHead(LinkList &L);//顺序查找第i个结点
LNode* GetElemIndex(LinkList &L,int i);//顺序查找指定结点
LNode* GetNode(LinkList &L,LNode* node);//链表插入元素
//1.按照位序插入(先顺序查找到i结点，然后在后面插入)
bool ListInsert(LinkList &L,int i,int newelem);//2.指定结点后插操作
bool InsertNextNode(LNode *p,int newelem);//3.指定结点前插操作
bool InsertPriorNode(LNode *p,int newelem);//删除元素
//1.按照指定位置删除,并记录删除位置的元素
bool DeleteNodeByIndex(LinkList &L,int i,int &elem);
//2.按照指定结点删除
bool DeleteNodeByElem(LNode *p);//获取链表长度(带头结点)
int getSize(LinkList &L);//头插法建立链表(逆序)
LinkList List_tailInsert(LinkList &L);//尾插法建立链表(正向)
LinkList List_headInsert(LinkList &L);//------------------------------------------
//创建循环单链表
bool initCycleLinkList(LinkList &L);//判断循环单链表是否为空
bool Empty(LinkList &L);//------------------------------------------
//静态链表（适用于文件分配表FAT的存储）
typedef struct{int data;int next;
}SLinkList[MaxSize];
//SLinkList L;来定义一个长度为MaxSize的静态链表

NodeList.cpp

//
//  NodeList.cpp
//  FirstP
//
//  Created by 赫赫 on 2023/10/31.
//#include "NodeList.hpp"//初始化单链表(带头结点)
bool initList(LinkList &L){L=(LNode *)malloc(sizeof(LNode));if(L==NULL){return false;}else{L->next=NULL;return true;}
}
//初始化单链表(不带头结点)
bool initListNoHead(LinkList &L){L=NULL;return true;
}//顺序查找第i个结点(带头结点)
LNode* GetElemIndex(LinkList &L,int i){int j=1;LNode *p=L->next;if(i==0){return L;}if(i<0){return NULL;}while(p!=NULL&&j<i){p=p->next;j++;}return p;
}
//顺序查找指定结点(带头结点)
LNode* GetNode(LinkList &L,LNode* node){LNode *p=L->next;while(p!=NULL&&p->data!=node->data){p=p->next;}return p;
}//链表插入元素
//1.按照位序插入,带头结点(先顺序查找到第i-1个结点，然后在后面插入)
bool ListInsert(LinkList &L,int i,int newelem){if(i<1){return false;}LNode *p=L->next;int j=1;while(p!=NULL&&j<i-1){//寻找第i个结点p=p->next;j++;}if(p==NULL){//未找到第i-1个结点return false;}else{//将新元素放在第i-1个结点后面LNode *newnode=(LNode*)malloc(sizeof(LNode));newnode->data=newelem;newnode->next=p->next;p->next=newnode;return true;}
}
//2.指定结点后插操作
bool InsertNextNode(LNode *p,int newelem){if(p==NULL){return false;}LNode *newnode=(LNode*)malloc(sizeof(LNode));if(newnode==NULL){return false;}newnode->data=newelem;newnode->next=p->next;p->next=newnode;return true;
}
//3.指定结点前插操作
//如果已知头指针，可以遍历搜索然后插入
//这里主要写一下未知头指针的情况。
bool InsertPriorNode(LNode *p,int newelem){if(p==NULL){return false;}LNode* newnode=(LNode *)malloc(sizeof(LNode));if(newnode==NULL){//内存分配失败return false;}//按照后插操作在p指针后面插入结点，然后进行数据的转移newnode->next=p->next;p->next=newnode;int temp=p->data;p->data=newnode->data;newnode->data=temp;return true;
}//删除元素
//1.按照指定位置删除,并记录删除位置的元素(带头结点)
bool DeleteNodeByIndex(LinkList &L,int i,int &elem){if(i<0){return false;}LNode *p=L->next;int j=1;while(p!=NULL&&j<i-1){//先定位到i-1的元素p=p->next;j++;}if(p==NULL){return false;}if(p->next==NULL){return false;}//删除第i个结点，也就是p->next;LNode *q=p->next;elem=q->data;p->next=q->next;free(q);//释放q指针指向的空间return true;
}//2.按照指定结点删除
//和前插法类似，若未知头结点则需要通过复制数据的方式完成删除操作
//但是当p节点是最后一个结点是，该算法没有头结点不能实现
bool DeleteNodeByElem(LNode *p){if(p==NULL){return false;}//和后继结点交换数据，指针指向后继节点的后继LNode *q=p->next;p->data=q->data;p->next=q->next;free(q);return true;
}//获取链表长度(带头结点)
int getSize(LinkList &L){int len=0;LNode *p=L->next;if(p==NULL){return len;}while(p!=NULL){len++;p=p->next;}return len;
}//头插法建立链表(逆序)
LinkList List_tailInsert(LinkList &L){int x=0;//接收输入元素//首先建立头结点L=(LinkList)malloc(sizeof(LNode));LNode *newnode,*end=L;scanf("%d",&x);while(x!=9999){//不断地往尾结点后面插入newnode=(LNode*)malloc(sizeof(LNode));newnode->data=x;end->next=newnode;end=newnode;scanf("%d",&x);}//注意下面这个语句end->next=NULL;return L;
}//尾插法建立链表(正向)
LinkList List_headInsert(LinkList &L){int x=0;//接收输入元素//首先建立头结点，并初始化L=(LinkList)malloc(sizeof(LNode));//注意下面这个语句L->next=NULL;LNode *newnode;scanf("%d",&x);while(x!=9999){//不断地往投头结点后面插入newnode=(LNode*)malloc(sizeof(LNode));newnode->data=x;newnode->next=L->next;L->next=newnode;scanf("%d",&x);}return L;
}//------------------------------------------
//创建循环单链表
bool initCycleLinkList(LinkList &L){L=(LNode*)malloc(sizeof(LNode));if(L==NULL){return false;}L->next=L;//头结点指针指向自己，表为空return true;
}//判断循环单链表是否为空
bool Empty(LinkList &L){if(L->next==L){return true;}else{return false;}
}