sunxulist.c

数据结构线性表源代码

/*线性表的顺序存储操作， 线性表的逻辑顺序与存储的物理顺序相同*/
#include <stdio.h>
#include <string.h>

/*初始分配量*/
#define LIST_INIT_SIZE 15
/*分配增量*/
#define LIST_INCREMENT 10
typedef int ElemType;

struct Sqlist
{
	/*用指针代替数组，这里是存储基址，存储的开始的物理地址*/
	ElemType *elem;
	int length;
	int listsize;
};

/*线性表的初始化*/
int InitList(struct Sqlist* lst)
{
	lst->elem = (int*)malloc( (LIST_INIT_SIZE) * (sizeof(ElemType)));
	/*先分配出空间的初始分配量*/
	
	/*分配失败*/
	if( lst->elem == NULL )
	{
		printf("Error: init list and malloc error");
		return -1;
	}

	/*当前长度*/
	lst->length = 0;

	/*初始分配容量*/
	lst->listsize = LIST_INIT_SIZE;
	printf("init success: init list and malloc success\n");

	return 0;
}

/*扩展空间*/

int AgainMalloc(struct Sqlist *lst)
{
	if(lst->length >= lst->listsize)
	{
		/*可以用原来的基地址直接相加*/
		lst->elem = malloc( (lst->listsize + LIST_INCREMENT) * sizeof(ElemType));
		
				if(lst->elem == NULL)
				{
					return -1;
				}
		
	}

	lst->listsize += LIST_INCREMENT;

	return 0;

}
/*打印线性表*/
int PrintList( struct Sqlist *lst)
{
	int i;
	printf("打印线性表\n");
	printf("线性表的长度为：%d\n", lst->length);
	for( i= 0; i<= lst->length-1; i++)
	{
		printf(" %d\n", *(lst->elem + i));
	}
}

/*向线性表表头插入元素elem,切记插入时候首先检查空间是否够用 */
int InsertFirstlist( struct Sqlist* lst, ElemType e)
{
	int i, flag;

	/*判断线性表是否拥有空间, 如果长度和分配空间相同，则要增加空间，一次增加LISTINCREMENT个空间*/
	flag = AgainMalloc(lst);
	if(flag != 0)
	{
		printf("Increase mem error\n");
		return -1;
	}

	/*线性表后移, 只有当lst->length -1 >=0 时， 才会向后移动；即元素为1时，才会向后移动*/
	for( i= lst->length-1; i>=0; i--)
	{
		*(lst->elem+i+1) = *(lst->elem+i);

	}
	*(lst->elem) = e;

	/*插入完成后，改变线性表的长度*/
	lst->length = lst->length+1;

	return 0;

}

/*在顺序表的最后插入元素e*/
int InsertLastList(struct Sqlist *lst, ElemType e)
{
	int len, flag;
	
	/*如果空间不够，扩展空间*/
	flag = AgainMalloc(lst);
		if(flag != 0)
		{
			printf("Increase mem error\n");
			return -1;
		}

	/*顺序表的长度*/
	len = lst->length;

	/*最后一个元素 *(lst->elem+len-1)为插入之前的最后一个元素*/
	*(lst->elem+len) = e;
	(lst->length)++;
}

/*向线性表的某个位置插入一个元素*/
int InsertLocList(struct Sqlist *lst, int at, ElemType e)
{
	/*在顺序表的第at 位置之前插入一个元素e ；第 at 位置相当于*（elem+at-1);*/

	int i;

	/*错误检查， 检查 at 位置， 1<= at<= lst->length+1 */
	if(at <1 || at > (lst->length +1))
	{
		printf("插入位置不对");
		return -1;
	}
	for(i = lst->length; i>= at; i--)
	{
		/* 切记*（elem+i-1) 原来顺序表的最后一个元素*/
		*(lst->elem+i)= *(lst->elem + i-1);
	}
	*((lst->elem)+at-1) = e;
	lst->length++;

	return 0;
}

/*向有序线性表插入一个元素，使插入后仍然有序*/
int InsertOrderList(struct Sqlist *lst, ElemType e)
{
	int i =0;
	int j, k;

	/*如果线性表空进不够， 则再次分配空间*/
	AgainMalloc(lst);
	while( i < lst->length)
	{
		/*找到插入位置*/
		if( *(lst->elem+i) > e)
		{
			j= i;

			/*后移线性表*/
			for(k= lst->length-1; k>=j; k--)
			{
				*(lst->elem+k+1) = *(lst->elem+k);
				
			}
			
			*(lst->elem+j) = e;
		/*改变线性表的长度*/
		lst->length++;
			break;
		
		}
		i++;

	}
	return 0;
}

