小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

顺序表详解（C语言版）_c语言顺序表

作者：小丑西瓜9 | 2024-04-13 13:13:42

踩

c语言顺序表

文章目录

前言
一、顺序表的定义
二、顺序表的存储结构
三、顺序表的常用操作
四、扩展
五、附录

前言

本文介绍了顺序表的定义和常见操作并使用C语言代码对其进行实现。

一、顺序表的定义

顺序表是线性表的顺序表示，即用一组地址连续的存储单元依次存储线性表的数据元素。

二、顺序表的存储结构

结构图
在这里插入图片描述
代码描述
为了使顺序表的空间分配尽可能不受限制，这里先让顺序表的初始化容量为8，当空间不足时再对容量进行扩展，每次容量的增量为3。

#define SEQLIST_INIT_SIZE 8  //初始化大小
#define INC_SIZE          3  //空间的增量

typedef int ElemType;        //元素类型

typedef struct SeqList
{
    ElemType *base;          //指向顺序表开辟的基准空间
    int       capacity;     //容量 
    int       size;         //表的长度(大小)
}SeqList;
1
2
3
4
5
6
7
8
9
10
11

三、顺序表的常用操作

1.初始化

//顺序表的初始化
void InitSeqList(SeqList *list)
{
    list->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
    assert(list->base != NULL);
    list->capacity = SEQLIST_INIT_SIZE;
    list->size = 0;
}
1
2
3
4
5
6
7
8

2.容量扩展

