Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1016480
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-10-31 13:41:58

链表

  链表 是 一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组 成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
  线性表的 链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系,对数据元素 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。由这两部分信息组成一个"结点"(如下图所示),表示线性 表中一个数据元素 。
  数据域 data 指针域 next
  其中存储数据元素信息的域称作数据域(设域名为data),存储直接后继存储位置的域称为指针域(设域名为next)。指针域中存储的信息又称做指针或链。
  由分别表示,,…, 的N 个结点依次相链构成的链表,称为线性表的链式存储表示,由于此类链表的每个结点中只包含一个指针域,故又称单链表或线性链表.
  =====================================================
#include
#include

struct iNode{
    int data;
    iNode *next;
};

struct iNode *create()
{
    struct iNode *hp = NULL;
    struct iNode *tp = NULL;

    struct iNode *cp = NULL;

    int data;
    while (1)
    {
        scanf("%d",&data);
        if (data <= 0) break;
        cp = (struct iNode*)malloc(sizeof(struct iNode));
        if (cp == NULL)
        {
            printf("OVER FLOW");
            break;
        }
        cp->data = data;
        cp->next = NULL;
        if (hp == NULL)
        {
            hp = tp = cp;
        }else{
            tp->next = cp;
            tp = cp;
        }
    }
    printf("Create Success!\n");
    return hp;
}

void head_insert(struct iNode *head, int position, int val)
{
    struct iNode *p = head;
    struct iNode *node = NULL;
    int i = 0;
    while (p && ++i < position -1)
    {
        p = p -> next;
        //++i;

    }
    node = (struct iNode *)malloc(sizeof(struct iNode));
    node->data = val;
    node->next = p->next;
    p->next = node;
}

void tail_insert(struct iNode *head, int position, int val)
{
    struct iNode *p = head;
    struct iNode *node = NULL;
    int i = 0;
    while (p && ++i < position)
    {
        p = p->next;
    }
    node = (struct iNode *)malloc(sizeof(struct iNode));
    node->data = val;
    node->next = p->next;
    p->next = node;
}

void del_node(struct iNode *head, int position, int &val)
{
    struct iNode *p = head;
    struct iNode *d = NULL;
    int i = 0;
    while(p && ++i < position -1){
        p = p->next;
    }
    d = p->next;
    p->next = d->next;
    val = d->data;
    free(d);
}

void printl(struct iNode *head)
{
    struct iNode *p = head;
    if (p != NULL)
    {
        do{
            printf("%d ",p->data);
            p = p->next;
        }while(p != NULL);
    }else{
        printf("List ERROR\n");
    }
    printf("\n");
}

int main()
{
    struct iNode *list = create();
    int val = 0;
    printf("List:\n");
    printl(list);
    printf("\n\nInserted 1:\n");
    head_insert(list,5,34);
    printl(list);
    printf("\n\nDeleted:\n");
    del_node(list,5,val);
    printl(list);
    printf("Element: %d\n",val);
    printf("\n\nInserted 2:\n");
    tail_insert(list,5,32);
    printl(list);
    return 0;
}
阅读(2555) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~