（C语⾔）单链表的顺序实现（数据结构⼀）
1.数据类型定义
在代码中为了清楚的表⽰⼀些错误和函数运⾏状态，我们预先定义⼀些变量来表⽰这些状态。在head.h头⽂件中有如下定义：
1//定义数据结构中要⽤到的⼀些变量和类型
2#ifndef HEAD_H
3#define HEAD_H
4
5#include <stdio.h>
6#include <malloc.h>
7#include <stdlib.h>
8
9#define TRUE 1
10#define FALSE 0
11#define OK 1
12#define ERROR 0
13#define INFEASIBLE -1
14#define OVERFLOW -2 //分配内存出错
c语言listinsert函数15
16typedef int Status; //函数返回值类型
17typedef int ElemType; //⽤户定义的数据类型
18
19#endif
2.单链表数据结构实现
为了实现单链表，我们定义结构体 LinearList，具体代码如下：
1typedef struct{
2 ElemType *elem; //存放数据
3 int length; //链表长度
4 int listsize; //链表容量
5}LinearList;
3.链表⽅法摘要
1Status InitList(LinearList & L); //初始化链表
2
3Status DestroyList(LinearList &L); //销毁链表
4
5Status ClearList(LinearList &L); //清空链表
6
7Status ListEmpty(LinearList L); //链表是否为空
8
9Status ListLength(LinearList L); //链表长度
10
11Status GetElem(LinearList L,int i,ElemType &e); //获得链表第i位置的长度，返回给e
12
13Status LocateElem(LinearList L,ElemType e,Status(*comp)(ElemType,ElemType)); //链表中满⾜comp条件的数据的位置14
15Status PriorElem(LinearList L,ElemType cur_e,ElemType &per_e) // cur_e的前⼀个数据
16
17Status NextElem(LinearList L,ElemType cur_e,ElemType &next_e); //cur_e的后⼀个数据
18
19Status ListInsert(LinearList &L,int i,ElemType e); //在第i个位置插⼊e
20
21Status ListDelete(LinearList &L,int i,ElemType &e); //删除第i位置数据，并给e
22
23Status Union(LinearList &La,LinearList Lb); //La=la并Lb
24
25Status MergeList(LinearList La,LinearList Lb,LinearList &Lc); //La和Lb从⼩到⼤排序后给Lc
26
27Status MergeList_pt(LinearList La,LinearList Lb,LinearList &Lc); //La和Lb从⼩到⼤排序后给Lc，指针实现
4.单链表顺序实现
在LinearList.h⽂件中实现单链表的⽅法，具体代码如下：
1#ifndef LINEARLIST_H
2#define LINEARLIST_H
3
4#include "head.h"
5
6#define LIST_INIT_SIZE 100 //初始化链表⼤⼩
7#define LIST_INCERMENT 10 //链表容量增加基本单元
8
9
10typedef struct{
11 ElemType *elem; //存放数据
12 int length; //链表长度
13 int listsize; //链表容量
14}LinearList;
15
16
17Status equal(int a,int b){
18 return a==b;
19}
20
21Status InitList(LinearList & L){
22 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
23 if (!L.elem) return OVERFLOW;
24 L.length=0;
25 L.listsize=LIST_INIT_SIZE;
26 return OK;
27}
28
29Status DestroyList(LinearList &L){
30 free(L.elem);
30 free(L.elem);
31 L.elem=NULL;
32 L.length=0;
33 L.listsize=0;
34 return OK;
35};
36
37Status ClearList(LinearList &L){
38 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
39 if (!L.elem) return OVERFLOW;
40 L.length=0;
41 L.listsize=LIST_INIT_SIZE;
42 return OK;
43}
44
45Status ListEmpty(LinearList L){
46 return L.length==0;
47}
48
49Status ListLength(LinearList L){
50 return L.length;
51}
52
53Status GetElem(LinearList L,int i,ElemType &e){
54 if (i<1 || i>L.length) return ERROR;
55 e=L.elem[i-1];
56 return OK;
57}
58
59Status LocateElem(LinearList L,ElemType e,Status(*comp)(ElemType,ElemType)){
60 int i=0;
61 for (;i<L.length;i++)
62 {
63 if (comp(e,L.elem[i]))
64 break;
65 }
66 if (i==L.length)
67 {
68 return 0;
69 }
70 return i+1;
71}
72
73Status PriorElem(LinearList L,ElemType cur_e,ElemType &per_e){
74 int i=LocateElem(L,cur_e,equal);
75 if (i<=1) return ERROR;
76 per_e=L.elem[i-2];
77 return OK;
78}
79
80Status NextElem(LinearList L,ElemType cur_e,ElemType &next_e){
81 int i=LocateElem(L,cur_e,equal);
82 if ( i==0 || i==L.length) return ERROR;
83 return L.elem[i];
84}
85
86Status ListInsert(LinearList &L,int i,ElemType e){
87 int length=L.length;
88 if(i<1 ||i>length+1) return ERROR;
89 if (length>=L.listsize){
90 ElemType *newBase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCERMENT)*sizeof(ElemType));
91 if(!newBase) return OVERFLOW;
92 L.elem=newBase;
93 L.listsize+=LIST_INCERMENT;
94 }
95 ElemType *q=&L.elem[i-1];
95 ElemType *q=&L.elem[i-1];
96 ElemType *p=&L.elem[length];
97 while(q<=p){
98 *(p+1)=*p;
99 p--;
100 }
101 *q=e;
102 ++L.length;
103 return OK;
104};
105
106
107Status ListDelete(LinearList &L,int i,ElemType &e){
108 if(i<1 ||i>L.length) return ERROR;
109 ElemType *p=&L.elem[i-1];
110 ElemType *q=&L.elem[L.length-1];
111 e=*p;
112 while(p<=q){
113 *p=*(p+1);
114 ++p;
115 }
116 --L.length;
117 return OK;
118
119}
120
121Status Union(LinearList &La,LinearList Lb){
122 int la_l=ListLength(La);
123 int lb_l=ListLength(Lb);
124 for (int i=1;i<=lb_l;i++)
125 {
126 ElemType e=0;
127 GetElem(Lb,i,e);
128 if(!LocateElem(La,e,equal)){
129 int l=ListLength(La);
130 ListInsert(La,++l,e);
131 }
132 }
133 return OK;
134}
135
136Status MergeList(LinearList La,LinearList Lb,LinearList &Lc){ 137 int La_l=ListLength(La);
138 int Lb_l=ListLength(Lb);
139 InitList(Lc);
140 int i=1,j=1,k=1;
141 while(i<=La_l&&j<=Lb_l){
142 ElemType La_e,Lb_e;
143 GetElem(La,i,La_e);
144 GetElem(Lb,j,Lb_e);
145 if (La_e<=Lb_e)
146 {
147 ListInsert(Lc,k++,La_e);
148 i++;
149 }else{
150 ListInsert(Lc,k++,Lb_e);
151 j++;
152 }
153 }
154 while(i<=La_l){
155 ElemType La_e;
156 GetElem(La,i,La_e);
157 ListInsert(Lc,k++,La_e);
158 i++;
159 }
160 while(j<=Lb_l){
161 ElemType Lb_e;
162 GetElem(Lb,j,Lb_e);
163 ListInsert(Lc,k++,Lb_e);
164 j++;
165 }
166 return OK;
167}
168
169Status MergeList_pt(LinearList La,LinearList Lb,LinearList &Lc){ 170 int pc_l=La.length+Lb.length;
171 Lc.elem=(ElemType*)malloc(sizeof(ElemType)*pc_l);
172 Lc.length=pc_l;
173 Lc.listsize=pc_l;
174 if (!Lc.elem) return OVERFLOW;
175 ElemType* pa=La.elem;
176 ElemType* pb=Lb.elem;
177 ElemType* pc=Lc.elem;
178 ElemType* pa_last=pa+La.length-1;
179 ElemType* pb_last=pb+Lb.length-1;
180 while(pa<=pa_last&&pb<=pb_last){
181 if(*pa<=*pb){
182 *pc++=*pa++;
183 }else{
184 *pc++=*pb++;
185 }
186 }
187 while(pa<=pa_last){
188 *pc++=*pa++;
189 }
190 while(pb<=pb_last){
191 *pc++=*pb++;
192 }
193 return OK;
194
195
196
197}
198#endif
5.单链表测试
1#include "LinearList.h"
2
3void main(){
4 LinearList L;
5 InitList(L); //初始化链表
6 for (int i=1;i<10;i++)
7 ListInsert(L,i,i); //向链表中插⼊数据
8
9 printf("\n链表L中数据：");
10 for(int i=1;i<ListLength(L);i++){
11 ElemType e;
12 GetElem(L,i,e);
13 printf("%d->",e);
14 }
15 printf("end");
16
17 ElemType e;
18 ListDelete(L,5,e); //删除第5位置数据
19 printf("\n删除第5位置数据为：%d",e);
20
21
22 PriorElem(L,6,e); //前⼀个数据
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论