《大话数据结构》之线性表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《大话数据结构》之线性表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8435字，纯文字阅读大概需要13分钟。

内容图文

链表

顺序存储

《大话数据结构》之线性表 - 文章图片

简单来说就是用数组存储数据。

链式存储

这个简单来说就是存储下一个地址，比如《海贼王》中的历史时板，每块板子上的信息都是不足的，如果你想要找到最终的答案，需要从上一块石板开始到下一块石板。

《大话数据结构》之线性表 - 文章图片

或者再举个例子，比如这是个游戏任务，一个游戏任务会被拆分成多个小任务，在每个小任务的部分，会要求你完成该部分的任务，然后再给出你下一条任务的提示。

静态存储

这个回归到最开始的顺序存储，只不过原先的数组中，每个值不仅存储当前的值，还存储下一个值的数组下标。

《大话数据结构》之线性表 - 文章图片

循环链表

这个要说也很简单，就是在在链表末尾元素的指针指向头节点。

《大话数据结构》之线性表 - 文章图片

双向链表

很简单，就是在上面的链式存储的基础之上，再增加一个向前的指针：

《大话数据结构》之线性表 - 文章图片

下面就是一些代码的例子了，因为循环链表和双向链表的本质还是链表，所以下面的例子中没有。

const.php

#define ElementType int
#define ElementPrintType "%d"
#define BR printf("\n")

list.h

#include "const.h"
#include "stdio.h"
#include "stdlib.h"

#define MAX_LIST_LENGTH 100

#define Error 0
#define Success 1

typedef int Return;
/**
 * 顺序存储部分
 */
typedef struct {
    ElementType data[MAX_LIST_LENGTH];
    int length;
} SqlList;
/**
 * 添加元素
 * @param sqlList
 * @param newData
 * @param position
 * @return
 */
Return addElement(SqlList *sqlList,ElementType newData,int position){
    if(position<0 || position>sqlList->length || position>MAX_LIST_LENGTH){
        return Error;
    }
    ElementType lastData=sqlList->data[position],temp;
    for (int i = position; i <MAX_LIST_LENGTH; ++i) {
        temp=sqlList->data[i];
        sqlList->data[i]=lastData;
        lastData=temp;
    }
    sqlList->data[position]=newData;
    sqlList->length++;
    return Success;
}
/**
 * 删除元素
 * @param sqlList
 * @param position
 * @return
 */
Return deleteElement(SqlList *sqlList,int position){
    if(position<0 || position>sqlList->length || position>MAX_LIST_LENGTH){
        return Error;
    }
    for (int i = position; i < MAX_LIST_LENGTH; ++i) {
        sqlList->data[i]=sqlList->data[i+1];
    }
    sqlList->data[sqlList->length]=0;
    sqlList->length--;
    return Success;
}
/**
 * 搜索元素
 * @param sqlList
 * @param search
 * @return
 */
Return searchSqlList(SqlList *sqlList,ElementType search){
    for (int i = 0; i < sqlList->length; ++i) {
        if(sqlList->data[i]==search){
            return Success;
        }
    }
    return Error;
}
/**
 * 辅助函数，打印函数
 * @param sqlList
 */
void PrintfSqlList(SqlList* sqlList){
    printf("the length is %d\n",sqlList->length);
    for (int i = 0; i < sqlList->length; ++i) {
        printf("Position %d's data is ",i);
        printf(ElementPrintType,sqlList->data[i]);
        BR;
    }
}
/**
 * 效果展示
 */
void sqlListIndex(){
    SqlList sqlList={
            .length=0
    };
    addElement(&sqlList,0,0);
    addElement(&sqlList,1,1);
    addElement(&sqlList,1,0);
    PrintfSqlList(&sqlList);
    addElement(&sqlList,3,3);
    PrintfSqlList(&sqlList);
    addElement(&sqlList,2,2);
    PrintfSqlList(&sqlList);
    deleteElement(&sqlList,0);
    PrintfSqlList(&sqlList);
    deleteElement(&sqlList,3);
    PrintfSqlList(&sqlList);
    deleteElement(&sqlList,1);
    PrintfSqlList(&sqlList);
    if(searchSqlList(&sqlList,1)==Success){
        printf("%d in the list\n",1);
    }else{
        printf("%d not in the list\n",1);
    }
}
/**
 * 线性表链式存储结构
 */
typedef struct {
    ElementType value;
    struct Node *next;
} Node;
/**
 * 添加元素
 * @param addPosition
 * @param newNode
 * @return
 */
