线性表的链式储存(链表)
typedef struct LNode *List;
struct LNode
{
ElementType Data;
List Next;
};
struct LNode L;
List PTRL;
求表长
int Length(List PtrL)
{
List p=PtrL; /* p指向的是第一个结点*/
int j=0;
while(p)
{
p=p->Next;
j++; /* 当前p指向的是第j个结点*/
}
return j;
}
//时间性能为O(n)
查找(按序号查找:FindKth)
List FindKth(int K,List PtrL)
{
List p=Ptrl;
int i=1;
while (p!=NULL&&i<K)
{
p=p->Next;
i++;
}
if(i==K)return p; /* 找到第K个,返回指针*/
else return NULL; /*否则返回空*/
}
查找(按值查找:Find)
List Find(ElementType X,List PtrL)
{
List p=PtrL;
while(p!=NULL&&p->Date!=X)
p=p->Next;
return p;
}
插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点)
List Insert(ElementType X,int i,List PrtL)
{
List p,s;
if(i==1) /* 新结点插入在表头*/
{
s=(List)malloc(sizeof(struct LNode)); /* 申请、填装结点*/
s->Date=X;
s->Next=PtrL;
return s; /* 返回新表头指针*/
}
p=FindKth(i-1,PtrL) /* 查找第i-1个结点*/
if(p==NULL) /* 第i-1个不存在,不能插入*/
{
printf("参数i错");
return NULL;
}
else
{
s=(List)malloc(sizeof(struct LNode)); /* 申请、填装结点*/
s->Date=X;
s->Next=p->Next; /* 新结点插入在第i-1个结点的后面*/
p->Next=s;
return PtrL;
}
}
删除(删除链表的第i(1<=i<=n)个位置上的结点)
List Delete(int i,List PtrL)
{
List p,s;
if(i==1) /* 若要删除的是表的第一个结点*/
{
s=PtrL; /* s指向第一个结点*/
if(PtrL!=NULL)PtrL=PtrL->Next; /* 从链表中删除*/
else return NULL;
free(s); /* 释放被删除结点*/
return PtrL;
}
p=FindKth(i-1,PtrL); /* 查找第i-1个结点 */
if(p==NULL)
{
printf("第%d个结点不存在",i-1);
return NULL;
}
else if(p->Next==NULL)
{
printf("第%d个结点不存在",i);
return NULL;
}
else
{
s=p->Next; /* s指向第i个结点*/
p->Next-s->Next; /* 从链表中删除*/
free(s); /* 释放被删除结点*/
return PtrL;
}
}
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 zzzqqqyyy2002@163.com