【数据结构】顺序表、单链表、循环链表的插入与删除
写在前面的在复习数据结构的过程中对于链表的操作总是容易忘记,时不时的就不知道具体的该怎么操作了,所以把这几个比较细节的地方总结一下,让自己印象加深一下,给之后的学习做个参考。 接下来主要总结一下单链表和循环链表的插入与删除的方法和具体的代码。导图如下 顺序表插入
void InsertSeqlist(SeqList L,DataType x,int i)
{
//将元素x插入到顺序表L的第i个数据元素之前
if(L.length==Maxsize) exit("该链表已满!");
if(i<1 || i>L.length + 1) exit("插入非法位置!");
for(j=L.length,j>=i;j--)
{
L.data[j]=L.data[j-1]; //依次后移
}
L.data[i-1]=x; //将x插入到下标为i-1的位置
L.length++; //表长加1
}
删除
void DeleteSeqList(SeqList L,int i)
{
//删除线性表L中第i个结点
if(i<1 || i>L.length) exit("非法位置!");
for(j=i; j<L.length; j++) //第i个元素的下角标为i-1
{
L.data[j-1]=L.data[j]; //依次左移
}
L.length--;
}
定位
int LocateSeqList(SeqList L,DataType x)
{
int i=0;
while((i<L.length) && (L.data[i]!=x)) //在顺序表中查找值为x的节点
{
i++;
}
if(i<L.length) return i+1;
else return 0;
}
单链表插入
void InsertLinklist(LinkList head,int i)
{
Node *p,*q;
if(i==1) q=head;
else q=GetLinklist(head,i-1); //找到第i-1 个数据元素节点
if(q==NULL) exit("找不到插入的位置!"); //第i-1个节点不存在
else
{
p=malloc(sizeof(Node)); p->data=x; //生成新节点
p->next=q->next; //新街点链指向*q的后继节点
q->next=p; //修改*q的链域
}
}
"链接操作p->next=q->next 和 q->next=p 两条语句的执行顺序不能颠倒,否则结点*q的链域值(指向原表第i个结点的指针)将丢失"
删除
void DeleteLinklist(LinkList head,int i)
{
Node *q;
if (i==1) q=head;
else q=GetLinklist(head,i-1); //先找待删除节点的直接前驱
if(q!=NULL && q->next!=NULL) //若直接前驱存在切待删除结点存在
{
p=q->next; //p指向待删除结点
q->next=p->next; //移除待删除结点
free(p); //释放已移除的结点p的空间
}
else exit("找不到要删除的结点!")
}
双向循环链表删除
p->prior->next=p->next; //p前驱结点的后链指向p的后继结点
p->next->prior=p->prior; //p后继节点的前链指向p的前驱结点
free(p); //释放*p的空间
"前两行的语句可以颠倒"
导图如下: 插入
t->prior=p;
t->next=p->next;
p->next->prior=t;
p->next=t;
总结
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |