C语言之链表

  这两天在复习C语言的知识,为了给下个阶段学习OC做准备,以下的代码的编译运行环境是Xcode5.0版本,写篇博文把昨天复习的C语言有关链表的知识给大家分享一下,以下是小菜自己总结的内容,代码也是按照自己的思路所编写的,有不足之处还请大牛们批评指教。

  确切的说链表属于数据结构中线性表中的内容,在链表中存储的内容是按线性排列的,就像是一条线把所要存的数据串起来,可以把链表类比成一串珠子,数据就是一个个的珠子,数据间的next指针就相当于穿珠子的线。

  链表操作的时间复杂度: 往链表中插入数据的时间复杂度为O(1)。

  想真正的理解链表及在C语言中的表示方法的前提是理解C语言中的指针和结构体,闲话少说,进代码才是关键,代码中基本上都有注释

  1.用结构体定义链表的节点

 //定义链表中的节点
 typedef struct node{
     //存储数据
     int data;
     //指向下一个节点
     struct node *next;
 }Node;

  2.定义链表的整体结构,存放链表的节点和链表中的信息

//定义链表结构
typedef struct {
    //存放头节点
    Node *head;
    //记录节点的个数
    int count;
}List;

  

  3.链表的初始化,给链表分配头结点,节点个数初始化为0

/************************************************
 *功能:初始化链表,分配头结点,结点个数为0
 *参数:链表指针
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
void initLinkList(List *list)
{
    //给头节点分配内存
    list->head = malloc(sizeof(Node));
    //头结点的下一个节点为空
    list->head->next = NULL;
    //总节点个数为0
    list->count = ;
}

  4.建立单项链表,这里为了简单起见,把要存入数据先存入到array中,下面我是用逆序的方法来创建链表的,是从head节点后插入数据,也可以用顺序建链表,从链表的后面插入数据

/************************************************
 *功能:逆序建立链表,从头结点后插入
 *参数:链表指针
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
void createLinkList(List *list)
{
    //建立链表用到的数据
    ] = {,,,,,,,,,};
    //临时节点指针用于分配节点内存
    Node *p;
    ; i < ; i++)
    {
        //给新的节点分配内存
        p = (Node *)malloc(sizeof(Node));
        //给新节点赋值
        p->data = a[i];
        //把值加入到头节点后面,逆序建立链表
        p->next = list->head->next;
        list->head->next = p;
        //链表节点个数加一
        list->count++;
    }
}

  5.为了方便查看链表中的值,需要一个打印链表中的数据的函数

/************************************************
 *功能:打印链表中的值
 *参数:链表指针
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
void printList(List *list)
{
    //临时节点指针变量
    Node *p;
    //从头开始遍历
    p = list->head->next;
    while (p != NULL)
    {
        //自定义的输出整的函数
        print(p->data);
        p = p->next;
    }
    putchar('\n');
}

  6.查询元素在链表中对于的位置

/************************************************
 *功能:查找链表中指定值的位置,有的返还其位置,无,返还-1
 *参数:链表指针,要查找的值
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
int search(List *list, int obj)
{
    //定义游标指针
    Node *p;
    //标记值的位置
    ;
    p = list->head->next;
    while (p != NULL)
    {
        local ++;
        if (p->data == obj)
        {
            //返回值的位置
            return local;
        }
        p = p->next;
    }
    //值不存在返回-1
    ;
}

  7.删除链表中的相应的数据

/************************************************
 *功能:删除链表中的值
 *参数:链表指针,要删除的值
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
void delete(List *list, int obj)
{
    //查询要删除的元素是否在链表中,有返还相应的位置,没有则返还-1
    int flag = search(list, obj);

    //判断值的合法性
    )
    {
        printf("没有要删除的值!\n");
    }
    else
    {
        //定义两个辅助游标指针
        Node *p, *q;

        //给q,p赋值
        q= list->head;
        p = list->head->next;

        //循环查找相应的值并删除
        while (p != NULL)
        {
            if (p->data == obj)
            {
                q->next = p->next;
                p->next = NULL;
                free(p);
                break;
            }
            q = p;
            p = p->next;
        }
    }
}

  8.往链表中插入数据

/************************************************
 *功能:往指定的位置后插入相应的值
 *参数:链表指针,插入的位置,插入的值
 *作者:Mr.li
 *日期:14-07-23
 ************************************************/
void insert(List *list, int local, int number)
{
    ;
    //判断值的合法性
    if(count > list->count)
    {
        printf("你输入的值不合法\n");
    }
    else
    {
        //定义游标指针,指向链表的头结点
        Node *p = list->head;
        while (count != local) {
            p++;
            count++;
        }

        //分配新的结点并给新的结点赋值
        Node *q = (Node *) malloc(sizeof(Node));
        q->data = number;
        q->next = NULL;

        //插入新的结点
        q->next = p->next;
        p->next = q;
    }

}

  以上是小菜学习链表的代码了,给大家分享一下!!

  

上一篇:javascript学习笔记全记录


下一篇:一起来写2048(160行python代码)