实验1．顺序表操作和单链表操作_数据结构实验报告-实验一 顺序表、单链表基本操作的实现

一、实验目的

1．掌握线性表的存储结构及相关的操作；

2．熟悉对顺序表、单链表的一些基本操作，如初始化、插入、删除等；

3．用C语言编制程序，程序中写出详细注释；

4．给出测试结果，验证程序的正确性。

二、实验要求

1、程序要求包含头文件以及main函数

2、实验中所设计的函数（算法）需要满足实验的要求

3、程序的编译、运行要成功通过

4、运行的结果正确，且有相应的提示

三、实验环境

WIND7、VC++6.0或C与C++程序设计学习与实验系统

四、实验内容

1．插入元素操作：将新元素x从尾部插入顺序表a中、将新元素x插入到顺序表a中第i个位置、将新元素x插入到递增有序的顺序表a中适当的位置。

2．删除元素运算：删除顺序表a中第i个元素、删除顺序表a中值相同的多余元素。

3．创建一个带头结点的单链表

4．插入元素操作：将新元素x插入到单链表head的头部、将新元素x插入到单链表head的尾部、将新元素x插入到单链表head中第i个元素之后。

5．删除元素运算：删除单链表head中值为x的元素。

五、源代码及算法分析

1．插入元素操作：将新元素x从尾部插入顺序表a中、将新元素x插入到顺序表a中第i个位置、将新元素x插入到递增有序的顺序表a中适当的位置。

// 求表长操作 
int getlen (sqlist * L) {
	return(L -> length);
}
 
// 插入操作
int insert (sqlist * L, int i, ElemType x) {
	int j;
	if (i < 1 || i > L -> length+1) return 0;			/* 参数i不合理，返回0 */
	if (L -> length == L -> listsize) {					/* 存储空间不够，增加一个存储空间 */
		L -> data = (ElemType * )realloc(L -> data, (L -> listsize+1) * sizeof(ElemType));
		L -> listsize++;								/* 重置存储空间长度 */
	}
	for (j = L -> length-1; j >= i-1; j--)
		L -> data[j+1] = L -> data[j];					/* 将序号为i及之后的数据元素后移一位 */
	L -> data[i-1] = x;									/* 在序号i处放入x */
	L -> length++;										/* 顺序表长度增1 */
	return 1;											/* 插入成功，返回1 */
} 
 
// 将新元素x插入到递增有序的顺序表a中适当的位置
int compare(sqlist * L, ElemType x) {
	for(int i = 0; i <= getlen(L); i++) {
		if(x <= L->data[i]) {							// 如果x<=某个元素，则x放在该元素的位置上 
			insert(L, i+1, x);
			break;
		}
		else {											// 如果x比所有元素都大，则x放在顺序表的末尾 
			insert(L, getlen(L)+1, x);
			break;
		}
	}
}

算法分析：插入操作主要用到了getlen(sqlist * L)、insert(sqlist * L, int i, ElemType x)和compare(sqlist * L, ElemType x)方法。①getlen()方法主要是返回表长的长度。

②insert()方法主要实现了将新元素x插入到顺序表lists中第i个位置。首先，该方法的形参有顺序表的指针，整型变量i和顺序表的新元素x。然后在方法体内首先通过第一个if判断语句，判断参数i是否合理，如果参数i不合理，返回0；接着通过第二个if判断语句判断顺序表长度与当前存储空间是否相等，不等则通过realloc()方法增加一个存储空间并重置存储空间长度。再接着通过for循环将序号为i及之后的数据元素后移一位，在序号i处放入x，顺序表长度增1，插入成功，返回1。

③compare()方法主要实现了将新元素x插入到递增有序的顺序表a中适当的位置。首先运用for循环将新输入的元素x与顺序表中原有的元素从下标索引为0开始比较，如果x<=某个元素，则将该元素的下标i+1，调用insert()方法，把x放在适当位置；如果x>所有元素，x放在顺序表的末尾，则直接调用insert()方法，第二个参数输入getlen()方法返回的值+1。

最后就是在main()方法里调用上述方法即可。

2．删除元素运算：删除顺序表a中第i个元素、删除顺序表a中值相同的多余元素。

// 删除操作
int deletes(sqlist * L, int i, ElemType * e) {
	int j;
	if (i < 1 || i > L->length) return 0;				/* 参数i不合理，返回0 */
	*e = L -> data[i-1];								/* 存储被删除的元素 */
	for (j = i; j < L->length; j++) {
		L -> data[j-1] = L -> data[j];					/* 将序号为i及之后的数据元素前移一位 */
	}					
	L->length--;										/* 顺序表长度减1 */
	return 1;											/* 删除成功，返回1 */
}
 
