欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构_数据结构_数据结构_数据结构_初级_顺序表_静态

程序员文章站 2024-03-20 14:24:46
...


代码实现顺序表的操作函数 

// 值类型 
typedef int DataType; 

typedef struct SeqList { 
DataType data; // 值 
int size; // 数量 
} SeqList; 

// 初始化 
void SeqListInit(SeqList *pSL); 

// 尾部插入 
void SeqListPushBack(SeqList *pSL, DataType data); 

// 头部插入 
void SeqListPushFront(SeqList *pSL, DataType data); 

// 尾部删除 
void SeqListPopBack(SeqList *pSL); 

// 头部删除 
void SeqListPopFront(SeqList *pSL); 

// 按下标插入,pos 的范围是 [0, size] 
void SeqListInsert(SeqList *pSL, int pos, DataType data); 

// 按下标删除,pos 的范围是 [0, size) 
void SeqListErase(SeqList *pSL, int pos); 

// 按值删除,只删遇到的第一个 
void SeqListRemove(SeqList *pSL, DataType data); 

// 按值删除,删除所有的 
void SeqListRemoveAll(SeqList *pSL, DataType data); 

// 清空 
void SeqListClear(SeqList *pSL); 

// 按值查找,返回第一个找到的下标,如果没找到,返回 -1 
int SeqListFind(SeqList *pSL, DataType data); 

// 判断是否为空,1 表示空, 0 表示不空 
int SeqListEmpty(SeqList *pSL); 

// 返回数量 
int SeqListSize(SeqList *pSL); 

// 销毁 
void SeqListDestroy(SeqList *pSL);


test.h

#pragma once

#include<stdio.h>
#include<windows.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>



typedef int DataType;
#define MAX_SIZE	(100)

typedef struct SeqList {
	DataType array[MAX_SIZE];	// 存数据的空间
	int size;		// 1) 有效数据有多少个 2) 当前可用的数组下标
}	SeqList;


// 初始化
void SeqListInit(SeqList *pSL);
// 销毁
void SeqListDestroy(SeqList *pSL);

// 增删改查
// 增
// 尾插
void SeqListPushBack(SeqList *pSL, DataType data);
// 头插
void SeqListPushFront(SeqList *pSL, DataType data);
// 根据下标插入
void SeqListInsert(SeqList *pSL, int pos, DataType data);

// 删
// 尾删
void SeqListPopBack(SeqList *pSL);
// 头删
void SeqListPopFront(SeqList *pSL);
// 根据下标删除
void SeqListErase(SeqList *pSL, int pos);

// 根据数据删除,只删除遇到的第一个
void SeqListRemove(SeqList *pSL, DataType data);

// 根据数据删除,删除所有遇到的
void SeqListRemoveAll(SeqList *pSL, DataType data);

// 根据下标更新
void SeqListUpdate(SeqList *pSL, int pos, DataType data);

// 查询
// 返回遇到的第一个下标,如果没有遇到,返回 -1
int SeqListFind(SeqList *pSL, DataType data);
//输出打印
void SeqListprint(SeqList *pSL);


void SeqListInit(SeqList *pSL)
{
	//内容初始化
	//size=0
	assert(pSL != NULL);
	memset(pSL->array, 0, MAX_SIZE*sizeof(DataType));
	pSL->size = 0;
}
void SeqListDestroy(SeqList *pSL)
{
	assert(pSL != NULL);
	pSL->size = 0;

}
// 尾插
void SeqListPushBack(SeqList *pSL, DataType data)
{
	assert(pSL != NULL);
	assert(pSL->size < MAX_SIZE);
	pSL->array[pSL->size] = data;
	pSL->size++;
}
//头插
void SeqListPushFront(SeqList *pSL, DataType data)
{
	assert(pSL != NULL);
	assert(pSL->size < MAX_SIZE);
	//将已有数据往后搬移
	//以条件写循环
#if 0
	//1.1以要搬移的数做循环的指示
	int pose;
	for (pose = pSL->size-1; pose >= 0; pose--)
	{
		pSL->array[pose + 1] = pSL->array[pose];
	}
#endif
//#if 0
	//以要搬到的位置做循环指示
	int space;
	for (space = pSL->size; space > 0; space--)
	{
		pSL->array[space] = pSL->array[space-1];
	}
//#endif
	/*int i = 0;
	for (i = 0; i < pSL->size; i++)
	{
		pSL->array[pSL->size - i] =pSL->array[pSL->size - 1 - i];
	}*/
	pSL->array[0] = data;
	pSL->size++;
}
//根据下标插入
void SeqListInsert(SeqList *pSL, int pos, DataType data)
{
	assert(pSL!=NULL);
	assert(pSL->size < MAX_SIZE);
	assert(pos>0 && pos < pSL->size);
	//把[pose,size)数据往后搬移一个(从后往前)
	int space;
	for (space = pSL->size; space>pos; space--)
	{
		pSL->array[space] = pSL->array[space-1];
	}
	pSL->array[pos] = data;
	pSL->size++;
}

