顺序表的简单实现(C语言)_大家以宿舍成员,使用编程语言实现: 创建一个顺序表,顺序按照床位顺序,数据元素的

**

顺序表的简单实现(C语言)

**
顺序表的特点：
1、随机访问，可以在O(1)时间内找到第 i 个元素。
2、存储密度高，每个节点只存储数据元素。
3、拓展容量不方便（即使动态分配空间时间复杂度也比较高）。
4、插入、删除操作不方便，需要移动大量元素。

#顺序表的静态实现

#include <stdio.h>

#define Maxsize 10

typedef struct {
    int data[Maxsize];
    int length;
}SeqList;

// 初始化表
void InitList(SeqList *L){
    if(L == NULL){
        L->length = 0;
        }
}

// 创建表
void CreateList(SeqList *L, int n){
    L->length = n;
    int i = 0;
    for(i; i < n; i++){
//        scanf("%d", &L->data[i]);
        L->data[i] = i;
    }
}

// 销毁表
void DestoryList(SeqList *L){
    int i = 0;
    for(i; i < L->length; i++){
        L->data[i] = 0;
    }
    L->length = 0;
}

// 插入元素
void ListInsert(SeqList *L, int i, int e){
    if(L->length < Maxsize && i > 0 && i < Maxsize){
        int j;
        for(j = L->length; j > i; j--){    //插入位置以后的元素全部后移一位
            L->data[j] = L->data[j-1];
        }
        L->data[i] = e;
        L->length++;
    } else{
        printf("Fail");
    }
}

// 删除元素
void ListDelete(SeqList *L, int i, int *e){
    if(i > 0 && i < Maxsize){
        int  j;
        *e = L->data[i-1];
        for(j = i; j < Maxsize - i; j++){
            L->data[j-1] = L->data[j];
        }
        L->length--;
        printf("已删除第%d位,值为%d的元素\n", i, *e);
    } else
        printf("Delete location does not exist!\n");
}

// 按值查找元素
void LocateElem(SeqList L, int e){
    int i, j = 0;
    for(i; i < L.length; i++){
        j++;
        if(e == L.data[j])
            printf("在 %d 位", j);
    }
    printf("\n");
}

// 按位查找元素
void GetElem(SeqList L, int i){
    printf("在第%d位的元素,其值为%d\n", i, L.data[i-1]);
}

// 输出表
void PrintList(SeqList L){
    if(&L != NULL){
        int i;
        for(i = 0; i < L.length; i++){
            printf("%d ", L.data[i]);
        }
        printf("\n");
    }
}

int main() {
    int sys, e;
    SeqList L;
    InitList(&L);
    printf("sys num: 0.Exit; 1.CreateList; 2.ListInsert; 3.ListDelete; 4.LocateElem; 5.GetElem; 6.DestoryList\n");

    while (1){
        scanf("%d", &sys);
        if(sys == 0) break;
        switch (sys) {
            case 1:     // 初化
                CreateList(&L, 7);
                PrintList(L);
                break;
            case 2:     // 插入
                ListInsert(&L, 5, 10);
                PrintList(L);
                break;
            case 3:     // 删除
                
                ListDelete(&L, 3, &e);
                PrintList(L);
                break;
            case 4:     // 按值查找
                LocateElem(L, 10);
                break;
            case 5:     // 按位查找
                GetElem(L, 3);
                break;
            case 6:     // 销毁表
                DestoryList(&L);
                PrintList(L);
                break;
            default:
                printf("Fail");
        }
    }
    return 0;
}
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

静态顺序表在声明时就已经决定好最大容量无法改变。但是通过malloc方法可以实现动态申请空间。

顺序表的动态实现

#include<stdio.h>
#include<stdlib.h>  // 该库含有动态空间申请malloc方法

#define InitSize 10 // 顺序表初始长度


typedef int ElemType;
typedef struct {
    ElemType *data;  // 指示动态分配数组的指针
    int MaxSize;     // 最大容量
    int length;      // 当前长度
}SqList;

// 顺序表的初始化
void InitList(SqList *L){
    if(L == NULL){
        L->data = (ElemType *)malloc(InitSize*sizeof(ElemType));    // 申请InitSize个可以存放ElemType类型的空间
        L->length = 0;  // 设置初始长度为零，防止脏数据
        L->MaxSize = InitSize;
    }
    
}

// 顺序表空间的扩容
void IncreaseSize(SqList *L, int len){
    ElemType *p = L->data;              //申请一个空间暂时存放原来的顺序表
    L->data = (ElemType *)malloc((L->MaxSize + len)*sizeof(ElemType));    // 申请比原来多len长度的新空间
    int i;
    for(i = 0; i <= L->length; i++){    // 将原来顺序表的数据复制到新空间
        L->data[i] = p[i];
    }
    L->MaxSize = L->MaxSize + len;
    free(p);    // 释放暂存空间
}

