数据结构---动态顺序表

时间：2022-07-08 10:25:23

typedef int DataType;			//数据类型

typedef struct{					//元素结构体
	DataType *data;				//存的数据
	int maxSize, n;				//表的最大容量和数据长度
}SeqList;	



 
接下来给出主要两个操作方法增加和删除元素的实现 

 

1、增加
 

主要思路：插入一个元素时，需要要指定插入的表是哪个，位置在哪，元素是什么。也就是传入的参数
 

a、首先判断要插入的位置是否正确，必须大于或等于1（假设我们把第一个元素的位置叫做1号位置），同时要插入的位置必须小于表的长度，而且要顺序插入，就是必须要连续的不能，第一个有，第二个空，第三个又有。
 

b、如果这时表满了，我们就要分配更多的空间给表（我这里是又分配了100个空间），同时要记得把表容量加上。
 

c、重要的来了，我们怎么插入一个元素，而且还要保证后面的元素呢？很简单，找出要插入的位置把这个位置，包括这个位置的元素全部向后移动一个位置，然后吧我们要的元素放入i这个位置。



图示：
 

假设原来有 ：  
 

 

a  b  c  d  e  f
 

现在有一个x元素要插入到b的位置也就是2号位置x
 

这时先把a后所有的元素向后移动a b  cd e  f
 

 

a  ()  b  c  d  e  f
 

然后吧x放到2号位置  
 

 

a  (x)  b  c  d  e  f
 

 


 

int insert(SeqList *L, int i, DataType x)
{
	DataType *newspace;
	if (i > L->n + 1 || i < 1)								//判断位置是否正确
	{
		printf("插入位子不对\n");
		return 0;
	}

	if (L->n >= L->maxSize)									//如果空间不够再分配100个
	{
		newspace = (DataType *)realloc(L->data, 100 * sizeof(DataType));
		L->data = newspace;
		L->maxSize += 100;
	}

	for (int k = (i-1); k < L->n; k++)						//循环向后插入
	{
		L->data[L->n] = L->data[L->n - 1];
		L->n--;
	}

	L->data[i - 1] = x;
	L->n++;
	return 1;

}
 
2、删除 

 

主要思路：和增加差不多，这里我就简单描述一下
 

a、找出要删除的元素，判断元素和位置是否匹配
 

b、把要删除的元素之后的元素全部向前移动一个位置，就好了



 

int reMove(SeqList *L, int i, DataType x)
{

	int tmp = *(L->data + i-1);					//备份指针
	if (tmp != x)								//如果位子和元素对应不上就错误
	{
		printf("请输入正确的元素\n");
		return 0;
	}
	for (int k = i - 1; k <= L->n - 1; k++)		//循环向前插入
	{
		L->data[k] = L->data[k + 1];
	}
	L->n--;
	return 1;
}
 
备注：当要对指针操作时候必须要备份指针，防止对指针的操作影响后面的指针找不到准缺的位置 

 

最后给出全部代码：
 

 

