数据结构 / day03作业

1.顺序表按元素删除

//main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	sqlist *list=create_space();
	// printf("&list=%pn", list);

	int n;
	int index;
	data_type element, key;

	printf("please input n;");
	scanf("%d", &n);
	

	for(int i=0; i<n; i++)
	{
		printf("please input %d element:n", i+1);
		scanf("%d", &element);
		int flag = append(list, element);
		//printf("main-->flag=%dn", flag);
		if(flag==-1)
		{
			puts("list full or errorn");

			break;
		}
	}

	puts("---output inputed list---n");
	//printf("output inputed listn");	
	output(list);
	putchar(10);
	/*

	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");
	
	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");

	puts("------");
	printf("output list after deleten");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	search_by_index(list, 1);

	puts("------");
	update(list, 1, 99);
	printf("element 1 has been updatedn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	insert(list, 1, 100);
	printf("postion 1 insrerted an elementn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	printf("please input index for deleting:");
	scanf("%d", &index);
	delete_by_index(list, index);
	printf("postion %d element has been deletedn", index);
	output(list);

	
	puts("---update by element---");
	printf("please input key for updating:");
	scanf("%d", &key);
	printf("please input  element for updating:");
	scanf("%d", &element);
	int ret = update_by_element(list, key, element);
	if(ret==-1)
	{
	
		printf("key %d is not found or other errorn", key );
	}
	else
	{
		printf("element %d has been updated to %d at pos %dn",key, element, ret );
	}

	output(list); */

	puts("---delete by element---");
	printf("please input element to delete:");
	scanf("%d", &element);
	int ret = delete_by_element(list, element);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		printf("element %d has been deletedn", element);
	}

	output(list);




	return 0;
}

//head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


//顺序表结构体
#define MAXSIZE 20

typedef int data_type;

typedef struct
{
	//数据元素
	data_type data[MAXSIZE];

	//顺序表长度
	int len;

}sqlist; // SQLIST --> sqlist

sqlist *create_space();
int full_sqlist(sqlist*list);
int append(sqlist *list, data_type element);
int delete_tail(sqlist *list);
void output(sqlist *list);
int empty_sqlist(sqlist *list);
int insert(sqlist *list, int index, data_type element);
void search_by_index(sqlist *list, int index);
int index_out_of_range(sqlist *list, int index);
int update(sqlist *list, int index, data_type element);
int delete_by_index(sqlist *list, int index);
int search_by_element(sqlist *list, data_type element);
int update_by_element(sqlist *list, data_type key, data_type element );
int delete_by_element(sqlist *list, data_type element );

#endif
//test.c

#include "head.h"


sqlist *create_space()
{
	sqlist *list = (sqlist*)malloc(sizeof(sqlist));
	if(NULL==list)
	{
		puts("error");
		return NULL;
	}

	list->len=0; //顺序表初始化长度清0

	//数据清0
	memset(list->data, 0, sizeof(list->data));
	return list;
}

int full_sqlist(sqlist*list)
{
	int flag = list->len==MAXSIZE;
	//printf("full_list-->flag=%dn", flag);
	return flag;
}

int empty_sqlist(sqlist *list)
{
	if(list->len==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int append(sqlist *list, data_type element)
{

	// printf("list=%pn", list);   
	if(NULL==list || full_sqlist(list))
	{   
		return -1; 

	}   

	list->data[list->len++]=element;
	return 0;

	//  

}     

void output(sqlist *list)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return;

	}

	for(int i=0; i<list->len; i++)
	{
		printf("%dt", list->data[i]);
	}
	putchar(10);

}

int delete_tail(sqlist *list)
{	
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return -1;
	}


	list->len--;
	//不可以释放空间
	return 0;



}

int insert(sqlist *list, int index, data_type element)
{
	if(NULL==list || full_sqlist(list)||index>list->len||index<0 )
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=list->len-1; i>=index; i--)
	{
		list->data[i+1] = list->data[i];
	}
	list->data[index]=element;
	list->len++;
	return 0;

}

int index_out_of_range(sqlist *list, int index)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULL or empty!");
		return -1;
	}

	if(index<0||index>=list->len)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

