002-线性表及其顺序结构存储实现

moc

1、线性表的基本概念
1.定义
    线性表（list）是由0个或多个元素组成的集合；
    线性表中的数据元素之间是有顺序的；
    线性表的数据元素个数是有限的；
    线性表中数据元素的类型必须相同。
数学描述：
    线性表是具有相同类型的n(n≥0)个数据元素的有限序列（a1, a2, a3, ... , an）,其中ai是表项，n是表的长度。

2.性质
    a0为线性表的第一个元素，只有一个后继；
    an为线性表的最后一个元素，只有一个前驱；
    除了a0和an以外的元素，既有前驱又有后继；
    线性表能够逐项访问和顺序存取。
3.线性表的操作
    创建线性表；
    销毁线性表；
    清空线性表；
    将元素插入到线性表；
    将元素从线性表中删除；
    获取线性表某个位置的元素；
    获取线性表的长度等。
2、线性表的顺序存储结构
顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
  这种存储结构需要提前根据存入元素的最大容量分配空间，一旦分配好，容量是固定的。
设计与实现：

1. #ifndef _MY_SEQLIST_H__
   
2. #define _MY_SEQLIST_H__
   
3. #include "stdio.h"
   
4. #include "stdlib.h"
   
5. #include "string.h"
   
6. 
   
7. typedef void SeqList;
   
8. typedef void SeqListNode;
   
9. 
   
10. // 根据容量创建并返回一个空的线性表
    
11. SeqList* SeqList_Create(int capacity);
    
12. 
    
13. // 销毁一个线性表
    
14. void SeqList_Destroy(SeqList* list);
    
15. 
    
16. // 清空一个线性表
    
17. void SeqList_Clear(SeqList* list);
    
18. 
    
19. // 获取线性表的长度
    
20. int SeqList_Length(SeqList* list);
    
21. 
    
22. // 获取线性表的容量
    
23. int SeqList_Capacity(SeqList* list);
    
24. 
    
25. // 在线性表的pos位置插入元素node
    
26. int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
    
27. 
    
28. // 获取线性表pos位置的元素
    
29. SeqListNode* SeqList_Get(SeqList* list, int pos);
    
30. 
    
31. // 删除线性表pos位置的元素
    
32. SeqListNode* SeqList_Delete(SeqList* list, int pos);
    
33. 
    
34. #endif

复制代码

1. 插入元素算法
        判断线性表是否合法；
        判断插入位置是否合法；
        容错修正  插入位置大于当前长度但小于链表容量，自动添加到尾部；
        把最后一个元素到插入位置的元素一次向后移一个位置；
        将新元素插入；
        线性表长度加1.

1. int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
   
2. {
   
3.         int i = 0, ret = 0;
   
4.         TseqList* tlist = NULL;
   
5.         tlist = (TseqList*)list;
   
6.         if (list == NULL || node == NULL || pos < 0)
   
7.         {
   
8.                 ret = -1;
   
9.                 printf("Fun SeqList_Insert() error: %d \n", ret);
   
10.                 return ret;
    
11.         }
    
12. 
    
13.         if (pos >= tlist->capacity)
    
14.         {
    
15.                 ret = -2;
    
16.                 printf("链表已满: %d \n", ret);
    
17.                 return ret;
    
18.         }
    
19. 
    
20.         // 容错修正  插入位置大于当前长度但小于链表容量，自动添加到尾部
    
21.         if (pos >= tlist->length)
    
22.         {
    
23.                 pos = tlist->length;
    
24.         }
    
25. 
    
26.         //1.元素后移
    
27.         for (i = tlist->length; i > pos; i--)
    
28.         {
    
29.                 tlist->node[i] = tlist->node[i - 1];
    
30.         }
    
31.         //2. 插入元素
    
32.         tlist->node[i] = node;
    
33.         tlist->length++;
    
34. 
    
35.         return 0;
    
36. }

复制代码

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

1. SeqListNode* SeqList_Get(SeqList* list, int pos)
   
2. {
   
3.         int i = 0, ret = 0;
   
4.         TseqList* tlist = NULL;
   
5.         tlist = (TseqList*)list;
   
6.         if (list == NULL || pos < 0 || pos > tlist->length)
   
7.         {
   
8.                 ret = -1;
   
9.                 printf("Fun SeqList_Get() error: %d \n", ret);
   
10.                 return ret;
    
11.         }
    
12.         return tlist->node[pos];
    
13. }

复制代码

3. 删除元素算法
        判断线性表是否合法；
        判断删除位置是否合法；
        将要删除的元素取出；
        把删除位置后的元素分别向前移一个位置；
        线性表长度减1.       
注意：线性表的容量和实际长度是两个不同的概念。

1. SeqListNode* SeqList_Delete(SeqList* list, int pos)
   
2. {
   
3.         int i = 0, ret = 0;
   
4.         SeqListNode* tmp;
   
5.         TseqList* tlist = NULL;
   
6.         tlist = (TseqList*)list;
   
7.         if (list == NULL || pos < 0)
   
8.         {
   
9.                 ret = -1;
   
10.                 printf("Fun SeqList_Insert() error: %d \n", ret);
    
11.                 return NULL;
    
12.         }
    
13.     // 缓存删除的结点
    
14.         tmp = (SeqListNode*)tlist->node[pos];
    
15.         // 结点前移
    
16.         for (i = pos + 1; i < tlist->length; i++)
    
17.         {
    
18.                 tlist->node[i - 1] = tlist->node[i];
    
19.         }
    
20.         tlist->length--;
    
21.         return tmp;
    
22. }

复制代码

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

完整代码： 线性表顺序存储.zip (1.97 KB, 下载次数: 12)

2018-9-23 11:41 上传

点击文件名下载附件
线性表顺序存储