嵌入式学习-线性表Day05-双向链表

双向链表

操作函数

1）创建一个空的双向链表

2）双向链表中间插入

3)双向链表尾插

4）双线链表中间删除

5）双线链表删除最后一个节点

双向循环链表

双向链表

//双向链表的节点定义

typedef int datatype;

typedef struct node_t

{

datatype data;//数据域

struct node_t *next;//指向下一个节点的指针 next 下一个

struct node_t *prior;//指向前一个节点的指针 prior 先前的

}link_node_t,*link_list_t;

//将双向链表的头指针和尾指针封装到一个节点体里

//思想上有点像学的链式队列

typedef struct doublelinklist

{

link_list_t head; //指向双向链表的头指针

link_list_t tail; //指向双向链表的尾指针

int len; //用来保存当前双向链表的长度

}double_node_t,*double_list_t;

操作函数

1）创建一个空的双向链表

2）双向链表中间插入

​​​​​​​3)双向链表尾插

4）双线链表中间删除

5）双线链表删除最后一个节点

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
    datatype data;        // 数据域
    struct node_t *next;  // 指向下一个节点的指针 next 下一个
    struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} link_node_t, *link_list_t;// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{
    link_list_t head; // 指向双向链表的头指针
    link_list_t tail; // 指向双向链表的尾指针
    int len;
} double_node_t, *double_list_t;
// 1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{// 1.开辟存放头尾指针结构体的空间
    double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
    if (p == NULL){perror("createEmptyDoubleLinkList err");
        return NULL;}// 2.初始化（开辟头节点的空间）
    p->len = 0;
    p->tail = p->head = (link_list_t)malloc(sizeof(link_node_t));
    if (p->tail == NULL){perror("p->tail malloc err");
        return NULL;}// 3.初始化头节点
    p->tail->next = NULL;
    p->tail->prior = NULL;
    return p;
}
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{// 0.容错判断
    if (post < 0 || post > p->len){perror("insertIntoDoubleLinkList err");
        return -1;}// 1.开辟一个新节点存放数据，初始化
    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->prior = NULL;
    pnew->next = NULL;// 2.将新节点插入链表// 分两种情况// 尾插
    if (post == p->len){
        p->tail->next = pnew;
        pnew->prior = p->tail;
        p->tail = pnew; // 移动尾指针}
    else // 中间插入{// 1)temp指针指向被插入位置
        link_list_t temp = NULL;
        if (post < p->len / 2) // 前半段(从前向后移动){
            temp = p->head;
            for (int i = 0; i <= post; i++)
                temp = temp->next;}
        else // 后半段（从后向前移动）{
            temp = p->tail;
            for (int i = 0; i < p->len - 1 - post; i++)
                temp = temp->prior;}// 2)进行插入操作（先连前面，再连后面）
        temp->prior->next = pnew;
        pnew->prior = temp->prior;
        temp->prior = pnew;
        pnew->next = temp;}// 链表长度+1
    p->len++;
    return 0;
}
// 3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{printf("正向遍历：");
    link_list_t temp = p->head;
    while (temp->next != NULL){
        temp = temp->next;printf("%d  ", temp->data);}printf("\n-------------------\n");printf("反向遍历：");
    temp = p->tail;
    while (temp != p->head){printf("%d  ", temp->data);
        temp = temp->prior;}printf("\n-------------------\n\n");
}
// 5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{
    return p->len == 0;
}
// 4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{// 1.容错判断
    if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p)){perror("deletePostDoubleLinkList err");
        return -1;}// 2.对删除位置进行判断
    if (post == p->len - 1) // 尾删{
        p->tail = p->tail->prior; // 向前移动尾指针free(p->tail->next);      // 释放被删除节点
        p->tail->next = NULL;}
    else // 中间删{// 1)将temp移动到被删除位置
        link_list_t temp = NULL;
        if (post < p->len / 2) // 前半段{
            temp = p->head;
            for (int i = 0; i <= post; i++)
                temp = temp->next;}
        else // 后半段{
            temp = p->tail;
            for (int i = 0; i < p->len - 1 - post; i++)
                temp = temp->prior;}// 2)进行删除操作
        temp->prior->next = temp->next;
        temp->next->prior = temp->prior;free(temp);
        temp = NULL;}// 链表长度-1
    p->len--;
    return 0;
}
// 6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{
    return p->len;
}
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p, datatype data)
{
    link_list_t h = p->head;
    int post = 0;
    while (h->next != NULL){
        h = h->next;
        if (h->data == data)
            return post;
        post++;}
    return -1;
}
// 8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
{// 1.容错判断
    if (post < 0 || post >= p->len){perror("changeDataDoubleLinkList err");
        return -1;}// 2.将temp移动到被修改位置
    link_list_t temp = NULL;
    if (post < p->len / 2) // 前半段{
        temp = p->head;
        for (int i = 0; i <= post; i++)
            temp = temp->next;}
    else // 后半段{
        temp = p->tail;for(int i=0;i<p->len-1-post;i++)
            temp=temp->prior;}// 3.修改数据
    temp->data = data;
    return 0;
}
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{
    link_list_t h = p->head->next;
    link_list_t pdel = NULL;//1.遍历无头单向链表
    while (h!= NULL){if(h->data == data) //删除{if(h == p->tail)//尾删{
                p->tail = p->tail->prior;free(p->tail->next);
                p->tail->next=NULL;
                h = NULL;//结束遍历}
            else//中间删除{
                h->prior->next = h->next;
                h->next->prior = h->prior;
                pdel = h;
                h = h->next;//继续遍历free(pdel);
                pdel = NULL;}
            p->len--;//长度-1}
        else//不删除
            h=h->next;}
    return 0;
}
int main(int argc, char const *argv[])
{
    double_list_t p = createEmptyDoubleLinkList();
    for (int i = 1; i <= 5; i++)insertIntoDoubleLinkList(p, i - 1, i);showDoubleLinkList(p); // 1 2 3 4 5insertIntoDoubleLinkList(p, 1, 200);showDoubleLinkList(p); // 1 200 2 3 4 5deletePostDoubleLinkList(p, 2);showDoubleLinkList(p);                                            // 1 200 3 4 5printf("%d post is %d\n", 200, searchPostDoubleLinkList(p, 200)); // 1changeDataDoubleLinkList(p,1,300);showDoubleLinkList(p);//1 300 3 4 5deleteDataDoubleLinkList(p,300);showDoubleLinkList(p);//1 3 4 5
    while (!isEmptyDoubleLinkList(p)){deletePostDoubleLinkList(p, 0);}free(p->head);
    p->head = NULL;free(p);
    p = NULL;    return 0;
}

