首页 > 其他 > 详细

简易静态顺序表

时间:2016-03-02 07:02:23      阅读:148      评论:0      收藏:0      [点我收藏+]

        顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。

        顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中


任务要求:实现一个简易静态顺序表

功能要求:可以进行尾插元素,尾删元素,头插元素,头删元素,在指定位置插入指定元素,删除指                   定元素,删除所有指定的元素,给表进行排序,进行二分查找,翻转表。


【代码实现】

//SeqList.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

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

#define MAX 100
typedef int DataType;

typedef struct SeqList
{
	DataType arr[MAX];
	int size;
}SeqList, *pSeqList;

void InitList(pSeqList pSeq);
void Print(SeqList MySeq);
void PushBack(pSeqList pSeq, DataType x);
void PopBack(pSeqList pSeq);
void PushFront(pSeqList pSeq, DataType x);
void PopFront(pSeqList pSeq);
void Insert(pSeqList pSeq, int pos, DataType x);
void Remove(pSeqList pSeq, DataType x);
int Find(pSeqList pSeq, DataType x);
void Erase(pSeqList pSeq,int pos);
void RemoveAll(pSeqList pSeq, DataType x);
void ReverseList(pSeqList pSeq);
void SortList(pSeqList pSeq);
int BinarySearch(SeqList Seq, DataType x);

#endif// __SEQLIST_H__


//SeqList.c

#include "SeqList.h"

void InitList(pSeqList pSeq)  //初始化表
{
	memset(pSeq->arr, 0, sizeof(pSeq->size));
	pSeq->size = 0;
}

void PushBack(pSeqList pSeq, DataType x)  //尾插
{				 
	if (pSeq->size >= MAX)
	{
		printf("顺序表已满!!!\n");
		return;
	}
	pSeq->arr[pSeq->size++] = x;
}

void PopBack(pSeqList pSeq)	 //尾删
{
	if (pSeq->size == 0)
	{
		printf("顺序表已空\n");
		return;
	}
	pSeq->size--;
}

void PushFront(pSeqList pSeq, DataType x) //头插
{
	int i;
	if (pSeq->size == MAX)
	{
		printf("顺序表已满\n");
		return;
	}
	for(i = pSeq->size; i >= 0; i--)
	{
		pSeq->arr[i+1]= pSeq->arr[i];
	}
	pSeq->arr[0] = x;
	pSeq->size++;
}

void PopFront(pSeqList pSeq)  //头删
{
	int i = 0;
	if (pSeq->size == 0)
	{
		printf("顺序表已空\n");
		return;
	}
	for (i=0; i <= pSeq->size; i++)
	{
		pSeq->arr[i] = pSeq->arr[i+1];
	}
	pSeq->size--;
}

void Insert(pSeqList pSeq, int pos, DataType x)	//指定位置插入指定元素
{				 
	int i;
	if (pSeq->size == MAX)
	{
		printf("顺序表已满\n");
		return;
	}
	else
	{
		if (pos > 0 && pos < pSeq->size)
		{
			for(i = pSeq->size; i >= pos; i--)
			{
				pSeq->arr[i+1]= pSeq->arr[i];
			}
			pSeq->arr[pos] = x;
			pSeq->size++;
		}
		else
		{
			printf("请正确输入要插入数的位置,范围(0,%d)\n",pSeq->size);
			return;
		}
	}
}

int Find(pSeqList pSeq, DataType x)	//遍历指定元素
{		
	int i = 0;
	for(i; i<pSeq->size; i++)
	{
		if (pSeq->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void Erase(pSeqList pSeq,int pos)	//删除制定下标元素
{		 
	for(pos; pos<=pSeq->size; pos++)
	{
		pSeq->arr[pos] = pSeq->arr[pos+1];
	}
	pSeq->size--;
}

void Remove(pSeqList pSeq, DataType x) //删除指定元素x
{
	int ret = Find(pSeq, x);
	if (ret == -1)
	{
		printf("顺序表没有%d!!\n", x);
		return;
	}
	Erase(pSeq,ret);
}

void RemoveAll(pSeqList pSeq, DataType x) //删除所有指定元素x
{
	int ret = 0;
	while (-1 != (ret=Find(pSeq, x)))
	{
		Erase(pSeq, ret);
	}
}

void ReverseList(pSeqList pSeq)	 //翻转
{
	int start = 0;
	int end = pSeq->size-1;
	while (start < end)
	{
		DataType tmp = pSeq->arr[start];
		pSeq->arr[start] = pSeq->arr[end];
		pSeq->arr[end] = tmp;
		start++;
		end--;
	}
}

void SortList(pSeqList pSeq) //排序
{
	int i = 0;
	int j = 0;
	for(i=0; i<pSeq->size-1; i++)
	{
		for(j=0; j<pSeq->size-i-1; j++)
		{
			if (pSeq->arr[j]>pSeq->arr[j+1])
			{
				DataType tmp = pSeq->arr[j];
				pSeq->arr[j] = pSeq->arr[j+1];
				pSeq->arr[j+1] = tmp;
			}
		}
	}
}

int BinarySearch(SeqList Seq, DataType x) //二分查找
{
	int left = 0;
	int right = Seq.size - 1;
	while (left<right)
	{
		int mid = (left + (right - left))>1;
		if (Seq.arr[mid] > x)
		{
			right = mid - 1;
		}
		else if(Seq.arr[mid] == x)
		{
			return mid;
		}
		else
		{
			left = mid +1;
		}
	}
}

void Print(SeqList MySeq) //打印表
{
	int i;
	for(i = 0; i < MySeq.size; i++)
	{
		printf("%d ",MySeq.arr[i]);
	}
	printf("\nover\n");
}

void test()
{
	int ret = 0;
	SeqList MySeq;
	InitList(&MySeq);
	Print(MySeq);
	PushBack(&MySeq, 2);
	PushBack(&MySeq, 1);
	PushBack(&MySeq, 4);
	PushBack(&MySeq, 3);
	Print(MySeq);
	PopBack(&MySeq);
	Print(MySeq);
	PushFront(&MySeq, 5);
	Print(MySeq);
	PopFront(&MySeq);
	Print(MySeq);
}

int main()
{					
	test();
	system("pause");
	return 0;
}

本文出自 “Pzd流川枫” 博客,请务必保留此出处http://xujiafan.blog.51cto.com/10778767/1746529

简易静态顺序表

原文:http://xujiafan.blog.51cto.com/10778767/1746529

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!