【数据结构】之 线性表详解(5)

?

循环单链表

定义

循环链表是一个首尾相接的链表。将单链表最后一个结点的指针域有NULL改为指向表头结点，就得到了单链形式的循环链表，并成为循环单链表。

对于循环单链表，若经常要在首尾两端进行操作，则可以设一个为指针在表尾（如下图中C）。

c语言定义如下：

typedef struct cNode{
    char data;
    int len;    //表长 
    struct cNode *next;
}Node,*cNode;

创建

和前面一样，这里只讲尾插法创建

?

//尾插法建立表 
cNode createFromTail(cNode L){
    Node *s,*r;
    int i = 0,flag = 1;
    char data;
    
    r = L;
    printf("尾插法建立表,&data);
        getchar();
        if(data != '#'){
            s = (cNode)malloc(sizeof(Node));
            s->data = data;
            s->next = r->next;
            r->next = s;
            r = s;
            L->len++;
        }else{
            printf("结束输入...\n");
            flag = 0;
        }
    }
    r->next = L;
    print(L);
    return L;
}

基本操作

查找

//按内容查找
cNode searchAsContent(cNode L){
    Node *p;
    char data;
    int i = 1; 
    
    p = L->next;
    printf("\n请输入查找内容：");
    scanf("%c",&data);
    getchar();
    
    //遍历完表且未找到数据退出循环， 找到数据时退出函数 
    while(p != L){
        if(p->data == data){
            printf("按内容查找成功，第 %d 个位置的数据为 %c\n",p->data);
            return p;
        }
        p = p->next;
        i++;
    }
    
    //未找到数据
    if(p == L){
        printf("按内容查找失败！未在表中找到数据！\n");
    }
}  

?

插入

//插入
cNode insertCNode(cNode L){
    Node *pre,*s;    
    int k,i;
    char data;
    pre = L->next;
    k = 1;
    printf("\n请输入你要插入的位置和内容(格式: address content)：");
    scanf("%d %c",&data);
    getchar();
    
    //插入位置不可能为负 
    if(i <= 0){
        printf("插入失败！插入位置不合法！插入位置不能为负\n");
        return NULL;
    }
    
    ////遍历完表且未找到插入位置(此时i大于表的长度) 或 找到插入位置时退出函数 退出循环
    while(pre != L && k < i - 1){
        pre = pre->next;
        k++;
    }
    
    if(pre == L){
        
        // 未找到插入位置(此时i大于表的长度)
        printf("插入失败！插入位置不合法！插入位置超出表的长度\n");
        return NULL;
    }else{
        
        //找到插入位置并插入数据     ，注意:pre指向插入位置的前一个结点  
        s = (cNode)malloc(sizeof(Node));
        s->data = data;
        s->next = pre->next;
        pre->next = s;
        L->len++; 
        printf("插入成功！");
        print(L);
        return L;
    }
} 

?

删除

//删除 
cNode delList(cNode L){
    Node *pre,i;
    pre = L;
    printf("请输入删除的数据的位置(格式：address)：");
    scanf("%d",&i); 
    getchar();
    
    //删除的位置必须合法 
    if(i > L->len || i<= 0){
        printf("删除的位置超出了链表的长度!\n");
        return;
    }
    
    // 找到删除位置退出
    while(pre->next != L && k < i - 1){
        pre = pre->next;
        k++;
    }
    
    //删除操作 
    r = pre->next;
    pre->next = r->next;
    free(r);
    L->len--;
    printf("删除成功！\n"); 
    print(L);
    return L;
} 

?

（编辑：ASP站长网）