void search_by_index(sqlist *list, int index)
{
	if(NULL==list||index_out_of_range(list, index)||empty_sqlist(list))
	{
		printf("list is NULL or index out of range");
		return;
	}

	data_type element = list->data[index];
	printf("found element:%dn", element);



}


int update(sqlist *list, int index, data_type element)
{
	if(NULL==list||empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or empty or index errorn");
		return -1;
	}

	list->data[index] = element;
	return 0;

}

int delete_by_index(sqlist *list, int index)
{
	if(NULL==list || empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=index; i<list->len-1; i++)
	{
		list->data[i] = list->data[i+1];
	}


	list->len--;
	return 0;
}

int rm_duplicate(sqlist *list)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}

}

int search_by_element(sqlist *list, data_type element)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	for(int i=0; i<list->len; i++)
	{
		if(element==list->data[i])
		{
			return i;
		}

	}
	return -1;
}

int update_by_element(sqlist *list, data_type key, data_type element )
{
	int found=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return found;
	}


	for(int i=0; i<list->len; i++)
	{
		if(key==list->data[i])
		{
			list->data[i] = element;
			found=i;
		}

	}
		return found;
}

int delete_by_element(sqlist *list, data_type element )
{


	int flag=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return flag;
	}

	int idx=search_by_element(list, element);
	if(idx==-1)
	{
		return -1;
	}

	int ret=delete_by_index(list, idx);
	return ret;

}

2 顺序表按元素修改

//main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	sqlist *list=create_space();
	// printf("&list=%pn", list);

	int n;
	int index;
	data_type element, key;

	printf("please input n;");
	scanf("%d", &n);
	

	for(int i=0; i<n; i++)
	{
		printf("please input %d element:n", i+1);
		scanf("%d", &element);
		int flag = append(list, element);
		//printf("main-->flag=%dn", flag);
		if(flag==-1)
		{
			puts("list full or errorn");

			break;
		}
	}

	puts("---output inputed list---n");
	//printf("output inputed listn");	
	output(list);
	/*

	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");
	
	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");

	puts("------");
	printf("output list after deleten");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	search_by_index(list, 1);

	puts("------");
	update(list, 1, 99);
	printf("element 1 has been updatedn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	insert(list, 1, 100);
	printf("postion 1 insrerted an elementn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	printf("please input index for deleting:");
	scanf("%d", &index);
	delete_by_index(list, index);
	printf("postion %d element has been deletedn", index);
	output(list);
*/	
	
	puts("---update by element---");
	printf("please input key for updating:");
	scanf("%d", &key);
	printf("please input  element for updating:");
	scanf("%d", &element);
	int ret = update_by_element(list, key, element);
	if(ret==-1)
	{
	
		printf("key %d is not found or other errorn", key );
	}
	else
	{
		printf("element %d has been updated to %d at pos %dn",key, element, ret );
	}

	output(list);



	return 0;
}
// head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


//顺序表结构体
#define MAXSIZE 20

typedef int data_type;

typedef struct
{
	//数据元素
	data_type data[MAXSIZE];

	//顺序表长度
	int len;

}sqlist; // SQLIST --> sqlist

sqlist *create_space();
int full_sqlist(sqlist*list);
int append(sqlist *list, data_type element);
int delete_tail(sqlist *list);
void output(sqlist *list);
int empty_sqlist(sqlist *list);
int insert(sqlist *list, int index, data_type element);
void search_by_index(sqlist *list, int index);
int index_out_of_range(sqlist *list, int index);
int update(sqlist *list, int index, data_type element);
int delete_by_index(sqlist *list, int index);
int search_by_element(sqlist *list, data_type element);
int update_by_element(sqlist *list, data_type key, data_type element );


#endif
// test.c

#include "head.h"


sqlist *create_space()
{
	sqlist *list = (sqlist*)malloc(sizeof(sqlist));
	if(NULL==list)
	{
		puts("error");
		return NULL;
	}

	list->len=0; //顺序表初始化长度清0

	//数据清0
	memset(list->data, 0, sizeof(list->data));
	return list;
}

int full_sqlist(sqlist*list)
{
	int flag = list->len==MAXSIZE;
	//printf("full_list-->flag=%dn", flag);
	return flag;
}