Return addNode(Node *addPosition,Node *newNode){
    newNode->next=addPosition->next;
    addPosition->next=newNode;
    return Success;
}
/**
 * 删除元素
 * @param indexNode
 * @param removeValue
 * @return
 */
Return deleteNode(Node *indexNode,ElementType removeValue){
    Node *nextNode=indexNode;
    if (indexNode->value==removeValue){
        printf("Can't delete the index value\n");
        exit(0);
    }
    Node *lastNode;
    do {
        lastNode=nextNode;
        nextNode=nextNode->next;
        if (nextNode->value==removeValue){
            lastNode->next=nextNode->next;
            free(nextNode);
            return Success;
        }
    } while (nextNode->next);
    return Error;
}
/**
 * 辅助函数，打印值
 * @param indexNode
 */
void PrintNode(Node *indexNode){
    Node *nextNode=indexNode;
    printf(ElementPrintType,nextNode->value);
    BR;
    do {
        nextNode=nextNode->next;
        printf(ElementPrintType,nextNode->value);
        BR;
    } while (nextNode->next);
}
/**
 * 搜索链表
 * @param indexNode
 * @param searchValue
 * @return
 */
Return searchNode(Node *indexNode,ElementType searchValue){
    Node *nextNode=indexNode;
    if (indexNode->value==searchValue){
        return Success;
    }
    do {
        nextNode=nextNode->next;
        if (nextNode->value==searchValue){
            return Success;
        }
    } while (nextNode->next);
    return Error;
}
/**
 * 效果演示
 */
void nodeIndex(){
    Node indexNode={
            .value=0
    };
    Node *n,*last;
    last=&indexNode;
    for (int i = 1; i <10; ++i) {
        n= malloc(sizeof(Node));
        n->value=i;
        addNode(last,n);
        last=n;
    }
    PrintNode(&indexNode);
    printf("Remove the node\n");
    deleteNode(&indexNode,1);
    PrintNode(&indexNode);
    if (searchNode(&indexNode,1)==Success){
        printf("1 is in the node list\n");
    }else{
        printf("1 is not in the node list\n");
    }
    if (searchNode(&indexNode,8)==Success){
        printf("8 is in the node list\n");
    }else{
        printf("8 is not in the node list\n");
    }
}

/**
* 静态存储
*/

typedef struct {
    ElementType data;
    int cur;
} StaticLinkList;

void emptyStaticLinkList(StaticLinkList staticLinkList[]){
    for (int i = 0; i < MAX_LIST_LENGTH; ++i) {
        staticLinkList[i].cur=0;
    }
}
/**
 * 获取静态列表的最后一个值的下标
 * @param staticLinkList
 * @param position
 * @return
 */
int getStaticLinkListEndIndex(StaticLinkList staticLinkList[],int position){
    if (staticLinkList[position].cur){
        return getStaticLinkListEndIndex(staticLinkList,staticLinkList[position].cur);
    }
    return position;
}
/**
 * 获取静态列表中的一个空位置的值
 * @param staticLinkList
 * @param position
 * @return
 */
int getEmptyStaticLinkListIndex(StaticLinkList staticLinkList[],int position){
    if (position==0){
        position++;
    }
    // 超过设定值
    if (position>MAX_LIST_LENGTH){
        exit(0);
    }
    if (staticLinkList[position].cur){
        return getEmptyStaticLinkListIndex(staticLinkList,position+1);
    }
    return position;
}
/**
 * 添加一个元素
 * @param staticLinkList
 * @param newData
 * @param position
 * @return
 */
Return addStaticLinkList(StaticLinkList staticLinkList[],ElementType newData,int position){
    if (position==0){
        staticLinkList[position].data=newData;
        return Success;
    }
    if (staticLinkList[position].cur){
        // 当前该位置有数据占据该位置
        // 将当前位置的数据拷贝至一个空的数组位置
        int emptyStaticLinkListIndex= getEmptyStaticLinkListIndex(staticLinkList,1);
        staticLinkList[emptyStaticLinkListIndex].data=staticLinkList[position].data;
        staticLinkList[emptyStaticLinkListIndex].cur=staticLinkList[position].cur;
        // 将新的值存储进当前位置中
        staticLinkList[position].data=newData;
        staticLinkList[position].cur=emptyStaticLinkListIndex;
    }else{
        // 搜索静态表的最后一个值
        int staticListLinkEndIndex= getStaticLinkListEndIndex(staticLinkList,0);
        // 将新的值存储进空的数组下标中
        staticLinkList[position].data=newData;
        // 并将静态表的最后一个数组下标指向那里
        staticLinkList[staticListLinkEndIndex].cur=position;
    }
    return Success;
}
/**
 * 删除静态表的值
 * @param staticLinkList
 * @param position
 * @return
 */
Return deleteStaticLinkList(StaticLinkList staticLinkList[],int position){
    // 不允许抹除整个数组
    if (position==0){
        exit(0);
    }
    if (position>MAX_LIST_LENGTH){
        return Error;
    }
    int nextPosition=0;
    // 寻找被删除元素的上级
    while (staticLinkList[nextPosition].cur!=position){
        nextPosition=staticLinkList[nextPosition].cur;
    }
    if (staticLinkList[nextPosition].cur){
        // 将当前被删除的元素的下一个元素交给它的上级
        staticLinkList[nextPosition].cur=staticLinkList[position].cur;
        staticLinkList[position].cur=0;
    }
    // 即使这里没有找到该元素的上级也没有关系，说明当前位置不在数组之中
    return Success;
}
/**
 * 搜索静态表中的一个值
 * @param staticLinkList
 * @param data
 * @return
 */
Return searchStaticLinkList(StaticLinkList staticLinkList[],ElementType data){
    if (staticLinkList[0].data==data){
        return Success;
    }
    int position=0;
    do {
        if (staticLinkList[position].data==data && staticLinkList[position].cur){
            break;
        }
        position=staticLinkList[position].cur;
    } while (staticLinkList[position].cur);
    return staticLinkList[position].data==data?Success:Error;
}
/**
 * 辅助函数，打印输出的
 * @param staticLinkList
 */
void printStaticLinkList(StaticLinkList staticLinkList[]){
    int position=0;
    do {
        printf("Index:%d & data:",position);
        printf(ElementPrintType,staticLinkList[position].data);
        BR;
        position=staticLinkList[position].cur;
    } while (position);
}
/**
 * 演示代码
 */
void staticLinkListIndex(){
    StaticLinkList staticLinkList[MAX_LIST_LENGTH];
    emptyStaticLinkList(staticLinkList);
    addStaticLinkList(staticLinkList,1,0);
    addStaticLinkList(staticLinkList,2,3);
    addStaticLinkList(staticLinkList,3,10);
    printStaticLinkList(staticLinkList);
    printf("Try to delete some indexes\n");
    deleteStaticLinkList(staticLinkList,3);
    printStaticLinkList(staticLinkList);
    if(searchStaticLinkList(staticLinkList,2)==Error){
        printf("2 is not in static link list\n");
    }else{
        printf("2 is in static link list\n");
    }
    if(searchStaticLinkList(staticLinkList,3)==Error){
        printf("3 is not in static link list\n");
    }else{
        printf("3 is in static link list\n");
    }
}

内容总结

以上是互联网集市为您收集整理的《大话数据结构》之线性表全部内容，希望文章能够帮你解决《大话数据结构》之线性表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/998777.html

来源：【匿名】

【上一篇】反射【下一篇】关于IE的RegExp.exec的问题

更多 ►

【《大话数据结构》之线性表】教程文章相关的互联网学习教程文章

邻接矩阵#define MNNum 100//最大顶点数 typedef char VerTexTypre;//顶点的数据类型 typedef int ArcType;//顶点的权值类型 typedef struct {VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum, arcnum;//图的点数和边数 }AMGraph;邻接表#define MVNum 100//最大顶点数 typedef struct ArcNode//边结点{int adjvex;//该边的顶点位置struct ArcNode *nextarc;//指向下一条边的指针otherInfo info;/...

数据结构线性栈【代码】

#ifndef _MY_LINKSTACK_H_ #define _MY_LINKSTACK_H_typedef void LinkStack;//创建链表栈 LinkStack* LinkStack_Create();//销毁链表栈int LinkStack_Destroy(LinkStack** stack);//清空链表栈int LinkStack_Clear(LinkStack* stack);//压栈int LinkStack_Push(LinkStack* stack, void* item);//出栈void* LinkStack_Pop(LinkStack* stack);//获取栈顶元素void* LinkStack_Top(LinkStack* stack);//获取栈的大小int LinkStack_Siz...

数据结构 - 几种常见的排序方法【图】

