线性表

线性表的顺序表示和实现

1. 初始化

   步骤：

   1. 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
   2. 将表的当前长度设为0

   代码：

   1 2 3 4 5 6 7 8 9 10 11

   //初始化 const int MAXSIZE = 100; bool InitList(SqList L) { L.elem = new ElemType[MAXSIZE]; if(!L.elem){ return 0; } L.length = 0; return true; }

2. 取值

   步骤:

   1. 判断指定的位置序号i的值是否合理$$（1<=i<=L.length）$$，若不合理，返回false
   2. 若值合理，则将第i个数据元素L.elem[i-1]赋值参数e，通过e返回第i个数据元素的传值

   1 2 3 4 5 6 7 8 9

   //取值 int GetElem(SqList L,int i,ElemType e) { if(i<1 || i>L.length){ return -1; } e=L.elem[i-1]; return e; }

3. 查找

   步骤：

   1. 从第一个元素起，依次将其值和e比较，若找到和e值相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1
   2. 若查遍整个顺序表都没有找到，则查找失败，返回0

   1 2 3 4 5 6 7 8 9 10 11 12

   //查找 int LocateElem(SqList L,ElemType e) { for(int i=0;i<L.length;i++){ if(e==L.elem[i]){ return i+1; }else{ return 0; } } return 0; }

4. 插入

   1. 判断插入位置i是否合法(i值的合法范围为1<=i<=n+1)，若不合法返回FALSE
   2. 判断顺序表的存储空间是否已满，若满了，返回FALSE
   3. 将第n个至第i个元素依次向后移动一个位置，空出第i个位置(i=n+1时无序移动)
   4. 将要插入的元素e放入第i个元素
   5. 表长加一

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   //插入 bool ListInsert(SqList &L,int i,ElemType e) { if(i<1 || i>L.length+1) { return false; } if(L.length==MAXSIZE){//判断顺序表的存储空间是否已满 return false; } for(int j=L.length-1;j>=i-1;j--){ L.elem[j+1]=L.elem[j]; } L.elem[i-1] = e; ++L.length; return true; }

5. 删除

   步骤:

   1. 判断删除位置i是否合法(合法的值为1<=i<=n)，若不合法则返回FALSE
   2. 将第i+1个元素至第n个元素依次向前移动一个位置(i=n时无需移动)
   3. 表长减一

   1 2 3 4 5 6 7 8 9 10 11 12

   //删除 bool ListDelete(SqList &L,int i) { if(i>L.length && i<1){ return false; } for(int j=i;j<=L.length-1;j++){ L.elem[j-1]=L.elem[j]; } --L.length; return true; }

测试：

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

#include<iostream>
using namespace std;

typedef int ElemType;
typedef struct {
	ElemType *elem;
	int length;
} SqList;

//基本操作的实现

//初始化
const int MAXSIZE = 100;
bool InitList(SqList &L, int length) {
	L.elem = new ElemType[MAXSIZE];
	if (!L.elem) {
		return 0;
	}
	L.length = length;
	return true;
}

//赋值
int PushElem(SqList &L, int i, ElemType e) {
	if (i < 1 || i > L.length) {
		return -1;
	}
	L.elem[i - 1] = e;
	return 0;
}

//取值
int GetElem(SqList &L, int i, ElemType &e) {
	if (i < 1 || i > L.length) {
		return -1;
	}
	e = L.elem[i - 1];
	return e;
}

//查找
void LocateElem(SqList &L, ElemType e) {
	for (int i = 0; i < L.length; i++) {
		if (e == L.elem[i]) {
			cout<<"位置为"<<i + 1<<endl;
		}
	}
}

//插入
bool ListInsert(SqList &L, int i, ElemType e) {
	if (i < 1 || i > L.length + 1) {
		return false;
	}
	if (L.length == MAXSIZE) { //判断顺序表的存储空间是否已满
		return false;
	}
	for (int j = L.length - 1; j >= i - 1; j--) {
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i - 1] = e;
	++L.length;
	return true;
}

//删除
bool ListDelete(SqList &L, int i) {
	if (i > L.length && i < 1) {
		return false;
	}
	for (int j = i; j <= L.length - 1; j++) {
		L.elem[j - 1] = L.elem[j];
	}
	--L.length;
	return true;
}

//打印
void PrintList(SqList &L) {
	for (int i = 0; i < L.length; i++) {
		cout << "第" << i + 1 << "个元素：" << L.elem[i] << endl;
	}
}

int main() {
	SqList L;
	InitList(L, 4);
	PushElem(L, 1, 1);
	PushElem(L, 2, 2);
	PushElem(L, 3, 3);
	PushElem(L, 4, 4);
	LocateElem(L, 4);
	PrintList(L);
	cout<<endl;
	
	//在第三个位置，插入元素5
	ListInsert(L, 3, 5);
	PrintList(L);
	cout<<endl;
	
	ListDelete(L, 1);
	PrintList(L);
	cout<<endl;
	
	return 0;
}

运行：

线性表的链式表示和实现

单链表

1. 初始化

   1. 生成新节点作为头结点，用头指针L指向头结点
   2. 头结点的指针域置空

2. 取值

   1. 用指针p指向首元结点，用j做计数器初值赋为1
   2. 从首元结点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为空(NULL)，并且没有到达序号为i的节点，则循环执行以下操作：
      • p指向下一节点
      • 计数器j加一
   3. 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回ERROR；否则取值成功，此时j=i时，p所指的节点就是要找的第i个节点，用参数e保存当前节点的数据域，返回OK

3. 查找

   1. 用指针p指向首元结点
   2. 从首元结点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一节点
   3. 返回p。若查找成功，p此时指向节点的地址值；若查找失败，则p的值为NULL

4. 插入

   1. 查找节点a_i-1并由指针p指向该节点
   2. 生成一个新节点*s
   3. 将新节点*s的数据域置为e
   4. 将新节点*s的指针域指向节点a_i
   5. 将节点*p的指针域指向新节点*s

5. 删除

   1. 查找节点a_i-1并由指针p指向该节点
   2. 临时保存待删除的节点a_i的地址在q中，以备释放
   3. 将节点*p的指针域指向a_i的直接后继节点
   4. 释放节点a_i的空间

6. 创建单链表

   • 前插法
   • 后插法

循环链表

双向链表

顺序表和链表的比较

空间性能

时间性能