线性表之顺序表

线性表之顺序表（C++版）http://t.csdn.cn/pEmnl

seqlist.h文件包含结构体的定义，函数的声明

#pragma once
#include
#include
#include
#define Initsel 8
#define INC_SIZE 8
typedef int ElemType;//代表当前元素的类型，方便修改
typedef struct SeqList
{
	ElemType* base;//指向一个表,内容
	int capacity;//容量
	int size;//大小
}SeqList;
void InitSeqList(SeqList* list);//初始化
void push_back(SeqList *list,ElemType val);//尾插
void Show(SeqList* list);//显示
void push_front(SeqList* list, ElemType val);//头插
void pop_back(SeqList *list);//尾删
void pop_front(SeqList* list);//头删
void inser_pos(SeqList* list, int val,int pos);//按位置插入
int find(SeqList* list, int val);//按值查找
int length(SeqList* list);//长度
void delete_pos(SeqList* list, int pos);//按位置删除
int delete_val(SeqList* list, int val);//按值删除
void sort(SeqList* list);//排序
void reverse(SeqList* list);//逆序
void swap(int& a, int& b);//交换函数
void clear(SeqList* list);//清空
void destroy(SeqList* list);//销毁
bool Inc(SeqList* list);//增加空间

list.cpp文件，顺序表的初始化以及函数实现

#include"seqlist.h"
 
//初始化
void InitSeqList(SeqList* list)
{
	list->base = (ElemType*)malloc(sizeof(ElemType) * Initsel);
	assert(list->base != NULL);
	list->capacity = Initsel;
	list->size = 0;
}
 
//增加空间
bool Inc(SeqList* list)
{
	ElemType *newbase  = (ElemType*)realloc(list->base, sizeof(ElemType) * list->capacity+INC_SIZE);
	if (newbase == NULL)
	{
		printf("增容失败\n");
		return false;
	}
	list->base = newbase;
	list->capacity += INC_SIZE;
	return true;
}
 
//尾插
void push_back(SeqList* list, ElemType val)
{
	if (list->size >= list->capacity&& !Inc(list))
	{
		printf("顺序表满了，不能尾插\n");
		return;
	}
	list->base[list->size] = val;
	list->size++;
 
}
 
//头插
void push_front(SeqList* list, ElemType val)
{
	if (list->size >= list->capacity && !Inc(list))
	{
		printf("顺序表满了，不能头插\n");
		return;
	}
	for (int i = list->size; i > 0; --i)
	{
		list->base[i] = list->base[i - 1];
	}
	list->base[0] = val;
	list->size++;
}
 
//显示
void Show(SeqList* list)
{
	assert(list != NULL);
	for (int i = 0; i < list->size; i++)
	{
		printf("%d ", list->base[i]);
	}
	printf("\n");
}
 
//尾删
void pop_back(SeqList* list)
{
	assert(list != NULL);
	list->size--;
}
 
//头删
void pop_front(SeqList* list)
{
	//把后面的数据移到前面
	for (int i = 1; i < list->size; ++i)
	{
		list->base[i - 1] = list->base[i];
	}
	list->size--;
}
 
//随机插入一个数
void inser_pos(SeqList* list, int val, int pos)
{
	//判断位置是否合法
	if (pos<0 || pos>list->size)return;
	if (list->size == list->capacity && !Inc(list))
	{
		return;
	}
	for (int i = list->size; i > pos; --i)
	{
		list->base[i] = list->base[i - 1];
	}
	list->base[pos] = val;
	list->size++;
}
 
//按值查找
int find(SeqList* list, int val)
{
	if (list->size == 0)return -1;
	for (int i = 0; i < list->size; ++i)
	{
		if (list->base[i] == val) return i;
	}
	return -1;
}
 
//长度
int length(SeqList* list)
{
	return list->size;
}
 
//按位置删除
void delete_pos(SeqList* list, int pos)
{
	if (pos<0||pos >= list->size)return ;
	for (int i = pos; i < list->size-1; i++)
	{
		list->base[i] = list->base[i + 1];
	}
	list->size--;
}
 
