2-1 线性表之顺序表 及其C语言实现

#ifndef SQ_LIST_01_H_
#define SQ_LIST_01_H_

#define MAX 10
typedef struct Sq_List_Static{
	int data[MAX];//创建一个数组来充当顺序表
	int length;//记录元素个数
}sq_list_;

//线性表主要的基本操作
void Init(sq_list_ *l);//初始化
int Len(sq_list_ *l);//求长度
int Get(sq_list_ *l, int i);//按索引返回元素
int Locate(sq_list_ *l, int x);//查找元素索引
void Insert(sq_list_ *l, int i, int x);//指定索引处插入元素
void Delete(sq_list_ *l, int i);//删除指定索引的元素

#endif // !SQ_LIST_01_H_

#include<iostream>
#include"sq_list_01.h"

/*初始化*/
void Init(sq_list_ *l) {
	l->length = 0;
}

/*返回长度*/
int Len(sq_list_ *l) {
	return l->length;
}

/*返回指定索引元素*/
int Get(sq_list_ *l, int i) {
	if (i >= 0 && i < l->length) {//索引应该大于0且小于表长
		return l->data[i];
	}
	else
		return NAN;
}

/*返回元素索引*/
int Locate(sq_list_ *l, int x) {
	//可以选用其他更好的查找方法，这里为了简便只用遍历方法
	for (int i = 0; i < l->length; i++)
		return x == l->data[i] ? i : -1;//三目运算符
	//如果x等于某个元素就返回其索引，如果没有这样的元素就返回-1，表示没有
}

/*按索引插入元素x*/
void Insert(sq_list_ *l,int i, int x) {
	//先判满，看顺序表是否还有空间能装得下新元素
	if (l->length >= MAX) {
		std::cout << "\nthe list is full!\n";
		return;
	}
	//然后判断选择插入的索引位置是否合理
	//已有元素的索引为0---length-1，所以插入元素的范围只能是 0---length,
	if (i<0 || i>l->length) {
		std::cout << "\ninvalid index: "<<i<<"! the index should be 0 - "<< l->length<<" \n";
	}
	//把i位置及其之后的元素都后移一位
	int j;
	for (j = l->length - 1; j > i; j--)
		l->data[j + 1] = l->data[j];
	l->data[i] = x;//在i位置赋值x
	l->length++;//更新表长
}

/*删除指定索引元素*/
void Delete(sq_list_ *l, int i) {
	//判空
	if (l->length<=0) {
		std::cout << "\the list is empty!\n";
		return;
	}
	if (i<0 || i>l->length - 1) {
		std::cout << "\ninvalid index: "<<i<<"! the index should be 0 - " << l->length-1 << " \n";
		return;
	}
	for (int j = i; j < l->length - 1; j++)
		l->data[j] = l->data[j + 1];

	l->length--;
}

#include<iostream>
#include"sq_list_01.h"

using std::cin;
using std::cout;
using std::endl;

int main() {

	sq_list_ list_0;

	Init(&list_0);
	cout << "\nthe length of list: " << Len(&list_0) << endl;
	
	/*这里故意将插入元素的次数设置为多于MAX，看是否能顺利运行*/
	for (int i = 0; i < MAX + 1; i++) {
		Insert(&list_0, i, i*i);
		for (int j = 0; j < list_0.length; j++) {
			cout << Get(&list_0, j) << "   ";
		}
		cout << endl;
	}
	cout << "\nthe length of list: " << Len(&list_0) << endl;

	

	for (int k = list_0.length; k >=0; k--) {
		Delete(&list_0, k);
		for (int j = 0; j < list_0.length; j++) {
			cout << Get(&list_0, j) << "   ";
		}
		cout << endl;
	}

	cin.get();
	return 0;
}

#ifndef SQ_LIST_02_H_
#define SQ_LIST_02_H_

#define MAX 10

typedef struct Sq_List_Dynamic {

	int * head;//动态内存块的地址
	int length;//顺序表的元素个数
	int ListSize = MAX;//顺序表的容量

}list;

void Init(list *l);
int Len(list *l);
int Get(list *l, int i);
int Locate(list *l, int x);

void Insert(list *l, int i, int x);
void Delete(list *l, int i);

void Destroy(list *l);
#endif

#include<iostream>
#include"sq_list_02.h"

using std::cin;
using std::cout;
using std::endl;


void Init(list *l) {
	l->head = (int*)malloc( l->ListSize * sizeof(int) );//动态开辟内存，并返回地址给head
	l->length = 0;
}

int Len(list *l) {
	return l->length;
}

int Get(list *l, int i) {
	//作为顺序表依然从0开始计数，所以合理范围是 0 --- length-1
	if (i >= 0 && i < l->length)
		return l->head[i];
	else
		return NAN;
}

int Locate(list *l, int x) {

	for (int i = 0; i < l->length; i++)
		return x == l->head[i] ? i : -1;//三木运算符
	//如果x等于某个数就返回索引i，否则返回-1表示没有这个数
}

void Insert(list *l, int i, int x) {
	//判断插入位置是否合理
	if (i<0 || i>l->length) {
		cout << "\ninvalid index: " << i << " ! the valid index should be in range of 0---" << l->length - 1 << endl;
		return;
	}

	//判断顺序是否已经满了，这里和静态顺序表有个区别
	if (l->length >= l->ListSize) {
		//在动态顺序表已满的时候，可以再用realloc函数给它紧接着原来的内存又开辟新的内存！
		//我下面这行代码就又多开辟了一个内存，允许在表满的情况下，继续在尾部多插入一个元素
		l->head = (int *)realloc( l->head,(l->ListSize + 1) * sizeof (int));
		l->ListSize++;//别忘了把顺序表的总容量的数值也增1，
	}

	//接下来的操作和静态顺序表一样，将i位置及其之后的元素右移，然后将新元素赋值给i位置
	for (int j = l->length - 1; j >= i; j--)
		l->head[j + 1] = l->head[j];

	l->head[i] = x;
	l->length++;
}
void Delete(list *l, int i) {
	if (i<0 || i>l->length - 1) {
		cout << "\invalid index: " << i << " ! the valid index should be in range of 0---" << l->length - 1 << endl;
		return;
	}

	for (int j = i; j < l->length - 1; j++) {
		l->head[j] = l->head[j + 1];
		l->length--;
	}
}

/*对于开辟的动态内存，要记得手动释放，否则造成内存泄漏*/
void Destroy(list *l) {
	free(l->head);
}

#include<iostream>
#include"sq_list_02.h"

using std::cin;
using std::cout;
using std::endl;

int main() {

	list L;
	Init(&L);
	cout << "\nThe length of the list is " << Len(&L) << endl;

	for (int i = 0; i < MAX + 2; i++) {
		Insert(&L, i, i * 10);
		for (int j = 0; j < L.length; j++) {
			cout << Get(&L, j) << "  ";
		}
		cout << endl;
	}

	for (int i = L.length; i >=0; i--) {
		Delete(&L, i);

		for (int j = 0; j < L.length; j++) {
			cout << Get(&L, j) << "  ";
		}
		cout << endl;
	}


	cin.get();
    //对于动态开辟的内存，一定要记得手动给释放掉！！！
	Destroy(&L);
	return 0;
}