顺序链表的C风格实现

 1 //头文件  
 2 #ifndef _SEQLIST_H_  
 3 #define _SEQLIST_H_  
 4 //定义数据类型  
 5 typedef void SeqList;  
 6 typedef void SeqListNode;  
 7   
 8 //顺序链表的生成  
 9 SeqList* SeqList_Create(int capacity);  
10 //顺序链表的删除  
11 void SeqList_Destory(SeqList* list);  
12 //顺序链表的清空  
13 void SeqList_Clear(SeqList* list);  
14 //返回链表长度  
15 int SeqList_Length(SeqList* list);  
16 //返回链表容量  
17 int SeqList_Capacity(SeqList* list);  
18 //在POS位置插入节点  
19 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);  
20 //获取POS位置的节点信息  
21 SeqListNode* SeqList_Get(SeqList* list, int pos);  
22 //删除POS位置的节点信息  
23 SeqListNode* SeqList_Delete(SeqList* list, int pos);  
24   
25 #endif

  1 //Cpp
  2  
  3 #include "seqList.h"
  4 #include <iostream>
  5 using namespace std;
  6 //定义一个链表头
  7 typedef struct _tag_SeqList
  8 {
  9     int length;
 10     int capacity;
 11     unsigned int **node; //       使用**防止数据丢失
 12 }TSeqList;
 13  
 14  
 15  
 16 //创建一个线性表
 17 SeqList* SeqList_Create(int capacity)
 18 {
 19     int ret = 0;
 20     TSeqList *temp = NULL;   //创建临时指针变量remp
 21  
 22     temp = (TSeqList *)malloc((sizeof(TSeqList)));  //分配内存
 23     //异常处理
 24     if (temp == NULL)
 25     {
 26         ret = -1;
 27         cout << "SeqList_Create Err!" << endl;
 28         return NULL;
 29     }
 30     memset(temp, 0, sizeof(TSeqList));  // 快速填充为0
 31  
 32     //为所有节点分配内存空间 （*容量）
 33     temp->node = (unsigned int **)malloc(sizeof(unsigned int *) * capacity);
 34  
 35  
 36     if (temp->node == NULL)
 37     {
 38         ret = -2;
 39         cout << "SeqList_Create Err!  (malloc..)" << endl;
 40         return NULL;
 41     }
 42  
 43  
 44     temp->capacity = capacity;
 45     temp->length = 0;
 46     return temp;
 47 }
 48  
 49  
 50  
 51 //删除(释放)一个线性表
 52 void SeqList_Destory(SeqList* list)
 53 {
 54     TSeqList *tlist = NULL; 
 55     //判断是否为空
 56     if(list == NULL)
 57     {
 58         cout << "Destory Err" << endl;
 59         return ;
 60     }
 61     tlist = (TSeqList *)list;
 62     //先释放node内存 再释放List内存
 63     if (tlist->node != NULL)
 64     {
 65         free(tlist->node);
 66     }
 67     free(tlist);
 68  
 69     return;
 70 }
 71  
 72  
 73 //清空一个线性表
 74 void SeqList_Clear(SeqList* list)
 75 {
 76     TSeqList *tlist = NULL; 
 77     if(list == NULL)
 78     {
 79         cout << "Clear Err " << endl;
 80         return ;
 81     }
 82     //直接将链表的长度重置为0
 83     tlist = (TSeqList *)list;
 84     tlist->length = 0;
 85     return;
 86 }
 87  
 88  
 89 //返回一个线性表的长度
 90 int SeqList_Length(SeqList*    list)
 91 {
 92     TSeqList *tlist = NULL; 
 93     //异常处理
 94     if(list == NULL)
 95     {
 96         cout << "Length Err, list == NULL" << endl;
 97         return -1;
 98     }
 99  
100     tlist = (TSeqList *)list;
101     return tlist->length;
102 }
103  
104  
105 //返回线性表的容量
106 int SeqList_Capacity(SeqList* list)
107 {
108     TSeqList *tlist = NULL; 
109     //异常处理
110     if(list == NULL)
111     {
112         cout << "Capacity Err, list == NULL" << endl;
113         return -1;
114     }
115     tlist = (TSeqList *)list;
116  
117     return tlist->capacity;
118 }
119  
120  
121 //在POS位置插入一个节点
122 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
123 {
124     int i = 0;
125     int ret = 0;
126     TSeqList *tlist = NULL; 
127  
128     //异常处理
129     if(list == NULL || node == NULL || pos<0)
130     {
131         cout << "Insert Err, (list == NULL || node == NULL || pos<0)" << endl;
132         ret = -1;
133         return ret;
134     }
135     tlist = (TSeqList *)list;
136  
137     //判断是否满了
138     if (tlist->length >= tlist->capacity)
139     {
140         cout << "满了" << endl;
141         ret = -2;
142         return ret;
143     }
144     //容错修正 如果插入的pos位置大于链表长度 并且此时容量未满
145     if (pos >= tlist->length)  /////////
146     {
147         pos = tlist->length;
148     }
149  
150     //位置后移并储存
151     for(i = tlist->length; i > pos; i--)
152     {
153         tlist->node[i] = tlist->node[i-1];
154     }
155     //将node[i]改为node
156     tlist->node[i] = (unsigned int*) node;
157     tlist->length++;
158     return 0;
159  
160 }
161  
162  
163 //获取节点信息
164 SeqListNode* SeqList_Get(SeqList* list, int pos)
165 {
166     TSeqList *tlist = NULL; 
167     //异常处理
168     if(list == NULL || pos < 0)
169     {
170         cout << "SeqList_Get Err, list == NULL" << endl;
171         return NULL ;
172     }
173     tlist = (TSeqList *)list;
174     //强制类型转换
175     return (SeqListNode*)tlist->node[pos];
176 }
177  
178  
179 //删除一个节点
180 SeqListNode* SeqList_Delete(SeqList* list, int pos)
181 {
182     TSeqList *tlist = NULL; 
183     SeqListNode* ret = 0;
184     //异常处理
185     if(list == NULL || pos < 0)
186     {
187         cout << "Delete Err" << endl;
188         return NULL ;
189     }
190     tlist = (TSeqList *)list;
191     //将POS位置的node地址给临时ret指针变量
192     ret = (SeqListNode*)tlist->node[pos];
193     //pos 位置后的元素往前移动
194     for(int i = pos + 1; i < tlist->length; i++)
195     {
196         tlist->node[i - 1] = tlist->node[i];
197     }
198     tlist->length--;
199     //返回删除的元素
200     return ret;
201 }

