数据结构（一）- 单链表
目录单链表
单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构【链尾除外】，内存结构由数据域和 Next 指针域组成。
单链表图示（网图侵删）：
单链表的实现
链表通常由各个结构体链接而成，在下面的例子中我们构建一个含有两个元素及一个后继节点指针的结构体：
struct node
{
string name;
int v;
node* next;
};
当然了，你也可以在结构体中使用模板变量来适应不同情况。
单链表增删查改及排序显示等各种操作
接下来我们要实现动态操作单链表进行各种操作
增加节点
首先是增加节点，创建以下函数:
node* append_node(node* buf,string name,int v)
{
//分配内存，构建一个元素,这里使用C++方法，在语境中与C的malloc()等价。
node* newp = new node[1];
newp->v = v;
newp->name = name;
newp->next=NULL;
//判断是否空链表
if(buf==NULL)
{
//是空链表，直接添加
buf = newp;
}
else
{
//不是空链表，生成buf的游动指针
node* n_head = buf;
//移到最后一个元素
while(n_head->next!=NULL){
n_head = n_head->next;
}
//更改元素的后继地址
n_head->next = newp;
}
return buf;
}
删除节点
node* delete_node(node* buf,int i)
{
//生成游标指针
node* n_head = buf;
//如果删除第一个元素
if(i==0)
{
//越过第一个元素，游标设为下一个节点
n_head = n_head->next;
buf = n_head;
}
else
{
int c=0;
//移动到要删除元素的前一位
while(c!=i-1)
{
c++;
n_head=n_head->next;
}
//获取要删除元素指针
node* dd = n_head->next;
//要删除元素前一位元素的新后继节点指针
n_head->next = dd->next;
//释放内存
delete dd;
}
return buf;
}
从一个位置增加节点
node* insert_node(node* buf,int i,string name,int v)//i为插入节点的位置
{
//分配内存，构建一个元素
node* newp = new node[1];
newp->v = v;
newp->name = name;
newp->next=NULL;
//判断是否空链表
if(buf==NULL)
{
buf = newp;
}
else
{
int c=0;
node* n_head = buf;
//移动到要增加的节点位置的前一位
while(c!=i-1)
{
//获取节点原指向
n_head = n_head->next;
c+=1;
}
//汇入新节点并调整后继节点指向
newp->next = n_head->next;
n_head->next = newp;
}
return buf;
}
显示所有节点内容
void show(node* buf)
{
node* n_head = buf;
while(n_head!=NULL)
{
cout<<n_head->name<<"\t"<<n_head->v<<endl;
n_head = n_head->next;
}
}
排序节点
void sort_node(node* buf)
{
node* p1 = buf;
while(p1!=NULL)
{
node* p2 = p1->next;
while(p2!=NULL)
{
if(p1->v < p2->v)
{
string tn = p1->name;
int tv = p1->v;
p1->name = p2->name;
p1->v = p2->v;
p2->name = tn;
p2->v = tv;
}
p2 = p2->next;
}
p1 = p1->next;
}
}
测试
最后通过编写主函数来测试以上函数的使用:
int main()
{
node* buf=NULL;
buf = append_node(buf,"zs",70);
buf = append_node(buf,"ls",60);
buf = append_node(buf,"hw",90);
buf = append_node(buf,"cl",80);
buf = insert_node(buf,2,"gq",50);
buf = delete_node(buf,3);
show(buf);
cout<<"==============排序==========="<<endl;
sort_node(buf);
show(buf);
return 0;
}
效果：
至此，我们完成了所有内容！