线性结构-链表

简介: 链表定义n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点,每个节点只有一个后继节点首节点没有前驱节点,尾节点没有后继节点专业术语头结点:第一个有效节点为前的节点头节点一般不存放数据加头结点的目的是为了方便链表的操...

链表定义

  1. n个节点离散分配
  2. 彼此通过指针相连
  3. 每个节点只有一个前驱节点,每个节点只有一个后继节点
  4. 首节点没有前驱节点,尾节点没有后继节点

专业术语

  1. 头结点:
    第一个有效节点为前的节点
    头节点一般不存放数据
    加头结点的目的是为了方便链表的操作
  2. 首结点:第一个存放有效数据的节点
  3. 尾结点:最后一个存放有效数据的节点
  4. 头指针:指向头节点的指针变量
  5. 尾指针:指向尾结点的指针变量
img_912c9a46b30bc6338e9abbf5175a7847.png
image.png

链表分类

  • 单链表
img_912c9a46b30bc6338e9abbf5175a7847.png
  • 双链表
img_36aa8f5b45a122eab48c8a3037fb5c72.png
  • 循环链表:尾结点指针域指向头结点
img_ed9297020417ae9e097d56cf879b12c3.png
  • 非循环链表:除了循环链表外,其他都是非循环链表

非循环单链表的实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>
/**
    定义一个链表结构体数据类型
*/
typedef struct Node{
    int data; //数据域
    struct Node * pNext; //指针域
}NODE,*PNODE; //NODE 等价于 struct Node,PNODE 等价于 struct Node *

/**
    函数声明
*/
PNODE create_list(); //初始化一个空链表
void traverse_list(PNODE pHead);  //遍历链表
bool isEmpty(PNODE pHead); //判断链表是否为空
int length_list(PNODE pHead); //计算链表的长度
bool insert_list(PNODE,int,int);  //插入链表
bool delete_list(PNODE,int,int *);  //删除链表
void sort_list(PNODE);  //排序链表

int main()
{
    int elem; //保存删除元素的值
    PNODE pHead=NULL; //等价于 struct Node * pHead
    pHead = create_list(); //创建一个非循环单链表,并把链表的头结点的地址赋给pHead
    //测试链表是否为空
    if(isEmpty(pHead))
        printf("链表为空!!!!!\n");
    //测试 遍历数组
    traverse_list(pHead);

    //测试 计算链表长度
    int leng = length_list(pHead);
    printf("链表的长度是:%d\n",leng);

    //测试 对链表进行排序
    sort_list(pHead);
    traverse_list(pHead);

    //测试 对链表插入元素
    insert_list(pHead,2,88);
    traverse_list(pHead);

    //测试 删除链表中的元素
    if(delete_list(pHead,2,&elem))
        printf("删除成功,你删除的元素是: %d\n ",elem);
    else
        printf("删除失败,找不到需要删除的元素!");
    traverse_list(pHead);
    return 0;
}

/**
    创建一个空链表
*/
PNODE create_list(){
    int length; //链表个数
    int data; //链表结点值

    //生成头结点,并把头结点的地址赋给头指针
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if(pHead==NULL){
        printf("内存分配失败,程序终止!\n");
        exit(-1);
    }

    //定义一个尾指针,初始化时尾指针和头指针指同时指向头结点,并且其指针域为空,因为此时除了头结点外没有其他的结点
    PNODE pTail = pHead;
    pTail->pNext=NULL;
    //确定结点个数
    printf("请输入要生成链表结点的个数,length= ");
    scanf("%d",&length);

    //输入各结点的值
    for(int i=0; i<length; i++){
        printf("请输入第%d个结点的值: ",i+1);
        scanf("%d",&data);

        //生成新结点
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(pNew==NULL){
            printf("内存分配失败,程序终止!\n");
            exit(-1);
        }
        //把输入的值存到结点的数据域上
        pNew->data=data;
        //把新生成的结点挂到链表的最后面,尾插法
        pTail->pNext=pNew;
        pNew->pNext=NULL; //最后一个结点没有后继结点,所以它的指针域为空
        //把尾指针指向最后一个结点
        pTail=pNew;
    }

    return pHead;
}