// 删除顺序表a中值相同的多余元素
void delete_r(sqlist *L) {
 	int count;
 	int k;
 for(int i = 0;i<L->length;i++) {
 	k = i+1;
 	count = 0;
 	for(int j = i+1; j<L->length; j++)  {
 		if(L->data[i]!=L->data[j]) {
 			L->data[k++] = L->data[j];
 		}
 	else {
 		count++;
 		}
 	}
 	L->length-=count;
	}
}

        算法分析：删除元素运算主要用到deletes(sqlist * L, int i, ElemType * e)和delete_r(sqlist *L)两个方法。

• deletes()方法主要是删除顺序表a中第i个元素。deletes()方法的形参是顺序表的地址，整型变量i和ElemType类型的e指针。在该方法里，首先用if判断传入的参数i是否合理，若不合理则返回0。然后用*e存储被删除的元素，接着开始用for循环将序号为i及之后的数据元素前移一位，也就是覆盖要删除的元素：首先for循环里的条件是j赋值为用户输入的i，接着如果j小于顺序表的长度，就进行+1操作。然后就通过下标索引把下标为j-1的元素赋值为下标为j的元素值，以此类推。
• delete_r()方法主要是删除顺序表a中值相同的多余元素。先定义两个整型变量count和k。利用这两个变量作为索引下标，把相同的元素用后一位元素覆盖掉原来的值。

3．创建一个带头结点的单链表

// 创建一个带头结点的单链表
slink * creslink(int n)
{
	slink * head, * p, * s;							// p用于指向新链入节点，s用于指向新开辟节点 
	int i;
	p = head = (slink *)malloc(sizeof(slink));		// 创建头节点 
	for(i = 1; i <= n; i++) {
		s = (slink *)malloc(sizeof(slink));			// s指向新开辟节点 
		printf("请输入元素：");
		scanf("%d", &s -> data);					// 新节点数据域赋值 
		p -> next = s;								// 将新节点连接到p所指节点的后面 
		p = s;										// p指向新链入节点 
	}
	p -> next = NULL;								// 尾节点的指针域置为空 
	return head;									// 返回头指针 
}

算法分析：p用于指向新链入节点并用malloc()函数返回内存地址值，s用于指向新开辟节点同样用malloc()函数返回内存地址值，s指向新开辟节点，将新节点连接到p所指节点的后面 ，p指向新链入节点 ，最后把尾节点的指针域置为空，返回头指针。

4．插入元素操作：将新元素x插入到单链表head的头部、将新元素x插入到单链表head的尾部、将新元素x插入到单链表head中第i个元素之后

// 插入元素操作
int insert(slink * head, int i, ElemType x) {
	slink * p, * q;
	int j;
	if(i < 1) return 0;								// 参数i不合理，返回0 
	p = head;
	j = 0;
	while(p != NULL && j<i-1) {
		p = p -> next;								// 从第一个节点开始查找第i-1个节点，由p指向它 
		j++;
	}
	if(p == NULL) return 0;							// 参数i值超过链表长度+1，返回0 
	q = (slink *)malloc(sizeof(slink));
	q -> data = x;									// 创建值为x的节点q 
	q -> next = p -> next;							// 将q指向的节点插到p指向的节点之后 
	p -> next = q;
	return 1;										// 插入成功，返回1 
}

算法分析：首先使用if判断语句判断参数i是否合理，若不合理则返回0；然后再使用while循环从第一个节点开始查找第i-1个节点，由p指向它；再使用if判断语句判断p是否等于NULL，若等于NULL，则链表长度+1，返回0；最后创建值为x的节点q，将q指向的节点插到p指向的节点之后。

5．删除元素运算：删除单链表head中值为x的元素。

// 删除元素运算
int deletes(slink * head, int i, ElemType * e) {
	slink * p, * q;
	int j;
	if(i < 1) return 0;
	p = head;
	j = 0;
	while(p -> next != NULL && j<i-1) {
		p = p -> next;
		j++;
	}
	if(p -> next == NULL) return 0;
	q = p -> next;
	p -> next = q -> next;
	* e = q -> data;
	free(q);
	return 1;
}

算法分析：首先使用if判断语句判断参数i是否合理，若不合理则返回0；接着使用while循环从第1个节点开始查找第i-1个节点，由p指向它；再使用if判断语句判断p->next是否等于NULL，若等于NULL，则参数i值超过链表的长度并且返回0；接着p指向第i个节点，p的指针域指向q指向节点的下一个节点，删除第i个节点。

六、运行测试（对实验结果进行相应分析，或总结实验的心得体会，并提出算法的改进意见）

1．插入元素操作：将新元素x从尾部插入顺序表a中、将新元素x插入到顺序表a中第i个位置、将新元素x插入到递增有序的顺序表a中适当的位置。

