【C语言--数据结构】线性顺序表

线性表的本质：
1.线性表(List)是零个或者多个数据元素的集合；
2.线性表中的数据元素之间是有顺序的；
3.线性表中的数据元素个数是有限的；
4.线性表中的数据元素的类型必须相同；
定义：
线性表是具有相同类型的n(>=0)个数据元素的有限序列
(a1,a2,a3.....) a1是表项，n是表长度
性质：
1.a0为线性表的第一个元素，只有一个后继
2.an为线性表的最后一个元素，只有一个前驱
3.除了a0,an外的其它元素ai,既有前驱，又有后继
4.线性表能够逐项访问和顺序存取

总结：
(1)线性表是数据元素的有序并且有限的集合
(2)线性表中的元素必须是类型相同的
(3)线性表可用于描述“队列类型”关系的问题

代码范例：

（1）头文件

 1 #ifndef __SEQLIST_H__
 2 #define __SEQLIST_H__
 3 
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 #include <malloc.h>
 7 
 8 typedef void SeqListNode;
 9 typedef void SeqList;
10 
11 /* 函数声明 */
12 SeqList *SeqList_Create(int iCapacity);
13 void SeqList_Destory(SeqList *pstList);
14 void SeqList_Clear(SeqList* pstList);
15 int SeqList_Length(SeqList* pstList);
16 int SeqList_Capacity(SeqList* pstList);
17 int SeqList_Insert(SeqList* pstList, SeqListNode *pstNode, int iPos);
18 SeqListNode* SeqList_Get(SeqList* pstList, int iPos);
19 SeqListNode* SeqList_Delete(SeqList* pstList, int iPos);
20 
21 
22 #endif

