C语言顺序表

偏执的太偏执、 2024-03-31 12:53 102阅读 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