排序：分类：稳定和不稳定的排序：假设一组排序中有两个相同的数字，排序前后排序后两个数字的先后顺序不变；不稳定的排序则有可能发生改变。内排序和外排序：内排序指的是在内存中排序，外排序则涉及到外部的存储空间排序方法：排序方法又分为很多种有：插入类排序，交换类排序，选择类排序，归并排序，基数排序插入排序又分为：直接插入排序，折半插入排序，2-路插入排序，表插入排序和希尔排序等。直接插入排序：简...

《程序设计与数据结构》第四周学习总结

学号 20172326 《程序设计与数据结构》第四周学习总结教材学习内容总结列表与栈，队列的关系与区别有序列表插入时插入方法无序列表的区别 Comparable方法的重载用链表，数组实现列表教材学习中的问题和解决过程问题1：问题1理解：XXXXXX 问题2：XXXXXX 问题2理解：XXXXXX ... 代码调试中的问题和解决过程问题1：XXXXXX 问题1解决方案：XXXXXX 问题2：XXXXXX 问题2解决方案：XXXXXX ... 代码托管上周考试错题总结错题1及原因，...

20172322 2017-2018-2《程序设计与数据结构》课程总结【图】

20172322 2018-2019-1《程序设计与数据结构》课程总结每周作业链接汇总第一次作业：什么叫高质量软件；学习教材1、2章节。第二次作业：学习教材3、4章节，栈相关知识的学习，利用数组和链实现栈。第三次作业：学习教材第5章，队列相关知识的学习；完成技能调查表。第四次作业：学习教材第6章，列表相关只是的学习，有序列表、无序列表、索引列表等。第五次作业：学习教材第9章，选择与排序相关知识的学习。第六次作业：学习教...

20172313 2018-2019-1 《程序设计与数据结构》第四周学习总结【代码】【图】

20172313 2018-2019-1 《程序设计与数据结构》第四周学习总结教材学习内容总结列表集合有序列表：其元素按照元素的某种内在特性进行排序。（有序列表中的元素具有内在关联，这种关联定义了元素之间的顺序）无序列表：其元素间不具有内在顺序，元素按照它们在列表中的位置进行排序。（无序列表中的元素按使用者所选择的任意方式排序）索引列表：其元素可以用数字索引来引用。（索引列表为它的元素维护一段连续的数字索引值）J...

冷月手撕408之数据结构(2)-数据结构绪论【图】

数据结构绪论不是考纲的重点，但是一定要会求时间复杂度，这是必考的一个点。初试不考复试也会考，所以必须要会求。其他的概念有一个了解。主要的重点冷月做出了标识，主要构架如下图（pdf版或xmind源文件请私聊我：数据结构）。冷月点睛数据结构绪论数据结构定义：在计算机中数据之间的存储关系逻辑结构有线性结构（线性表、栈、队列）,非线性结构(树、图)存储结构顺序存储：逻辑上连续，物理上也连续链式存储：逻辑上连续，物理...

每天3分钟操作系统修炼秘籍（23）：进程表和进程数据结构【代码】【图】

点我查看秘籍连载进程表和进程数据结构内核负责管理维护所有进程，为了管理进程，内核在内核空间维护了一个称为进程表（Process Table）的数据结构，这个数据结构中记录了所有进程，每个进程在数据结构中都称为一个进程表项（Process Table Entry），如图。从图中可知，进程表中除了记录了所有进程的PID，还使用一个字段记录了所有进程的指针，指向每个进程的进程控制块（Process Control Block，PCB），请记住PCB这个词，它太重...

【数据结构从青铜到王者】第七篇:数据结构之堆【代码】【图】

系列文章目录文章目录系列文章目录前言一、堆的概念二、堆的性质三、堆的实现1.用数组定义堆结构struct Heap2.交换两个数Swap函数3.向下调整算法AdjustDown函数4.向上调整算法AdjustUp函数5.初始化堆HeapInit函数6.销毁堆HeapDestory函数7.堆的插入HeapPush函数8.堆的删除HeapPop函数9.取堆顶数据 HeapTop函数10.取堆数据个数 HeapSize函数11.堆判空 HeapEmpty函数12.打印堆HeapPrint函数总结前言一、堆的概念如果有一个关键码的...

【数据结构】双链表【代码】【图】

#include<iostream> #include<cstdlib> using namespace std; typedef struct DuLNode {int data;DuLNode *prior,*next; }; void InitSList(DuLNode *&SL) {//初始化双链表 SL=(DuLNode*)malloc(sizeof(DuLNode));SL->prior=SL->next=NULL; } void createSList(DuLNode *&SL) {//创建双链表 DuLNode *s,*r;r=SL;while(1) {s=( DuLNode*)malloc(sizeof(DuLNode)); cin>>s->data; if(s->data==-1)break;r->next=s;s->prior=r;r=s;...