测试代码:

 1 #include "User.h"
 2 #include "seqList.h"
 3 #include <iostream>
 4  
 5 using namespace std;
 6 //定义一个结构体
 7 typedef struct Teacher
 8 {
 9     int age;
10     char name[64];
11  
12 }teacher;
13  
14  
15 int main0()
16 {
17     int ret = 0;
18     int i = 0;
19     //创建顺序链表
20     SeqList* list = NULL;
21     list = SeqList_Create(10);
22  
23     teacher t1,t2,t3,t4,t5;
24  
25     t1.age = 31;
26     t2.age = 32;
27     t3.age = 33;
28     t4.age = 34;
29     t5.age = 35;
30     //头插法插入元素
31     ret = SeqList_Insert(list, (SeqListNode*) &t1, 9);  //测试容错
32     ret = SeqList_Insert(list, (SeqListNode*) &t3, 0);
33     ret = SeqList_Insert(list, (SeqListNode*) &t4, 0);
34     ret = SeqList_Insert(list, (SeqListNode*) &t5, 0);
35     //遍历元素并显示age
36     for (;i < SeqList_Length(list); i++)
37     {
38         teacher* temp = (teacher*) SeqList_Get(list, i);
39         if (temp == NULL)
40         {
41             return 1;
42         }
43         //cout << "temp->age: " << ((teacher* )SeqList_Get(list, i))->age << endl;
44         cout << "temp->age: " << temp->age << endl;
45     }
46     cout << endl;
47     //删除 并显示删除结果
48     int m = 1;
49     while (SeqList_Length(list) > 0)
50     {
51         teacher *t = NULL;
52         t = (teacher*)SeqList_Delete(list, 0);
53         cout << "第" << m << "次头删的数据" << endl;
54         cout << "t->age" << t->age << endl;
55         m++;
56         cout << endl;
57     }
58  
59     //每次遍历删除头部后的链表
60     /*int m = 1;
61     while (SeqList_Length(list) > 0)
62     {
63         SeqList_Delete(list, 0);
64         cout << "第" << m << "次头删的结果" << endl;
65         for (i = 0;i < SeqList_Length(list); i++)
66         {
67             teacher* temp = (teacher*) SeqList_Get(list, i);
68             //cout << "temp->age: " << ((teacher* )SeqList_Get(list, i))->age << endl;
69             cout << "temp->age: " << temp->age << endl;
70         }
71         m++;
72         cout << endl;
73     }
74 */
75     system("pause");
76     return 0;
77 }