[C++数据结构]1.2 线性表的链式存储

我在编写部分内容时，偷了很大的懒，因为我只关注了最核心的那几部分，如果您需要了解这部分内容的全貌请搜索其他文章！！！ 1 需要构造的函数

1. Status InitList L(LinkList &L);
//生成新节点作为表头，用头指针L指向头结点；把头结点的指针域置空

2.isEmpty
//判断是否为空即判断头结点指针域是否为空，因为当加入元素时，头结点的指针域是一定要指向第一个元素的地址

3.DestroyList
//引入一个新指针，他指向表头，然后直接释放这块地方；指向下一个，释放。。。重复重复；需要注意的是要保存地址指向下一个地方；

4.ClearList
//需要三个指针，不删除头结点，然后清除所有元素delete

5.ListLen
//弄个计数器

6.LocateElem
//查找，从头开始找

7. GetElem
//获取i位置的元素

8. InsertList
9. DeleteList
 //两者类似，增加（删减）插入位置元素的地址即可

2 节点的设计

关于节点的设计，我们当然可以像老师那样将链表名跟节点放在一起，但是在对象的设计角度来说，他们两个的“方法”将重叠，比如说一个链表的任意节点都可以使用初始化链表的 *** 作。因此我觉得把他们设计成两个对象

由于这次的设计会涉及到两种对象，一个是链表本身（或者说头结点），另一个是普通节点，他们在一些 *** 作上是不相容的，比如说我们想要计算这个链表有多长，但是我们不会计算一个节点有多长；我们会想在链表插入一个节点，但是我们不会对一个节点对象插入一个节点。

实际上这是只在单链表才需要考虑的，如果设置成双链表，或者循环列表，那么表头即链表名无所谓跟节点有区别。

typedef struct
{
	int age;
	float grade;
}ElemType;

class LNode
{
private:
	ElemType* elem;
	
public:
	LNode* next;
	LNode(ElemType*e,LNode* left=NULL)
	{
		elem = e;
		next = left;
	}
	void show()
	{
		cout << "age is: " << elem->age << " ,grade is: " << elem->grade << endl;
	}

};

lnode为左节点，一个节点里面存在两个数据，一个数据ElemType去存储复杂的数据类型，另一个LNode* next。

3 方法

以下方法我很多是偷懒没写全的，比如Insert的位置我没有判定是否合法，首节点和结尾的处理我也没做

class LinkList
{

public:
	LNode* next;

	LinkList()
	{
		next = NULL;
		cout << "Link List Inited!" << endl;
	}

	~LinkList()
	{

	}

	bool isEmpty()
	{
		if (next == NULL)
		{
			cout << "is Empty!" << endl;
			return 0;
		}
		else
		{
			cout << "Not Empty!" << endl;
			return 1;
		}
	}

	int ListLen()
	{
		auto p = next;
		int i = 0;
		while (p != NULL)
		{
			p = p->next;
			i++;
		}
		cout << "length is: " << i << endl;
		return i;
	}

	void Print()
	{
		auto p = next;
		while (p != NULL)
		{
			p->show();
			p = p->next;
		}
	}

//todo loc valid?
	void InsertList(LNode* n, int loc)
	{
		auto p = next;
		auto q = next;
		int i = 1, j = 1;
		//先找到loc位置上的元素地址，然后让n连接他
		while (i != (loc))
		{
			p = p->next;
			i++;
		}
		n->next = p;

		
		//后找到loc-1位置上的元素，然后让q连接n；
		//loc,loc-1查找的顺序不能调换
		while (j != (loc -1))
		{
			q = q->next;
			j++;
		}
		q->next = n;

	}

//todo loc valid?
	void DeleteList(int loc)
	{
		auto p = next;
		auto q = next;
		int i = 1, j = 1;
		while (i != (loc+1))
		{
			p = p->next;
			i++;
		}

		while (j != (loc - 1))
		{
			q = q->next;
			j++;
		}

		q->next = p;
	}

//todo loc valid?
	LNode* GetElem(int loc)
	{
		auto p = next;
		int i = 1;
		while (i<(loc))
		{
			p = p->next;
			i++;
		}
		return p;
	}
	

	int LocateElem(LNode* n, int (*cmp)(void* e1, void* e2))
	{
		auto p = next;
		int i = 1;
		for (p; p != NULL; p = p->next)
		{
			if (cmp(p, n) == 0)
			{
				cout << "Location Found:  " << i << endl;
				return i;
			}
			i++;
		}
		printf("No such elem!\n");
		return -1;
	}
	

};

测试文件

#include "Header.h"

int cmp_age(void* e1, void* e2)
{
	return (int)(((ElemType*)e1)->age - ((ElemType*)e2)->age);
}


int main()
{
	//创建链表
	LinkList L;
	//L.isEmpty();
	//节点数据以及创建节点
	ElemType p1 = { 1,1.1 };
	//ElemType q1 = { 14,11.11 };
	ElemType p2 = { 2,2.2 };
	ElemType p3 = { 3,3.3 };
	ElemType p4 = { 4,4.4 };
	LNode n1(&p1);
	LNode n2(&p2);
	LNode n3(&p3);
	LNode n4(&p4);

	//连接节点
	L.next = &n1;
	n1.next = &n2;
	n2.next = &n3;
	n3.next = &n4;

	L.isEmpty();
	L.Print();
	L.ListLen();

	//测试insert
	//ElemType q1 = { 14,11.11 };
	//LNode m1(&q1);
	//L.InsertList(&m1, 2);
	//L.ListLen();
	//L.Print();

	测试Delete
	//L.DeleteList(2);
	//L.ListLen();
	//L.Print();

	//测试Get
	//LNode m2(&p1);
	//m2 = *L.GetElem(2);
	//m2.show();


	测试Locate
	//ElemType q1 = { 14,11.11 };
	//LNode m1(&q1);
	//L.LocateElem(&m1, cmp_age);

	return 0;
}