单链表各种基本运算的算法

初始化单链表

/初始化单链表
void InitList(LinkNode *&L)
{
//创建头结点
	L=(LinkNode*)malloc(sizeof(LinkNode));
	L->next=NULL;
}

头插法建立单链表

//头插法建立单链表
void CreateListF(LinkNode *&L,ElemType a[],int n)
  {
//创建头结点
	LinkNode *s;
	L=(LinkNode*)malloc(sizeof(LinkNode));
	L->next=NULL;
        for (int i=0;idata=a[i];
// 将s插在原开始结点之前,头结点之后
			s->next=L->next;
			L->next=s;
           }
  }

尾插法建立单链表

//尾插法建立单链表
void CreateListR(LinkNode *&L,ElemType a[],int n)
  {
	int i;
	LinkNode*s,*r;
//创建头结点
	L=(LinkNode*)malloc(sizeof(LinkNode));
//r始终指向终端结点,开始时指向头结点
	r=L;
        for (i=0;idata=a[i];
//将*s插入*r之后
			r->next=s;
//尾指针r后移
			r=s;
        }
//终端结点next域置为NULL
		r->next=NULL;
  }

在单链表的指点位置插入数据元素

  //在单链表的指定位置插入结点
int ListInsert(LinkNode *&L,int i,ElemType e)
{
    int j=0;
    LinkNode *p=L,*s;
    if(i<=0)
        return false;
 //查找第i-1个结点
 while(jnext;
 }
        //未找第i-1个结点,返回false
	if (p==NULL)
		return false;
        //找到第i-1个结点p，插入新结点并返回true
	else
	{
		//创建新结点*s
		s=(LinkNode*)malloc(sizeof(LinkNode));
	  //给结点S的数据域赋值
	  s->data=e;
		//将*s插入到*p之后
		s->next=p->next;
		p->next=s;
		return true;
	}
}

删除第i个元素

//在单链表的指定位置删除结点
int ListDelete(LinkNode *&L,int i,ElemType &e)
{
    //p指向头结点，j置为0（及头结点的序号为零）
    int j=1;
    LinkNode *p=L,*q;
    if(i<=0)
        return false;
     //查找第i-1个结点
        while(j<=i-1&&p!=NULL)
        {
            j++;
            p=p->next;
        }
	//未找到第i-1个结点
	if (p==NULL)
		return false;
	else
	{
    //q指向要删除的结点
     q=p->next;
     //若不存在第i个结点，返回false
     if(q==NULL)
        return false;
     e=q->data;
	   //从单链表中删除*q结点
	   p->next=q->next;
	   free(q);
		return true;
	}
}

求单链表中第i个元素值

//求单链表中第i个元素值
int GetElem(LinkNode *L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L;
    if(i<=0)
        return false;
    //找第i个结点p
    while(j<1&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    //不存在第i个数据结点 返回false
    if(p==NULL)
        return false;
    else
        e=p->data;
    return true;
}

查找第一个值域为e的元素序号

//查找第一个值域为e的元素序号
int LocateElem(LinkNode *L,ElemType e)
{
    int i=1;
    //p指向首结点，i置为1（即首结点的序号为1）
    LinkNode *p=L->next;
    //查找data值为e的结点，其序号为i
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
        i++;
    }
    if(p==NULL)
        //不存在值为e的结点，返回0
        return(0);
    else
    //存在值为e的结点，返回逻辑序号
        return(i);
}

//判断线性表是否为空
int ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}

求单链表长度

//求单链表的长度
int ListLength(LinkNode *L)
{
    int i=0;
    //p指向头结点，i置为0（即头结点的序号为零）
    LinkNode *p=L;
    while(p->next!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}

销毁单链表

//销毁线性表
void DestroyList(LinkNode *&L)
{
    LinkNode *pre=L,*p=pre->next;
    while(p!=NULL)
    {
        free(pre);
        //pre、p同步后移一个结点
        pre=p;
        p=pre->next;
    }
    //此时p为NULL，pre指向尾结点，释放它
    free(pre);
}

输出单链表

//输出单链表
void DispList(LinkNode *L)
{
//定义指针p指向单链表的第一结点
	LinkNode*p=L->next;
	while (p!=NULL)
	{
//输出结点数据
		printf("%c",p->data);
//指针后移
		p=p->next;
	}
	printf("n");
}

判断线性表是否为空

//判断线性表是否为空
int ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}

