# 数据结构—链表

0
12

### 3.2动态内存分配

malloc：

fp = (数据类型*)malloc(sizeof(数据类型))

free：

free(void *fp)

### 3.3链表的建立

`typedef struct list{  int num;  struct list *next;}node;typedef node *link;​link creat_list(int n){  link head;  link ptr;  int i;​  head = (link)malloc(sizeof(node));  if(!head)   {    cout << "内存分配失败" << endl;    return 0;   }  head->next = NULL;  ptr = head;​  cout << "输入n个数据" << endl;  for(i = 1; i <= n; ++i)   {    scanf("%d", &ptr->num);    ptr->next = (link)malloc(sizeof(node));    if(!ptr->next)     {      cout << "内存分配失败" << endl;      return 0;     }    ptr->next->next = NULL;    ptr = ptr->next;   }  return head;}`

### 3.4链表的遍历

`link find_node(link head, int num){  link ptr;  ptr = head;  while (ptr != NULL)   {    if(ptr->num == num)      return ptr;    ptr = ptr->next;   }  cout << "node" << endl;  return ptr;}`

### 3.5链表的连接

`link concatenate(link ptr1, link ptr2){  link ptr;  ptr = ptr1;  while(ptr->next != NULL) //让ptr1的尾巴指向ptr2的头    ptr = ptr->next;  ptr->next = ptr2;  return ptr1;}`

### 3.6链表内节点的删除

• 删除第一个节点

• 删除最后一个节点

• 删除中间节点

`link delete_node(link head, link ptr){  link previous;  if(ptr == head) //删头    return head->next;  else   {    previous = head;    while (previous->next != ptr)     {      previous = previous->next;     }    previous->next = ptr->next;   }  free(ptr); //有借有还，再借不难  return head;}`

### 3.7释放链表的内存空间

`link destroy_list(link head){  link ptr;  while(head != NULL)   {    ptr = head;    head = head->next;    free(ptr);   }}`

### 3.8链表内节点的插入

`link insert_node(link head, link ptr, int value) //插入在ptr之后{  link new_node = (link)malloc(sizeof(node));  if(!new_node)   {    cout << "分配内存失败" << endl;    return NULL;   }  new_node->num = value;  new_node->next = NULL;  if(ptr == NULL) //头插   {    new_node->next = head;    return new_node;   }  else   {    if(ptr->next == NULL) //尾插      ptr->next = new_node;    else //中间插     {      new_node->next = ptr->next;      ptr->next = new_node;     }       }  return head;}`

### 3.9链表结构的反转

`link invert_list(link head){  link mid, last;  mid = NULL;  while(head != NULL)   {    last = mid;    mid = head;    head = head->next;    mid->next = last;   }  return mid;}`

1. 执行while之前 head指向链表第一个 mid == NULL， last无值

2. 执行一次 head指向链表第二个 mid 指向 链表第一个 last == NULL

3. 再执行一次 head指向链表第三个 mid 指向 链表第二个 last 指向 链表第一个 并且 mid的前驱是last

4. 反复直到反转完成 返回mid 也就是反转后的头节点

### 3.10循环链表结构

#### 3.10.1首先建立链表

`typedef struct clist{  int data;  struct clist *next;}cnode;typedef cnode *clink;​clink creat_list(int n){  clink head;  clink ptr;  int i;​  head = (clink)malloc(sizeof(cnode));  if(!head)   {    cout << "内存分配失败" << endl;    return 0;   }  head->next = NULL;  ptr = head;​  cout << "输入n个数据" << endl;  for(i = 1; i <= n; ++i)   {    scanf("%d", &ptr->data);    ptr->next = (clink)malloc(sizeof(cnode));    if(!ptr->next)     {      cout << "内存分配失败" << endl;      return 0;     }    ptr->next->next = NULL;    ptr = ptr->next;   }  ptr->next = NULL;  return head;}`

#### 3.10.2循环链表内节点的插入

• 情况一 ：插在链表的头部成为链表的新开始

• 将新节点的指针指向链表的第一个节点

• 找到最后一个节点且将其指针指向新节点

• 返回新节点 为链表新头部

• 情况二：除情况一的其他情况，假设插在ptr之后

• 将新节点的指针指向ptr下一节点

• 将ptr的下一节点设为新节点

`clink insert_node(clink head, clink ptr, int value){  clink new_node = (clink)malloc(sizeof(cnode));  clink previous;  if(!new_node)   {    cout << "分配内存失败" << endl;    return NULL;   }  new_node->data = value;  new_node->next = NULL;  if(head == NULL) //原先就是空表   {    new_node->next = new_node;    return new_node;   }  if(ptr == NULL) // 头插   {    new_node->next = head;    previous = head;    while(previous->next != NULL)      previous = previous->next;    previous->next = new_node;    head = new_node;   }  else   {    new_node->next = ptr->next;    ptr->next = new_node;   }  return head;}`

