【数据结构与算法-C语言版】顺序表(线性表的顺序存储结构)及C语言实现

程序来自：

 http://data.biancheng.net/view/4.html

注释为自己手动添加，仅供交流学习，欢迎指导。

#include <stdio.h>
#include <stdlib.h>
#define Size 4


#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);



typedef struct Table{
	
	int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
	//定义的数组指针的名字也可以作为首地址来使用
	int length;//记录当前顺序表的长度
	int size;//记录顺序表分配的存储容量
}table;


//主程序中使用   table t1 = initTable();  来初始化 t1
//不传入参数，而且返回值是t，所以可以用 等号
//不同于C++ 类中的成员函数的使用，暂时称为 C语言结构体的非成员函数吧
table initTable(){
	table t;
	t.head = (int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
	//分配的数组要用 (int*) 表示，这样申请的动态空间就是 int 型的

	if (!t.head) //如果申请失败，作出提示并直接退出程序
	{
		printf("初始化失败");
		exit(0);
	}
	t.length = 0;//空表的长度初始化为0
	t.size = Size;//空表的初始存储空间为Size
	return t;
}




//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t, int elem, int add)
{
	//判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），
	//或者插入的位置本身不存在，程序作为提示并自动退出）
	if (add>t.length + 1 || add<1) {
		printf("插入位置有问题");
		return t;
	}
	//做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
	if (t.length == t.size) {
		//c语言里尽量不要使用 realloc ，容易引发内存泄漏
		t.head = (int *)realloc(t.head, (t.size + 1)*sizeof(int));
		if (!t.head) {
			printf("存储分配失败");
			return t;
		}
		t.size += 1;
	}
	//插入操作，需要将从插入位置开始的后续元素，逐个后移
	for (int i = t.length - 1; i >= add - 1; i--) {
		t.head[i + 1] = t.head[i];
	}
	//后移完成后，直接将所需插入元素，添加到顺序表的相应位置
	t.head[add - 1] = elem;
	//由于添加了元素，所以长度+1
	t.length++;
	return t;
}




table delTable(table t, int add){
	//这里的大小判断与数组下标是否 - 1 无关，length是数组实际的长度，而不是C语言里 -1 之后的长度
	if (add>t.length || add<1) {
		printf("被删除元素的位置有误");
		exit(0);
	}
	//删除操作
	//并没有对删除后的最后一个数进行管理，估计程序结束后就会释放吧
	//如果删除一个元素，要使用自增运算  从前向后循环赋值
	//如果增加一个元素，要使用自减运算  从后向前循环赋值
	for (int i = add; i<t.length; i++) {
		t.head[i - 1] = t.head[i];
	}
	t.length--;		//执行完一次，t.length就 -1
	return t;
}


//查找函数，其中，elem表示要查找的数据元素的值
int selectTable(table t, int elem){
	for (int i = 0; i<t.length; i++) {
		if (t.head[i] == elem) {
			return i + 1;
		}
	}
	return -1;//如果查找失败，返回-1
	//上面的 for 循环没有找到元素  就无法  return i + 1  那就要 return -1
}
//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
table amendTable(table t, int elem, int newElem){
	int add = selectTable(t, elem);
	t.head[add - 1] = newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
	return t;
}


//数组展示
void displayTable(table t){
	for (int i = 0; i<t.length; i++) {
		printf("%d", t.head[i]);
	}
	printf("\n");
}
int main(){
	//先初始化
	table t1 = initTable();
	for (int i = 1; i <= Size; i++) {
		t1.head[i - 1] = i;
		t1.length++;
	}
	printf("原顺序表：\n");
	displayTable(t1);		//看起来是展示了t1， 其实t1是包含了数组、数组长度、数组大小的结构体，这样才能用

	//PAUSE


	printf("删除元素1:\n");
	t1 = delTable(t1, 1);
	displayTable(t1);
	printf("%d\n", t1.length);

	printf("在第2的位置插入元素5:\n");
	t1 = addTable(t1, 5, 2);
	displayTable(t1);

	printf("查找元素3的位置:\n");
	int add = selectTable(t1, 3);
	printf("%d\n", add);

	printf("将元素3改为6:\n");
	t1 = amendTable(t1, 3, 6);
	displayTable(t1);
	return 0;
}

 

 

 

附（a）  在C语言中结构体定义的两种方式--省略结构体名称 与 写出结果体名称的优势与劣势

例子：

//在C中定义一个结构体类型要用typedef:
typedef struct Student
{
    int a;
}Stu;
//于是在声明变量的时候就可：Stu stu1;(如果没有typedef就必须用struct Student stu1;来声明)
//这里的Stu实际上就是struct Student的别名。Stu==struct Student

//另外这里也可以不写Student（于是也不能struct Student stu1;了，必须是Stu stu1;）
//这样在主程序里就不容易清楚地知道  stu1 是不是 struct 类型了
typedef struct
{
    int a;
}Stu;

 

 

附（b）  在主程序内把结构体作为形参传入子函数之后，如果对结构体内原有的数组进行操作

那么 该数组 就会发生改变（推测应该是进行了指针操作），而结构体内其他的成员变量却不会改变
这与c语言中子函数调用前后 主程序内变量不变  不同 

例子：

//程序需要注意的是，在主程序内把结构体作为形参传入子函数之后，如果对结构体内原有的数组进行操作
//那么 该数组 就会发生改变（推测应该是进行了指针操作），而结构体内其他的成员变量却不会改变
//这与c语言中子函数调用前后 主程序内变量不变  不同 


#include <stdio.h>
#include <stdlib.h>
#define Size 4


#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);



typedef struct Table{

	int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
	//定义的数组指针的名字也可以作为首地址来使用
	int length;//记录当前顺序表的长度
	int size;//记录顺序表分配的存储容量
}table;


//主程序中使用   table t1 = initTable();  来初始化 t1
//不传入参数，而且返回值是t，所以可以用 等号= 来初始化
table initTable(){
	table t;
	t.head = (int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
	//分配的数组要用 (int*) 表示，这样申请的动态空间就是 int 型的

	if (!t.head) //如果申请失败，作出提示并直接退出程序
	{
		printf("初始化失败");
		exit(0);
	}
	t.length = 0;//空表的长度初始化为0
	t.size = Size;//空表的初始存储空间为Size
	return t;
}




//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t, int elem, int add)
{
	//判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），
	//或者插入的位置本身不存在，程序作为提示并自动退出）
	if (add>t.length + 1 || add<1) {
		printf("插入位置有问题");
		return t;
	}
	//做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
	if (t.length == t.size) {
		//c语言里尽量不要使用 realloc ，容易引发内存泄漏
		t.head = (int *)realloc(t.head, (t.size + 1)*sizeof(int));
		if (!t.head) {
			printf("存储分配失败");
			return t;
		}
		t.size += 1;
	}
	//插入操作，需要将从插入位置开始的后续元素，逐个后移
	for (int i = t.length - 1; i >= add - 1; i--) {
		t.head[i + 1] = t.head[i];
	}
	//后移完成后，直接将所需插入元素，添加到顺序表的相应位置
	t.head[add - 1] = elem;
	//由于添加了元素，所以长度+1
	t.length++;
	return t;
}




table delTable(table t, int add){
	if (add>t.length || add<1) {
		printf("被删除元素的位置有误");
		exit(0);
	}
	//删除操作
	for (int i = add; i<t.length; i++) {
		t.head[i - 1] = t.head[i];
	}
	t.length--;
	return t;
}


//查找函数，其中，elem表示要查找的数据元素的值
int selectTable(table t, int elem){
	for (int i = 0; i<t.length; i++) {
		if (t.head[i] == elem) {
			return i + 1;
		}
	}
	return -1;//如果查找失败，返回-1
}
//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
table amendTable(table t, int elem, int newElem){
	int add = selectTable(t, elem);
	t.head[add - 1] = newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
	return t;
}
void displayTable(table t){
	for (int i = 0; i<t.length; i++) {
		printf("%d", t.head[i]);
	}
	printf("\n");
}
int main(){
	//先初始化
	table t1 = initTable();
	table t2 = initTable();
	for (int i = 1; i <= Size; i++) {
		t1.head[i - 1] = i;
		t1.length++;
	}
	printf("原顺序表：\n");
	displayTable(t1);		//看起来是展示了t1， 其实t1是包含了数组、数组长度、数组大小的结构体，这样才能用

	//PAUSE


		printf("删除元素1:\n");
	t1 = delTable(t1, 1);
	displayTable(t1);


	//通过子函数修改了结构体 t1 的值
	//实际上是对t1.head进行了操作，这里面包含了指针操作
	//但对t1.length的自增操作无效，因为里面不涉及指针操作
	//...不懂...
	printf("-----在第2的位置插入元素5:\n");
	t2 = addTable(t1, 5, 2);
	displayTable(t2);


	printf("-----displayTable(t1);\n");
	displayTable(t1);
	printf("t1.length = %d\n", t1.length);


	printf("在第2的位置插入元素5:\n");
	t1 = addTable(t1, 5, 2);
	displayTable(t1);

	printf("查找元素3的位置:\n");
	int add = selectTable(t1, 3);
	printf("%d\n", add);

	printf("将元素3改为6:\n");
	t1 = amendTable(t1, 3, 6);
	displayTable(t1);
	return 0;
}