线性表的类型定义

[数据结构]常见数据结构的typedef类型定义总结⽬录数据结构类型定义:1.线性表线性表(顺序存储类型描述):#define MaxSize 50 //定义线性表的最⼤长度typedef struct {ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度} SqList; //顺序表的类型定义线性表(动态存储类型描述)#define InitSize 100 //表长度的初始定义typedef struct {ElemType *data; //指⽰动态分配数组的指针int MaxSize,length; //数组的最⼤容量和当前个数} SeqList; //动态分配数组顺序表的类型定义L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);//初始内存分配2.线性表的链式表⽰单链表的结点类型描述:typedef struct LNode{ //定义单链表结点类型ElemType data; //数据域struct LNode *next; //指针域}LNode,*LinkList;双链表的结点类型描述:typedef struct DNode{ //定义双链表结点类型ElemType data; //数据域struct DNode *prior,*next; //前驱和后继指针}DNode,*DLinkList;静态链表结点类型的描述:#define MaxSize 50 //静态链表的最⼤长度typedef struct { //静态链表结构类型的定义ElemTypen data; //存储数据元素int next; //下⼀个元素的数组下标} SLinkList[MaxSize];3.栈的数据结构顺序栈的数据结构描述#define MaxSize 50typedef struct { //定义栈中元素的最⼤个数ElemType data[MaxSize];//存放栈中元素int top; //栈顶指针} SqStack;链栈的数据结构描述typedef struct Linknode{ElemType data; //数据域struct Linknode *next; //指针域} *LiStack; //栈类型定义4.队列队列的顺序存储类型描述：#define MaxSize 50　//定义队列中元素的最⼤个数typedef struct{ElemType data[MaxSize]//存放队列元素int front,rear;//队头指针和队尾指针} SeQueue;队列的链式存储typedef struct { //链式队列结点ElemType data;struct LinkNode *next;} LinkNode;typedef struct{ //链式队列LinkNode *front, *rear;//队列的队头和队尾指针} LinkQueue;5.⼆叉树⼆叉树的链式存储描述[lchild][data][rchild]typedef struct BiTNode{ElemType data; //数据域struct BiTNode *lchild,*rchild; //左，右指针} BiTNode,*BiTree;线索⼆叉树的存储结构描述：typedef struct ThreadNode{ElemType data; //数据元素struct ThreadNode *lchild,*rchild; //左右孩⼦指针int ltag,rtag; //左右线索标志} ThreadNode,*ThreadTree;6.树,森林双亲表⽰法的存储结构描述如下：#define MAX_TREE_SIZE 100 //树中最多结点数typedef struct{ //树的结点定义ElemType data; //数据元素int parent; //双亲位置域} PTNode;typedef struct { //树的类型定义PTNode nodes[MAX_TREE_SIZE]； //双亲定义int n; //结点数} PTree;孩⼦兄弟表⽰法的存储结构描述如下：typedef struct CSNode {ElemType data; //数据域struct CSNode *firstchild,*nextsibling;//第⼀个孩⼦和右兄弟指针} CSNode,*CSTree;7.图图的邻接矩阵存储结构定义如下#define MaxVertexNum 100 //顶点数⽬的最⼤值typedef char VertexType; //顶点的数据类型typedef int EdgeType; //带权图中边上权值的数据类型typedef struct {vertexType Vex[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]；//邻接矩阵,边表 int vexnum,arcnum; //图的当前顶点数和弧数} MGraph;图的邻接表存储结构定义如下：＃define MaxVertexNum 100 //图中顶点数⽬的最⼤值typedef struct ArcNode{ //边表结点int adjvex; //该弧所指向的顶点的位置struct ArcNode *next; //指向下⼀条弧的指针//InfoType info; //⽹的边权值} ArcNode;typedef struct VNode{ //顶点表结点VectexType data; //顶点信息ArcNode *first; //指向第⼀条依附该顶点的弧的指针} VNode,AdjList[MaxVertexNum];typedef struct { //邻接表AdjList vertices; //图的顶点数和弧数int vexnum,arcnum; //ALGraph是以邻接表存储的图类型} ALGraph;图的⼗字链表存储结构定义如下：#define MaxVertexNum 100 //图中顶点数⽬的最⼤值typedef struct ArcNode{ //边表结点int tailvex, headvex; //该弧的头尾结点struct ArcNode *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点 //InfoType info; //相关信息指针}typedef struct VNode{ //顶点表结点VertexType data; //顶点信息ArcNode *firstin, *firstout; //指向第⼀条⼊弧和出弧} VNode;typedef struct {VNode xlist[MaxVertexNum]; //邻接表int vexnum,arcnum; //图的顶点数和弧数} GLGraph; //GLGraph是以⼗字邻接存储的图类型图的邻接多重表存储结构定义如下：＃define MaxVertexNum 100 //图中顶点数⽬的最⼤值typedef struct ArcNode{ //边表结点bool mark; //访问标记int ivex,jvex; //分别指向该弧的两个结点struct ArcNode *ilink,*jlink; //分别指向该弧的两个顶点的下⼀条边 //InfoType info; //相关信息指针}typedef struct VNode{ //顶点表结点VertexType data; //顶点信息ArcNode *firstedge; //指向第⼀条依附该顶点的边} VNode;typedef struct{VNode adjmulist[MaxVertexNum]; //邻接表int vexnum,arcnum; //图的顶点数和弧数} AMLGraph; //AMLGraph是以邻接多重表存储的图类型。

