考研笔记之数据结构之线性表（严蔚敏版）

1. 顺序表的特点为表中元素的逻辑顺序与物理顺序相同。
2. sizeof(数据类型)：数据元素所占用的存储空间的大小
3. 起始位置为LOC(A),第i个元素为LOC(A)+(n-1)*sizeof(数据类型)

1. 使用静态数组
2. 大小确定无法改变

#define MaxSize 10
typedef struct {
	ElemType data[MaxSize];
	int length;
}mystruct;

ElemType:是一个抽象的数据类型，表示我们想使用的所有数据类型。（编写程序不能直接使用哦！）

# include
# define maxSize 10 // 定义最大长度
typedef struct {
	int data[maxSize]; // 使用静态数组存储元素
	int lenth; // 顺序表的当前长度
}sqList;  // 顺序表类型定义
void initList(sqList &L) {
	for (int i = 0; i < maxSize; i++) { //设置所有元数组素初始值（这里的括号可以去掉）
		L.data[i] == 0; //定义初始长度
	}
	L.lenth = 0;
}
int main() {
	sqList L; //生成一个顺序表
	initList(L); //初始化顺序表
	return 0;
}

如果数组满了，顺序表的表长确定，数组空间确定（存储空间是静态的）

1. 使用“动态数组”
2. L.data=(ElemType *)malloc(sizeof(ElemType)*initSize);
3. 顺序表满时可以使用malloc动态扩展存储的最大容量
4. 需要元素复制到新的存储区域，并用free函数释放原区域

# define initSize 10 //初始长度
typedef struct {
	ElemType* data; //动态分配数组指针
	int maxSize;  //最大容量
	int length;   // 当前长度
}sqList;  // 类型的定义

PS:
—malloc、free函数—
L.data=(ElemType *)malloc(sizeof(ElemType)*initSize)
``

# include
#include  // 使用malloc、free函数需要引用头文件
# define initSize 10 // 默认最大长度
typedef struct {
	int * data;
	int maxSize;
	int length;
}sqList;

void initList(sqList& L) {
	L.data = (int*)malloc(initSize * sizeof(int));//用malloc函数申请一篇连续的空间
	L.length = 0;
	L.maxSize = initSize;
}

void increaseSize(sqList& L, int len) {
	int* p = L.data;
	L.data = (int*)malloc((L.maxSize + len) * sizeof(int));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];
	}
	L.maxSize = L.maxSize + len;
	free(p);
}

int main() {
	sqList L; //声明一个顺序表
	initList(L); //初始化顺序表
	increaseSize(L, 5);
	return 0;
}

顺序表的特点：

1. 随机访问，在O(1)内找到第i个元素
2. 存储密度高，每个节点只存储数据元素
3. 扩展不方便（采用动态分配的方式实现扩展时间复杂度也比较高）
4. 插入、删除不方便需要移动大量的元素

# define maxSize 10
typedef struct {
	ElemType data[maxSize];
	int length;
}sqList;

ElemType getElem(sqList L, int i) {
	return L.data[i - 1];
}

# define initSize 10
typedef struct {
	ElemType* data;
	int MaxSize;
	int length;
}sqList;

Elemtype getElem(sqList L, int i) {
	return L.data[i - 1];
}

// 按值查找(返回数组下标)
int localElem(sqList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e){
			return i + 1;
		}
	}
	return 0; //没有找到返回0

PS: 结构类型相同的比较不能直接使用等号，需要分别对结构体中的每一个元素进行比较

时间复杂度：

• 最好的结果O(1)：出现在顺序表第一个位置
• 最坏的结果O(n)：出现在顺序表最后一个位置
• 平均的结果O((n+1)/n)：出现在每一个位置的概率相等

# include
# include 
# define initSize 10
typedef struct {
	int * data;
	int maxSize;
	int length;
}sqList;

void initList(sqList& L) {
	L.data = (int*)malloc(initSize * sizeof(int));
	L.length = 0;
	L.maxSize = initSize;
}

void increaseSize(sqList& L, int len) {
	int* p = L.data;
	L.data = (int*)malloc((L.maxSize + len) * sizeof(int));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];
	}
	L.maxSize = L.maxSize + len;
	free(p);
}

// 按位查找
int getElem(sqList L, int i) {
	return L.data[i - 1];
}

// 按值查找(返回数组下标)
int localElem(sqList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e){
			return i + 1;
		}
	}
	return 0;
}


int main() {
	sqList L;
	initList(L);
	increaseSize(L, 5);
	return 0;
}

单链表的定义：通过一组任意的存储单元来存储线性表中的数据元素。（除了存储自身信息外还需要存储指向后继的指针）

# include
# include 

typedef struct LNode{ // 定义单链表节点类型
	ElemType data;  // 每个节点存放一个数据类型
	struct  LNode* next; //指针指向下一个节点
}LNode,*linkList;

