链表是指用一组任意的存储单元来依次存放线性表的结点,这组存储单元即可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此,链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息,这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构:
(1)存储数据元素自身信息的部分,称为数据域;
(2)存储与前驱或后继结点的逻辑关系,称为指针域;
其中:data域是数据域,用来存放结点的值。next是指针域(亦称链域),用来存放结点的直接后继的地址(或位置)。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域,故将这种链表称为单链表(Single Linked)。
显然,单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。同时,由于最后一个结点无后继,故结点的指针域为空,即NULL(图示中常用^表示)。
#include<iostream>//单链表基本操作插入 删除 增加 获得长度 打印
using namespace std;
typedef int ElemType;
typedef struct lnode
{
int data;
lnode *next;//lnode 类的啊啊啊
}lnode;
class LinkList
{
private:
lnode *head;
int length = 0 ;
public:
void CreatList1(int n);//头插法
void CreatList2(int n);//尾插法
void ListInsert(int i,int e);//插入i个位置某个数e
int ListDelete(int i);//删掉第i个数
int GetElem(int i);//获得第i个数
int LocateElem(int e);//获得数e的地址
int Listlength();//获得长度
void printList();//打印链表;
void reverse(lnode *& head);
};
void LinkList::CreatList1(int n)
{
lnode *p;
cout<<"输入"<<n<<"个数据元素值"<<endl;
for(int i=0;i<n;i++)
{
p=new lnode;
cin>>p->data;
p->next=head->next;
head->next=p;
length++;
}
}
void LinkList::CreatList2(int n)
{
lnode *p,*s=head;
cout<<"输入"<<n<<"个数据元素"<<endl;
for(int i=0;i<n;i++)
{
p=new lnode;
cin>>p->data;
p->next=NULL;
s->next=p;
s=p;
length++;
}
}
int LinkList::LocateElem(int e)
{
lnode *p=head->next;
int j=1;
while(p&&p->data!=e)
{
p=p->next;
j++;
}
if(p==NULL)
return 0;
else
return j;
}
int LinkList::GetElem(int i)
{
lnode *p=head->next;
int j=1;
while(p&&j<i)
{
p=p->next;
j++;
}
if(!p||j>i)
return -1;
else
return p->data;
}
void LinkList::ListInsert(int i,int e)
{
int j=0;
lnode*p=head;
while (p&&j<i-1)
{
p=p->next;
j++;
}
if(!p||j>i-1)
{
cout<<"failure"<<endl;
return ;
}
else
{
lnode*s=new lnode;
s->data=e;
s->next=p->next;
p->next=s;
length++;
}
}
int LinkList::ListDelete(int i)
{
int j=0;
lnode*p=head;
while (p&&j<i-1)
{
p=p->next;
j++;
}
if(!p||j>i-1)
{
cout<<"fail to delete"<<endl;
return -1;
}
else
{
lnode*s=p->next;
p->next=s->next;
j=s->data;
delete s;
return j;
}
}
int LinkList::Listlength()
{
return length;
}
void LinkList::printList()
{
int i = length;
lnode* p = head;
while(i --)
{
p = p -> next;
cout<<p -> data <<" ";
}
}
void LinkList::reverse(lnode *& head)
{
lnode* p = head -> next;
if(!p || ! p -> next)
{
cout<<" wrong"<<endl;
return;
}
lnode * qr = p -> next, * q;
p ->next = NULL;
}
int main()
{
LinkList LinkLista;
LinkLista.CreatList1(5);
LinkLista.printList();
cout << "length:"<<LinkLista.Listlength()<<endl;
LinkLista.ListInsert(2,5);
LinkLista.printList();
return 0;
}