代码贴--动态顺序表--数据结构

本博客将记录操作系统中的动态顺序表的相关代码

头文件（SeList.h）

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
//动态顺序表

typedef struct SeqList
{
	SQDataType*  a;
	int size;//有效数据的个数
	int capacity;//容量
}SL;//别名，简洁代码
//typedef struct SeqList SL;与上面的代码等价


//初始化、增删查改等接口函数
void SeqListInit(SL* ps);//传地址！

void SeqListPrint(SL* ps);

void SeqListCheckCapacity(SL* ps);

void SeqListDestory(SL* ps);
//尾插 头插 尾删 头删
void SeqListPushBack(SL* ps,SQDataType x);
void SeqListPushFront(SL* ps,SQDataType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
void SeqListInsert(SL* ps, int pos, SQDataType x);
void SeqListErase(SL* ps, int pos);
int SeqListFind(SL* ps, SQDataType x);
void SeqListModity(SL* ps, int pos,SQDataType x);

源文件（SeqList.cpp）

#include"SeqList.h"
#include<iostream>
using namespace std;
//增删查改等接口函数
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//判断空间，增容
void SeqListCheckCapacity(SL* ps)
{
	//满了就扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));//一般情况下，扩容会扩大一倍
		if (tmp == NULL)
		{
			printf(" realloc fail!!!");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//头插
void SeqListPushFront(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps->size> 0);
	ps->size--;
}
//头删
void SeqListPopFront(SL* ps)
{
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}
//指定位置添加
void SeqListInsert(SL* ps, int pos,SQDataType x)
{
	assert(pos < ps->size);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//随机位置删除
void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);
	int start = pos;
	while (start< ps->size)
	{
		ps->a[start] = ps->a[start+1];
		start++;
	}
	ps->size--;
}
//打印
void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		cout<<ps->a[i]<<" ";
	}
	cout << endl;
}
//销毁
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
//查找
int SeqListFind(SL* ps, SQDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		return -1;
	}
}
//更改
void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);
	ps->a[pos] = x;
}

测试文件（Test.cpp）

#include"SeqList.h"
#include<iostream>
using namespace std;

void TestSeqList()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPushBack(&s1, 6);
	SeqListPushBack(&s1, 7);
	SeqListPushBack(&s1, 8);
	SeqListPrint(&s1);

	SeqListPushFront(&s1, 0);
	SeqListPushFront(&s1, -1);
	SeqListPrint(&s1);
	
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPrint(&s1);

	SeqListPopFront(&s1);
	SeqListPopFront(&s1);
	SeqListPrint(&s1);

	SeqListInsert(&s1, 1, 9);
	SeqListPrint(&s1);

	SeqListErase(&s1, 1);
	SeqListPrint(&s1);
	SeqListDestory(&s1);

}
void menu()
{
	cout<<"***********************************************************"<<endl;
	cout<<"1.尾插数据， 2.头插数据"<<endl;
	cout << "3.尾删数据， 4.头删数据" << endl;
	cout<<"5.打印数据， -1.退出"<<endl;
	cout<<"***********************************************************"<<endl;
	cout<<"请输入你的操作选项"<<endl;
}
int main()
{
	SL  s;
	SeqListInit(&s);
	int x = 0;
	int option = 0;
	while (option != -1)
	{
		menu();
		cin >> option;
		switch (option)
		{
		case 1:
			cout<<"请输入你要插入的数据，以-1结束"<<endl;
			do {
				cin >> x;
				if (x != -1)
				{
					SeqListPushBack(&s, x);
				}
			} while (x != -1);
			break;
		case 2:
			cout << "请输入你要插入的数据，以-1结束" << endl;
			do {
				cin >> x;
				if (x != -1)
				{
					SeqListPushFront(&s, x);
				}
			} while (x != -1);
			break;
		case 3:
			SeqListPopBack(&s);
			break;

		case 4:
			SeqListPopFront(&s);
			break;

		case 5:
			SeqListPrint(&s);

			break;

		default:
			break;
		}
	}
	SeqListDestory(&s);

	return 0;
}

代码演示