数据结构：顺序表的基本操作

线性表的顺序存储

顺序表的线性存储示意图

       假设线性表中有n个元素，每个元素占k个存储单元，第一个元素的地址为Loc(a1),则第i个元素的地址Loc(ai):

       Loc(ai) = Loc(a1) + (i-1) * k;
其中Loc(a1)称为基地址。

C语言定义线性表的顺序存储结构

#define ListSize 100 //线性表的最大长度 typedef int DataType; typedef struct { DataType data[ListSize]; //用数组存储线性表中的元素 DataType length; //顺序表中元素的个数 }SeqList, *PSeqList; 

       DataType是数据元素类型，可以根据需要定义，可以使用SeqList定义数据表类型变量，使用*PSeqList定义数据表指针变量;

顺序表的基本操作

(1) 顺序表的初始化

       顺序表的初始化就是把顺序表 初始化为空的顺序表；只需把顺序表的长度length置为0即可；

void InitList(PSeqList L) { if (L == NULL) { return; } L->length = 0; }

(2)求顺序表的长度

       顺序表的长度就是就顺序表中的元素的个数，由于在插入和删除操作中都有对数据表的长度进行修改，所以求表长只需返回length的值即可；

int LengthList(PSeqList L) { if (L == NULL) { return 0; } return L->length; }

(3)按序号查找
       查找顺序表中第i个元素的值（按序号查找），如果找到，将将该元素值赋给e。查找第i个元素的值时，首先要判断查找的序号是否合法，如果合法，返回第i个元素对应的值。