#### 3.10.3循环链表内节点的删除

• 情况一：删第一个

• 将链表的开始移向下一节点

• 将最后一个节点指向第二个节点

• 情况二：除情况一的其他情况，删除ptr

• 找到ptr的前一个节点

• 将ptr前一个节点的后继设为ptr的后继

`clink delete_node(clink head, clink ptr){  clink previous;  if(head == NULL) //空表    return NULL;  previous = head;  if(head != head->next) //不止一个节点    while(previous->next != ptr)      previous = previous->next;​  if(ptr == head) //头插   {    head = head->next;    previous->next = ptr->next;   }  else   {    previous->next = ptr->next;   }  free(ptr);  return head;}`

### 3.11双向链表结构

#### 3.11.1双向链表的建立

`typedef struct dlist{  int data;  struct dlist *front; //后继  struct dlist *back; //前驱}dnode;typedef dnode *dlink;​dlink create_dlist(int *arr, int len){  dlink head, before, new_node;  int i;  head = (dlink)malloc(sizeof(dnode));  if(!head)   {    cout << "内存分配失败" << endl;    return NULL;   }  head->data = arr[0];  head->back = NULL;  head->front = NULL;  before = head;  for(i = 1; i < len; ++i)   {    new_node = (dlink)malloc(sizeof(dnode));    new_node->data = arr[i];    new_node->front = NULL;    new_node->back = before;    before = new_node;   }  return head;}`

#### 3.11.2双向链表的插入

• 情况一：头插

• 将新节点的指针front指向双向链表的开始

• 将表头的back指向新节点

• 情况二：尾插

• 将最后一个节点的front指向新节点

• 新节点的back指向尾部

• 情况三：中间插，假设在ptr之后

• 新节点的前驱指向ptr

• 新节点的后继变为ptr的后继

• ptr的后继指向新节点

• 原ptr后继的前驱指向新节点

`dlink insert_node(dlink head, dlink ptr, int value){  dlink new_node = (dlink)malloc(sizeof(dnode));  if(!new_node)   {    cout << "内存分配失败" << endl;    return NULL;   }  new_node->back = NULL;  new_node->front = NULL;  new_node->data = value;  if(head == NULL) //空表    return new_node;  if(ptr == NULL) //头插   {    new_node->front = head;    head->back = new_node;    head = new_node;   }  else   {    if(ptr->front == NULL) //尾插     {      ptr->front = new_node;      new_node->back = ptr;     }    else     {      ptr->front->back = new_node;      new_node->front = ptr->front;      new_node->back = ptr;      ptr->front = new_node;     }       }  return head; }`

#### 3.11.3双向链表节点的删除

• 情况一：删头

• 将第二个节点的前驱设为NULL

• 情况二：删尾

• 最后一节点的后继设为NULL

• 情况三：删中间，删除ptr

• ptr前驱的后继设为ptr后继的前驱

• ptr后继的前驱设为ptr前驱的后继

`dlink delete_node(dlink head, dlink ptr){  if(ptr->back == NULL) //删头   {    head = head->front;    head->back = NULL;   }  else   {    if(ptr->front == NULL) //删尾     {      ptr->back->front == NULL;     }    else     {      ptr->back->front = ptr->front;      ptr->front->back = ptr->back;     }       }  free(ptr);  return head;}`

### 3.12循环双向链表

#### 3.12.1建立

`typedef struct dlist{  int data;  struct dlist *front; //后继  struct dlist *back; //前驱}cdnode;typedef cdnode *cdlink;​cdlink create_dlist(int *arr, int len){  cdlink head, before, new_node;  int i;  head = (cdlink)malloc(sizeof(cdnode));  if(!head)   {    cout << "内存分配失败" << endl;    return NULL;   }  head->data = arr[0];  head->back = NULL;  head->front = NULL;  before = head;  for(i = 1; i < len; ++i)   {    new_node = (cdlink)malloc(sizeof(cdnode));    new_node->data = arr[i];    new_node->front = NULL;    new_node->back = before;    before = new_node;   }  head->back = new_node;  new_node->front = head;  //head->back = NULL;  //new_node->front = NULL;  return head;}`
• 情况一：删除或插入第一个节点

• 情况二：除情况一

#### 3.12.2删除

