| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 546 人关注过本帖, 1 人收藏
标题:《大话数据结构》读书笔记之线性表抽象数据类型(双向循环链表实现)
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  问题点数:0  回复次数:1   
《大话数据结构》读书笔记之线性表抽象数据类型(双向循环链表实现)
/*
    Name: 线性表抽象数据类型(使用双向循环链表实现)
    Copyright:
    Author: 巧若拙
    Date:13-09-14 17:07
    Description:
*/

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

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型,其值是函数结果状态代码,如OK等

typedef struct DuNode{
    ElemType data;//数据域
    struct DuNode *prior;//直接前驱指针
    struct DuNode *next;//直接后继指针
} DuNode, *DuLinkList;

Status InitList(DuLinkList *L);//建立一个带头结点的空线性表L
Status ListEmpty(DuLinkList L);//判断线性表是否为空,若线性表为空,返回TRUE,否则返回FALSE
Status ClearList(DuLinkList *L);//将线性表清空(只留下头结点)
int ListLength(DuLinkList L);//返回线性表L的元素个数
Status DisplayList(DuLinkList L);//输出线性表L的所有元素
Status GetElem(DuLinkList L, int i, ElemType *e);//将线性表L中第i个位置元素值赋给e
Status LocateElem(DuLinkList L, ElemType e);//在线性表L中查找是否存在与给定值e相等的元素
Status ListInsert(DuLinkList *L, int i, ElemType e);//在线性表L中的第i个位置之前插入新元素e
Status ListDelete(DuLinkList *L, int i, ElemType *e);//删除线性表L中的第i个位置,并将该元素值赋给e

int main(void)
{
    DuLinkList a = NULL;
    ElemType *p, e = 0;
    int i;
   
    InitList(&a);//建立一个空的线性表
   
    ListInsert(&a, 1, 1);
    for (i=1; i<MAXSIZE; i++)
    {
        ListInsert(&a, i, i+100);
    }
   
    DisplayList(a);
   
    printf("len = %d\n", ListLength(a));
    for (i=1; i<ListLength(a); i+=2)
    {
        ListDelete(&a, i, &e);//删除线性表L中的第i个位置,并将该元素值赋给e
    }
    printf("len = %d\n", ListLength(a));
    printf("e = %d\n", e);
   
    DisplayList(a);
   
    i = 5;
    e = 1050;
    if (LocateElem(a, e))//在线性表L中查找是否存在与给定值e相等的元素
    {
        printf("存在%d\n", e);
    }
    else
    {
        printf("不存在%d\n", e);
        ListInsert(&a, i, e);
    }
   
    DisplayList(a);
   
    ListDelete(&a, ListLength(a), &e);//删除线性表L中的最后一个元素
    DisplayList(a);
   
    ListDelete(&a, 1, &e);//删除线性表L中的第一个元素
    DisplayList(a);
   
    ClearList(&a);//将线性表清空(只留下头结点)
    DisplayList(a);
   
    return 0;
}

/*
函数功能:建立一个带头结点的空线性表L
初始条件:无
操作结果:初始化线性表L。操作成功返回OK,否则返回ERROR  
*/
Status InitList(DuLinkList *L)//建立一个带头结点的空线性表L  
{
    *L = (DuLinkList)malloc(sizeof(DuNode));

    if (!(*L))
    {
        printf("Out of space!");
        return ERROR;
    }
   
    (*L)->prior = (*L)->next = (*L);
   
    return OK;
}


/*
函数功能:判断线性表是否为空
初始条件:双向循环链表线性表L已经存在
操作结果:若线性表为空,返回TRUE,否则返回FALSE
*/
Status ListEmpty(DuLinkList L)
{
    return (L->next == L) ? TRUE : FALSE;
}

/*
函数功能:将线性表清空
初始条件:双向循环链表线性表L已经存在
操作结果:将线性表清空(只留下头结点)。操作成功返回OK,否则返回ERROR  
*/
Status ClearList(DuLinkList *L)
{
    DuLinkList p, q;
   
    if (*L == NULL)
    {
        return ERROR;
    }
   
    p = (*L)->next; //p指向第一个结点(非头结点)
    while (p != (*L))
    {
        q = p->next;
        (*L)->next = q;
        q->prior = *L;
        free(p);
        p = q;
    }
   
    return OK;
}

