A8站源码交易平台
怎样了解链表
看有个人写的很好，便是说你现在有一个小纸条，上面写着一个抽屉的地址，那个抽屉里有一些你需求的东西，和一个新的写着地址的小纸条，这个小纸条又指向了一个新的抽屉，大体能够这么了解
程序所包括的头文件
#include
#include
using namespace std;
当然假如要做随机次序的链表的话
最好也包括ctime这个库
榜首部分—构建抽屉 A8站源码交易平台
已然把装有东西和写有地址的小纸条比作抽屉那么咱们无妨先写出抽屉的结构体`
typedef struct listpoint
{
int data;
listpoint *next;
}listpoint;
这便是一个最简略的结构体
int data,是一个数字，是咱们存在抽屉里的东西
而listpoint *next是一个指向和这个抽屉结构相同的新的抽屉的指针；
咱们能够在抽屉里放指向下一个抽屉的指针，天然也就能够在抽屉里放指向上一个抽屉的指针
typedef struct listpoint
{
int data;
listpoint *next;
listpoint *last;
}listpoint;
A8站源码交易平台
咱们在抽屉里不仅仅能够放一个数，咱们能够往里面放一个收纳盒，例如，鄙人面的结构体中包括了另一个结构体
typedef struct data
{
int number;
string name;
string sex;
}data;
typedef struct listpoint
{
data *information;
listpoint *next;
listpoint *last;
}listpoint;
A8站源码交易平台
那个叫做information的小收纳盒里，装着一个人的学号，名字，性别等信息
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
第二部分—创立一个链表
创立一个根底链表
listpoint *create_normal_list(int n) /*链表每一个节点都是指向 listpoint结构的指针，所以返回值是listpoint *,n是指创立的链表的节点数目*/
{
listpoint *head,*normal,*end;/*创立头节点，其他节点，和尾节点*/
head=(listpoint*)malloc(sizeof(listpoint));
head->information=(data*)malloc(sizeof(data));
/*分配内存*/
end=head;/*最开端最终一个节点便是头节点，留意由于经过指针能够直接对地址上的东西进行操作，此刻end和head指向同一个地址，对end所指向地址进行操作，等同于对head地址所做的操作*/
for(int i=0;i<n;i++)
{
normal=(listpoint*)malloc(sizeof(listpoint));
normal->information=(data*)malloc(sizeof(data));
/*给新节点分配内存*/
cout<<"input the number :";
cin>>normal->information->number;
cout<<"input the name :";
cin>>normal->information->name;
cout<<"input the sex :";
cin>>normal->information->sex;
cout<<"----------------------------------"<<endl;
/* 往新节点存入数据，留意咱们只给后边的节点存入数据，head不存数据*/
end->next=normal;/*往end后增加新节点*/
normal->last=end;/*新节点的上一个节点便是end*/
end=normal;/*最终一个节点变成新节点*/
}
end->next=NULL;/*链表的最终指向一个新地址*/
head->last=NULL;/*链表最开端的节点没有上一个节点*/
return head;
}
A8站源码交易平台
创立环状链表
操作和之前相同，只不过最终一个节点的下一个指向头节点
listpoint *create_loop_list(int n)
{
listpoint *head,*normal,*end;
head=(listpoint*)malloc(sizeof(listpoint));
head->information=(data*)malloc(sizeof(data));
end=head;
for(int i=0;i<n;i++)
{
normal=(listpoint*)malloc(sizeof(listpoint));
normal->information=(data*)malloc(sizeof(data));
cout<<"input the number :";
cin>>normal->information->number;
cout<<"input the name :";
cin>>normal->information->name;
cout<<"input the sex :";
cin>>normal->information->sex;
cout<<"----------------------------------"<<endl;
end->next=normal;
normal->last=end;
end=normal;
}
end->next=head;
head->last=end;
return head;
}
创立随机枝杈链表
**这一部分能够最终再看 **
每一个节点都有一个分支指向随机一个节点，这时候咱们就要引进ctime库用来运用srand((int)(time(NULL)));以生成随机数，这儿还用到了后边的一个函数
listpoint *search_point(listpoint *list,int n);是用来查找节点的
#include
#include
#include
using namespace std;
typedef struct data
{
int number;
string name;
string sex;
}data;
typedef struct listpoint
{
data *information;
listpoint *next;
listpoint *last;
listpoint *branch;
}listpoint;
listpoint *create_random_branch_list(int n)
{
listpoint *search_point(listpoint *list,int n);
listpoint *head;
head=create_normal_list(n);
listpoint *p,*bp;
p=head;
srand((int)(time(NULL)));
int randnum;
while((p=p->next)!=NULL)
{
randnum=rand()%n+1;
bp=search_point(head,randnum);
p->branch=bp;
}
return head;
}
A8站源码交易平台
生成随机排序链表
同能够最终再看
先生成正常次序链表，再从最终n个节点中随机挑选一个，将其除掉并刺进到榜首个节点的方位，然后再从最终n-1个节点中随机挑选一个，除掉后刺进第二个节点方位，以此类推
listpoint *create_random_sort_list(int n)
{
listpoint *head;
head=create_normal_list(n);
listpoint *p1,*p2;
int n1=0;
int n2=n;
srand((int)(time(NULL)));
int randnum;
while(n2!=1)
{
p1=head;
p2=head;
randnum=rand()%n2+1+n1;
for(int i=0;i<randnum;i++)
{p2=p2->next;}
for(int i=0;i<n1;i++)
{p1=p1->next;}
if(randnum==n)
{
p2->last->next=NULL;
}
else
{
p2->next->last=p2->last;
p2->last->next=p2->next;
}
p1->next->last=p2;
p2->next=p1->next;
p1->next=p2;
p2->last=p1;
n1+=1;
n2-=1;
}
return head;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
第三部分—修正链表
修正数据，由于咱们经过指针能够直接修正地址贮存的信息，所以函数并不需求返回值
void change_point(listpoint *list,int n,data *ifmation)
{
listpoint *p;
p=list;
for(int i=0;i<n;i++)
{
p=p->next;
}
p->information=ifmation;
}
删去节点
void delete_point(listpoint *list,int n)
{
listpoint *p;
p=list;
for(int i=0;i<n;i++)
{
p=p->next;
}
p->last->next=p->next;
p->next->last=p->last;
free(p);
}
A8站源码交易平台
刺进节点
void insert_point(listpoint *list,int n,data *ifmation)
{
listpoint *p;
p=list;
for(int i=0;i<n-1;i++)
{
p=p->next;
}
listpoint *insertpoint;
insertpoint=(listpoint*)malloc(sizeof(listpoint));
insertpoint->information=ifmation;
insertpoint->next=p->next;
p->next->last=insertpoint;
p->next=insertpoint;
insertpoint->last=p;
}
搜索节点
listpoint *search_point(listpoint *list,int n)
{
listpoint *p;
p=list;
for(int i=0;i<n;i++)
{
p=p->next;
}
return p;
}
输出单个节点数据
void output_point(listpoint *point)
{
cout<<"the number is :"number<<endl;
cout<<"the name is :"name<<endl;
cout<<"the sex is :"sex<<endl;
cout<<"----------------------------------"<<endl;
}
输出整个链表数据
void output_list(listpoint *point)
{
listpoint *p;
p=point;
cout<<endl<<endl<<endl;
while((p=p->next)!=NULL)
{
output_point(p);
}
}
输出部分链表m点到n点
void output_list_part(listpoint *list,int m,int n)
{
int difference=n-m;
listpoint *p;
p=list;
cout<<endl<<endl<<endl;
for(int i=0;i<m;i++)
{
p=p->next;
}
for(int i=0;i<difference+1;i++)
{
output_point(p);
p=p->next;
}
}
第五部分—主函数使用
举个比如，生成7个节点的随机次序链表
并输出
int main()
{
listpoint *head;
head=create_random_sort_list(7);
output_list(head);
system("pause");
return 0;
}
A8站源码交易平台
第六部分—完好代码
#include
#include
#include
using namespace std;
typedef struct data
{
int number;
string name;
string sex;
}data;
typedef struct listpoint
{
data *information;
listpoint *next;
listpoint *last;
listpoint *branch;
}listpoint;
/********************************************************/
listpoint *create_normal_list(int n)
{
listpoint *head,*normal,*end;
head=(listpoint*)malloc(sizeof(listpoint));
head->information=(data*)malloc(sizeof(data));
end=head;
for(int i=0;i<n;i++)
{
normal=(listpoint*)malloc(sizeof(listpoint));
normal->information=(data*)malloc(sizeof(data));
cout<<"input the number :";
cin>>normal->information->number;
cout<<"input the name :";
cin>>normal->information->name;
cout<<"input the sex :";
cin>>normal->information->sex;
cout<<"----------------------------------"<<endl;
end->next=normal;
normal->last=end;
end=normal;
}
end->next=NULL;
head->last=NULL;
return head;
}
listpoint *create_loop_list(int n)
{
listpoint *head,*normal,*end;
head=(listpoint*)malloc(sizeof(listpoint));
head->information=(data*)malloc(sizeof(data));
end=head;
for(int i=0;i<n;i++)
{
normal=(listpoint*)malloc(sizeof(listpoint));
normal->information=(data*)malloc(sizeof(data));
cout<<"input the number :";
cin>>normal->information->number;
cout<<"input the name :";
cin>>normal->information->name;
cout<<"input the sex :";
cin>>normal->information->sex;
cout<<"----------------------------------"<<endl;
end->next=normal;
normal->last=end;
end=normal;
}
end->next=head;
head->last=end;
return head;
}
listpoint *create_random_branch_list(int n)
{
listpoint *search_point(listpoint *list,int n);
listpoint *head;
head=create_normal_list(n);
listpoint *p,*bp;
p=head;
srand((int)(time(NULL)));
int randnum;
while((p=p->next)!=NULL)
{
randnum=rand()%n+1;
bp=search_point(head,randnum);
p->branch=bp;
}
return head;
}
listpoint *create_random_sort_list(int n)
{
listpoint *head;
head=create_normal_list(n);
listpoint *p1,*p2;
int n1=0;
int n2=n;
srand((int)(time(NULL)));
int randnum;
while(n2!=1)
{
p1=head;
p2=head;
randnum=rand()%n2+1+n1;
for(int i=0;i<randnum;i++)
{p2=p2->next;}
for(int i=0;i<n1;i++)
{p1=p1->next;}
if(randnum==n)
{
p2->last->next=NULL;
}
else
{
p2->next->last=p2->last;
p2->last->next=p2->next;
}
p1->next->last=p2;
p2->next=p1->next;
p1->next=p2;
p2->last=p1;
n1+=1;
n2-=1;
}
return head;
}
/********************************************************/
