数据结构与算法-线性表专题(二)-循环单链表

循环单链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环单链表是尾结点的指针域NULL改为指向头结点。

循环单链表

判断空链


空链

head == head->next;
rear == rear->next;

0.数据结构声明

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//单链表结构设计
typedef struct Node{
    ElementType data;//数据
    struct Node *next;//指针域
}Node;
typedef struct Node * SingleCycleLinkList;

1.初始化

Status InitList(SingleCycleLinkList *list){
    
    int item = 0;
    SingleCycleLinkList tempNode = NULL;
    SingleCycleLinkList targetNode = NULL;
    
    while (1) {
        
        if (*list == NULL) {//空表
            
            //初始化存储空间
            *list = (SingleCycleLinkList)malloc(sizeof(Node));
            //初始化失败，结束
            if(!list) exit(0);
            //数据赋值
            (*list)->data = item;
            //空表指针域指向自己
            (*list)->next = *list;
        }else{//非空表
            
            int i;
            targetNode = *list;
            //找到尾结点，使尾结点指向新结点，新结点指向头结点
            for (i = 0; targetNode->next != *list;targetNode = targetNode->next,i++)
                
            tempNode = (SingleCycleLinkList)malloc(sizeof(Node));

            if (tempNode == NULL) return ERROR;
            
            //数据赋值
            tempNode->data = item;
            //空表指针域指向头结点
            tempNode->next = *list;
            //尾结点指向新结点
            targetNode->next = tempNode;
        }
    }
    return OK;
}

SingleCycleLinkList list;
InitList(&list);

2.遍历

void Description(SingleCycleLinkList list){
    
    //空链
    if (list == NULL){
        
        printf("这是个空链！\n");
    }else{
        
        SingleCycleLinkList tempNode;
        tempNode = list;
        do {
            printf("%5d",tempNode->data);
            tempNode = tempNode->next;
        } while (tempNode != list);
        printf("\n");
    }
}

SingleCycleLinkList list;
InitList(&list);
Description(list);

3.插入

特别注意区分头结点


情况1

情况2
Status ListInsert(SingleCycleLinkList *list, int index, int data){
    
    SingleCycleLinkList temp, target;
    int i;
    if (index == 1) {
        
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 找到链表最后的结点_尾结点,
        //3. 让新结点的next 执行头结点.
        //4. 尾结点的next 指向新的头结点;
        //5. 让头指针指向temp(临时的新结点)
        
        temp = (SingleCycleLinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
    
        temp->data = data;
        //找到头结点
        for (target = *list; target->next != *list; target = target->next);
        temp->next = *list;
        target->next = temp;
        *list = temp;
        
    }else{
        
        //如果插入的位置在其他位置;
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
        
        temp = (SingleCycleLinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;

        temp->data = data;
        for ( i = 1,target = *list; target->next != *list && i != index - 1; target = target->next,i++) ;
        temp->next = target->next;
        target->next = temp;
    }
    
    return OK;
}

int index;
int data;
printf("输入要插入的位置和数据用空格隔开：");
scanf("%d %d",&index,&data);
ListInsert(&list,index,data);
Description(list);

4.删除


删除
Status ListRemove(SingleCycleLinkList *list,int targetIndex){
    
    SingleCycleLinkList temp,target;
    int i;
    //temp 指向链表首元结点
    temp = *list;
    if(temp == NULL) return ERROR;
    
    if (targetIndex == 1) {
        
        if ((*list)->next == *list) {//只有一个结点
            
            (*list) = NULL;
            return OK;
        }
        
        //如果删除的是头结点
        //找到尾结点，使尾结点的指针域指向头结点的下一个
        //标记当前头结点
        temp = *list;
        for (target = *list; target->next != *list; target = target->next);
        
        *list = (*list)->next;
        target->next = *list;
        free(temp);
    }else{
        
        //如果删除其他结点--其他结点
        //1. 找到删除结点前一个结点target targetIndex-1
        //2. 使得target->next 指向下一个结点
        //3. 释放需要删除的结点temp
        for (i = 1,target = *list; target->next != *list && i != targetIndex-1; target = target->next,i++){
            
            temp = target->next;
            target->next = temp->next;
            free(temp);
        }
    }
    
    return OK;
}

printf("输入要删除的位置：");
scanf("%d",&index);
ListRemove(&list, index);
Description(list);

5.查找

int IndexOfValueInList(SingleCycleLinkList list,int value){
    
    if (list == NULL) return -1;
    int index = 1;
    
    SingleCycleLinkList tempList = list;
    while (tempList->data != value && tempList->next != list) {
        
        index++;
        tempList = tempList->next;
    }
    
    if (tempList->next == list && tempList->data != value) {
        
        return -1;
    }
    
    return index;
}

int targetIndex = -1;
printf("输入要查询的数据：");
scanf("%d",&data);
targetIndex = IndexOfValueInList(list, data);
if(targetIndex != -1){
printf("%d位置是targetIndex = %d\n",data,targetIndex);
}else{
printf("查无此值\n");
}

思考：约瑟夫杀人问题

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,242评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,769评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,484评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,133评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,007评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,080评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,496评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,190评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,464评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,549评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,330评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,205评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,567评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,889评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,160评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,475评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,650评论 2赞 335