博客

实验一 顺序表、单链表基本操作的实现

实验目的

1、顺序表

（1）掌握顺序表的存储结构形式及其描述

（2）掌握顺序表的建立、查找、插入、删除操作

2、链表

（1）掌握单链表的存储结构形式及其描述

（2）掌握单链表的建立、查找、插入和删除操作

实验内容

1、顺序表

1. 编写函数，输入一组整型元素序列，建立一个顺序表。
2. 编写函数，实现对该顺序表的遍历（每个元素被访问一次且仅被访问一次）。
3. 编写函数，在顺序表中顺序查找某一元素，查找成功则返回其存储位置i，否则返回错误信息。
4. 编写函数，实现在顺序表的第i个位置上插入一个元素x。
5. 编写函数，实现删除顺序表中第i个元素。
6. 编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述函数。
   
   2、链表
7. 编写函数，实现随机产生或键盘输入一组元素，建立一个带头结点的单链表（无序）。
8. 编写函数，实现遍历单链表。
9. 编写函数，在非递减有序单链表中插入一个元素使链表仍然有序。
10. 编写函数，实现在非递减有序链表中删除值为x的结点。
11. 编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述函数。

顺序表

#include<iostream>
#include<fstream>
using namespace std; 
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100 
#define ERROR 0 

//定义顺序表 
typedef struct
{
   
  int *elem;
  int Length;
}SqList;

//创建顺序表 
int InitiList(SqList &L)
{
   //构造一个空的顺序表L 
	L.elem=new int[MAXSIZE];//为顺序表分配一个大小为MAXSIZE的数组空间 
	if(!L.elem)
	{
   
		printf("空间分配失败！");
	}
	L.Length=0;
	return 1;
} 
	 
//依次输入顺序表元素
void inputSqList(SqList &L,int y)
{
   
	int i,x;
	printf("请依次输入顺序表：");
	for(i=0;i<y;i++)
	{
   
		scanf("%d",&x);
		L.elem[i]=x;
	}
	L.Length=y;
 } 
	
//实现对该顺序表的遍历
void outputSqList(SqList &L)
{
   
	int i;
	printf("[\t");
	for(i=0;i<L.Length;i++)
	{
   
		printf("%d\t",L.elem[i]);
	 } 
	 printf("]");
 } 


int Insert_SqList(SqList &L,int i,int x)   /*插入运算函数*/
{
     //判断插入的位置是否合理 
	if(i<0||i>L.Length+1){
   
		printf("插入的位置不合理！");
		return 0; 
	}
	//判断存储空间是否已满 
	if(L.Length==MAXSIZE){
    
	    printf("存储空间已满！");
	    return 0;
	} 
	//在顺序表的第i个位置上插入一个元素x 
	for(int j=L.Length-1;j>=i-1;j--)
	L.elem[j+1]=L.elem[j];//插入之后的元素后移
	L.elem[i-1]=x;//将新元素x放入第i个位置 
	++L.Length;//表长加1
	return 1;
}

int Delete_SqList(