單鏈表創建、刪除、查找、插入之C語言實現

本文將詳細的介紹C語言單鏈表的創建、刪除、查找、插入以及輸出功能

一、創建

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
/*結構體部分*/
typedef struct Node
{
    ElemType data;   //數值域
    struct Node *next;  //指針域
}Linklist;

Linklist *InitList(Linklist *L)    //初始化單鏈表
{
    L = (Linklist *) malloc(sizeof(Linklist));
    L->next = NULL;
    return L;
}

Linklist *CreateList(int n)
{
    /*通過輸入n個數據，創建一個單鏈表*/
    int x,i;
    Linklist *L,*r,*p;
    L = InitList(L); //構造頭結點
    r = L;
    printf("input %d value: ",n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        p = (Linklist *)malloc(sizeof(Linklist));
        p -> data = x;
        p -> next = NULL;
        r->next = p;
        r = r->next;    //指針r始終指向鏈表中末數據元素所在位置

    }
    return L;
}

二、插入

int InsItem1(Linklist *L,ElemType item,int x) /*給定的序號來插入*/
{
    int i = 1;
    Linklist *p,*t;
    p = L;
    t = (Linklist *)malloc(sizeof(Linklist));
    t ->data = item;
    if(L->next==NULL)
    {   /*若L為空表且要求將新結點插入到第0個位置*/
        if(x==1)
            {
                L->next=t;
                t->next=NULL;
                return 1;
            }
        /*若L為空表且要求將新結點插入到第非0個位置     ，則操作失敗*/
        else
        {
            printf("wrong!\n");
            return 0;
        }
    }
    while(p->next!=NULL&&i<x)
    /*查找第i個節點*/
    {
        p = p->next;
        i++;
    }
    if(p->next==NULL&&i<x)
    /*在表中不存在插入位置i ，找不到，則插入操作失敗*/
    {
        printf("The node %d is not exist\n",x);
        return 0;
    }
    else
    {
        t->next = p->next;
        p->next = t;
        return 1;
    }
}

int InsItem2(Linklist *L,ElemType item,ElemType k) /*插入給定值在鏈表中的位置*/
{
    Linklist *q,*p,*t;
    t = (Linklist *)malloc(sizeof(Linklist));
    t->data = item;
    if(L->next==NULL)
    {
        printf("The linklist is empty\n");
        return 0;
    }
    else
    {
        q = L;
        p = L->next;
        while(p->next!=NULL)/*查找值為k的結點*/
        {
            if(p->data!=k)
            {
                q = p;
                p = p->next;
            }
            else
                break;
        }
        if(p==NULL)/*如p= =NULL，則沒有值為k的結點，插入操作失敗*/
        {
            printf("The node %d is not exist\n",k);
            return 0;
        }
        else
        {
            q->next = t;
            t->next = p;
            return 1;
        }
    }
}

三、刪除

int DelItem(Linklist *L,int x)
//在單鏈表中刪除數據元素
{
    int i = 1;
    Linklist *p,*q;
    p = L;
    if(L->next==NULL) /*L為空表，無結點可刪除*/
    {
        printf("The linklist is empty!\n");
        return 0;
    }
    while(p->next!=NULL&&i<x)
    {
        p = p->next;
        i++;
    }
    if(p->next==NULL)
        /*若沒有第i個結點，則刪除操作失敗*/
    {
        printf("The node %d is not exist\n",x);
        return 0;
    }
    else
    {
        q = p->next;
        p->next = p->next->next;
        free(q);
        return 1;
    }

}

四、查找

int LocItem(Linklist *L,ElemType x)
//查找給定值的結點位置
{
    Linklist *p,*q,*r;
    int i = 1;
    if(L->next==NULL)
    {
        printf("The linklist is empty\n");
        return 0;
    }
    else
    {
        p = L->next;
        while(p!=NULL)
        {
            if(p->data!=x)
            {
                i++;
                p = p->next;
            }
            else
                break;
        }
        if(p==NULL)
        /*如p= =NULL，則沒有值為item的結點，刪除操作失敗*/
        {
            printf("The node %d is not exist\n",x);
            return 0;
        }
        /*若找到該節點返回該節點的位置*/
        else
            return i;
    }
}

五、輸出

void output(Linklist *L) //輸出
{
    Linklist *p;
    p = L->next;
    printf("output element: \n");
    for(;p!=NULL;p=p->next)
    {
        printf(" %d ",p->data);
    }
    printf("\n");
}

六、主函數部分

int main()
{
    ElemType x = 5;
    Linklist *L;
    L = CreateList(x);
    output(L);
    InsItem1(L,3,2);
    output(L);
    InsItem1(L,3,4);
    output(L);
    DelItem(L,3);
    output(L);
    printf("3的位置是: %d",LocItem(L,3));
}