2．删除元素运算：删除顺序表a中第i个元素、删除顺序表a中值相同的多余元素。

1和2的运行结果如下图：

由图知，1和2的要求均已完成且通过测试。

3．创建一个带头结点的单链表

4．插入元素操作：将新元素x插入到单链表head的头部、将新元素x插入到单链表head的尾部、将新元素x插入到单链表head中第i个元素之后。

5．删除元素运算：删除单链表head中值为x的元素。

3、4和5的运行结果如下图：

由图知，3、4和5的要求均已完成且通过测试。

七、完整代码

1.顺序表

# include <stdio.h>
# include <malloc.h>
# define INITSIZE 100     /* 顺序表存储空间的初始分配量 */
 
typedef int ElemType;    /* 在实际问题中,根据需要定义所需的数据类型 */
 
typedef struct { 
  ElemType *data;        /* 存储空间基地址 */
  int length;            /* 顺序表长度(即已存入的元素个数) */
  int listsize;         /* 当前存储空间容量(即能存入的元素个数) */
}sqlist;
 
void initlist (sqlist * L) {
	L -> data = (ElemType * )malloc(sizeof(ElemType) * INITSIZE);
	L -> length = 0;
	L -> listsize = INITSIZE;
}
 
// 求表长操作 
int getlen (sqlist * L) {
	return(L -> length);
}
 
// 插入操作
int insert (sqlist * L, int i, ElemType x) {
	int j;
	if (i < 1 || i > L -> length+1) return 0;			/* 参数i不合理，返回0 */
	if (L -> length == L -> listsize) {					/* 存储空间不够，增加一个存储空间 */
		L -> data = (ElemType * )realloc(L -> data, (L -> listsize+1) * sizeof(ElemType));
		L -> listsize++;								/* 重置存储空间长度 */
	}
	for (j = L -> length-1; j >= i-1; j--)
		L -> data[j+1] = L -> data[j];					/* 将序号为i及之后的数据元素后移一位 */
	L -> data[i-1] = x;									/* 在序号i处放入x */
	L -> length++;										/* 顺序表长度增1 */
	return 1;											/* 插入成功，返回1 */
} 
 
// 将新元素x插入到递增有序的顺序表a中适当的位置
int compare(sqlist * L, ElemType x) {
	for(int i = 0; i <= getlen(L); i++) {
		if(x <= L->data[i]) {							// 如果x<=某个元素，则x放在该元素的位置上 
			insert(L, i+1, x);
			break;
		}
		else {											// 如果x比所有元素都大，则x放在顺序表的末尾 
			insert(L, getlen(L)+1, x);
			break;
		}
	}
}
 
// 删除操作
int deletes(sqlist * L, int i, ElemType * e) {
	int j;
	if (i < 1 || i > L->length) return 0;				/* 参数i不合理，返回0 */
	*e = L -> data[i-1];								/* 存储被删除的元素 */
	for (j = i; j < L->length; j++) {
		L -> data[j-1] = L -> data[j];					/* 将序号为i及之后的数据元素前移一位 */
	}					
	L->length--;										/* 顺序表长度减1 */
	return 1;											/* 删除成功，返回1 */
}
 
// 删除顺序表a中值相同的多余元素
void delete_r(sqlist *L) {
 	int count;
 	int k;
 for(int i = 0;i<L->length;i++) {
 	k = i+1;
 	count = 0;
 	for(int j = i+1; j<L->length; j++)  {
 		if(L->data[i]!=L->data[j]) {
 			L->data[k++] = L->data[j];
 		}
 	else {
 		count++;
 		}
 	}
 	L->length-=count;
	}
}
 
// 输出操作
void list (sqlist * L) {
	int i;
	for (i = 0; i < L -> length; i++)
		printf("%5d", L -> data[i]);
	printf("\n");
} 
 