int empty_sqlist(sqlist *list)
{
	if(list->len==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int append(sqlist *list, data_type element)
{

	// printf("list=%pn", list);   
	if(NULL==list || full_sqlist(list))
	{   
		return -1; 

	}   

	list->data[list->len++]=element;
	return 0;

	//  

}     

void output(sqlist *list)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return;

	}

	for(int i=0; i<list->len; i++)
	{
		printf("%dt", list->data[i]);
	}
	putchar(10);

}

int delete_tail(sqlist *list)
{	
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return -1;
	}


	list->len--;
	//不可以释放空间
	return 0;



}

int insert(sqlist *list, int index, data_type element)
{
	if(NULL==list || full_sqlist(list)||index>list->len||index<0 )
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=list->len-1; i>=index; i--)
	{
		list->data[i+1] = list->data[i];
	}
	list->data[index]=element;
	list->len++;
	return 0;

}

int index_out_of_range(sqlist *list, int index)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULL or empty!");
		return -1;
	}

	if(index<0||index>=list->len)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

void search_by_index(sqlist *list, int index)
{
	if(NULL==list||index_out_of_range(list, index)||empty_sqlist(list))
	{
		printf("list is NULL or index out of range");
		return;
	}

	data_type element = list->data[index];
	printf("found element:%dn", element);



}


int update(sqlist *list, int index, data_type element)
{
	if(NULL==list||empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or empty or index errorn");
		return -1;
	}

	list->data[index] = element;
	return 0;

}

int delete_by_index(sqlist *list, int index)
{
	if(NULL==list || empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=index; i<list->len-1; i++)
	{
		list->data[i] = list->data[i+1];
	}


	list->len--;
	return 0;
}

int rm_duplicate(sqlist *list)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}

}

int search_by_element(sqlist *list, data_type element)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	for(int i=0; i<list->len; i++)
	{
		if(element==list->data[i])
		{
			return i;
		}

	}
	return -1;
}

int update_by_element(sqlist *list, data_type key, data_type element )
{
	int found=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return found;
	}


	for(int i=0; i<list->len; i++)
	{
		if(key==list->data[i])
		{
			list->data[i] = element;
			found=i;
		}

	}
		return found;
}
please input n;5
please input 1 element:
1
please input 2 element:
2
please input 3 element:
3
please input 4 element:
4
please input 5 element:
5
---output inputed list---

1	2	3	4	5	
---update by element---
please input key for updating:3
please input  element for updating:7
element 3 has been updated to 7 at pos 2
1	2	7	4	5	

3. 顺序表去重

//main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	sqlist *list=create_space();
	// printf("&list=%pn", list);

	int n;
	int index;
	data_type element, key;

	printf("please input n;");
	scanf("%d", &n);
	

	for(int i=0; i<n; i++)
	{
		printf("please input %d element:n", i+1);
		scanf("%d", &element);
		int flag = append(list, element);
		//printf("main-->flag=%dn", flag);
		if(flag==-1)
		{
			puts("list full or errorn");

			break;
		}
	}

	puts("---output inputed list---n");
	//printf("output inputed listn");	
	output(list);
	putchar(10);
	/*

	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");
	
	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");

	puts("------");
	printf("output list after deleten");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	search_by_index(list, 1);

	puts("------");
	update(list, 1, 99);
	printf("element 1 has been updatedn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	insert(list, 1, 100);
	printf("postion 1 insrerted an elementn");
	printf("list len=%dn", list->len);
	output(list);

	puts("---delete by index---");
	printf("please input index for deleting:");
	scanf("%d", &index);
	delete_by_index(list, index);
	printf("postion %d element has been deletedn", index);
	output(list);

	
	puts("---update by element---");
	printf("please input key for updating:");
	scanf("%d", &key);
	printf("please input  element for updating:");
	scanf("%d", &element);
	int ret = update_by_element(list, key, element);
	if(ret==-1)
	{
	
		printf("key %d is not found or other errorn", key );
	}
	else
	{
		printf("element %d has been updated to %d at pos %dn",key, element, ret );
	}

	output(list); 

	puts("---delete by element---");
	printf("please input element to delete:");
	scanf("%d", &element);
	int ret = delete_by_element(list, element);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		printf("element %d has been deletedn", element);
	}

	output(list);
*/
	
	puts("---remove duplicate element---n");
	puts("> list before remove duplicate:n");
	output(list);
	int ret = rm_duplicate(list);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		puts("> list after remove duplicate:n");
		output(list);
	}





	return 0;
}
//head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


