1. 线性表:

  • 多项式表示问题的启示：
    1. 同一个问题可以有不同的表示（存储）方法
    2. 有一类共性问题：有序线性序列的组织和管理

“线性表(Linear List)”：由同类型数据元素构成有序序列的线性结构

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

线性表的抽象数据类型描述

类型名称：线性表（List）

数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2, … ,an )

操作集：线性表L 属于 List，整数i表示位置，元素X 属于 ElementType，

线性表基本操作主要有：

  1. List MakeEmpty()：初始化一个空线性表L；
  2. ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；
  3. int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；
  4. void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；
  5. void Delete( int i, List L )：删除指定位序i的元素；
  6. int Length( List L )：返回线性表L的长度n。

线性表的顺序存储实现:

1> 数组线性表[线性结构]

  • 利用数组的连续存储空间顺序存放线性表的各元素

主要操作的实现:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小
typedef int ElementType;  // ElementType 可定义为任意类型
typedef struct LNode *List; 
struct LNode{
ElementType Data[MAXSIZE]; 
int Last;  // Last 定义线性表的最后一个元素
};

List MakeEmpty(); //初始化顺序表 
int Find(ElementType X,List L); //查找 X 第一次出现的下标 
void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X 
void Delete(int i,List L);   //删除下标为 i 的当前值 
ElementType FindKth(int K,List L);  //返回下标为 K 的当前值
int Length(List L);  //返回顺序表的长度 


// 初始化
List MakeEmpty()
{
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;

    return L;
}

// 按值差找
int Find(ElementType X, List L)
{
    int cnt=0;
    while(cnt <= L->Last && L->Data[cnt] != X)  cnt++;
    if(cnt > L->Last)  return -1;
    else return cnt;
    return 0;
}

// 插入
void Insert(ElementType X, int i, List L)
{
    int j;
    if(L->Last == MAXSIZE-1)  
    {
        cout << "表已满" << endl;
        return;
    }
    else if(i<0)
    {
        cout << "位置不合法" << endl;
        return;
    }
    for(int j=L->Last; j>=i; j--)  L->Data[j+1] = L->Data[j];
    L->Data[i] = X;
    L->Last++;
    return;
}

// 删除
void Delete(int i, List L)
{
    int j;
    if(i<0 || i>L->Last)
    {
        cout << "位置不合法" << endl;
        return;
    }
    for(int j=i; j<L->Last; j++)  L->Data[j] = L->Data[j+1];
    L->Data[L->Last] = NULL;
    L->Last--;
    return;
}

// 按序差找
ElementType FindKth(int K,List L)
{
    if(K<0 || K>L->Last)
    {
        cout << "位置不合法" << endl;
        return NULL;
    }
    return L->Data[K];
}

// 表长
int Length(List L)
{
    return L->Last+1;
}

2> 链表线性表[线性结构]:

  • 不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

主要操作的实现:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <algorithm>
using namespace std;

typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;

struct LNode{
    ElementType Data;   //数据域 
    List Next;   // 下一个链表的地址 
}; 

List L;

List MakeEmpty(); //初始化链表 
int Length(List L);  // 以遍历链表的方法求链表长度 
List FindKth(int K,List L);  // 按序号查找 
List Find(ElementType X,List L);  // 按值查找 
List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 
List Delete(int i,List L); // 删除第 i(i>0) 个结点 
void Print(List L); // 输出链表元素 


// 初始化链表
List MakeEmpty()
{
    List L = new struct LNode;
    L = NULL;
    return L;
}

// 表长
int Length(List L)
{
    List p = L;
    int cnt = 0;
    while(p)
    {
        p = p->Next;
        cnt++;
    }
    return cnt;
}

// 按序差找
List FindKth(int K, List L)
{
    List p = L;
    int cnt = 1;
    while(p && cnt<K)
    {
        p = p->Next;
        cnt++;
    }
    if(cnt == K)  return p;
    else  return NULL;
}

