学习过程主要依照中国MOOC课程，感谢MOOC，感谢浙大授课大佬。
线性表及其实现
线性表
以一元多项式表示及运算为例：
- 顺序存储结构直接表示。数组各分量对应多项式各项，如a[i]表示项x^i的系数ai,表示方法简单，操作也很方便，但有时会造成空间的浪费，例如表示f(x)=x+x^2000，就要开辟一个2001大小的数组来表示；
- 顺序存储结构表示非零项。每个非零项ai*x^i涉及两个信息：系数ai和指数i，可以将一个多项式看作一个二元数组（ai,i）的集合，每一项按照指数大小顺序存储的话，进行加减操作也比较简单；
- 链表结构存储非零项。链表中每个结点存储一个非零项，包括系数和指数两个数据域以及一个指针域。
线性表：由同类型数据元素构成有序序列的线性结构。
线性表的实现
- 线性表的顺序存储实现。利用数组的连续存储空间顺序存放线性表的各元素；
- 线性表的链式存储实现。不要求逻辑上相邻的两个元素物理上也相邻。
两种方式都包括移动、查找、插入、删除等操作。
1 | typedef int Position; |
1 | typedef struct LNode *PtrToLNode; |
广义表
广义表是线性表的推广，对于线性表而言，n个元素都是基本的单元素，而在广义表中，这些元素不仅可以是单元素也可以是另一个广义表。
多重链表
链表中的节点可能同时隶属于多个链，也就是说多重链表中结点的指针域会有多个，但包含两个指针域的链表并不一定是多重链表，例如双向链表不是多重链表。树、图等复杂的数据结构都可以采用多重链表来存储，
典型的多重链表：十字链表（用来存储稀疏矩阵等）
堆栈及其实现#
堆栈
堆栈：具有一定操作约束的线性表。
只在一端（栈顶，Top）做插入（入栈，Push）、删除（出栈，Pop），后入先出（Last In First Out，LIFO）
堆栈的实现
- 顺序存储实现。用一个一维数组以及一个一个记录栈顶元素位置的变量组成。
- 链式存储实现。栈的链式存储结构实际上就是一个单项链，叫做链栈。插入和删除操作只能在链栈的栈顶进行，栈顶指针Top应该在链表的头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48typedef int Position;
struct SNode {
ElementType *Data; /* 存储元素的数组 */
Position Top; /* 栈顶指针 */
int MaxSize; /* 堆栈最大容量 */
};
typedef struct SNode *Stack;
Stack CreateStack( int MaxSize )
{
Stack S = (Stack)malloc(sizeof(struct SNode));
S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
S->Top = -1;
S->MaxSize = MaxSize;
return S;
}
bool IsFull( Stack S )
{
return (S->Top == S->MaxSize-1);
}
bool Push( Stack S, ElementType X )
{
if ( IsFull(S) ) {
printf("堆栈满");
return false;
}
else {
S->Data[++(S->Top)] = X;
return true;
}
}
bool IsEmpty( Stack S )
{
return (S->Top == -1);
}
ElementType Pop( Stack S )
{
if ( IsEmpty(S) ) {
printf("堆栈空");
return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
}
else
return ( S->Data[(S->Top)--] );
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49typedef struct SNode *PtrToSNode;
struct SNode {
ElementType Data;
PtrToSNode Next;
};
typedef PtrToSNode Stack;
Stack CreateStack( )
{ /* 构建一个堆栈的头结点，返回该结点指针 */
Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;
}
bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
return ( S->Next == NULL );
}
bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
PtrToSNode TmpCell;
TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
TmpCell->Data = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
return true;
}
ElementType Pop( Stack S )
{ /* 删除并返回堆栈S的栈顶元素 */
PtrToSNode FirstCell;
ElementType TopElem;
if( IsEmpty(S) ) {
printf("堆栈空");
return ERROR;
}
else {
FirstCell = S->Next;
TopElem = FirstCell->Data;
S->Next = FirstCell->Next;
free(FirstCell);
return TopElem;
}
}队列及其实现
队列
队列：具有一定操作约束的线性表。
只在一端插入（入队，AddQ），在另一端删除（出队，DeleteQ），先进先出（FIFO）。队列的实现
- 顺序存储实现。由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
- 链式存储实现。队列的链式存储结构实际上也是一个单项链。插入和删除操作在链表的两头进行，队列指针front和rear分别指向链表的头和尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
Queue CreateQueue( int MaxSize )
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
bool IsFull( Queue Q )
{
return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
bool AddQ( Queue Q, ElementType X )
{
if ( IsFull(Q) ) {
printf("队列满");
return false;
}
else {
Q->Rear = (Q->Rear+1)%Q->MaxSize;
Q->Data[Q->Rear] = X;
return true;
}
}
bool IsEmpty( Queue Q )
{
return (Q->Front == Q->Rear);
}
ElementType DeleteQ( Queue Q )
{
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
Q->Front =(Q->Front+1)%Q->MaxSize;
return Q->Data[Q->Front];
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode {
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
bool IsEmpty( Queue Q )
{
return ( Q->Front == NULL);
}
ElementType DeleteQ( Queue Q )
{
Position FrontCell;
ElementType FrontElem;
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
FrontCell = Q->Front;
if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
else
Q->Front = Q->Front->Next;
FrontElem = FrontCell->Data;
free( FrontCell ); /* 释放被删除结点空间 */
return FrontElem;
}
}
以上。
注：转载文章请注明出处，谢谢~