C语言顺序表

GeekLiHua

发布于 2025-01-21 15:13:09

2800

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

C语言顺序表

简介：本文是我学习数据结构期间，用C语言所写的顺序表。

ASet.h

#ifndef _ASet_h_
#define _ASet_h_

#include "Element.h"

#define ASetInitSize 1024
#define ASetIncrement 128

typedef struct
{
    int size, cardinal;
    ELEMENT *element;
} ASET;

void ASetCreate(ASET *set);
void ASetDestroy(ASET *set);
void ASetResize(ASET *set, int size);
int ASetFind(const ASET *set, const ELEMENT *element);
int ASetExist(const ASET *set, const ELEMENT *element);
void ASetAppend(ASET *set, const ELEMENT *element);
void ASetOutput(const ASET *set);
void ASetRemove(ASET *set, const ELEMENT *element);
void ASetClear(ASET *set);
void ASetInput(ASET *set);
int ASetEmpty(const ASET *set);
int ASetCardinal(const ASET *set);
ASET* ASetAssign(ASET *dst, const ASET *src);
ASET* ASetMul(ASET *dst, const ASET *src1, const ASET *src2);
SET* ASetAdd(ASET *dst, const ASET *src1, const ASET *src2);
ASET* ASetSub(ASET *dst, const ASET *src1, const ASET *src2);
int ASetGt(const ASET *set1, const ASET *set2);
int ASetGe(const ASET *set1, const ASET *set2);
int ASetLt(const ASET *set1, const ASET *set2);
int ASetLe(const ASET *set1, const ASET *set2);
int ASetEq(const ASET *set1, const ASET *set2);
int ASetNe(const ASET *set1, const ASET *set2);
#endif

Aset.c

创建集合

void ASetCreate(ASET *set)
{
	set->size = ASetInitSize;
	set->element = (ELEMENT *) malloc (sizeof (ELEMENT) * set->size);
	set->cardinal = 0;
}

销毁集合

void ASetDestroy(ASET *set)
{
	set->size = 0;
	set->cardinal = 0;
	free(set->element);
	set->element = NULL; 
}

改变动态数组尺寸

void ASetResize(ASET *set, int size)
{
	if (size >= set->cardinal && size != set->size)
	{
		ELEMENT *a;
		a = (ELEMENT *) malloc (sizeof (ELEMENT) * size);
		int i;
		for (i = 0; i < set->cardinal; i++)
		{
			a[i] = set->element[i];
		}
		set->size = size;
		free(set->element);
		set->element = a;
	}
}

查找元素

int ASetFind(const ASET *set, const ELEMENT *element)
{
	int height, lower, half;
	int index = -1;
	height = set->cardinal - 1;
	lower = 0;
	while (lower <= height)
	{
		half = (height + lower) / 2;
		if (ElementEq(&set->element[half], element))
		{
			index = half;
			break;
		}
		else if (ElementGt(&set->element[half], element))
		{
			height = half - 1;
		}
		else if (ElementLt(&set->element[half], element))
		{
			lower = half + 1;
		}
	}
	return index;
}

判断元素

int ASetExist(const ASET *set, const ELEMENT *element)
{
	int i, flag = 0;
	flag = ASetFind(set, element) != -1;
	return flag;
}

添加元素

void ASetAppend(ASET *set, const ELEMENT *element)
{
	if(!ASetExist(set, element)) 
	{
		if (set->cardinal == set->size)
		{
			ASetResize(set, set->size + ASetIncrement);
		}
		int i;
		set->cardinal++;
		for (i = set->cardinal - 1; ElementGt(&set->element[i - 1], element) && i > 0; i--)
		// This step is cruial 
		// The conditions in the set are successfully avoided.
		// When there are on elements in the set, the garbage value cannot be compared
		// Move elements lager than element back to make room for element
		{
			set->element[i] = set->element[i - 1];
		}
		set->element[i] = *element;
	}
}

