理解链表的头插和尾插方法：与数组的不同之处

准备重新复习一遍数据结构了，基础的东西不能丢呀。当作复习笔记和一些思考来写。

链表由一系列不必在内存中相连的结构组成。每个结构均含有表元素和指向包含该元素后继元的结构的指针，成为next指针。最后的next指针指向NULL。所以一般写成一个结构体包含数据域和指针域

struct ListNode 
{
    int data;
    struct ListNode *next;
};

数组和链表的区别(记得那会儿校招找工作的时候也考了)

• 数组静态分配内存，数组动态分配内存
• 数组在内存中连续，链表在内存中不连续
• 数组元素在栈区，链表元素在堆区(因为用了malloc)
• 数组利用下表定位，时间复杂度O(1)，链表定位时间复杂度O(n)
• 数组插入或删除元素的时间复杂度是O(n)，链表时间复杂度是O(1)

今天在写插入的时候一直不知道表头是干嘛的为什么要用一个表头，直到在写头插法的时候，每次插入到最前面，改变了链表的起始端指针，程序老是被我写着有问题，然后看了一下《数据结构与算法分析》的书上是这样写的

第一，程序并不存在从所给定义出发在表的前面插入元素的真正显性的方法。第二，从表的前面实行的删除是一个特殊的情况因为他改变了表的起始端，编程中的疏忽会造成表的丢失。第三个问题涉及一般的删除，虽然上述指针的移动很简单，但是删除算法要求我们记住被删除单元前面的表元。

事实上，做一个简单的修改就能解决三个问题，我们将留出一个标志节点，成为表头或者哑节点。这是一种习惯。

(书上说是一种习惯但是头节点真好用啊)

推荐一篇博客带头节点和不带头节点的区别

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct ListNode
{
	int data;
	struct ListNode * next;
};

typedef struct ListNode ListNode;

ListNode * CreateListNode(int data);        //创建一个节点
void TailInsert(ListNode *HeadNode,ListNode * NewNode);    //尾插法
void TopInsert(ListNode *HeadNode,ListNode * NewNode);     //头插法
void PrintList(ListNode *HeadNode);            //打印

int main()
{
	ListNode * Header1 = NULL;
	Header1 = CreateListNode(0);

	ListNode * Header2 = NULL;
	Header2 = CreateListNode(0);
	
	for(int i=0; i<10;i++)
	{
		TopInsert(Header1,CreateListNode(i*5));
	}

	for(int i=0; i<10;i++)
	{
		TailInsert(Header2,CreateListNode(i*5));
	}

	printf("头插法：\n");
	PrintList(Header1);
	printf("\n");
	printf("尾插法：\n");
	PrintList(Header2);
	free(Header1);
	free(Header2);
	return 0;
}

ListNode * CreateListNode(int data)
{
	ListNode * node = NULL;
	node = (ListNode *)malloc(sizeof(ListNode));
	if(node == NULL)
	{
		printf("malloc error\n");
		return NULL;
	}
	memset(node, 0 ,sizeof(ListNode));
	node->data = data;
	node->next = NULL;
	return node;
}

void TailInsert(ListNode *HeadNode,ListNode * NewNode)
{
	ListNode *p = HeadNode;
	while( p->next != NULL)
	{
		p=p->next;
	}
	p->next = NewNode;
}

void TopInsert(ListNode *HeadNode,ListNode * NewNode)
{
	ListNode *p = HeadNode;
	NewNode->next = p->next;
	p->next = NewNode;
}

void PrintList(ListNode *HeadNode)
{
        ListNode *p = HeadNode;
	while(p ->next!= NULL)
	{
		p = p->next;
       		printf("%d\t",p->data);
	}
}

输出结果:

(我居然没有销毁链表)

2022年7月15日

 顺序存储类型的静态分配

#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize];
    int length;
}SqList;

顺序存储类型的动态分配

#define InitSize 100
typedef struct
{
    ElemType *data;
    int MaxSize;        //数组的最大容量
    int Cur_length;         //当前个数
}SeqList;

C的初始动态分类的语句

L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);

//C++
L.data = new ElemType[InitSize];