第一章——线性表（顺序表和链表）

再度回顾基础内容。为数据结构打下扎实基础。

---

实验内容：

顺序表：

建立一个顺序表，实现遍历，增删改查的操作。

链表：

建立一个单链表，使其有序完成遍历，增删改查的操作。

顺序表的思路就不说了，无非就是数组；

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct node{
	int MAX_SIZE;//最大容量 
	int *Data;//数组 
	int SIZE;//当前大小 
}List;

//create
int CreateList(List &L,int N)
{

	if(N<=0){
		printf("ERROR!");
		return 0;
	}
	L.MAX_SIZE=N;
	L.Data=(int*)malloc(sizeof(int)*N);//maxsize 申请空间
	L.SIZE=0;//初始大小 
	printf("CREATE_OK\n");
	return 1;
}
//For_Each
void forEach(List *L){
	if(L->SIZE<=0){
		printf("NO_DATA!\n");
		return;
	}
	printf("***\n");
	printf("当前的容器大小:%d\n",L->SIZE);
	int i;
	for(i=0;i<L->SIZE;i++){
		printf("%d:%d ",i,L->Data[i]);
	}
	printf("\n***\n");
}
//find
int FindIndex(List *L,int value){
	int i;
	for(i=0;i<L->SIZE;i++){
		if(L->Data[i]==value){
			return i;
		}
	}
	printf("FIND_ERROR");
	return -1;//未找到 
}
//add
int insert(List *L,int index,int value)
{
	if(index<0||index>L->MAX_SIZE){
		printf("INSERT_ERROR!");
		return 0;
	}
	//开始插入
	int i;
	for(i=L->SIZE;i>index;i--){
		L->Data[i+1]=L->Data[i];//往后挪 
	} 
	L->Data[index]=value;
	L->SIZE++;
	printf("INSERT_OK\n");
	return 1;
}
//delete
int Delete(List *L,int index){
	if(index<0||index>L->SIZE){
		printf("DELETE_ERROR!");
		return 0;
	}
	int i;//保存该数据
	 for(i=index;i<L->SIZE;i++){
	 	L->Data[i]=L->Data[i+1];
	 }
	 L->SIZE--;
	 printf("Delete_OK");
	 return 1;
}
int main(){
	List L;
	int N,index,value;
	
	printf("主菜单\n");
	start:
	printf("\n请输入对应索引进行相应的操作\n");
	printf("输入1建立一个新的顺序表\n");
	printf("输入2为顺序表插入数据\n");
	printf("输入3遍历该顺序表\n");
	printf("输入4查找顺序表中的元素\n");
	printf("输入5删除顺序表中某一个元素\n");
	printf("输入-1退出\n");
	int ret,i,Ran;
	srand(time(NULL));
	scanf("%d",&ret);
	while(1){
		switch(ret){
		case 1:
			printf("输入表的容量\n");
			scanf("%d",&N);
			CreateList(L,N);
			
			for(i=0;i<N/2;i++){
				Ran=rand()%99;
				insert(&L,i,Ran);
			}
			goto start;
		case 2:
			printf("请分别输入要插入的位置以及要插入的数据\n");
			scanf("%d %d",&index,&value); 
			insert(&L,index,value);
			goto start;
		case 3:
			forEach(&L);
			goto start;
		case 4:
			printf("请输入要查找的数据,我将返回一个索引给你\n");
			scanf("%d",&value);
			printf("查找位置:&d\n",FindIndex(&L,value)); 
			goto start;
		case 5:
			printf("请输入要删除数据的位置\n");
			scanf("%d",&index);
			Delete(&L,index);
			goto start;	
		case -1:
			goto end;	
	}
	}
	end:
	return 0;
}

链表：

