单循环链表的初始化、创建、删除、查找与遍历

单循环链表的基本操作
服务器君一共花费了287.747 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

链表、双链表、单循环链表、双循环链表 的实现代码都差不多,区别只是在对指针域的修改。下面,是对单循环链表的实现:

#include <stdio.h>
#include <stdlib.h>

/*存储结构的定义*/
typedef struct CLinkList {
    int data ;
    struct CLinkList * next ;
}node;

int main()
{
    node * pHead = NULL ;
    char opp;
    int find;

    printf("\n1.初始化链表 \n2.插入结点 \n3.删除结点 \n4.返回结点位置 \n5.遍历链表  \n0.退出 \n请选择你的操作:\n");
    while(opp != '0'){
        scanf("%c",&opp);
        switch(opp){
            case '1':
                ds_init(&pHead);
                printf("\n");
                ds_traverse(pHead) ;
                break;

            case '2':
                printf("输入需要插入结点的位置?");
                scanf("%d", &find);
                ds_insert(&pHead,find) ;
                printf("在位置%d插入值后:\n", find) ;
                ds_traverse(pHead) ;
                printf("\n");
                break;

            case '3':
                printf("输入需要删除的结点位置?");
                scanf("%d", &find);
                ds_delete(&pHead,find) ;
                printf("删除第%d个结点后:\n", find) ;
                ds_traverse(pHead) ;
                printf("\n");
                break;

            case '4':
                printf("你要查找倒数第几个结点的值?");
                scanf("%d", &find);
                printf("元素%d所在位置:%d\n", find, ds_search(pHead,find)) ;
                //ListTraverse(L);
                printf("\n");
                break;

            case '5':
                ds_traverse(pHead) ;
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }

    return 0 ;
}


/************************************************************************/
/* 操作                                                                 */
/************************************************************************/

/*初始化循环链表*/
void ds_init(node ** pNode) {
    int item ;
    node * temp ;
    node * target ;

    printf("输入结点的值,输入0完成初始化\n");
    while(1) {
        scanf("%d",&item) ;
        fflush(stdin) ;
        if(item == 0)
            return ;

        if((*pNode) == NULL) { /*循环链表中只有一个结点*/
                *pNode = (node*)malloc(sizeof(struct CLinkList)) ;
                if(!(*pNode))
                    exit(0) ;
                (*pNode)->data = item ;
                (*pNode)->next = *pNode ;
            }
        else {
            /*找到next指向第一个结点的结点*/
            for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ;

            /*生成一个新的结点*/
            temp = (node *) malloc(sizeof(struct CLinkList)) ;
            if(!temp)
                exit(0) ;
            temp->data = item ;
            temp->next = *pNode ;
            target->next = temp ;
        }
    }
}

/*插入结点*/
/*参数:链表的第一个结点,插入的位置*/
void ds_insert(node ** pNode ,int i) {
    node * temp ;
    node * target ;
    node * p ;
    int item ;
    int j = 1 ;

    printf("输入要插入结点的值:");
    scanf("%d",&item) ;

    if(i == 1) { //新插入的结点作为第一个结点
        temp = (node *)malloc(sizeof(struct CLinkList)) ;
        if(!temp)
            exit(0) ;
        temp ->data = item ;

        /*寻找到最后一个结点*/
        for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ;
        temp->next = (*pNode) ;
        target->next = temp ;
        *pNode = temp ;
    }
    else {
        target = *pNode ;
        for( ; j < (i-1) ; target=target->next,++ j) ;
        temp = (node *)malloc(sizeof(struct CLinkList)) ;
        if(!temp)
            exit(0) ;
        temp ->data = item ;
        p = target->next ;
        target->next = temp ;
        temp->next = p ;
    }
}

/*删除结点*/
void ds_delete(node ** pNode,int i) {
    node * target ;
    node * temp ;
    int j = 1 ;

    if(i == 1) { //删除的是第一个结点
        /*找到最后一个结点*/
        for(target = *pNode ; target->next != *pNode ;target = target->next) ;
        temp = *pNode ;
        *pNode = (*pNode)->next ;
        target->next = *pNode ;
        free(temp) ;
    }
    else {
        target = *pNode ;
        for( ; j < i-1 ; target= target->next,++j) ;
        temp = target->next ;
        target->next = temp->next ;
        free(temp) ;
    }
}

/*返回结点所在位置*/
int ds_search(node * pNode,int elem) {
    node * target ;
    int i = 1 ;

    for(target = pNode ; target->data != elem && target->next != pNode ; ++i , target = target->next) ;
    if(target->next == pNode) /*表中不存在该元素*/
        return 0 ;
    else
        return i ;
}
/*遍历*/
void ds_traverse(node * pNode) {
    node * temp ;
    temp = pNode ;
    printf("***********链表中的元素******************\n");
    do {
        printf("%4d ",temp->data) ;
    }while((temp = temp->next) != pNode) ;
    printf("\n") ;
}

你可以全部代码拷到IDE运行。

延伸阅读

此文章所在专题列表如下:

  1. 结构之美:定义一个线性表
  2. 结构之美:线性表的查找、插入与删除操作
  3. 结构之美:线性表的链式存储结构——链表
  4. 结构之美:单链表的初始化、创建与遍历
  5. 结构之美:单链表的头结点与头指针
  6. 结构之美:使用头插法创建单链表
  7. 结构之美:使用尾插法创建单链表
  8. 结构之美:单链表的销毁删除
  9. 结构之美:查找单链表指定位置结点的数据
  10. 结构之美:在单链表指定位置插入数据
  11. 结构之美:删除单链表指定位置的数据
  12. 结构之美:单链表逆序
  13. 结构之美:判断单链表中是否有环
  14. 结构之美:获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美:双向循环链表的结构与定义

本文地址:http://www.nowamagic.net/librarys/veda/detail/1875,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1875

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《UNIX环境高级编程(第2版)》 史蒂文斯 (作者), 拉戈 (作者), 尤晋元 (译者), 张亚英 (译者), 戚正伟 (译者)

《UNIX环境高级编程(第2版)》是被誉为UNIX编程“圣经”的Advanced Programming in the UNIX Environment一书的更新版。在本书第1版出版后的十几年中,UNIX行业已经有了巨大的变化,特别是影响UNIX编程接口的有关标准变化很大。本书在保持了前一版的风格的基础上,根据最新的标准对内容进行了修订和增补,反映了最新的技术发展。书中除了介绍UNIX文件和目录、标准I/O库、系统数据文件和信息、进程环境、进程控制、进程关系、信号、线程、线程控制、守护进程、各种I/O、进程间通信、网络IPC、伪终端等方面的内容,还在此基础上介绍了多个应用示例,包括如何创建数据库函数库以及如何与网络打印机通信等。

更多计算机宝库...