单链表

//链式存储结构 -- 单链表


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

typedef struct node{ //结点类型定义

    int data; //结点的数据域

    struct node *next; //结点的指针域

}ListNode;

typedef ListNode *LinkList;
ListNode *p;
ListNode *pHead = NULL;

//改进：使用与线分配好的静态数组避免malloc失败

//use static buffer

//int a[100] = {0};


//用尾插法建立带头结点的单链表 O(n)

LinkList CreatListR1(void)
{
    char ch;
    LinkList head=(ListNode *)malloc(sizeof(ListNode));//生成头结点

    ListNode *s,*r; //工作指针

    r=head; // 尾指针初值也指向头结点

    while((ch=getchar())!='\n'){
        s=(ListNode *)malloc(sizeof(ListNode));//生成新结点

        s->data=ch; //将读入的数据放入新结点的数据域中

        r->next=s;
        r=s;
    }
    r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空


    return head;
}

//尾插法建循环单链表 返回单链表的头指针 O(n)

LinkList CreatListB(int len)
{
    LinkList head = NULL; //头指针

    ListNode *s = NULL; //工作指针

    ListNode *r = NULL; //工作指针(尾)

        
    for(int i=1; i<=len; ++i){
        s=(ListNode *)malloc(sizeof(ListNode));//生成新结点

        s->data = i;
        if (head==NULL)
            head=s;//新结点插入空表

        else
            r->next=s;//将新结点插到*r之后

        r=s;//尾指针指向新表尾

    }
    r->next = head;//头尾相连

    
    return head;
}

//头插法建循环单链表 返回单链表的头指针 O(n)

LinkList CreatListF(int len)
{
    LinkList head = NULL; //头指针

    ListNode *s = NULL; //工作指针

    ListNode *r = NULL; //工作指针(尾)


    for(int i=1; i<=len; ++i){
        s = (ListNode *)malloc(sizeof(ListNode));
        s->data = i;
        s->next = head;
        if(head!=NULL)
            head = s;
        else
            r = head = s;
    }
    r->next = head;//头尾相连

    
    return head;
}

//打印循环链表

void printList(LinkList p)
{
    ListNode *head = p;
    ListNode *tmp = p;

    if(p->next == p){
        printf("%d\n", tmp->data);
        return;
    }

    do{
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }while(head != tmp);
    putchar('\n');
}

int main(void)
{
    int len;
    printf("input len: ");
    scanf(" %d", &len);

    LinkList p1 = CreatListF(len);
    printList(p1);

    LinkList p2 = CreatListB(len);
    printList(p2);

    return 0;
}