单链表总结
单链表的定义:
typedef struct LNode {
ElemType data;
struct LNode *next;
}Lnode,*LinkList;
初始化单链表:
Status InitList_L (LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
if (!L) exit(OVERFLOW);
L->next = null;
Return OK;
}
查找元素:
Status Getelem(Linklist &L,int i,Elemtype &e)
{
p=L-next;//让p指向第一个结点
int j=1;
while(p!=NULL&&j>i)
{
p=p->next;
j++;
}
if (!p||j>i)return ERROR; //第i个元素不存在
e=p->data;
return OK;
}
按值查找:
Status LocateNode_L(LinkList L,Elemtype key,LNode &e)
{
p=L–>next;
while( p && p–>data!=key)
p=p–>next;
if(!p) return ERROR;
e=*p;
return OK;
}
插入操作算法:
Status ListInsert_L(LinkList &L, int i, ElemType e){
//在带头结点的线性链表L中第i元素结点之前插入元素e
p=L; j=0
while (p&&j<i-1)
{p=p->next; ++j;}//寻找第i-1个元素结点
if(!p||j>i-1)
return ERROR; // i小于1 则 j>i-1
s=(LinkList)malloc(sizeof(LNode)); //分配新结点
s->data=e;
s->next=p->next;
p->next=s; //插入新结点
return OK;
}
删除操作算法:
Status ListDelete_L(LinkList &L, int i, ElemType &e){
//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
p=L; j=0;
while (p->next&&j<i-1){ //寻找第i-1个结点
p=p->next; ++j;
}
if(!p->next)||j>i-1)return ERROR; // 表中无第i个结点(i不合法)
q=p->next;p->next=q->next; //删除结点
e =q->data; free(q); // 回收(释放)结点空间
return OK;
}//
头插法建立单链表
void CreateList_L(LinkList &1, int n) {
//逆序输入n个元素的值,建立带表头结点的线性链表
L=(LinkList)malloc(sizeof (LNode));//建立头结点
L->next=NULL; //先建立一个带头结点的单链表
for (i=n; i>0;--i){
p=(LinkList)malloc(sizeof(LNode));//生成新结点
scanf(&p->data);//输入元素值
p->next=L->next;L->next=p; //插入到表头/
}
}
头插法建立单链表:
void CreateList_L(LinkList &L, int n) {
//输入n个元素的值,建立带表头结点的线性链表
L=(LinkList)malloc(sizeof (LNode));
L->next=NULL; //先建立一个带头结点的单链表
r=L;
for (i=1; i<=n;i++){
p=(LinkList)malloc(sizeof(LNode));//生成新结点
scanf(&p->data);//输入元素值
p->next=NULL;
r->next=p;
r=p;
}
}