sqlist.cpp

这是我用VC编写的一些数据结构程序

/* 2005-03-04   -------------------------------------------------------
  实验内容：
	  编写程序建立顺序存储的线性表L，其数据元素按非递减有序排列，插入一个
	  元素X后，该线性表L仍保持有序。
  实验要求：
	  L的存储结构为：
	  #define LIST_INIT_SIZE 100  // 顺序表存储空间的初分配量
	  #define LISTINCREMENT  10   // 顺序表存储空间的分配增量	  
		struct   //线性表的结构
		{
			int *elem;    //存储空间的基地址
			int length;   //当前的长度
			int listsize; //当前分配的容量
		};
  测试数据：
      建立： 1,3,5,7,9
	  插入： x=-1,6,10  
-----------------------------------------------------------------------*/		

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<string.h>

#define LIST_INIT_SIZE 100  // 顺序表存储空间的初分配量
#define LISTINCREMENT  10   // 顺序表存储空间的分配增量

typedef struct   //线性表的结构
{
	int *elem;    //存储空间的基地址
	int length;   //当前的长度
	int listsize; //当前分配的容量
}SQLIST;


void Create(SQLIST &L)      //建立线性表
{
	L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int));
	if(!L.elem)
		printf("为线性表分配空间失败!");

	L.length =0;
	L.listsize =LIST_INIT_SIZE;
}

 
void Insert(SQLIST &A,int x)     //实现有序的插入操作
{
	if(A.length ==A.listsize) printf("线性表错误!");

	if(x > A.elem[A.length-1])
		A.elem[A.length]=x;   //与最大的元素进行判断，以决定是否插在最后
	else
	{
		int i=0;
		while(x >= A.elem[i]) 
			i++;   //从第一个元素起，寻找正确的插入位置

		for(int j=A.length; j>=i; j--)
			A.elem[j+1]=A.elem[j];  //将所找位置后面的所有数据都向右移动一个位置

		A.elem[i]=x;  //插入新的数据
	}
	A.length++; //顺序表的长度加1
}

void main()
{
	printf("程序说明:\n");
	printf("    建立顺序存储的单链表，其数据元素按元素值非递减有序排列，插入一个数据元素后，该线性表仍保持有序\n\n");

	SQLIST s;
	Create(s);    //为线性表分配空间

	s.elem[0]=1;  //建表
	s.elem[1]=3;
	s.elem[2]=5;
	s.elem[3]=7;
	s.elem[4]=9;
	s.length=5;
	printf("\n\n已建立的顺序表为：\n");
	for(int i=0; i<s.length; i++)
		printf("%d ",s.elem[i]);


	printf("\n\n请输入要插入的数据:\n ");
	int tmp;
	scanf("%d",&tmp);
	
	Insert(s,tmp);
  
	printf("\n\n插入数据后的顺序表为：\n");
	for(i=0; i<s.length; i++)
		printf("%d ",s.elem[i]);

	_getch(); //如果不加如该句，则执行用Visual C++编译后的exe文件，控制台窗口会一闪而过，看不请执行结果:)
}