第2章
2.1 线性表定义
- 定义：一个线性表是n个数据元素的有限序列。一个数据元素可以由若干个数据项组成。通常把数据元素称为记录，含有大量记录的线性表又称文件。
2.2 线性表的顺序表示和实现
- 定义：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
- 高级语言一般称为数组。
- 数据元素逻辑相邻，物理地址也相邻
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct {
ElemType *elem; //存储空间基址
int length; //线性表当前存储数据元素的长度
int listsize; //线性表当前分配的存储容量（以sizeof(ElemType)为单位）
}
2.3 线性表的链式表示和实现
2.3.1 线性链表
- 存储结构特点：用一组任意的存储单元存储线性表的数据元素。
- 数据元素逻辑上连续，物理地址不一定连续。
- 每个数据元素称为结点
- 节点包括两个域：存储数据的数据域；存储直接后继存储位置的指针域。
- n个节点链接成一个链表，即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
- 头节点：在单链表的第一个结点之前设置一个结点，称为头节点。
线性表的单链表存储结构（带头节点）：
typedef struct LNode{ //结点类型定义
ElemType data; //数据域
struct LNode *next; //指针域
} *Link;
typedef struct { //头结点的定义
Link head,tail; //分别指向线性链表中的头结点和最后一个结点
int len; //表示线性链表中数据元素的个数
}
- 静态链表：借用一维数组来描述线性链表
定义：
#define MAXSIZE 1000 //链表的最大长度
typedef struct {
ElemType data; //数据域
int cur; //模拟指针，实际上是后继元素的数组下标。
}
image.png
2.3.2 循环链表
循环链表：最后一个结点的指针域指向头结点，整个链表形成一个环。
2.3.3 双向链表
双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前驱。
typedef struct DuLNode {
ElemType data; //数据域
struct DuLNode *prior; //前驱的地址
struct DuLNode *next; //后继的地址
}
第3章 栈和队列
3.1 栈
3.1.1 栈的定义
栈：是限定仅在表尾进行插入和删除操作的线性表，因此，表尾段称为栈顶，表头端称为栈底。
LIFO：last in first out，后进先出。
3.1.2 栈的表示和实现
- 顺序栈：数组
#define LIST_INIT_SIZE 100 //存储空间的初始分配量
#define LISTINCREMENT 10 //存储空间的分配增量
typedef struct {
SElemType *base; //栈底指针，在构造前和销毁后，base=NULL
SElemType *top; //栈顶指针
int stacksize; //当前分配的存储容量（以sizeof(SElemType)为单位）
}SqStack;
微信图片_20211226152312.jpg
若base=NULL表示栈不存在，top==base可以作为栈空的标记。每当插入新的栈顶元素时，指针top+1，删除栈顶元素时，top-1，所以，非空栈中的top指针始终在栈顶元素的下一个位置上。
-
链式栈：链表
微信图片_20211226152320.jpg
3.2 栈的应用举例
3.2.2 括号匹配的检验
/*
括号匹配的校验
*/
#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100 //存储空间的初始分配量
#define LISTINCREMENT 10 //存储空间的分配增量
typedef struct {
char *base; //栈底指针，在构造前和销毁后，base=NULL
char *top; //栈顶指针
int stacksize; //当前分配的存储容量（以sizeof(char)为单位）
}SqStack;
//初始化一个空栈
int initStack(SqStack *S){
S->base = (char*) malloc(LIST_INIT_SIZE * sizeof(char));
if(!S->base) return 0; //存储分配失败
S->top = S->base;
S->stacksize = LIST_INIT_SIZE;
return 1;
}
//获取栈顶元素
int getTop(SqStack S,char *e){
if(!S.base || S.base == S.top) return 0; //空栈
*e = *(S.top - 1);
return 1;
}
//入栈
int push(SqStack *S,char e){
if(!S->base) return 0; //栈不存在
if(S->top - S->base >= S->stacksize){ //栈满了，需要扩容
S->base = (char*)realloc(S->base,(S->stacksize + LISTINCREMENT)*sizeof(char));
if(S->base) return 0; //空间分配失败
S->top = S->base + S->stacksize;
S->stacksize = S->stacksize + LISTINCREMENT;
}
*S->top++ = e; //top指针位置存放e，然后top加1，指向下一个位置。
return 1;
}
//出栈
int pop(SqStack *S,char *e){
if(!S->base || S->base == S->top) return 0; //空栈
*e = *--S->top; //top指针先减1，此时指向的就是栈顶元素
return 1;
}
//括号匹配校验
int match(char arr[],int len){
SqStack S;
int i;
char e;
if(!arr || !len) return 0;
initStack(&S);
for(i=0;i<len;i++){
if(arr[i] == '[' || arr[i] == '('){
push(&S,arr[i]);
printf("入栈：%c\n",arr[i]);
}else if(arr[i] == ']' || arr[i] == ')'){
pop(&S,&e);
printf("判断：%c %c\n",e,arr[i]);
if(e == '[' && arr[i] == ']')
continue;
else if(e == '(' && arr[i] == ')')
continue;
else
return 0; //不匹配
}else{
return 0; //非法字符
}
}
if(S.base != S.top){
return 0;
}
return 1;
}
int main(){
int len, res;
char arr[8] = {'[','(','[',']','[',']',')',']'};
len = sizeof(arr) / sizeof(char);
printf("数组长度len=%d\n",len);
res = match(arr,len);
printf("括号是否匹配：%d\n",res);
return 1;
}
第六章 树和二叉树
建立二叉树与遍历
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结点
typedef struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//构建二叉树
BiTNode* buildTree(){
char c;
BiTNode *p;
c = getchar();
printf("用户输入：%c\n",c);
if(c == '0') return NULL;
p =(BiTNode*) malloc(sizeof(BiTNode));
printf("构建地址：%d\n",p);
p->data = c;
p->lchild = buildTree();
p->rchild = buildTree();
return p;
}
//递归前序遍历
void PreOrderTraverse(BiTNode *p){
if(p == 0) return;
printf("%c",p->data);
PreOrderTraverse(p->lchild);
PreOrderTraverse(p->rchild);
return;
}
int main(){
BiTree T = buildTree();
printf("构建完毕\n");
PreOrderTraverse(T);
printf("\n");
return 1;
}