[数据结构与算法]数据结构——链表

数据结构——链表

对于c语言而言，链表中的元素在内存中不是连续存储的，栈和队列在内存中是连续存储的。
链表中需要有一个头指针。头指针对与链表而言十分重要。可以通过头指针找到链表中的第一个节点。
每一个节点可以分为两个部分，一部分存放节点对应的指针，即指针域，另一部分存放数据，即数据域。
每一个节点的指针域的指针数据指向下一个结点开始的地址。通过这种方式将链表的所有的节点连接起来。最后一个节点的指针域为空NULL。

链表不支持随机访问，链表在内存中并不是连续存在的，而是随机分布的，找到下一个节点的指针就必须找到上一个节点的指针，所以链表的使用必须先找到头指针。
栈和队列支持对元素进行随机访问。
链表可以实现更快的重新排列数据，但是牺牲了随机访问元素的功能。

创建链表

struct node
{
    unsigned char elem;
    struct node *next; 
};

链表的操作;

1. 创建链表

//创建节点
       // 分配节点的内存空间（用到malloc函数）
       //填充数据域
       //填充指针域（暂时未链接，故为NULL）
struct node *head = NULL;

void creat_list(unsigned char elem);
{
   struct node *p =  (struct node *)malloc(sizeof(struct node));
   p->elem = elem;
   p->next = NULL;
}

尾插法建链表：

// 将节点链接
struct node *head = NULL;
struct node *tail = NULL;

void creat_list(unsigned char elem);
{
   struct node *p =  (struct node *)malloc(sizeof(struct node));
   p->elem = elem;
   p->next = NULL;
   
   if(head == NULL)
        head = p;
   else
        tail->next = p;
        
  tail = p;
}

在链表中增加一个节点：
考虑两个问题：①插入链表的位置；②插入链表的值。

void insert_node(int pos,unsigned char elem)
{
        struct node *pre;
        pre = head;
        int i = 0;
        struct node *p =  (struct node *)malloc(sizeof(struct node)); 
        
        if(pos == 0)//插入节点在链表头部；
        {
            p->elem = elem;
            p-。next = head;
            head = p;
        }
        else
        {
            while(i < pos - 1)//找前趋点
            {
                   pre = pre->next;
                   i++;
            }
        
             p->elem = elem;
             p->next = pre->next;
             pre->next = p;
             
             if(p->next == NULL)//在尾节点插入节点
                    tail = p;
        }
}

在链表中删除一个节点：

void  delete_node(int pos)
{
        struct node *pre;
        pre = head;
        int i;
        struct node *p;
        
        if(pos == 0)//删除的头节点
        {
                head = head-next;
                free(pre);
        }
        else
        {
                while(i < pos -1)
               {
                      pre = pre->next;
                      i++;
               }
        
                p = pre->next;
                p->next = p->next;
                if(p->next == NULL)//删除尾节点
                        tail = pre;
                free(p);
        }
}

遍历显示整个链表：

void print_linklist(void)
{
        struct node *p;
        
        for(p = head; p; p = p->next)
        printf("%c", p->elem);
        
        printf("/n");
}

查找链表中的节点：

int search(unsigned char elem)
{
        struct node *p;
        
        for(p = head; p ; p = p->next)
            if(p->elem == elem)
                return 1;
                
        return 0;
}