// 等价于
struct LNode{
	ElemType data;
	struct LNode* next;
};
typedef struct LNode LNode;  //将结构体重命名为LNode
typedef struct LNode *linklist; //表示指向struct LNode的指针(将结构体指针重命名为linkList)

//声明头指针
LNode* L;
// 或
linkList* L;

理解：

• LNode是一个具象的结构体，指向的是包含某个数据类型的数据域和指针域的结构体类型
• LinkList是LNode的指针类型，它占用一定的内存空间，内存空间中的值位一个LNode类型结构体的地址
  声明一个不带头节点的单链表

typedef struct LNode{ // 定义单链表节点类型
	int data;  // 每个节点存放一个int类型
	struct  LNode* next; //指针指向下一个节点
}LNode,*linkList;

bool initList(linkList& L) {
	L = NULL;  //空表无任何节点
	return true;
}
// 判断单链表是否为空
bool Empty(linkList L) {
	if (L == NULL) {
		return true;
	}
	else
	{
		return false;
	}
}

int main()  {
	linkList L; //初始化空表
	initList(L); 
	return 0;
}

带头节点的单链表

# include
# include 

typedef struct LNode{ // 定义单链表节点类型
	int data;  // 每个节点存放一个int类型
	struct  LNode* next; //指针指向下一个节点
}LNode,*linkList;

//  初始化一个单链表
bool initList(linkList& L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L==NULL)
	{
		return false;
	}
	L->next = NULL;
	return true;
}

int main() {
	linkList L;
	initList(L);
	return 0;
}

最后插入新的结点的顺序不能颠倒

typedef struct LNode{ // 定义单链表节点类型
	int data;  // 每个节点存放一个int类型
	struct  LNode* next; //指针指向下一个节点
}LNode,*LinkList;

// 中间插入
bool ListInsert(LinkList& L, int i, int e) {
	if (i<1)  //判断插入的位置是否合适
	{
		return false;
	}
	LNode* p; //指针p指向当前扫描到的结点
	int j = 0;  //p指向第几个结点
	p = L;
	while (p!=NULL && j  //循环到i-1个节点 （找到i-1个结点）
		p = p->next;
		j++;
	}
	if (p == NULL) {  //i的值不合法，超出了插入的范围（i-1）
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

后插操作：

// 后插（在某个结点后插入一个结点）
bool InsertNextNode(LNode* p, int e) {
	if (p == NULL) {
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) {
		printf("分配失败");
	}
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

前插操作：

// 前插操作(偷天换日) 原理：使用尾插法在后面插入一个新的结点
// 然后将前一个结点的data放到新结点，然后将要插入的数据放到p中
bool InsertPriNode(LNode* p, int e) {
	if (p == NULL) {
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s==NULL)
	{
		return false;
	}
	s->next = p->next; 
	p->next = s;    // 将新结点s连接到p之后
	s->data = p->data; //将P中的元素，复制到s中
	p->data = e;    // 将p中的元素覆盖为e
	return true;
}

// 王道书的版本
bool insertPrinorNode(LNode* p, LNode* s) {
	if (p==NULL||s==NULL){
		return false;
	}
	s->next = p->next;
	p->next = s;
	int tep = p->data;
	p->data = s->data;
	s->data = tep;
	return true;
}

删除操作：

// 按位序删除
bool ListDelete(LinkList& L, int i, int e) {
	if (i < 1){
		return false;
	}
	LNode* p;  // 当前指针所在的结点位置
	int j = 0; //指向第几个结点
	p = L; //指向头结点，第0个（无数据）
	while (p!=NULL&&j //循环到第i-1个（找到删除结点的前驱结点）
		p = p->next;
		j++;
	}
	if (p == NULL) {  //i的值不合法
		return false;
	}
	if (p->next == NULL) { //第i-1个结点之后无其他按结点
		return false;
	}
	LNode* q = p->next; //令q指向被删除的结点
	e = q->data;  //用e返回删除的值
	free(p);   // 释放存储空间
	return true; // 删除成功
}

//删除指定结点p（无法删除链表的最后一个元素）
bool DeleteNode(LNode* p) {
	if (p == NULL) {
		return false;
	}
	LNode* q = p->next;
	q->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

不带头结点的插入
相比于带头节点的来说，需要多谢一块代码来处理第一个结点的删除

bool ListInsert(LinkList& L, int i, int e) {
	if (i<1)  //判断插入的位置是否合适
	{
		return false;
	}
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next=L;
		L = s;
		return true;
	}
	LNode* p; //指针p指向当前扫描到的结点
	int j = 0;  //p指向第几个结点
	p = L;
	while (p!=NULL && j  //循环到i-1个节点 
		p = p->next;
		j++;
	}
	if (p == NULL) {  //i的值不合法，超出了插入的范围（i-1）
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

小结：

• 空表的判断：
  • 不带头结点：L==NULL
  • 带头节点：L->next == NULL
• 区别LNode和LinkList
  • LNode强调这是节点
  • LinkList强调这是链表