单链表
@
1，单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
链表中的数据是以节点来表示的，每个结点的构成：元素( 数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
链表的结点结构：
┌───┬───┐
│data │next │
└───┴───┘
2，C语言实现单链表
typedef struct Node
{
int data;//数据域
struct Node*next;//节点指针（下一个）
}Node,*List;//List===>>struct Node*
void InitList(List p)
{
assert(p!=NULL);
if(p->next==NULL)
{
return;
}
p->next=NULL;
}
static Node*GetNode(int val) //设置新节点
{
Node*pGet=(Node*)malloc(sizeof(Node));
assert(pGet!=NULL);
pGet->data=val;
pGet->next=NULL;
return pGet;
}
bool Insert_head(List p,int val) //头插
{
assert(p!=NULL);
Node*pGet=GetNode(val);
pGet->next=p->next;
p->next=pGet;
return true;
}
bool Insert_tail(List p, int val) //尾插
{
assert(p!=NULL);
Node*pcur=p;
for(;pcur!=NULL;pcur=pcur->next)
{}
Node*pGet=GetNode(val);
pcur->next=pGet;
return true;
}
bool Insert_pos(List p, int pos, int val) //从pos位置插入
{
Node*pcur=p;
for(int i=0;i<=pos-1;i++)
{
pcur=pcur->next;
}
Ndoe*pGet=GetNode(val);
pGet->next=pcur->next;
pcur->next=pGet;
return true;
}
int Getlength(List p)
{
int count=0;
Node*pcur=p->next;
while(pcur!=NULL)
{
count++;
pcur=pcur->next;
}
return count;
}
Node *Search_pre(List p, int key)
{
Node*pcur=p;
for(;pcur->next!=NULL;pcur=pcur->next)
{
if(pcur->next->data==key)
{
return pcur;
}
}
return true;
}
bool Delete(List p, int key)
{
Node*p1=Search_pre(p.key);
if(p1==NULL)
{
return fasle;
}
Node*pDel=p1->next;
p1->next=pDel->next;
free(pDel);
pDel=NULL;
return true;
}
bool IsEmpty(List p)
{
if(p->next==NULL)
{
return true;
}
return false;
}
void Show(List p)
{
Node*pcur=p->next;
while(pcur!=NULL)
{
printf("%d ",pcur->data);
}
printf("
");
}
void Destroy(List p)
{
Node*pDel=NULL;
while(p->next!=NULL)
{
pDel=p->next;
p->next=pDel->next;
free(pDel);
}
pDel=NULL;
}
void reverse(List p) //逆置
{
assert(p!=NULL);
Node*revhead=NULL;
Node*prev=NULL;
Node*pnode=p;
while(pnode!=NULL)
{
Node*pnext=pnode->next;
if(pnext==NULL)
{
revhead=pnode;
}
pnode->next=prev;
prev=pnode;
pnode=pnext;
}
return revhead;
}
3，OOP实现单链表
class Link
{
public:
Link()
{
phead=new Node;
}
~Link()
{
Node*pcur=phead;
while(pcur!=NULL)
{
phead=phead->pnext;
delete phead;
pcur=phead;
}
}
void inserthead(int val)
{
Node*pcur=new Node(val);
pcur->pnext=phead->pnext;
phead->pnext=pcur;
}
void inserttail(int val)
{
Node*pcur=phead;
while(pcur->pnext!=NULL)
{
pcur=pcur->pnext;
}
pcur->pnext=new Node(val);
}
void deleteNode(int val)
{
Node*pcur1=phead;
Node*pcur2=phead->pnext;
while(pcur2!=NULL)
{
if(pcur2->data==val)
{
pcur1->pnext=pcur2->pnext;
delete pcur2;
pcur2=pcur1->pnext;
}
else
{
pcur1=pcur2;
pcur2=pcur2->pnext;
}
}
}
void show()
{
Node*pcur=phead->next;
while(pcur!=NULL)
{
cout<<pcur->data<<" ";
pcur=pcur->pnext;
}
}
private:
class Node
{
public:
Node(int data):pdata(data),pnext(NULL){}
int pdata;
Node*pnext;
};
Node*phead;
};