十二的编程笔记

# 链表与顺序表的比较 顺序表: ・需要预分配一定长度的存储空间。太大易造成存储空间的浪费，太小又将造成频繁地进行存储空间的再分配。 ・顺序表是一种随机存取的结构，对顺序表中任一元素进行存取的时间相同。 ・顺序表对插入、删除操作需要移动近一半的数据元素。 链表: ・存储分配灵活，链表中的结点可在程序执行过程中动态生成。 ・链表是一种顺序存取的结构，对链表中的每个结点都必须从头指针所指结点起顺链扫描。 ・链表对插入、删除操作不需要移动数据元素。

# 双向链表 1. 概念 在双向链表中，每个结点有两个指针域，一个指向后继 结点，另一个指向直接前驱结点。 判空： L->next==Null && L->prior==Null2. 定义 typedef struct DuLNode { DataType data; struct DuLNode *prior; struct DuLNode *next;}DuLNode, *DuLinkList;// 定义头指针： DuLinkList L;// 定义工作指针： DuLNode...

# 顺序表 # 1. 概念 定义：具有相同数据类型的 n (n≥0) 个数据元素组成的有限 序列。是最简单、最常用的数据结构。 ・线性表的顺序表示就是用一组地址连续的存储单 元依次存储线性表的数据元素。 ・线性表的这种机内表示称做线性表的顺序存储结 构或顺序映像。 ・通常，称这种存储结构的线性表为顺序表。 # 2. 定义 // 静态描述typedef struct node{ DataType data[maxsize]; int length;}sqlist;sqlist L;// 动态描述typedef struct...

# 单链表 1. 概念 结点：数据元素及直接后继的存储位置组成一个数据元素的存储结构称为一个结点。 结点包括两个域： 数据域：存储元素本身的信息 指针域：存储直接后继的位置，指针域中存储的信息称作指针或链 单链表：由于链表的每个结点中只包含一个指针域，故又称线性链表或单链表 头指针：头指针指示链表中第一个结点的存储位置。 由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为 “空”(NULL) 链式存储结构特点: 存储空间可以不连续。不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。 头指针 (Head...

# 4. 链队列 1) 定义 typedef struct Node{ QueueElementType data; /* 数据域 */ struct Node *next; /* 指针域 */}LinkQueueNode;typedef struct{ LinkQueueNode * front; LinkQueueNode * rear;}LinkQueue;2) 初始化 int InitQueue(LinkQueue * Q){ /* 将 Q 初始化为一个空的链队列 */ ...

# 3. 循环队列 1) 定义 队空 sq.front==sq.rear队满 sq.front==sq.rear或者: 另外设一个标志存储队中元素个数num==0代表队空，num==MAXSIZE代表队满 少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front2) 基本操作 typedef struct{ datatype data[M] ; int front ; int rear ; int count ; // 记录队中元素个数} cirqueue ;//0) 初始化 q->front=q->rear =...

# 队列 # 1. 概念 队列是只允许在一端删除，另一端插入的线性表，允许删除的一端叫队头 (front), 允许插入的一端叫队尾 (rear)。 特点：先进先出 (FIFO) # 2. 顺序队列 1. 语言描述 #define MAXSIZE 1024 // 最大队列长度typedef struct{datatype data[MAXSIZE]; /* 队员的存储空间 */int rear,front; /* 队头队尾指针 */}SqQueue;2. 具体操作 置空队: sq.front= sq.rear=0入队: sq.data[sq.rear]=x;...

# 链栈 # 1. 概念 链式存储结构：用于收集计算机存储器中所有空闲存储空间，来保存自栈底到栈顶的数据元素。 链栈：链式存储结构栈称为链栈。 # 2. 定义 typedef struct node{ StackElementType data; struct node *next;}LinkStackNode;typedef LinkStackNode *LinkStack;# 3. 操作 1) 进栈 int Push(LinkStack top, StackElementType x)/* 将数据元素 x 压入栈 top 中...

# 顺序栈 # 1. 概念 顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 顺序栈：顺序存储结构的栈称为顺序栈。 # 2. 定义 //1. 顺序栈的静态定义#define MAXSIZE 1024typedef struct{ ElemType data[MAXSIZE]; int top;}SqStack;//2.顺序栈的动态定义 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; # 3....

# 栈的应用 1. 括号匹配的检验 int pipei(){ sqstack s; char c; s.top=0; scanf(“%c”,&c); while(c!=’#’){ switch(c){ case ‘(‘ : push(s,c); scanf(“%c”,&c);break; case ‘{‘ : push(s,c); scanf(“%c”,&c);break; case ‘<‘ : push(s,c);...