数据结构学习——3
一、循环链表(约瑟夫环)
源码
/*===============================================
* 文件名称：joseph.c
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：约瑟夫环
================================================*/
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct Node
{
data_t data;
struct Node *next;
}link_t;
//joseph func
void joseph(link_t *head,int k,int m,int len)
{
link_t *q,*p = head;
//移动到第k个人
for(int i = 1 ; i < k ; i++)
{
p = p->next;
}
printf("出队序列: \n");
while(p->next != p)
{
//开始计数，找到报出m的人的前一个位置，方便删除
for(int i = 1 ; i < m - 1 ; i++)
{
p = p->next;
}
//q为要出队的人
q = p->next;
//出队的人前驱，连上该人的后继
p->next = q->next;
//出队后后继补位上来
p = p->next;
//输出出队人的编号
printf("%4d",q->data);
free(q);
}
printf("\t最后未出队编号: %d",p->data);
free(p);
printf("\n");
}
//初始化循环单链表
link_t *joseph_ring_init(int n)
{
link_t *p,*q,*head = NULL;
for(int i = 1 ; i <= n ; i++)
{
p = (link_t *)malloc(sizeof(link_t));
p->data = i;
if(head == NULL)
head = p;
else
q->next = p;
q = p;
}
p->next = head;
return head;
}
int main(int argc, char *argv[])
{
int n;
printf(">:");
scanf("%d",&n);
link_t *p,*head = joseph_ring_init(n);
p = head;
for(int i = 0 ; i < n + 10 ; i++)
{
printf("%4d",p->data);
p = p->next;
}
printf("\n");
joseph(head,3,4,n);
return 0;
}
运行结果
二、双向链表
每个节点有两个指针，一个用于指向下一个节点，一个用于指向上一个节点。
结构
typedef int data_t;
typedef struct Node
{
data_t data;
struct Node *prior;
struct Node *next;
}dlink_t;
dlink.h
/*===============================================
* 文件名称：dlink.h
* 创 建 者：
* 创建日期：2025年07月29日
* 描 述：
================================================*/
#ifndef __DLINK_H__
#define __DLINK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct Node
{
data_t data;
struct Node *prior,*next;
}dlink_t;
//create
dlink_t *link_create();
//empty
int is_empty(dlink_t *head);
//length
int link_length(dlink_t *head);
//clear
void link_clear(dlink_t *head);
//show
void link_show(dlink_t *head);
//insert
int link_insert(dlink_t *head,data_t data,int pos);
//delete
int link_delete(dlink_t *head,data_t data);
//search
dlink_t *link_search(dlink_t *head,data_t data);
//alter
int link_alter(dlink_t *head,data_t old_val,data_t new_val);
#endif
dlink.c
/*===============================================
* 文件名称：dlink.c
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：双向循环链表
================================================*/
#include "dlink.h"
dlink_t *link_create()
{
dlink_t *head = (dlink_t *)malloc(sizeof(dlink_t));
if(head == NULL)
return NULL;
head->next = NULL;
head->prior = NULL;
head->data = -1;
return head;
}
//empty
int is_empty(dlink_t *head)
{
return head->next == NULL;
}
//length
int link_length(dlink_t *head)
{
dlink_t *p = head;
int count = 0;
while(p != NULL)
{
count++;
p = p->next;
}
return count;
}
//clear
void link_clear(dlink_t *head)
{
if(head->next == NULL)
return;
dlink_t *p,*q;
p = q = head->next;
while(p->next != NULL)
{
q = p;
p = p->next;
free(q);
}
}
//show
void link_show(dlink_t *head)
{
dlink_t *p = head->next;
while(p != NULL)
{
printf("%4d ",p->data);
p = p->next;
}
printf("\n");
}
//insert
int link_insert(dlink_t *head,data_t data,int pos)
{
if(pos < 0 || pos > link_length(head))
return 0;
dlink_t *p = head;
while(pos--)
p = p->next;
dlink_t *new = (dlink_t *)malloc(sizeof(dlink_t));
new->data = data;
//判断是不是在表尾插入
if(p->next == NULL)
{
new->next = NULL;
}
else
{
p->next->prior = new;
new->next = p->next;
}
p->next = new;
new->prior = p;
return 1;
}
//delete
int link_delete(dlink_t *head,data_t data)
{
if(is_empty(head))
return 0;
dlink_t *q,*p = head->next;
while(p != NULL)
{
if(p->data != data)
{
p = p->next;
continue;
}
//判断是不是在表尾删除
q = p;
if(q->next == NULL)
q->prior->next = NULL;
else
{
q->next->prior = q->prior;
q->prior->next = q->next;
}
free(q);
p = p->next;
}
return 1;
}
//search
dlink_t *link_search(dlink_t *head,data_t data)
{
if(is_empty(head))
return NULL;
dlink_t *p = head->next;
while(p != NULL)
{
if(p->data == data)
return p;
p = p->next;
}
return NULL;
}
//alter
int link_alter(dlink_t *head,data_t old_val,data_t new_val)
{
if(is_empty(head))
return 0;
dlink_t *p = link_search(head,old_val);
if(p == NULL)
{
printf("The old_val has not find!\n");
return 0;
}
p->data = new_val;
return 1;
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：双向循环链表
================================================*/
#include "dlink.h"
int main(int argc, char *argv[])
{
dlink_t *head = link_create();
for(int i = 0 ; i < 10 ; i++)
link_insert(head,i+1,i);
link_insert(head,5,10);
link_show(head);
link_delete(head,5);
link_show(head);
link_alter(head,3,200);
link_show(head);
link_alter(head,100,105);
return 0;
}
运行截图
双向链表：弥补了单链表的无法找到前驱的缺点
三、双向循环链表
类型：头结点依旧充当链表的起始位置，但是不参与循环
cycdlink.h
/*===============================================
* 文件名称：cycdlink.h
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：双向循环链表
================================================*/
#ifndef __CYCDLINK_H__
#define __CYCDLINK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct Node
{
data_t data;
struct Node *next,*prior;
}dlink_t;
//create
dlink_t *link_create();
//empty
int is_empty(dlink_t *head);
//length
int link_length(dlink_t *head);
//clear
void link_clear(dlink_t *head);
//show
void link_show(dlink_t *head);
//insert
int link_insert(dlink_t *head,data_t data,int pos);
//delete
int link_delete(dlink_t *head,data_t data);
//search
dlink_t *link_search(dlink_t *head,data_t data);
//alter
int link_alter(dlink_t *head,data_t old_val,data_t new_val);
#endif
cycdlink.c
/*===============================================
* 文件名称：cycdlink.c
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：双向循环链表
================================================*/
#include "cycdlink.h"
//create
dlink_t *link_create()
{
dlink_t *head = (dlink_t *)malloc(sizeof(dlink_t));
if(head == NULL)
return NULL;
head->next = NULL;
head->prior = NULL;
head->data = -1;
return head;
}
//empty
int is_empty(dlink_t *head)
{
return head->next == NULL;
}
//length
int link_length(dlink_t *head)
{
if(is_empty(head))
return 0;
int count = 0;
dlink_t *p = head->next;
//遍历计数，在头元素的前驱结束
while(p != head->next->prior)
{
p = p->next;
count++;
}
//记入尾部元素个数
count += 1;
return count;
}
//clear
void link_clear(dlink_t *head);
//show
void link_show(dlink_t *head)
{
if(is_empty(head))
return;
dlink_t *p = head->next;
while(p != head->next->prior)
{
printf("%4d ",p->data);
p = p->next;
}
//输出尾元素的data
printf("%4d\n",p->data);
}
//insert
int link_insert(dlink_t *head,data_t data,int pos)
{
dlink_t *p = head->next;
dlink_t *new = (dlink_t *)malloc(sizeof(dlink_t));
new->data = data;
//空表直接插入，无需计算pos位置
if(p == NULL)
{
head->next = new;
new->next = new;
new->prior = new;
return 1;
}
//根据pos位置往左或右插入
if(pos < 0)
while(pos++) //往左寻找插入位置
p = p->prior;
else
while(pos--) //往右寻找位置
p = p->next;
new->next = p->next;
p->next->prior = new;
p->next = new;
new->prior = p;
return 1;
}
//search
dlink_t *link_search(dlink_t *head,data_t data)
{
if(is_empty(head))
return NULL;
dlink_t *p = head->next;
while(1)
{
if(p->data == data)
return p;
//判断是否为尾元素
if(p == head->next->prior)
break;
p = p->next;
}
//运行到此处表明完整遍历一遍之后没有找到对应值，返回空
return NULL;
}
//alter
int link_alter(dlink_t *head,data_t old_val,data_t new_val)
{
dlink_t *p = link_search(head,old_val);
if(p == NULL)
return 0;
p->data = new_val;
return 1;
}
//delete
int link_delete(dlink_t *head,data_t data)
{
//调用search函数，找到对应的节点
dlink_t *p = link_search(head,data);
if(p == NULL)
return 0;
//节点个数为1 直接删除
if(link_length(head) == 1)
{
head->next = NULL;
free(p);
return 1;
}
//删除节点是head->next指向节点
if(p == head->next)
{
head->next = p->next;
}
//更改相应前驱、后继
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
return 1;
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：青木莲华
* 创建日期：2025年07月29日
* 描 述：双向循环链表
================================================*/
#include "cycdlink.h"
int main(int argc, char *argv[])
{
dlink_t *head = link_create();
link_insert(head,0,0);
for(int i = 1 ; i < 5 ; i++)
link_insert(head,i,i);
for(int i = -1; i >= -5 ; i--)
link_insert(head,i,i);
printf("show: ");
link_show(head);
printf("test loop: ");
dlink_t *p = head->next;
for(int i = 0 ; i < link_length(head)+5;i++)
{
printf("%4d ",p->data);
p = p->next;
}
printf("\ndelete Node of head->next: ");
link_delete(head,0);
link_show(head);
printf("test alter(old_val=3,new_val=50):");
link_alter(head,3,50);
link_show(head);
return 0;
}
运行截图
京公网安备 11010502036488号