Chinaunix首页 | 论坛 | 博客

特殊借口

首页　| 　博文目录　| 　关于我

特殊借口

  • 博客访问： 251072
  • 博文数量： 52
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1538
  • 用 户 组： 普通用户
  • 注册时间： 2013-04-24 07:45
个人简介

生活就像海洋，只有意志坚强的人，才能到达彼岸。

文章分类

全部博文（52）

文章存档

2013年（52）

我的朋友
最近访客
推荐博文
相关博文
线性表的实现(国嵌学习笔记)

分类： C/C++

2013-08-13 22:24:56

1、定义：线性表是具有相同类型的n（>=0）个数据元素的有限序列。

2、性质：

线性表的第一个元素只有一个后继，最后一个元素只有一个前驱，其他的元素既有前驱又有后继，线性表能够逐项访问和顺序存取。

3、线性表的操作：

创建线性表、销毁线性表、清空线性表、将元素插入线性表、将元素从线性表中删除、获取线性表中某个位置的元素、获取线性表的长度。

4、实现线性表：

线性表在程序中表型为一种特殊的数据类型；线性表的操作在程序中的表现为一组函数。

List* List_Create();

void List_Destroy(List* list);

void List_Clear(List* list);

int List_Insert(List* list, ListNode* node, int pos);

ListNode* List_Delete(List* list, int pos);

ListNode* List_Get(List* list, int pos);

int List_Length(List* list);

顺序存储定义：

线性变的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

在C语言中可以用一维数组来实现顺序存储结构：
存储空间的起始位置：数组node
线性表的最大容量：数组长度MAXSIZE
线性表的当前长度：length

#define MAXSIZE 20

typedef struct _tag_List
{
    char node[MAXSIZE];
    int length;
}List;

获取元素的操作：
    判断线性表是否合法；
    判断位置是否合法；
    直接通过数组小标的方式获取元素；

char Get(List* list, int pos)
{
    char ret = -1;
    /*判断线性表的合法性，判断位置的合法性*/
    if( (list != NULL) && (0 <= pos) && (pos < list->length) )
    {
        ret = list->nose[pos];
    }

    return ret;
}

插入元素操作：

    判断线性表是否合法；
    判断插入位置是否合法；
    把最后一个元素到插入位置的元素后移一个位置
    将新元素插入；
    线性表长度加1；

插入元素算法：

int Insert(List* list, char c, int pos)
{
    /*判断线性表合法性*/
    int ret = (list != NULL);
    int i = 0;
    
    /*判断插入位置合法性*/
    ret = ret && (list->length + 1 <= MAXSIZE);
    ret = ret && (0 <= pos);

    if(ret)
    {
        if( pos >= list->length )
        {
            pos = list->length;
        }

        /*从最后一个元素开始到第pos个位置分别将它们向后移一个位置*/
        for( i = list->length; i>pos; i--)
        {
            list->node[i] = list->node[i-1];
        }

        list->node[i] = c;//将新元素插入

        list->length++;   //将线性表长度加1
    }
    
    return ret;
}

删除元素算法
    判断线性表是否合法；
    判断删除的位置是否合法；
    将元素取出；
    将删除位置后的元素分别向前移动一个位置
    线性表长度减1；

char Delete(List* list, int pos)
{
    char ret = -1;
    int i = 0;

    /*判断线性表是否合法，判断删除位置是否合法*/
    if( (list != NULL) && (0 <=pos) && (pos < list->length) )
    {
        /*取出删除元素*/
        ret = list->node[pos];

        /*将删除位置pos以后的元素分别向前移动一个位置*/
        for( i = pos + 1; i < list->length; i++)
        {
            list->node[i-1] = list->node[i];
        }
        
        list->length--;   //线性表长度减1；
    }
    
    return ret;
}


点击(此处)折叠或打开

  1. /*SeqList.h*/
  2. ********************************************************
  3. #ifndef _SEQLIST_H_
  4. #define _SEQLIST_H_

  6. typedef void SeqList;
  7. typedef void SeqListNode;

  9. SeqList* SeqList_Create(int capacity);

  11. void SeqList_Destroy(SeqList* list);

  13. void SeqList_Clear(SeqList* list);

  15. int SeqList_Length(SeqList* list);

  17. int SeqList_Capacity(SeqList* list);

  19. int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

  21. SeqListNode* SeqList_Delete(SeqList* list, int pos);

  23. SeqListNode* SeqList_Get(SeqList* list, int pos);

  25. #endif
  26. *******************************************************



