AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

线性表的链式存储实现【C语言】

2022-09-27 281
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，而线性表的链式存储特点则是用一组任意的存储单元存储线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的。对于链式存储的每个数据元素而言，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息，即直接后继的存储位置。这两部分信息组成了数据元素的存储映像，称为结点。链式存储的结构包含两个域：一个用于存储数据元素的信息，另一个用于存储直接后继的存储位置；存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

线性表链式存储的实现

C语言实现代码

预定义字符

//函数结果状态代码 
#define TRUE     1     //代码中出现TRUE相当于出现了1 
#define FALSE    0     //出现FALSE相当于出现了0 
#define OK       1     //出现OK相当于出现了1 
#define ERROR    0     //出现ERROR相当于出现了0 
#define INFEASIBLE    -1
#define OVERFLOW      -2 

typedef int Status;    //定义函数的返回状态 
typedef int ElemType;

在这里使用了typedef定义了Status和ElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同

1、单链表的构造

typedef struct LNode {
  ElemType data;                    // 结点数据域
  struct LNode *next;            // 结点指针域
}LNode, *LinkList;

2、初始化单链表（带头结点）

  • 生成新结点作为头结点，用头指针L指向头结点
  • 头结点的指针域为空
Status InitList(LinkList &L)
{// 构造一个空的单链表
  L = (LinkList) malloc (sizeof(LNode));
  if(!L) return ERROR;
  L -> next = NULL;
  printf("空的头结点创建成功\n");
  return OK;
}
在该函数传参时一定要在L之前加"&“符号，表示引用传递，保证形参和实参同时改变。
"->"是一个指针类型的运算符，它是用于指向结构体子数据的指针

3、线性表的赋值

Status SetList(LinkList &L, ElemType e)
{
  LinkList p;
  p = L;
  while (p -> next)
  {
    p = p -> next;
  }
  s = (LinkList)malloc(sizeof(LNode));
  s -> data = e;
  s -> next = p -> next;
  p -> next = s;
  return OK;
}

4、判断线性表是否为空

Status ListEmpty(LinkList L)
{
    if(L){
        if(L->next == NULL)        
        printf("线性表是空表\n");
        else
        printf("线性表不是空表\n");
    }
    else{
    printf("线性表不存在，无法判断\n");    
    }
    return OK;
}
在判断线性表是否为空时，首先判断头结点是否存在，当头结点存在时看头结点的指针域是否为空，当指针域为空时说明首元结点不存在，单链表是空表；当指针域不为空时说明存在首元结点，单链表不是空表。

5、线性表的销毁

Status DestroyList(LinkList &L)
{
  if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在\n");
        return ERROR;
    }
    LinkList p = L->next;    //使p指向单链表的首元结点  
    while(p != NULL){     //当p结点不为空时一直进入循环 
        free(L);          //释放L结点 
        L = p;            //将p结点赋值给L结点 
        p = L->next;      //将p结点赋值给L结点以后使p结点指向L的下一个结点 
    } 
    free(L);    //此时p的值为NULL，L指向尾结点，将其释放
    L = NULL;   
    printf("线性表已销毁\n"); 
}

6、线性表的清空

Status ClearList(LinkList &L)
{
  if (!L->next) 
  {
    printf("线性表为空表\n");
    return ERROR;
  }
  LinkList p, q;
  p = L->next;
  while (p)
  {
    q = p -> next;
    free(p);
    p = q;
  }
  L -> next = NULL;
  printf("线性表已清空");
  return OK;
}

7、线性表的表长

Status ListLength(LinkList &L)
{
  LinkList p;
  int i = 0;
  while (p)
  {
    i++;
    p = p -> next;
  }
  return i;
}

8、线性表的取值

Status GetElem(LinkList L,int i)
{// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
     p = L -> next;                                                 // 初始化，p指向首元结点，计数器j初值赋为1
  int j = 1;
  while (p && j < 1) {                                    // 顺链域向后扫描，直到p为空或p指向第i个元素
    p = p -> next;                                            // p指向下一个结点
    ++j;                                                                // 计数器j相应加1    
  }
  if (!p || j > i)
  {
    printf("当前位置没有元素\n");
    return ERROR;                // i值不合法i > n或i <= 0
  }
  printf("第%d个元素的值是：%d\n", i, p -> data);
  return OK;
}

