数据结构:顺序链表

#include "pch.h"
#include <iostream>
//c++实现线性表的链式存储结构
#define MAXSIZE 100
//单链表的结构体
typedef struct LNode
{
	int data;
	//---这里声明的是一个结构体的指针,保存结构体的地址
	struct LNode *next;
}LNode,*LinkList;
/* 
这里*LinkList主要作为头指针使用,
所以这个东西是用来保存地址的,和那个next是一样的
*/
using namespace std;
//结构体的初始化
bool InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	L->data = 0;//前面第一个是首元节点不存数据
	LinkList p=L;
	int i = 6;
	while (--i!=1)
	{
		LinkList N = new LNode;
		p->next = N;
		p->next->data = i;
		p = p->next;
	}
	p->next = NULL;
	return true;
}
//打印单链表
void PrintLink(LinkList L)
{
	LinkList p = L->next;
	while (p)
	{
		cout << p->data<<endl;
		p = p->next;
	}
}

//获取单链表值
bool GetElem(LinkList L, int i, int &e)
{
	/*这里其实就是根据头结点
	然后通过计数器来不断计数来获取相应的值*/
	LinkList p = L->next;//这里定义一个指针变量来存放Lnode的地址
	//因为L是首元节点所以第一个数组其实是第二个Lnode
	int j=1;//计数器
	while (p && j <i)//当指针为空或者超过i还没有找到的话就跳出循环
	{
		//这里之所以是j<i是因为我们需要找到i位置的指针
		//而这里p指的的其实是第j个指针(j++之后)
		p = p->next;
		j++;
	}
	if (!p || j > i) return false;//这里说明没有找到
	e = p->data;
	return true;
}
//单链表的插入
bool ListInsert(LinkList &L, int i, int e)
{
	LinkList p = L;//先让p指向首元节点,以便后面处理
	int j = 0;
	while (p && j < i- 1)
	{
		//找到i前面那个数字,所以是j<i-1
		p = p->next;
		++j;
	}
	if (!p || j > i - 1) return false;//判断是否找到了
	LinkList s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
//单链表的删除
bool ListDelete(LinkList &L, int i)
{
	LinkList p = L->next;
	int j = 0;
	while (p && j < i - 1)//查找第i-1个节点
	{
		p = p->next;
		++j;
	}
	if (!p->next || j > i - 1) return false;//判断是否第i个节点是否存在
	LinkList q = p->next;//找到第i个节点然后删除
	p->next = q->next;
	delete q;
	return true;
}
//前插法插入数据,其实就是把数据插在首元节点后面
bool InsertDataFront(LinkList &L, int e)
{
	LinkList s = new LNode;
	s->data = e;//这里L指向的是首元节点,所以我们可以直接修改L->next的值
	s->next = L->next;
	L->next = s;
	return true;
}
bool InsertDataBack(LinkList &L,int e)
{
	LinkList p = L->next;
	while ( p->next) p=p->next;
	LinkList s = new LNode;
	s->data = e;
	s->next = NULL;
	p->next = s;
	return true;
}
int main()
{	
	//这里定义了一个指向头结点的指针
	//*L保存的是头结点的地址,头结点也是一个指针
	//头结点指向的是LNdode
	LinkList *L = new LinkList;
	if (InitList(*L)) cout << "Init ok!"<<endl;
	PrintLink(*L);
	int e = 0;
	if (GetElem(*L, 1, e)) cout << "该值为:" << e << endl;
	else cout << "没有找到该值!" << endl;
	if (ListInsert(*L, 2, 10)) cout << "插入成功!" << endl;
	else cout << "插入失败!" << endl;
	PrintLink(*L);
	if(ListDelete(*L, 2))cout << "删除成功!" << endl;
	else cout << "删除失败!" << endl;
	PrintLink(*L);
	InsertDataFront(*L,20);
	PrintLink(*L);
	InsertDataBack(*L, 30);
	PrintLink(*L);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

Title - Artist
0:00