/*对线性表进行排序，使其递增排列*/
/* 编写程序时，如果拿不准可以举个简单的例子， 然后决定j, i 的大小*/
int ReOrderList( struct Sqlist *lst)
{
	/*使用直接插入排序 , 注意此处的线性表没有 "哨兵"*/
	int i, j,k;
	int temp;
	
	/*线性表从0开始，没有监视哨*/
	for( i=1; i<=lst->length-1; i++)
	{
		if ( *(lst->elem+i) < *(lst->elem+i-1) )
		{
			/* 那么要把第i个元素插入到之前i-1 各有序表中 ,否则此元素位置不变*/
			/*利用别的辅助空间，充当哨兵保存值*/
			temp = *(lst->elem+i);
			j=i;

			/*记录后移，直到发现插入位置*/
			do{
				*(lst->elem+j) = *(lst->elem+j-1);
				j--;



			}while( *(lst->elem+j-1) > temp && j >= 1);/*注意while 的条件*/

			/*记录要插入的位置*/
			*(lst->elem+j) = temp;
	
		}

	}
}

/*下面是删除线性表的操作*/
/**--------------------------------------->>>>>>>----------------**/

/*删除线性表一个元素 并返回它，从表头开始删除一个元素*/
ElemType DeleteFirstList(struct Sqlist *lst)
{
	ElemType e;
	if(lst->length <= 0)
	{
		printf("DeleteFirstlist error: the list is empty");
		exit(1);
	}
	if( lst->length > 0)
	{
		
		e = *(lst->elem);
		lst->elem++;
		lst->length--;
		return e;
	}

}

ElemType DeleteFirstList2( struct Sqlist *lst)
{
	ElemType temp;
    int i;
    if(lst->length == 0){
        printf("线性表为空，不能进行删除操作！ ");
        exit(1);
    }
    temp = lst->elem[0];
    for(i = 1; i < lst->length; i++)
       lst->elem[i-1] = lst->elem[i];
    lst->length--;
    return temp;
	
}

/* 从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */
ElemType DeleteLastList1( struct Sqlist *lst)
{
	ElemType e;
	
	/*如果线性表长度为0 */
	if( lst->length <= 0 )
	{
		printf("DeletLastList Error: the list is empty\n");
		exit(1);
	}

	/*取元素的最后一个值*/
	e = *( lst->elem + lst->length-1);
	/*线性表的长度减去1 */
	lst->length--;
		return e;
}

ElemType DeleteLastList2( struct Sqlist *lst)
{
	if(lst->length == 0){
        printf("线性表为空，不能进行删除操作！ ");
        exit(1);
    }
    lst->length--;
    return lst->elem[lst->length];        /* 返回原来表尾元素的值 */
	
}
/*从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */
ElemType DeletePosList( struct Sqlist *lst, int pos)
{
	int i;
	ElemType data;

	/* 若pos越界则退出运行 */
	if(pos < 1 || pos > lst->length)
	{    
        printf("元素序号越界！ ");
        exit(1);
    }
    
	
	/*保存要删除的元素*/
	data = lst->elem[pos-1];

	/*后面的位置向前移动*/
	for(i= pos-1; i< lst->length-1; i++)
	{
		lst->elem[i] = lst->elem[i+1];
	}
	lst->length--;
	return data;

}

/* 从线性表中删除值为x的第一个元素，若成功返回0，失败返回-1 */
int DeleteValue(struct Sqlist *lst, ElemType x)
{
	int i,j;
	/*如果线性表长度为0，退出程序*/
	if( lst->length <= 0 )
	{
		printf("The list is empty!");
		exit(-1);
	}

	/*如果相等，则删除此元素*/
	for( i=0;i<lst->length; i++)
	{
		if(lst->elem[i] == x)
		{
			for( j=i; j<lst->length; j++)
			{
				lst->elem[j] = lst->elem[j+1];
			}

			/*线性表长度减一*/
			lst->length--;
			break;


		}
		
	}

	
	
}

/*返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 */
ElemType GetPosValue(struct Sqlist *lst, int pos)
{
	ElemType data;
	/*判断程序异常*/
	if(pos < 1 || pos >= (lst->length) )
	{
		printf("GetPosValue Error");
		return;
	}

	data = lst->elem[pos-1];
	return data;
	/*或者直接用 return lst->elem[pos-1]*/

	
}

