当前位置：首页 > article >正文

数据结构----链表

article 2024/9/21 20:23:04

1.数据结构基本概念

数据结构：是一组用来保存一种或者多种特定关系的数据的集合，其核心在于如何组织和存储数据。

1.1数据结构的分类

集合：其中的元素之间关系平等，没有明显的层级或关系链。

图形结构：元素之间形成多对多的关系，形成网状结构，非常适合表示复杂的关系网络。

树型结构：元素之间具有一对多的关系，最典型的例子是二叉树，它有效地表达了层级和分支的关系。

线性结构：元素之间仅存在一对一的关系，线性表（如数组、链表）、队列、栈等都是线性

结构的实现。这些结构的特点是数据项之间有序排列。

顺序存储：使用一段连续的内存空间来保存元素。其优点是空间连续，访问方便；但缺点是

插入和删除操作需要移动大量元素，且需要预分配内存空间，易造成存储空间碎片。

链式存储：与顺序存储不同，链式存储采用一组非连续的内存空间来保存元素。每个元素

（或称为节点）除了存储数据外，还包含指向下一个元素的指针（单向链表）或指向前后元素的指

针（双向链表）。优点是插入和删除数据方便，不需要预分配内存；缺点是访问元素效率较低。

其他存储方式

索引存储：通过关键字构建索引表，快速找到数据的存储位置，提高了数据检索的效率。

散列存储（哈希存储）：将数据元素的存储位置与其关键码之间建立确定的对应关系，实现了快速查找的存储方式。

1.2 示例

link.h


#ifndef __LINK_h__
#define __LINK_h__

typedef int DataType;//链表存储数据类型；

typedef struct node//链表结点类型；
{
    DataType date;               //  数据域；
    struct node *pnext;          //  指针域；
}Link_node_t;

typedef struct Link         //链表对象类型；
{
    Link_node_t *phead;     //链表头结点地址；
    int clen;               //链表当前结点数；
}Link_t;



extern Link_t *create_link();//链表创建；
extern int push_link_head(Link_t *plink,DataType data);
extern void printf_link(Link_t *plink);
extern int push_link_tail(Link_t *plink,DataType data);
extern int pop_link_head(Link_t *plink);
extern int pop_link_tail(Link_t *plink);

extern Link_node_t *find_link_data(Link_t *plink, DataType data);
extern int change_link_data(Link_t*plink,DataType data,DataType new_data);
extern int pop_link_all(Link_t * plink);
extern Link_node_t *find_link_end_k_node(Link_t *plink,int k);
extern Link_node_t *find_mid_link_node(Link_t *plink);
extern int delete_link(Link_t *plink , DataType n);

#endif

link.c

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


Link_t *create_link()
{
    Link_t *plink = (Link_t *)malloc(sizeof(Link_t));
    if(NULL == plink)
    {
        perror("fail malloc");
        return NULL;
    }
    plink->phead = NULL;
    plink->clen = 0;
    return plink;
}
int push_link_head(Link_t *plink,DataType data)
{
    Link_node_t *pnode = (Link_node_t *)malloc(sizeof(Link_node_t));
    if(NULL == pnode )
    {
        perror("fail malloc");
    }
    pnode->date = data;
    pnode->pnext = NULL;
    pnode->pnext= plink->phead;
    plink->phead= pnode;
    plink->clen +=1;
}
void printf_link(Link_t *plink)
{
    Link_node_t *p = plink->phead;
    while(p!= NULL)
    {
        printf("%d  ",p->date);
        p=p->pnext;
    }
    printf("clen = %d\n",plink->clen);
}
int push_link_tail(Link_t *plink,DataType data)
{
    Link_node_t *pnode = (Link_node_t *)malloc(sizeof(Link_node_t));
    if(NULL == pnode )
    {
        perror("fail malloc");
    }
    pnode->date = data;
    pnode->pnext = NULL;
    if(plink->phead == NULL)
    {
        push_link_head(plink,data);
    }
    else
    {
        Link_node_t *p = plink->phead;
        while(p->pnext != NULL)
        {
            p=p->pnext;
        }
        p->pnext=pnode;
        plink->clen+=1;

    }
    return 0;
}
int pop_link_head(Link_t *plink)
{
    Link_node_t *p = plink->phead;
    if(NULL == plink->phead)
    {
        return 0;
    }
    plink->phead= p->pnext;
    free(p);
    plink->clen -=1;

    return 0;
}
int pop_link_tail(Link_t *plink)
{  
    Link_node_t *p = plink->phead;
    
    if(NULL == plink->phead)
    {
        return 0;
    }
    else if(plink->clen==1)
    {
        pop_link_head(plink);   
    }
    else
    {
        while(p->pnext->pnext !=NULL)
        {
            p=p->pnext;
        }
        free(p->pnext);
        p->pnext = NULL;
        plink->clen -=1;
    }
    return 0;
}

Link_node_t *find_link_data(Link_t *plink, DataType data)
{
    Link_node_t *p = plink->phead;
    if(plink->clen ==0)
    {
        return NULL;
    }
    else
    {
        while(p!= NULL)
        {
            if(p->date == data)
            {
                printf("find\n");
                return p;
            }
            p=p->pnext;

        }
        printf("no find\n");
        return NULL;
    }
}

int change_link_data(Link_t *plink,DataType data,DataType new_data)
{
    Link_node_t *p =find_link_data(plink,data);
    if(p==NULL)
    {
        return -1;
    }
    p->date =new_data;
    return 0;
}

int pop_link_all(Link_t * plink)
{
    for(int i =0;i<plink->clen;++i)
    {
        pop_link_head(plink);
    }
    free(plink);
    return 0;
}

Link_node_t *find_mid_link_node(Link_t *plink)
{
    Link_node_t *p = plink->phead;
    if(plink->clen ==0)
    {
        return NULL;
    }
    for(int i = 0 ; i < plink->clen / 2; ++i)
    {
        p = p->pnext;
    }
    printf("mid=%d\n",p->date);
    return p;
}
Link_node_t *find_link_end_k_node(Link_t *plink,int k)
{
    Link_node_t *p = plink->phead;
    if(plink->clen ==0)
    {
        return NULL;
    }
    int a = plink->clen-k;
    if(a<0)
    {
        return NULL;
    }
    else
    {
        for(int i = 0 ; i < a; ++i)
        {
            p = p->pnext;
        }       
        printf("k=%d\n",p->date);
        return p;
    }
}
int delete_link(Link_t *plink , DataType n)
{
    if(plink->clen == 0)
    {
        return 0;
    }
    else if(plink->clen == 1)
    {
        pop_link_head(plink);
        return 1;
    }
    Link_node_t *p = plink->phead;
    Link_node_t *q = plink->phead;
    int i = 0;
    for(i = 0 ; i < n - 1 ; ++i)
    {
        p = p->pnext;
    }
    for(i = 0 ; i < n - 2 ; ++i)
    {
        q = q->pnext;
    }
    q->pnext = p->pnext;
    free(p);
    plink->clen--;
    return 1;
}

查看全文

http://www.kler.cn/news/294341.html