C++学习记录-数据结构-链表

C++学习记录-数据结构-链表

当要按顺序储存一大组数据，且要随时往里面增减数据，此时数组就显得不方便，用链表则会快很多

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多

代码实现：

1.创建链表结构体

struct data {
	int dat;//用于储存数据
    
	data* next=NULL;//用于指向下一个数据
};

2.定义用于指示的变量

int num = 0;//定义一个整形变量用于计算链表中数据的数量

int dat;//用于录入数据

struct data* head=NULL;//定义一个头指针指向链表的第一个数据

struct data* point = NULL;//定义一个指示指针用于在遍历时指示当前位置

3.开始往链表中插入数据

cout << "请输入欲添加的数据" << endl;
cin >> dat;
//录入数据

if (head == NULL)
{
	head = new struct data;
	head->dat = dat;
	point = head;
	num++;
	//如果头指针为空，则为头指针开辟内存空间存储，同时指示指针指向第一个数据
}

else {
	if (head->dat >= dat)
	{
		struct data* newhead = new struct data;
		newhead->dat = dat;
		newhead->next = head;
		head = newhead;
		num++;
		//如果新数据小于第一个数据，则要更新头指针和指示指针
	}
    
	else {
		point = head;//更新一下指示指针
		for (int i = 0; i < num; i++)//开始对链表进行遍历
		{
			if (point->next == NULL || (point->dat <= dat && point->next->dat >= dat))
			{
				struct data* newmid = new struct data;
				newmid->dat = dat;
				newmid->next = point->next;
				point->next = newmid;
				num++;
				break;
				//找到插入的位置，进行数据插入
			}
            //当遍历到链表尾部时，或者在链表中间找到可以插入的位置时
            
			else {
				point = point->next;
				//指示指针下移，继续遍历
			}
		}
	}
}