主函数

int main()
{
    //声明变量
        int i,n=10;
    LinkNode *L;
    ElemType e;
    ElemType a[10];
    printf("请输入%d个元素: n",n);
    for(i=0;i初始化线性表Ln");
     //调用InitList（）初始化单链表
    InitList(L);
    printf("<2>初始化线性表为空！n");
    //调用ListEmpTY()判断线性表是否为空
    printf("<3>该单链表为%s!n",ListEmpty(L)?"空":"非空");
     //调用CreateListF（）建立单链表
	printf("<4>采用头插法建立单链表：n");

     CreateListF(L,a,n);
	printf("<5>输出单链表L:n");
 //调用CreateListR（）建立单链表
	printf("<6>采用尾插法建立单链表：n");

     CreateListR(L,a,n);
	printf("<7>输出单链表L:");
	//调用DispList(L) 输出线性表
	DispList(L);
	//调用ListLength()求单链表的长度
	printf("<8>该单链表的长度为：%dn",ListLength(L));
	//调用GetElem()求线性表中第i个元素值
	printf("<9>单链表中第6个元素值为：n");
	GetElem(L,6,e);
	//调用LocateElem()查找第一个值为e的元素序号
	LocateElem(L,4);
     printf("<10>在第2个元素位置上插入f元素n");
	//调用ListInsert (L);
	 ListInsert(L,2,'f');
	printf("<11>输出单链表L:");
	//调用DispList(L) 输出线性表
	DispList(L);
	printf("<12>删除L的第3个元素n");
    //调用ListDelete( );
     ListDelete(L,3,e);
	printf("<13>输出单链表L:");
//调用DispList(L) 输出线性表
    DispList(L);
    //调用DestroyList()销毁单链表
    printf("<14>销毁单链表n");
    DestroyList(L);
    printf("<15>销毁成功！");

}

单链表各种基本运算的算法

 //定义头文件
#include
#include
//定义元素类型
typedef char ElemType;
//定义单链表结点类型
typedef struct LNode
{
	ElemType data;
	//指向后继结点
	struct LNode*next;
}LinkNode;//声明单链表结点类型

//初始化单链表
void InitList(LinkNode *&L)
{
//创建头结点
	L=(LinkNode*)malloc(sizeof(LinkNode));
	L->next=NULL;
}

//头插法建立单链表
void CreateListF(LinkNode *&L,ElemType a[],int n)
  {
//创建头结点
	LinkNode *s;
	L=(LinkNode*)malloc(sizeof(LinkNode));
	L->next=NULL;
        for (int i=0;idata=a[i];
// 将s插在原开始结点之前,头结点之后
			s->next=L->next;
			L->next=s;
           }
  }

//尾插法建立单链表
void CreateListR(LinkNode *&L,ElemType a[],int n)
  {
	int i;
	LinkNode*s,*r;
//创建头结点
	L=(LinkNode*)malloc(sizeof(LinkNode));
//r始终指向终端结点,开始时指向头结点
	r=L;
        for (i=0;idata=a[i];
//将*s插入*r之后
			r->next=s;
//尾指针r后移
			r=s;
        }
//终端结点next域置为NULL
		r->next=NULL;
  }

  //在单链表的指定位置插入结点
int ListInsert(LinkNode *&L,int i,ElemType e)
{
    int j=0;
    LinkNode *p=L,*s;
    if(i<=0)
        return false;
 //查找第i-1个结点
 while(jnext;
 }
        //未找第i-1个结点,返回false
	if (p==NULL)
		return false;
        //找到第i-1个结点p，插入新结点并返回true
	else
	{
		//创建新结点*s
		s=(LinkNode*)malloc(sizeof(LinkNode));
	  //给结点S的数据域赋值
	  s->data=e;
		//将*s插入到*p之后
		s->next=p->next;
		p->next=s;
		return true;
	}
}


//在单链表的指定位置删除结点
int ListDelete(LinkNode *&L,int i,ElemType &e)
{
    //p指向头结点，j置为0（及头结点的序号为零）
    int j=1;
    LinkNode *p=L,*q;
    if(i<=0)
        return false;
     //查找第i-1个结点
        while(j<=i-1&&p!=NULL)
        {
            j++;
            p=p->next;
        }
	//未找到第i-1个结点
	if (p==NULL)
		return false;
	else
	{
    //q指向要删除的结点
     q=p->next;
     //若不存在第i个结点，返回false
     if(q==NULL)
        return false;
     e=q->data;
	   //从单链表中删除*q结点
	   p->next=q->next;
	   free(q);
		return true;
	}
}

//求单链表中第i个元素值
int GetElem(LinkNode *L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p=L;
    if(i<=0)
        return false;
    //找第i个结点p
    while(j<1&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    //不存在第i个数据结点 返回false
    if(p==NULL)
        return false;
    else
        e=p->data;
    return true;
}

//查找第一个值域为e的元素序号
int LocateElem(LinkNode *L,ElemType e)
{
    int i=1;
    //p指向首结点，i置为1（即首结点的序号为1）
    LinkNode *p=L->next;
    //查找data值为e的结点，其序号为i
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
        i++;
    }
    if(p==NULL)
        //不存在值为e的结点，返回0
        return(0);
    else
    //存在值为e的结点，返回逻辑序号
        return(i);
}

//判断线性表是否为空
int ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}