//空间不足，重新开辟
bool Inc(SeqList *list)
{
    ElemType *newbase = (ElemType*)realloc(list->base,sizeof(ElemType)*(list->capacity+INC_SIZE));
    //空间开辟是否失败？
    if(newbase == NULL)
    {
        printf("增配空间失败,内存不足.\n");
        return false;
    }
    list->base = newbase;
    list->capacity += INC_SIZE;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.尾插
在这里插入图片描述

//在顺序表尾部插入数据
void push_back(SeqList *list, ElemType x)
{
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能尾部插入数据.\n",x);
        return;
    }
    //数据尾插
    list->base[list->size] = x; //size的大小就是尾部插入时数组的下标
    list->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.头插
在这里插入图片描述

//在顺序表头部插入数据
void push_front(SeqList *list, ElemType x)
{
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能头部插入数据.\n",x);
        return;
    }
    //将顺序表数据后移
    for(int i=list->size; i>0; --i)
    {
        list->base[i] = list->base[i-1];
    }
    //数据头插
    list->base[0] = x;
    list->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.存储数据显示

//显示顺序表内的数据
void show_list(SeqList *list)
{
    for(int i=0; i<list->size; ++i)
    {
        printf("%d ",list->base[i]);
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9

6.尾删

//删除顺序表尾部数据
void pop_back(SeqList *list)
{
    //判断顺序表是否为空？
    if(list->size == 0)
    {
        printf("顺序表已空,不能尾部删除数据.\n");
        return;
    }
    //将size值减1，来达到删除的目的
    list->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

7.头删
在这里插入图片描述

//删除顺序表头部数据
void pop_front(SeqList *list)
{
    //判断表是否为空?
    if(list->size == 0)
    {
        printf("顺序表已空,不能尾部删除数据.\n");
        return;
    }
    //将顺序表中的数据前移一位(第一个数据除外)
    for(int i=0; i<list->size-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    //将size值减1，来达到删除的目的
    list->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.按位置插入数据
在这里插入图片描述

//按位置插入数据
void insert_pos(SeqList *list, int pos, ElemType x)
{
    //判断位置是否合法？
    if(pos<0 || pos>list->size)
    {
        printf("插入数据的位置非法，不能插入数据.\n");
        return;
    }
    
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能按位置插入数据.\n",x);
        return;
    }
    
    //将该位置及其之后的数据都向后移动一位
    for(int i=list->size; i>pos; --i)
    {
        list->base[i] = list->base[i-1];
    }
    //将数据插入
    list->base[pos] = x;
    list->size++;
}
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

9.查找数据
假定顺序表内的数据唯一

//查找数据
int find(SeqList *list, ElemType key)
{
    //遍历顺序表，查找数据
    for(int i=0; i<list->size; ++i)
    {
        if(list->base[i] == key)
            return i;  //找到数据返回
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11

10.求顺序表长度

//求顺序表的长度
int length(SeqList *list)
{
    return list->size;
}
1
2
3
4
5

11.按位置删除数据
在这里插入图片描述

//按位置删除数据
void delete_pos(SeqList *list, int pos)
{
    //判断位置是否合法？
    if(pos<0 || pos>=list->size)
    {
        printf("删除数据的位置非法,不能删除数据.\n");
        return;
    }
    //将该位置之后的数据都向前移动一位
    for(int i=pos; i<list->size-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    list->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

12.按值删除数据

//按值删除
void delete_val(SeqList *list, ElemType key)
{
    //查找值所在的位置
    int pos = find(list,key);
    //顺序表中是否存在该值？
    if(pos == -1)
    {
        printf("要删除的数据不存在.\n");
        return;
    }
    //存在该值就删除
    delete_pos(list,pos);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

13.排序

//顺序表的排序(冒泡排序 )
void sort(SeqList *list)
{
    //冒泡排序，每趟比较可以确定一个最大(最小)的数，所以需要size-1趟(最后一次自己跟自己比较不需要)
    for(int i=0; i<list->size-1; ++i) 
    {
        //每趟中需要比较size-i-1次(前面比较完的i个数不需要重复比较，最后一次自己跟自己比较不需要)
        for(int j=0; j<list->size-i-1; ++j) 
        {
            if(list->base[j] > list->base[j+1])
            {
                ElemType tmp = list->base[j];
                list->base[j] = list->base[j+1];
                list->base[j+1] = tmp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

14.逆置
在这里插入图片描述

//顺序表的逆置
void resver(SeqList *list)
{
    //判断是否需要进行逆置操作
    if(list->size==0 || list->size==1)
        return;
    //low低位指针，指向低位
    int low = 0;
    //hight高位指针,指向高位
    int high = list->size-1;
    //临时空间
    ElemType tmp;
    //当低位指针所指位置小于高位指针指向位置时，进行数据交换
    while(low < high)
    {
        tmp = list->base[low];
        list->base[low] = list->base[high];
        list->base[high] = tmp;

        low++;
        high--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

15.清空顺序表

//销毁顺序表
void destroy(SeqList *list)
{
    free(list->base);
    list->base = NULL;
    list->capacity = 0;
    list->size = 0;
}
1
2
3
4
5
6
7
8

四、扩展

将两个从小到大排序的有序表按照由小到大的顺序合并到另一个有序表中。

//将两个从小到大排序的有序表按照由小到大的顺序合并到另一个有序表中
void merge(SeqList *lt, SeqList *la, SeqList *lb)
{
    //构造存放有序表la和lb的有序表lt
    lt->capacity = la->size + lb->size;
    lt->base = (ElemType*)malloc(sizeof(ElemType)*lt->capacity);
    assert(lt->base != NULL);

    int ia = 0;
    int ib = 0;
    int ic = 0;
    //当有序表la和lb中的元素都还没比较完时，将它们相应下标下的元素进行比较，并将小的元素放入lt
    while(ia<la->size && ib<lb->size)
    {
        if(la->base[ia] < lb->base[ib])
            lt->base[ic++] = la->base[ia++];
        else
            lt->base[ic++] = lb->base[ib++];
    }
    //当只有有序表la中有元素时，将la中的剩余元素逐一放入lt
    while(ia < la->size)
    {
        lt->base[ic++] = la->base[ia++];
    }
    //当只有有序表lb中有元素时，将lb中的剩余元素逐一放入lt
    while(ib < lb->size)
    {
        lt->base[ic++] = lb->base[ib++];
    }
    //更新有序表lt的长度
    lt->size = la->size + lb->size;
}
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

五、附录

Main.cpp

#include"SeqList.h"


//顺序表常用操作测试
void main()
{
    SeqList mylist;
    InitSeqList(&mylist);

    ElemType Item;
    int pos;
    int select = 1;
    while(select)
    {
        printf("**************************************\n");
        printf("* [1]  push_back    [2]  push_fornt  *\n");
        printf("* [3]  show_list    [4]  pop_back    *\n");
        printf("* [5]  pop_front    [6]  insert_pos  *\n");
        printf("* [7]  find         [8]  lenght      *\n");
        printf("* [9]  delete_pos   [10]  delete_val *\n");
        printf("* [11] sort         [12]  resver     *\n");
        printf("* [13] clear        [14*]  destroy   *\n");
        printf("* [0]  quit_system                   *\n");
        printf("**************************************\n");
        printf("请选择:>");
        scanf("%d",&select);
        if(select == 0)
            break;

        switch(select)
        {
        case 1:
            printf("请输入要插入的数据(-1结束):>");
            while(scanf("%d",&Item),Item!=-1)
            {
                push_back(&mylist,Item);
            }
            break;
        case 2:
            printf("请输入要插入的数据(-1结束):>");
            while(scanf("%d",&Item),Item!=-1)
            {
                push_front(&mylist,Item);
            }
            break;
        case 3:
            show_list(&mylist);
            break;
        case 4:
            pop_back(&mylist);
            break;
        case 5:
            pop_front(&mylist);
            break;
        case 6:
            printf("请输入要插入数据:>");
            scanf("%d",&Item);
            printf("请输入要插入的位置:>");
            scanf("%d",&pos);
            insert_pos(&mylist,pos,Item);
            break;
        case 7:
            printf("请输入要查找的数据:>");
            scanf("%d",&Item);
            pos = find(&mylist,Item);
            if(pos == -1)
                printf("查找的数据%d在顺序表中不存在.\n",Item);
            else
                printf("查找的数据%d在顺序表中的%d下标位置.\n",Item,pos);
            break;
        case 8:
            printf("顺序表的长度为:> %d\n",length(&mylist));
            break;
        case 9:
            printf("请输入要删除数据的位置:>");
            scanf("%d",&pos);
            delete_pos(&mylist,pos);
            break;
        case 10:
            printf("请输入要删除的数据:>");
            scanf("%d",&Item);
            delete_val(&mylist,Item);
            break;
        case 11:
            sort(&mylist);
            break;
        case 12:
            resver(&mylist);
            break;
        case 13:
            clear(&mylist);
            break;
        //case 14:
            //destroy(&mylist);
        //    break;
        default:
            printf("输入的选择错误，请重新输入.\n");
            break;
        }
    }
    destroy(&mylist);
}


/*
//扩展测试
void main()
{
    SeqList mylist,youlist,list;
    InitSeqList(&mylist);
    InitSeqList(&youlist);

    push_back(&mylist,1);
    push_back(&mylist,3);
    push_back(&mylist,5);
    push_back(&mylist,7);
    push_back(&mylist,9);

    push_back(&youlist,2);
    push_back(&youlist,4);
    //push_back(&youlist,6);
    push_back(&youlist,8);
    //push_back(&youlist,10);

    merge(&list,&mylist,&youlist);
    show_list(&list);
}
*/
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

SeqList.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

#define SEQLIST_INIT_SIZE 8  //初始化大小
#define INC_SIZE          3  //空间的增量

typedef int ElemType;        //元素类型

typedef struct SeqList
{
    ElemType *base;          //指向顺序表开辟的基准空间
    int       capacity;     //容量 
    int       size;         //表的长度(大小)
}SeqList;

bool Inc(SeqList *list);
void InitSeqList(SeqList *list);
void push_back(SeqList *list, ElemType x);
void push_front(SeqList *list, ElemType x);
void show_list(SeqList *list);

void pop_back(SeqList *list);
void pop_front(SeqList *list);
void insert_pos(SeqList *list, int pos, ElemType x);
int  find(SeqList *list, ElemType key);
int length(SeqList *list);

void delete_pos(SeqList *list, int pos);
void delete_val(SeqList *list, ElemType key);

void sort(SeqList *list);
void resver(SeqList *list);
void clear(SeqList *list);
void destroy(SeqList *list);

void merge(SeqList *lt, SeqList *la, SeqList *lb);

#endif //__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
36
37
38
39
40
41
42

SeqList.cpp

#include"SeqList.h"

//空间不足，重新开辟
bool Inc(SeqList *list)
{
    ElemType *newbase = (ElemType*)realloc(list->base,sizeof(ElemType)*(list->capacity+INC_SIZE));
    //空间开辟是否失败？
    if(newbase == NULL)
    {
        printf("增配空间失败,内存不足.\n");
        return false;
    }
    list->base = newbase;
    list->capacity += INC_SIZE;
    return true;
}

//顺序表的初始化
void InitSeqList(SeqList *list)
{
    list->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
    assert(list->base != NULL);
    list->capacity = SEQLIST_INIT_SIZE;
    list->size = 0;
}

//在顺序表尾部插入数据
void push_back(SeqList *list, ElemType x)
{
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能尾部插入数据.\n",x);
        return;
    }
    //数据尾插
    list->base[list->size] = x; //size的大小就是尾部插入时数组的下标
    list->size++;
}

//在顺序表头部插入数据
void push_front(SeqList *list, ElemType x)
{
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能头部插入数据.\n",x);
        return;
    }
    //将顺序表数据后移
    for(int i=list->size; i>0; --i)
    {
        list->base[i] = list->base[i-1];
    }
    //数据头插
    list->base[0] = x;
    list->size++;
}

//显示顺序表内的数据
void show_list(SeqList *list)
{
    for(int i=0; i<list->size; ++i)
    {
        printf("%d ",list->base[i]);
    }
    printf("\n");
}

//删除顺序表尾部数据
void pop_back(SeqList *list)
{
    //判断顺序表是否为空？
    if(list->size == 0)
    {
        printf("顺序表已空,不能尾部删除数据.\n");
        return;
    }
    //将size值减1，来达到删除的目的
    list->size--;
}

//删除顺序表头部数据
void pop_front(SeqList *list)
{
    //判断表是否为空?
    if(list->size == 0)
    {
        printf("顺序表已空,不能尾部删除数据.\n");
        return;
    }
    //将顺序表中的数据前移一位(第一个数据除外)
    for(int i=0; i<list->size-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    //将size值减1，来达到删除的目的
    list->size--;
}

//按位置插入数据
void insert_pos(SeqList *list, int pos, ElemType x)
{
    //判断位置是否合法？
    if(pos<0 || pos>list->size)
    {
        printf("插入数据的位置非法，不能插入数据.\n");
        return;
    }
    
    //判断顺序表空间是否满且增加空间是否失败？
    if(list->size >= list->capacity && !Inc(list))
    {
        printf("顺序表空间已满，%d不能按位置插入数据.\n",x);
        return;
    }
    
    //将该位置及其之后的数据都向后移动一位
    for(int i=list->size; i>pos; --i)
    {
        list->base[i] = list->base[i-1];
    }
    //将数据插入
    list->base[pos] = x;
    list->size++;
}

//查找数据
int find(SeqList *list, ElemType key)
{
    //遍历顺序表，查找数据
    for(int i=0; i<list->size; ++i)
    {
        if(list->base[i] == key)
            return i;  //找到数据返回
    }
    return -1;
}

//求顺序表的长度
int length(SeqList *list)
{
    return list->size;
}

//按位置删除数据
void delete_pos(SeqList *list, int pos)
{
    //判断位置是否合法？
    if(pos<0 || pos>=list->size)
    {
        printf("删除数据的位置非法,不能删除数据.\n");
        return;
    }
    //将该位置之后的数据都向前移动一位
    for(int i=pos; i<list->size-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    list->size--;
}
//按值删除
void delete_val(SeqList *list, ElemType key)
{
    //查找值所在的位置
    int pos = find(list,key);
    //顺序表中是否存在该值？
    if(pos == -1)
    {
        printf("要删除的数据不存在.\n");
        return;
    }
    //存在该值就删除
    delete_pos(list,pos);
}

//顺序表的排序(冒泡排序 )
void sort(SeqList *list)
{
    //冒泡排序，每趟比较可以确定一个最大(最小)的数，所以需要size-1趟(最后一次自己跟自己比较不需要)
    for(int i=0; i<list->size-1; ++i) 
    {
        //每趟中需要比较size-i-1次(前面比较完的i个数不需要重复比较，最后一次自己跟自己比较不需要)
        for(int j=0; j<list->size-i-1; ++j) 
        {
            if(list->base[j] > list->base[j+1])
            {
                ElemType tmp = list->base[j];
                list->base[j] = list->base[j+1];
                list->base[j+1] = tmp;
            }
        }
    }
}

//顺序表的逆置
void resver(SeqList *list)
{
    //判断是否需要进行逆置操作
    if(list->size==0 || list->size==1)
        return;
    //low低位指针，指向低位
    int low = 0;
    //hight高位指针,指向高位
    int high = list->size-1;
    //临时空间
    ElemType tmp;
    //当低位指针所指位置小于高位指针指向位置时，进行数据交换
    while(low < high)
    {
        tmp = list->base[low];
        list->base[low] = list->base[high];
        list->base[high] = tmp;

        low++;
        high--;
    }
}

//清空顺序表
void clear(SeqList *list)
{
    list->size = 0;
}

//销毁顺序表
void destroy(SeqList *list)
{
    free(list->base);
    list->base = NULL;
    list->capacity = 0;
    list->size = 0;
}

//将两个从小到大排序的有序表按照由小到大的顺序合并到另一个有序表中
void merge(SeqList *lt, SeqList *la, SeqList *lb)
{
    //构造存放有序表la和lb的有序表lt
    lt->capacity = la->size + lb->size;
    lt->base = (ElemType*)malloc(sizeof(ElemType)*lt->capacity);
    assert(lt->base != NULL);

    int ia = 0;
    int ib = 0;
    int ic = 0;
    //当有序表la和lb中的元素都还没比较完时，将它们相应下标下的元素进行比较，并将小的元素放入lt
    while(ia<la->size && ib<lb->size)
    {
        if(la->base[ia] < lb->base[ib])
            lt->base[ic++] = la->base[ia++];
        else
            lt->base[ic++] = lb->base[ib++];
    }
    //当只有有序表la中有元素时，将la中的剩余元素逐一放入lt
    while(ia < la->size)
    {
        lt->base[ic++] = la->base[ia++];
    }
    //当只有有序表lb中有元素时，将lb中的剩余元素逐一放入lt
    while(ib < lb->size)
    {
        lt->base[ic++] = lb->base[ib++];
    }
    //更新有序表lt的长度
    lt->size = la->size + lb->size;
}
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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/416612