线性表之链表基本操作的实现1
这里,我们首先实现单链表的基本操作。
1.创建单链表
LinkList CreateLinkList(LinkList L)
{
L=(LinkList)malloc(sizeof(LNode)); //创建一个头结点
L->next=NULL; //头结点的指针域为空
return L;
}
2.采用前插法插入数据
void InsertElem_For(LinkList head,User user) //即把每次插入的数据都设置为首元结点
{
LinkList p=(LinkList)malloc(sizeof(LNode)); //创建一个新的结点
p->user=user; //将目标数据放置进入数据域
p->next=head->next; //把当前的首元结点与目标结点相连,即目标结点指向首元结点
head->next=p; //把目标结点与头结点相连,即头结点指向目标结点,此时目标结点变成首元结点
}
3.采用后插法插入数据
void InsertElem_Back(LinkList head,User user) //即把每个插入的数据都放在最后一位
{
LinkList p=(LinkList)malloc(sizeof(LNode));
LinkList r=head; //这里我们采用新建一个空链表,每次加入数据后,r都会指向尾节点
p->user=user;
p->next=NULL;
r->next=p; //链表的尾指针指向目标结点
r=p; //指向目标结点的指针成为新的尾指针
}
4.在某个位置插入一个结点
bool AddElem(LinkList head,int index,User user)
{
int j=0;
while(head && j<index-1) //结束循环后head指向目标位置的前一个结点
{
head=head->next;
j++;
}
if(!head || j>index+1)
{
return false;
}
LinkList p=(LinkList)malloc(sizeof(LNode));
p->user=user;
p->next=head->next; //将目标结点指向当前位置的结点
head->next=p; //将当前位置的前一个结点指向目标结点,此时目标结点插入到当前位置
return true;
}
5,根据某个位置返回对应的结点信息
User GetElemByIndex(LinkList head,int index)
{
int j=0;
while(head && j<index) //返回目标位置的结点
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user;
user.id=456;
strcpy(user.username,"error");
return user;
}
return head->user;
}
6.根据结点信息找到该结点在链表中的位置
int GetIndexByUser(LinkList head,User user)
{
int index=0;
bool bo=false;
while(head)
{
User user1=head->user;
if(strcmp(user1.username,user.username)==0)
{
bo=true;
break;
}
index++;
head=head->next;
}
return bo?index:-1;
}
7.修改某个位置对应的结点信息
void UpdateElemByIndex(LinkList head,int index,User user)
{
int j=0;
while(head && j<index)
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user1;
user1.id=456;
strcpy(user1.username,"error");
head->user=user1;
}
head->user=user;
}
8.删除某个位置对应的结点
void DeleteElemByIndex(LinkList head,int index)
{
int j=0;
while(head && j<index-1) //当前的head应该指向的是目标结点的前一个结点
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user1;
user1.id=456;
strcpy(user1.username,"error");
head->user=user1;
}
LinkList p=head->next; //p指向目标结点
head->next=p->next; //将目标结点的上一个结点指向目标结点的下一个结点
free(p); //释放目标结点
}
这里我们对插入某个结点进行图形讲解(例4):
bool AddElem(LinkList head,int index,User user)
{
int j=0;
while(head && j<index-1) //结束循环后head指向目标位置的前一个结点
{
head=head->next;
j++;
}
if(!head || j>index+1)
{
return false;
}
LinkList p=(LinkList)malloc(sizeof(LNode));
p->user=user; //1.将数据放置在数据域
p->next=head->next; //2.将目标结点指向当前位置的结点
head->next=p; //3.将当前位置的前一个结点指向目标结点,此时目标结点插入到当前位置
return true;
}
第一步(p1=head):
第二步:
第三步:
这样就完成了链表的插入
这里附上完整的代码:
#include<bits/stdc++.h>
using namespace std;
typedef struct
{
char username[20];
int id;
}User;
//单链表的存储结构
typedef struct LNode
{
User user; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; //LinkList为指向LNode的指针类型
//创建单链表,创建头节点,指针指向头节点
LinkList CreateLinkList(LinkList L)
{
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
return L;
}
//前插法向单链表中加入数据
void InsertElem_For(LinkList head,User user)
{
LinkList p=(LinkList)malloc(sizeof(LNode));
p->user=user;
p->next=head->next;
head->next=p;
}
//后插法向单链表中加入数据
void InsertElem_Back(LinkList head,User user)
{
LinkList p=(LinkList)malloc(sizeof(LNode));
LinkList r=head; //每次加入数据后,r都会指向尾节点
p->user=user;
p->next=NULL;
r->next=p;
r=p;
}
//在某个位置添加一个节点(插入)
bool AddElem(LinkList head,int index,User user)
{
int j=0;
while(head && j<index-1)
{
head=head->next;
j++;
}
if(!head || j>index+1)
{
return false;
}
LinkList p=(LinkList)malloc(sizeof(LNode));
p->user=user;
p->next=head->next;
head->next=p;
return true;
}
//根据位置查找某个子节点
User GetElemByIndex(LinkList head,int index)
{
int j=0;
while(head && j<index)
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user;
user.id=456;
strcpy(user.username,"error");
return user;
}
return head->user;
}
//根据值查找到节点在链表中的位置
int GetIndexByUser(LinkList head,User user)
{
int index=0;
bool bo=false;
while(head)
{
User user1=head->user;
if(strcmp(user1.username,user.username)==0)
{
bo=true;
break;
}
index++;
head=head->next;
}
return bo?index:-1;
}
//修改第n个节点的信息
void UpdateElemByIndex(LinkList head,int index,User user)
{
int j=0;
while(head && j<index)
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user1;
user1.id=456;
strcpy(user1.username,"error");
head->user=user1;
}
head->user=user;
}
//删除第n个节点的信息
void DeleteElemByIndex(LinkList head,int index)
{
int j=0;
while(head && j<index-1)
{
head=head->next;
j++;
}
if(!head || j>index)
{
User user1;
user1.id=456;
strcpy(user1.username,"error");
head->user=user1;
}
//当前的head应该指向的是目标节点的前一个节点
LinkList p=head->next;
head->next=p->next;
free(p);
}
int main()
{
LinkList L;
User user;
//创建单链表
LinkList head=CreateLinkList(L);
//前插法插入数据
user.id=123;
strcpy(user.username,"gjw");
InsertElem_For(head,user);
//后插法插入数据
//user.id=123;
//strcpy(user.username,"gjw3");
//InsertElem_Back(head,user);
//在某个位置添加一个节点(插入)
user.id=123;
strcpy(user.username,"gjw1");
AddElem(head,1,user);
//根据位置查找某个子节点
//User user1=GetElemByIndex(head,1);
//cout<<user1.username<<endl;
//根据值查找到节点的位置
//user.id=123;
//strcpy(user.username,"gjw");
//int index=GetIndexByUser(head,user);
//cout<<index<<endl;
//修改第n个节点的信息
//user.id=123;
//strcpy(user.username,"gjw8");
//UpdateElemByIndex(head,1,user);
//删除第n个节点的信息
User user1=GetElemByIndex(head,1);
cout<<user1.username<<endl;
DeleteElemByIndex(head,1);
user1=GetElemByIndex(head,1);
cout<<user1.username<<endl;
return 0;
}
学到这里,其实发现单链表的实现也不难,是吧?