Daisy's Blog
ZJU 数据结构课程笔记 | 线性表
Daisy Author
  2023-07-14 14:45:57   2024-10-19 23:23:34    1.6k Words  7 Mins

这是我在学习浙江大学 MOOC『数据结构』的第二章：线性表 的过程中做的笔记。

ZJU 数据结构 MOOC 课程链接

引入： 一元多项式及其计算

  • 多项式系数
  • 多项式指数

1.顺序存储结构

数组表示： a[i]代表项的系数

缺陷：不仅存储非零项导致空间巨大浪废

方便但有很大问题

2.顺序存储结构表示非零项

涉及两个信息：系数与指数 => 二元组（,）

结构数组表示：结构体存储,

3.链表存储结构

p1

启示

1.同一问题可以有不同表示方法
2.有一类共性问题：有序线性序列的组织和管理

什么是线性表

def：同类型数据元素构成有序序列的线性结构

  • 表中元素个数称为线性表的长度
  • 线性表没有元素时，称为空表
  • 表起始位置称为表头，结束位置称为表尾

p2

链表

链式存储结构，增加删除元素通过增添删除链节实现

定义链节：

1
2
3
4
5
6
7
typedef struct LNode *List
struct LNode {
	ElementType Data;
	List Lnode L;	
};
struct Lnode L;
List Ptrl;

function1 求表长

1
2
3
4
5
6
7
8
9
10
int length(List Ptrl) //Ptrl代表头指针
{
	int j = 0;
	List p = Ptrl;
	while (p) {
		p = p -> next;
		j ++;
	}
	return j;
}

function2 查找

  • 按序号查找
1
2
3
4
5
6
7
8
9
10
List FindKth(int k, List Ptrl)
{
	List p = ptrl;
	int i = 1;
	while (p !=  NULL && i < k) {
		p = p -> next;
		i ++;
	}
	return p;
}
  • 按值查找
1
2
3
4
5
6
7
List Find(ElementType X, List Ptrl)
{
	List p = Ptrl;
	while (p != NULL && p -> Data != X)
		p = p -> next;
	return p;
}

function3 插入

  1. 构造新节点，s指向
  2. 找到i - 1节点，p指向
  3. 修改指针，插入节点 注意链表指针赋值顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
List Insert(ElementType X, int i, List Ptrl)
{
	List p, s;
	//插在头节点
	if (i == 1) {
		s = (List)malloc(sizeof(struct LNode));
		s -> Data = X;
		s -> Next = Ptrl;
		return s;
	}
	p = FIndKth(i - 1, Ptrl)
	if (p == NULL) {
		printf("参数i错误")；
		return NULL;
	} else {
		s = (List)malloc(sizeof(struct LNode));
		s -> Data = X;
		s -> next = p -> next;
		p -> next = s;
		return Ptrl;
	}
}

function4 删除

  1. 找到i - 1节点，p指向
  2. 找到将删除节点，s指向
  3. 修改指针，释放所删除节点内存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List Delet(int i, List Ptrl)
{
	List p, s;
	if (i == 1) {
		s = Ptrl;
		if (Ptrl != NULL) Ptrl = Ptrl -> next;
		else return NULL;
		free(s);
		return Ptrl;
	}
	p = FindKth(i - 1, Ptrl)
	if (p == NULL) { //所删除节点的前一节点是否存在
		printf("node No.%d doesnt exist"，,i - 1);
		return NULL;
	} else if (p -> next = NULL) { //所删除节点是否存在
		printf("node No.%d doent exist", i);
		return NULL;
	} else {
		s = p -> next;
		p -> next = s -> next;
		free(s);
		return Ptrl;
	}
}

广义表

  • 线性表推广
  • 元素可以是单元素或另一个广义表
1
2
3
4
5
6
7
8
9
typedef struct GNode *GList;
strcut GNode {
	int Tag; //标志域：0 - 单元素，1 - 广义表
	union { //子表指针域Sublist与Data复用，共享存储空间
		ElelmentType Data;
		Glist SubList;
	} URegion;
	GList Next; //指向下一节点
};

多重链表

节点可能同时隶属多个链表

  • 节点指针域会有多个
  • 包含两个指针域的链表不一定是多重链表，比如双向链表

用途：存储树，图等数据结构

堆栈

后缀表达式：运算符号位于两个运算数后

1
2
3
a b c * + d e / -
<=>
a + b * c - d / e

从左到右扫描，逐个处理运算数和运算符号 ==利用堆栈==

p3

p4

堆栈的顺序存储实现

实现：一维数组＋记录栈顶元素位置的变量

1
2
3
4
5
6
#define MaxSize <堆栈容量>
typedef strcut SNode *Stack
struct SNode {
	ElementType Data[MaxsSize];
	int Top; //Top = -1 表示堆栈空
};

function1 入栈

1
2
3
4
5
6
7
8
9
10
void Push(Stack PtrS, ELementTypeType item)
{
	if (PtrS -> Top == MaxSize - 1) {
		printf("the stack is full");
		return ERROR;
	} else {
		PtrS -> Data[++ (PtrS -> Top)] = item;
		return ;
	}
}

funciton2 出栈

1
2
3
4
5
6
7
8
9
ElementType Pop(stack PtrS)
{
	if (PtrS -> Top == -1) {
		printf("the stack is empty");
		return ERROR;
	} else {
		return (PtrS -> Data[(PtrS -> Top) --]);
	}
}

堆栈的链式结构实现

Tips 堆栈的单向操作性决定了堆栈的链式结构只能从头节点进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct SNode *Stack;
struct SNode {
	ElementType Data;
	struct SNode *next;
};
SNode ptrl;
Stack CreateStack() //创造空节点，next指向栈的头节点
{
	Stack S; 
	S = (stack)malloc(sizeof(struct SNode));
	S -> next = NULL:
	return S;
}
int isEmpty(Stack S)
{
	return (S -> Next == NULL);
}

