C语言实现数据结构顺序表

1.顺序表的定义

线性表可分为两种存储结构，一种是顺序存储结构，一种是链式存储结构。一般来说，顺序表是一个相同数据类型的集合，且内存地址一定相邻。在C语言中，一般使用数组实现。
2.顺序表的存储结构

使用结构体来表示顺序表，在结构体中，有两个成员，一个用来存储数据，一个用来表示顺序表的长度

1. typedef struct {
2.         Element data[MAXSIZE];
3.         int length;
4. }List;

复制代码

3.顺序表的抽象数据结构

​        抽象数据结构可以表示它的元素以及对应的一些操作

1. ADT 线性表（List）
2. Data
3.         线性表的数据对象集合为{a_1,a_2,.....,a_n},每个元素的类型均为DataType。其中，除了第一个元素a_1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a_n外，每一个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系
4. Operation
5.         IniList(*L):初始化操作，建立一个空的线性表L。
6.         ListEmpty(L):若线性表为空，返回true，反之返回false。
7.         ClearList(*L):将线性表清空。
8.         GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e。
9.         LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素表中序号表示成功；否则，返回0表示失败。
10.         ListInsert(*L,i,e):在线性表L中的第i个位置插入新元素e。
11.         ListDelete(*L,i,*e):删除线性表L中的第i个位置元素，并用e返回其值。
12.         ListLength(L):返回线性表L的元素个数
13. endADT

复制代码

4 顺序表的一些操作

这里只简单介绍几种基本操作，如初始化，判断是否为空等等。
4.1顺序表初始化

由于结构定义存储元素的地方是一个静态数组，该数组会在结构声明时由系统自动分配内存空间，所以只需初始化它的长度即可。后面将使用长度来访问该数组。

1. //初始化顺序表
2. void InitList(List *l){
3.         l->length=0;
4. }

复制代码

4.2判断是否为空

当它长度为0时为空表，反之不为空表

1. //判断表是否为空
2. bool ListEmpty(List l){
3.         if(l.length==0)
4.                 return true;
5.         else
6.                 return false;
7. }

复制代码

4.3返回顺序表的长度

长度由结构中length表示，直接返回即可。若要严谨一点可在前面加上判断if(l==NULL),若它没有初始化则返回错误，但一般我们使用这些函数的前提就是要初始化表

1. //获取表的长度
2. int ListLength(List l){
3.         return l.length;
4. }

复制代码

5.顺序表的插入


该操作将元素e插入到表L的第i个位置上，其中1=i-1;j--){                l->data[j+1]=l->data[j];        }                l->data[i-1] = x;        l->length++;        return l;}[/code]6. 顺序表的删除


​        将表的第i个位置元素删除，并用参数e带回被删除元素。1data[j+1]; //前移        }        l->length--;        return *e;}[/code]​        与插入相反的时，删除时需要从第i个位置上往前移动，直接覆盖掉被删除的元素。
7. 顺序表的全部实现

​        我们将结构、函数声明定义在一个头文件里，并用一个c源文件取实现它。最后在main.c里测试。
1. List.h

[code]#ifndef LIST_H#define LIST_H#include#include#include#define MAXSIZE 50typedef int Element;typedef struct {
        Element data[MAXSIZE];
        int length;
}List;#endif//初始化顺序表void InitList(List *l);//使用数组初始化顺序表,n表示数组的长度List* arrInitList(List *l,int *arr,int n);//判断表是否为空bool ListEmpty(List l);//获取表的长度int ListLength(List l);//清空顺序表void ClearList(List *l);/*在顺序表第i个位置插入元素x        1length-1; j>=i-1;j--){                l->data[j+1]=l->data[j];        }                l->data[i-1] = x;        l->length++;        return l;}/*删除顺序表第i个位置的元素，用e带回1data[i-1]; //记录被删除的元素元素        /*        从第i个位置开始，将第i+1个元素往前覆盖。最后长度-1        */        for(int j=i-1;jlength;j++){                l->data[j]=l->data[j+1]; //前移        }        l->length--;        return *e;}//查看所有元素void showList(List l){        if(ListEmpty(l)){                exit(1); //退出并返回错误代码        }                printf("[");        for(int i=0;i