[C++知识库]单链表的基本操作（C语言实现）

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<malloc.h>
#define ElemType int
typedef struct LNode		//单链表结点类型
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

int Length(LinkList L)		//测表长
{
	int j=0;
    LNode *p=L->next;
    while(p!=NULL)
    {
    	p=p->next;
        j++;
    }
    return j;
}

LinkList HeadInsert(LinkList L)		//头插法创建单链表（带头结点）
{
    LNode *s;
    int e;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&e);
    while(e!=-1)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L->next;
        L->next=s;
        scanf("%d",&e);
    }
    return L;
}

LinkList TailInsert(LinkList L)		//尾插法创建单链表（带头结点）
{
    int e;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s=NULL;
    LNode *r=L;			//定义尾指针，注意在L初始化之后
    scanf("%d",&e);
    while(e!=-1)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        r->next=s;
        r=s;
        scanf("%d",&e);
    }
    r->next=NULL;
    return L;
}

LNode *GetElem(LinkList L,int i)		//按序号查找结点，并返回其地址
{
    int j=1;
    LNode *p=L->next;
    if(i==0)
    	return L;
    if(i<1||i>Length(L))
    	return NULL;
    for(j=1;j<i;j++)
    	p=p->next;
    return p;
}

LNode *LocateElem(LinkList L,ElemType e)	//按值查找结点，并返回其地址
{
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;
}

bool ListInsert(LinkList L,ElemType e,int i)		//向单链表插入结点
{
    LNode *s=(LNode*)malloc(sizeof(LNode));
    LNode *r=GetElem(L,i-1);
    if(i<1||i>Length(L))
    	return false;
    s->data=e;
   	s->next=r->next;
    r->next=s;
    return true;
}

bool ListDelete(LinkList L,int i)
{
    LNode *s=GetElem(L,i);
    LNode *r=GetElem(L,i-1);
    if(i<1||i>Length(L))
    	return false;
    r->next=s->next;
    free(s);
    return true;
}
void display(LinkList L)		//输出当前单链表
{
    printf("当前单链表内元素是：");
    LNode *p=L->next;
    for(p=L->next;p!=NULL;)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

int main()
{
    LinkList L=NULL;
    int e,i,t;
    LNode *p=NULL;
    
    //测试HeadInsert
    printf("请输入任意个数字来组成单链表（头插法）:");
    L=HeadInsert(L);
    display(L);
    
    //测试TailInsert
    printf("请输入任意个数字来组成单链表（尾插法）:");
    L=TailInsert(L);
    display(L);
    

    //测试GetElem
    printf("请输入你要查找的元素的位序：");
    scanf("%d",&i);
    p=GetElem(L,i);
    printf("该元素的值为：%d\n",*p);
    
    //测试LocateElem
    printf("请输入你要查找的元素的值：");
    scanf("%d",&e);
    p=LocateElem(L,e);
    printf("该元素的地址为：%p\n",p);
    
    //测试ListInsert
    printf("请输入你要插入的元素的值：");
    scanf("%d",&e);
    printf("请输入你要将该元素插入表的位序：");
    scanf("%d",&i);
    t=ListInsert(L,e,i);
    if(t)
    	printf("插入成功！\n");
    else
    	printf("插入失败！\n");
    display(L);
    
    //测试ListDelete
    printf("请输入你想删除的元素的位序：");
    scanf("%d",&i);
    t=ListDelete(L,i);
    if(t)
    	printf("删除成功！\n");
    else
    	printf("删除失败！\n");
    display(L);
    
    return 0;
}