【数据结构】线性表

摘要

1. 脏数据：在新开辟（分配）一片存储空间时，这块存储空间会保留之前存储在此的数据，这些数据就叫脏数据。

顺序表

顺序表中元素的逻辑顺序与物理顺序相同。

存储空间分配方式

• 静态分配

  创建存储空间时指定空间的大小，空间占满时添加新数据会导致溢出报错。

  #include <stdio.h>
  #define MaxSize 10
  
  typedef struct {
    int data[MaxSize];
    int length;
  }SqList;
  

• 动态分配

  存储空间在程序执行期间动态分配，在空间占满时开辟出另一块更大的存储空间替换掉原来的存储空间。

  typedef struct {
  	int *data;
    int MaxSize; // 顺序表的最大容量
  	int length;   // 顺序表的当前长度
  }SqList;
  

顺序表的代码实现

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int *data;   	// 指向存储空间的指针
	int length;		// 当前存储的元素数量
	int maxLength; 	// 最大存储元素数量
} SeqList;

// 初始化顺序表
void initSeqList(SeqList &L, int maxLength) {
	// 开辟存储空间
	L.data = (int *)malloc(sizeof(int) * maxLength);
	// 初始化数据，清除脏数据
	for(int i = 0; i < maxLength; i++) {
		L.data[i] = 0;
	}
	L.maxLength = maxLength;
	L.length = 0;
};

// 增加顺序表长度
void increaseSeqList(SeqList &L, int length) {
	int *p = L.data;
	L.data = (int *)malloc(sizeof(int) * (length + L.maxLength));
	for(int i = 0; i < L.length; i++) {
		L.data[i] = p[i];
	}
	L.maxLength = length + L.maxLength;
	free(p);
	p = NULL;
}

// 打印顺序表元素
void printSeqList(SeqList &L) {
	for(int i = 0; i < L.length; i++) {
		printf("顺序表元素：%d-%d\n", i, L.data[i]);
	}
	printf("顺序表已存数据/最大长度：%d/%d\n", L.length, L.maxLength);
}

// 插入元素
bool insertItemToSeqList(SeqList &L,int index, int value) {
	// 只能按顺序添加
	if(index > L.length) {
		return false;
	}
	// 避免溢出
	if(index > L.maxLength) {
		return false;
	}
	int len = L.length;
	// 添加时index之后的元素全部后移，要移动 L.length - index 个元素，从后往前遍历更方便
	while(len-- > index) {
		L.data[len + 1] = L.data[len];
	}
	L.data[index] = value;
	L.length++;
	return true;
}

// 删除元素
bool removeItemFromSeqList(SeqList &L,int index) {
	// 避免越界
	if(index < 0 || index > L.length - 1) {
		return false;
	}
	// 删除时要把index后的所有元素前移，要移动 L.length - index 个元素，从index下标开始遍历，所有数据前移一位，不需要遍历最后一位
	for(int i = index; i < L.length - 1; i++) {
		L.data[i] = L.data[i + 1];
	}
	L.length--;
	return true;
}

int main()
{
	SeqList L;
	// 初始化
	initSeqList(L, 10);
	// 添加元素
	insertItemToSeqList(L, 0, 1);
	insertItemToSeqList(L, 0, 2);
	insertItemToSeqList(L, 0, 3);
	insertItemToSeqList(L, 0, 4);
	printSeqList(L);
	// 扩展顺序表存储空间
	increaseSeqList(L, 10);
	printSeqList(L);
	// 删除下标1位置的元素
	removeItemFromSeqList(L, 1);
	printSeqList(L);
  return 0;
}