C语言实现静态顺序表的实例详解

时间:2021-07-17 07:20:13

C语言实现静态顺序表的实例详解

线性表

定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识。只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作。

接下来看看静态的顺序表,直接上代码:

SeqList.h

?
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
#define _CRT_SECURE_NO_WARNINGS 1
 
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
 
#define MAX 10
 
typedef int DataType;
 
typedef struct SeqList
{
 DataType data[MAX];
 int sz;
}SeqList,*pSeqList;
 
void InitSeqList(pSeqList ps);
void PushBack(pSeqList ps, DataType d);
void PopBack(pSeqList ps);
void PushFront(pSeqList ps, DataType d);
void PopFront(pSeqList ps);
void Display(const pSeqList ps);
int Find(pSeqList ps, DataType d);
void Insert(pSeqList ps, DataType d, int pos);
void Remove(pSeqList ps, DataType d);
void RemoveAll(pSeqList ps, DataType d);
void Reverse(pSeqList ps);
void Sort(pSeqList ps);
int BinarySearch(pSeqList ps, DataType d);
 
#endif//__SEQLIST_H__

SeqList.c

?
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SeqList.h"
 
void InitSeqList(pSeqList ps)
{
 assert(ps);
 ps->sz = 0;
 memset(ps->data, 0, sizeof(DataType)*MAX);
}
void PushBack(pSeqList ps, DataType d)
{
 assert(ps);
 if (ps->sz == MAX)
 {
  return;
 }
 ps->data[ps->sz] = d;
 ps->sz++;
}
void PopBack(pSeqList ps)
{
 assert(ps);
 if (ps->sz == 0)
 {
  return;
 }
 ps->sz--;
}
void PushFront(pSeqList ps, DataType d)
{
 int i = 0;
 assert(ps);
 for (i = ps->sz; i >= 1; i--)
 {
  ps->data[i] = ps->data[i - 1];
 }
 ps->data[0] = d;
 ps->sz++;
}
void PopFront(pSeqList ps)
{
 int i = 0;
 assert(ps);
 for (i = 0; i < ps->sz; i++)
 {
  ps->data[i] = ps->data[i + 1];
 }
 ps->sz--;
}
void Display(const pSeqList ps)
{
 int i = 0;
 assert(ps);
 for (i = 0; i < ps->sz; i++)
 {
  printf("%d ", ps->data[i]);
 }
 printf("\n");
}
int Find(pSeqList ps, DataType d)
{
 int i = 0;
 assert(ps);
 for (i = 0; i < ps->sz; i++)
 {
  if (ps->data[i] == d)
  {
   return i;
  }
 }
 return -1;
}
void Insert(pSeqList ps, DataType d, int pos)
{
 int i = 0;
 assert(ps);
 if (ps->sz == MAX)
 {
  return;
 }
 //方式一
 //for (i = ps->sz - 1; i >= pos; i--)
 //{
 // ps->data[i + 1] = ps->data[i];
 //}
 //方式二
 memmove(ps->data + pos + 1, ps->data + pos, sizeof(DataType)*(ps->sz - pos));
 ps->data[pos] = d;
 ps->sz++;
}
void Remove(pSeqList ps, DataType d)
{
 int i = 0;
 int pos = 0;
 assert(ps);
 pos = Find(ps, d);
 if (pos != -1)
 {
  for (i = pos; i < ps->sz; i++)
  {
   ps->data[i] = ps->data[i + 1];
  }
  ps->sz--;
 }
}
void RemoveAll(pSeqList ps, DataType d)
{
 int i = 0;
 int pos = 0;
 assert(ps);
 pos = Find(ps, d);
 while ((pos = Find(ps, d)) != -1)
 {
  for (i = pos; i < ps->sz; i++)
  {
   ps->data[i] = ps->data[i + 1];
  }
  ps->sz--;
 }
}
void Reverse(pSeqList ps)
{
 int left = 0;
 int right = ps->sz - 1;
 assert(ps);
 while (left < right)
 {
  DataType tmp = ps->data[right];
  ps->data[right] = ps->data[left];
  ps->data[left] = tmp;
  left++;
  right--;
 }
}
void Sort(pSeqList ps)
{
 int i = 0;
 int j = 0;
 assert(ps);
 for (i = 0; i < ps->sz; i++)
 {
  for (j = 0; j < ps->sz - i - 1; j++)
  {
   if (ps->data[j]>ps->data[j + 1])
   {
    DataType tmp = ps->data[j];
    ps->data[j] = ps->data[j + 1];
    ps->data[j + 1] = tmp;
   }
  }
 }
}
int BinarySearch(pSeqList ps, DataType d)
{
 int left = 0;
 int right = ps->sz - 1;
 while (left <= right)
 {
  int mid = left - ((left - right) >> 1);
  if (d > ps->data[mid])
  {
   left = mid + 1;
  }
  else if (d < ps->data[mid])
  {
   right = mid - 1;
  }
  else
  {
   return mid;
  }
 }
 return -1;
}

test.c

?
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 _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
 
void test1()
{
 SeqList list;
 InitSeqList(&list);
 PushBack(&list, 1);
 PushBack(&list, 2);
 PushBack(&list, 3);
 PushBack(&list, 4);
 Display(&list);
 PopBack(&list);
 Display(&list);
 PopBack(&list);
 Display(&list);
 PopBack(&list);
 Display(&list);
 PopBack(&list);
 Display(&list);
}
 
void test2()
{
 int pos = 0;
 SeqList list;
 InitSeqList(&list);
 PushFront(&list, 1);
 PushFront(&list, 2);
 PushFront(&list, 3);
 PushFront(&list, 2);
 PushFront(&list, 4);
 PushFront(&list, 2);
 Display(&list);
 pos = Find(&list, 3);
 printf("%d\n", list.data[pos]);
 PopFront(&list);
 Display(&list);
 PopFront(&list);
 Display(&list);
 PopFront(&list);
 Display(&list);
 PopFront(&list);
 Display(&list);
}
void test3()
{
 int pos = 0;
 SeqList list;
 InitSeqList(&list);
 PushFront(&list, 1);
 PushFront(&list, 2);
 PushFront(&list, 3);
 PushFront(&list, 2);
 PushFront(&list, 4);
 PushFront(&list, 2);
 Display(&list);
 Insert(&list, 6, 2);
 Display(&list);
 Remove(&list, 1);
 Display(&list);
 RemoveAll(&list, 2);
 Display(&list);
}
void test4()
{
 int pos = 0;
 SeqList list;
 InitSeqList(&list);
 PushFront(&list, 1);
 PushFront(&list, 2);
 PushFront(&list, 3);
 PushFront(&list, 2);
 PushFront(&list, 4);
 Display(&list);
 Reverse(&list);
 Display(&list);
 Sort(&list);
 Display(&list);
 pos = BinarySearch(&list, 3);
 printf("%d\n", list.data[pos]);
}
int main()
{
 test4();
 system("pause");
 return 0;
}

动态顺序表的实现:http://www.zzvips.com/article/166552.html

 以上使用C语言动态顺序表的实现如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/SuLiJuan66/article/details/46685779