算法逻辑
链表由节点及连线组成,一个节点分配一个数据,将新旧节点连接成为一个链表。节点中有数据和下个节点的地址(指针)。
typedef int Elemtype;
typedef struct LNode{
Elemtype data;
LNode *next;
}LNode,*LinkList;
操作数据
头插法(有头节点)
新建节点,将数据放入后将头节点的next指针指向的地址给新节点的next指针(将准备断开的线备份接一条给新节点牵着)。
将头节点的next指针指向新节点(断开线重新连)
void HeadInList(LinkList &L){
L=(LinkList)malloc(sizeof(LNode)); //创建头节点
L->next=NULL; //设置最后的一个元素的next为NULL
int x;
scanf("%d",&x);
LinkList n; //声明用作创建新节点的结构体变量
while(x!=9999){
n=(LinkList)malloc(sizeof(LNode)); //创建新节点
n->data=x;
n->next=L->next; //新节点的next连接到插入位置的后继上
L->next=n; //L的next连接到新节点上
scanf("%d",&x);
}
}
运行结果:
尾插法
声明一个新指针用作标记当前位置
新节点获取数据
当前位置的节点next指针指向新节点
位标指针移动到新节点(位标指针指向最后一个节点)
新节点的next指向NULL(最后一个节点)
void EndInList(LinkList &L){
L=(LinkList)malloc(sizeof(LNode)); //创建头节点
int x;
scanf("%d",&x);
LinkList n,p=L; //n为新节点,p为当前节点位置
while(x!=9999){
n=(LinkList)malloc(sizeof(LNode));
n->data=x;
p->next=n; //新节点插与入位置的前驱连接
p=n;
scanf("%d",&x);
}
n->next=NULL;
}
运行结果:
位置查找
声明一个节点类型的结构体指针储存查找返回的节点,通过遍历进行位置的查找。
LinkList GetItem(LinkList L,int Spos){
int i=0;
while(L&&i<Spos){
L=L->next;
i++;
}
return L;
}
按值查找
通过遍历进行对比,将相同数值返回
LinkList GetNum(LinkList L,int value){
while (L){
if(L->data==value){
return L;
}
L=L->next;
}
}
第i个位置插入
使用循环遍历且进行计数,到目标位置后进行插入操作
bool ListInsert(LinkList L,int pos,int value){
LinkList p=GetItem(L,pos-1);
LinkList q;
q=(LinkList)malloc(sizeof(LNode));
q->data=value;
q->next=p->next;
p->next=q;
return true;
}
删除
通过将删除位置的前驱和后继连接,后将要删除的节点free
bool ListDelete(LinkList &L,int pos){
LinkList p = GetItem(L,pos-1); //获取待删除节点位置的前驱地址
if(!p){
return false;
}
LinkList q = p->next; //获取待删除节点的地址
if(!q){ //检查q是否存在
return false;
}
p->next=q->next; //将待删除节点的前驱和后继相连(孤立节点)
free(q); //删除节点
}
评论