输出集合

void ASetOutput(const ASET *set)
{
	putchar('{');
	if (set->cardinal == 0)
	{
		putchar (' ');
	}
	int i;
	for (i = 0; i < set->cardinal; i++)
	{
        putchar (' ');
		ElementOutput(&set->element[i]);
		if (i != set->cardinal - 1)
		{
			putchar (',');
		}
	}
	if (set->cardinal)
	{
		putchar(' ');
	}
	putchar ('}');
}

删除元素

void ASetRemove(ASET *set, const ELEMENT *element)
{
	int k = 0;
    for (int i = 0; i < set->cardinal; i++)
    {
        if (ElementEq(&set->element[i], element))
        {
            k++;
        }
        else if (k)
        {
            set->element[i - k] = set->element[i];
        }
    }
    set->cardinal -= k;
}

清空集合

void ASetClear(ASET *set)
{
	set->cardinal = 0;
}

输入集合

/* Input set*/
void ASetInput(ASET *set)
{
	scanf (" {");
	char x;
	ELEMENT element;
	ASetClear (set);
	while (scanf (" %c", &x), x != '}')
	{
		ungetc(x, stdin);
		if (set->cardinal)
		{
			scanf (" ,");	
		}
		if (set->cardinal == set->size)
		{
			ASetResize(set, set->size + ASetIncrement);
		}
		ElementInput(&element);
		ASetAppend(set, &element);
	}
}

判断空集

int ASetEmpty(const ASET *set)
{
	return set->cardinal == 0; 
}

集合基数

int ASetCardinal(const ASET *set)
{
	return set->cardinal; 
}

测试程序(main.c)

#include <stdio.h>
#include <ctype.h>
#include "ASet.h"

int main()
{
	ELEMENT element;
    ASET set;
    ASetCreate(&set);
	char choice;
	do
	{
		printf("E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > ");
		scanf(" %c", &choice);
		choice = toupper(choice);
		switch (choice)
		{
			case 'E':
				puts(ASetEmpty(&set) ? "空集" : "非空集"); 
				break;
			case 'D':
				printf("基数: %d\n", ASetCardinal(&set)); 
				break;
			case 'A':
				printf("元素: ");
				ElementInput(&element);
        		ASetAppend(&set, &element);
				break;
			case 'R':
				printf("元素: ");
				ElementInput(&element);
				ASetRemove(&set, &element);	
				break;
			case 'C':
				ASetClear(&set); 
				break;	
			case 'I':
				printf("集合: ");
				ASetInput(&set);
				break;	
			case 'O':
				printf("集合: ");
				ASetOutput(&set);
				putchar('\n');
				break;
			case 'X':
                printf("元素: ");
				ElementInput(&element);
				puts(ASetExist(&set, &element) ? "存在" : "不存在");
				break;
			case 'Q':
				break;
			default:
				puts("不正确的选项!");
		}
	}
	while(choice != 'Q');
	ASetDestroy(&set);
	return 0;
}

运行结果：

E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > t
不正确的选项!
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > E
空集
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > d
基数: 0
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > I
集合: { 31, 25, 16, 87, 49, 25, 87 }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > o
集合: { 16, 25, 31, 49, 87 }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > A
元素: 54
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > a
元素: 25
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > O
集合: { 16, 25, 31, 49, 54, 87 }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > r
元素: 49
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > R
元素: 18
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > o
集合: { 16, 25, 31, 54, 87 }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > E
非空集
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > d
基数: 5
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > X
元素: 31
存在
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > x
元素: 32
不存在
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > C
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > o
集合: { }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > e
空集
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > D
基数: 0
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > a
元素: 18
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > A
元素: 15
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > a
元素: 37
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > O
集合: { 15, 18, 37 }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > i
集合: { }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > O
集合: { }
E-判空 D-基数 A-添加 R-删除 C-清空 I-输入 O-输出 X-元素 Q-退出 > q

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int