您的位置:首页 > 教程资讯 > 网络编程 > C语言 > 能判断是否还有剩余空间的静态链表

能判断是否还有剩余空间的静态链表

发布于:2016-05-26 10:03:03   分享到:

  第一次系统的学习数据结构是在半年前,看小甲鱼的数据结构与算法视频,自学的话有许多不懂得地方,什么AVL树,红黑树,图的最短路径,最小生成树...但总归对数据结构与算法有一个大体的印象,到现在随着不断写代码,做OJ题,愈发认识到数据结构与算法的重要性,打算再看一遍,现在看着:大话数据结构(程杰著),数据结构(C语言版严蔚敏著),不推荐新手使用 数据结构与算法分析(Mark Allen Weiss 著)这本书真的很难懂。

  回归正题,我看了许多书有关静态链表的描述和代码发现都没有判断是否还有剩余空间,自己琢磨了一个晚上把代码弄好了。

  1 #include <stdio.h>      //Anjaxs
  2 #include <stdbool.h>
  3
  4 #define MAXSIZE  7
  5 typedef  int ElemType;
  6 
  7 typedef struct{
  8     ElemType data;
  9     int cur;
 10 }StaticList;
 11 
 12 int Malloc_SL(StaticList * space);
 13 void Free_SL(StaticList * space, int k);
 14 void InitList(StaticList * space); 
 15 bool ListInsert(StaticList * L, int i, ElemType e);
 16 bool ListDelete(StaticList * L, int i);
 17 int ListLength(StaticList * L);
 18 void show(StaticList * L);
 19 
 20 int main()
 21 {
 22     int i;
 23     int choice;
 24     StaticList L[MAXSIZE];
 25     InitList(L);
 26     printf("1:插入 2:删除 3:输出 0:退出\n");
 27     while (scanf("%d",&choice) && choice!=0)
 28     {
 29         int x;
 30         int pos;
 31         switch (choice)
 32         {
 33             case 1:
 34                 printf("输入要插入的数字和位置\n");
 35                 scanf("%d %d", &x, &pos);
 36                 ListInsert(L, pos, x);
 37                 break;
 38             case 2:
 39                 printf("输入要删除的位置\n");
 40                 scanf("%d",&pos);
 41                 ListDelete(L, pos);
 42                 break;
 43             case 3:
 44                 show(L);
 45                 break;
 46             default:
 47                 printf("请输入1-3.\n");
 48                 break;
 49         }
 50         printf("1:插入 2:删除 3:输出 0:退出\n");
 51     }
 52 
 53     return 0;
 54 }
 55 
 56 
 57 void InitList(StaticList *space)
 58 {
 59     int i;
 60     //space[0].cur为指向第一个空闲位置的指针
 61     //space[MAXSIZE-1].cur为头指针
 62     for (i = 0; i < MAXSIZE-1; ++i){
 63         space[i].data = 0;
 64         space[i].cur = i+1;
 65     }
 66     //目前静态链表为空,最后一个元素的cur为0
 67     space[MAXSIZE-1].cur = 0;
 68     space[MAXSIZE-1].data = 0;
 69 }
 70 
 71 bool ListInsert(StaticList *L, int i, ElemType e)
 72 {
 73     int j, k, l;
 74     k = MAXSIZE-1;
 75     if (i < 1 || i > ListLength(L)+1){
 76         printf("请输入合法的位置。\n");
 77         return false;
 78     }
 79     if (ListLength(L) >= MAXSIZE-2)
 80     {
 81         printf("没有空闲空间了。\n");
 82         return false;
 83     }
 84     j = Malloc_SL(L);
 85     if (j)
 86     {
 87         L[j].data = e;
 88         for (l = 1; l <= i-1; ++l)
 89             k = L[k].cur;
 90         L[j].cur = L[k].cur;
 91         L[k].cur = j;
 92         return true;
 93     }
 94     
 95     return false;
 96 }
 97 
 98 bool ListDelete(StaticList * L, int i)
 99 {
100     int j, k;
101     if (i < 1 || i > ListLength(L)){
102         printf("请输入合法的位置。\n");
103         return false;
104     }
105     
106     k = MAXSIZE-1;
107     for (j = 1; j <= i-1; ++j)
108         k = L[k].cur;
109     j = L[k].cur;
110     L[k].cur = L[j].cur;
111     Free_SL(L,j);
112     return true;
113 }
114 
115 int ListLength(StaticList * L)
116 {
117     int j = 0;
118     int i = L[MAXSIZE-1].cur;
119     while (i)
120     {
121         i = L[i].cur;
122         j++;
123     }
124 
125     return j;
126 }
127 
128 int Malloc_SL(StaticList * space)
129 {
130     //返回第一个备用空闲的下标
131     int i = space[0].cur;
132     
133     if (space[0].cur)
134         space[0].cur = space[i].cur;
135     
136     return i;    
137 }
138 
139 void Free_SL(StaticList * space, int k)
140 {
141     space[k].cur = space[0].cur;
142     space[0].cur = k;
143 }
144 
145 void show(StaticList * L)
146 {
147     int i;
148     printf("%30s\n","静态链表");
149     printf("%8s","index:");
150     for (i=0 ; i<MAXSIZE ; ++i)
151     {
152         printf("%5d ",i);
153     }
154     printf("\n%8s","data:");
155     for (i=0 ; i<MAXSIZE ; ++i)
156     {
157         printf("%5d ",L[i].data);
158     }
159     printf("\n%8s","cur:");
160     for (i=0 ; i<MAXSIZE ; ++i)
161     {
162         printf("%5d ",L[i].cur);
163     }    
164     printf("\n\n");
165     i = L[MAXSIZE-1].cur;
166     while (i)
167     {
168         printf("%d->", L[i].data);
169         i = L[i].cur;
170     }
171     printf("^\n\n");
172 }

关于我们  加入我们  版权声明  商务合作  友情链接  网站地图  站长统计

脚本大全-脚本语言之家-版权所有 

Copyright (C) 2016 jiaoben.net, All Rights Reserved