9、单链表的插入

Status ListInsert(LinkList &L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
  p = L; j = 0;
  while (p && (j < i - 1)) {
    p = p -> next;                                                    // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!p || j > i - 1) 
  {
    printf("当前结点无法插入元素\n");
    return ERROR;                // i > n+1 或者 i < 1
  }
  s = new LNode;                                                        // 生成新结点*s
  s -> data = e;                                                        // 将结点*s的数据域置为e
  s -> next = p -> next;                                        // 将结点*s的指针域指向结点ai
  p -> next = s;                                                        // 将结点*p的指针域指向结点*s
  printf("插入元素成功\n");
  return OK;
}

10、单链表的删除

Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中，删除第i个元素
  LinkList p,q;
  p = L; 
  int j = 0;
  while ((p -> next) && (j < i - 1)) {
    p = p > next;                                                // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!(p -> next) || (j > i - 1)) 
  {
    printf("该位置无法删除元素\n");
    return ERROR;        // 当i > n 或 i < 1时删除位置不合理
  }
  q = p -> next;                                                                        // 临时保存被删除结点的地址以备释放
  p -> next = p -> next -> next;                                        // 改变删除结点前驱结点的指针域
  free(p);                                                                                  // 释放删除结点空间
  printf("当前位置元素已删除\n");
  return OK;
}

11、打印线性表

Status PrintList(LinkList L)
{
    if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在，无法打印\n");
        return ERROR;
    }
    LinkList p;
    p = L->next;    //将L的首元结点赋值给p ,为了不将头结点打印出来 
    while(p){
        printf(" %d",p->data);   //将p结点的数据域输出 
        p = p->next;    //结点不断的向后移动 
    }
    printf("\n");
    return OK;
}

代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h> 

//函数结果状态代码 
#define TRUE     1     //代码中出现TRUE相当于出现了1 
#define FALSE    0     //出现FALSE相当于出现了0 
#define OK       1     //出现OK相当于出现了1 
#define ERROR    0     //出现ERROR相当于出现了0 
#define INFEASIBLE    -1
#define OVERFLOW      -2 

typedef int Status;    //定义函数的返回状态 
typedef int ElemType; 

typedef struct LNode {
  ElemType data;                    // 结点数据域
  struct LNode *next;            // 结点指针域
}LNode, *LinkList;

//构造一个空的头结点 
Status InitList(LinkList &L)
{// 构造一个空的单链表
  L = (LinkList) malloc (sizeof(LNode));
  if(!L) return ERROR;
  L -> next = NULL;
  printf("空的头结点创建成功\n");
  return OK;
} 

//对线性表进行赋值 
Status SetList(LinkList &L, ElemType e)
{
  LinkList p;
  p = L;
  while (p -> next)
  {
    p = p -> next;
  }
  s = (LinkList)malloc(sizeof(LNode));
  s -> data = e;
  s -> next = p -> next;
  p -> next = s;
  return OK;
}

//对线性表进行销毁
Status DestroyList(LinkList &L)
{
  if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在\n");
        return ERROR;
    }
    LinkList p = L->next;    //使p指向单链表的首元结点  
    while(p != NULL){     //当p结点不为空时一直进入循环 
        free(L);          //释放L结点 
        L = p;            //将p结点赋值给L结点 
        p = L->next;      //将p结点赋值给L结点以后使p结点指向L的下一个结点 
    } 
    free(L);    //此时p的值为NULL，L指向尾结点，将其释放
    L = NULL;   
    printf("线性表已销毁\n"); 
}

//对线性表进行重置
Status ClearList(LinkList &L)
{
  if (!L->next) 
  {
    printf("线性表为空表\n");
    return ERROR;
  }
  LinkList p, q;
  p = L->next;
  while (p)
  {
    q = p -> next;
    free(p);
    p = q;
  }
  L -> next = NULL;
  printf("线性表已清空");
  return OK;
}
 
