线性表---基于严魏敏版数据结构c语言实现---谭浩强版c语言
数据元素在计算机中的存储分为顺序存储和链式存储
顺序存储：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
链式存储：借助指示元素存储地址的指针表示数据元素之间的逻辑关系
ps：谭浩强版c语言涉及8.8内存的动态分配与静态分配
动态分配：数据存储容量不固定（谭浩强：8.8P285 动态分配是需要时随时开辟，不需要时随时释放）
谷歌搜索动态分配的连续存储：（64页）通过程序设计语言提供的动态存储功能，申请一组指定大小的连续空间
静态分配：数据存储容量固定
谷歌搜索静态分配的连续存储：（64页）程序设计语言提供的构造类数据类型---数组（顺序表）
ps：严魏敏版章节区分为顺序表和链表的实现，仅仅有动态分配的顺序存储没有静态分配的顺序存储，但是本人认为代码实现不仅限于顺序表和线性表的实现，更应该严格地区分为四类，动态分配的顺序存储、静态分配的顺序存储、动态分配的链式存储、静态分配的链式存储，且顺序表和链表的划分并不等同于顺序存储和链式存储的划分，所以本篇会介绍基于静态分配和动态分配的顺序存储和链式存储
线性表基于动态分配的顺序存储结构--严魏敏（抄书原文p22）
（实现方法：结构体成员表列用指针和动态开辟数组）https://www.cnblogs.com/Romi/archive/2012/01/07/2315788.html
1.顺序表构造
顺序表构造前进行如下宏定义和变量替换，方便代码的理解：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 |
#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;
|
采用结构体构造一个顺序表，定义顺序表的地址、长度、存储容量的表示，代码如下：
| 1 2 3 4 5 |
typedef struct{
ElemType *elem; //定义了顺序表中元素类型的数组指针，指向顺序表存储空间的基址
int length; //顺序表的长度(也即元素个数)
int listsize; //当前分配给顺序表的存储容量
}SqList;
|
2.顺序表的初始化
接下来对该顺序表进行初始化，为顺序表分配一个预定义大小的数组空间，并将当前顺序表长度设为0，如果元素个数大于分配的存储容量则再对容量进行扩充(初始化时不扩充，顺序表使用中按需要进行容量扩充)。代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 |
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
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#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
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#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");
}
|