// 按值差找
List Find(ElementType X, List L)
{
    List p = L;
    int cnt;
    while(p && p->Data!=X)  p = p->Next;
    return p; // 若没有找到 则返回最后一个链表的Next，即NULL
}

/* 插入
1. 用 s 指向一个新的结点
2. 用 p 指向链表的第 i-1 个结点 
3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 
4. p->Next = s，将 p 的下一结点改为 s   */
List Insert(ElementType X, int i, List L)
{
    List p, s;
    if(i == 1)
    {
        s = new struct LNode;
        s->Data = X;
        s->Next = L;
        return s;
    }
    p = FindKth(i-1, L);
    if(!p)
    {
        cout << "Error" << endl;
        return NULL;
    }
    else
    {
        s = new struct LNode;
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return L;
    }
}

/* 删除
1. 用 p 指向链表的第 i-1 个结点 
2. 用 s 指向要被删除的的第 i 个结点
3. p->Next = s->Next，p 指针指向 s 后面
4. free(s)，释放空间 */
List Delete(int i, List L)
{
    List p, s;
    if(i == 1)
    {
        s = L;
        if(L)  L = L->Next;
        else return NULL;
        delete s;
        return L;
    }
    p = FindKth(i-1, L);
    if(!p || !(p->Next))
    {
        cout << "ERROR!" << endl;
        return NULL;
    }
    else
    {
        s = p->Next;
        p->Next=s->Next;
        delete s;
        return L;
    }
}

// 输出链表元素
void Print(List L)
{
    List t;
    int flag = 1;
    cout << "Present List is: ";
    for(t = L; t; t=t->Next)
    {
        cout << t->Data << ' ';
        flag = 0;
    }
    if(flag)  cout << "NULL" << endl;
}




2.堆栈:

1> 栈的顺序储存[线性结构]

  • 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

主要操作的实现:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXSIZE 100   // 堆栈元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型 
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[MAXSIZE];   // 存储堆栈元素
    int Top;  // 记录栈顶元素下标 
}; 

Stack CreateStack();  // 初始化堆栈 
int IsFull(Stack S); // 判断堆栈是否已满 
int IsEmpty(Stack S);   // 判断堆栈是否为空 
void Push(Stack S,ElementType item);   // 入栈 
ElementType Pop(Stack S);   // 出栈


// 初始化堆栈
Stack CreateStack()
{
    Stack S = new struct SNode;
    S->Top = -1;
    return S;
}

// 是否已满
int IsFull(Stack S)
{
    return (S->Top == MAXSIZE-1);
}

// 是否为空
int IsEmpty(Stack S)
{
    return (S->Top == -1);
}

// 入栈
void Push(Stack S, ElementType item)
{
    if(IsFull(S))
    {
        cout << "IsFull !" << endl;
        return;
    }
    else
    {
        S->Top++;
        S->Data[S->Top] = item;
        return;
    }
}

// 出栈
ElementType Pop(Stack S)
{
    if(IsEmpty(S))
    {
        cout << "IsEmpty !" << endl;
        return 0;
    }
    else
    {
        ElementType val = S->Data[S->Top];
        S->Top--;
        return val;
    }
}

2> 栈的链表储存[线性结构]

  • 栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

主要操作的实现: 
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
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXSIZE 100   // 堆栈元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型 
typedef struct SNode *Stack;
struct SNode{
    ElementType Data;   // 存储堆栈元素
    Stack Next;  // 记录栈顶元素下标 
}; 

Stack CreateStack();  // 初始化链栈 
int IsEmpty(Stack S);  // 判断链栈是否为空 
void Push(Stack S,ElementType item);  // 入栈 
ElementType Pop(Stack S);  // 出栈


// 初始化
Stack CreateStack()
{
    Stack S = new struct SNode;
    Stack Next = NULL;
    return S;
}

// 是否为空
int IsEmpty(Stack S)
{
    return(S->Next == NULL);
}

// 入栈
void Push(Stack S, ElementType item)
{
    Stack temp = new struct SNode;
    temp->Data = item;
    temp->Next = S->Next;
    S->Next = temp;
}

