首页 > 静态链表实现(A-B)+(B-A)【代码】

静态链表实现(A-B)+(B-A)【代码】

-----------------------------------------------第一次发代码,写在前面------------------------------------------------------

思路不完全等同于严师太的课本,所以代码并不是参照课本。

代码参照《大话数据结构》相应章节,并经过了相应修改

注意:链表下标为i的节点和链表中第i个节点在链表初始化后是一样的,但是在经过删除操作后不一样了。

为此本人在这里浪费了很多时间调试。注意细节。

代码可有某些地方有瑕疵,但是通过了C::B跑了几组数据,应该没大问题。

共同学习,共同进步!

 

-----------------------------------------------以下摘自《大话数据结构》----------------------------------------------------

在静态链表中,每一个结点包含两部分内容,一部分是data(即有意义的数据),另一部分是cur(存储该元素下一个元素所在数组对应的下标)。

有几个特殊的结点:

首先是下标为0的结点中不包含有意义的数据,它的cur存储的是备用链表(即没有存储的数据的那些结点)第一个结点的下标。如上图2所示,数组第一个元素的cur存放的是7。

其次是数组最后一个元素,数组最后一个元素的cur存放的是静态链表的第一个结点的下标(此处的第一个结点,是指有实质意义的数据的结点)。

最后就是链表的最后一个元素(并不一定是数组的最后一个元素),链表最后一个元素的cur一般存放0,表示它后面的结点为空了。

 

---------------------------------------------代码如下---------------------------------------------------------

 

  1 #include 
  2 
  3 using namespace std;
  4 
  5 #define MAXSIZE 100
  6 
  7 typedef struct
  8 {
  9 int data;
 10 int cur;
 11 }component,SLinkList[MAXSIZE];
 12 
 13 
 14 int InitSpace_SL(SLinkList& space)
 15 {
 16 for(int i=0;i1;i++) space[i].cur=i+1;
 17 space[MAXSIZE-1].cur=0;
 18 return 0;
 19 }
 20 
 21 
 22 int LocateElem_SL(SLinkList &S,int e)//在静态链表中查找第一个值为e的元素,若找到,则返回它在线性表中的位序,否则返回0;
 23 {
 24 int i=S[MAXSIZE-1].cur;
 25 while(i&&S[i].data!=e)
 26 i=S[i].cur;
 27 if(!i) return 0;
 28 else return i;
 29 }
 30 
 31 
 32 int ListLength_SL(SLinkList& L)
 33 {
 34 int j=0;
 35 int i=L[MAXSIZE-1].cur;
 36 while(i)
 37 {
 38 i=L[i].cur;
 39 j++;
 40 }
 41 return j;
 42 }
 43 
 44 
 45 int Malloc_SL(SLinkList &space)
 46 {
 47 int i=space[0].cur;
 48 if(space[0].cur) space[0].cur=space[i].cur;
 49 return i;
 50 }
 51 
 52 
 53 int Free_SL(SLinkList &space,int k)//把下标为k的空闲节点回收到备用链表,该节点成为备用链表中的首节点
 54 {
 55 space[k].cur=space[0].cur;
 56 space[0].cur=k;
 57 return 0;
 58 }
 59 
 60 int ListInsert_SL(SLinkList &L,int i,int e)//在L中第i个元素之前插入新的元素e
 61 {
 62 int j,k,l;
 63 k=MAXSIZE-1;//k为数组最后一个元素的下标
 64 if(i<1||i>ListLength_SL(L)+1) return 0;
 65 j=Malloc_SL(L);
 66 if(j)//L不为空表
 67 {
 68 L[j].data=e;
 69 for(l=1;l<=i-1;i++)
 70 k=L[k].cur;
 71 L[j].cur=L[k].cur;
 72 L[k].cur=j;
 73 }
 74 return 0;
 75 }
 76 
 77 
 78 int ListInsert2_SL(SLinkList &L,int e)//在备用链表表头插入一个元素
 79 {
 80 int i,j=L[MAXSIZE-1].cur,k=Malloc_SL(L);
 81 for(i=1;i< ListLength_SL(L);i++)
 82 j=L[j].cur;
 83 L[j].cur=k;
 84 L[k].data=e;
 85 L[0].cur=L[k].cur;
 86 L[k].cur=0;
 87 return 0;
 88 }
 89 
 90  
 91 
 92 int ListDelete_SL(SLinkList &L,int i)//删除在L中的第i个元素e
 93 {
 94 int j,k;
 95 if(i<1||i>ListLength_SL(L)) return 0;
 96 k=MAXSIZE-1;
 97 for(j=1;j<=i-1;j++)
 98 k=L[k].cur;
 99 j=L[k].cur;
100 L[k].cur=L[j].cur;
101 Free_SL(L,j);
102 return 0;
103 }
104 
105 
106 int ListDelete2_SL(SLinkList &L,int i)//删除在L中下标为i的元素L[i]
107 {
108 int k=L[MAXSIZE-1].cur,m=L[k].cur;
109 int j=L[0].cur;
110 while(m!=i)
111 {
112 k=L[k].cur;
113 m=L[k].cur;
114 }
115 L[k].cur=L[m].cur;
116 L[0].cur=i;
117 L[i].cur=j;
118 return 0;
119 }
120 int MergeList_SL(SLinkList &L1,SLinkList &L2)//(A-B)+(B-A)
121 {
122 int i=L2[MAXSIZE-1].cur;
123 int m;
124 while(i)
125 {
126 m=0;
127 int j=L1[MAXSIZE-1].cur;
128 while(j)
129 {
130 m=LocateElem_SL(L1,L2[i].data);
131 if(m) {ListDelete2_SL(L1,m);break;}
132 j=L1[j].cur;
133 }
134 if(!m) ListInsert2_SL(L1,L2[i].data);
135 i=L2[i].cur;
136 }
137 return 0;
138 }
139 
140 
141 int main()
142 {
143 int m,n,j;
144 SLinkList L1,L2;
145 InitSpace_SL(L1);
146 InitSpace_SL(L2);
147 cout<<"输入集合A中的元素个数:"<<endl;
148 cin>>m;
149 cout<<"输入集合A中各元素的值:"<<endl;
150 for(int i=1;i<=m;i++)
151 {
152 cin>>L1[i].data;
153 L1[0].cur=L1[i].cur;
154 }
155 L1[m].cur=0;
156 L1[MAXSIZE-1].cur=1;
157 cout<<"输入集合B中的元素个数:"<<endl;
158 cin>>n;
159 cout<<"输入集合B中各元素的值:"<<endl;
160 for(int i=1;i<=n;i++)
161 {
162 cin>>L2[i].data;
163 L2[0].cur=L2[i].cur;L2[MAXSIZE-1].cur=1;
164 }
165 L2[n].cur=0;
166 L2[MAXSIZE-1].cur=1;
167 MergeList_SL(L1,L2);
168 j=L1[MAXSIZE-1].cur;
169 while(j)
170 {
171 cout<" ";
172 j=L1[j].cur;
173 }
174 return 0;
175 }

 

 

-----XJX

转载于:https://www.cnblogs.com/journal-of-xjx/p/5897654.html

更多相关:

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...