1 顺序表 ADT
+ Status InitList(SeqList &L) 初始化顺序表
+ void printList(SeqList L) 遍历顺序表
+ int ListLength(SeqList L) 获得表长
+ Status GetElement(SeqList L, int i, ElementType &e) (按位)取值
+ int LocateElement(SeqList L, ElementType e) (按值)查找
+ Status ListInsert(SeqList &L, int i, ElementType e) (按位)插入
+ Status ListDelete(SeqList &L, int i) (按位)删除
2 编程实现
2.1 定义基础数据类型
ElementType (数据元素类型/结构体)
struct ElementType {
char data; // char -> ElementType
bool operator==(const ElementType b) const{ // 重载结构体 ElementType 的运算符
return this->data == b.data;
}
bool operator!=(const ElementType b) const{
return this->data != b.data;
}
};
Status (状态/枚举类型)
enum Status { ERROR, OK, OVERFLOW };
SeqList (顺序表/结构体)
#define MAXSIZE_SEQLIST 100
typedef struct{
ElementType *elements; // 存储空间的基地址
int length; // 当前长度
} SeqList; // 线性表之顺序表
2.2 初始化顺序表
Status InitList(SeqList &L)
Status InitList(SeqList &L){
L.elements = new ElementType[MAXSIZE_SEQLIST]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elements){
exit(OVERFLOW); // 存储分配失败 -> (异常)退出
}
L.length = 0;
return OK;
}
2.3 遍历顺序表
void printList(SeqList L)
void printList(SeqList L){
printf("[SeqList.h#printList] L.length: %d\n", L.length);
printf("[SeqList.h#printList] L.elements: \t");
for(int i=0; i< L.length; i++){
printf("%c \t", L.elements[i]);
}
printf("\n");
}
2.4 获得表长
int ListLength(SeqList L)
int ListLength(SeqList L){
return L.length;
}
2.5 (按位)取值
Status GetElement(SeqList L, int i, ElementType &e)
Status GetElement(SeqList L, int i, ElementType &e){
if(i<1 || i>L.length){ // 判断i值是否合理，若不合理：返回 ERROR
return ERROR;
}
e = L.elements[ i-1 ]; // 赋值; elements[i-1] 单元存储的第 i 个数据元素
return OK;
}
2.6 (按值)查找
int LocateElement(SeqList L, ElementType e)
int LocateElement(SeqList L, ElementType e){
for(int i=0; i<L.length; i++){
if(L.elements[i] == e){ //(前提：已重载结构体 ElementType 的'=='运算符)
return i+1;
}
}
return -1;
}
2.7 (按位)插入
Status ListInsert(SeqList &L, int i, ElementType e)
Status ListInsert(SeqList &L, int i, ElementType e){
if(i<1 || i>L.length+1){ // i 值不合法 (易错： 忘记 +1)
return ERROR;
}
if(L.length == MAXSIZE_SEQLIST){ // 当前存储空间已满
return ERROR;
}
for(int j=L.length; j>=i; j--){ // 插入位置 及之后的元素后移
L.elements[j] = L.elements[j-1];
}
L.elements[i-1] = e; //将新元素 e 放入 第 i 个位置
L.length += 1; //表长 + 1
return OK;
}
2.8 (按位)删除
Status ListDelete(SeqList &L, int i)
Status ListDelete(SeqList &L, int i){
if(i<1 || i>L.length){ // i 值不合法
return ERROR;
}
for(int j=i-1; j<=L.length-1; j++){ // 删除位置 及之后的元素前移
L.elements[j] = L.elements[j+1];
}
L.length -= 1;
return OK;
}
3 测试运行(Main.cpp)
#include <stdio.h>
//#include <iostream.h>
#include <iostream>
using namespace std; #include "base.h"
#include "SeqList.h" int main(){
SeqList L; // 顺序表 InitList(L); ElementType e;
e.data = 'F';
ListInsert(L, 1, e);
printList(L); e.data = 'G';
ListInsert(L, 1, e);
printList(L); Status status = GetElement(L, 1, e);
printf("status: %d\n", status); status = ListDelete(L, 1);
printList(L); printElementType(e); return 0;
}
运行结果
[SeqList.h#printList] L.length: 1
[SeqList.h#printList] L.elements: F
[SeqList.h#printList] L.length: 2
[SeqList.h#printList] L.elements: G F
status: 1
[SeqList.h#printList] L.length: 1
[SeqList.h#printList] L.elements: F
[base.h#printElementType] ElementType.data: G
4 参考资料
1 《数据结构(C语言版 第二版)》.严蔚敏.李冬梅.吴伟民