// 出栈
ElementType Pop(Stack S)
{
    Stack First = S->Next;
    ElementType TopVal;
    if(IsEmpty(S))
    {
        cout << "IsEmpty !" << endl;
        return 0;
    }
    else
    {
        TopVal = First->Data;
        S->Next = First->Next;
        delete First;
        return TopVal;
    }
}




2.队列:

1> 循环队列的顺序储存[线性结构]

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#define MAXSIZE 12
typedef struct QNode *Queue;
struct QNode
{
	int front;
	int rear;
	int Data[MAXSIZE];
};

Queue CreateQueue();   // 初始化队列 
void AddQ(Queue Q, int item);  //  入队
int IsFull(Queue Q);   // 判断队列是否已满 
int DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q);  // 判断队列是否为空 

Queue CreateQueue()
{
	Queue Q = new struct QNode;
	Q->front = -1, Q->rear = -1;
	return Q;
}

int IsFull(Queue Q)
{
	return (Q->rear+1) % MAXSIZE == Q->front;
}

int IsEmpty(Queue Q)
{
	return Q->rear == Q->front;
}

void AddQ(Queue Q, int item)
{
	if(IsFull(Q))  cout << "Queue is full!" << endl;
	else
	{
		Q->rear = (Q->rear+1) % MAXSIZE;
		Q->Data[Q->rear] = item;
	}
}

int DeleteQ(Queue Q)
{
	if(IsEmpty(Q))
	{
		cout << "Queue is empty!" << endl;
		return 0;
	}
	else
	{
		Q->front = (Q->front+1) % MAXSIZE;
		return Q->Data[Q->front];
	}
}

// 测试程序
int main(){
	Queue Q = CreateQueue();
	AddQ(Q,3);
	printf("3 in\n");
	AddQ(Q,5);
	printf("5 in\n");
	AddQ(Q,11);
	printf("11 out\n");
	printf("%d out\n",DeleteQ(Q));
	printf("%d out\n",DeleteQ(Q));
	printf("%d out\n",DeleteQ(Q));
	return 0;
}

2> 队列的链表储存[线性结构]

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct QNode *Queue;
struct Node{
	int Data;
	struct Node *Next;
};
struct QNode{
	struct Node *rear;
	struct Node *front;
};

Queue CreateQueue();
void AddQ(Queue Q, int Data);
int DeleteQ(Queue Q);
int IsEmpty(Queue Q);

Queue CreateQueue()
{
	Queue Q = new struct QNode;
	Q->front = NULL;
	Q->rear = NULL;
	return Q;
}

int IsEmpty(Queue Q)
{
	return Q->front == NULL;
}

void AddQ(Queue Q, int Data)
{
	struct Node *node;
	node = new struct Node;
	node->Data = Data;
	node->Next = NULL;
	if(Q->rear == NULL)
	{
		Q->rear = node;
		Q->front = node;
	}
	else
	{
		Q->rear->Next = node;
		Q->rear = node;
	}
}

int DeleteQ(Queue Q)
{
	struct Node *FrontCell;
	int FrontElem;
	if(IsEmpty(Q))
	{
		cout << "Queue is empty!" << endl;
		return 0;
	}
	else
	{
		FrontCell = Q->front;
		if(Q->front == Q->rear)  Q->front = Q->rear = NULL;
		else  Q->front = Q->front->Next;
		FrontElem = FrontCell->Data;
		delete FrontCell;
		return FrontElem;
	}
}

// 测试程序
int main()
{
	Queue Q;
	Q = CreateQueue();
	AddQ(Q,5);
	cout << Q->rear->Data << endl;
	AddQ(Q,4);
	cout << Q->rear->Data << endl;
	AddQ(Q,3);
	cout << Q->rear->Data << endl;
	cout << "-----------------------------------" << endl;
	printf("out:%d\n",DeleteQ(Q));
	printf("out:%d\n",DeleteQ(Q));
	printf("out:%d\n",DeleteQ(Q));
	printf("%d\n",DeleteQ(Q));
	return 0;
}