数据结构-栈【代码】【图】

part 5栈 1 概念 1.1 现象弹夹式手枪、洗盘子摞盘子、浏览器回退功能、word、画图的撤销操作 1.2 特点原理：后进先出（LIFO结构） 1 .3 定义栈：限定在表尾进行插入（尾插法）或删除操作的线性表栈顶（表尾）允许插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。空栈不含任何数据元素的栈。压栈（进栈）：栈的插入出栈：栈的删除 1.4 逻辑示意图 1.5 进栈出栈变化形式最先进栈的只能最后出栈？解析：栈对线...

数据结构链表源码【代码】【图】

数据结构链表源码数据结构链表源码，仅供自己复习专用。#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>typedef struct Node{int data;struct Node *next; }node,*linklist;linklist List;int get(linklist L,int i) {int j=1;linklist p;p=L->next;while (p&&j<i){p=p->next;++j;}if(!p&&j>i)return -1;return (p->data); }int insert(linklist L,int i,int val) {int j=1;linklist p,s;p=L;while...

如何在Django请求之间保持共享数据结构在内存中

我的Django应用程序对性能非常敏感,所有请求都需要访问相同的数据结构.如何以可以访问所有请求的方式存储数据结构？背景：我目前正在使用缓存后端.这有点慢,因为DS很大,每次都必须检索和取消. 我知道HTTP交互应该是无状态的,并且明知需要打破这种约束.没有什么不好的事情应该发生,因为它是只读的吗？解决方法:有几种方法可以解决这个问题： >将数据结构完全移出Python(而不是每次都从存储介质加载).例如,如果您的结构有利于它,您...

ffplay源码分析2-数据结构【代码】

本文为作者原创，转载请注明出处：https://www.cnblogs.com/leisure_chn/p/10301253.html ffplay是FFmpeg工程自带的简单播放器，使用FFmpeg提供的解码器和SDL库进行视频播放。本文基于FFmpeg工程4.1版本进行分析，其中ffplay源码清单如下： https://github.com/FFmpeg/FFmpeg/blob/n4.1/fftools/ffplay.c 在尝试分析源码前，可先阅读如下参考文章作为铺垫： [1]. 雷霄骅，视音频编解码技术零基础学习方法 [2]. 视频编解码基础概念 ...

BUAA_数据结构_5TH_1. 树叶节点遍历（树-基础题）【代码】【图】

BUAA_数据结构_5TH_1. 树叶节点遍历（树-基础题）题目描述：从标准输入中输入一组整数，在输入过程中按照左子结点值小于根结点值、右子结点值大于等于根结点值的方式构造一棵二叉查找树，然后从左至右输出所有树中叶结点的值及高度（根结点的高度为1）。例如，若按照以下顺序输入一组整数：50、38、30、64、58、40、10、73、70、50、60、100、35，则生成下面的二叉查找树：从左到右的叶子结点包括：10、35、40、50、60、70、100，...

首页 / 更多教程 / 《大话数据结构》之线性表

《大话数据结构》之线性表

内容导读

内容图文

链表

顺序存储

链式存储

静态存储

循环链表

双向链表

const.php

list.h

内容总结

内容备注

内容手机端

【《大话数据结构》之线性表】教程文章相关的互联网学习教程文章

数据结构第六章小结【代码】【图】

数据结构线性栈【代码】

数据结构 - 几种常见的排序方法【图】

《程序设计与数据结构》第四周学习总结

20172322 2017-2018-2《程序设计与数据结构》课程总结【图】

20172313 2018-2019-1 《程序设计与数据结构》第四周学习总结【代码】【图】

冷月手撕408之数据结构(2)-数据结构绪论【图】

每天3分钟操作系统修炼秘籍（23）：进程表和进程数据结构【代码】【图】

【数据结构从青铜到王者】第七篇:数据结构之堆【代码】【图】

【数据结构】双链表【代码】【图】

数据结构-栈【代码】【图】

数据结构链表源码【代码】【图】

如何在Django请求之间保持共享数据结构在内存中

ffplay源码分析2-数据结构【代码】

BUAA_数据结构_5TH_1. 树叶节点遍历（树-基础题）【代码】【图】

更多教程 - 最新教程

更多教程 - 最热教程