数据结构（1）

1.定义
     一组用来保存一种或者多种特定关系的数据的集合（组织和存储数据）

     程序的设计：将现实中大量而复杂的问题以特定的数据类型和特定的存储结构存储在内存中， 并在此基础上实现某个特定的功能的操作；
程序 = 数据结构 + 算法

 2.数据与数据之间的关系 
  数据的逻辑结构：数据元素与元素之间的关系
           集合：关系平等
           线性结构：元素之间一对一的关系（表（数组，链表），队列。栈。。。）
           树型结构：元素之间一对多的关系（二叉树）
           图形结构：元素之间多对多的关系（网状结构）
    数据的物理结构：数据的逻辑结构在计算机内存中的存储形式
           顺序存储：采用一段连续的内存空间保存元素
                    优点：空间连续，访问方便
                    缺点：插入删除需要移动大量的元素
                          需要预分配内存空间
                          容易造成存储空间碎片
            链式存储：采用一组非连续的内存空间保存元素
                    缺点：访问元素效率低
                    优点：插入和删除数据方便
                          不需要预分配内存
            索引存储：通过关键字构建索引表，通过索引表来来找到数据的存储位置
            散列存储（哈希存储）：将数据元素的存储位置与关键码之间建立确定对
                     应关系从而实现查找的存储方式

3.链式存储

    1.单向链表 

    1.链表的创建和插入

#include<stdio.h>
#include"link.h"
#include<head.h>
Link_Attribute_t *create_link()
{
    Link_Attribute_t *plink = malloc(sizeof(Link_Attribute_t));
    if(NULL == plink)
    {
        perror("malloc fail");
        return NULL;
    }
    plink->phead = NULL;
    plink->clen = 0;
    return plink;
}
int push_link_head(Link_Attribute_t *plink,TYDEDATA data)
{
    link_node_t *pnode = malloc(sizeof(link_node_t));
    if(NULL == pnode)
    {
        perror("malloc fail");
        return -1;
    }
    pnode->data = data;
    pnode->pnext = NULL;
    pnode->pnext = plink->phead;
    plink->phead = pnode;
    plink->clen++;
    return 0;
}

链表的删除

int remove_link_head(Link_Attribute_t *plink)
{
    if(is_empty_link(plink))
    {
        return 0;
    }
    else
    {
        link_node_t *p = plink->phead;
        plink->phead = p->pnext;
        free(p);
        plink->clen--;
        return 0;
    }
}
int remove_link_back(Link_Attribute_t *plink)
{
    link_node_t *p = plink->phead;
    if(is_empty_link(plink))
    {
        return 0;
    }
    else
    {
        if(NULL == p->pnext)
        {
            remove_link_head(plink);
        }
        else
        {
            while(p->pnext->pnext != NULL)
            {
                p = p->pnext;
            }
            free(p->pnext);
            p->pnext = NULL;
            plink->clen--;
            return 0;
        }
    }
}

链表的查找、修改和销毁

link_node_t *find_link_data(Link_Attribute_t *plink,TYDEDATA data)
{
    link_node_t *p = plink->phead;
    if(p->data == data)
    {
        return plink->phead;
    }
    else
    {
        while(p->pnext->data != data)
        {
            p = p->pnext;
        }
        return p->pnext;
    }
}
int change_link_data(Link_Attribute_t *plink,TYDEDATA data,TYDEDATA newdata)
{
    link_node_t *p = plink->phead;
    while(p->data != data)
    {
        p = p->pnext;
    }
    p->data = newdata;
    return 0;
}
int destroy_link(Link_Attribute_t *plink)
{
    while(plink->clen != 0)
    {
        //remove_link_back(plink);
        remove_link_head(plink);
    }
    printf("clen = %d\n",plink->clen);
    free(plink);
    return 0;
}

链表的排序

void insert_sort_link(Link_Attribute_t *plink)
{
    link_node_t *ptmp = plink->phead->pnext;
    link_node_t *pinsert = ptmp;
    plink->phead->pnext = NULL;
    while(pinsert != NULL)
    {
        link_node_t *p = plink->phead;
        //ptmp = ptmp->pnext;
        if(pinsert->data < plink->phead->data)
        {
            ptmp = ptmp->pnext;
            pinsert->pnext = plink->phead;
            plink->phead = pinsert;
            pinsert = ptmp;
            continue;
        }
        else
        {
            while(p->pnext != NULL && p->pnext->data < pinsert->data)
            {
                p = p->pnext;
            }
            ptmp = ptmp->pnext;
            pinsert->pnext = p->pnext;
            p->pnext = pinsert;
            pinsert = ptmp;
        }
    }
}