11、单链表的新建、查找

本章需要掌握：

1、单链表怎么定义？
2、对单链表来说头插、尾插、查找（位/值）、插入i位置e操作代码。

1、头插、尾插、查找（位/值）、插入i位置e

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

typedef int ElemType;
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;
}LNode,*LinkList;

//LNode*是结构体指针，和LinkList完全等价的
//输入3,4,5,6,7,9999
void list_head_insert(LNode* &L)
{
    L= (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s;//用来指向申请的新结点
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;//s的next指向原本链表的第一个结点
        L->next=s;//头结点的next，指向新结点
        scanf("%d",&x);
    }
}

//尾插法新建链表
void list_tail_insert(LNode* &L)
{
    L= (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;//s是用来指向申请的新结点，r始终指向链表尾部
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
        s->data=x;
        r->next=s;//新结点给尾结点的next指针
        r=s;//r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;//让尾结点的next为NULL
}

void print_list(LinkList L)
{
    L=L->next;
    while(L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}

//按位置查找
LinkList GetElem(LinkList L,int SearchPos)
{
    int j=0;
    if(SearchPos<0)
    {
        return NULL;
    }
    while(L&&j<SearchPos)
    {
        L=L->next;
        j++;
    }
    return L;
}

//按值查找
LinkList LocateElem(LinkList L,ElemType SearchVal)
{
    while(L)
    {
        if(L->data==SearchVal)//如果找到对应的值，就返回那个结点的地址
        {
            return L;
        }
        L=L->next;
    }
    return NULL;
}

//i代表插入到第几个位置
bool ListFrontInsert(LinkList L,int i,ElemType InsertVal)
{
    LinkList p= GetElem(L,i-1);
    if(NULL==p)
    {
        return false;
    }
    LinkList q;
    q=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
    q->data=InsertVal;
    q->next=p->next;
    p->next=q;
    return true;
}

//头插法，尾插法来新建链表
int main() {
    LinkList L,search;//L是链表头指针，是结构体指针类型
//    list_head_insert(L);//输入数据可以为3 4 5 6 7 9999,头插法新建链表
    list_tail_insert(L);
    print_list(L);//链表打印
//    //按位置查找
//    search=GetElem(L,2);
//    if(search!=NULL)
//    {
//        printf("Succeeded in searching by serial number\n");
//        printf("%d\n",search->data);
//    }
//    search=LocateElem(L,6);//按值查询
//    if(search!=NULL)
//    {
//        printf("Search by value succeeded\n");
//        printf("%d\n",search->data);
//    }
    bool ret;
    ret=ListFrontInsert(L,2,99);//新结点插入第i个位置
    print_list(L);
    return 0;
}

🌺2、OJ作业

网站：http://oj.lgwenda.com/

1、链表（LinkList）

描述：输入3 4 5 6 7 9999一串整数，9999代表结束，通过头插法新建链表，并输出，通过尾插法新建链表并输出。

输入：3 4 5 6 7 9999，第二行也是3 4 5 6 7 9999，数据需要输入两次

输出：如果输入是3 4 5 6 7 9999，那么输出是7 6 5 4 3，数之间空格隔开，尾插法的输出是3 4 5 6 7

🌺🌺🌺题解ヾ（^▽^）ゞ🌼🌼🌼

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

typedef int ElemType;
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode,*LinkList;

void list_head_insert(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));//给头指针申请空间
    L->next=NULL;
    ElemType x;
    LinkList s;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));//给新结点申请空间
        s->data=x;//把读取到的数据放入新结点的数据域
        s->next=L->next;//让新结点指向原有链表的第一个结点
        L->next=s;//新结点成为第一个结点
        scanf("%d",&x);
    }
}

void PrintList(LinkList L) {
    L = L->next;//去到第一个结点
    while (L != NULL) {
        printf("%d", L->data);//打印当前结点数据
        L = L->next;//指向下一个结点
        if (L != NULL) {
            printf(" ");
        }
    }
    printf("\n");
}

void list_tail_insert(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));//给头指针申请空间
    L->next=NULL;
    ElemType x;
    LinkList s,r=L;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));//给新结点申请空间
        s->data=x;//把读取到的数据放入新结点的数据域
        r->next=s;//原有链表的尾结点的next，指向新结点
        r=s;//尾指针指向新的尾结点
        scanf("%d",&x);
    }
    r->next=NULL;//尾结点的next要为NULL
}
int main() {
    LinkList L;//链表头指针，代表链表
    list_head_insert(L);
    PrintList(L);
    list_tail_insert(L);//尾插法新建链表
    PrintList(L);
    return 0;
}