//顺序表结构体
#define MAXSIZE 20

typedef int data_type;

typedef struct
{
	//数据元素
	data_type data[MAXSIZE];

	//顺序表长度
	int len;

}sqlist; // SQLIST --> sqlist

sqlist *create_space();
int full_sqlist(sqlist*list);
int append(sqlist *list, data_type element);
int delete_tail(sqlist *list);
void output(sqlist *list);
int empty_sqlist(sqlist *list);
int insert(sqlist *list, int index, data_type element);
void search_by_index(sqlist *list, int index);
int index_out_of_range(sqlist *list, int index);
int update(sqlist *list, int index, data_type element);
int delete_by_index(sqlist *list, int index);
int search_by_element(sqlist *list, data_type element);
int update_by_element(sqlist *list, data_type key, data_type element );
int delete_by_element(sqlist *list, data_type element );
int rm_duplicate(sqlist *list);

#endif
//test.c

#include "head.h"


sqlist *create_space()
{
	sqlist *list = (sqlist*)malloc(sizeof(sqlist));
	if(NULL==list)
	{
		puts("error");
		return NULL;
	}

	list->len=0; //顺序表初始化长度清0

	//数据清0
	memset(list->data, 0, sizeof(list->data));
	return list;
}

int full_sqlist(sqlist*list)
{
	int flag = list->len==MAXSIZE;
	//printf("full_list-->flag=%dn", flag);
	return flag;
}

int empty_sqlist(sqlist *list)
{
	if(list->len==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int append(sqlist *list, data_type element)
{

	// printf("list=%pn", list);   
	if(NULL==list || full_sqlist(list))
	{   
		return -1; 

	}   

	list->data[list->len++]=element;
	return 0;

	//  

}     

void output(sqlist *list)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return;

	}

	for(int i=0; i<list->len; i++)
	{
		printf("%dt", list->data[i]);
	}
	putchar(10);

}

int delete_tail(sqlist *list)
{	
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return -1;
	}


	list->len--;
	//不可以释放空间
	return 0;



}

int insert(sqlist *list, int index, data_type element)
{
	if(NULL==list || full_sqlist(list)||index>list->len||index<0 )
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=list->len-1; i>=index; i--)
	{
		list->data[i+1] = list->data[i];
	}
	list->data[index]=element;
	list->len++;
	return 0;

}

int index_out_of_range(sqlist *list, int index)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULL or empty!");
		return -1;
	}

	if(index<0||index>=list->len)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

void search_by_index(sqlist *list, int index)
{
	if(NULL==list||index_out_of_range(list, index)||empty_sqlist(list))
	{
		printf("list is NULL or index out of range");
		return;
	}

	data_type element = list->data[index];
	printf("found element:%dn", element);



}


int update(sqlist *list, int index, data_type element)
{
	if(NULL==list||empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or empty or index errorn");
		return -1;
	}

	list->data[index] = element;
	return 0;

}

int delete_by_index(sqlist *list, int index)
{
	if(NULL==list || empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=index; i<list->len-1; i++)
	{
		list->data[i] = list->data[i+1];
	}


	list->len--;
	return 0;
}

int rm_duplicate(sqlist *list)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	
	for(int i=0; i<list->len-1; i++)
	{
		int cur=i;
		for(int j=i+1; j<list->len; j++)
		{
			if(list->data[cur]==list->data[j])
			{
				printf("list->len=%d, i=%d, j=%dn", list->len, i, j);
				delete_by_index(list, j);
				j--;
			
			}
		}
	}
	return 0;


}

int search_by_element(sqlist *list, data_type element)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	for(int i=0; i<list->len; i++)
	{
		if(element==list->data[i])
		{
			return i;
		}

	}
	return -1;
}