双向循环链表

双向循环链表	解决约瑟夫问题
#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node_t
{
	datatype data;struct node_t * prior;struct node_t * next;
}link_node_t,*link_list_t;typedef struct doublelinklist
{
	link_list_t head;
	link_list_t tail;
}double_node_t,*double_list_t;int main(int argc, const char *argv[])
{int i;int all_num = 8;//猴子总数int start_num = 3;//从3号猴子开始数int kill_num = 3;//数到几杀死猴子 
	link_list_t h = NULL;
	link_list_t pdel = NULL;//用来指向被杀死猴子的节点printf("请您输入猴子的总数，开始号码，出局号码:\n");scanf("%d%d%d",&all_num,&start_num,&kill_num);//1.创建一个双向的循环链表
	double_list_t p = (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针if(NULL == p){perror("malloc failed");return -1;}
	p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));if(NULL == p->tail){perror("p->tail malloc failed");return -1;}
	p->head->data = 1;
	p->head->prior = NULL;
	p->head->next = NULL;//将创建n个新的节点，链接到链表的尾for(i = 2; i <= all_num; i++){
		link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));if(NULL == pnew){perror("pnew malloc failed");return -1;}
		pnew->data = i;
		pnew->prior = NULL;
		pnew->next = NULL;//(1)将新的节点链接到链表的尾
		p->tail->next = pnew;
		pnew->prior = p->tail;//(2)尾指针向后移动，指向当前链表的尾
		p->tail = pnew;}//(3)形成双向循环链表 
	p->tail->next = p->head;
	p->head->prior = p->tail;//调试程序 
#if 0while(1){printf("%d\n",p->head->data);
		p->head = p->head->next;sleep(1);}
#endif//2.循环进行杀死猴子
	h = p->head;//(1)先将h移动到start_num处，也就是开始数数的猴子号码处for(i = 0; i < start_num-1; i++)
		h = h->next;while(h->next != h)//当h->next == h 就剩一个节点了，循环结束{//(2)将h移动到即将杀死猴子号码的位置for(i = 0; i < kill_num-1; i++)
			h = h->next;//(3)进行杀死猴子，经过上面的循环后，此时的h指向即将杀死的猴子
		h->prior->next = h->next;
		h->next->prior = h->prior;
		pdel = h;//pdel指向被杀死猴子的位置printf("kill is -------%d\n",pdel->data);
		h = h->next;//需要移动，从杀死猴子后的下一个位置开始数free(pdel);}printf("猴王是%d\n",h->data);return 0;
}