C语言-数据结构-单链表的初始化，插入和输出

【问题描述】

设有头结点单链表，实现单链表的初始化、插入和输出算法。

【输入形式】

第一行输入一个N（N大于等于1，小于1000），一个M（N大于等于1，小于1000）；

第二行输入N个整数，以空格作为分隔，创建长度为N的单链表；

接着输入M组数据：pos和e，以空格分隔，分别表示插入位置和插入元素的值。

【输出形式】

若插入成功，输出yes；若插入不成功，输出error。

最后输出单链表所有元素（以空格分隔）。

【样例输入1】

5  3

-4  5  2  7  0

2  100

0  3

7  1

【样例输出1】

yes

error

yes

-4  100  5  2  7  0  1

链表：线性表的链式表示。

特点是采用一组任意的存储单元来存放线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。链表中每一个数据元素是由用于存放代表其本身信息的数据域和用于存放指示数据元素之间逻辑关系的指针域两部分组成的，数据元素的这种特殊存储方式，称为结点。

 链表的实现：

typedef  int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*linkList;

LNode *p的含义：

若p的值非空，则表明p指向某个结点，p->data表示p所指结点中的数据域，p->next表示p所指结点中的指针域，若非空，则指向其"后继"结点。

链表的初始化：为线性链表设定一个头指针head值向头结点，并使其指针域为空。

linkList initList()
{
    LNode *L;
    L=(LNode *)malloc(sizeof(LNode));     //申请一个头结点
    if(!L) return NULL;     //申请失败
    L->next=NULL;     //头结点指针域置空
    return L;
}

线性链表的插入：在线性链表的第i-1个结点和第i个结点之间插入第一个新的结点。

   链表的插入不需要移动元素，插入算法的基本步骤如下：

（1）寻找插入位置，即第i-1个结点位置。

（2）申请结点的存储空间，生产新结点。

（3）修改第i-1个结点和新结点的指针域，将新结点链接在链表中。

int insertList(linkList head, int pos, ElemType e)
{
    LNode*p=head,*s;
    int j=0;
    while(p&&jnext;
        if(p==NULL)
            printf("errorn");
        j++;
    }
    if(pos<1)
    {
        printf("errorn");
        return 0;
    }
    if(!p||j>pos-1)return 0;
    s=(LNode*)malloc(sizeof(LNode));
    if(!s)return 0;
    s->data=e;
    s->next=p->next;
    p->next=s;
    printf("yesn");
    return 1;
}

然后依次输出链表中的元素：

void printList(linkList head)
{
    LNode *p;
    for(p=head->next;p!=NULL;p=p->next)
        printf("%d ",p->data);
}

最后检查完整代码的运行结果：

#include
#include
typedef  int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*linkList;


linkList initList()
{
    LNode *L;
    L=(LNode *)malloc(sizeof(LNode));
    if(!L) return NULL;
    L->next=NULL;
    return L;
}


int insertList(linkList head, int pos, ElemType e)
{
    LNode*p=head,*s;
    int j=0;
    while(p&&jnext;
        if(p==NULL)
            printf("errorn");
        j++;
    }
    if(pos<1)
    {
        printf("errorn");
        return 0;
    }
    if(!p||j>pos-1)return 0;
    s=(LNode*)malloc(sizeof(LNode));
    if(!s)return 0;
    s->data=e;
    s->next=p->next;
    p->next=s;
    printf("yesn");
    return 1;
}

void printList(linkList head)
{
    LNode *p;
    for(p=head->next;p!=NULL;p=p->next)
        printf("%d ",p->data);
}
int main()
{
    linkList head;
    ElemType e;
    int i,n,m,pos;
    scanf("%d%d",&n,&m);
    head=initList();
    LNode *p,*p1;
    p=head;
    
 for(i=1;i<=n;i++){
        p1=(LNode*)malloc(sizeof(LNode));
        scanf("%d",&e);
        p1->data=e;
        p1->next=NULL;
        p->next=p1;
        p=p->next;
    }
    
for(i=1;i<=m;i++){
        scanf("%d",&pos);
        scanf("%d",&e);
        insertList(head,pos,e);
    }
    
    printList(head);
    return 0;
}

运行结果：