数组基础知识

顺序表

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdbool.h>

#define SEQLIST_INIT_SIZE 8
#define INC_SIZE		  3

typedef int ElemType;//为什么非要这么定义?目前使用的是C语言，且我们现在的表是一个整型数据的顺序表，极有可能我们的表存放的包括别的类型的数据，如字符数据、结构体数据等等；
//如果仅仅是整型数据，一旦对类型进行修改了，那么所有的与类型相关的程序都要进行修改，不然报错；

typedef struct SeqList
{
	ElemType* base;//指向顺序表的空间
	int capacity;//容量
	int size;//大小
}SeqList;

bool Inc(SeqList* list);
void InitSeqList(SeqList* list);//初始化顺序表结构，传递mylist的地址，因为要对结构改变，因此，以地址形式进行传递
void push_front(SeqList* list, ElemType x);
void push_back(SeqList* list, ElemType x);
void show_list(SeqList* list);
void pop_back(SeqList* list);
void pop_front(SeqList* list);
void insert_pos(SeqList* list, int pos, ElemType item);
int find(SeqList* list, ElemType item);
int length(SeqList* list);
void delete_pos(SeqList* list, int pos);
void delete_val(SeqList* list, ElemType key);
void sort(SeqList* list);
void reverse(SeqList* list);
void clear(SeqList* list);
void destory(SeqList* list);
void merge(SeqList lt, SeqList la, SeqList lb);

#endif//__SEQLIST_H__

SeqList.cpp

#include"SeqList.h"

//在.h文件中声明之后，就要在相应的.cpp文件中进行实现
//当定义了mylist之后，事实上只定义了mylist结构，杂base、capacity、size都是未初始化的随机状态
//这三个的初始化过程是：给base开辟一个顺序表的内存空间，然后对base的容量和大小进行设置。

//初始化链表
void InitSeqList(SeqList* list)
{
	list->base = (ElemType)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);//开辟完成后，要进行转换
	//当开辟完成之后，我们要对其进行断言 //为了使用这些函数，需要引入malloc函数和assert函数
	assert(list->base != NULL);//如果空间为空，说明开辟不成功，不然就是成功了
	list->capacity = SEQLIST_INIT_SIZE;
	list->size = 0;
}

//插入数据，首先要考虑表满不满，删除数据，首先要考虑表空不空

//[1]头插法插入数据
void push_front(SeqList* list, ElemType x)
{
	if (list->size >= list->capacity && !Inc(&list))
	{
		printf("the SeqList is full,Can't push_back this element %d\n", x);
		return;
	}

	for (int i = list->size; i > 0; --i)//当i = 0时，数据的移动都结束了
	{
		list->base[i] = list->base[i - 1];
	}

	list->base[0] = x;
	list->size++;
}

//[2]尾插法插入数据
void push_back(SeqList* list, ElemType x)
{
	//并上增加内存的返回值，表示为true，表示增加内存成功，继续执行下面程序
	//1.容量已满，增加空间失败，为true打印并返回
	//2.如果满了且增加空间成功，就可以继续增加数据
	if (list->size >= list->capacity && !Inc(&list))
	{
		printf("the SeqList is full,Can't push_back this element %d\n", x);
		return;
	}
	list->base[list->size] = x;
	list->size++;
}

//[3]遍历顺序表
void show_list(SeqList* list)
{
	for (int i = 0; i < list->size; ++i)
	{
		printf("%d ", list->base[i]);
	}
	printf("\n");
}

//[4]头删法删除数据
void pop_front(SeqList* list)
{
	if (list->size == 0)//判断表是否为空
	{
		printf("顺序表为空，不能头部删除数据！\n");
		return;
	}
	for (int i = 0; i < list->size - 1; ++i)
	{
		list->base[i] = list->base[i + 1];
	}
	list->size--;
}

//[5]尾删法删除数据
void pop_back(SeqList* list)
{
	if (list->size == 0)//判断表是否为空
	{
		printf("顺序表为空，不能尾部删除数据！\n");
		return;
	}
	list->size--;//删除数据与否，并非要真正从内存中删除，只是从逻辑角度表达出，这个数据是否是有效数据；逻辑上删除后，就变成了无效数据
}

