笔记静态链表的实现

 1 #include "stdafx.h"
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 #define MAXSIZE 100
 7 
 8 typedef int ElemType;
 9 
10 typedef struct {
11     ElemType data;
12     int cur;
13 }component,SLinkList[MAXSIZE];
14 
15 void InitSpace_SL(SLinkList &space) {
16     for (int i = 0; i < MAXSIZE - 1; ++i) space[i].cur = i + 1;
17     space[MAXSIZE - 1].cur = 0;
18 }
19 
20 int Malloc_SL(SLinkList &space) {
21     int i = space[0].cur;
22     if (space[0].cur) space[0].cur = space[i].cur;
23     return i;
24 }
25 
26 void Free_SL(SLinkList & space, int k) {
27     space[k].cur = space[0].cur; space[0].cur = k;
28 }
29 
30 void difference(SLinkList &space, int &S) {
31     InitSpace_SL(space);  //初始化备用空间
32     S = Malloc_SL(space);  //生成S的头结点
33     int r = S;
34     cout << "请输入A,B集合的元素个数,用空格隔开" << endl;
35     int m, n;
36     cin >> m >> n;
37     int i, j;
38     cout << "请依次输入A集合的元素并按回车" << endl;
39     int nn;
40     //给A集合添加数据
41     for (j = 1; j <= m; ++j) {
42         i = Malloc_SL(space); //取出下一个空间索引
43         cin>>nn; //赋值
44         space[i].data = nn;
45         space[r].cur = i;  //尾插法（r指向的是最后一个结点，让上一次最后结点指向i索引）
46         r = i;     //r指向最后的节点
47     }
48 
49     space[r].cur = 0;  //将最后一个结点指向空（也就是0）
50     printf("请依次输入B集合的元素\n");
51     int b;
52     int p;
53     int k;
54     for (j = 1; j <= n; ++j) {
55         cin >> b; //读取并记录到临时变量b
56         p = S;  //记录头结点
57         k = space[S].cur;  //k指向第一个结点
58         while (k != space[r].cur && space[k].data != b) {
59             p = k;
60             k = space[k].cur; //指向下一个结点
61         }
62         if (k == space[r].cur) {  //不存在元素b,插入到r所指结点之后
63             i = Malloc_SL(space);
64             space[i].data = b;
65             space[i].cur = space[r].cur;
66             space[r].cur = i;
67         }
68         else {  //存在元素b，删除
69             space[p].cur = space[k].cur;
70             Free_SL(space, k);
71             if (r == k) r = p;
72         }
73     }
74     //指回头指针
75     space[0].cur = S;
76 
77 }
78 
79 void Show_SL(SLinkList &space) {
80     printf("链表的打印结果是\n");
81     int s = Malloc_SL(space); //指向头结点
82     while (space[s].cur != 0) {
83         s = Malloc_SL(space);
84         cout << space[s].data<<" ";
85     }
86     cout << endl;
87 }
88 
89 
90 int main() {
91     SLinkList sl;
92     int s;
93     difference(sl, s);
94     Show_SL(sl);
95     system("pause");
96     return EXIT_SUCCESS;
97 }

 实现效果如下：

 

 

 

学习自 严蔚敏的《数据结构》静态链表