单链表的基本操作

#include<stdio.h>
#include<malloc.h>
typedef int DataType;
typedef struct linknode
{
    DataType data;
    struct linknode *next;
}LinkList;

/* 单链表的初始化：
首先申请一个结点并让指针head指向该结点，
然后将它的指针域赋为空（NULL），
最后返回头指针head
*/

LinkList* InitList()//初始化
{
    LinkList *head;
    head=(LinkList*)malloc(sizeof(LinkList));//分配空间
    head->next=NULL;
    return head;
}

void CreateListHead(LinkList *head,int n)//头插法建表
{
    LinkList *s;
    int i;
    printf("请输入%d个整数：",n);
    for(i=0;i<n;i++)
    {
        s=(LinkList*)malloc(sizeof(LinkList));
        scanf("%d",&s->data);
        s->next=head->next;
        head->next=s;
    }
    printf("单链表建立完成！\n");
}

void CreateListLast(LinkList *head,int n)//尾插法建表
{
    LinkList *s,*last;
    int i;
    last=head;//开始时指向头结点
    printf("请输入%d个整数：",n);
    for(i=0;i<n;i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList));
        scanf("%d",&s->data);
        s->next=NULL;
        last->next=s;
        last=s;//将last指针指向表尾结点
    }
    printf("单链表建立完成！\n");
}

int LengthList(LinkList *head)//求链表长度
{
    LinkList *p=head->next;
    int j=0;
    while(p!=NULL)
    {
        p=p->next;
        j++;
    }
    return j;
}

void Locate(LinkList *head,DataType x)
{
    int j=1;
    LinkList *p;
    p=head->next;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
        j++;
    }
    if(p!=NULL)
        printf("在表的第%d位找到值为%d的结点",j,x);
    else
        printf("表中没有值为%d的结点！",x);
}

void SearchList(LinkList *head,int i)//按位查找
{
    LinkList *p;
    int j=0;
    p=head;
    if(i<0||i>LengthList(head))
        printf("输入的位置错误");
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
    if(j==i)
        printf("在第%d位上的元素值为%d",i,p->data);
}

void DispList(LinkList *head)
{
    LinkList *p;
    p=head->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
}

void InsList(LinkList *head,int i,DataType x)//插入元素
{
    int j=0;
    LinkList *p,*s;
    p=head;
    while(p->next!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p!=NULL)
    {
        s=(LinkList*)malloc(sizeof(LinkList));
        s->data=x;
        s->next=p->next;
        p->next=s;
        printf("插入元素成功！\n");
    }
    else
        printf("插入元素失败！\n");
}

void DelList(LinkList *head,int i)//删除元素
{
    int j=0;
    DataType x;
    LinkList *p=head,*s;
    while(p->next!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    s=p->next;
    p->next=s->next;
    x=s->data;//把要删除的元素的值放入x中
    free(s);
}



int main()
{
    LinkList *head;
    int n,j,i;
    DataType x;

    head=InitList();

    printf("请输入要建立的单链表的长度：\n");
    scanf("%d",&n);
    //CreateListHead(head,n);//‘头插法’建立一个单链表
    CreateListLast(head,n);//‘尾插法’建立一个单链表

    j=LengthList(head);//单链表长度
    printf("链表的长度为：%d\n",j);

    printf("请输入要查的数值：");
    scanf("%d",&x);
    Locate(head,x);//按值查找
    printf("\n");

    printf("请输入查找的元素位置：");
    scanf("%d",&i);
    SearchList(head,i);//按位查找
    printf("\n");

    printf("请输入要插入的元素的位置：");
    scanf("%d",&i);
    printf("请输入要插入的元素的数值：");
    scanf("%d",&x);
    InsList(head,i,x);//插入元素
    printf("显示单链表：");
    DispList(head);//显示元素

    printf("\n请输入要删除的元素的位置：");
    scanf("%d",&i);
    DelList(head,i);//删除元素
    printf("显示单链表：");
    DispList(head);//显示元素
}