点击(此处)折叠或打开

  1. /*SeqList.c*/
  2. *******************************************************
  3. #include <stdio.h>
  4. #include <malloc.h>
  5. #include "SeqList.h"

  7. typedef unsigned int TSeqListNode;/*插入结点的指针，以达到可复用的目的*/

  9. typedef struct _tag_SeqList
  10. {
  11.     int capacity;
  12.     int length;
  13.     TSeqListNode* node;
  14. }TSeqList;

  16. SeqList* SeqList_Create(int capacity)//O(1)
  17. {
  18.     TSeqList* ret = NULL;
  19.     if( capacity >= 0 )
  20.     {
  21.         ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
  22.     }
  23.     if( ret != NULL )
  24.     {
  25.         ret->capacity = capacity;
  26.         ret->length = 0;
  27.         ret->node = (TSeqListNode*)(ret + 1);
  28.     }
  29.     return ret;
  30. }

  32. void SeqList_Destroy(SeqList* list)//O(1)
  33. {
  34.     free(list);
  35. }

  37. void SeqList_Clear(SeqList* list)//O(1)
  38. {
  39.     TSeqList* sList = (TSeqList*)list;
  40.     if( sList != NULL )
  41.     {
  42.         sList->length = 0;
  43.     }
  44. }

  46. int SeqList_Length(SeqList* list)//O(1)
  47. {
  48.     TSeqList* sList = (TSeqList*)list;
  49.     int ret = -1;
  50.     if( sList != NULL )
  51.     {
  52.         ret = sList->length;
  53.     }
  54.     return ret;
  55. }

  57. int SeqList_Capacity(SeqList* list)//O(1)
  58. {
  59.     TSeqList* sList = (TSeqList*)list;
  60.     int ret = -1;
  61.     if( sList != NULL )
  62.     {
  63.         ret = sList->capacity;
  64.     }
  65.     return ret;
  66. }

  68. int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)//O(N)
  69. {
  70.     TSeqList* sList = (TSeqList*)list;
  71.     int ret = (sList != NULL);
  72.     int i = 0;
  73.     ret = ret && (sList->length + 1 <= sList->capacity);
  74.     ret = ret && (0 <= pos);
  75.     if( ret )
  76.     {
  77.         if( pos >= sList->length)
  78.         {
  79.             pos = sList->length ;
  80.         }
  81.         for( i=sList->length; i>pos; i-- )
  82.         {
  83.             sList->node[i] = sList->node[i-1];
  84.         }
  85.         sList->node[i] = (TSeqListNode)node;
  86.         sList->length++;
  87.     }
  88.     return ret;
  89. }

  91. SeqListNode* SeqList_Delete(SeqList* list, int pos)//O(n)
  92. {
  93.     TSeqList* sList = (TSeqList*)list;
  94.     SeqListNode* ret = SeqList_Get(list,pos);
  95.     int i = 0;
  96.     if( ret != NULL)
  97.     {
  98.         for(i=pos+1; i<sList->length; i++)
  99.         {
  100.             sList->node[i-1] = sList->node[i];
  101.         }
  102.     sList->length--;
  103.     }
  104.     return ret;
  105. }

  107. SeqListNode* SeqList_Get(SeqList* list, int pos)//O(1)
  108. {
  109.     TSeqList* sList = (TSeqList*)list;
  110.     SeqListNode* ret = NULL;
  111.     if( (sList != NULL) && (0 <= pos) && (pos <= sList->length) )
  112.     {
  113.         ret = (SeqListNode*)(sList->node[pos]);
  114.     }
  115.     return ret;
  116. }
  117. *************************************************************************



点击(此处)折叠或打开

  1. /*main.c*/
  2. *************************************************************************
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "SeqList.h"
  6. /* run this program using the console pauser or add your own getch, system("pause") or input loop */

  8. int main(int argc, char *argv[])
  9. {
  10.     SeqList* list = SeqList_Create(5);
  11.     int i = 0;
  12.         int j = 1;
  13.     int k = 2;
  14.     int x = 3;
  15.     int y = 4;
  16.     int z = 5;
  17.     int index = 0;

  18.
  19.     SeqList_Insert(list, &i, 0);
  20.     SeqList_Insert(list, &j, 0);
  21.     SeqList_Insert(list, &k, 0);
  22.     SeqList_Insert(list, &x, 0);
  23.     SeqList_Insert(list, &y, 0);
  24.     SeqList_Insert(list, &z, 0);
  25.     for(index=0; index<SeqList_Length(list);index++)
  26.     {
  27.         int* p = (int*)SeqList_Get(list,index);
  28.         printf("%d\n",*p);
  29.     }
  30.     printf("\n");
  31.     while( SeqList_Length(list) > 0)
  32.     {
  33.         int* p = (int*)SeqList_Delete(list,0);
  34.         printf("%d\n",*p);
  35.     }
  36.     SeqList_Destroy(list);
  37.     return 0;
  38. }