/**
    遍历链表
*/
void traverse_list(PNODE pHead){
    //一般不对头指针直接操作,而是重新定义一个操作指针p,并且这个p要指向首结点
    PNODE p = pHead->pNext;

    //当链表为空时,结束程序
    if(p==NULL){
        printf("链表为空!\n");
        return;
    }

    //当链表不为空时,输出链表的值
    while(p != NULL){
        printf("%d\t",p->data);
        p=p->pNext;
    }
    printf("\n");

    return;
}

/**
    判断链表是否为空
*/
bool isEmpty(PNODE pHead){
    if(pHead->pNext==NULL)
        return true;
    else
        return false;
}

/**
    计算链表的长度,即结点的个数
*/
int length_list(PNODE pHead){
    PNODE p = pHead->pNext;
    int leng=0; //必须要初始化,如果不初始化,会出现垃圾数字

    while(p != NULL){
        leng++;
        p=p->pNext;
    }
    return leng;
}

/**
    对链表进行排序
    狭义的算法是与数据的存储方式密切相关
    广义的算法是与数据的存储方式无关
    所以,虽然单链表与顺序表的存储方式不同,但是在排序相关操作上基本上是一致的
*/
void sort_list(PNODE pHead){
    int i,j,t;
    int leg=length_list(pHead);
    PNODE p=NULL,q=NULL;
    for(i=0,p=pHead->pNext; i<leg-1; i++,p=p->pNext){
        for(j=i+1,q=p->pNext; j<leg; j++,q=q->pNext){
            if(p->data > q->data){ //类似于数组中的 a[i]>a[j]
                t=p->data;  //类似于数组中的 t=a[i]
                p->data = q->data;  //类似于数组中的 a[i]=a[j]
                q->data=t;  //类似于数组中的 a[j]=t
            }
        }
    }
    return;
}

/**
    在pHead所指向的链表的第pos个节点前插入一个值为element的新结点
    并且pos的值从1开始
*/
bool insert_list(PNODE pHead,int pos,int element){
    int i=0;
    PNODE p=pHead;
    //找到需要插入元素的位置,因为p->pNext可能为空,所以从头结点开始判断
    while(p != NULL && i<pos-1){
        p=p->pNext;
        ++i;
    }

    if(p==NULL || i>pos-1)
        return false;

    //为新结点动态分配内存空间
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew==NULL){
        printf("动态内存分配失败!");
        exit(-1);
    }

    pNew->data = element;

    //把新结点插入元素中,借助第三个指针进行操作
    /*PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;*/

    //把新结点插入元素中,直接操作
    pNew->pNext = p->pNext;
    p->pNext = pNew;

    return true;
}

/**
    删除链表中指定位置的元素
*/
bool delete_list(PNODE pHead,int pos,int * pElement){
    int i=0;
    PNODE p=pHead;
    //找到需要删除的元素,因为是删除元素,所以要从首结点开始判断
    while(NULL != p->pNext && i<pos-1){
        p=p->pNext;
        i++;
    }

    if(p->pNext == NULL || i>pos-1)
        return false;

    //在时行删除之前,把要删除的元素保存下来
    PNODE q=p->pNext;
    *pElement = q->data;

    //执行删除操作
    p->pNext = p->pNext->pNext;
    free(q);
    q=NULL;

    return true;

}

目录
相关文章
|
2月前
|
C++
数据结构01-线性结构-链表栈队列-栈篇
数据结构01-线性结构-链表栈队列-栈篇
|
8天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
13 0
【数据结构OJ题】链表的回文结构
|
23天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
24天前
|
存储
【数据结构】详解链表结构
【数据结构】详解链表结构
9 0
|
2月前
|
算法
【每日一题】牛客网——链表的回文结构
【每日一题】牛客网——链表的回文结构
|
2月前
|
存储 C语言
数据结构基础:双链表结构、实现
数据结构基础:双链表结构、实现
|
2月前
|
存储
【数据结构】【版本1.2】【线性时代】——链表之王(双向带头循环)
【数据结构】【版本1.2】【线性时代】——链表之王(双向带头循环)
|
2月前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
67 0
|
2月前
牛客网:OR36 链表的回文结构
牛客网:OR36 链表的回文结构
16 0
牛客网:OR36 链表的回文结构
|
2月前
|
算法
链表的回文结构
链表的回文结构