【数据结构】线性表之链式存储结构

前端之家收集整理的这篇文章主要介绍了【数据结构】线性表之链式存储结构前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

数据结构定义

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

数据结构头文件

NodeList.h

#pragma once
#include "common.h"

class NodeList
{
public:
	NodeList(void);
	~NodeList(void);

	int InitList(LNode **L);

	int DestroyList(LNode **L);

	int ClearList(LNode **L);

	bool isListEmpty(LNode *L);

	int getListLength(LNode *L);

	ElemType getElem(LNode *L,int index);

	//从列表中找到某一元素的位置
	ElemType* locateElem(LNode *L,ElemType Q);

	LNode* ListInsert(LNode **L,int index,ElemType e);

	void ListDelete(LNode **L,ElemType &e);

	void ChangeElem(LNode **L,ElemType e);

	void Printsqlist(LNode *L);

	void ListAdd(LNode **L,ElemType e);
};

数据结构算法的实现NodeList.cpp
#include "NodeList.h"


NodeList::NodeList(void)
{
}


NodeList::~NodeList(void)
{
}

int NodeList::InitList(LNode **L)
{
	*L = NULL;
	return 0;
}

int NodeList::DestroyList(LNode **L)
{
	free(*L);
	free(L);
	L = NULL;
	return 0;
}

int NodeList::ClearList(LNode **L)
{
	LNode* cp;
	LNode* np;
	cp = *L;
	
	while (cp != NULL)
	{
		np = cp->next;
		free(cp);
		cp = np;
	}
	*L = NULL;
	return 0;
}

bool NodeList::isListEmpty(LNode *L)
{
	if(L==NULL)
	{
		return true;	
	}
	else
	{
		return false;
	}


}

int NodeList::getListLength(LNode *L)
{
	if (L == NULL)
	{
		return 0;
	}

	int i = 0;
	while (L != NULL)
	{
		L = L->next;
		i++;
	}
	return i;

}

ElemType NodeList::getElem(LNode *L,int index)
{
	if (index<0)
	{
		printf("index wrong in function getElem\n");
		exit(1);
	}
	int i = 0;
	while (L != NULL)
	{
		L = L->next;
		if (i==index)
			break;
		i++;
	}

	if (L!=NULL)
	{
		return L->data;
	}
	else
	{
		printf("wrong index!\n");
		exit(1);
	}

}

//从列表中找到某一元素的位置
ElemType* NodeList::locateElem(LNode *L,ElemType Q)
{
	int i = 0;
	while (L != NULL)
	{
		if (L->data == Q)
			return &L->data;
		L = L->next;
		i++;
	}
	return NULL;
}

LNode* NodeList::ListInsert(LNode **L,ElemType e)
{
	if (*L == NULL || index<0)
	{
		exit(1);
	}
	LNode* pc = *L;
	LNode* pn ;

	LNode* inser = (LNode*)malloc(sizeof(LNode));
	inser->data = e;

	int i = 0;
	while(pc != NULL)
	{
		i++;
		pn = pc->next;
		if (i == index)
		{
			inser->next = pn;
			pc->next = inser;
			break;
		}
		pc = pn;
		
	}
}

void NodeList::ListDelete(LNode **L,ElemType &e)
{
	if (*L == NULL || index<0)
	{
		exit(1);
	}
	LNode* pc = *L;

	int i =0;
	while (pc != NULL)
	{
		if (i == index)
		{
			pc->next = pc->next->next;
			break;
		}
		pc = pc->next;
		i++;
	}
}

void NodeList::ChangeElem(LNode **L,ElemType e)
{
	if (*L == NULL || index<0)
	{
		exit(1);
	}
	int i = 0;
	LNode * pc = *L;
	while (pc != NULL)
	{
		if (i == index)
		{
			pc->data = e;
		}
		pc = pc->next;
		i++;
	}
	if (index > i)
	{
		exit(1);
	}
	
}

void NodeList::Printsqlist(LNode *L)
{
	if (L == NULL)
	{
		exit(1);
	}
	int i = 0;
	while (L != NULL)
	{
		printf("LNode[%d]:%d  ",i,L->data);
		L = L->next;
		i++;
	}
	printf("\n");
}

void NodeList::ListAdd(LNode **L,ElemType e)
{
	LNode* newP = (LNode *)malloc(sizeof(LNode));
	newP->next = NULL;
	newP->data = e;
	if (*L == NULL)
	{
		*L = newP;
	}
	else
	{
		LNode* np = *L;
		while (np->next != NULL)
		{
			np = np->next;
		}
		np->next = newP;
	}
}

测试代码
void TEST_NodeList()
{
	printf("-----------------------------------------------------\n");
	printf("-------Here is A Test For NodeList-------------------\n");
	NodeList nodeLIST;
	LNode* L;
	nodeLIST.InitList(&L);
	int i = 0;
	for (i=0;i<10;i++ )
	{
		nodeLIST.ListAdd(&L,i);
	}
	nodeLIST.Printsqlist(L);
	int len = nodeLIST.getListLength(L);
	nodeLIST.ListInsert(&L,3,1111);

	ElemType e;
	nodeLIST.ListDelete(&L,7,e);

	nodeLIST.ChangeElem(&L,9,212121);

	nodeLIST.Printsqlist(L);
}

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