该存储方式的优点在于无需为线性表中的逻辑关系增加额外的空间，可以快速的获取表中合法位置的元素；缺点在于插入和删除操作需要移动大量的元素，当线性表长度变化比较大时难以确定存储空间的容量。

链式存储结构：

定义：为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示直接后继的信息。
链式存储逻辑结构：
    n个结点链接成一个链式线性表的结构叫做链表，当每个结点中止包含一个指针域时，叫做单链表。
链表的基本概念：
表头结点：链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息。
数据结点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息。
尾结点：链表中的最后一个数据结点，其下一元素指针为空，表示无后继。

在C语言中可以用结构体来定义链表中的指针域，链表中的头结点也可以用结构体实现

结点指针域定义：
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
    LinkListNode* next;
};

头结点定义：
typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
}TLinkList;

数据元素定义示例：
struct Value
{
    LinkListNode header;
    int v;
};

获取第pos个元素操作
    判断线性表是否合法；
    判断位置是否合法；
    由表头开始通过next指针移动pos后，当前元素的next指针即指向要获取的元素；

LinkListNode* current = (LinkListNode*)list;

for(i=0; i
{
    current = current->next;
}

ret = current->next;


插入元素到位置pos的算法
    判断线性表是否合法；
    判断插入位置是否合法；
    由表头开始通过next指针移动pos后，当前元素的next指针即指向要插入的位置；
    将新元素插入；
    线性表长度加1；

LinkListNode* current = (LinkListNode*)list;

for(i=0; (i < pos) && (current->next != NULL); i++)
{
    current = current->next;
}

node->next = current->next;
current->next = node;

sList->length++;


删除第pos个元素的算法
    判断线性表的合法性；
    判断插入位置是否合法；
    获取第pos个元素；
    将第pos个元素从链表中删除
    线性表长度减1；

TLinkList* sList = (TLinkList*)list
LinkListNode* ret = NULL;
int i = 0;

if( (sList != NULL) && (0<=pos) && (pos < sList->length) )
{
    LinkListNode* current = (LinkListNode*)list;

    for(i=0;i
    {
        current = current->next;
    }

    ret = current->next;
    current->next = ret->next;

    sList->length--;
}


点击(此处)折叠或打开

  1. /*LinkList.h*/
  2. *******************************************************************
  3. #ifndef _LINKLIST_H_
  4. #define _LINKLIST_H_

  6. typedef void LinkList;
  7. typedef struct _tag_LinkListNode LinkListNode;
  8. struct _tag_LinkListNode
  9. {
  10.     LinkListNode* next;
  11. };

  13. LinkList* LinkList_Create();

  15. void LinkList_Destroy(LinkList* list);

  17. void LinkList_Clear(LinkList* list);

  19. int LinkList_Length(LinkList* list);

  21. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

  23. LinkListNode* LinkList_Get(LinkList* list, int pos);

  25. LinkListNode* LinkList_Delete(LinkList* list, int pos);

  27. #endif


**********************************************************************


点击(此处)折叠或打开

  1. /*LinkList.c*/
  2. ***********************************************************************
  3. #include <stdio.h>
  4. #include <malloc.h>
  5. #include "LinkList.h"

  7. typedef struct _tag_LinkList
  8. {
  9.     LinkListNode header;
  10.     int length;
  11. } TLinkList;

  13. LinkList* LinkList_Create()
  14. {
  15.     TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
  16.     if( ret != NULL )
  17.     {
  18.         ret->length = 0;
  19.         ret->header.next = NULL;
  20.     }
  21.     return ret;
  22. }


  25. void LinkList_Destroy(LinkList* list)
  26. {
  27.     free(list);
  28. }

  30. void LinkList_Clear(LinkList* list)
  31. {
  32.     TLinkList* sList = (TLinkList*)list;
  33.     if(sList != NULL)
  34.     {
  35.         sList->length = 0;
  36.         sList->header.next = NULL;
  37.     }
  38. }

  40. int LinkList_Length(LinkList* list)
  41. {
  42.     TLinkList* sList = (TLinkList*)list;
  43.     int ret = -1;
  44.     if(sList != NULL)
  45.     {
  46.         ret = sList->length;
  47.     }
  48.     return ret;
  49. }

  51. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
  52. {
  53.     TLinkList* sList = (TLinkList*)list;
  54.     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
  55.     int i = 0;
  56.     if( ret )
  57.     {
  58.         LinkListNode* current = (LinkListNode*)sList;
  59.         for(i=0; (i<pos)&&(current->next != NULL); i++)
  60.         {
  61.             current = current->next;
  62.         }
  63.         node->next = current->next;
  64.         current->next = node;
  65.         sList->length++;
  66.     }
  67.     return ret;
  68. }

  70. LinkListNode* LinkList_Get(LinkList* list, int pos)
  71. {
  72.     TLinkList* sList = (TLinkList*)list;
  73.     LinkListNode* ret = NULL;
  74.     int i = 0;
  75.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length))
  76.     {
  77.         LinkListNode* current = (LinkListNode*)sList;
  78.         for(i=0; i<pos; i++)
  79.         {
  80.             current = current->next;
  81.         }
  82.     ret = current->next;
  83.     }
  84.     return ret;
  85. }

  87. LinkListNode* LinkList_Delete(LinkList* list, int pos)
  88. {
  89.     TLinkList* sList = (TLinkList*)list;
  90.     LinkListNode* ret = NULL;
  91.     int i = 0;
  92.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length))
  93.     {
  94.         LinkListNode* current = (LinkListNode*)sList;
  95.         for(i=0; i<pos; i++)
  96.         {
  97.             current = current->next;
  98.         }
  99.         ret = current->next;
  100.         current->next = ret->next;
  101.         sList->length--;
  102.     }
  103.     return ret;
  104. }
  105. *************************************************************************



