数据结构之线性表的顺序示意与实现

数据结构之线性表的顺序表示与实现

以下代码中包含了线性表的顺序表示与实现，包含元素的查找与删除，元素的添加，以及两个线性表合并，全部参考于《数据结构》

仅供参考

**************************************************************
*  声明：本文所有内容均为原创，转载请声明出处                *
*  blog: http://blog.****.net/weixingstudio                  *
*  watkins.song                                              *
**************************************************************

// SeqList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "iostream"

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 50

typedef int DataType;
using namespace std;

typedef struct
{
	DataType *data;
	int length;
	int ListSize;
}SeqList;

int InitList_Seq(SeqList &L);
int ListInsert_Seq(SeqList &L,int i, DataType e);
int ListDelete_Seq(SeqList &L, int i, DataType &e);
int LocateElem_Seq(SeqList L, DataType e, int (*compare)(DataType, DataType));
int compare_elem(DataType a, DataType b);
void MergeList_Seq(SeqList la, SeqList lb, SeqList &lc);

int _tmain(int argc, _TCHAR* argv[])
{
	int source[10]={102,88,2,34,17,97,23,89,55,10};
	SeqList L; // 定义一个顺序表
	InitList_Seq(L); // 初始化顺序表
	for(int i=1;i<=10;i++)
	{
		ListInsert_Seq(L,i,source[i-1]);
		printf("%5d",source[i-1]);
	}
	printf("\n");
	for(int i=1;i<=L.length;i++)
	{
		printf("%5d",L.data[i-1]);
	}
	printf("\n");

	// 删除一个元素测试
	DataType e;
	ListDelete_Seq(L,10,e);
	for(int i=1;i<=L.length;i++)
	{
		printf("%5d",L.data[i-1]);
	}
	printf("\n");

	// 查找指定元素的位置
	int (*compare)(DataType, DataType)=compare_elem; // 定义一个指向函数的指针
	int tobefound=2;
	int position=LocateElem_Seq(L,tobefound,compare);
	printf("the position of 2 is :%3d\n", position);

	// 合并两个已经排好序的顺序线性表
	SeqList la;
	InitList_Seq(la);
	SeqList lb;
	InitList_Seq(lb);
	SeqList lc;
	InitList_Seq(lc);
	int sa[5]={7,18,89,201,222};
	int sb[7]={1,8,19,72,111,234,444};
	for(int i=1;i<=5;i++)
	{
		ListInsert_Seq(la,i,sa[i-1]);
	}
	for(int i=1;i<=7;i++)
	{
		ListInsert_Seq(lb,i,sb[i-1]);
	}
	MergeList_Seq(la,lb,lc);
	printf("/////////////////////////////////////////////////////////////////\n");
	printf("merged list\n");
	for(int i=0;i<lc.length;i++)
	{
		printf("%4d",lc.data[i]);
	}
	getchar();
	return 0;
}

// 初始化顺序表
int InitList_Seq(SeqList &L)
{
	// 分配一个空的线性表空间
	L.data=(DataType *)malloc(LIST_INIT_SIZE * sizeof(DataType));
	if(!L.data)
	{
		// 分配空间失败
		return 0;
	}
	L.length=0;
	L.ListSize=LIST_INIT_SIZE;
	return 1; // 分配空间成功
}

// 在指定位置插入元素, 指定的位置为1-n，对于用户来说，数组从1开始
// 插入元素后，需要将后面的所有元素向后移动
int ListInsert_Seq(SeqList &L,int i, DataType e)
{
	// 如果插入位置在最后一个元素之后, 则直接插入，不用移动元素
	if(i==L.length+1)
	{
		L.data[i-1]=e;
		L.length++;
		return 1;
	}
	// 判断插入位置是否合法,在第i个元素之前插入数据
	if(i<1||i>L.length) 
	{
		// 插入位置出错
		return 0;
	}
	// 当前存储空间已满，分配新的存储空间
	if(L.length>=L.ListSize)
	{
		DataType *newbase;
		newbase=(DataType *)realloc(L.data,(L.ListSize+LIST_INCREMENT)*sizeof(DataType));
		if(!newbase)
		{
			// 新的储存空间分配失败
			return 0;
		}
		L.data=newbase;
		L.ListSize+=LIST_INCREMENT;
	}
	// 获取插入位置
	DataType *q=&(L.data[i-1]);
	DataType *p; // 最初指向最后以后元素 
	for(p=&(L.data[L.length-1]);p>=q;--p)
	{
		*(p+1)=*p; // 将数组元素向后移动
	}
	// 插入指定的元素
	*q=e;
	L.length++;
	return 1;
}

// 在顺序表中删除指定位置的元素
// 通过DataType &e 引用类型返回删除的元素的值
// 删除元素之后需要将被删除元素后面的所有元素向前移动
int ListDelete_Seq(SeqList &L, int i, DataType &e)
{
	// 判断删除元素的指定位置是否合法
	if(i<1||i>L.length)
	{
		return 0;
	}
	// 判断是否是最后一个元素，也可以不进行判断，不进行判断的程序也是正确的
	if(i==L.length)
	{
		DataType *p=&(L.data[i-1]);//指向被删除的元素
		e=*p;
		--L.length;
		return 1;
	}
	DataType *p=&(L.data[i-1]);//指向被删除的元素
	e=*p;
	DataType *q=L.data+L.length-1; // 指向最后一个元素
	for(++p;p<=q;++p)
	{
		*(p-1)=*p; // 将元素向前移动
	}
	--L.length;
	return 1;
}

// 查找指定的元素
int LocateElem_Seq(SeqList L, DataType e, int (*compare)(DataType, DataType))
{
	// 
	int i=1;
	DataType *p=L.data; // 指向第一个元素
	while(i<=L.length&&!(*compare)(*p++,e)) // 通过指向函数的指针调用函数
	{
		// 继续查找下一个元素
		++i;
	}
	if(i<=L.length)
	{
		return i; 
	}
	else
	{
		return -1; // 找不到返回-1
	}
}

// 比较函数
int compare_elem(DataType a, DataType b)
{
	// 比较数据
	if(a==b)
		return 1;
	else
		return 0;
}

// 合并两个顺序线性表
// 合并以后的线性表按照非递减的顺序排列
void MergeList_Seq(SeqList la, SeqList lb, SeqList &lc)
{
	// 对两个顺序表进行合并，并返回lc
	DataType *pa=la.data; // 指向la的数据的指针
	DataType *pb=lb.data;
	lc.ListSize=lc.length=la.length+lb.length;
	DataType *pc=lc.data=(DataType *)malloc(lc.ListSize*sizeof(DataType));
	if(!lc.data) return;
	DataType *pa_last=la.data+la.length-1;
	DataType *pb_last=lb.data+lb.length-1;
	while(pa<=pa_last&&pb<pb_last)
	{
		if(*pa<=*pb) *pc++=*pa++;
		else *pc++=*pb++;
	}
	while(pa<=pa_last) *pc++=*pa++;
	while(pb<=pb_last) *pc++=*pb++;
}