int main() {
	ElemType a;
	ElemType e;
	sqlist lists;
	
	initlist(&lists);
	
	printf("input datas(-1 : end):");
	scanf("%d", &a);
	while(a != -1) {
		insert(&lists, lists.length+1, a);
		scanf("%d", &a);
	}
	
	// 将新元素x从尾部插入顺序表lists中
	printf("请输入新元素x：");
	ElemType x;
	scanf("%d", &x); 
	insert(&lists, getlen(&lists)+1, x);
	printf("新元素x从尾部插入顺序表后的结果是：\n");
	list(&lists);
	
	// 将新元素x插入到顺序表lists中第i个位置
	printf("请输入新元素y：");
	ElemType y;
	scanf("%d", &y);
	printf("请输入你要插入的位置：");
	int location;
	scanf("%d", &location);
	insert(&lists, location, y);
	printf("元素插入到第%d位后的结果是：\n", location);
	list(&lists);
	
	// 将新元素z插入到递增有序的顺序表a中适当的位置中 
	sqlist nlists;
	initlist(&nlists);				// 创建一个新的空顺序表 
	printf("请输入递增有序的顺序表(-1 : end):");
	ElemType datas;
	scanf("%d", &datas);
	while(datas != -1) {
		insert(&nlists, nlists.length+1, datas);
		scanf("%d", &datas);
	}
	printf("请输入新元素z：");
	ElemType z;
	scanf("%d", &z);
	compare(&nlists, z);
	printf("将新元素z插入到递增有序的顺序表a中适当的位置后的结果是：");
	list(&nlists);
	
	// 删除顺序表a中第i个元素
	printf("请输入你要删除nlists顺序表中第i个元素：");
	int removes;
	ElemType t;
	scanf("%d", &removes);
	deletes(&nlists, removes, &t);
	printf("删除元素后的顺序表结果为：\n");
	list(&nlists);
	
	// 删除顺序表a中值相同的多余元素
	delete_r(&nlists);
	printf("删除顺序表a中值相同的多余元素后的结果是：");
	list(&nlists);
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2.单向链表

# include <stdio.h>
# include <malloc.h>
 
typedef int ElemType;
typedef struct node
{	
	ElemType data;			// 数据域 
	struct node * next;		// 指针域 
} slink;
 
// 创建一个带头结点的单链表
slink * creslink(int n)
{
	slink * head, * p, * s;							// p用于指向新链入节点，s用于指向新开辟节点 
	int i;
	p = head = (slink *)malloc(sizeof(slink));		// 创建头节点 
	for(i = 1; i <= n; i++) {
		s = (slink *)malloc(sizeof(slink));			// s指向新开辟节点 
		printf("请输入元素：");
		scanf("%d", &s -> data);					// 新节点数据域赋值 
		p -> next = s;								// 将新节点连接到p所指节点的后面 
		p = s;										// p指向新链入节点 
	}
	p -> next = NULL;								// 尾节点的指针域置为空 
	return head;									// 返回头指针 
}
 
// 插入元素操作
int insert(slink * head, int i, ElemType x) {
	slink * p, * q;
	int j;
	if(i < 1) return 0;								// 参数i不合理，返回0 
	p = head;
	j = 0;
	while(p != NULL && j<i-1) {
		p = p -> next;								// 从第一个节点开始查找第i-1个节点，由p指向它 
		j++;
	}
	if(p == NULL) return 0;							// 参数i值超过链表长度+1，返回0 
	q = (slink *)malloc(sizeof(slink));
	q -> data = x;									// 创建值为x的节点q 
	q -> next = p -> next;							// 将q指向的节点插到p指向的节点之后 
	p -> next = q;
	return 1;										// 插入成功，返回1 
}
 
// 删除元素运算
int deletes(slink * head, int i, ElemType * e) {
	slink * p, * q;
	int j;
	if(i < 1) return 0;
	p = head;
	j = 0;
	while(p -> next != NULL && j<i-1) {
		p = p -> next;
		j++;
	}
	if(p -> next == NULL) return 0;
	q = p -> next;
	p -> next = q -> next;
	* e = q -> data;
	free(q);
	return 1;
}
 
// 输出操作 
void list(slink * head) {
	slink * p;
	p = head -> next;
	while(p != NULL) {
		printf("%4d", p -> data);
		p = p -> next;
	}
	printf("\n");
}
 
int main() {
	// 创建一个带头结点的单链表
	slink * links;
	printf("请输入你要存储的元素个数：\n");
	int n;
	scanf("%d", &n);
	links = creslink(n);
	printf("链表存储完元素后的结果是：\n");
	list(links);
	
	// 将新元素x插入到单链表head的头部
	ElemType x;
	printf("请输入插入链表头部的元素：");
	scanf("%d", &x);
	insert(links, 1, x);
	printf("元素插入到头部后的结果为：");
	list(links);
	
	// 将新元素x插入到单链表head的尾部
	printf("请输入插入链表尾部的元素：");
	scanf("%d", &x);
	insert(links, n+2, x);
	printf("元素插入到尾部后的结果为：");
	list(links);
	
	// 将新元素x插入到单链表head中第i个元素之后
	printf("请输入插入链表i位置的元素：");
	scanf("%d", &x);
	int i;
	printf("请输入你要插入的i位置：");
	scanf("%d", &i);
	insert(links, i, x);
	printf("元素插入到链表i位置后的结果为：");
	list(links);
	
	// 删除单链表head中值为x的元素
	printf("你要删除的元素的位置是第几位：");
	scanf("%d", &i);
	ElemType e;
	deletes(links, i, &e);
	printf("删除元素后的结果是："); 
	list(links);
}