//求单链表的长度
int ListLength(LinkNode *L)
{
    int i=0;
    //p指向头结点，i置为0（即头结点的序号为零）
    LinkNode *p=L;
    while(p->next!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}

//销毁线性表
void DestroyList(LinkNode *&L)
{
    LinkNode *pre=L,*p=pre->next;
    while(p!=NULL)
    {
        free(pre);
        //pre、p同步后移一个结点
        pre=p;
        p=pre->next;
    }
    //此时p为NULL，pre指向尾结点，释放它
    free(pre);
}

 //输出单链表
void DispList(LinkNode *L)
{
//定义指针p指向单链表的第一结点
	LinkNode*p=L->next;
	while (p!=NULL)
	{
//输出结点数据
		printf("%c",p->data);
//指针后移
		p=p->next;
	}
	printf("n");
}


int main()
{
    //声明变量
        int i,n=10;
    LinkNode *L;
    ElemType e;
    ElemType a[10];
    printf("请输入%d个元素: n",n);
    for(i=0;i初始化线性表Ln");
     //调用InitList（）初始化单链表
    InitList(L);
    printf("<2>初始化线性表为空！n");
    //调用ListEmpTY()判断线性表是否为空
    printf("<3>该单链表为%s!n",ListEmpty(L)?"空":"非空");
     //调用CreateListF（）建立单链表
	printf("<4>采用头插法建立单链表：n");

     CreateListF(L,a,n);
	printf("<5>输出单链表L:n");
 //调用CreateListR（）建立单链表
	printf("<6>采用尾插法建立单链表：n");

     CreateListR(L,a,n);
	printf("<7>输出单链表L:");
	//调用DispList(L) 输出线性表
	DispList(L);
	//调用ListLength()求单链表的长度
	printf("<8>该单链表的长度为：%dn",ListLength(L));
	//调用GetElem()求线性表中第i个元素值
	printf("<9>单链表中第6个元素值为：n");
	GetElem(L,6,e);
	//调用LocateElem()查找第一个值为e的元素序号
	LocateElem(L,4);
     printf("<10>在第2个元素位置上插入f元素n");
	//调用ListInsert (L);
	 ListInsert(L,2,'f');
	printf("<11>输出单链表L:");
	//调用DispList(L) 输出线性表
	DispList(L);
	printf("<12>删除L的第3个元素n");
    //调用ListDelete( );
     ListDelete(L,3,e);
	printf("<13>输出单链表L:");
//调用DispList(L) 输出线性表
    DispList(L);
    //调用DestroyList()销毁单链表
    printf("<14>销毁单链表n");
    DestroyList(L);
    printf("<15>销毁成功！");

}