一、结构体
#include <iostream>
using namespace std;
//一个链表要实现的操作有
//建立链表,遍历链表,查找链表,插入和删除节点
//查找和遍历某种程度上来说是一样的,反正都是扎进堆里然后去找你想要的那个数
//创建链表还有两个前置条件,一个是链表头,还有一个是结点,这两个类
//节点由于存放数据和下一个节点的首地址
//而链表头用于存放第一个节点的首地址和链表的长度
//链表如果直接用struct会简单得多,因为struct的默认权限是public而不是private
struct Node //创建结点类
{
int data;//数据
Node *next;//下一个结点的首地址
//总有种循环的感觉,类的定义里面套了一个正在定义的类
};
struct List //再创建一个链表类
{
Node *head; //指向第一个结点的首地址
int len;//链表长度
};
void creatEmpty(List &list)//创建一个空链表的头
//要注意,任何类的成员是不可以在声明时初始化的,要定义成员就必须通过构造函数或全局函数,类内函数之类的
{
list.head=NULL;
list.len=0;
}
void creatList(List &list,int n)//这一步是创建第一个结点,所以传进来的是链表头
{
Node *node=new Node;//创建第一个结点的空间
list.head=node;
cin>>node->data; //同时你要为第一结点的data赋值
//这个地方也可以通过传进来一个参数,node->data=a,这样赋值
node->next=NULL; //第一结点的next应该指向再下一个结点的首地址,但还没出来,先给个NULL
//这样也可以解决链表的最后一个结点的next是NULL的问题
list.len++;
//接下来的步骤就是根据第一个结点继续往下创建链表了
Node *p;
for(int i=0;i<n-1;i++)//n是总共要创建多少结点(感觉奇奇怪怪的,那我还要len干什么)
{
p=node;//这个时候p接受new出来的node,p就是第一个结点的首地址
node=new Node;//然后node变成下一个结点
p->next=node;//p这个指代当前结点的首地址,让第一个结点的next赋上新的第二结点的首地址
cin>>node->data;//输入第二结点的data
node->next=NULL;//给默认的NULL
list.len++;
}
delete p;
}
bool Search(List &list,int data)
{
Node *p;
p=list.head;
while(p!=NULL)
{
if(p->data==data)
return true;
else p=p->next;
}
delete p;
return false;
}
//插入结点分为两种情况,在列表头和第一个节点之间插一个,让第一个节点变成第二个结点
//或者在两个结点之间插一个
//具体到要在哪个结点前面插,又需要遍历链表给出首地址了。
void insert(List&list,int data,int po)//在哪插,就是根据这个po来判断了
{
Node *p=new Node;//新增的结点
if(po==1)
{
p->next=list.head;
p->data=data;
list.head=p;
}
else
{
p=list.head; //p这个时候就相当于第一个结点的首地址
for(int i=0;i<po-2;i++)
{
p=p->next;
}
//这个时候p就是第po-1个结点的首地址
Node *q1=p;
Node *q2=q1->next;//q2就是第po个节点的首地址
//p存放的next已经是p2了
q1->next=p;
p->data=data;
delete p;//记得delete
}
list.len++;
}
void Delete(List &list,int po)//注意一下函数名 delete已经有了
{
if(po=1)
{
list.head=list.head->next;
list.len--;
}
else
{
Node *p=new Node;
p=list.head;
for(int i=0;i<po-2;i++)
{
p=p->next;
}
//这个时候p就是第po-1个结点的首地址
Node *q=p;
q->next=p->next->next;
list.len--;
delete p;//记得delete
}
}
int main()
{
List L;
creatEmpty(L);//创建链表的头
int n;
cin>>n;
creatList(L,n);//链表创建完成
bool flag;
flag=Search(L,8);
if(flag) cout<<"链表中有这个数"<<endl;
else cout<<"链表中没有这个数"<<endl;
}
二、类
类更巧妙,也更难写一点,要关注一下
另外,类外访问Node的data是有权限问题的,可直接将整个List声明为Node的友元类来解决,相当的简单粗暴,剩下的我不高兴写了,哪天想起来再补吧,但整体上来说只要实现了这个,把struct中的insert和delete函数稍作修改作为类的成员函数就可以了。
#include <iostream>
using namespace std;
class Node
{
friend class List;//粗暴一点直接友元
int data;
Node *next;
public:
Node(int data) //这本来是createlist的开头部分,创建第一个结点,到这里就变成了构造函数
{
this->data=data;
next=NULL;
}
void setnext(Node *p)//这个是给for循环创建结点的过程中,给当前结点的next赋值的函数,因此只要传入Node的指针就可以了
//指针所应该拥有的空间是在create函数中给的
{
next=p;
}
};
class List
{
Node *head;
int len;
public:
List()
{
head=NULL;
len=0;
}
List(int n)//这两个有参构造和无参构造完成了creatEmpty 创建了空链表的头
{
head=NULL;
len=n;
}
void createList()
{
int n;
cin>>n;
Node *node=new Node(n);//创建第一个节点并且通过构造函数给第一个结点的data赋值
head=node;//head指向第一个结点
for(int i=0;i<n-1;i++)
{
int n_data;
cin>>n_data;
Node *p=node;//接受第一个结点
node=new Node(n_data);//对于这个new出来的新结点,在有参构造函数中next赋成NULL
p->setnext(node);//调用第一节结点的构造函数,根据结点的构造函数,会将这个新new出来的node赋值给里面的next
//len也不用++了,在List的有参构造里面直接就给了,就像在struct里面写的,这个len意义还真不大
}
}
bool search(int num)
{
Node *p;
p=head;
if(p->data!=num)
{
}
}
};
int main()
{
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)