单链表--CRUD

头结点是在链表的开始结点之前附加一个结点。它具有两个优点:

1、由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;

2、无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。

3、头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。

 1、单链表的创建

注意：

  上述算法里，动态申请新结点空间时未加错误处理，这对申请空间极少的程序而言不会出问题。但在实用程序里，尤其是对空间需求较大的程序，凡是涉及动态申请空间，一定要加入错误处理以防系统无空间可供分配。

 

2、单链表的查找运算 

（1）按序号查找

   ① 链表不是随机存取结构,在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。

   ② 查找的思想方法

    　计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为NULL且j≠i时，则表示找不到第i个结点。注意：头结点可看做是第0个结点。

   ③算法分析：

while语句的终止条件是搜索到表尾或者满足j≥i，其频度最多为i，它和被寻找的位置有关。在等概率假设下，平均时间复杂度为：O(n)。

（2）按值查找

   ①思想方法 

    从开始结点出发，顺着链逐个将结点的值和给定值key作比较，若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。

   ②算法分析

    　该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为O(n)。

3.插入运算
（1）思想方法
    　插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。

 (2)算法分析

    　算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。

4.删除运算
（1）思想方法
   　 删除运算是将表的第i个结点删去。
具体步骤： 
   　（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
   　（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
   　（3）释放结点ai的空间，将其归还给"存储池"。

 
注意：
    　设单链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的。
   　 当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-＞next！=NULL）时，才能确定被删结点存在。

（2）算法分析
    　算法的时间复杂度也是O（n）。
    　链表上实现的插入和删除运算，无须移动结点，仅需修改指针。

 

#include<stdio.h>
#include<malloc.h>
typedef char DataType;
typedef struct node
        {
            DataType data;
            struct node * next;
        }ListNode;

typedef struct node *LinkList;



void print(LinkList head)
{
    LinkList p=head->next;
    while(p)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    printf("\n");
}

/*
**从开始结点出发，顺着链逐个将结点的值和给定值key作比较，
**若有结点的值与key相等，则返回首次找到的其值为key的结点的存储位置；
**否则返回NULL。
*/
ListNode * getNodeByVal(LinkList head,char key)
{
    LinkList p=head->next;
    while(p && p->data != key)
    {
        p=p->next;
    }
    return p;
}

/*
**按序号查找，
**在带头结点的单链表head中查找第i个结点，
**若找到（0≤i≤n）,0为头结点
*/
ListNode * getNodeByNum(LinkList head,int i)
{
    int j;
    ListNode * p;
    p=head;
    j=0;//从头结点开始扫描
    while(p->next && j<i)
    {
        p=p->next;
        j++;
    }
    if(i==j)
        return p;
    else
        return NULL;//当传入的i <0 || i>n无效

}

/*
**插入运算是将值为x的新结点插入到表的第i个结点的位置上，
**即插入到ai-1与ai之间
*/
ListNode * insertList(LinkList head,char x, int i)
{
    LinkList p=getNodeByNum(head,i-1);//寻找第i-1个结点
    if(p==NULL)//i<1或i>n+1时插入位置i有错
    {
         printf("position error");
    }
    LinkList s=(ListNode *)malloc(sizeof(ListNode));
    s->data=x;
    s->next=p->next;
    p->next=s;
    return head;
}
/*
**删除运算是将表的第i个结点删去
**设单链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的。
*/
LinkList delList(LinkList head,int i)
{
    LinkList p=getNodeByNum(head,i-1);//寻找第i-1个结点
    if(p==NULL || p->next == NULL)//i<0或i=>n时删除位置i有错
    {
         printf("position error");
    }
    LinkList r=p->next;//r指向将要删除的节点
    p->next = r->next;
    free(r);
    return head;
}

/*
**尾插法创建带头结点链表
*/
LinkList CreatListR(void)
{
    char ch;
    LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成头结点，可以存储一些信息
    LinkList r,s;
    r=head;
    while(scanf("%c",&ch)!=EOF && ch!='0')
    {
        s =(ListNode *)malloc(sizeof(ListNode));
        s->data=ch;
        r->next=s;
        r=s;
    }
    r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
    return head;
}

int main()
{
    /*注意一下字符输入与整数吾同
    abcdef0
    dPress any key to continue*/
    LinkList head=CreatListR();
    LinkList NUM4=getNodeByNum(head,4);
    printf("%c",NUM4->data);

    NUM4 = getNodeByVal(head,'d');
    printf("\n%c",NUM4->data);

    head=insertList(head,'e',5);
    print(head);
    head=delList(head,5);
    print(head);
    return 0;
}