int update_by_element(sqlist *list, data_type key, data_type element )
{
	int found=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return found;
	}


	for(int i=0; i<list->len; i++)
	{
		if(key==list->data[i])
		{
			list->data[i] = element;
			found=i;
		}

	}
		return found;
}

int delete_by_element(sqlist *list, data_type element )
{


	int flag=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return flag;
	}

	int idx=search_by_element(list, element);
	if(idx==-1)
	{
		return -1;
	}

	int ret=delete_by_index(list, idx);
	return ret;

}

4. 顺序表有序合并

//main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	sqlist *list=create_space();
	// printf("&list=%pn", list);

	int n;
	int index;
	data_type element, key;
	/*
	printf("please input n;");
	scanf("%d", &n);
	

	for(int i=0; i<n; i++)
	{
		printf("please input %d element:n", i+1);
		scanf("%d", &element);
		int flag = append(list, element);
		//printf("main-->flag=%dn", flag);
		if(flag==-1)
		{
			puts("list full or errorn");

			break;
		}
	}

	puts("---output inputed list---n");
	//printf("output inputed listn");	
	output(list);
	putchar(10);


	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");
	
	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");

	puts("------");
	printf("output list after deleten");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	search_by_index(list, 1);

	puts("------");
	update(list, 1, 99);
	printf("element 1 has been updatedn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	insert(list, 1, 100);
	printf("postion 1 insrerted an elementn");
	printf("list len=%dn", list->len);
	output(list);

	puts("---delete by index---");
	printf("please input index for deleting:");
	scanf("%d", &index);
	delete_by_index(list, index);
	printf("postion %d element has been deletedn", index);
	output(list);

	
	puts("---update by element---");
	printf("please input key for updating:");
	scanf("%d", &key);
	printf("please input  element for updating:");
	scanf("%d", &element);
	int ret = update_by_element(list, key, element);
	if(ret==-1)
	{
	
		printf("key %d is not found or other errorn", key );
	}
	else
	{
		printf("element %d has been updated to %d at pos %dn",key, element, ret );
	}

	output(list); 

	puts("---delete by element---");
	printf("please input element to delete:");
	scanf("%d", &element);
	int ret = delete_by_element(list, element);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		printf("element %d has been deletedn", element);
	}

	output(list);
	
	puts("---remove duplicate element---n");
	puts("> list before remove duplicate:n");
	output(list);
	int ret = rm_duplicate(list);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		puts("> list after remove duplicate:n");
		output(list);
	}
*/
	puts("---combine 2 lists---n");

	sqlist *la=create_space();
	sqlist *lb=create_space();
	sqlist *lc=create_space();

	append(la, 11);
	append(la, 11);
	append(la, 17);
	append(la, 24);
	append(la, 45);

	append(lb, 13);
	append(lb, 16);
	append(lb, 16);
	append(lb, 36);
	append(lb, 45);
	append(lb, 62);

	puts(">list la:n");
	output(la);
	puts(">list lb:n");
	output(lb);

	combine(la, lb, lc);
	puts(">list lc after combine:n");
	output(lc);
	





	return 0;
}

//head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


//顺序表结构体
#define MAXSIZE 30

typedef int data_type;

typedef struct
{
	//数据元素
	data_type data[MAXSIZE];

	//顺序表长度
	int len;

}sqlist; // SQLIST --> sqlist

sqlist *create_space();
int full_sqlist(sqlist*list);
int append(sqlist *list, data_type element);
int delete_tail(sqlist *list);
void output(sqlist *list);
int empty_sqlist(sqlist *list);
int insert(sqlist *list, int index, data_type element);
void search_by_index(sqlist *list, int index);
int index_out_of_range(sqlist *list, int index);
int update(sqlist *list, int index, data_type element);
int delete_by_index(sqlist *list, int index);
int search_by_element(sqlist *list, data_type element);
int update_by_element(sqlist *list, data_type key, data_type element );
int delete_by_element(sqlist *list, data_type element );
int rm_duplicate(sqlist *list);
void combine(sqlist *la,sqlist*lb,sqlist*lc);

#endif

//test.c

#include "head.h"