int GetData(PSeqList L, int i) { if (L->length < 1 || (L->length > LengthList(L))) { return 0; } //数据元素的序号从1开始，数组下表从0开始，第i个元素对应的数组下标为i-1; return L->data[i - 1]; }

(4)插入操作
       在数据表的第i个位置插入元素，在顺序表的第i个位置插入元素e，首先将顺序表第i个位置的元素依次向后移动一个位置，然后将元素e插入第i个位置，移动元素要从后往前移动元素，即：先移动最后一个元素，在移动倒数第二个元素，依次类推；插入元素之前要判断插入的位置是否合法，顺序表是否已满，在插入元素之后要将表长L->length++;

int InsList(PSeqList L, int i, DataType e) { //判断插入位置是否合法 if (i < 1 || L->length >(LengthList(L) + 1)) { printf("插入位置不合法!\n"); return 0; } //判断顺序表是否已满 else if (L->length >= ListSize) { printf("顺序表已满，不能插入！\n"); return 0; } else { for (k = i; k <= L->length; k--) { L->data[k + 1] = L->data[k]; } L->data[i - 1] = e; L->length++; //数据表的长度加1 return 1; } return 0; }

(5) 删除操作

       删除表中的第i个元素e，删除数据表中的第i个元素，需要将表中第i个元素之后的元素依次向前移动一位，将前面的元素覆盖掉。移动元素时要想将第i+1个元素移动到第i个位置，在将第i+2个元素移动i+1的位置，直到将最后一个元素移动到它的前一个位置，进行删除操作之前要判断顺序表是否为空，删除元素之后，将表长L->length--;

int DelList(PSeqList L, DataType i, DataType* e) { if (L->length < 1) { printf("表为空！\n"); return 0; } *e = L->data[i - 1]; for (k = i; k < L->length; k++) { L->data[k - 1] = L->data[k]; } L->length--; return *e; } 

(6)按内容查找

       查找数据元素e在表中的位置，可以从表头开始一直遍历表中元素，如果找到与要查找元素e相等的元素，则返回元素在表中的位置，数组下标从0开始，则元素在表中对应的位置序号值应为对应数组下标加1，没有找到则返回0；

int Locate(PSeqList L, DataType e) { for (k = 0; k < L->length; k++) { if (L->data[k] == e) { //k为e对应的数组下标，在表中对应序号应为k+1 return k + 1; } } return 0; } 

(7)头插

       头插，即在表头插入元素e，在表头插入元素，需要将表中的元素依次后移一位，然后将要插入的元素e赋给数字的首元素，执行插入操作后将表长L->length++;需要注意的是移动元素要从顺序表的最后一个元素开始移动，如果从第1个元素开始移动，会使得第1个元素的值覆盖第2个元素的值，然后把第二个元素后移则会使第2个元素的值(原来第1个元素值)覆盖第3个元素的值，依次类推，最后出插入元素外，其余元素值均为原顺序表中第一个元素的值。

void PushFront(PSeqList L, DataType e) { if (L->length == ListSize) { printf("顺序表已满，不能插入！\n"); } //将表中元素依次后移一位 for (k = L->length; k > 0; k--) { L->data[k] = L->data[k - 1]; } //插入元素 L->data[0] = e; L->length++; }

(8)头删

       删除顺序表中的第一个元素，只要将顺序表中的元素从第2个开始，依次向前移动1位，覆盖原来顺序表中元素对应位置的前一个值，在删除元素之前要判断顺序表是否为空，删除顺序表元素之后将顺序表长度L->length--;

void PopFront(PSeqList L) { if (EmptyList(L)) { printf("顺序表为空\n"); } for (k = 1; k <= L->length - 1; k++) { L->data[k - 1] = L->data[k]; } L->length--; }

(9)尾插

       在顺序表表尾插入元素e，L->data[L->length] = e;将元素e的值赋给顺序表中最后一个元素的下一个元素；尾插操作，需要判断顺序表是否已满，尾插后将顺序表长度L->length++;

void PushBack(PSeqList L, DataType e) { if (L->length == ListSize) { printf("顺序表已满，不能插入!\n"); } L->data[L->length] = e; L->length++; }

(10) 尾删

       删除表尾元素，只需将顺序表的长度减1,类似于出栈操作，栈顶指针top –。

void PopBack(PSeqList L) { if (EmptyList(L)) { printf("表为空！\n"); } L->length--; }

(11) 清空顺序表

       清空顺序表就是将表中的元素删除。删除表中的元素只需将表的长度置为0。

void ClearList(PSeqList L) { L->length = 0; }

(12)判断表是否为空

       如果顺序表的长度为0，则顺序表为空，返回1，否则，返回0；

int EmptyList(PSeqList L) { if (L->length == 0) { return 1; } return 0; }

(13)打印表中元素

       依次打印顺序表中的元素，如果顺序表为空则输出提示。

void PrintList(PSeqList L) { if (EmptyList(L)) { printf("表为空！\n"); return; } for (k = 0; k < L->length; k++) { printf("%-3d", L->data[k]); } printf("\n"); }

顺序表的基础操作完整代码

SeqList.h数据结构的定义和基本操作函数声明

#pragma once #define ListSize 100 //线性表的最大长度 typedef int DataType; typedef struct { DataType data[ListSize]; //用数组存储线性表中的元素 DataType length; //顺序表的长度 }SeqList, *PSeqList; void InitList(PSeqList L); //顺序表的初始化操作 int LengthList(PSeqList L); //求顺序表的长度 int GetData(PSeqList L, int i); //返回数据表中第i个元素的值 int InsList(PSeqList L, int i, DataType e); //在顺序表的第i个位置插入元素 int DelList(PSeqList L, DataType i, DataType* e); //删除顺序表L的第i个数据元素 int Locate(PSeqList L, DataType e); //查找数据元素e在表中的位置 void PushFront(PSeqList L, DataType e); //头插，在表头插入元素e void PopFront(PSeqList L); //头删,删除表中的第一个元素 void PushBack(PSeqList L, DataType e); //尾插，在表尾插入元素e void PopBack(PSeqList L); //尾删，删除表尾元素 void ClearList(PSeqList L); //清空顺序表 int EmptyList(PSeqList L); //判断顺序表是否为空 void PrintList(PSeqList L); //打印表中元素 

SeqList.c 函数的具体实现

#include 
       #include "SeqList.h" int k = 0; //全局变量，用于作部分操作的循环变量 //初始化顺序表 void InitList(PSeqList L) { if (L == NULL) { return; } L->length = 0; } //求顺序表的长度 int LengthList(PSeqList L) { if (L == NULL) { return 0; } return L->length; } //返回数据表中第i个元素的值 int GetData(PSeqList L, int i) { if (L->length < 1 || (L->length > LengthList(L))) { return 0; } //数据元素的序号从1开始，数组下表从0开始，第i个元素对应的数组下标为i-1; return L->data[i - 1]; } //在L中第i个位置，插入新的数据元素e int InsList(PSeqList L, int i, DataType e) { //判断插入位置是否合法 if (i < 1 || L->length >(LengthList(L) + 1)) { printf("插入位置不合法!\n"); return 0; } //判断顺序表是否已满 else if (L->length >= ListSize) { printf("顺序表已满，不能插入！\n"); return 0; } else { for (k = i; k <= L->length; k--) { L->data[k + 1] = L->data[k]; } L->data[i - 1] = e; L->length++; //数据表的长度加1 return 1; } return 0; } //删除L的第i个数据元素 int DelList(PSeqList L, DataType i, DataType* e) { if (L->length < 1) { printf("表为空！\n"); return 0; } *e = L->data[i - 1]; for (k = i; k < L->length; k++) { L->data[k - 1] = L->data[k]; } L->length--; return *e; } //查找e在表中的位置 int Locate(PSeqList L, DataType e) { for (k = 0; k < L->length; k++) { if (L->data[k] == e) { //k为e对应的数组下标，在表中对应序号应为k+1 return k + 1; } } return 0; } //头插，在表头插入元素e void PushFront(PSeqList L, DataType e) { if (L->length == ListSize) { printf("顺序表已满，不能插入！\n"); } //将表中元素依次后移一位 for (k = L->length; k > 0; k--) { L->data[k] = L->data[k - 1]; } //插入元素 L->data[0] = e; L->length++; } //头删,删除顺序表中的第一个元素，把顺序表中的元素依次往前移动一位 void PopFront(PSeqList L) { if (EmptyList(L)) { printf("顺序表为空，不能插入！\n"); } for (k = 1; k <= L->length - 1; k++) { L->data[k - 1] = L->data[k]; } L->length--; } //尾插 void PushBack(PSeqList L, DataType e) { if (L->length == ListSize) { printf("顺序表已满，不能插入!\n"); } L->data[L->length] = e; L->length++; } //尾删 void PopBack(PSeqList L) { if (EmptyList(L)) { printf("表为空！\n"); } L->length--; } //清空顺序表 void ClearList(PSeqList L) { L->length = 0; } //判断表是否为空 int EmptyList(PSeqList L) { if (L->length == 0) { return 1; } return 0; } //打印表中元素 void PrintList(PSeqList L) { if (EmptyList(L)) { printf("表为空！\n"); return; } for (k = 0; k < L->length; k++) { printf("%-3d", L->data[k]); } printf("\n"); }

mian.c函数的简单测试代码

#include 
     
       .h> 
      #include 
      
        .h> 
       #include "SeqList 
       .h" int 
       main() { SeqList L; DataType data; 
       //初始化顺序表 
       InitList(&L); 
       //在表中插入元素 
       printf("依次在表中插入元素(1,2,3,4,5)：\n"); 
       InsList(&L, 1, 1); 
       InsList(&L, 2, 2); 
       InsList(&L, 3, 3); 
       InsList(&L, 4, 4); 
       InsList(&L, 5, 5); 
       //打印表中元素 
       printf("表中元素有：\n"); 
       PrintList(&L); 
       //头插 
       printf("在表头依次插入元素，6,7:\n"); 
       PushFront(&L, 6); 
       PushFront(&L, 7); 
       //尾插 
       printf("在表尾依次插入元素，8,9:\n"); 
       PushBack(&L, 8); 
       PushBack(&L, 9); 
       printf("表中元素有：\n"); 
       PrintList(&L); 
       //头删 
       printf("头删一个元素:\n"); 
       PopFront(&L); 
       //尾删 
       printf("尾删一个元素:\n"); 
       PopBack(&L); 
       //输出表中第4个元素值 
       PrintList(&L); 
       printf("表中第4个元素值为：\n%d\n",GetData(&L, 4)); 
       //查找表中第 i个元素的位置 
       printf("元素2在表中的位置为：\n"); 
       printf("%d\n",Locate(&L, 2)); 
       //删除表中第2个元素对应的值 
       printf("删除表中第2个元素：%d\n", DelList(&L, 2, &data)); 
       printf("顺序表的长度为：%d\n", LengthList(&L)); 
       printf("表中元素为：\n"); 
       PrintList(&L); 
       //printf("删除的元素值为：%d\n", data); 
       //清空顺序表 
       ClearList(&L); 
       PrintList(&L); 
       system("pause"); return 0; }