`cdlink delete_node(cdlink head, cdlink ptr){  if(head == NULL)    return NULL;  if(ptr == head) head = head->front; //头  ptr->back->front = ptr->front;  ptr->front->back = ptr->back;  free(ptr);  return head;}`

#### 3.12.3插入

`cdlink insert_node(cdlink head, cdlink ptr, int value){  cdlink new_node = (cdlink)malloc(sizeof(cdnode));  if(!new_node)   {    cout << "内存分配失败" << endl;    return NULL;   }  new_node->data = value;  if(head == NULL) //空表   {    new_node->back = new_node;    new_node->front = new_node;    return new_node;   }  if(ptr == NULL) //头插   {    head->back->front = new_node;    new_node->front = head;    new_node->back = head->back;    head->back = new_node;    head = new_node;   }  else   {    ptr->front->back = new_node;    new_node->front = ptr->front;    new_node->back = ptr;    ptr->front = new_node;   }  return head;}`

### 最后代码大汇总

```#include <bits/stdc++.h>
using namespace std;

typedef struct list
{
int num;
struct list *next;
}node;

{
int i;

{
cout << "内存分配失败" << endl;
return 0;
}

cout << "输入n个数据" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->num);
if(!ptr->next)
{
cout << "内存分配失败" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
}

{
while (ptr != NULL)
{
if(ptr->num == num)
return ptr;
ptr = ptr->next;
}
cout << "node" << endl;
return ptr;
}

{
ptr = ptr1;
while(ptr->next != NULL)
ptr = ptr->next;
ptr->next = ptr2;
return ptr1;
}

{
else
{
while (previous->next != ptr)
{
previous = previous->next;
}
previous->next = ptr->next;
}
free(ptr);
}

{
{
free(ptr);
}
}

{
if(!new_node)
{
cout << "分配内存失败" << endl;
return NULL;
}
new_node->num = value;
new_node->next = NULL;
if(ptr == NULL) //头插
{
return new_node;
}
else
{
if(ptr->next == NULL) //尾插
ptr->next = new_node;
else //中间插
{
new_node->next = ptr->next;
ptr->next = new_node;
}

}
}

{
mid = NULL;
{
last = mid;
mid->next = last;
}
return mid;
}

int main()
{

return 0;
}   ```
```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef struct clist
{
int data;
struct clist *next;
}cnode;

{
int i;

{
cout << "内存分配失败" << endl;
return 0;
}

cout << "输入n个数据" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->data);
if(!ptr->next)
{
cout << "内存分配失败" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
ptr->next = NULL;
}

{
if(!new_node)
{
cout << "分配内存失败" << endl;
return NULL;
}
new_node->data = value;
new_node->next = NULL;
{
new_node->next = new_node;
return new_node;
}
if(ptr == NULL) // 头插
{
while(previous->next != NULL)
previous = previous->next;
previous->next = new_node;
}
else
{
new_node->next = ptr->next;
ptr->next = new_node;
}
}

{
return NULL;
while(previous->next != ptr)
previous = previous->next;

{
previous->next = ptr->next;
}
else
{
previous->next = ptr->next;
}
free(ptr);
}

int main()
{

return 0;
}```

```#include <bits/stdc++.h>
using namespace std;

typedef struct dlist
{
int data;
struct dlist *front; //后继
struct dlist *back; //前驱
}dnode;

{
int i;
{
cout << "内存分配失败" << endl;
return NULL;
}
for(i = 1; i < len; ++i)
{
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
}

{
if(!new_node)
{
cout << "内存分配失败" << endl;
return NULL;
}
new_node->back = NULL;
new_node->front = NULL;
new_node->data = value;
return new_node;
if(ptr == NULL) //头插
{
}
else
{
if(ptr->front == NULL) //尾插
{
ptr->front = new_node;
new_node->back = ptr;
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}

}
}

{
if(ptr->back == NULL) //删头
{
}
else
{
if(ptr->front == NULL) //删尾
{
ptr->back->front == NULL;
}
else
{
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
}

}
free(ptr);
}

int main()
{

return 0;
}```
```#include <bits/stdc++.h>
using namespace std;

typedef struct dlist
{
int data;
struct dlist *front; //后继
struct dlist *back; //前驱
}cdnode;

{
int i;
{
cout << "内存分配失败" << endl;
return NULL;
}
for(i = 1; i < len; ++i)
{
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
//new_node->front = NULL;
}

{
return NULL;
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
free(ptr);
}

{
if(!new_node)
{
cout << "内存分配失败" << endl;
return NULL;
}
new_node->data = value;
{
new_node->back = new_node;
new_node->front = new_node;
return new_node;
}
if(ptr == NULL) //头插
{
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}