数据结构----链表

一丶概念

          链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
          和顺序表不同同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。

二丶特点

         特点：内存不连续，通过指针进行连接
         解决: 长度固定的问题，插入删除麻烦的问题
         逻辑结构：线性结构
         存储结构：链式存储
         操作：增删改查

struct node
{int data;   //数据域：存储数据struct node *next;    //指针域：存储下一个节点的地址
};

三丶单向链表

1.分类

        有头链表：存在一个头节点，头节点数据域无效，指针域有效。
        无头链表：每一个节点的数据域和指针域都有效。

2.有头单向链表

        存在一个头节点，数据域无效，指针域有效

#include <stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域struct node *next;//指针域
} node_t, *node_p;
int main(int argc, char const *argv[])
{node_t A={1,NULL};//输入数据node_t B={2,NULL};node_t C={3,NULL};node_t D={4,NULL};A.next=&B;B.next=&C;C.next=&D;node_p p;//头指针指向头节点node_t S = {'\0',&A};p=H.next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");return 0;
}

3.无头单向链表

所有节点的指针域和数据域都有效

#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;     //数据域用来存数据struct node *next; //指针域用来存下一个节点的地址
} node_t, *node_p;// node_t A; //等同于 struct node A;
// node_p p; //等同于 struct node *p;int main(int argc, char const *argv[])
{//1.定义4个节点node_t A = {'a', NULL};node_t B = {'b', NULL};node_t C = {'c', NULL};node_t D = {'d', NULL};//2.连接四个节点A.next = &B; //连接A和BB.next = &C;C.next = &D;//3.定义一个头指针指向第一个节点node_p p = &A;//4. 通过指针遍历无头单向链表while (p != NULL){printf("%c ", p->data); //打印节点中的数据域 a b c dp = p->next;            //让p指向下一个节点}printf("\n");return 0;
}

链表尾插法练习

写一个有头单向链表，用于保存输入的学生成绩，实现一输入学生成绩就创建一个新的节点，将成绩保存起来。再将该节点链接到链表的尾，直到输入-1结束。

要求：每个链表的节点由动态内存分配得到 , 也就是用malloc。

过程：

1.  malloc申请空间link_node_t大小作为头节点

2.  将新节点放到链表尾部

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域存放数据struct node *next;//指针域记录下一个结点地址
} node_t, *node_p;
void ShowLinklist(node_p p)//打印数据
{while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
int main(int argc, char const *argv[])
{int score = 0;// 创建一个头节点node_p p_head = (node_p)malloc(sizeof(node_t));if (NULL == p_head)//容错判断{printf("malloc err");return -1;}//让头指针的指针域置空p_head->next = NULL;//创建一个尾节点node_p p_tail = (node_p)malloc(sizeof(node_t));if (NULL == p_head){printf("p_tail malloc err");return -1;}p_tail = p_head;//让尾节点指向头节点while (1){//循环输入成绩scanf("%d", &score);//输入-1时停止结束循环if (score == -1)break;//新建一个节点p_newnode_p p_new = (node_p)malloc(sizeof(node_t));if (NULL == p_new)//容错判断{printf("p_new malloc err");return -1;}p_new->data = score; //将数据存入新的节点p_new->next = NULL;//让新的节点的指针域置空p_tail->next = p_new;//让尾节点连接到新的节点p_tail=p_new;//更新尾节点}node_p p = p_head->next;ShowLinklist(p);return 0;
}

4.有头单向链表的函数操作

插入的思想

1. 先遍历找到要插入节点的前一个节点，假设这个节点为A；A的下一个节点为B；将C插入A与B之间；
2.先让C的指针域指向B；
3.再让A的指针域指向C；

（注意：顺序不可以调换）

int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}

删除的思想

      1.先遍历找到要删除节点的前一个节点，假设为A；

      2、找一个临时指针指向要删除的节点；
      3、  将A的指针域指向删除节点的下一个节点；
      4、  释放被删除节点

int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放，指针置空p1 = NULL;
}

转置的思想：

(1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表
(2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)

void ReverseLinkList(node_p p)
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前，保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点（相当于无头单向链表的头指针）//1.断头，断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点，防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表，指向此时的第一个节点q=temp;}

完整的单链表操作

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;          // 数据域存放数据struct node *next; // 指针域记录下一个结点地址
} node_t, *node_p;
node_p CreateEpLinkist() // 创建一个空的有头单向链表
{node_p p = (node_p)malloc(sizeof(node_t)); // 开辟节点空间大小if (NULL == p){printf("CreatEpLinklist err");return NULL;}p->next = NULL; // 初始化头结点return p;
}
int StrlenLinklist(node_p p)//计算单链表长度
{int len = 0;while (p->next != NULL){p = p->next;len++;}return len;
}
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放，指针置空p1 = NULL;
}
void ModifyLinklist(node_p p, int post, int data) // 修改函数
{for (int i = 0; i <= post; i++) // 让指针指向要修改的节点位置p = p->next;p->data = data; // 指针域等于新的数据
}
void SearchLinklist(node_p p, int data)//查找数据
{int i = 0;p = p->next;while (p != NULL){if (p->data == data){printf("%d\n", i);//打印第一个相同数据的下标break;}p = p->next;i++;}
}
void ClearLinklist(node_p p)//清空链表
{while(StrlenLinklist(p)!=0){DeleteLinklist(p,0);//删除第一个节点}
}
void ShowLinklist(node_p p)// 打印数据
{while (p->next)// 当指针p的指针域为空时停止循环{p = p->next;printf("%d ", p->data);}printf("\n");
}
void ReverseLinkList(node_p p)//链表转置
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前，保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点（相当于无头单向链表的头指针）//1.断头，断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点，防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表，指向此时的第一个节点q=temp;}}
int IsEpLinklist(node_p p)
{return p->next == NULL;
}
int main(int argc, char const *argv[])
{node_p p = CreateEpLinkist(); // 创建一个空的有头单向链表InsertLinklist(p, 0, 1);// 进行插入数据InsertLinklist(p, 1, 2);InsertLinklist(p, 2, 3);InsertLinklist(p, 3, 4);InsertLinklist(p, 4, 5);InsertLinklist(p, 5, 6);ShowLinklist(p);// 打印数据DeleteLinklist(p, 0);// 删除数据ShowLinklist(p);// 打印数据ModifyLinklist(p, 0, 0); // 修改数据ShowLinklist(p);// 打印数据SearchLinklist(p, 2);ReverseLinkList(p);ShowLinklist(p);// 打印数据ClearLinklist(p);if(IsEpLinklist(p))printf("IsEpLinkList\n");free(p);p =NULL;return 0;return 0;
}

5.单向循环链表

四丶总结：

顺序表和单向链表比较：
             (1).顺序表在内存当中连续存储的(数组)，但是链表在内存当中是不连续存储的，通过指针将数据链接在一起
            (2).顺序表的长度是固定的，但是链表长度不固定
            (3).顺序表查找方便，但是插入和删除麻烦，链表，插入和删除方便，查找麻烦