数据结构 上机【实验一】

实验1  顺序表基本操作

实验目的
1．  熟悉C语言的上机环境，掌握C语言的基本结构。
2．  会定义线性表的顺序存储结构。
3．  熟悉对顺序表的一些基本操作和具体的函数定义。
注意事项
在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。
实验内容
该程序的功能是对元素类型为整型的顺序表进行一些操作。该程序包括顺序表结构类型的定义以及对顺序表操作的具体的函数定义和主函数。
/* 定义DataType为int类型 */
typedef int DataType;
 
/*顺序表存储空间的总分配量*/
#define MAXSIZE 100
 
/* 顺序存储类型 */
typedef struct
{DataType data[MAXSIZE]; /*存放线性表的数组*/
int length;               /* length是顺序表的长度*/
}SeqList;
 
/* 初始化顺序表 */
SeqList SeqListInit( )
 
/* 清空顺序表 */
void ListClear(SeqList L)
 
/* 求顺序表长度 */
int ListLength(SeqList L)
 
/* 检查顺序表是否为空 */
int ListEmpty(SeqList L)
 
/*检查顺序表是否为满 */
int ListFull(SeqList L)
 
/* 遍历顺序表 */
void ListTraverse(SeqList L)
 
/* 从顺序表中查找元素 */
DataType ListGet(SeqList L ,int i)
 
/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */
int ListLocate(SeqList L, DataType x)
 
/* 向顺序表中插入元素 */
void ListInsert(SeqList L，int i，DataType x)
 
/* 从顺序表中删除元素 */
void ListDelete(SeqList L,int i) 
 
/*求顺序表中元素的前驱*/
DataType ListPrior (SeqList L,DataType e)
 
/*求顺序表中元素的后继*/
DataType ListNext(SeqList L,DataType e)

  1 // 实验1 顺序表基本操作 
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 
  5 /* 定义DataType为int类型 */
  6 
  7 typedef int DataType;
  8  
  9 
 10 /*顺序表存储空间的总分配量*/
 11 
 12 #define MAXSIZE 100
 13 
 14 /* 顺序存储类型 */
 15 
 16 typedef struct{
 17         DataType data[MAXSIZE]; /*存放线性表的数组*/
 18         int length;               /* length是顺序表的长度*/
 19 }SeqList;
 20 
 21 /* 1.初始化顺序表 */
 22 
 23 SeqList SeqListInit( )
 24 {
 25     SeqList sq;    //分配线性表的存储空间
 26     sq.length = 0;
 27     return sq;
 28 }
 29  
 30 
 31 /* 2.清空顺序表 */
 32 
 33 void ListClear(SeqList *L)
 34 {
 35     L->length =    0;
 36 }
 37  
 38 
 39 /* 3.求顺序表长度 */
 40 
 41 int ListLength(SeqList L)
 42 {
 43     return L.length;
 44 }
 45 
 46 /* 4.检查顺序表是否为空 */
 47 
 48 int ListEmpty(SeqList L)
 49 {
 50     if(L.length==0)    //是空的
 51         return 1;
 52     else    //不是空的
 53         return 0;
 54 }
 55  
 56 
 57 /* 5.检查顺序表是否为满 */
 58 
 59 int ListFull(SeqList L)
 60 {
 61     if(L.length==MAXSIZE)    //满了
 62         return 1;
 63     else 
 64         return 0;
 65 }
 66  
 67 
 68 /* 6.遍历顺序表 */
 69 
 70 void ListTraverse(SeqList L)
 71 {
 72      int i;
 73      for(i=0;i<L.length;i++){
 74         printf("%d ",L.data[i]);                                     
 75      }
 76      printf("\n");
 77 }
 78  
 79 
 80 /* 7.从顺序表中查找元素 */
 81 
 82 DataType ListGet(SeqList L ,int i)
 83 {
 84     return L.data[i-1];
 85 }
 86 
 87  
 88 
 89 /* 8.从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */
 90 
 91 int ListLocate(SeqList L, DataType x)
 92 {
 93     int i;
 94     for(i=0;i<L.length;i++){
 95         if(L.data[i]==x)
 96             return i+1;
 97     }
 98     return 0;
 99 }