sqlist *create_space()
{
	sqlist *list = (sqlist*)malloc(sizeof(sqlist));
	if(NULL==list)
	{
		puts("error");
		return NULL;
	}

	list->len=0; //顺序表初始化长度清0

	//数据清0
	memset(list->data, 0, sizeof(list->data));
	return list;
}

int full_sqlist(sqlist*list)
{
	int flag = list->len==MAXSIZE;
	//printf("full_list-->flag=%dn", flag);
	return flag;
}

int empty_sqlist(sqlist *list)
{
	if(list->len==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int append(sqlist *list, data_type element)
{

	// printf("list=%pn", list);   
	if(NULL==list || full_sqlist(list))
	{   
		return -1; 

	}   

	list->data[list->len++]=element;
	return 0;

	//  

}     

void output(sqlist *list)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return;

	}

	for(int i=0; i<list->len; i++)
	{
		printf("%dt", list->data[i]);
	}
	putchar(10);

}

int delete_tail(sqlist *list)
{	
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return -1;
	}


	list->len--;
	//不可以释放空间
	return 0;



}

int insert(sqlist *list, int index, data_type element)
{
	if(NULL==list || full_sqlist(list)||index>list->len||index<0 )
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=list->len-1; i>=index; i--)
	{
		list->data[i+1] = list->data[i];
	}
	list->data[index]=element;
	list->len++;
	return 0;

}

int index_out_of_range(sqlist *list, int index)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULL or empty!");
		return -1;
	}

	if(index<0||index>=list->len)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

void search_by_index(sqlist *list, int index)
{
	if(NULL==list||index_out_of_range(list, index)||empty_sqlist(list))
	{
		printf("list is NULL or index out of range");
		return;
	}

	data_type element = list->data[index];
	printf("found element:%dn", element);



}


int update(sqlist *list, int index, data_type element)
{
	if(NULL==list||empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or empty or index errorn");
		return -1;
	}

	list->data[index] = element;
	return 0;

}

int delete_by_index(sqlist *list, int index)
{
	if(NULL==list || empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=index; i<list->len-1; i++)
	{
		list->data[i] = list->data[i+1];
	}


	list->len--;
	return 0;
}

int rm_duplicate(sqlist *list)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	
	for(int i=0; i<list->len-1; i++)
	{
		int cur=i;
		for(int j=i+1; j<list->len; j++)
		{
			if(list->data[cur]==list->data[j])
			{
				printf("list->len=%d, i=%d, j=%dn", list->len, i, j);
				delete_by_index(list, j);
				j--;
			
			}
		}
	}
	return 0;


}

int search_by_element(sqlist *list, data_type element)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	for(int i=0; i<list->len; i++)
	{
		if(element==list->data[i])
		{
			return i;
		}

	}
	return -1;
}

int update_by_element(sqlist *list, data_type key, data_type element )
{
	int found=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return found;
	}


	for(int i=0; i<list->len; i++)
	{
		if(key==list->data[i])
		{
			list->data[i] = element;
			found=i;
		}

	}
		return found;
}

int delete_by_element(sqlist *list, data_type element )
{


	int flag=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return flag;
	}

	int idx=search_by_element(list, element);
	if(idx==-1)
	{
		return -1;
	}

	int ret=delete_by_index(list, idx);
	return ret;

}


void combine(sqlist *la,sqlist*lb,sqlist*lc)
{
    int p=0;
    int q=0;
    while(p<la->len && q<lb->len)
    {
        if(la->data[p] <=lb->data[q])
        {
            lc->data[lc->len++]=la->data[p++];
        }
        else
        {
            lc->data[lc->len++]=lb->data[q++];
            
        }
    }
    //把la剩余元素存到lc
    while(p<la->len)
    {
        lc->data[lc->len++]=la->data[p++];
        
    }
    //把lb剩余元素存到lc
    while(q<lb->len)
    {
        lc->data[lc->len++]=lb->data[q++];
        
    }
}

5 顺序表释放空间

//main.c