（2）函数实现

  1 /*
  2 ** 顺序存储结构的线性表
  3 */
  4 #include "SeqList.h"
  5 
  6 typedef unsigned int TSeqListNode;
  7 
  8 typedef struct _tag_SeqList
  9 {
 10     int iCapacity;
 11     int iLength;
 12     TSeqListNode *node;
 13 }TSeqList;
 14 
 15 /* 线性表相关函数的实现 */
 16 
 17 /**************************************************************************
 18 ** 函 数 名: SeqList_Create
 19 ** 函数作用: 创建一个线性顺序表
 20 ** 返 回 值: SeqList *
 21 ** 日    期: 2017年2月13日
 22 ** 作    者: Rookie
 23 ***************************************************************************/
 24 SeqList *SeqList_Create(int iCapacity)
 25 {
 26     TSeqList* pstRet = NULL;
 27 
 28     if (0 <= iCapacity)
 29     {
 30         pstRet = (TSeqList *)malloc(sizeof(TSeqList) + sizeof(TSeqListNode)*iCapacity);
 31     }
 32 
 33     if (pstRet != NULL)
 34     {
 35         pstRet->iCapacity = iCapacity;
 36         pstRet->iLength = 0;
 37         pstRet->node = (TSeqListNode *)(pstRet + 1);
 38     }
 39 
 40     return pstRet;
 41 }
 42 
 43 /**************************************************************************
 44 ** 函 数 名: SeqList_Destory
 45 ** 函数作用: 销毁一个线性顺序表
 46 ** 返 回 值: void
 47 ** 日    期: 2017年2月13日
 48 ** 作    者: Rookie
 49 ***************************************************************************/
 50 void SeqList_Destory(SeqList *pstList)
 51 {
 52     free(pstList);
 53 
 54     return;
 55 }
 56 
 57 /**************************************************************************
 58 ** 函 数 名: SeqList_Clear
 59 ** 函数作用: 一个线性顺序表清空
 60 ** 返 回 值: void
 61 ** 日    期: 2017年2月13日
 62 ** 作    者: Rookie
 63 ***************************************************************************/
 64 void SeqList_Clear(SeqList* pstList)
 65 {
 66    TSeqList* pstListTemp = (TSeqList *)pstList;
 67 
 68     if (pstListTemp != NULL)
 69     {
 70         pstListTemp->iLength = 0;
 71     }
 72     
 73     return;
 74 }
 75 
 76 /**************************************************************************
 77 ** 函 数 名: SeqList_Length
 78 ** 函数作用: 获取顺序表的长度
 79 ** 返 回 值: int 
 80 ** 日    期: 2017年2月14日
 81 ** 作    者: Rookie
 82 ***************************************************************************/
 83 int SeqList_Length(SeqList* pstList)
 84 {
 85     int iRet = -1;
 86     TSeqList* pstListTemp = (TSeqList *)pstList;
 87 
 88     if (pstListTemp != NULL)
 89     {
 90         iRet = pstListTemp->iLength;
 91     }
 92 
 93     return iRet;
 94 }
 95 
 96 /**************************************************************************
 97 ** 函 数 名: SeqList_Capacity
 98 ** 函数作用: 获取顺序表的容量
 99 ** 返 回 值: int 
100 ** 日    期: 2017年2月14日
101 ** 作    者: Rookie
102 ***************************************************************************/
103 int SeqList_Capacity(SeqList* pstList)
104 {
105     int iRet = -1;
106     TSeqList* pstListTemp = (TSeqList *)pstList;
107 
108     if (pstListTemp != NULL)
109     {
110         iRet = pstListTemp->iCapacity;
111     }
112 
113     return iRet;
114 }
115 
116 /**************************************************************************
117 ** 函 数 名: SeqList_Insert
118 ** 函数作用: 向线性表中插入一个节点
119 ** 返 回 值: int 
120 ** 日    期: 2017年2月14日
121 ** 作    者: Rookie
122 ***************************************************************************/
123 int SeqList_Insert(SeqList* pstList, SeqListNode *pstNode, int iPos)
124 {
125     TSeqList* pstListTemp = (TSeqList *)pstList;
126     int iRet = (pstListTemp != NULL);
127     int iLoop;
128 
129     iRet = iRet && ((pstListTemp->iLength + 1) <= pstListTemp->iCapacity);
130     iRet = iRet && (0 <= iPos);
131 
132     if (iRet)
133     {
134         if (iPos > pstListTemp->iLength)
135         {
136             iPos = pstListTemp->iLength;
137         }
138 
139         for (iLoop = pstListTemp->iLength; iLoop > iPos; iLoop--)
140         {
141             pstListTemp->node[iLoop] = pstListTemp->node[iLoop-1];
142         }
143 
144         pstListTemp->node[iLoop] = (TSeqListNode)pstNode;
145         pstListTemp->iLength++;
146     }
147 
148     return iRet;
149 }
150 
151 /**************************************************************************
152 ** 函 数 名: SeqList_Get
153 ** 函数作用: 获取顺序表的指定位置的值
154 ** 返 回 值: int 
155 ** 日    期: 2017年2月14日
156 ** 作    者: Rookie
157 ***************************************************************************/
158 SeqListNode* SeqList_Get(SeqList* pstList, int iPos)
159 {
160     TSeqList* pstListTemp = (TSeqList *)pstList;
161     SeqListNode* pstRet = NULL;
162 
163     if ((NULL != pstListTemp) && (0 <= iPos) && (iPos <= pstListTemp->iLength))
164     {
165         pstRet = (SeqListNode*)pstListTemp->node[iPos];
166     }
167 
168     return pstRet;
169 }
170 
171 /**************************************************************************
172 ** 函 数 名: SeqList_Delete(SeqList* pstList, int iPos)
173 ** 函数作用: 删除顺序表的指定位置的值
174 ** 返 回 值: 
175 ** 日    期: 2017年2月14日
176 ** 作    者: Rookie
177 ***************************************************************************/
178 SeqListNode* SeqList_Delete(SeqList* pstList, int iPos)
179 {
180     TSeqList* pstListTemp = (TSeqList *)pstList;
181     SeqListNode* pstRet = SeqList_Get(pstList, iPos);
182     int iLoop;
183 
184     if (NULL != pstRet)
185     {
186         for (iLoop = iPos+1; iLoop < pstListTemp->iLength; iLoop++)
187         {
188             pstListTemp->node[iLoop-1] = pstListTemp->node[iLoop];
189         }
190         pstListTemp->node[iLoop] = (TSeqListNode)NULL;
191         pstListTemp->iLength--;
192     }
193 
194     return pstRet;
195 }