//判断线性表是否为空
Status ListEmpty_L(LinkList L)
{
    if(L){
        if(L->next == NULL)        
        printf("线性表是空表\n");
        else
        printf("线性表不是空表\n");
    }
    else{
    printf("线性表不存在，无法判断\n");    
    }
    return OK;
}

//获取线性表的长度
Status ListLength(LinkList &L)
{
  LinkList p;
  int i = 0;
  while (p)
  {
    i++;
    p = p -> next;
  }
  return i;
}

//获取线性表某一位置对应的元素
Status GetElem(LinkList L,int i)
{// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
     p = L -> next;                                                 // 初始化，p指向首元结点，计数器j初值赋为1
  int j = 1;
  while (p && j < 1) {                                    // 顺链域向后扫描，直到p为空或p指向第i个元素
    p = p -> next;                                            // p指向下一个结点
    ++j;                                                                // 计数器j相应加1    
  }
  if (!p || j > i)
  {
    printf("当前位置没有元素\n");
    return ERROR;                // i值不合法i > n或i <= 0
  }
  printf("第%d个元素的值是：%d\n", i, p -> data);
  return OK;
}

//在线性表某一位置插入元素
Status ListInsert(LinkList &L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
  p = L; j = 0;
  while (p && (j < i - 1)) {
    p = p -> next;                                                    // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!p || j > i - 1) 
  {
    printf("当前结点无法插入元素\n");
    return ERROR;                // i > n+1 或者 i < 1
  }
  s = new LNode;                                                        // 生成新结点*s
  s -> data = e;                                                        // 将结点*s的数据域置为e
  s -> next = p -> next;                                        // 将结点*s的指针域指向结点ai
  p -> next = s;                                                        // 将结点*p的指针域指向结点*s
  printf("插入元素成功\n");
  return OK;
}

//删除线性表某一位置的元素
Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中，删除第i个元素
  LinkList p,q;
  p = L; 
  int j = 0;
  while ((p -> next) && (j < i - 1)) {
    p = p > next;                                                // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!(p -> next) || (j > i - 1)) 
  {
    printf("该位置无法删除元素\n");
    return ERROR;        // 当i > n 或 i < 1时删除位置不合理
  }
  q = p -> next;                                                                        // 临时保存被删除结点的地址以备释放
  p -> next = p -> next -> next;                                        // 改变删除结点前驱结点的指针域
  free(p);                                                                                  // 释放删除结点空间
  printf("当前位置元素已删除\n");
  return OK;
}

//打印线性表
Status PrintList(LinkList L)
{
    if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在，无法打印\n");
        return ERROR;
    }
    LinkList p;
    p = L->next;    //将L的首元结点赋值给p ,为了不将头结点打印出来 
    while(p){
        printf(" %d",p->data);   //将p结点的数据域输出 
        p = p->next;    //结点不断的向后移动 
    }
    printf("\n");
    return OK;
}

