xianxingbiaonizhi（shunxubiao）.c

来自「数据结构中实现顺序表的逆置算法」· C语言 代码 · 共 143 行

/* 程序名 */
 
 #include<string.h>
 #include<ctype.h>
 #include<malloc.h> /* malloc()等 */
 #include<limits.h> /* INT_MAX等 */
 #include<stdio.h> /* EOF(=^Z或F6),NULL */
 #include<stdlib.h> /* atoi() */
 #include<io.h> /* eof() */
 #include<math.h> /* floor(),ceil(),abs() */
 #include<process.h> /* exit() */
 /* 函数结果状态代码 */
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 typedef int ElemType;
  
  
  /* 线性表的动态分配顺序存储结构 */
 
 #define LIST_INIT_SIZE 10 			// 线性表存储空间的初始分配量 
 #define LISTINCREMENT 2 			// 线性表存储空间的分配增量 
 typedef struct
 {
   ElemType *elem; 					// 存储空间基址 
   int length; 						// 当前长度 
   int listsize; 					// 当前分配的存储容量(以sizeof(ElemType)为单位) 
 }SqList;
 
  
  
  /* 顺序表示的线性表的基本操作 */
 Status InitList(SqList *L) /* 算法2.3 */
 { /* 操作结果：构造一个空的顺序线性表 */
   (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
   if(!(*L).elem)
     exit(OVERFLOW); /* 存储分配失败 */
   (*L).length=0; /* 空表长度为0 */
   (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */
   return OK;
 }

 Status DestroyList(SqList *L)
 { /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */
   free((*L).elem);
   (*L).elem=NULL;
   (*L).length=0;
   (*L).listsize=0;
   return OK;
 }

 int ListLength(SqList L)
 { 									// 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 
   return L.length;
 }

  Status ListInsert(SqList *L,int i,ElemType e) // 算法2.4 
 { // 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 
   // 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 
   ElemType *newbase,*q,*p;
   if(i<1||i>(*L).length+1) 		// i值不合法 
     return ERROR;
   if((*L).length>=(*L).listsize) 	// 当前存储空间已满,增加分配 
   {
     newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
     if(!newbase)
       exit(OVERFLOW); 				// 存储分配失败 
     (*L).elem=newbase; 			// 新基址 
     (*L).listsize+=LISTINCREMENT; // 增加存储容量 
   }
   q=(*L).elem+i-1; 				// q为插入位置 
   for(p=(*L).elem+(*L).length-1;p>=q;--p) // 插入位置及之后的元素右移 
     *(p+1)=*p;
   *q=e; 							// 插入e 
   ++(*L).length; 					// 表长增1 
   return OK;
 }
 Status ListTraverse(SqList L,void(*vi)(ElemType*))
 { /* 初始条件：顺序线性表L已存在 
    操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败 
    vi()的形参加'&'，表明可通过调用vi()改变元素的值 */
   ElemType *p;
   int i;
   p=L.elem;
   for(i=1;i<=L.length;i++)
     vi(p++);
   printf("\n");
   return OK;
 }
 
 
 
 /* 逆置链表的程序 */
 
 void change(SqList *L) /* 逆置算法 */
 {
   ElemType e;
   int L_len;
   int i;
   L_len=ListLength(*L); /* 求线性表的长度 */
   for(i=0;i<=L_len/2;i++)
   {
		e=*((*L).elem+i);
		*((*L).elem+i)=*((*L).elem+L_len-i-1);
		*((*L).elem+L_len-i-1)=e;
   }
 }

 void print(ElemType *c)
 {
   printf("%d ",*c);
 }

 main()
 {
   SqList L;
   Status i;
   ElemType e;
   int j;
   i=InitList(&L);
   if(i==1)
   {/* 创建空表L成功 */
	   printf("请输入5个数字：");
	   for(j=1;j<=5;j++)
	   {
		   scanf("%d",&e);
		   i=ListInsert(&L,j,e);
	   }
   }
   printf("逆置前的表：L= "); /* 输出表L的内容 */
   ListTraverse(L,print);
   change(&L);
   printf("逆置后的表：L= "); /* 输出新表L的内容 */
   ListTraverse(L,print);
 }