Code,  Study,  Tech

单链表实现:建表和查找

注:

单链表最后一个结点的指针为“空”(NULL),当链表为空时,则表头指针为空。

建表时不论是空表还是元素读取结束都要记得将末元素后继置空!


  • 建表(头插与尾插):

LL_Create().c源码:

#include<stdio.h>
#include<malloc.h>


/***********单链表结点结构体定义**************/
typedef struct node
{
    int data; //数据域
    struct node *next;//指向后继结点的指针域
}NODE;


/***********头插法建表函数**************/
NODE *Head_Create()
{

    NODE *head;//声明头结点
    head = (NODE*)malloc(sizeof(NODE));//建立头结点

    NODE *p;//p为待插入结点

    NODE *first;//辅助结点first,即链表首结点(除头结点外)

    char ch;//输入结束标志
    ch = '*';//输入结束标志初始化为*
    int x;//a存储建表时插入元素的值

    head ->next = NULL;//初始化空链表,头结点后继置空

    first = head ->next;//将first设在头结点后,元素的插入将在头结点与first之间执行

    printf("--------用头插法建立单链表,请输入链表数据,以?结束。--------\n");

    while(ch != '?')//输入结束标志用?(英文)结束
    {
        scanf("%d", &x); //读取输入元素值

        p = (NODE*) malloc(sizeof(NODE));//初始化新结点
        p ->data = x;//将值赋给新结点data域

        head ->next = p;//修改头结点之后指针为新结点
        p ->next = first;//将p的后继改成原头结点后第一个元素first
        first = p;//修改first为新插入的结点q

        ch = getchar();//读取输入标志
    }

    return(head);//返回头结点
}

/***********尾插法建表函数**************/
NODE *Tail_Create()
{
    NODE *head;//声明头结点
    head = (NODE*)malloc(sizeof(NODE));//建立头结点

    NODE *p;//p为待插入结点

    NODE *last;//辅助结点last,即链表末结点

    char ch;//输入结束标志
    ch = '*';//输入结束标志初始化为*
    int x;//a存储建表时插入元素的值

    last = head;//末结点last在链表初始空时即头结点

    printf("--------用尾插法建立单链表,请输入链表数据,以?结束。--------\n");

    while(ch != '?')//输入结束标志用?(英文)结束
    {
        scanf("%d", &x); //读取输入元素值

        p = (NODE*) malloc(sizeof(NODE));//初始化新结点
        p ->data = x;//将值赋给新结点data域
        last ->next = p;//修改末结点后继为新插入的结点p
        last = p;//将末结点设为新插入的p

        ch = getchar();//读取输入标志
    }

    last ->next = NULL;//读取完插入元素后将链表末结点后继置空
    return(head);//返回头结点

}

/***********遍历输出表元素**************/
void LL_Display(NODE *Llist)
{
      printf("--------------输出单链表元素:--------------\n");
    //遍历单链表执行输出
    Llist = Llist ->next; //指到第一个结点
    while(Llist != NULL)
    {
        printf("%d ",Llist ->data);//非空则输出元素值
        Llist = Llist ->next;//指向下一个元素
    }
}

int main(void)
{
    printf("--------------使用C语言创建单链表:--------------\n");
    printf("*****请选择你想使用的建表方式,输入数字序号*****\n");
    printf("*****1.头插法*****\n");
    printf("*****2.尾插法*****\n");

    int op_id = 0;
    scanf("%d", &op_id);

    switch(op_id)
    {
    case 1://头插
        {
            NODE *hc;
            hc = Head_Create();//创建单链表hc
            LL_Display(hc);
        }
        break;

    case 2://尾插
        {
            NODE *tc;
            tc = Tail_Create();//创建单链表tc
            LL_Display(tc);
        }
        break;
    }

    return 0;
}

测试输出:

--------------使用C语言创建单链表:--------------
*****请选择你想使用的建表方式,输入数字序号*****
*****1.头插法*****
*****2.尾插法*****
1
--------用头插法建立单链表,请输入链表数据,以?结束。--------
1 2 3 4 5?
--------------输出单链表元素:--------------
5 4 3 2 1
*********************************************************************
2
--------用尾插法建立单链表,请输入链表数据,以?结束。--------
1 2 3 4?
--------------输出单链表元素:--------------
1 2 3 4

  • 按位查找:find_position()函数
NODE *find_position(NODE *head, int i)
{
    int j = 1;
    NODE *p;
    p = head ->next;
    while((p!=NULL) && (j < i))
    {
        p = p ->next;
        j++;
    }

    return p;
}

  • 按值查找:find_value()函数
NODE *find_value(NODE *head, int vl)
{
    int j = 1;
    NODE *p;
    p = head ->next;
    while((p!=NULL)&&(p ->data != vl))
    {
        p = p->next;
        j++;
    }

    return p;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注