/*
//[6]根据位置插入数据——分开考虑了头部和尾部
void insert_pos(SeqList *list, int pos, ElemType x)
{
	if (pos < 0 || pos > list->size)//pos == size是可以的，相当于在最后一个数的后边插入
	{
		printf("插入数据的位置非法，不能插入数据");
		return;
	}

	if (list->size >= list->capacity)
	{
		printf("顺序表已满，不能插入数据！\n");
		return;
	}

	if (pos == 0)
		push_front(list, x);
	else if (pos == list->size)
		push_back(list, x);
	else//当既不是头插入又不是尾插入的时候，就要移动数据;而移动数据的多少，和我们要插入的位置有关系
	{
		for (int i = list->size; i > pos; --i)
		{
			list->base[i] = list->base[i - 1];
		}
		list->base[pos] = x;
		list->size++;
	}
}

*/

//[6]根据位置插入数据——不分开考虑头部和尾部
void insert_pos(SeqList* list, int pos, ElemType x)
{
	if (pos < 0 || pos > list->size)//pos == size是可以的，相当于在最后一个数的后边插入
	{
		printf("插入数据的位置非法，不能插入数据");
		return;
	}

	if (list->size >= list->capacity && !Inc(&list))
	{
		printf("the SeqList is full,Can't push this element by position %d\n", x);
		return;
	}

	//不单独考虑头和尾也行的
	for (int i = list->size; i > pos; --i)
	{
		list->base[i] = list->base[i - 1];
	}
	list->base[pos] = x;
	list->size++;
}

//[7]元素查找所在的位置
int find(SeqList* list, ElemType key)
{
	for (int i = 0; i < list->size; ++i)
	{
		if (list->base[i] == key)
			return i;
	}
	return -1;//找不到就返回 -1
}

//[8]查看顺序表的长度
int length(SeqList* list)
{
	return list->size;
}

//[9]按位置删除
//只要涉及到位置，对于顺序表来说，位置比较关键，首先要判断位置的合法性
void delete_pos(SeqList* list, int pos)
{
	if (pos < 0 || pos >= list->size)//顺序表是从 0 开始的
	{
		printf("删除数据的位置非法，不能删除数据\n");
		return;
	}

	for (int i = pos; i < list->size - 1; ++i)
	{
		list->base[i] = list->base[i + 1];
	}
	list->size--;
}

//[10]按数据删除
//要删除数据，首先要知道元素是否在顺序表中存在，即数据的有效性
void delete_val(SeqList* list, ElemType key)
{
	int pos = find(list, key);
	if (pos == -1)//顺序表是从 0 开始的
	{
		printf("顺序表中不存在该数据\n");
		return;
	}

	delete_pos(list, pos);
}

//[11]排序——采用冒泡排序
void sort(SeqList* list)
{
	for (int i = 0; i < list->size - 1; ++i)//控制遍历的趟数
	{
		for (int j = 0; j < list->size - i - 1; ++j)//控制的是内部比较的次数
		{
			if (list->base[j] > list->base[j + 1])
			{
				ElemType tmp = list->base[j];
				list->base[j] = list->base[j + 1];
				list->base[j + 1] = tmp;
			}
		}
	}
}

//[12]逆置顺序表
//方法很多：
//1.申请一个空间大小和它一样的辅助空间，然后首尾对调赋值，然后再对调赋值（方法可行，但是不可取，太浪费空间）
//2.双指针:highr 和 low，low指向头部
void reverse(SeqList* list)
{
	//逆置之前先判断顺序表，当元素个数<=0时，交换无意义
	if (list->size == 0 || list->size == 1)
		return;

	int low = 0;
	int high = list->size - 1;
	ElemType tmp;
	while (low < high)
	{
		tmp = list->base[low];
		list->base[low] = list->base[high];
		list->base[high] = tmp;
		low++;
		high--;
	}
}

//[13]清空顺序表
void clear(SeqList* list)
{
	list->size = 0;//表还是存在的，只是把数据都删除了而已
}

//[14]销毁顺序表
void destory(SeqList* list)
{
	free(list->base);//malloc申请的，要由free还回去
	list->base = NULL;
	list->capacity = 0;
	list->size = 0;
}

//当表空间已满时，不能再通过头插、尾插、按位置插等方法，
//我们如果要插入数据，如果空间满了，那么我们需要自动在尾部对空间进行增加，
//除非malloc空间时，内存已经不足了，此时才真正的认为空间已经满了，不能再插入数据，
//除此以外只要你能申请空间，我们都希望以解决问题为主，而不是直接返回。

bool Inc(SeqList* list)
{
	ElemType* newbase = (ElemType*)realloc(list->base, sizeof(ElemType) * (list->capacity + INC_SIZE));//重新对已有的base空间进行分配内存
	if (newbase == NULL)
	{
		printf("增配空间失败，原因：内存不足");
		return false;
	}
	list->base = newbase;
	list->capacity += INC_SIZE;
	return true;
}