点击(此处)折叠或打开

  1. /*main.c*/
  2. *************************************************************************
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "LinkList.h"
  6. /* run this program using the console pauser or add your own getch, system("pause") or input loop */

  8. struct Value
  9. {
  10.     LinkListNode header;
  11.     int v;
  12. };

  14. int main(int argc, char *argv[])
  15. {
  16.     int i = 0;
  17.     LinkList* list = LinkList_Create();
  18.     
  19.     struct Value v1;
  20.     struct Value v2;
  21.     struct Value v3;
  22.     struct Value v4;
  23.     struct Value v5;
  24.     
  25.     v1.v = 1;
  26.     v2.v = 2;
  27.     v3.v = 3;
  28.     v4.v = 4;
  29.     v5.v = 5;
  30.     
  31.     LinkList_Insert(list, (LinkListNode*)&v1, LinkList_Length(list));
  32.     LinkList_Insert(list, (LinkListNode*)&v2, LinkList_Length(list));
  33.     LinkList_Insert(list, (LinkListNode*)&v3, LinkList_Length(list));
  34.     LinkList_Insert(list, (LinkListNode*)&v4, LinkList_Length(list));
  35.     LinkList_Insert(list, (LinkListNode*)&v5, LinkList_Length(list));
  36.     
  37.     for(i=0; i<LinkList_Length(list); i++)
  38.     {
  39.         struct Value* pv = (struct Value*)LinkList_Get(list, i);
  40.         
  41.         printf("%d\n", pv->v);
  42.     }
  43.     
  44.     while( LinkList_Length(list) > 0 )
  45.     {
  46.         struct Value* pv = (struct Value*)LinkList_Delete(list, 0);
  47.         
  48.         printf("%d\n", pv->v);
  49.     }
  50.     
  51.     LinkList_Destroy(list);
  52.     
  53.     return 0;
  54. }



线性表的链式结构的优点是无需一次性定制链表的容量，插入和删除操作无需移动数据元素；
不足是数据元素必须保存后继元素的位置信息，获取指定数据的元素操作需要顺序访问之前的元素。
阅读(3128) | 评论(0) | 转发(0) |
0

上一篇：函数（C语言的核心）（国嵌学习笔记）

下一篇：静态链表实现（国嵌学习笔记）

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6