数据结构（严蔚敏）2.3.2静态链表
数据结构（严蔚敏）2.3.2静态链表
柳月树
数据结构（严蔚敏）2.3.2静态链表
#include<stdio.h>
#include<stdlib.h>
//静态链表
#define maxsize 1000
typedef float elemtype;
typedef struct{
elemtype data;
int cur;
}compoent,slinklist[maxsize];
//算法2.15
int malloc_jt(slinklist &l){//从备用空间取得一个结点
int i=l[0].cur;
if(l[0].cur) //C语言中1...n是真，如果0号指向的不为0,就把0号指向的改为第i号指向的
//第一次的时候，由于0号指向的为1，通过if，则0号指向的变成了1号指向的，即0号指向2了，这时候返回的int为1
//第二次的时候，由于0号指向的为2，通过if，则0号指向的变为了2号指向的，即0号指向3了，这时候返回的int为2
l[0].cur=l[i].cur;
return i;
}
//算法2.16
void free_jt(slinklist &l,int k){//将空闲出的结点放到备用结点上，此处为释放k号
//因为0号本来指向的就是首个备用的，将旧的首个备用赋为k指向的，在将0指向k,设为新的首个备用
l[k].cur=l[0].cur;//将0号指向的赋给k号指向的
l[0].cur=k;//将0号指向的赋成k
}
//算法2.14
void initlist_jt(slinklist &l){
for(int i=0;i<maxsize;i++)
l[i].cur=i+1;
l[maxsize-1].cur=0;
}
int listlength_jt(slinklist l){
return l[0].data;
}
int insertlist_jt(slinklist &l,elemtype e,int &end){
int j=malloc_jt(l);
if(j){
l[j].data=e;
l[0].data++;
l[end].cur=j;
l[j].cur=0;
end=j;
return 0;
}
return j;
}
int deletelist_jt(slinklist &l,int k,int &start){
int is=start;
int length=listlength_jt(l);
if(k==start){//如果删除的是第一个
start=l[k].cur;
free_jt(l,k);
l[0].data--;
return start;
}
for(int i=0;i<length;i++){
if(l[is].cur==k){
if(l[k].cur==0){//如果删除的是最后一个
l[is].cur==0;
l[0].data--;
free_jt(l,k);
return length;
}
int j=l[is].cur=l[l[is].cur].cur;//要删除的前一个指向要删除的后一个
free_jt(l,k);
l[0].data--;
return j;
}
is=l[is].cur;
}
return 0;
}
int locateelem_jt(slinklist l,elemtype e,int start){
while(start&&l[start].data!=e){
start=l[start].cur;
}
return start;
}
void printf_jt(slinklist l,int i){
int k=listlength_jt(l);
for(;k>0;i=l[i].cur){
printf("%f ",l[i].data);
k--;
}
}
int scanf_jt(slinklist &l){
printf("请输入您想输入的个数：");
int num=NULL;scanf("%d",&num);
printf("请您开始输入\n");
int i,seat;
if(num<=0) return 0;
if(num>1){
seat=malloc_jt(l);
l[0].data=num;
for(int j=0;j<num;j++){
elemtype e=NULL;
scanf("%f",&e);
i=insertlist_jt(l,e,seat);
}}
l[i].cur=0;//使最后一个结点指向第0个
return l[seat].cur;
}
//算法2.17 (A-B)U(B-A) 但是：例如A有1，B输入1、1，结果还是有1
void difference_jt(slinklist &l,int &s){//自己写的
initlist_jt(l);
s=malloc_jt(l);//给s分配第一个结点,由于此项，导致链表内空间位置为1不能用
int r=s;//r指向最后结点
s=l[r].cur;
printf("请输入您想输入A的元素个数： ");
int num=0;scanf("%d",&num);l[0].data=(elemtype)num;
printf("请输入集合A：\n");
for(int k=0;k<num;k++){
r=malloc_jt(l);
scanf("%f",&l[r].data);
}
l[r].cur=0;
printf("请输入您想输入B的元素个数： ");
scanf("%d",&num);
printf("请输入集合B：\n");
elemtype e;
for(int k=0;k<num;k++){
scanf("%f",&e);
int yorn=locateelem_jt(l,e,s);
if(yorn){//找到，删除
deletelist_jt(l,yorn,s);
}
else{//没找到
int j=insertlist_jt(l,e,r);
}
}
}
void difference(slinklist &space,int &s){//教材
initlist_jt(space);
s=malloc_jt(space);//不做存储数据使用
int r=s,m,n;
printf("请输入A和B列表中的元素个数：");
scanf("%d%d",&m,&n); printf("开始输入A：");
for(int j=1;j<=m;j++){//输入A
int i=malloc_jt(space);
scanf("%f",space[i].data);
space[r].cur=i;
r=i;}//使r始终指向最后一个
space[r].cur=0; printf("开始输入B：");
for(int j=1;j<=n;++j){
int b;scanf("%f",b);
int p=s;
int k=space[s].cur;//k指向第一个结点（存储数据的）
while(k!=space[r].cur&&space[k].data!=b){
p=k;
k=space[k].cur;
}
if(k==space[r].cur){//列表存在此
int i=malloc_jt(space);
space[i].data=b;
space[i].cur=space[r].cur;
space[i].cur=i;
}
else{
space[p].cur=space[k].cur;
free_jt(space,k);
if(r==k) r==p;}//若删除的是r,即删除的是最后一个，就要修改修改为p,即修改最后一个指向0号
}
}
void main(){
slinklist l;
//printf("**************测试initlist_jt \n");
//initlist_jt(l);
//printf("\n");
//printf("**************测试scanf_jt \n");
//int seat=scanf_jt(l);
//printf("\n");
//printf("**************测试printf_jt \n");
//printf_jt(l,seat);
//printf("\n");
printf("**************测试difference_jt \n");
int seat;
difference_jt(l,seat);
printf("\n");
printf_jt(l,seat);
printf("\n");
//printf("**************测试locateelem_jt \n为3的是元素位序为：%d\n",locateelem_jt(l,3,seat));
}