/* 判断线性表L是否为空，若为空则返回1, 否则返回0 */
int IsEmpty( struct Sqlist *lst)
{
	if(lst->length <= 0)
	{
		printf("The list is empty!");
		return 0;
	}
	else
	{
		if( lst->length > 0)
		{
			printf("The list is not empty!\n");
			return 1;
		}
	}
}


/**---------------------------------------<<<<<<<<----------------**/
/*主程序*/

void main()

{
	/*声明一个顺序表变量*/
	struct Sqlist seqlist;
	struct Sqlist reorderlist;
	int flag,i;
	int a[20] = {25, 12, 14, 9, 5, 1, 20, 18,56,23,13,22,24,26,27,29,55,66,123,232};
	int lastb[5] = {101, 106, 111, 105,100};
	int atc[5] ={3000, 6000, 9000, 12000, 15000};
	int orderint[4]= {10, 5,20, 8};

	ElemType elemvalue;
	

	/* 初始化顺序表*/
	flag = InitList(&seqlist);
	if(flag)
	{
		printf("Error: Init list error");
	}

   /*向线性表表头插入元素*/
    
	printf("main: InsertFirstlist\n");
    for(i =0; i<=19; i++)
	{
		InsertFirstlist(&seqlist, a[i]);
	}

	PrintList(&seqlist);

	/*在顺序表的最后插入5个元素*/
	for( i=0; i<5; i++)
		{
			InsertLastList(&seqlist, lastb[i]);
		}

	PrintList(&seqlist);

	/*在顺序表每隔两个元素插入一个元素*/
	for(i=0; i<5; i++)
	{
		InsertLocList(&seqlist, 3*(i+1), atc[i]);

	}
	PrintList(&seqlist);

	/*对顺序表进行排序*/
	ReOrderList(&seqlist);

	PrintList(&seqlist);
			
	/*在有序表插入一个元素 数值为3100，使之仍然有顺序*/
	InsertOrderList(&seqlist, 3100);
	PrintList(&seqlist);

	/*删除线性表的表头，并返回元素*/
	elemvalue = DeleteFirstList(&seqlist);
	printf("删除的第一个元素为：%d\n", elemvalue);

	PrintList(&seqlist);

	elemvalue = DeleteFirstList2(&seqlist);
	printf("删除的第一个元素为：%d\n", elemvalue);
	
	PrintList(&seqlist);

	/*删除线性表的最后一个元素，并返回元素的值*/
	
	elemvalue = DeleteLastList1(&seqlist);
	printf("删除的最后一个元素为：%d\n", elemvalue);
	PrintList(&seqlist);

	elemvalue = DeleteLastList2(&seqlist);
	printf("删除的最后一个元素为：%d\n", elemvalue);
	PrintList(&seqlist);

	/*删除指定位置的元素, 比如删除第10个元素*/
	elemvalue = DeletePosList(&seqlist, 10);
	printf("删除的第10个元素为：%d\n", elemvalue);
	PrintList(&seqlist);

	/*像数组那样显示线性表的第一个元素*/
	printf("the list the first data is:%d", seqlist.elem[0]);

	/*删除线性表中与给定值相等的元素*/
	printf("删除线性表中与给定元素值相同的元素: 3100 \n");
	flag = DeleteValue(&seqlist, 3100);
	if(flag == -1)
	{
		printf("DeleteValue Error");
		return;
	}
	PrintList(&seqlist);

	/*获得线性表制定位置的数值 ，现在不放获得第 5 个元素的值*/
	elemvalue = GetPosValue(&seqlist, 5);
	printf("第5个元素的值为：%d\n", elemvalue);

	/*判断线性表是否为空*/
	flag = IsEmpty(&seqlist);
	

	
    return;
    


}



/*下面注释掉的部分是为了验证 排序程序*/
/*
int main()
{
	int i, flag;
	struct Sqlist reorderlist;
	int orderint[5]= {10,5,20,8,12};
	/ *初始化顺序表* /
		flag = InitList(&reorderlist);
	if(flag)
	{
		printf("Error: Init list error");
	}
	
	/ *对线性表进行排序* /
	printf("检查对顺序表的排序");
	for( i=0; i<5; i++)
	{
		InsertLastList(&reorderlist, orderint[i]);
	}
	ReOrderList(&reorderlist);
	PrintList(&reorderlist);
	return 0;
}*/