// 创建表
void CreateList(SqList *L, int len){
    int i;
    L->length = len;
    for(i = 0; i < len ; i++){
        scanf("%d", &L->data[i]);   // 数据存入
    }
    
}

// 销毁表
void DestoryList(SqList *L){
    if(L->data == NULL){    // 非空判断
        printf("SqList does not exist\n");
        return;
    }
    free(L->data);
    free(L);
    printf("DestoryList successded!\n");
}

// 清空表,保留表结构
void ClearList(SqList *L){
    L->length = 0;
    printf("ClearList successded!\n");
}

// 插入元素
void ListInsert(SqList *L, int pos, int elem){     // pos为插入位置
    if(pos >= L->length+1 && pos <= 1){            // 插入位置不能大于顺序表的当前长度+1
        printf("Invalid insertion position!\n");
        return;
    }else if (L->length >= L->MaxSize)
    {
        printf("The SqList has reached the maximum value, please expand it first!\n");
        return;
    }else {
        int i;
        L->length++;
        for(i = L->length; i >= pos; i--){
            L->data[i] = L->data[i-1];             // 从最后一个到插入位置的元素都后移一位
        }     
        L->data[pos-1] = elem;
    }
}

// 删除元素
void ListDelete(SqList *L, int pos, int *elem){
    if(pos >= L->length+1 && pos <= 1){    // 删除位置合法性判断
        printf("It is illegal to delete the location!\n");
    }else{
        elem = L->data[pos-1];
    int i;
    for(i = L->length; i <= pos; i--){     // 从删除位置后每个元素位置前移
        L->data[i] = L->data[i-1];
    }
    L->length--;
    }
}

// 按值查找
void LocateElem(SqList L, int elem){
    int i;
    for(i = 0; i < L.length; i++){
        if( L.data[i] == elem){  // 只能判断第一个值相同的,如果写成 elem == L.data[i] 只能查找顺序表中值相等的第一个
            printf("Element with value %d is at position %d\n", elem, i+1);     // 此处不能使用i++,会改变i的值
        }
    }
}

// 按位查找
void GetElem(SqList L, int pos){
    if(pos >= L.length+1 && pos <= 1){    // 位置合法性判断
        printf("It is illegal to delete the location!\n");
    }else{
        printf("The value of the element at position %d is %d .\n", pos, L.data[pos-1]);
    }
}

// 输出表
void PrintList(SqList L){
    if(L.data == NULL){     // 先判空
        printf("SqList does not exist!\n");
    }else{
        int i;
        for(i = 0; i < L.length; i++){
            printf("%d ", L.data[i]);
        }
        printf("\n");
    }
}

int main(){
    SqList L;       // 声明一个顺序表
    int elem;       // 元素
    int pos;        // 位置
    int len;        // 顺序表大小
    int status;     // 操作码
    InitList(&L);   // 初始化顺序表
    printf("Please enter a status code:\n1.IncreaseSize     2.CreateList    3.ListInsert\n");
    printf("4.ListDelete    5.LocateElem    6.GetElem\n7.DestoryList    8.PrintList     9.ClearList\n0.Exit\n");
    while(1){
        scanf("%d", &status);
        if(status == 0) break;
        switch (status){
            case 1: 
                printf("Please enter the length of the SqList you want to increate!\n");
                scanf("%d", &len);
                IncreaseSize(&L, len); 
                break;
            case 2: 
                printf("Please enter the length of the SqList you want to create!\n");
                scanf("%d", &len);     // 输入想创建的表大小
                CreateList(&L, len); 
                PrintList(L);
                break;
            case 3:
                printf("Please enter the element position and value to insert!\n");
                scanf("%d%d", &pos, &elem);
                ListInsert(&L, pos, elem); 
                PrintList(L);
                break;
            case 4:
                printf("Please enter the element position to delete!\n");
                scanf("%d", &pos);
                ListDelete(&L, pos, &elem); 
                PrintList(L);
                break;
            case 5:
                printf("Please enter the element value to find!\n");
                scanf("%d", &elem);
                LocateElem(L, elem);
                break;
            case 6:
                printf("Please enter the element position to find!\n");
                scanf("%d", &pos);
                GetElem(L, pos);
                break;
            case 7: DestoryList(&L); break;   
            case 8: PrintList(L); break; 
            case 9: ClearList(&L); break;
            default: 
                printf("Error!\n");
                break;
        }
    }                                                         
}
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
176
177
178
179
180
181
182

运行展示