小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

数据结构---线性表的静态/动态分配与顺序/链式存储_从空间,时间,操作等层面比较线性表静态存储和动态

作者：小丑西瓜9 | 2024-02-29 23:35:01

踩

从空间,时间,操作等层面比较线性表静态存储和动态

线性表---基于严魏敏版数据结构c语言实现---谭浩强版c语言

数据元素在计算机中的存储分为顺序存储和链式存储

顺序存储：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系

链式存储：借助指示元素存储地址的指针表示数据元素之间的逻辑关系

ps：谭浩强版c语言涉及8.8内存的动态分配与静态分配

动态分配：数据存储容量不固定（谭浩强：8.8P285 动态分配是需要时随时开辟，不需要时随时释放）

谷歌搜索动态分配的连续存储：（64页）通过程序设计语言提供的动态存储功能，申请一组指定大小的连续空间

静态分配：数据存储容量固定

谷歌搜索静态分配的连续存储：（64页）程序设计语言提供的构造类数据类型---数组（顺序表）

ps：严魏敏版章节区分为顺序表和链表的实现，仅仅有动态分配的顺序存储没有静态分配的顺序存储，但是本人认为代码实现不仅限于顺序表和线性表的实现，更应该严格地区分为四类，动态分配的顺序存储、静态分配的顺序存储、动态分配的链式存储、静态分配的链式存储，且顺序表和链表的划分并不等同于顺序存储和链式存储的划分，所以本篇会介绍基于静态分配和动态分配的顺序存储和链式存储

线性表基于动态分配的顺序存储结构--严魏敏（抄书原文p22）

（实现方法：结构体成员表列用指针和动态开辟数组）https://www.cnblogs.com/Romi/archive/2012/01/07/2315788.html

1.顺序表构造

顺序表构造前进行如下宏定义和变量替换，方便代码的理解：

#define TRUE 1

#define FALSE 0

#define OK 1

#define ok 1

#define ERROR 0

#define error 0

#define INFEASIBLE -1

#define LIST_INIT_SIZE 100;

#define LISTINCREMENT 10;

typedef int ElemType;

typedef int Status;

采用结构体构造一个顺序表，定义顺序表的地址、长度、存储容量的表示，代码如下：

typedef struct{

ElemType *elem; //定义了顺序表中元素类型的数组指针，指向顺序表存储空间的基址

int length; //顺序表的长度(也即元素个数)

int listsize; //当前分配给顺序表的存储容量

}SqList;

2.顺序表的初始化

接下来对该顺序表进行初始化，为顺序表分配一个预定义大小的数组空间，并将当前顺序表长度设为0，如果元素个数大于分配的存储容量则再对容量进行扩充(初始化时不扩充，顺序表使用中按需要进行容量扩充)。代码如下：

Status InitList(SqList *L)

{

(*L).elem=(ElemType*)malloc(100*sizeof(ElemType));

//不知什么问题不能用LIST_INIT_SIZE，必须用100，下面的realloc函数也是一样？

if((*L).elem==NULL)

{

exit(OVERFLOW);

}

(*L).length=0;

(*L).listsize=LIST_INIT_SIZE;

return ok;

}

线性表基于静态分配的顺序存储结构--

（实现方法1：结构体成员表列用静态数组）仅作参考https://www.cnblogs.com/newwy/archive/2010/10/10/1847449.html

https://blog.csdn.net/zwj1452267376/article/details/85011271

静态分配内存：

const int Maxsize = 100;//定义表格的最大长度
//ElemType表示存储元素的类型
typedef struct{
ElemType data[MaxSize];//顺序表中的元素
int length;//顺序表的当前长度
}Sqlist;

（实现方法2：严魏敏（静态链表实现抄书原文p31）争议处理：https://ask.csdn.net/questions/274643?ops_request_misc=%7B%22request_id%22%3A%22158195017719725256734898%22%2C%22scm%22%3A%2220140713.130063897..%22%7D&request_id=158195017719725256734898&biz_id=4&utm_source=distribute.pc_search_result.none-task

StaticLinkList.h

#ifndef _STATIC_LINK_LIST_H_
#define _STATIC_LINK_LIST_H_
#define MAXSIZE 100

typedef enum {ERROR,OK}Status;

typedef struct{
int cur;
int data;
}StaticLinkList[MAXSIZE];

线性表基于动态分配的链式存储结构--严魏敏（抄书原文p28）

（实现方法1：定义结构体成员为指针）

//-----线性表的单链表存储结构-----
typedef struct LNode { //自定义数据类型
ElemType data ; //数据域
struct LNode *next ; //指针域
} LNode, *LinkList ;

（实现方法2：定义结构体成员为指针）https://www.cnblogs.com/choon/p/3915706.html

#define _CRT_SECURE_NO_DEPRECATE

#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1

#include <stdio.h>

#include <stdlib.h>

/*所谓动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。*/

struct Student

{

int No;//学号

struct Student *next;

};

int main()

{

struct Student *p1, *p2, *head;

int n = 0; //结点个数

head = NULL;

p1 = (struct Student *)malloc(sizeof(struct Student));

printf("请输入1个学号\n");

scanf("%d", &p1->No);

p2 = p1; //开始时，p1和p2均指向第1个结点

while (p1->No != 0)

{

n++;

if (n == 1)

{

head = p1;

}

else

{

p2->next = p1;

}

p2 = p1;//p2是最后一个结点

printf("请输入学号，输入0终止：\n");

p1 = (struct Student *)malloc(sizeof(struct Student));

scanf("%d", &p1->No);

};

p2->next = NULL;//输入完毕后，p2->next为NULL

//遍历动态链表

struct Student *p;

p = head;

while (p != NULL)

{

printf("%d,", p->No);

p = p -> next;

}

printf("\n");

system("pause");

}

线性表基于静态分配的链式存储结构--谭浩强（p310）

（实现方法：结构体成员为指针）

https://www.cnblogs.com/choon/p/3915706.html

#define _CRT_SECURE_NO_DEPRECATE

#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1

#include <stdio.h>

#include <stdlib.h>

/*所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。*/

struct Student

{

int num;

float score;

struct Student *next;

};

int main()

{

struct Student stu1, stu2, stu3, *head, *p;

stu1.num = 1001; stu1.score = 80; //对结点stu1的num和score成员赋值

stu2.num = 1002; stu2.score = 85; //对结点stu2的num和score成员赋值

stu3.num = 1003; stu3.score = 90; //对结点stu3的num和score成员赋值

head = &stu1; //头指针指向第1个结点stu1

stu1.next = &stu2; //将结点stu2的地址赋值给stu1结点的next成员

stu2.next = &stu3; //将结点stu3的地址赋值给stu2结点的next成员

stu3.next = NULL; //stu3是最后一个结点，其next成员不存放任何结点的地址，置为NULL

p = head; //使p指针也指向第1个结点

//遍历静态链表

do{

printf("%d,%f\n", p->num, p->score); //输出p所指向结点的数据

p = p->next; //然后让p指向下一个结点

} while (p != NULL); //直到p的next成员为NULL，即完成遍历

system("pause");

}

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/169307