结构体（2），链表，共用体

链式数据结构 -- 链表

定义：

struct Node 
{
    int data; //数据域 --存储要处理的数据 
    struct Node *next; //指针域，保存地址-- 指向下一个节点 
};  //数据域+指针域

//节点类型 

struct Node n1; 
struct Node n2;
struct Node n3;

s1-->s2-->s3 

狗链 

头节点：链表的第一个节点，用于找到该链表实现操作，数据域一般不需要使用

首节点：链表用于存储数据的第一个节点，是头节点的后一个节点

尾节点：链表用于存储数据的最后一个节点，后一个节点p->next为NULL

特点

    优势: 增加和删除数据 方便
    劣势: 存取不方便 

操作: //数据结构体 数据的处理 增删改查 

创建链表：

1.使用malloc函数创建头结点

2.传回头结点，可以return也可以传入struct Node **（只有函数内*运算才能实现被调修改主调）

第一种：

返回值为void，传入参数为struct Node**型

此时注意（*head）->next需要加空号，因为->运算优先级比*高

void createEmptyLinklist(struct Node **head)
{
	struct Node *head = malloc(sizeof(struct Node));
	(*head)->next = NULL;
}

第二种：

返回值为struct Node*，参数为struct Node*

struct Node *createEmptyLinklist(struct Node *head)
{
	*head = malloc(sizeof(struct Node));
	(*head)->next = NULL;
	return *head;
}

插入链表：

头插入：

1.创建新节点

2.将该节点的next变为原来头结点的next（保证原来头结点的next不丢失）

3.将头节点的next变为插入的节点

void pushFront(struct Node *head,int dt)
{
	//s1.创建节点 
	struct Node *new = malloc(sizeof(struct Node ));
	new->data = dt;
	
	//s2 
	new->next = head->next;
 
	//s3 
	head->next = new;
}

尾插入：

1.创建新节点

2.取到尾节点

3.在尾节点后面插入

void pushBack(struct Node *head,int dt)
{
	//s1 
	struct Node *new = malloc(sizeof(struct Node));
	new->data = dt;
    //s2
	struct Node *p = head;
	while (p->next!=NULL)
	{
		p = p->next;
	}
	//s3 
	p->next = new;
	new->next = NULL;
}

删除：

头删：

1.创建临时节点

2.判断首节点是否为空（也就是head->next是否为NULL）

3.将首节点的next替换原来的首节点，并将首节点的地址赋值给临时节点

4.释放首节点

void popFront(struct Node *head)
{
	struct Node *p = NULL;
 
	if (isEmpty(head) == 0)
	{
		p = head->next;
		head->next = p->next;
		free(p);
	}
}

尾删：

1.创建临时节点

2.判断首节点是否为空（也就是head->next是否为NULL）

3.将p的位置移动到尾节点的上一个位置（因为删除尾节点之后，还要更改该节点的next为NULL）

4.释放尾节点，并将尾节点的上一个位置的next更改为NULL

void popBack(struct Node *head)
{
	struct Node *p = head;
 
	if (isEmpty(head) == 0)
	{
		while (p->next->next != NULL)
			p = p->next;
		free(p->next);
		p->next = NULL;
	}
}

销毁链表：

1.使用任意一个删除法删除除头结点外所有节点

2.删除头结点，并更改为NULL（因为头结点是在主函数中定义的）

void destroyLinklist(struct Node **head)
{
	while (isEmpty(*head) == 0)
	{
		popFront(*head);
	}
  
	free(*head);
	*head=NULL; //将head修改成NULL 防止野指针操作 
}

链表逆序：

1.断开头结点与其他节点

1.定义p用于取出插入的节点，q用于保存下一节点位置（插入之后p->next会丢失）

3.进行不分配空间的头插

4.p移动到p->next的位置

void reverseLinkList(struct Node *head)  
{
	struct Node *p=head->next;
	head->next=NULL;
	struct Node *q=NULL;
	while(p!=NULL)
	{
		q=p->next;
		p->next=head->next;
		head->next=p;
		p=q;
	}
}

查找中间节点：

创建两个节点，从头结点开始，一个每次移动一个节点（pmid），一个每次移动两个节点（pend），当pend移动到最后一个位置时，另一个节点移动到中间位置

struct Node *searchMiddleNode(struct Node *head)
{
	struct Node *pmid=head;
	struct Node *pend=head;
	if(isEmpty(head)==0)
	{
		while(pend!=NULL && pend->next!=NULL) 
		{
			pmid=pmid->next;
			pend=pend->next->next;
		}
	}
	else
	{
		pmid=NULL;
	}
	return pmid;
}

共用体：

共用体 (union)

union demo
{
  int a;
  char b;
  short c;
};

计算机早期的时候，能不能尽量节省空间?

共用体技术:
      可以让，多个变量，共用 同一块内存空间 

语法:

union 共用体名
{
    成员列表 
};

注意:

  1.共用体初始化时，只能给一个值，这个值默认时给到第一个成员的 
  2.共用体空间中数据，取决最后一次给到值 
    赋值的时候，每个成员只能影响，自己对应的字节
  3.共用体类型
    可以定义变量
    可以定义数组
    可以定义指针 
    可以做函数参数 和 返回值 

->判断字节序的大小端

d.b为1，小端（低位数据放在低地址处，低低），d为0，大端（低位数据放在高地址处，高低）

int isLittleBigEnd(void)
{
    union
    {
        int a；
        char b；
    }d={1}；
    return    d.b
}

->短类型转换为长类型：

无符号：高位拓展0

有符号：进行符号位拓展

#include 
 
union demo
{
	char a;
	int b;
};
 
int main()
{
	union demo d={0x10};
	printf("%#x\n",d.a);
	printf("%#x\n",d.b);
}

首先，char和int默认为有符号位

当此时我给a赋值0x10时，d.b的值为0x10（此时符号位为0）

当此时我给a赋值0x90时，d.b的值为0xffffff90（此时符号位为1）