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

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

文章存档

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_

  5. typedef void SeqList;
  6. typedef void SeqListNode;

  7. SeqList* SeqList_Create(int capacity);

  8. void SeqList_Destroy(SeqList* list);

  9. void SeqList_Clear(SeqList* list);

  10. int SeqList_Length(SeqList* list);

  11. int SeqList_Capacity(SeqList* list);

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

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

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

  15. #endif
  16. *******************************************************



点击(此处)折叠或打开

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

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

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

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

  28. void SeqList_Destroy(SeqList* list)//O(1)
  29. {
  30.     free(list);
  31. }

  32. void SeqList_Clear(SeqList* list)//O(1)
  33. {
  34.     TSeqList* sList = (TSeqList*)list;
  35.     if( sList != NULL )
  36.     {
  37.         sList->length = 0;
  38.     }
  39. }

  40. int SeqList_Length(SeqList* list)//O(1)
  41. {
  42.     TSeqList* sList = (TSeqList*)list;
  43.     int ret = -1;
  44.     if( sList != NULL )
  45.     {
  46.         ret = sList->length;
  47.     }
  48.     return ret;
  49. }

  50. int SeqList_Capacity(SeqList* list)//O(1)
  51. {
  52.     TSeqList* sList = (TSeqList*)list;
  53.     int ret = -1;
  54.     if( sList != NULL )
  55.     {
  56.         ret = sList->capacity;
  57.     }
  58.     return ret;
  59. }

  60. int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)//O(N)
  61. {
  62.     TSeqList* sList = (TSeqList*)list;
  63.     int ret = (sList != NULL);
  64.     int i = 0;
  65.     ret = ret && (sList->length + 1 <= sList->capacity);
  66.     ret = ret && (0 <= pos);
  67.     if( ret )
  68.     {
  69.         if( pos >= sList->length)
  70.         {
  71.             pos = sList->length ;
  72.         }
  73.         for( i=sList->length; i>pos; i-- )
  74.         {
  75.             sList->node[i] = sList->node[i-1];
  76.         }
  77.         sList->node[i] = (TSeqListNode)node;
  78.         sList->length++;
  79.     }
  80.     return ret;
  81. }

  82. SeqListNode* SeqList_Delete(SeqList* list, int pos)//O(n)
  83. {
  84.     TSeqList* sList = (TSeqList*)list;
  85.     SeqListNode* ret = SeqList_Get(list,pos);
  86.     int i = 0;
  87.     if( ret != NULL)
  88.     {
  89.         for(i=pos+1; i<sList->length; i++)
  90.         {
  91.             sList->node[i-1] = sList->node[i];
  92.         }
  93.     sList->length--;
  94.     }
  95.     return ret;
  96. }

  97. SeqListNode* SeqList_Get(SeqList* list, int pos)//O(1)
  98. {
  99.     TSeqList* sList = (TSeqList*)list;
  100.     SeqListNode* ret = NULL;
  101.     if( (sList != NULL) && (0 <= pos) && (pos <= sList->length) )
  102.     {
  103.         ret = (SeqListNode*)(sList->node[pos]);
  104.     }
  105.     return ret;
  106. }
  107. *************************************************************************



点击(此处)折叠或打开

  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 */

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

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



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

链式存储结构:

定义:为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示直接后继的信息。
链式存储逻辑结构:
    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_

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

  11. LinkList* LinkList_Create();

  12. void LinkList_Destroy(LinkList* list);

  13. void LinkList_Clear(LinkList* list);

  14. int LinkList_Length(LinkList* list);

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

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

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

  18. #endif


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


点击(此处)折叠或打开

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

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

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


  21. void LinkList_Destroy(LinkList* list)
  22. {
  23.     free(list);
  24. }

  25. void LinkList_Clear(LinkList* list)
  26. {
  27.     TLinkList* sList = (TLinkList*)list;
  28.     if(sList != NULL)
  29.     {
  30.         sList->length = 0;
  31.         sList->header.next = NULL;
  32.     }
  33. }

  34. int LinkList_Length(LinkList* list)
  35. {
  36.     TLinkList* sList = (TLinkList*)list;
  37.     int ret = -1;
  38.     if(sList != NULL)
  39.     {
  40.         ret = sList->length;
  41.     }
  42.     return ret;
  43. }

  44. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
  45. {
  46.     TLinkList* sList = (TLinkList*)list;
  47.     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
  48.     int i = 0;
  49.     if( ret )
  50.     {
  51.         LinkListNode* current = (LinkListNode*)sList;
  52.         for(i=0; (i<pos)&&(current->next != NULL); i++)
  53.         {
  54.             current = current->next;
  55.         }
  56.         node->next = current->next;
  57.         current->next = node;
  58.         sList->length++;
  59.     }
  60.     return ret;
  61. }

  62. LinkListNode* LinkList_Get(LinkList* list, int pos)
  63. {
  64.     TLinkList* sList = (TLinkList*)list;
  65.     LinkListNode* ret = NULL;
  66.     int i = 0;
  67.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length))
  68.     {
  69.         LinkListNode* current = (LinkListNode*)sList;
  70.         for(i=0; i<pos; i++)
  71.         {
  72.             current = current->next;
  73.         }
  74.     ret = current->next;
  75.     }
  76.     return ret;
  77. }

  78. LinkListNode* LinkList_Delete(LinkList* list, int pos)
  79. {
  80.     TLinkList* sList = (TLinkList*)list;
  81.     LinkListNode* ret = NULL;
  82.     int i = 0;
  83.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length))
  84.     {
  85.         LinkListNode* current = (LinkListNode*)sList;
  86.         for(i=0; i<pos; i++)
  87.         {
  88.             current = current->next;
  89.         }
  90.         ret = current->next;
  91.         current->next = ret->next;
  92.         sList->length--;
  93.     }
  94.     return ret;
  95. }
  96. *************************************************************************



点击(此处)折叠或打开

  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 */

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

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



线性表的链式结构的优点是无需一次性定制链表的容量,插入和删除操作无需移动数据元素;
不足是数据元素必须保存后继元素的位置信息,获取指定数据的元素操作需要顺序访问之前的元素。
阅读(3196) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~