#include "head.h"
int main(int argc, const char *argv[])
{
	sqlist *list=create_space();
	// printf("&list=%pn", list);

	int n;
	int index;
	data_type element, key;
	printf("please input n;");
	scanf("%d", &n);
	

	for(int i=0; i<n; i++)
	{
		printf("please input %d element:n", i+1);
		scanf("%d", &element);
		int flag = append(list, element);
		//printf("main-->flag=%dn", flag);
		if(flag==-1)
		{
			puts("list full or errorn");

			break;
		}
	}


	puts("---output inputed list---n");
	//printf("output inputed listn");	
	output(list);
	putchar(10);
	/*


	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");
	
	puts("------");
	delete_tail(list);
	printf("the last element has been deletedn");

	puts("------");
	printf("output list after deleten");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	search_by_index(list, 1);

	puts("------");
	update(list, 1, 99);
	printf("element 1 has been updatedn");
	printf("list len=%dn", list->len);
	output(list);

	puts("------");
	insert(list, 1, 100);
	printf("postion 1 insrerted an elementn");
	printf("list len=%dn", list->len);
	output(list);

	puts("---delete by index---");
	printf("please input index for deleting:");
	scanf("%d", &index);
	delete_by_index(list, index);
	printf("postion %d element has been deletedn", index);
	output(list);

	
	puts("---update by element---");
	printf("please input key for updating:");
	scanf("%d", &key);
	printf("please input  element for updating:");
	scanf("%d", &element);
	int ret = update_by_element(list, key, element);
	if(ret==-1)
	{
	
		printf("key %d is not found or other errorn", key );
	}
	else
	{
		printf("element %d has been updated to %d at pos %dn",key, element, ret );
	}

	output(list); 

	puts("---delete by element---");
	printf("please input element to delete:");
	scanf("%d", &element);
	int ret = delete_by_element(list, element);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		printf("element %d has been deletedn", element);
	}

	output(list);
	
	puts("---remove duplicate element---n");
	puts("> list before remove duplicate:n");
	output(list);
	int ret = rm_duplicate(list);
	if(ret==-1)
	{
	
		printf("element %d is not found or other errorn", element );
	}
	else
	{
		puts("> list after remove duplicate:n");
		output(list);
	}

	puts("---combine 2 lists---n");

	sqlist *la=create_space();
	sqlist *lb=create_space();
	sqlist *lc=create_space();

	append(la, 11);
	append(la, 11);
	append(la, 17);
	append(la, 24);
	append(la, 45);

	append(lb, 13);
	append(lb, 16);
	append(lb, 16);
	append(lb, 36);
	append(lb, 45);
	append(lb, 62);

	puts(">list la:n");
	output(la);
	puts(">list lb:n");
	output(lb);

	combine(la, lb, lc);
	puts(">list lc after combine:n");
	output(lc);
	
	*/
	
	puts("---free list space---n");
	sqlist *ret = free_list(list);
	
		printf("list=%pn", ret );
		puts("> list space has been releasedn");





	return 0;
}

//head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


//顺序表结构体
#define MAXSIZE 30

typedef int data_type;

typedef struct
{
	//数据元素
	data_type data[MAXSIZE];

	//顺序表长度
	int len;

}sqlist; // SQLIST --> sqlist

sqlist *create_space();
int full_sqlist(sqlist*list);
int append(sqlist *list, data_type element);
int delete_tail(sqlist *list);
void output(sqlist *list);
int empty_sqlist(sqlist *list);
int insert(sqlist *list, int index, data_type element);
void search_by_index(sqlist *list, int index);
int index_out_of_range(sqlist *list, int index);
int update(sqlist *list, int index, data_type element);
int delete_by_index(sqlist *list, int index);
int search_by_element(sqlist *list, data_type element);
int update_by_element(sqlist *list, data_type key, data_type element );
int delete_by_element(sqlist *list, data_type element );
int rm_duplicate(sqlist *list);
void combine(sqlist *la,sqlist*lb,sqlist*lc);
sqlist *free_list(sqlist *list);

#endif

//test.c

#include "head.h"


sqlist *create_space()
{
	sqlist *list = (sqlist*)malloc(sizeof(sqlist));
	if(NULL==list)
	{
		puts("error");
		return NULL;
	}

	list->len=0; //顺序表初始化长度清0

	//数据清0
	memset(list->data, 0, sizeof(list->data));
	return list;
}