线性表知识点总结定义：线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。

其中n为表长。

当n=0时 线性表是⼀个空表特点：线性表中第⼀个元素称为表头元素；最后⼀个元素称为表尾元素。

除第⼀个元素外，每个元素有且仅有⼀个直接前驱。

线性表的顺序存储⼜称为顺序表。

它是⽤⼀组地址连续的存储单元（⽐如C语⾔⾥⾯的数组），依次存储线性表中的数据元素，从⽽使得逻辑上相邻的两个元素在物理位置上也相邻。

建⽴顺序表的三个属性:1.存储空间的起始位置（数组名data）2.顺序表最⼤存储容量（MaxSize）3.顺序表当前的长度（length）其实数组还可以动态分配空间，存储数组的空间是在程序执⾏过程中通过动态存储分配语句分配总结：1.顺序表最主要的特点是随机访问（C语⾔中基于数组），即通过⾸地址和元素序号可以在O(1)的时间内找到指定的元素。

2.顺序表的存储密度⾼，每个结点只存储数据元素。

⽆需给表中元素花费空间建⽴它们之间的逻辑关系（因为物理位置相邻特性决定）1.插⼊算法思路：1.判断i的值是否正确1 2 3 4 5 6#define Maxsize 50 //定义线性表的最⼤长度typedef int Elemtype // 假定表中的元素类型是整型typedef struct{Elemtype data [maxsize]; // 顺序表中的元素int lengh; // 顺序表的类型定义}Sqlist;1234567891011121314 typedef int Elemtype // 假定表中的元素类型是整型typedef struct{Elemtype *data; // 指⽰动态分配数组的指针int Maxsize,lengh; // 数组的最⼤容量和当前个数}Sqlist;//C语⾔的动态分配语句为#define InitSize 100SeqList L;L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);/*注意:动态分配并不是链式存储，同样还属于顺序存储结构，只是分配的空间⼤⼩可以在运⾏时决定*/2.判断表长是否超过数组长度3.从后向前到第i个位置，分别将这些元素都向后移动⼀位4.将该元素插⼊位置i 并修改表长代码分析：最好情况：在表尾插⼊（即i=n+1），元素后移语句将不执⾏，时间复杂度为O(1)。

824-计算机基础考试大纲计算机基础包括数据结构、计算机网络两部分内容，每部分内容各占1/2。

I 数据结构课程基本要求：数据结构是在计算机科学中是一门综合性的专业基础课。

课程主要内容包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、内排序、文件管理和外排序等。

考试的具体要求包括：1. 全面系统地掌握队列、堆、栈、树、图等基本数据结构，深刻理解和熟练掌握课程中的典型算法；2. 提高对各种数据结构与算法的程序设计能力，提高对数据结构与算法的实际运用能力。

考试内容：1. 线性表1.1. 线性表的类型定义1.2. 线性表的顺序表示与实现1.3. 线性表的链式表示与实现2. 栈和队列2.1. 栈的定义与实现2.2. 栈与递归的实现2.3. 队列的定义与实现3. 串3.1. 串的定义与实现3.2. 串的模式匹配算法4. 数组和广义表4.1. 数组的定义与实现4.2. 矩阵的压缩存储4.3. 广义表的定义与实现4.4. 广义表的递归算法5. 树和二叉树5.1. 树的定义和基本术语5.2. 二叉树的定义、性质和存储结构5.3. 遍历二叉树和线索二叉树5.4. 树和森林5.5. 赫夫曼树及其应用5.6. 回溯法与树的遍历6. 图6.1. 图的定义和术语6.2. 图的存储结构6.3. 图的遍历6.4. 最短路径7. 动态存储管理7.1. 边界标识法7.2. 伙伴系统7.3. 存储紧缩8. 查找8.1. 静态查找表8.2. 动态查找表8.3. 哈希表9. 内部排序9.1. 内部排序算法，插入排序、快速排序、选择排序、归并排序和基数排序等9.2. 内部排序算法的比较10. 外部排序10.1. 外存信息的存取10.2. 多路平衡归并的实现10.3. 选择排序10.4. 最佳归并树11. 文件11.1. 有关文件的基本概念11.2. 顺序文件与索引文件11.3. 直接存取文件（散列文件）11.4. 多关键字文件参考书目：1.《数据结构（C语言版）》作者：严蔚敏，吴伟民出版社：清华大学出版社ISBN：97873020236852.《数据结构与算法》作者：张铭，王腾蛟，赵海燕出版社：高等教育出版社ISBN：9787040239614II 计算机网络课程基本要求1.掌握计算机网络的基本概念、基本原理和基本方法。