线性表

1.线性表

线性表

1.1 顺序表（顺序存储）

顺序表总结

• 静态分配

#define Size 10
typedef struct{
ElemType data[Size]; //用静态的数组存放数据
int length;
}SqList

• 动态分配

#define Size 10
typedef struct{
ElemType *data; //动态分配数组的指针
int MaxSize;//顺序表的最大容量
int length;//顺序表当前长度
}SqList

//1.C语言实现动态分配——malloc，free
L.data = (ElemType*)malloc(sizeof(ElemType) * Size);
⚠️ malloc()前需要加具体指针的强制转化，例如：（int *）(int*)malloc(sizeof(int) * Size)；

//2.C++实现动态分配——new，delete
代码实现自行查找

1.2 单链表

• 单链表定义

struct LNode{
ElemType data;
struct LNode *next;
}；

//typedef的使用
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode , *LinkList;

等价于下面

struct LNode{
ElemType data;
struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

• 不带头节点的单链表插入操作

不带头节点的插入

• 带头节点的单链表插入操作

带头节点的插入

• 单链表创建——头插法
  能实现链表逆序

  头插法

• 单链表创建——尾插法

尾插法

1.3 双链表

• 定义

struct DNode{
ElemType data;
struct DNode *prior , *next; //前驱和后继指针
};