数据结构C-数组-顺序表（三）
2019-01-18 本文已影响0人
江海大初学者
数据结构中有一种结构叫顺序结构，这种结构的数据在内存中是连续的。
图1 顺序表的内存示意图
其实这种结构就是数组。我们都知道，当你创建一个数组的时候，那么计算机就会在内存中开辟一个连续的空间。比如，int a[5]，那么计算机就会在内存中开辟一个5个连续的空间用来存储数据。
数组的特点就是长度固定，可以通过索性快速搜索。但是数组也有缺点，比如我们定义的数组长度为5，那么我们就无法为他添加第6个数据，所以为了解决这个问题，我们要重新开辟一个具有6个长度的数组。所以我们需要对数组重新封装，封装出一个功能强大的数组，而这个强大的数组就是我们要学习的顺序表。
既然是数据结构，那么肯定是要定义结构体的。那么第一点就是如何定义出需要的结构体。首先我们先定义一个最简单的数组，比如：int arr[5]，那这个就定义了一个数组。其次我们如何知道数组中元素的个数呢？我们在添加一个size变量即可，默认的时候size为0，每添加一个元素就执行size++，删除一个元素就执行size--。这样我们就定义出结构体了。
typedef struct {
int array[5];
int length;
} SeqList;
为了让这个结构体的可读性更好，我们把数字提取出来，作为全局常量来使用。
const int CAPACITY = 5; //CAPACITY是容量的意思
typedef struct {
int array[CAPACITY];
int length;
} SeqList;
定义好了结构体，我们就需要使用结构体了，首先我们需要声明这个结构体变量
SeqList list;
1. 初始化这个结构体init()
当我们声明SeqList的时候，编译器已经为list和length分配内存空间了，但是此时里面都是垃圾值，而list我们后面会通过操作把里面的值替换掉，所以不用初始化它，故我们只需要把这个length设为0即可。
void init(SeqList * list) {
list-> length = 0;
}
2. 判断顺序表是否为空isEmpty()
顺序表是否为空的标识是顺序的长度是否为0即可。返回布尔值，等于0为true，等于1为false。由于返回的是的布尔值，而c语言中没有bool类型，以及关键词true和false，所以我们需要自己定义。
#define true 1
#define false 0
typedef int bool;
bool isEmpty(SeqList * list) {
return list->length == 0;
}
3. 判断线性表是否已满isFull()
判断顺序表是否为满，只需要判断顺序表长度是否等于顺序表的容量
bool isFull(SeqList * list) {
return list->length == CAPACITY;
}
4. 获得元素get()
获得某个元素只需要使用数组下标即可
int get(SeqList * list, int index) {
return list->array[index];
}
如果要快速获得第一个或者最后一个元素，我们可以在添加以下两个方法
//获得第一个元素
int getFirst(SeqList * list) {
return list->array[0];
}
//获得最后一个元素
int getLast(SeqList * list) {
return list->array[list->length-1];
}
5.查找元素的下标
有时候我们需要根据元素来查找下标，如果找到则返回响应的下标，否则返回-1。
查找算法只需要从第一个元素开始，依次与e进行比较。
int locateElem(SeqList * list, int e) {
for(int i=0; i<list->length; i++) {
if(list->array[i] == e) {
return i;
}
}
return -1;
}
6. 插入元素
插入操作就是在顺序表的第index位置插入新的元素e。
在第index位置插入元素e，只需要把从第i个元素依次往后移动一个位置，然后把元素e赋值给第index位置的元素。移动元素时，先移动最后一个元素，再移动倒数第二个元素，以此类推。
例如有一个顺序表，[6,2,3,1]
顺序表[6,2,3,1]
如果我们要在第1的位置插入元素5（最小是第0个元素，符合计算机内部逻辑）
在第1的位置插入元素5
这个时候我们只需将1往后移动一个位置，3再往后移动一个位置，2往后移动一个位置，最后把5赋值给1的位置。
操作过程
当然，在这个操作前，我们必须首先判断index的值是否合法，不合法直接报错，然后还有判断这个线性表是否为满，满了也是不能添加的。
当添加了一个元素后，它的长度要加1。
void insert(SeqList * list, int index, int e) {
if(index<0 || index>list->length) {
printf("Insert failed! Index is out of range!");
exit(-1);
}
if(isFull(list)) {
printf("Insert failed! The SeqList is full!");
exit(-1);
}
for(int i=list->length-1; i>index; i--) {
list->array[i+1] = list->array[I];
}
list->array[index] = e;
list->length++;
}
7. 删除元素
删除元素就是删除线性表中第index个位置上的元素。假设我们要删除索引为2的元素，那么我们只需把后一个元素一次往前移动一个位置即可。
删除索引为2的元素
int deleteEl(SeqList * list, int index) {
if(index < 0 || index > list->length) {
printf("DeleteEl failed! Index error\n");
exit(-1);
}
int delEl = list->array[index];
for(int i = index; i< list->length-1; i--) {
list->array[i] = list->array[i+1];
}
list->length--;
return delEl;
}
基本代码：
//
// main.c
// SeqList
//
// Created by 季晓东 on 2019/3/26.
// Copyright © 2019 季晓东. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
const int CAPACITY = 5; //CAPACITY是容量的意思
typedef int bool;
typedef struct {
int array[CAPACITY];
int length;
} SeqList;
void init(SeqList * list);
bool isEmpty(SeqList * list);
bool isFull(SeqList * list);
int get(SeqList * list, int index);
int getFirst(SeqList * list);
int getLast(SeqList * list);
int locateElem(SeqList * list, int e);
void insert(SeqList * list, int index, int e);
int deleteEl(SeqList * list, int index);
void init(SeqList * list) {
list-> length = 0;
}
bool isEmpty(SeqList * list) {
return list->length == 0;
}
bool isFull(SeqList * list) {
return list->length == CAPACITY;
}
int get(SeqList * list, int index) {
return list->array[index];
}
int getFirst(SeqList * list) {
return list->array[0];
}
int getLast(SeqList * list) {
return list->array[list->length-1];
}
int locateElem(SeqList * list, int e) {
for(int i=0; i<list->length; i++) {
if(list->array[i] == e) {
return i;
}
}
return -1;
}
void insert(SeqList * list, int index, int e) {
if(index<0 || index>list->length) {
printf("Insert failed! Index is out of range!");
exit(-1);
}
if(isFull(list)) {
printf("Insert failed! The SeqList is full!");
exit(-1);
}
for(int i=list->length-1; i>index; i--) {
list->array[i+1] = list->array[i];
}
list->array[index] = e;
list->length++;
}
int deleteEl(SeqList * list, int index) {
if(index < 0 || index > list->length) {
printf("DeleteEl failed! Index error\n");
exit(-1);
}
int delEl = list->array[index];
for(int i = index; i< list->length-1; i++) {
list->array[i] = list->array[i+1];
}
list->length--;
return delEl;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
SeqList list;
init(&list);
for (int i=0; i<3; i++) {
insert(&list, i, i+11);
}
for (int i=0; i<3; i++) {
printf("%d,",get(&list, i));
}
printf("\n");
deleteEl(&list, 1);
for (int i=0; i<list.length; i++) {
printf("%d,",get(&list, i));
}
printf("\n");
return 0;
}
改进代码：
//
// main.c
// Array用来对数组进行封装，更好的实现对数组的操作
//s
// 代码规范：
// 1. 自定义bool数据类型及其值
// typedef int bool;
// #define true 1
// #define false 0
//
// 2. 指针变量前加p
// 如 int *pArr;
//
// 3. 逗号后面加空格，左大括号左边加空格，&&或||两边加空格，等号两边加空格
//
//
// 算法：
// 1.获得数组的有效的个数
// 2.获得数组的容量
// 3.判断数组是否为空
// 4.判断数组是否已满
// 5.插入某个元素
// 6.查找某个元素
// 7.修改某个元素
// 8.删除某个元素
// 9.是否包含某个元素
// 10.查找某个元素的位置
//
//
#include <stdio.h>
#include <stdlib.h>
//定bool类型的值true|false
#define true 1
#define false 0
#define EXIT -1
#define ZERO 0
//自定义bool数据类型
typedef int bool;
/**
自定义结构体数据类型Array
如：Array arr等价于struct Array arr
*/
typedef struct Array{
//数组的第一个元素
int *pBaseArray;
//数组的有效元素个数
int size;
//数组的总容量 0 <= size <= capacity
int capacity;
}Array;
//----------------------------------------------函数声明----------------------------------------------------------------
//初始化数组, capacity为数组的总容量
void init(Array *pArr, int capacity);
//获得有效元素的个数
int getSize(Array *pArr);
//获得数组的容量
int getCapacity(Array *pArr);
//判断数组是否为空
bool isEmpty(Array *pArr);
//判断数组是否已满
bool isFull(Array *pArr);
//在第index位置添加元素e，index从0开始
void add(Array *pArr, int index, int e);
//在数组最前添加元素
void addFirst(Array *pArr, int e);
//在数组最后添加元素
void addLast(Array *pArr, int e);
//查找第index位置上的元素，index从0开始
int get(Array *pArr, int index);
//查找第一个元素
int getFirst(Array *pArr);
//查找最后一个元素
int getLast(Array *pArr);
//修改元素
void set(Array *pArr, int index, int e);
//判断数组中是否包含元素e
bool contains(Array *pArr, int e);
//删除index位置上的元素，index从0开始
int delete(Array *pArr, int index);
//删除第一个元素
int deleteFirst(Array *pArr);
//删除最后一个元素
int deleteLast(Array *pArr);
//查找第一个元素e的位置，没有查到则返回-1
int indexOf(Array *pArr, int e);
//销毁数组
void destory(Array *pArr);
//显示数组信息
void show(Array *pArr);
//自定义错误提示
void error(char* msg);
//自定义警告提示
void warning(char* msg);
//----------------------------------------------函数实现----------------------------------------------------------------
void init(Array *pArr, int capacity) {
//为pBaseArray分配sizeof(int) * capacity个内存空间
pArr->pBaseArray = (int *)malloc(sizeof(int) * capacity);
//如果pBaseArray为空,则内存分配失败，退出程序
if (pArr->pBaseArray == NULL) {
error("Array memory allocation failed.");
exit(EXIT);
}
//初始条件总容量是用户传进来的总容量
pArr->capacity = capacity;
//初始条件元素个数为0
pArr->size = 0;
}
int getSize(Array *pArr) {
return pArr->size;
}
int getCapacity(Array *pArr) {
return pArr->capacity;
}
bool isEmpty(Array *pArr) {
return pArr->size == ZERO;
}
bool isFull(Array *pArr) {
return pArr->size == pArr->capacity;
}
void add(Array *pArr, int index, int e) {
//判断数组是否已满，不满才可以添加
if (isFull(pArr)) {
warning("Array is full.");
return;
}
for (int i = pArr->size; i>index; i--) {
pArr->pBaseArray[i] = pArr->pBaseArray[i-1];
}
pArr->pBaseArray[index] = e;
//维护size
pArr->size++;
}
void addFirst(Array *pArr, int e) {
add(pArr, ZERO, e);
}
void addLast(Array *pArr, int e) {
//判断数组是否已满，不满才可以添加
if (isFull(pArr)) {
warning("Array is full.");
return;
}
//在数组后面添加就是在size的位置添加元素e
pArr->pBaseArray[pArr->size] = e;
//维护size
pArr->size++;
}
int get(Array *pArr, int index) {
if (index<0 && index>=pArr->size) {
error("Index out of range.");
exit(EXIT);
}
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
return pArr->pBaseArray[index];
}
int getFirst(Array *pArr) {
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
return pArr->pBaseArray[ZERO];
}
int getLast(Array *pArr) {
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
return pArr->pBaseArray[pArr->size-1];
}
void set(Array *pArr, int index, int e) {
if (index<0 && index>=pArr->size) {
error("Index out of range.");
exit(EXIT);
}
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
pArr->pBaseArray[index] = e;
}
bool contains(Array *pArr, int e) {
for (int i=0; i<pArr->size; i++) {
if (pArr->pBaseArray[i] == e) {
return true;
}
}
return false;
}
int delete(Array *pArr, int index) {
if (index<0 && index>=pArr->size) {
error("Index out of range.");
exit(EXIT);
}
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
int delArr = pArr->pBaseArray[index];
for (int i=index; i<pArr->size-1; i++) {
pArr->pBaseArray[i] = pArr->pBaseArray[i+1];
}
pArr->size--;
return delArr;
}
int deleteFirst(Array *pArr) {
return delete(pArr, ZERO);
}
int deleteLast(Array *pArr) {
if (isEmpty(pArr)) {
error("Array is empty.");
exit(EXIT);
}
pArr->size--;
return pArr->pBaseArray[pArr->size-1];
}
int indexOf(Array *pArr, int e) {
for (int i=0; i<pArr->size; i++) {
if (pArr->pBaseArray[i] == e) {
return I;
}
}
return -1;
}
void destory(Array *pArr) {
free(pArr);
pArr=NULL;
}
void show(Array *pArr) {
printf("Array: capacity=%d, size=%d, ", pArr->capacity, pArr->size);
printf("[");
for (int i=0; i<pArr->size; i++) {
printf("%d", pArr->pBaseArray[I]);
if (i != pArr->size-1) {
printf(", ");
}
}
printf("]\n ");
return;
}
void error(char* msg) {
printf("\n---------------------------------------------------------------------------\n");
printf("ERROR: %s", msg);
printf("\n---------------------------------------------------------------------------\n\n");
}
void warning(char* msg) {
printf("\n---------------------------------------------------------------------------\n");
printf("WARNING: %s", msg);
printf("\n---------------------------------------------------------------------------\n\n");
}
//----------------------------------------------main函数----------------------------------------------------------------
int main(int argc, const char * argv[]) {
Array array;
init(&array, 5);
for (int i=0; i<4; i++) {
add(&array, i, i);
show(&array);
}
if (contains(&array, 0)) {
printf("true\n");
}else{
printf("false\n");
}
printf("get 1: %d\n", get(&array, 1));
printf("getFirst: %d\n", getFirst(&array));
printf("getLast: %d\n", getLast(&array));
printf("indexOf 3: %d\n", indexOf(&array, 3));
set(&array, 2, 1000);
show(&array);
addFirst(&array, -1);
show(&array);
delete(&array, 0);
show(&array);
deleteFirst(&array);
show(&array);
deleteLast(&array);
show(&array);
addLast(&array, 10);
show(&array);
// destory(&array);
addLast(&array, 10);
show(&array);
return 0;
}
Screen Shot 2019-01-18 at 2.05.43 PM.png
Screen Shot 2019-01-18 at 2.08.00 PM.png
