什么是链表
链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer).
从本质上来讲,链表与数组的确有相似之处,他们的相同点是都是线性数据结构,这与树和图不同,而它们的不同之处在于数组是一块连续的内存,而链表可以不是连续内存,链表的节点与节点之间通过指针来联系.
单链表反转
- 分析（头结点插入法）
- 实现链表反转，我们需要从第二个节点开始遍历，将当前节点的 next 指向前一个节点。这里需要注意的是，该变当前节点的 next 时，需要提前保存 next，不然遍历就会中断。
#include<iostream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#include<vector>
using namespace std;
#include <stdio.h>
#include <malloc.h>
#include <time.h>
typedef struct LinkNode{
int data;
struct LinkNode* next;
}LinkNode;
void printLink(LinkNode* header)
{
while(header != NULL) {
cout<< header->data;
header = header->next;
if (header != NULL) {
cout<< "->";
}
}
cout<<endl;
}
LinkNode* linkReverse(LinkNode* header)
{
if(header == NULL || header->next == NULL){
return header;
}
LinkNode* per = header;//保存原链表头结点
LinkNode* cur = header->next;//保存原链表第二个节点
per->next = NULL;//反转后，原链表头结点变成最后一个节点
while (cur != NULL) {
LinkNode* next = cur->next;//保存下一个待反转的节点
cur->next = per;//将带反转的节点插入头结点前
per = cur;//当前反转后的节点更新为头结点
cur = next;//更新下一个待反转节点
}
return per;
}
int main()
{
LinkNode* header = NULL;
LinkNode* cur = NULL;
for(int i = 1;i<=10;i++) {
LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
node->data = i;
node->next = NULL;
if(header == NULL && cur == NULL){
header = node;
cur = node;
} else {
cur->next = node;
cur = cur->next;
}
}
printLink(header);
LinkNode* reverse_link = linkReverse(header);
printLink(reverse_link);
return 0;
}
单链表
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <string.h>
using namespace std;
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;
typedef struct Node {
ElemType data;
struct Node* next;
}Node;
typedef struct Node * LinkList;
//创建一个含有n个元素的链表，data为100以内的随机值
void CreateListTail(LinkList& L,int n)
{
srand(time(0));
L = (LinkList)malloc(sizeof(Node));
LinkList r = L,p;
for(int j = 0;j < n;j++) {
p = (LinkList)malloc(sizeof(Node));
p -> data = rand()%100;
r -> next = p;
r = p;
}
r -> next = NULL;
}
//在链表的第i个元素后插入新元素e
Status ListInsert(LinkList& L,int i,ElemType e)
{
int j = 1;
LinkList p = L,s;
while (p && j < i) {
p = p->next;
++j;
}
if (!p || j>i) {
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p -> next;
p->next = s;
return OK;
}
//删除链表的第i个元素，并用e返回其data值，链表长度减一
Status ListDelete(LinkList& L,int i,ElemType* e)
{
int j = 1;
LinkList p = L,q;
while(p && j < i) {
p = p->next;
++j;
}
if (!p || j>i) {
return ERROR;
}
q = p -> next;
p->next = q -> next;
*e = q->data;
free(q);
free(p);
}
Status ListClear(LinkList& L)
{
LinkList p,q;
p = L -> next;
while(p) {
q= p->next;
free(q);
p = q;
}
L -> next = NULL;
return OK;
}
int main()
{
LinkList L;
int n = 10;
CreateListTail(L,n);
for(int i=0;i<n;i++){
static LinkList temp = L;
cout << temp -> data << endl;
temp = temp->next;
}
return 0;
}
双向链表
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct DOUBLE_LIST
{
int data;
struct DOUBLE_LIST *prev;
struct DOUBLE_LIST *next;
}double_list;
double_list *createlist() //创建有n个元素的双向链表 并输入元素
{
double_list *head, *p, *q;
int n,x;
head = (double_list *)malloc(sizeof(double_list));
head->prev = head;
head->next = head;
p = head;
printf("输入要创建双向链表的元素的个数：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d", &x);
q = (double_list *)malloc(sizeof(double_list));
q->data = x;
p->next = q;
head->prev = q;
q->prev = p;
q->next = head;
p = q;
}
return head;
}
//遍历并且输出这些元素
void printlist(double_list *head)
{
double_list *p;
p = head;
p = p->next;
while(p!=head)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//得到现在双向链表中的元素的个数
int lengthlist(double_list *head)
{
double_list *p;
p = head;
p = p->next;
int coun = 0;
while(p!=head)
{
coun++;
p = p->next;
}
return coun;
}
//在第i个元素之前插入数据data
void insertlist_f(double_list *head, int i, int data)
{
double_list *p = head, *q;
p = p->next;
i--;
while(i--)
p = p->next;
q = (double_list *)malloc(sizeof(double_list));
q->data = data;
(p->prev)->next = q;
q->prev = p->prev;
q->next = p;
p->prev = q;
}
//删除第i个位置的元素
void deletelist_i(double_list *head, int i)
{
double_list *p = head;
p = p->next;
i--;
while(i--)
p = p->next;
(p->prev)->next = p->next;
(p->next)->prev = p->prev;
free(p);
}
//删除值为x的元素
void deletelist_x(double_list *head, int x)
{
double_list *p = head, *q;
p = p->next;
while(p!=head)
if(p->data == x)
{
q = p->next;
(p->prev)->next = p->next;
(p->next)->prev = p->prev;
free(p);
p = q;
}
else
p = p->next;
}
//对双向链表进行排序
void sortlist(double_list *head) //升序
{
double_list *p = head, *q, *t;
p = p->next;
for(;p!=head;p=p->next)
for(t = p->next;t!=head;t=t->next)
{
if(p->data > t->data)
{
int a = p->data;
p->data = t->data;
t->data = a;
}
}
}
int main()
{
double_list *head;
head = createlist();
deletelist_x(head, 2);
//sortlist(head);
printlist(head);
insertlist_f(head, 2, 2);
printlist(head);
return 0;
}