// 删
// 尾删
void SeqListPopBack(SeqList *pSL)
{
	assert(pSL != NULL);
	assert(pSL->size > 0);
		pSL->size--;
}
// 头删
void SeqListPopFront(SeqList *pSL)
{
	assert(pSL != NULL);
	assert(pSL->size > 0);
	//把 [1, pSL->size) 的数据往前搬移一格
	int pos;
	for (pos = 1; pos< pSL->size; pos++)
	{
		pSL->array[pos-1] = pSL->array[pos];
	}
	pSL->size--;
}
// 根据下标删除
void SeqListErase(SeqList *pSL, int pos)
{
	assert(pSL != NULL);
	assert(pSL->size < MAX_SIZE);
	assert(pos>=0 && pos < pSL->size);
#if 0	// 以 要搬运到的位置下标作为循环指示
	// 要搬运到的位置下标
	int space;
	for (space = pos; space < pSL->size-1; space++)
	{
		pSL->array[space] = pSL->array[space + 1];
	}
#endif	pSL->size--;

	// 以 要搬运的数据下标作为循环指示
	int p;	// 要搬运的数据下标
	for (p = pos + 1; p < pSL->size; p++)//从后往前
	{
		pSL->array[p - 1] = pSL->array[p];
	}
	pSL->size--;
}

// 根据数据删除,只删除遇到的第一个
void SeqListRemove(SeqList *pSL, DataType data)
{
	assert(pSL != NULL);
	assert(pSL->size < MAX_SIZE);
	int pos = SeqListFind(pSL, data);
	if (pos != -1)
	{
		SeqListErase(pSL, pos);//根据下标删除
	}
}



// 根据数据删除,删除所有遇到的
void SeqListRemoveAll(SeqList *pSL, DataType data)
{
	assert(pSL != NULL);
	assert(pSL->size < MAX_SIZE);
#if 0
	while (1)
	{
		int pos = SeqListFind(pSL, data);
		if (pos == -1)
		{
			break;
		}
		SeqListErase(pSL, pos);//根据下标删除
	}//时间复杂度大
#endif 

#if 0	
	int pos;
	while ((pos = SeqListFind(pSL, data)) != -1)//不等于-1表示找到了
	{
		SeqListErase(pSL, pos);//根据下标删除
	}
#endif
	
#if 0
	int i, j;
	for (i = 0, j = 0; i < pSL->size; i++)
	{
		if (pSL->array[i] != data)
		{
			pSL->array[j] = pSL->array[i];
			j++;
		}
	}
	pSL->size=j;
#endif
	DataType *NewArray = (DataType*)malloc(sizeof(DataType)*pSL->size);
	assert(NewArray);
	int i, j, k;
	for (i = 0, j = 0; i < pSL->size; i++)
	{
		if (pSL->array[i] != data)
		{
			NewArray[j] = pSL->array[i];
			j++;
		}
	}
	pSL->size = j;
	// 把数据从 newArray 放回到 array
	for (k = 0; k < pSL->size; k++)
	{
		pSL->array[k] = NewArray[k];
	}
	free(NewArray);
}

// 根据下标更新
void SeqListUpdate(SeqList *pSL, int pos, DataType data)
{
	assert(pSL != NULL);
	assert(pos >= 0 && pos < pSL->size);
	pSL->array[pos] = data;
}

// 查询
// 返回遇到的第一个下标,如果没有遇到,返回 -1
int SeqListFind(SeqList *pSL, DataType data)
{
	assert(pSL != 0);
	int i;
	for (i = 0; i < pSL->size; i++)
	{
		if (pSL->array[i] == data)
		{
			return i;
		}
	}
	return -1;
}
void SeqListprint(SeqList *pSL)
{
	int i = 0;
	for (i = 0; i < pSL->size; i++)
	{
		printf("%d  ",pSL->array[i]);
	}
	printf("\n");
}



void TestSeqList()
{
	SeqList s1;
	SeqListInit(&s1);
	SeqListDestroy(&s1);
	//尾插
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListprint(&s1);
	//头插
    SeqListPushFront(&s1, 5);
	SeqListPushFront(&s1, 6);
	SeqListPushFront(&s1, 7);
	SeqListPushFront(&s1, 8);
	SeqListprint(&s1);
	//根据下标插入
	SeqListInsert(&s1, 2,0);
	SeqListprint(&s1);
	//尾删
	SeqListPopBack(&s1);
	SeqListprint(&s1);
	//头删
	SeqListPopFront(&s1);
	SeqListprint(&s1);
	// 根据下标删除
	SeqListErase(&s1, 2);
	SeqListprint(&s1);
	//查询
	SeqListFind(&s1, 7);
	// 根据下标更新
	SeqListUpdate(&s1, 2, 78);
	SeqListprint(&s1);

	// 根据数据删除,只删除遇到的第一个
	SeqListRemove(&s1, 7);
	SeqListprint(&s1);

	// 根据数据删除,删除所有遇到的
	SeqListRemoveAll(&s1, 78);
	SeqListprint(&s1);


	SeqListDestroy(&s1);


}

main.c


#include "test.h"

int main()
{
	 TestSeqList();
	system("pause");
	return 1;
}