线性表（动态分配 逆置、排序）
结构：线性表动态分配顺序存储结构
目的：逆置
代码如下：
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
using namespace std;
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
return OVERFLOW;
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
Status ListCreate_Sq(SqList &L, int n)
{
int i;
srand(time(0));
for (i = 0; i < n; i++)
{
L.elem[i] = rand() % 90 + 10;
++L.length;
}
if (L.length == 0)
return ERROR;
return OK;
}
Status ListOutput_Sq(SqList L)
{
int i;
if (L.length == 0)
return ERROR;
for (i = 0; i < L.length; i++)
printf("%d ", L.elem[i]);
printf("\n");
return OK;
}
Status ListConverse_Sq(SqList &L)
{
ElemType temp;
int i;
if (L.length == 0)
return ERROR;
for (i = 0; i < L.length; i++)
{
temp = L.elem[i];
L.elem[i] = L.elem[L.length - 1 - i];
L.elem[L.length - 1 - i] = temp;
}
return OK;
}
void main()
{
SqList L;
printf("Initialize the sequential list!");
InitList_Sq(L);
if (L.length == 0)
printf("The sequential list is empty!\n");
printf("Create the sequential list!\n");
ListCreate_Sq(L, 5);
printf("Output all elements of the sequential list!\n");
ListOutput_Sq(L);
ListConverse_Sq(L);
printf("Output all converse elements of the sequential list\n");
ListOutput_Sq(L);
int j;cin >> j;
system("puase");
}
结构：带头结点线性链表
目的：逆置，不另设新空间
代码如下：
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
using namespace std;
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList &L, int n)
{
LinkList p, q;
int i;
L = (LinkList)malloc(sizeof(LNode));
q = L;
srand(time(0));
for (i = 1; i <= n; i++)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = rand() % 90 + 10;
q->next = p;
q = q->next;
}
q->next = NULL;
}
Status OutputList_L(LinkList L)
{
LinkList p = L->next;
if (p == NULL)
return ERROR;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
Status ListConverse_L(LinkList &L)
{
LinkList p, q;
p = L->next;
L->next=NULL;
while (p!=NULL)
{
q = p;
p = p->next;
q->next = L->next;
L->next=q;
}
cout << "OK" << endl;
return OK;
}
void main()
{
LinkList L;
printf("Create the linked list,");
CreateList_L(L, 5);
printf("Output all elements of the linked list!\n");
OutputList_L(L);
ListConverse_L(L);
printf("Output all converse elements of the linked list!\n");
OutputList_L(L);
int j;
cin >> j;
}
结构：线性表动态分配顺序存储结构
目的：实现顺序表中数据元素按值非递减排列
代码如下：
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
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
return OVERFLOW;
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
Status ListCreate_Sq(SqList &L, int n)
{
int i;
srand(time(0));
for (i = 0; i < n; i++)
{
L.elem[i] = rand() % 90 + 10;
++L.length;
}
if (L.length == 0)
return ERROR;
return OK;
}
Status ListOutput_Sq(SqList L)
{
int i;
if (L.length == 0)
return ERROR;
for (i = 0; i < L.length; i++)
printf("%d ", L.elem[i]);
printf("\n");
return OK;
}
int Partition(SqList &L, int low, int high)
{
int temp = L.elem[low];
int pivotkey = L.elem[low];
while (low < high)
{
while (low < high&&L.elem[high] >= pivotkey)
--high;
L.elem[low] = L.elem[high];
while (low < high&&L.elem[low] <= pivotkey)
++low;
L.elem[high] = L.elem[low];
}
L.elem[low] = temp;
return low;
}
void QSort(SqList &L, int low, int high)
{
if (low < high)
{
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, high);
}
}
void ListSort_Sq(SqList &L)
{
QSort(L, 0, L.length-1 );
}
void main()
{
SqList L;
InitList_Sq(L);
if (L.length == 0)
printf("The sequential list is empty!\n");
ListCreate_Sq(L, 5);
ListOutput_Sq(L);
ListSort_Sq(L);
printf("Sorted:\n");
ListOutput_Sq(L);
system("pause");
}
结构：带头结点的线性链表L
目的：数据元素按值非递减排列
代码如下：
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
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList &L, int n)
{
LinkList p, q;
int i;
L = (LinkList)malloc(sizeof(LNode));
q = L;
srand(time(0));
for (i = 1; i <= n; i++)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = rand() % 90 + 10;
q->next = p;
q = q->next;
}
q->next = NULL;
}
Status OutputList_L(LinkList L)
{
LinkList p = L->next;
if (p == NULL)
return ERROR;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
Status result(LinkList L, int n)
{
LinkList p = L;
for (int i = 0; i < n; i++)
{
p = p->next;
}
return p->data;
}
LinkList par(LinkList L, int n)
{
LinkList p = L;
for (int i = 0; i < n; i++)
{
p = p->next;
}
return p;
}
int Partition(LinkList &L, int low, int high)
{
int temp = result(L,low);
int pivotkey = result(L,low);
LinkList p, q;
while (low < high)
{
p = par(L, low);
q = par(L, high);
while (low < high && q->data >= pivotkey)
{
--high;
q = par(L, high);
}
p->data = q->data;
//(L + low)->data = (L + high)->data;
while (low < high && p->data <= pivotkey)
{
++low;
p = par(L, low);
}
q->data = p->data;
//(L + high)->data = (L + low)->data;
}
p = par(L, low);
p->data = temp;
//(L + low)->data = temp;
return low;
}
void QSort(LinkList &L, int low, int high)
{
if (low < high)
{
int pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc - 1);
QSort(L, pivotloc + 1, high);
}
}
void ListSort_Sq(LinkList &L)
{
LinkList p = L->next;
int i = 0;
while (p != NULL)
{
++i;
p = p->next;
}
QSort(L, 1, i);
}
void main()
{
LinkList L;
CreateList_L(L, 5);
OutputList_L(L);
ListSort_Sq(L);
printf("Sorted:");
OutputList_L(L);
system("pause");
}
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
