【数据结构】线性表之顺序存储结构

代码如下：

公共头文件common.h

#ifndef __HI_COMM_H__
#define __HI_COMM_H__
 
 
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <string>
 
#define LIST_INIT_SIZE 100  /*线性表存储空间的初始分配量；*/
#define LIST_INCREMENT 10   /*线性表存储空间的分配增量；*/
#define ElemType int
//#define NULL (void*)0
 
/*线性表的顺序存储结构*/
typedef struct{
	ElemType *elem;  //线性表的基地址
	int length;      //当前长度
	int MaxSize;    //当前分配的存储容量
}sqlist;
 
/*线性表的链式存储结构*/
typedef struct frankLNode
{
	ElemType data;
	struct frankLNode* next; 
}LNode;   //
 
 
/*栈的顺序存储结构*/
typedef struct 
{
	ElemType* base;
	ElemType* top;
	int StackSize;
}FStack;
#define STACK_INIT_SIZE 100  /*栈存储空间的初始分配量；*/
#define STACK_INCREMENT 10   /*栈存储空间的分配增量；*/
 
 
/*队列的顺序存储结构*/
typedef struct frankQNode
{
	ElemType data;
	struct frankQNode *next;
}QNode;
 
typedef struct frankQueueHeader
{
	QNode* front;
	QNode* rear;
}QueueHeader;
 
/*二叉树的存储结构*/
 
typedef struct frankBinTreeNode
{
	ElemType data;
	struct frankBinTreeNode *left;
	struct frankBinTreeNode *right;
}BinTreeNode;
typedef BinTreeNode* pBinTreeNode;
 
 
#endif

数据结构算法的实现

头文件LinearList.h

#pragma once
#include "common.h"
 
class LinearList
{
public:
	LinearList(void);
	~LinearList(void);
 
 
 
	int InitList(sqlist *L);
 
	int DestroyList(sqlist *L);
 
	int ClearList(sqlist *L);
 
	bool isListEmpty(sqlist *L);
 
	int getListLength(sqlist *L);
 
	//给定一个序号，去查找这个序号对应的元素值；
	ElemType getElem(sqlist *L,int index);
 
	//从列表中找到某一元素的位置
	int locateElem(sqlist *L,ElemType Q);
 
	ElemType PriorElem(sqlist *L,ElemType Cur_e);
 
	ElemType NextElem(sqlist *L,ElemType Cur_e);
 
	int AgainMalloc(sqlist *L);
 
	sqlist* ListInsert(sqlist *L,int index,ElemType e);
 
	void ListDelete(sqlist *L,ElemType &e);
 
	sqlist* ChangeElem(sqlist *L,ElemType e);
 
	void Printsqlist(sqlist *L);
 
	sqlist* ListAdd(sqlist *L,ElemType e);
 
	void MergeList(sqlist La,sqlist Lb,sqlist &Lc);
};

数据结构算法实现：

NodeList.cpp

#include "LinearList.h"
 
LinearList::LinearList(void)
{
}
 
LinearList::~LinearList(void)
{
}
 
int LinearList::InitList(sqlist *L)
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!L->elem)
	{
		return -1;
	}
	L->length = 0;
	L->MaxSize = LIST_INIT_SIZE;
	return 0;
}
 
int LinearList::DestroyList(sqlist *L)
{
	if (L == NULL)
	{
		exit(1);
	}
 
	free(L);
	L = (sqlist *)0;
	return 0;
}
 
int LinearList::ClearList(sqlist *L)
{
	if (L == NULL)
	{
		exit(1);
	}
	free(L->elem);
	L->elem = (ElemType*)0;
	L->MaxSize = 0;
	L->length = 0;
	return 0;
}
 
bool LinearList::isListEmpty(sqlist *L)
{
	if (L == NULL)
	{
		exit(1);
	}
	if (L->MaxSize == 0)
	{
		return true;
	}else
	{
		return false;
	}
}
 
int LinearList::getListLength(sqlist *L)
{
	if (L == NULL)
	{
		exit(1);
	}
 
	return L->length;
}
 
//给定一个序号，去查找这个序号对应的元素值；
ElemType LinearList::getElem(sqlist *L,int index) 
{
	if (L == NULL)
	{
		exit(1);
	}
	else if (index<0 || index>L->length)
	{
		printf("wrong index number in Function getElem!\n");
 
	}
	return L->elem[index];
	
}
 
//从列表中找到某一元素的位置
int LinearList::locateElem(sqlist *L,ElemType e)
{
	if (L == NULL)
	{
		exit(1);
	}
 
	for (int i = 0;i<L->length;i++)
	{
		if (L->elem[i] == e)
		{
			return i+1;
		}
	}
	return -1;
}
 