/*
函数功能:返回线性表L的元素个数
初始条件:双向循环链表线性表L已经存在
操作结果:返回线性表L的元素个数
*/
int ListLength(DuLinkList L)
{
    DuLinkList p = L->next;
    int i = 0;
   
    while (p != L)
    {
        i++;
        p = p->next;   
    }
   
    return i;
}

/*
函数功能:输出线性表L的所有元素
初始条件:双向循环链表线性表L已经存在
操作结果:输出线性表L的所有元素。操作成功返回OK,否则返回ERROR
*/
Status DisplayList(DuLinkList L)
{
    int i = 1;
    DuLinkList p = L->next;
   
    while (p == L)
    {
        printf("none!\n");   
        return ERROR;
    }
   
    while (p != L)
    {
        printf("data[%d] = %d, ", i++, p->data);
        p = p->next;   
    }
    printf("\n");
        
    return OK;
}

/*
函数功能:将线性表L中第i个位置元素值赋给e
初始条件:双向循环链表线性表L已经存在,1 <= i <= ListLength(L);
操作结果:将线性表L中第i个位置元素值赋给e。操作成功返回OK,否则返回ERROR
*/
Status GetElem(DuLinkList L, int i, ElemType *e)
{
    int j = 1;
    DuLinkList p = L->next; //p指向第一个结点(非头结点)
   
    while (p != L && j < i) //寻找第i个结点
    {
        j++;
        p = p->next;   
    }
   
    if (p == L || j > i) //第i个元素不存在
    {
        return ERROR;
    }
   
    *e = p->data;
   
    return OK;
}

/*
函数功能:在线性表L中查找是否存在与给定值e相等的元素
初始条件:双向循环链表线性表L已经存在
操作结果:在线性表L中查找是否存在与给定值e相等的元素。找到返回TRUE,否则返回FALSE
*/
Status LocateElem(DuLinkList L, ElemType e)
{
    DuLinkList p = L->next; //p指向第一个结点(非头结点)
   
    while (p != L)
    {
        if (p->data == e)
        {
            return TRUE;
        }
        p = p->next;   
    }
   
    return FALSE;
}

/*
函数功能:在线性表L中的第i个位置之前插入新元素e
初始条件:双向循环链表线性表L已经存在,1 <= i <= ListLength(L);
操作结果:在线性表L中的第i个位置之前插入新元素e。操作成功返回OK,否则返回ERROR  
*/
Status ListInsert(DuLinkList *L, int i, ElemType e)
{
    DuLinkList s, p = (*L)->next; //p指向第一个结点(非头结点)
    int j = 1;
   
    if (i == 1 && ListEmpty(*L))//空表,插入第一个元素
    {
        goto INSERT;
    }
   
    while (p != *L && j < i)//寻找第i个结点
    {
        j++;
        p = p->next;   
    }

    if (p == *L || j > i) //第i个结点不存在
    {
        return ERROR;
    }
   
INSERT:
    s = (DuLinkList)malloc(sizeof(DuNode));
    if (!s)
    {
        printf("Out of space!");
        return ERROR;
    }
   
    s->data = e;
    s->next = p;
    s->prior = p->prior;
    s->prior->next = s;
    p->prior = s;
   
    return OK;
}

/*
函数功能:删除线性表L中的第i个位置,并将该元素值赋给e
初始条件:双向循环链表线性表L已经存在,1 <= i <= ListLength(L);
操作结果:删除线性表L中的第i个位置,并将该元素值赋给e。
操作成功返回OK,否则返回ERROR  
*/
Status ListDelete(DuLinkList *L, int i, ElemType *e)
{
    DuLinkList q, p = (*L)->next; //p指向第一个结点(非头结点)
    int j = 1;
   
    while (p != *L && j < i)//寻找第i个结点
    {
        j++;
        p = p->next;   
    }
   
    if (p == *L || j > i) //第i个结点不存在
    {
        return ERROR;
    }
   
    q = p->next;
    q->prior = p->prior;
    q->prior->next = q;
    *e = p->data;
    free(p);
   
    return OK;
}
搜索更多相关主题的帖子: Copyright 读书笔记 include 线性表 
2014-09-13 19:42
最爱雨
Rank: 2
等 级:论坛游民
帖 子:6
专家分:15
注 册:2014-9-16
  得分:0 
2014-09-16 21:33
快速回复:《大话数据结构》读书笔记之线性表抽象数据类型(双向循环链表实现)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.110333 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved