【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)
程序员文章站
2022-06-06 13:58:46
...
一.问题((A-B)U(B-A))静态链表实现
*《数据结构》P33
* 需要注意的是算法2.14没什么好说的,只是初始化整个结构体数组,算法2.15是在整个备用空间取一个结点当成新链表,算法2.16是把不再使用的节点还到备用链表上
* 可以看到算法2.17就是主要的算法了,其主要结构就是两个for循环,第一个for循环用于建立集合A的静态链表,第二个for用来输入集合B的元素,在每一趟循环中用while去遍历链表A,看元素是插入还是删除
二.代码与结果
#ifndef __HEAD_H__
#define __HEAD_H__ 100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#define MAXSIZE 10
#define PRINT(format,...) printf(format,##__VA_ARGS__)
/*static linklist*/
typedef struct
{
int data;
int cur;
} SLinkList;
/*function declarations*/
void initspace_sl(SLinkList* s);
void diff_sl(SLinkList * s);
void print_sl(SLinkList* s);
#endif
#include "head.h"
#define DEBUG 100
int main(void)
{
SLinkList s[MAXSIZE];
initspace_sl(&s[0]);
#ifdef DEBUG
print_sl(s);
#endif
diff_sl(s);
print_sl(s);
return 0;
}
#include "head.h"
static int malloc_sl(SLinkList* s)
{
int i = 0;
i = s[0].cur;
if(i != 0)
{
s[0].cur = s[i].cur;
}
return i;
}
/*将下标为k的节点回收*/
static void free_sl(SLinkList* s, int k)
{
s[k].cur = s[0].cur;
s[0].cur = k;
s[k].data = 0xFFFFFFFF;
return;
}
/*(A - B) U (B - A)*/
/*首先假设A={1, 3, 4}
首先假设B={2, 4, 6}
*/
void diff_sl(SLinkList* s)
{
int head = 0;
int i = 0; //for circle
int j = 0; //for circle
int k = 0; //for traverse chain-A
int prev = 0; //for traverse chain-A record previous pos
int rear = 0;
int tmp_b = 0;
head = malloc_sl(s);
rear = head;
/*chain A*/
for(i = 0; i < 3; i++)
{
j = malloc_sl(s);
PRINT("Please input data to A:%d/3:", i+1);
scanf("%d", &(s[j].data));
s[rear].cur = j;
rear = j;
}
s[rear].cur = 0;
/*chain B*/
for(i = 0; i < 3; i++)
{
PRINT("Please input data to B:%d/3:", i+1);
scanf("%d", &tmp_b);
k = s[head].cur;
while((k != s[rear].cur) && (s[k].data != tmp_b))
{
prev = k;
k = s[k].cur;
}
/*当前表中不存在该元素,插入在rear之后
*且rear位置不变
*/
if(k == s[rear].cur)/*insert*/
{
j = malloc_sl(s);
s[j].data = tmp_b;
s[j].cur = s[rear].cur;
s[rear].cur = j;
}
else /*delete*/
{
s[prev].cur = s[k].cur;
if(k == rear)
{
rear = prev;
}
free_sl(s, k);
}
}
return;
}
void initspace_sl(SLinkList* s)
{
int i = 0;
for(i = 0; i < MAXSIZE; i++)
{
s[i].data = 0xFFFFFFFF;
s[i].cur = i + 1;
}
s[MAXSIZE - 1].cur = 0;
return;
}
void print_sl(SLinkList* s)
{
int i = 0;
PRINT("=====START=====\n");
for(i = 0; i < MAXSIZE; i++)
{
PRINT("s[%d].data = %#x, s[%d].cur = %d\n", i, s[i].data, i, s[i].cur);
}
PRINT("=====ENDOF=====\n");
return;
}
情形一:A={1,3,5} B={2,4,6} (A - B)U(B - A)={1,3,5,6,4,2}
情形二:A={1,3,4} B={2,4,6} (A - B)U(B - A)={1,3,6,2}