ElemType LinearList::PriorElem(sqlist *L,ElemType Cur_e)
{
	if (L == NULL)
	{
		exit(1);
	}
	for (int i = 1 ;i<L->length; i++)
	{
		if (L->elem[i] == Cur_e)
		{
			return L->elem[i-1];
		}
	}
	exit(1);
}
 
ElemType LinearList::NextElem(sqlist *L,ElemType Cur_e)
{
	if (L == NULL)
	{
		exit(1);
	}
	for (int i = 0 ;i<L->length-1; i++)
	{
		if (L->elem[i] == Cur_e)
		{
			return L->elem[i+1];
		}
	}
	exit(1);
}
 
int LinearList::AgainMalloc(sqlist *L)
{
	ElemType* p = (ElemType*)malloc((L->MaxSize + LIST_INCREMENT ) * sizeof(ElemType));
	if (!p)
	{
		printf("Malloc Again Fail\n");
		exit(1);
	}
	memcpy(p,L->elem,sizeof(L->elem)*L->MaxSize); //之前遗漏这一句，注意，要把以前的元素拷贝过来
	L->elem = p;
	L->MaxSize = L->MaxSize + LIST_INCREMENT; 
	return 0;
}
 
sqlist* LinearList::ListInsert(sqlist *L,ElemType e)
{
	if (L == NULL)
	{
		exit(1);
	}
	if (index<0||index>L->length)
	{
		printf("index error in function ListInsert\n");
		exit(1);
	}
 
	if (L->length == L->MaxSize)
	{
		//重新分配更大的空间
		AgainMalloc(L);
	}
	for (int i = L->length+1; i>index; i--)
	{
		L->elem[i]=L->elem[i-1];
	}
	L->elem[index] = e;
	L->length = L->length + 1;
	return L;
}
 
sqlist* LinearList::ListAdd(sqlist *L,ElemType e)
{
	if (L == NULL)
	{
		exit(1);
	}
 
	if (L->length == L->MaxSize)
	{
		//重新分配更大的空间
		AgainMalloc(L);
	}
	
	L->elem[L->length]=e;
	L->length = L->length + 1;
	return L;
}
 
void LinearList::ListDelete(sqlist *L,ElemType &e)
{
	if (L == NULL)
	{
		exit(1);
	}
	if (index<0 || index>=L->length)
	{
		printf("index error in function ListDelete\n");
		exit(1);
	}
 
	for (int i = index; i< L->length-1; i++)
	{
		L->elem[i] = L->elem[i+1];
	}
	L->length = L->length - 1;
	e = L->elem[index];
}
 
sqlist* LinearList::ChangeElem(sqlist *L,ElemType e)
{
	if (L == NULL)
	{
		exit(1);
	}
	if (index<0 || index>=L->length)
	{
		printf("index error in function ListDelete\n");
		exit(1);
	}
	L->elem[index] = e;
	return L;
 
}
 
void LinearList::Printsqlist(sqlist *L)
{
	if (L == NULL)
	{
		exit(1);
	}
 
	for (int i = 0; i< L->length; i++)
	{
		printf("sqlist[%d]:%d  ",i,getElem(L,i));
	}
	printf("\n");
}
 
//归并;
void LinearList::MergeList(sqlist La,sqlist &Lc)
{
	Lc.elem = (ElemType *)malloc((La.length + Lb.length) * sizeof(ElemType));
	if (!Lc.elem)
	{
		exit(1);
	}
 
	ElemType* pa = La.elem;
	ElemType* pb = Lb.elem;
	ElemType* pc = Lc.elem;
	ElemType* pa_last = La.elem + La.length - 1;
	ElemType* pb_last = Lb.elem + 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++;
	}
}

测试：

void TEST_LinearList()
{
	printf("-----------------------------------------------------\n");
	printf("-------Here is A Test For LinearList-----------------\n");
 
	sqlist* L = (sqlist *)malloc(sizeof(sqlist));
	LinearList linearLIST;
	linearLIST.InitList(L);
	int i;
	printf("Add Elem!\n");
	for (i = 0;i<10;i++)
	{
		linearLIST.ListAdd(L,i);
	}
	linearLIST.Printsqlist(L);
 
	linearLIST.isListEmpty(L);
 
	int k = linearLIST.locateElem(L,5);
 
	sqlist* Q =  linearLIST.ListInsert(L,5,123);
	linearLIST.Printsqlist(L);
	linearLIST.Printsqlist(Q);
 
	ElemType e;
	linearLIST.ListDelete(L,8,e);
	linearLIST.Printsqlist(L);
}

说明：代码仅供参考，有错误的还望指正。

【数据结构】线性表之顺序存储结构

猜你在找的数据结构相关文章