/*
	作者：何翔宇
	时间：2014年12月3日
	坐标：黑龙江齐齐哈尔大学
	功能：顺序表的增加，删除等
	编译环境：vs2013社区版
	系统：Windows7
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define initSize 100			//初始化表大小
typedef int DataType;			//数据类型

typedef struct{					//元素结构体
	DataType *data;				//存的数据
	int maxSize, n;				//表的最大容量和数据长度
}SeqList;				

void initList(SeqList *L);						//初始化表
int	 insert(SeqList *L, int i, DataType x);		//插入一个数据，i是位置，x是数据
void output(SeqList *L);						//输出表
int  isFull(SeqList *L);						//判断表是否满
int  isEmpty(SeqList *L);						//判断是否为空
int  getLength(SeqList *L);						//得到表长度
int  getElem(SeqList *L, DataType x);			//获得元素位子
int  reMove(SeqList *L, int i, DataType x);		//删除一个元素，i是位置，下是数据
void printMsg();								//打印信息
int getOption();								//获取用户操作

void main()
{
	int op,i,x;
	SeqList L;
	initList(&L);
	printMsg();
	while (op = getOption())
	{
		switch (op)
		{
		case '1':
			printf("请输入位置和元素\n");
			scanf("%d %d", &i,&x);
			_flushall();
			insert(&L, i, x);
			printf("插入元素%d", x);
			break;
		case '2':
			printf("请输入位置和元素\n");
			scanf("%d %d", &i, &x);
			_flushall();
			reMove(&L, i, x);
			printf("删除元素%d\n", x);
			break;
		case '3':
			printf("请输入元素\n");
			scanf("%d", &x);
			_flushall();
			printf("%d", getElem(&L, x));
			break;
		case '4':
			output(&L);
			break;
		case '5':
			printf("%d", isFull(&L));
			break;
		case '6':
			printf("%d", isEmpty(&L));
			break;
		case '7':
			printf("%d", getLength(&L));
			break;
		case '8':
			printf("---byebye----");
			return;
			break;
		default:
			break;
		}
		printf("\n>> ");
	}
	return;

}




void initList(SeqList *L)
{
	L->data = (DataType *)malloc(100 * sizeof(DataType));	//初始化先分配100个空间

	if (!L->data)											//判断是否分配成功
	{
		printf("分配错误\n");
		return;
	}

	L->maxSize = initSize;									//分配大小
	L->n = 0;
}

int insert(SeqList *L, int i, DataType x)
{
	DataType *newspace;
	if (i > L->n + 1 || i < 1)								//判断位置是否正确
	{
		printf("插入位子不对\n");
		return 0;
	}

	if (L->n >= L->maxSize)									//如果空间不够再分配100个
	{
		newspace = (DataType *)realloc(L->data, 100 * sizeof(DataType));
		L->data = newspace;
		L->maxSize += 100;
	}

	for (int k = (i-1); k < L->n; k++)						//循环向后插入
	{
		L->data[L->n] = L->data[L->n - 1];
		L->n--;
	}

	L->data[i - 1] = x;
	L->n++;
	return 1;

}

int isFull(SeqList *L)
{
	return (L->n == L->maxSize) ? 1 : 0;
}

int isEmpty(SeqList *L)
{
	return (L->n == 0) ? 1 : 0;
}

int getLength(SeqList *L)
{
	return L->n;
}
void output(SeqList *L)
{
	DataType *temp = L->data;					//当对指针操作时候必须对指针进行拷贝
	for (int i = 0; i < L->n; i++)
	{
		printf("%d",*(temp++));
	}
	printf("\n");
}

int  getElem(SeqList *L, DataType x)
{
	DataType *temp = L->data;
	for (int i = 0; i < L->n; i++)
	{
		if (*(temp++) == x)
		{
			return i;
		}
	}
	return -1;
}
int reMove(SeqList *L, int i, DataType x)
{

	int tmp = *(L->data + i-1);					//备份指针
	if (tmp != x)								//如果位子和元素对应不上就错误
	{
		printf("请输入正确的元素\n");
		return 0;
	}
	for (int k = i - 1; k <= L->n - 1; k++)		//循环向前插入
	{
		L->data[k] = L->data[k + 1];
	}
	L->n--;
	return 1;
}

void printMsg()
{
	printf("1、插入一个数据\n");
	printf("2、删除一个数据\n");
	printf("3、获得一个元素位子\n");
	printf("4、查看所有数据\n");
	printf("5、查看表是否为满\n");
	printf("6、查看表是否为空\n");
	printf("7、查看表长度\n");
	printf("8、退出\n");
	printf(">> ");
}

int getOption()
{//获取用户输入操作  
	char input;
	scanf("%c", &input);
	_flushall();
	//fflush(stdin);	
	//input=toupper(input);  
	return input;
}




真是的 一贴代码注释都不整齐了 纠结啊 

标签：
相关文章