function push

1
2
3
4
5
6
7
8
9
10
void Push(ElementType item, Stack S)
{
	struct SNode *TempCell;
	TmpCell = (struct SNode *)malloc(sizeof(struct SNode));
	TmpCell -> Data = item;
	TmpCell -> next = S -> next;
	S -> next = TmpCell;
	return ;
	//实际完成插入操作
}

function pop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType Pop(stack S)
{
	struct SNode *FirstCell;
	ElementType TopElem;
	if (IsEmpty(S)) {
		printf("堆栈空");
		return NULL;
	} else {
		FirstCell = S -> next;
		S -> next = FistCell -> next;
		TopElem = FirstCell -> Element;
		free(FirstCell);
		return TopElem;
	}
}

堆栈运用：表达式求值

中缀表达式转化为后缀表达式

  1. 运算数相对顺序不变
  2. 运算符号顺序发生变化
    • 存储等待中的运算符号
    • 将当前运算符号与等待中的最后一个运算符号进行比较

p5

队列

具有一定操作约束的线性表

  • 插入和删除操作 ==一端插入，另一端删除==
1
first in, first out.

p6

队列的顺序存储实现

一维数组 + 记录头元素位置front + 记录尾元素位置rear

1
2
3
4
5
6
7
#define MaxSize <队列容量>
struct QNode {
	ElementType Data[MaxSize];
	int rear;
	int front;
};
typedef struct QNode *Queue;

front与rear初始化为-1（空），加入元素，rear++，删除元素，front++

==前置空间浪费== 循环队列

p7

front == rear时，队列空？满？无法判断！

解决方案：

  1. 使用额外标记
  2. 仅使用n - 1数组空间

function1 入队

1
2
3
4
5
6
7
8
9
void AddQ(Queue PtrQ, ElementType item)
{
	if ((PtrQ -> rear + 1) % MaxSize == PtrQ -> front) {
		printf("the queue is full");
		return ;
	}
	PtrQ -> rear = (PtrQ -> rear + 1) % MaxSize;
	PtrQ -> Data[PtrQ -> rear] = item;
}

function2 出队

1
2
3
4
5
6
7
8
9
10
ElementType DeleteQ(Queue PtrQ)
{
	if (PtrQ -> front == PtrQ -> rear) {
		printf("the Queue is empty");
		return ERROR;
	} else {
		PtrQ -> front = (PtrQ -> front + 1) % MaxSize;
		return PtrQ -> Data[PtrQ -> front];
	}
}

队列的链式存储实现

单链表，插入删除在链表的两端进行

p8

1
2
3
4
5
6
7
8
9
10
struct Node {
	ElementType Data;
	struct Node *Next;
};
struct QNode {
	struct Node *rear;
	struct Node *front;
};
typedef struct QNode *Queue;
Queue  PtrQ;

p9

front = NULL -> empty queue

funtion1 出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ElementType DeleteQ(Queue PtrQ)
{
	struct Node *FrontCell;
	ElementType FrontElem;
	if (PtrQ -> front == NULL) {
		printf("the queue is empty");
		return ERROR;
	} //检查队列是否为空
	FrontCell = PtrQ -> front;
	if (PtrQ -> front == PtrQ -> rear) //队列只含一元素
		PtrQ -> front = PtrQ -> rear = NULL;
	else 
		PtrQ -> front = PtrQ -> front -> next;
	FrontElem = FrontCell -> Data;
	free(FrontCell);
	return FrontElem;
}

funtion2 入队

1
2
3
4
5
6
7
8
9
10
void AddQ(Queue PtrQ, ELementType item)
{
	struct Node *NewNode;
	NewNode = (struct Node *)malloc(sizeof(struct Node));
	NewNode.Data = item;
	NewNode.Next = NULL;
	Ptrl -> rear -> next = NewNode;
	Ptrl -> rear = NewNode;
	return ;
}
ZJU 数据结构课程笔记 | 线性表
2023/07/14/Data-Structures-note-2/
Author
Daisy
Published
2023-07-14 14:45
License
  1. 引入： 一元多项式及其计算
    1. 1.顺序存储结构
    2. 2.顺序存储结构表示非零项
    3. 3.链表存储结构
    4. 启示
  2. 什么是线性表
  3. 链表
    1. function1 求表长
    2. function2 查找
    3. function3 插入
    4. function4 删除
  4. 广义表
    1. 多重链表
  5. 堆栈
    1. 堆栈的顺序存储实现
      1. function1 入栈
      2. funciton2 出栈
    2. 堆栈的链式结构实现
      1. function push
      2. function pop
    3. 堆栈运用：表达式求值
  6. 队列
    1. 队列的顺序存储实现
      1. function1 入队
      2. function2 出队
    2. 队列的链式存储实现
      1. funtion1 出队
      2. funtion2 入队
  1. 引入： 一元多项式及其计算
    1. 1.顺序存储结构
    2. 2.顺序存储结构表示非零项
    3. 3.链表存储结构
    4. 启示
  2. 什么是线性表
  3. 链表
    1. function1 求表长
    2. function2 查找
    3. function3 插入
    4. function4 删除
  4. 广义表
    1. 多重链表
  5. 堆栈
    1. 堆栈的顺序存储实现
      1. function1 入栈
      2. funciton2 出栈
    2. 堆栈的链式结构实现
      1. function push
      2. function pop
    3. 堆栈运用：表达式求值
  6. 队列
    1. 队列的顺序存储实现
      1. function1 入队
      2. function2 出队
    2. 队列的链式存储实现
      1. funtion1 出队
      2. funtion2 入队