int full_sqlist(sqlist*list)
{
	int flag = list->len==MAXSIZE;
	//printf("full_list-->flag=%dn", flag);
	return flag;
}

int empty_sqlist(sqlist *list)
{
	if(list->len==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int append(sqlist *list, data_type element)
{

	// printf("list=%pn", list);   
	if(NULL==list || full_sqlist(list))
	{   
		return -1; 

	}   

	list->data[list->len++]=element;
	return 0;

	//  

}     

void output(sqlist *list)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return;

	}

	for(int i=0; i<list->len; i++)
	{
		printf("%dt", list->data[i]);
	}
	putchar(10);

}

int delete_tail(sqlist *list)
{	
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULLn");
		return -1;
	}


	list->len--;
	//不可以释放空间
	return 0;



}

int insert(sqlist *list, int index, data_type element)
{
	if(NULL==list || full_sqlist(list)||index>list->len||index<0 )
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=list->len-1; i>=index; i--)
	{
		list->data[i+1] = list->data[i];
	}
	list->data[index]=element;
	list->len++;
	return 0;

}

int index_out_of_range(sqlist *list, int index)
{
	if(NULL==list||empty_sqlist(list))
	{
		printf("list is NULL or empty!");
		return -1;
	}

	if(index<0||index>=list->len)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

void search_by_index(sqlist *list, int index)
{
	if(NULL==list||index_out_of_range(list, index)||empty_sqlist(list))
	{
		printf("list is NULL or index out of range");
		return;
	}

	data_type element = list->data[index];
	printf("found element:%dn", element);



}


int update(sqlist *list, int index, data_type element)
{
	if(NULL==list||empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or empty or index errorn");
		return -1;
	}

	list->data[index] = element;
	return 0;

}

int delete_by_index(sqlist *list, int index)
{
	if(NULL==list || empty_sqlist(list)||index_out_of_range(list, index))
	{
		printf("list is NULL or index errorn");
		return -1;

	}

	for(int i=index; i<list->len-1; i++)
	{
		list->data[i] = list->data[i+1];
	}


	list->len--;
	return 0;
}

int rm_duplicate(sqlist *list)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	
	for(int i=0; i<list->len-1; i++)
	{
		int cur=i;
		for(int j=i+1; j<list->len; j++)
		{
			if(list->data[cur]==list->data[j])
			{
				printf("list->len=%d, i=%d, j=%dn", list->len, i, j);
				delete_by_index(list, j);
				j--;
			
			}
		}
	}
	return 0;


}

int search_by_element(sqlist *list, data_type element)
{
	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return -1;
	}
	for(int i=0; i<list->len; i++)
	{
		if(element==list->data[i])
		{
			return i;
		}

	}
	return -1;
}

int update_by_element(sqlist *list, data_type key, data_type element )
{
	int found=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return found;
	}


	for(int i=0; i<list->len; i++)
	{
		if(key==list->data[i])
		{
			list->data[i] = element;
			found=i;
		}

	}
		return found;
}

int delete_by_element(sqlist *list, data_type element )
{


	int flag=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULL or emptyn");
		return flag;
	}

	int idx=search_by_element(list, element);
	if(idx==-1)
	{
		return -1;
	}

	int ret=delete_by_index(list, idx);
	return ret;

}


void combine(sqlist *la,sqlist*lb,sqlist*lc)
{
    int p=0;
    int q=0;
    while(p<la->len && q<lb->len)
    {
        if(la->data[p] <=lb->data[q])
        {
            lc->data[lc->len++]=la->data[p++];
        }
        else
        {
            lc->data[lc->len++]=lb->data[q++];
            
        }
    }
    //把la剩余元素存到lc
    while(p<la->len)
    {
        lc->data[lc->len++]=la->data[p++];
        
    }
    //把lb剩余元素存到lc
    while(q<lb->len)
    {
        lc->data[lc->len++]=lb->data[q++];
        
    }
}

sqlist *free_list(sqlist *list)
{	
	int flag=-1;

	if(NULL==list || empty_sqlist(list))
	{
		printf("list is NULLn");
		return NULL;
	}

	free(list);
	list=NULL;
	return list;

}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>