数据结构链表

链表

特点:内存不连续，通过指针进行连接

解决：长度固定问题，插入、删除麻烦的问题

1）逻辑结构 ： 线性结构

2）存储结构 ：链式存储

3）操作 ： 增删改查

2.1单向链表

结构体：

struct node_t

{

int data;//数据域

struct node_t * next;//指针域，存放下一个节点地址

}；

2.1.1分类

1）有头单向链表

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

遍历有头单向链表：

#include<stdio.h>
typedef struct node_t
{int data;struct node_t *next;
}link_node_t,* link_list_t;
//link_list_t == link_node_t *
int main(int argc, char const *argv[])
{//1.定义3个节点
    link_node_t a = {1,NULL};
    link_node_t b = {2,NULL};
    link_node_t c = {3,NULL};//2.将节点进行连接
    a.next = &b;
    b.next = &c;//3.定义一个头节点指向第一个节点
    link_node_t s ;
    s.next = &a;//4.定义一个头指针指向头结点// link_node_t * h = &s;    link_list_t h = &s;//5.遍历有头单向链表//方法1：直接遍历有头单向链表/*
    while(h->next != NULL)
    {
        h=h->next;
        printf("%d ",h->data);
    }    *///方法2：先变成无头，再遍历
   h=h->next;while (h!= NULL){printf("%d ",h->data);
     h=h->next;}printf("\n");return 0;
}

2）无头单向链表

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

遍历无头单向链表：

#include<stdio.h>
typedef struct node_t
{int data;struct node_t *next;
}link_node_t,* link_list_t;
//link_list_t == link_node_t *
int main(int argc, char const *argv[])
{//1.定义3个节点
    link_node_t a = {1,NULL};
    link_node_t b = {2,NULL};
    link_node_t c = {3,NULL};//2.将节点进行连接
    a.next = &b;
    b.next = &c;//3.定义一个头指针指向第一个结点// link_node_t * h = &a;    link_list_t h = &a;//4.遍历无头单向链表while(h != NULL){printf("%d ",h->data);
        h=h->next; }printf("\n");return 0;
}

2.1.2操作函数

linklist.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_#include<stdio.h>
#include<stdlib.h>typedef int datatype;
typedef struct node_t
{
	datatype data;//数据域struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.遍历单向链表
void ShowLinkList(link_node_t *p);
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
//7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
//8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
//9.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data);
//10.转置链表
void ReverseLinkList(link_node_t *p);
//11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif

1）创建一个空的（有头）单向链表

2）向post位置插入一个数据

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

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

3）删除指定位置的数据

linklist.c

#include "linklist.h"// 1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList()
{// 1.开辟空间用来存放头结点
    link_list_t p = (link_list_t)malloc(sizeof(link_node_t));if (p == NULL){perror("CreateEpLinkList ERR");return NULL;}// 2.初始化
    p->next = NULL;return p;
}
// 4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{int num = 0;while (p->next != NULL){
        p = p->next;
        num++;}return num;
}
// 2.向单向链表的指定位置插入数据
// p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p, int post, datatype data)
{// 0.容错判断if (post < 0 || post > LengthLinkList(p)){perror("InsertIntoPostLinkList err");return -1;}// 1.将头指针指向被插入位置的前一个节点for (int i = 0; i < post; i++)
        p = p->next;// 2.创建一个新节点，存放数据
    link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));if (pnew == NULL){perror("pnew malloc err");return -1;}
    pnew->data = data;
    pnew->next = NULL;// 3.将新节点插入链表中（先连后面，再连前面）
    pnew->next = p->next;
    p->next = pnew;return 0;
}
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{return p->next == NULL;
}
// 5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)
{// 0.容错判断if (post < 0 || post >= LengthLinkList(p)){perror("DeletePostLinkList err");return -1;}// 1.将头指针指向被删除位置的前一个节点for (int i = 0; i < post; i++)
        p = p->next;// 2.进行删除操作// 1）定义一个指针pdel指向被删除位置
    link_list_t pdel = p->next;// 2）跨过被删除节点
    p->next = pdel->next;// 3）释放被删除节点free(pdel);
    pdel = NULL;return 0;
}
//3.遍历单向链表
void ShowLinkList(link_node_t *p)
{while (p->next !=NULL){
        p=p->next;printf("%d ",p->data);}printf("\n");}

main.c

#include"linklist.h"
int main(int argc, char const *argv[])
{
    link_list_t p = CreateEpLinkList();for(int i=0;i<5;i++)InsertIntoPostLinkList(p,i,i+1);ShowLinkList(p);DeletePostLinkList(p,0);ShowLinkList(p);while (!IsEpLinkList(p))DeletePostLinkList(p,0);free(p);
    p=NULL;return 0;
}