4-线性表链式存储-静态链表

一开始对照书上的总觉得哪里不对！傻吊捣鼓了两小时，总算弄出来了

自己用电脑打的感觉。。果然跟光看书不一样，还是不能懒。

【静态链表说明】

1、0号节点为备用空间链表的头结点，MAXSIZE-1号节点为实际链表空间首结点。

2、需要用户自己实现malloc和free函数。

3、辨明数组中哪些分量未被使用的解决办法是把所有未被使用、被删除的分量用游标链成一个备用的链表。

4、由于其实质是用数组替代指针，对于想要用没有指针的语言实现单链表，是一个很好的存储结构。

5、其链节点数据域包括两部分：data（存放数据）、cur（游标，存放后接节点的位置）

【注】

1、静态链表初始化的时候(createValue函数)一定要注意将最后一个元素的下标置零

2、插入与删除操作的过程中一定不要忘记对受影响的链表节点前后进行游标改写的操作

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstring>
  4 using namespace std;
  5 #define ture 1
  6 #define false 0
  7 #define ok 1
  8 #define error -3
  9 #define overflow -2
 10 typedef int Status;
 11 typedef string ElemType;
 12 #define MAXSIZE 100
 13 typedef struct node{
 14     ElemType data;
 15     int cur;
 16 }SLinkList[MAXSIZE];
 17 //space[0]备用链表的头结点
 18 //space[MAXSIZE-1]实际链表的头结点
 19 
 20 void InitSpace_SL(SLinkList &space)
 21 {
 22      space[MAXSIZE-1].cur=0;//表头结点为0号
 23     for(int i=0;i<MAXSIZE-1;i++)
 24       {
 25         space[i].cur=i+1;
 26         }
 27 }
 28 int malloc_SL(SLinkList &space)
 29 {
 30     int i=space[0].cur;//指向备用链表第一位元素节点
 31     if(space[0].cur)//备用链表中还有空节点
 32     i=space[0].cur;
 33     space[0].cur=space[i].cur;//备用链表头结点指向下一个备用节点
 34     return i;
 35 }
 36 
 37 void Free_SL(SLinkList &space,int k)
 38 {
 39     space[k].cur=space[0].cur;
 40     space[0].cur=k;//把标为k的空闲节点回收到备用表。
 41 }
 42 int ListLength(SLinkList &space)
 43 {
 44     int j=space[MAXSIZE-1].cur;
 45     int i=0;
 46     while(j)//最后一个节点的指针域为空，跳出循环
 47     {
 48         i++;
 49         j=space[j].cur;
 50     }
 51     return i;
 52 }
 53 int createValue(SLinkList &space,int num)
 54 {
 55     int i,j=MAXSIZE-1;
 56     space[j].cur=1;
 57     for(i=0;i<num;i++)
 58     {
 59         j=space[j].cur;
 60         cin>>space[j].data;
 61     }
 62     space[0].cur=space[j].cur;
 63     space[j].cur=0;
 64     return ok;
 65 }
 66 int InsertList(SLinkList &space,int i,ElemType s)
 67 {
 68     int k=MAXSIZE-1;
 69     if(i<1||i>ListLength(space))
 70         return error;
 71     int pos=malloc_SL(space);
 72     if(pos)
 73     {
 74         space[pos].data=s;
 75         for(int m=1;m<i;m++)
 76         {
 77             k=space[k].cur;
 78         }//找到第i-1个元素的下标
 79         space[pos].cur=space[k].cur;//一定要记得连接前后游标
 80         space[k].cur=pos;
 81         return ok;
 82     }
 83     return error;
 84 }
 85 void Delete_SL(SLinkList &space,int pos)//删除第pos个节点(下标从0开始)
 86 {
 87     int i;
 88     int k=space[MAXSIZE-1].cur;//指向表头结点
 89     if(i<1||i>ListLength(space))
 90         exit(0);
 91     //int i=0;
 92     pos--;
 93     while(pos--)//找到pos前一位节点
 94     {
 95         k=space[k].cur;
 96     }
 97     int lost=space[k].cur;
 98     space[k].cur=space[lost].cur;
 99     Free_SL(space,lost);
100 }
101 void showList(SLinkList &space)
102 {
103 
104     int j=space[MAXSIZE-1].cur;//0指向的是备用链表的第一位，若要遍历已经存储的链表体得从1号开始。
105        while(j)
106        {
107            cout<<space[j].data<<endl;
108            j=space[j].cur;
109        }
110      cout<<space[j].data<<endl;
111      cout<<"------------------"<<endl;
112 }
113 int main()
114 {
115     SLinkList L1;
116     InitSpace_SL(L1);
117 
118     createValue(L1,6);
119     showList(L1);
120     Delete_SL(L1,1);
121     showList(L1);
122     InsertList(L1,4,"winwin!");
123      showList(L1);
124     return 0;
125 }

4-线性表 链式存储-静态链表

4-线性表链式存储-静态链表