链表的排序：我这里用了两种排序方式，第一种是直接对链表进行冒泡排序，思路是和数组一样的。使用两个指针代替了数组的下标。第二种是将链表打包成一个数组，再对数组进行快排。最后装回链表。事先上网查过，还是第二种的速度快一点；自己通过测试也证实如此。

 

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int length;//当前大小 
typedef struct node{
	int data;//数据域 	
	struct node *next;//指针域 
}LinkList;
//排序1 直接链表实现冒泡排序 
void Sort1(LinkList *L){
	LinkList *i,*j;//充当i j下标 
	//冒泡排序 
	i=j=L;
	while( i != NULL){
		while( j != i ){
			if(j->data > i->data){
				int t =j->data;
				j->data=i->data;
				i->data=t;
			}
			j = j->next;
		}
		j=L; //归0 
		i = i->next;
	}
} 
void Qsort(int left,int right,int a[]){
	if(left>=right){//递归出口 
		return;
	}
	int temp=a[left];//做好标兵 
	int i=left,j=right;
	while(i<j){
		//从右边开始检查起 
		while(temp<a[j]&&j>i){
			j--;
		}
		if(temp>=a[j]&&j>i){
			int t=a[j];
			a[j]=a[i];
			a[i]=t;
			i++;
		}
		while(temp>a[i]&&j>i){
			i++;
		}
		if(temp<a[i]&&j>i){
			int t=a[i];
			a[i]=a[j];
			a[j]=t;
			j--;
		}
	}
	//出来的时候i=j
	a[j]=temp;//在这里左边比他小 右边比他大
	Qsort(left,i-1,a);
	Qsort(i+1,right,a); 
}
//排序2 用数组把链表的数据装好再使用快速排序 
void Sort2(LinkList *L){
	int nums[length+1];//使用数组把链表数据装进来排序
	int left=0,right=length-1,i=0;
	LinkList *t=L;
	while(t){
		nums[i++]=t->data;
		t=t->next;
	} 
	Qsort(left,right,nums);//进行快速排序
	t=L;
	for(i=0;i<length&&t!=NULL;i++){
		t->data=nums[i];
		t=t->next;
	}
}
//forEach 
void ForEach(LinkList *L){
	printf("***\n");
	LinkList *t;
	t=L;
	while(t){
		printf("%d ",t->data);
		t=t->next;
	} 
	printf("\n***\n");
}
//创建 
LinkList *Create()
{
	srand(time(NULL));
	LinkList *head,*node,*tail,*Thead;
	head=tail=NULL;
	int i,Ran;
	//随机产生5个元素 
	for(i=0;i<5;i++){ 				
		Ran=rand();
		node=(LinkList*)malloc(sizeof(LinkList));
		node->data=Ran%999;
		node->next=NULL;
		if(head==NULL){
			head=node;
		}
		else {
			tail->next=node;
			if(tail->data < head->data){
				int x=head->data;
				head->data =tail->data;
				tail->data=x;
			}
		}
		tail=node;
	}
	length=5;
	return head;
}
//插入新数据 
void insert(LinkList *L,int value) {
	length++;
	LinkList *t=L,*node;
	while(t->next){
		t=t->next;
	}
	node=(LinkList*)malloc(sizeof(LinkList));
	node->data=value;
	node->next=NULL;
	t->next=node;//接在尾部 
	
	Sort2(L);	
}
void Delete(LinkList **L,int value){
	LinkList *t=*L;
	int FLAG=0;
	if((*L)->data==value){
		(*L)=(*L)->next;
		length--;
		free(t);
		printf("删除成功!\n");
		return ;
	}
	while(t->next)
	{
		if(t->next->data==value){
			LinkList *p=t->next;
			length--;
			LinkList *node=t->next->next;
			t->next=node;
			free(p);
			printf("删除成功!\n");
			break;
		}
		t=t->next;
	}
	if(!FLAG){
		printf("你要删除的元素不存在!\n");
		return;
	}
	
} 


int main(){
	printf("主菜单\n");
	start:
	printf("\n请输入对应索引进行相应的操作\n");
	printf("输入1我将自动为你生成一个含有5个数据的链表\n");
	printf("输入2为顺序表插入数据\n");
	printf("输入3遍历该顺序表\n");
	printf("输入4删除顺序表中某一个元素\n");
	printf("输入-1退出\n");
	int ret,value;
	scanf("%d",&ret);
	LinkList *head;
	while(1){
		switch(ret){
		case 1:
			head=Create();
			printf("创建成功!");
			goto start;
		case 2:
			printf("请输入要插入的数据\n");
			scanf("%d",&value); 
			insert(head,value);
			goto start;
		case 3:
			ForEach(head);
			goto start;
		case 4:
			printf("请输入要删除数据的\n");
			scanf("%d",&value);
			Delete(&head,value);
			goto start;	
		case -1:
			goto end;	
	}
	}
	end:
	return 0;
}