//按值删除
int delete_val(SeqList* list, int val)
{
	int pos = find(list, val);
	if (pos == -1)
		return -1;
	delete_pos(list, pos);
}
 
//排序
void sort(SeqList* list)//从小到大
{
	for (int i =0; i size-1; ++i)
	{
		for (int j = 0; j < list->size-i-1; j++)
		{
			if (list->base[j] > list->base[j + 1])
			{
				swap(list->base[j], list->base[j + 1]);
			}
		}
	}
}
 
//逆序
void reverse(SeqList* list)
{
	int tmp = 0;
	int left = 0; int right = list->size - 1;
	while (left < right)
	{
		swap(list->base[left], list->base[right]);
		left++;
		right--;
	}
}
 
//交换函数
void swap(int &a, int &b)
{
	int tmp = 0;
	tmp = a;
	a = b;
	b = tmp;
}
 
//清空
void clear(SeqList* list)
{
	list->size = 0;
}
 
//销毁（与清空区别在于销毁要释放空间
void destroy(SeqList* list)
{
	free(list->base);
	list->base = NULL;
	list->capacity = 0;
	list->size = 0;
}

test.cpp测试代码

#include"seqlist.h"
 
int main()
{
	SeqList list;
	int select = 1;
	InitSeqList(&list);
	while (1)
	{
		printf("**********************************\n");
		printf("*[1] init         [2]push_back   *\n");
		printf("*[3] show         [4]push_front  *\n");
		printf("*[5] pop_back     [6]inser_pos   *\n");
		printf("*[7] find         [8]length      *\n");
		printf("*[9] delete_pos   [10]delete_val *\n");
		printf("*[11] sort        [12]reverse    *\n");
		printf("*[13]pop_front    [14]clear      *\n");
		printf("*[0] quit_system  [15]destroy    *\n");
		printf("**********************************\n");
		printf("请输入选项:");
		scanf_s("%d",&select);
		int val = 0;//值
		int pos = 0;//位置 
		if (select == 0)
			break;
		switch (select)
		{
		case 1:
			InitSeqList(&list);
			break;
		case 2:
			printf("请输入要插入的数，以-1结束:\n");
			while (scanf_s("%d", &val),val != -1)
			{
				push_back(&list, val);//尾插
			}
			break;
		case 3:
			Show(&list);
			break;
		case 4:
			printf("请输入要插入的数，以-1结束:\n");
			while (scanf_s("%d", &val), val != -1)
			{
				push_front(&list, val);//头插
			}
			break;
		case 5:
			pop_back(&list);//尾删
			break;
		case 6:
			printf("请输入插入的数据及位置：");
			scanf_s("%d %d", &val, &pos);
			inser_pos(&list,val,pos);
			break;
		case 7:
			printf("请输入查找的数据：");
			scanf_s("%d", &val);
			pos = find(&list, val);
			if (pos== -1)//按值查找
			{
				printf("%d没有找到\n",val);
			}
			else
			{
				printf("%d找到了，下标为%d\n",val,pos);
			}
			break;
		case 8:
			pos= length(&list);//长度
			printf("顺序表的长度为%d\n", list.size);
			break;
		case 9:
			printf("请输入删除的位置：");
			scanf_s("%d", &pos);
			delete_pos(&list,pos);//按位置删除
			break;
		case 10:
			printf("请输入要删的值:");
			scanf_s("%d", &val);
			delete_val(&list,val);//按值删除
			break;
		case 11:
			sort(&list);//排序
			break;
		case 12:
			reverse(&list);//逆序
			break;
		case 13:
			pop_front(&list);//头删
			break;
		case 14:
			clear(&list);//清空
			break;
		case 15:
			destroy(&list);//销毁
			break;
		default:
			printf("输入错误，请重新输入:\n");
			break;
		}
	}
	destroy(&list);//销毁
	return 0;
}