100 
101  
102 
103 /* 9.向顺序表中插入元素 */
104 
105 void ListInsert(SeqList* L,int i,DataType x)
106 {
107     if(L->length==MAXSIZE)    //顺序表已经满了，不能再插入元素了 
108         return;
109     int j;
110     for(j=L->length-1;j>=i-1;j--)    //元素后移 
111         L->data[j+1] = L->data[j];
112     L->data[i-1] = x;    //插入 
113     L->length++;    //长度加1
114     return ;
115 }
116 
117  
118 
119 /* 10.从顺序表中删除元素 */
120 
121 void ListDelete(SeqList* L,int i)  
122 {
123     int j;
124     for(j=i;j<L->length;j++){    //向前覆盖 
125         L->data[j-1] = L->data[j];    
126     }
127     L->length--;    //长度减1
128     return ;
129 }
130 
131  
132 
133 /* 11.求顺序表中元素的前驱*/
134 
135 DataType ListPrior (SeqList L,DataType e)
136 {
137     int i;
138     for(i=0;i<L.length;i++)
139         if(L.data[i]==e)
140             break;    
141     if(i==L.length)    //如果没有找到元素e 
142         return 0;
143     if(i==0)        //如果e是第一个元素，则没有前驱 
144         return 0;
145     return L.data[i-1];
146 }
147 
148  
149 
150 /* 12.求顺序表中元素的后继*/
151 
152 DataType ListNext(SeqList L,DataType e)
153 {
154     int i;
155     for(i=0;i<L.length;i++)
156         if(L.data[i]==e)
157             break;    
158     if(i==L.length)    //如果没有找到元素e 
159         return 0;
160     if(i==L.length-1)    //如果e是最后一个元素，说明他没有后继 
161         return 0;
162     return L.data[i+1];
163 }
164 
165 //测试程序 
166 int main()
167 { 
168     /* 初始化顺序表 */
169     SeqList L = SeqListInit();
170     
171     /* 向顺序表中插入元素 */
172     int i;
173     for(i=1;i<=10;i++)
174         ListInsert(&L,i,i);
175         
176     /* 遍历顺序表 */
177     ListTraverse(L);
178     printf("\n");
179 
180     /* 求顺序表长度 */
181     printf("顺序表长度：【%d】\n",ListLength(L));
182     printf("\n");
183 
184     /* 检查顺序表是否为空 */
185     if(ListEmpty(L))
186         printf("是否为空判定：顺序表已空\n");
187     else
188         printf("是否为空判定：顺序表未空\n");
189     printf("\n");
190 
191     /*检查顺序表是否为满 */
192     if(ListFull(L))
193         printf("是否为满判定：顺序表已满\n");
194     else
195         printf("是否为满判定：顺序表未满\n");
196     printf("\n");
197     
198     /* 从顺序表中查找元素 */
199     i=4;
200     printf("顺序表中第%d个元素是【%d】\n",i,ListGet(L,i));
201     printf("\n");
202 
203     /* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */
204     int x = 3;
205     printf("值为%d的元素是顺序表中第【%d】个元素\n",x,ListLocate(L,x));
206     printf("\n");
207 
208     /*求顺序表中元素的前驱*/
209     int e = 3;
210     printf("值为%d的元素的前驱是【%d】\n",e,ListPrior(L,e));
211     printf("\n");
212 
213     /*求顺序表中元素的后继*/
214     e = 5;
215     printf("值为%d的元素的后继是【%d】\n",e,ListNext(L,e));
216     printf("\n");
217 
218     /* 从顺序表中删除元素 */
219     i=10;
220     printf("删除第%d个元素之后：\n",i);
221     ListDelete(&L,i);
222     ListTraverse(L);
223     printf("\n");
224 
225     /* 清空顺序表 */
226     ListClear(&L);
227     ListTraverse(L);
228 
229     return 0;
230 }