int main(){
    SetConsoleTitle("java小豪");              //控制windows终端控制台的名称 
    LinkList L = NULL;                                   //声明线性表的头结点，但是并未进行初始化 
    int choose,i,e,n,v,k;
    while(1){
        printf("*****************************************\n");
        printf("*                                       *\n");
        printf("*  线性表的链式表示和实现：             *\n");
        printf("*                                       *\n");
        printf("*    1.  构造一个空的头结点             *\n");
        printf("*    2.  对线性表进行赋值               *\n");
        printf("*    3.  对线性表进行销毁               *\n");
        printf("*    4.  对线性表进行重置               *\n"); 
        printf("*    5.  判断线性表是否为空             *\n");
        printf("*    6.  获取线性表的长度               *\n");
        printf("*    7.  获取线性表某一位置对应的元素   *\n");
        printf("*    8.  在线性表某一位置插入元素       *\n");
        printf("*    9.  删除线性表某一位置的元素       *\n");
        printf("*    12. 打印线性表                     *\n");
        printf("*    13. 退出                           *\n");
        printf("*                                       *\n");
        printf("*****************************************\n");
        printf("请做出您的选择：");
        scanf("%d",&choose);
        switch(choose){
            case 1:InitList(L);break;
            case 2:{
                if(L){      //对线性表赋值的前提是线性表的头结点存在 
                    printf("请输入线性表元素的个数：");
                    scanf("%d",&n);
                    if(n > 0){
                        for(int i = 1;i <= n;i++){
                        printf("请输入第%d个元素的值：",i);
                        scanf("%d",&v);
                        SetList(L,v);
                        }
                    printf("线性表赋值成功\n");
                    }
                    else
                    printf("请输入一个有效数字\n");
                }
                else
                printf("线性表不存在，无法赋值\n"); 
                }
            break;
            case 3:DistoryList(L);break;
            case 4:ClearList(L);break;
            case 5:ListEmpty(L);break;
            case 6:{
                int ans = ListLength(L,1);
                printf("线性表的长度为：%d\n",ans-1);
            };break;
            case 7:{ 
                printf("请输入要获取元素的位置：");
                scanf("%d",&i);
                GetElem(L,i); 
            }
            break;
            case 8:{
                printf("请输入插入元素的位置：");
                scanf("%d",&i);
                printf("请输入插入元素的值：");
                scanf("%d",&e);
                ListInsert(L,i,e);
            }
            break;
            case 9:{
                printf("请输入要删除元素的位置：");
                scanf("%d",&i);
                DeleteList(L,i);
            }
            break;
            
            case 12:PrintList(L);break;
            case 13:exit(0);
        }
    }
    return 0;
}
文章标签：
C语言
存储
关键词：
存储C语言
java小豪
目录
相关文章
半截诗
|
3月前
|
存储 编译器 C语言
【C语言篇】数据在内存中的存储（超详细）
浮点数就采⽤下⾯的规则表⽰，即指数E的真实值加上127（或1023），再将有效数字M去掉整数部分的1。
半截诗
385 0
c的前世今生
|
2月前
|
存储 编译器 C语言
C语言存储类详解
在 C 语言中，存储类定义了变量的生命周期、作用域和可见性。主要包括：`auto`（默认存储类，块级作用域），`register`（建议存储在寄存器中，作用域同 `auto`，不可取地址），`static`（生命周期贯穿整个程序，局部静态变量在函数间保持值，全局静态变量限于本文件），`extern`（声明变量在其他文件中定义，允许跨文件访问）。此外，`typedef` 用于定义新数据类型名称，提升代码可读性。 示例代码展示了不同存储类变量的使用方式，通过两次调用 `function()` 函数，观察静态变量 `b` 的变化。合理选择存储类可以优化程序性能和内存使用。
c的前世今生
160 82
石小浪♪
|
1月前
|
C语言
链式顺序表实现(C语言描述)
本文介绍了如何在C语言中实现链式顺序表，包括数据结构的定义、节点的创建、数据的插入和删除以及链表的打印和销毁。
石小浪♪
39 2
平凡程序猿~
|
1月前
|
存储 C语言
C语言中的浮点数存储：深入探讨
C语言中的浮点数存储：深入探讨
平凡程序猿~
37 1
阿客不是客
|
1月前
|
存储 C语言
深入C语言内存：数据在内存中的存储
深入C语言内存：数据在内存中的存储
阿客不是客
33 0
小徐在进步
|
2月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
414 8
小徐在进步
|
2月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
50 6
小徐在进步
|
2月前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
40 3
小徐在进步
|
2月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
39 1
可能只会写BUG
|
2月前
|
存储 缓存 程序员
c语言的存储类型-存储类
本文详细介绍了C语言中的存储类型及其分类，包括基本类型（如整型、浮点型）和复合类型（如数组、结构体）。重点讲解了不同存储类别（`auto`、`static`、`register`、`extern`、`typedef`、`volatile`、`const`）的特点及应用场景，并展示了C11/C99引入的新关键字（如`_Alignas`、`_Atomic`等）。通过示例代码解释了每个存储类别的具体用法，帮助读者更好地理解和运用这些概念。
可能只会写BUG
48 2