void merge(SeqList* lt, SeqList* la, SeqList* lb)
{
	lt->capacity = la->size + lb->size;//用la->size而不用la->capacity
	lt->base = (ElemType*)malloc(sizeof(ElemType) * lt->capacity);
	assert(lt->base != NULL);

	int ia = 0;
	int ib = 0;
	int ic = 0;

	while (ia < la->size && ib <lb->size)//ia < la->size时，说明mylist表里还有相应的数据
	{
		if (la->base[ia] < lb->base[ib])
			lt->base[ic++] = la->base[ia++];
		else
			lt->base[ic++] = lb->base[ib++];
	}

	while (ia < la->size)
	{
		lt->base[ic++] = la->base[ia++];
	}

	while (ib < lb->size)
	{
		lt->base[ic++] = lb->base[ib++];
	}

	lt->size = la->size + la->size;
}

Main.cpp

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include "SeqList.h"


void main()
{
	SeqList mylist;
	InitSeqList(&mylist);//只有传入指针才能操作表

	ElemType item;//元素类型，在头文件中有定义
	int select = 1;
	int pos = 0;
	while (select)
	{
		printf("**********************************\n");
		printf("* [1]	push_back	[2]	push_front	 *\n");
		printf("* [3]	show_list	[4]	pop_back		 *\n");
		printf("* [5]	pop_front	[6]	insert_pos	 *\n");
		printf("* [7]	find		[8]	length		 *\n");
		printf("* [9]	delete_pos	[10]	delete_val	 *\n");
		printf("* [11]	sort		[12]	reverse		 *\n");
		printf("* [13]	clear		[14*]	destory		 *\n");//destory这个方法不应该由客户来调动；而是应该在退出程序时摧毁
		printf("* [0]	quit_system				 *\n");
		printf("**********************************\n");
		printf("请选择:>");
		scanf("%d", &select);
		if (select == 0)
			break;

		switch (select)
		{
		case 1:
			printf("请输入要插入的数据(-1结束):");
			while (scanf("%d", &item), item != -1)//这个是 ","表达式，即逗号表达式，输入的数据，最终判断true或false，是看","后面的最后一个表达式的真或假
			{
				push_back(&mylist, item);
			}
			break;
		case 2:
			printf("请输入要进行头插的数据(-1结束):");
			while (scanf("%d", &item), item != -1)//这个是 ","表达式，即逗号表达式，输入的数据，最终判断true或false，是看","后面的最后一个表达式的真或假
			{
				push_front(&mylist, item);
			}
			break;
		case 3:
			show_list(&mylist);
			break;//sort
		case 4:
			pop_back(&mylist);
			break;
		case 5:
			pop_front(&mylist);
			break;
		case 6:
			printf("请输入要插入的数据:>");
			scanf("%d", &item);
			printf("请输入要插入的位置:>");
			scanf("%d", &pos);
			insert_pos(&mylist, pos, item);
			break;
		case 7:
			printf("请输入要查找的数据:>");//只能找到第一次出现的元素，多次出现的还需要再学习
			scanf("%d", &item);
			pos = find(&mylist, item);
			if (pos == -1)
			{
				printf("没有找到该元素");
			}
			else
			{
				printf("元素所在的位置尾：%d\n", pos);
			}
			break;
		case 8:
			printf("顺序表的长度为:%d\n", length(&mylist));
			break;

		case 9:
			printf("请输入要删除数据的位置:");
			scanf("%d", &pos);
			delete_pos(&mylist, pos);
			break;

		case 10:
			printf("请输入要删除的数据:");
			scanf("%D", &item);
			delete_val(&mylist, item);
			break;
		case 11:
			sort(&mylist);
			break;
		case 12:
			reverse(&mylist);
			break;
		case 13:
			clear(&mylist);
			break;
			//case 14:
				//destory(&mylist);
				//break;
		default:
			printf("输入的选择错误，请重新输入");
			break;
		}
	}
	destory(&mylist);//一旦程序退出，那么我们就会把之前所malloc申请的空间和结构一一还给系统释放掉。
}



//2.合并mylist和youlist成list
void main()
{
	SeqList mylist,yourlist,list;
	InitSeqList(&mylist);
	InitSeqList(&yourlist);

	push_back(&mylist, 1);
	push_back(&mylist, 3);
	push_back(&mylist, 5);
	push_back(&mylist, 7);
	push_back(&mylist, 9);

	push_back(&yourlist, 2);
	push_back(&yourlist, 4);
	//push_back(&yourlist, 6);
	push_back(&yourlist, 8);
	//push_back(&yourlist, 10);

	merge(&list, &mylist, &yourlist);
}