精华内容
下载资源
问答
  • 实验一 顺序表基本操作的实现 一、实验学时: 2学时 二、实验目的 实现顺序表的基本操作 三、实验内容 顺序表的建立、取指定元素、返回指定元素位置 顺序表中插入新元素、删除指定元素操作的实现 四、主要仪器...

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

    一、实验学时: 2学时

    二、实验目的

    • 实现顺序表的基本操作

    三、实验内容

    1. 顺序表的建立、取指定元素、返回指定元素位置
    2. 顺序表中插入新元素、删除指定元素操作的实现

    四、主要仪器设备及耗材

    • 硬件:计算机一台
    • 软件:VC++ 6.0,MSDN2003或者以上版本

    五、实验步骤

    1. 分析问题
    2. 写出算法
    3. 编制程序
    4. 上机调试
    5. 分析结果

    六、程序清单

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>			//要用exit所以加它 
    #define OK 1				//成功返回值 
    #define ERROR 0         	//出错返回值 
    #define OVERFLOW -2    		//溢出返回值 
    #define MAXSIZE 10000   	//空间大小 
    //用户自定义类型Status 
    typedef int Status;
    
    //定义图书结构体 
    typedef struct
    {
    	char no[20];		//书号 
    	char name[50];		//书名 
    	float price;		//价格 
    }Book;
    
    //用户自定义类型SqList 
    typedef struct
    {
    	Book *elem;		//图书指针 
    	int length;		//图书顺序表长度 
    }SqList;
    
    //初始化顺序表 
    Status InitList(SqList &L)		//形参要的是SqList的引用,调用时是InitList(L),因为引用更改后它本身就更改了。不然传的只是副本,对原值无影响。 
    {
    	L.elem=new Book[MAXSIZE];	//为顺序表分配一个MAXSIZE大小的数组空间 
    	if(!L.elem) exit(OVERFLOW);	//分配失败退出 
    	L.length=0;					//空表长度为0 
    	return OK;
    }
    
    //取值 
    Book GetElem(SqList L,int i)	//取出顺序表位于第i个位置的元素 
    {
        if(i<1||i>L.length) printf("取值操作异常");	//取值异常 
        return L.elem[i-1];							//返回找到的值 
    }
    
    //查找 
    int LocateElem(SqList L,Book e)		//查找元素e在顺序表中的位置 
    {
    	int i;
        for(i=0;i<L.length;i++)
            if(strcmp(L.elem[i].no,e.no)==0&&strcmp(L.elem[i].name,e.name)==0&&L.elem[i].price==e.price) return i+1;
        return 0;
    }
    
    //插入 
    Status ListInsert(SqList &L,int i,Book e)	//将元素e插入到顺序表L的第i的位置 
    {
        if((i<1)||(i>L.length+1)) return ERROR;
        if(L.length==MAXSIZE) return ERROR;
        int j;
        for(j=L.length-1;j>=i-1;j--)
            L.elem[j+1]=L.elem[j];				//i位置及以后的元素整体后移 
        L.elem[i-1]=e;
        ++L.length;
        return OK;
    }
    
    //删除 
    SqList ListDelete(SqList &L,int i)
    {
        if((i<1)||(i>L.length+1)) printf("删除异常");
        int j; 
        for(j=i;j<=L.length-1;j++)
            L.elem[j-1]=L.elem[j];				//被删元素后面的整体前移 
        --L.length;
        return L;
    }
    
    int main()
    {
    	SqList L;
    	Status status = InitList(L);
    	if(!status)
    	{
    		printf("顺序表初始化失败!\n");
    		return ERROR;	
    	}
    	else
    	{
    		printf("顺序表初始化成功!\n");
    		Book e;
    		printf("请录入图书信息:\n");
    		printf("书号:");scanf("%s",&e.no);
    		printf("书名:");scanf("%s",&e.name);
    		printf("价格:");scanf("%f",&e.price);
    		int i;
    		for(i=1;;++i)
    		{
    			ListInsert(L,i,e);
    			printf("成功收藏%d本书至图书馆\n",i);
    			printf("书号:");scanf("%s",&e.no);
    			printf("书名:");scanf("%s",&e.name);
    			printf("价格:");scanf("%f",&e.price);
    			if(e.price==0)
    				break;
    		}
    		
    		printf("图书馆共%d本书\n",L.length);
    		printf("图书馆的图书列表:\n");
    		Book e1;
    		int j;
    		printf("编号\t书名\t\t价格\n");
    		for(j=1;j<=L.length;j++)
    		{
    			e1=GetElem(L,j);
    			printf("%s\t",e1.no);
    			printf("%s\t",e1.name);
    			printf("%-7.2f\n",e1.price);
    		}
    		Book e2={"10102","计算机组成原理",46.5};
    		int location = LocateElem(L,e2);
    		printf("其中第%s在第%d个位置\n",e2.name,location); 
    		printf("------------------------------\n"); 
    		
    		printf("删除第二本后的列表:\n"); 
    		SqList sl = ListDelete(L,2);
    		printf("图书馆共%d本书\n",sl.length);
    		printf("图书馆的图书列表:\n");
    		printf("编号\t书名\t\t价格\n");
    		for(j=1;j<=sl.length;j++)
    		{
    			e2=GetElem(sl,j);
    			printf("%s\t",e2.no);
    			printf("%s\t",e2.name);
    			printf("%-7.2f\n",e2.price);
    		}
    	}
    }
    

    七、运行结果及分析
    当价格为0结束输入
    八、小总结

    • 建立顺序表(初始化):初始化就是用指针指向新分配的空间,若内存不足分配失败则退出,否的话长度置为0,然后返回OK。
    • 取指定位置元素(取值):就是超出范围取值异常,在范围内就返回第i个元素。
    • 返回指定元素位置(查找):循环查找,如果是基本数据类型相等就行了,像本程序中用的是Book结构体类型,所以要比较每一个数据,都相等则返回位置。
    • 向指定位置插入元素(插入):超出范围和溢出都报错,i位置及以后的元素整体后移空出位置i放元素e,然后长度加1。
    • 删除指定位置元素(删除):超出范围报错,否则被删元素后面的元素整体前移,长度减1。
    • 要说的问题:&L与L
      参数里的这两者区别,带&是传的引用,可以更改L里的数据,不然的话只是传了一个副本,形参改变对实参无影响。
    展开全文
  • 数据结构-顺序表基本操作的实现(含全部代码)

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。 CreatList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n) InitList...

    今天起开始编写数据结构中的各种数据结构及其算法的实现。

    主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。

    今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。

    • CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    • InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    • InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    • ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    • LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    • Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    • PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    • SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    • ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表

    代码如下:

    /*
    Project: sequence_list(数据结构-顺序表)
    Date:    2018/09/12  20191012修改 添加Reverse  20200819修改 添加ClearList
    Author:  Frank Yu
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表
    */
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList &L)
    {
    	memset(L.data, 0, sizeof(L));//初始化数据为0
    	L.length = 0;                //初始化长度为0
    	return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreateList(SqList &L, int n)
    {
    	if (n<0 || n>MaxSize)false;//n非法
    	for (int i = 0; i<n; i++)
    	{
    		scanf("%d", &L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList &L, int i, ElemType e)
    {
    	if (i<1 || i>L.length + 1) //判断位置是否有效
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	if (L.length >= MaxSize)//判断存储空间是否已满
    	{
    		printf("当前存储空间已满!!!\n");
    		return false;
    	}
    	for (int j = L.length; j >= i; j--)//位置i及之后元素后移
    	{
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;
    	L.length++;
    	return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList &L, int i)
    {
    	if (i<1 || i>L.length)
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	for (int j = i; j <= L.length - 1; j++)//位置i之后元素依次前移覆盖
    	{
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L, ElemType e)
    {
    	for (int i = 0; i<L.length; i++)//从低位置查找
    	{
    		if (L.data[i] == e)
    			return i + 1;
    	}
    	return 0;
    }
    //倒置函数 将原顺序表直接倒置
    void Reverse(SqList &L)
    {
    	if (L.length)
    		for (int i = 0; i<L.length - 1 - i; i++)
    		{
    			int t = L.data[i];
    			L.data[i] = L.data[L.length - 1 - i];
    			L.data[L.length - 1 - i] = t;
    		}
    }
    //奇偶分开并排序
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false;
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0)i++;
    			while (L.data[j] % 2 == 0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if(!flag) //没有交换
    			{
    				Even = L.length - 1;//全奇数
    				Odd = 0; //全偶数
    			}
    		}
    	if (flag)
    	{
    		for(int i=0;i<L.length;i++)
    			if (L.data[i] % 2 == 0) 
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    //清空顺序表
    void ClearList(SqList &L) {
    	L.length = 0;
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for (int i = 0; i<L.length; i++)
    	{
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n; bool flag;
    	L.length = 0;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d", &n);
    	printf("请输入%d个数(空格隔开):", n);
    	flag = CreateList(L, n);
    	if (flag) {
    		printf("创建成功!\n");
    		PrintList(L);
    	}
    	else printf("输入长度非法!\n");
    
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
    	int place; ElemType e; bool flag;
    	printf("请输入要插入的位置(从1开始)及元素:\n");
    	scanf("%d%d", &place, &e);
    	flag = InsertList(L, place, e);
    	if (flag)
    	{
    		printf("插入成功!!!\n");
    		PrintList(L);
    	}
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
    	int place; bool flag;
    	printf("请输入要删除的位置(从1开始):\n");
    	scanf("%d", &place);
    	flag = ListDelete(L, place);
    	if (flag)
    	{
    		printf("删除成功!!!\n");
    		PrintList(L);
    	}
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
    	ElemType e; int flag;
    	printf("请输入要查找的值:\n");
    	scanf("%d", &e);
    	flag = LocateElem(L, e);
    	if (flag)
    	{
    		printf("该元素位置为:%d\n", flag);
    	}
    	else
    		printf("未找到该元素!\n");
    }
    //菜单
    void menu()
    {
    	printf("********1.创建                        2.插入*********\n");
    	printf("********3.删除                        4.查找*********\n");
    	printf("********5.倒置                        6.分奇偶排序***\n");
    	printf("********7.输出                        8.清空*********\n");
    	printf("********9.退出                              *********\n");
    }
    int main()
    {
    	SqList L; int choice;
    	InitList(L);
    	while (1)
    	{
    		menu();
    		printf("请输入菜单序号:\n");
    		scanf("%d", &choice);
    		if (9 == choice) break;
    		switch (choice)
    		{
    		case 1:Create(L); break;
    		case 2:Insert(L); break;
    		case 3:Delete(L); break;
    		case 4:Search(L); break;
    		case 5:Reverse(L); break;
    		case 6:SplitSort(L); break;
    		case 7:PrintList(L); break;
    		case 8:ClearList(L); break;
    		default:printf("输入错误!!!\n");
    		}
    	}
    	return 0;
    }

    结果截图:

    插入结果截图
    删除结果截图
    查找结果截图
    输出结果截图

    ---------------------------------------------2018-09-18更新 添加创建函数 菜单有改动-----------------------------------------

                                                                     

     

    ---------------------------------------------20191012更新 添加Reverse函数--------------------------------------------

    根据下方评论,添加了倒置函数,参考stl的Reverse写法

    template <class _RandomAccessIter>
    _STLP_INLINE_LOOP void
    __reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
      for (; __first < __last; ++__first)
        _STLP_STD::iter_swap(__first, --__last);
    }
    倒置展示

    2019年10月23日更新,应评论区小伙伴的要求,添加了奇偶分开,并排序的函数

    //奇偶分开并排序
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false;
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0)i++;
    			while (L.data[j] % 2 == 0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if(!flag) //没有交换
    			{
    				Even = L.length - 1;//全奇数
    				Odd = 0; //全偶数
    			}
    		}
    	if (flag)
    	{
    		for(int i=0;i<L.length;i++)
    			if (L.data[i] % 2 == 0) 
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    测试全奇偶

     

    有奇偶

    代码已更新至上方全部代码!!!

    -------------------------20200819修改 添加ClearList-------------------------------------

    代码由评论区用户__BlackHole提供,已更新至上方全部代码。

    至于销毁,我是使用的静态分配,如果是new(delete释放)或malloc(free释放)的话,需要释放空间,其实就是堆和栈的区别。

    堆和栈的区别就是申请方式不同:栈是系统自动分配空间,而堆则是程序员根据需要申请空间。由于栈上的空间是自动分配自动回收的,所以,栈内数据的生存周期只是在函数的运行过程中,运行后就释放掉。而堆上的数据只要程序员不释放空间,就一直可以访问到,缺点是一旦忘记释放会造成内存泄露。

    综上,我写的顺序表不需要进行销毁,当然,顺序表最大长度也固定了,各有利弊,如果是动态分配的话记得释放空间呀!

    更多数据结构与算法的实现:数据结构(严蔚敏版)与算法的实现(含全部代码)

    本人b站账号:lady_killer9

    有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。如果您感觉有所收获,自愿打赏,可选择支付宝18833895206(小于),您的支持是我不断更新的动力。

    展开全文
  • 【实验课程名称】算法与数据结构 【实验项目名称】顺序表基本操作的实现
  • 实验二顺序表基本操作的实现 链表基本操作的实现 线性表的顺序存储有何优缺点? 各举一两个例子说明求解什么样的问题用顺序存储较好
  • 2. 顺序表基本操作的实现;3. 掌握利用C/C++编程语言实现数据结构的编程方法;4. 通过上机时间加强利用数据结构解决实际应用问题的能力;二、 实验相关知识1. 线性表的顺序存储结构的实现;2. 线性表的应用三...

    一、 实验目的

    1. 掌握线性表的逻辑结构;

    2. 顺序表基本操作的实现;

    3. 掌握利用C/C++编程语言实现数据结构的编程方法;

    4. 通过上机时间加强利用数据结构解决实际应用问题的能力;

    二、 实验相关知识

    1. 线性表的顺序存储结构的实现;

    2. 线性表的应用

    三、 实验内容与要求

    (一)基础题

    1. 编写顺序表基本操作函数:

    ① InitList(LIST *L,int ms)初始化线性表;

    ② InsertList(LIST *L,int item,int rc)向顺序表的指定位置rc插入元素item;

    ③ DeleteList(LIST *L,int item)删除指定元素值item的顺序表记录;

    ④ DeleteList2(LIST *L,int rc)删除指定位置rc的顺序表记录;

    ⑤ FindList(LIST *L,int item)查找顺序表中的元素;

    ⑥ OutputList(LIST *L)输出顺序表元素。

    2. 调用上述函数实现下列操作:

    ① 初始化顺序表;

    ② 调用插入函数建立一个顺序表;

    ③ 在顺序表中寻找指定的元素;

    ④ 在顺序表中删除指定值的元素;

    ⑤ 在顺序表中删除指定位置的元素;

    ⑥ 遍历并输出顺序表。

    注:每完成一个步骤,及时地输出线性表元素,以便于观察操作结果。

    list.h

    #include<stdio.h>
    #include<stdlib.h>
    
    struct SeqList	 	/*定义顺序表结构*/
    {
    	int *list;		     /* 用于存储顺序表元素的数组*/
    	int size;    		 /* 顺序表长度 */
    	int MaxSize;         /* 顺序表的最大长度 */
    };
    typedef struct SeqList LIST;
    
    /* 初始化线性表        */
    /* L为指向顺序表的指针 */
    /* ms为顺序表最大长度  */
    void InitList( LIST *L, int ms );
    
    /* 输出功能,将顺序表元素输出至控制台屏幕*/
    /* L为指向顺序表的指针                   */
    void OutputList( LIST *L );
    
    /* 添加功能,在顺序表的某个插入位置插入元素 */
    /* 函数返回值整型,返回0成功,返回-1则失败  */
    /* L为指向顺序表的指针                      */
    /* item为插入的元素值                       */
    /* rc为插入的位置(即下标)                 */
    int InsertList( LIST *L, int item, int rc );
    
    /* 查找功能,在顺序表中查找元素                         */
    /* 函数返回值整型,返回>=0 为元素位置,若返回-1则没找到 */
    /* L为指向顺序表的指针,item为查找的元素                 */
    int FindList( LIST *L, int item );		
    
    /* 删除功能,在顺序表中删除元素                            */
    /* 函数返回值整型,返回>=0 为删除元素的位置,返回-1删除失败*/
    /* L为指向顺序表的指针,item为删除的元素                    */
    int DeleteList1( LIST *L, int item );
    
    /* 删除功能,在顺序表中删除元素                    */
    /* 函数返回值整型,返回0成功,返回-1删除失败       */
    /* L为指向顺序表的指针,rc为删除元素的位置(即下标)*/
    int DeleteList2( LIST *L, int rc );

    List.cpp
    void InitList( LIST *L, int ms )	
    {
    	if( (L->list = new int[] ) == NULL ) {
    		printf( "内存申请错误!\n" );
    		exit( 1 );
    	}
    	L->size = 0;     /*设置初始顺序表的长度*/         
    	L->MaxSize = ms; 
    }
    int InsertList( LIST *L, int item, int rc )	
    {
        int i;
    	if( L->size == L->MaxSize )	      /* 若顺序表已满 */
    		return -1;
        /* 合法插入位置为 0 --> L->size */
    	if( rc < 0 )      /* 若位置小于0,则插入位置设置为第一个元素的下标*/   
    		rc = 0;
    	if( rc > L->size )   /* 若位置大于L->size,则插入位置设置为最后一个元素的后一个位置*/
    		rc = L->size;
    	for( i = L->size - 1; i >= rc; i-- )	/* 将顺序表元素后移 */
    		L->list[i+1] = L->list[i];                     
    	L->list[rc] = item;   /*在rc位置插入item*/
    	L->size++;                   /*顺序表长度加1*/
    	return 0; 
    }
    void OutputList( LIST *L )		/* 输出线性表元素 */
    {
    	int i;
    	for( i = 0;i < L->size;i++ )
    		printf( "%d ", L->list[i]);
            printf( "\n" );
    }
    int FindList( LIST *L, int item )		
    {
    	int i;
    	for( i = 0; i < L->size; i++ )
    		if(L->list[i] == item )	/* 找到相同的元素,返回位置 */
    			return i;
    	return -1;				/* 失败 */
    }
    int DeleteList1( LIST *L, int item )	
    {
    	int i, n;
    	for( i = 0; i < L->size; i++ )
    		if( item == L->list[i] )	/* 找到相同的元素 */
    			break;
    	if( i < L->size ) {
    		for( n = i; n < L->size - 1; n++ )
    			L->list[n] = L->list[n+1];
    		L->size --;
    		return i;
    	}
            return -1;
    }
    /* 删除指定位置的线性表记录 */
    int DeleteList2( LIST *L, int rc )	 
    {
    	if(rc >= L->size)
    		return -1;
    	else
    		for(int i = rc;i < L->size;i++)
    			L->list[i] = L->list[i+1];
    		L->size--;
    	return 1;
    }
    main.cpp
    #include "List.h"
    
    /*主函数共有7处填空,请完成*/
    void main()
    {
    	LIST LL;
    	int i,r;
    	InitList(&LL,10 );	/*初始顺序表*/
    	printf("list addr=%p\t size=%d\t MaxSize=%d\n",LL.list,LL.size,LL.MaxSize);/*输出初始后顺序表状态*/
    	
    	while(1) /*插入元素*/
    	{
    		printf("请输入元素值,输入0结束插入操作");
    		fflush(stdin);  /*清空标准输入缓冲区*/
    		scanf("%d",&i);
    		if( i == 0 )      /*若输入0结束*/
    		  break;
    		printf("请输入插入位置:");
    		scanf("%d",&r);
    		InsertList( &LL,i,r - 1 );
    		printf("线性表为:");
    		OutputList(&LL);/*输出线性表元素*/
    	}
    	
    	while( 1 )  /* 按元素值查找 */
    	{
    		printf( "请输入查找元素值,输入0结束查找操作:" );
    		fflush( stdin );	/* 清空标准输入缓冲区 */
    		scanf( "%d", &i );
    		if( i == 0 )
              break;
    		r= FindList(&LL,i);     /*按元素值查找*/
            if( r < 0 )
    			printf( "没找到\n" );
    		else
    			printf( "有符合条件的元素,位置为:%d\n", r+1 );
    	}
    
    	
    	while( 1 )   /* 按元素值删除元素 */
    	{
    		printf( "请输入删除元素值,输入0结束删除操作:" );
    		fflush( stdin );	/* 清空标准输入缓冲区 */
    		scanf( "%d", &i );
    		if( i == 0 )
               break;
    		r =DeleteList1(&LL,i);   /*按元素值删除*/
            if( r < 0 )
    			printf( "没找到\n" );
    		else {                    	
    			printf( "有符合条件的元素,位置为:%d\n线性表为:", r+1 );
    			OutputList( &LL );
                    }
    	}
    
    	
    	while( 1 )  /* 按元素位置删除 */
    	{
    		printf( "请输入删除元素位置,输入0结束删除操作:" );
    		fflush( stdin );	/* 清空标准输入缓冲区 */
    		scanf( "%d", &r );
    		if( r == 0 )
              break;
    		i = DeleteList2(&LL,r - 1);     /*按位置删除*/
            if( i < 0 )
    			printf( "位置越界\n" );
    		else {                    	
    			printf( "线性表为:" );
    			OutputList( &LL );
                    }
    	}
    	system("pause");
    }

    (二)提高题

    1. 利用顺序表表示两个一元多项式,并完成两多项式的一些运算,如加法。输入包含两行数据,第一行输入第一个一元多项式polya各项的指数和系数,且以输入0 0结束,按指数的升序创建表示第一个多项式的顺序表,第二行输入第二个一元多项式polyb各项的指数和系数,按指数的升序创建表示第二个多项式的顺序表。程序能输出两一元多项式,计算两个一元多项式和并输出,对自己的算法进行时间复杂度的分析。

    【测试用例】

    输入

    3 -18 2 -49 6 13 4 -11 9 14 0 0

    1 -46 3 37 4 -27 5 3 7 -123 0 0

    输出

    1 -46 2 -49 3 19 4 -38 5 3 6 13 7 -123 9 14

     

    【解题思路】

    l 一元多项式满足顺序表的逻辑结构,相邻两项具有前驱和后继的关系,故可以使用顺序表结构表示。

     

    l 顺序表如何表示数据?

    一元多项式每项都有指数和系数中,故顺序表需存储这两部分内容。改造上题中顺序表的存储结构,可参考

    struct Data

         {

        int exp;

        int coef;

         };

    typedef  struct

    {  

         Data  *elem;

         int   last;

     } Polylist;

    l 创建多项式顺序表

    初始顺序表长度为0,空表。每获取一项的指数系数则对顺序表进行插入(按指数的升序)操作。

    创建好顺序表后,可以输出查看顺序表。

    l 两个多项式相加

    算法思相:与合并相似。两个多项式(按指数有序),将B多项式顺序表中的每一项x加入到A多项式顺序表,有以下情况:

    ① 若A表中不存在与x同指数的元素,则按x的指数大小插入到A表中;

    ② 若A表中已存在与x同指数的元素,则修改A表中与x指数相同的元素的系数应加上x的系数,若系数和为0,则要从顺序表中删除该指数对应的元素;

    Poly.cpp
    #include "Poly.h"
    void creatPoly(Polylist *p)
    {
    	if ((p->elem = new Data[1000]) == NULL) {
    		std::cout << "内存分配错误" << std::endl;
    		exit(1);
    	}
    	p->size = 0;
    	p->MaxSize = 1000;
    }
    
    void insertItem(Polylist *p, int exp, int coef)
    {
    	Data temp;
    	temp.coef = coef, temp.exp = exp;
    	if (p->size == 0) {
    		p->elem[0] = temp;
    		p->size++;
    		return;
    	}
    	int index = -1;
    	for (int i = 0; i < p->size; i++) {
    		if (exp <= p->elem[i].exp) {
    			index = i;
    			break;
    		}
    	}
    	if (index >= 0) {
    		for (int i = index; i < p->size; i++) {
    			p->elem[i+1] = p->elem[i];
    		}
    		p->elem[index] = temp;
    	}
     else {
    		p->elem[p->size] = temp;  //插入线性表的最后
    	}
    	p->size++;
    }
    
    void add(Polylist *a, Polylist *b, Polylist *c)
    {
    	int i, j;
    	for (i = 0, j = 0; i < a->size && j < b->size; ) {
    		Data t1 = a->elem[i], t2 = b->elem[j];
    		if (a->elem[i].exp == b->elem[j].exp) {
    			c->elem[c->size].exp = t1.exp;
    			c->elem[c->size++].coef = t1.coef + t2.coef;
    			i++;
    			j++;
    		} else if (a->elem[i].exp < b->elem[j].exp) {
    			c->elem[c->size++] = t1;
    			i++;
    		} else {
    			c->elem[c->size++] = t2;
    			j++;
    		}
    	}
    
    	while (i < a->size) {
    		c->elem[c->size++] = a->elem[i++];
    	}
    	while (j < b->size) {
    		c->elem[c->size++] = b->elem[j++];
    	}
    }
    
    void printPoly(Polylist *p)
    {
    	for (int i = 0; i < p->size; i++) {
    		if (p->elem[i].coef > 0) std::cout << "+";
    		std::cout << p->elem[i].coef << "x^" << p->elem[i].exp << " ";
    	}
    	std::cout << "\n";
    }
    main.cpp
    #include "Poly.h"
    int main()
    {
    	Polylist p1, p2,p3;
    	creatPoly(&p1);
    	printf("请输入第一个多项式的指数和系数\n");
    	int coef, exf;
    	while (std::cin >> exf >> coef) {
    		if (!exf && !coef) break;
    		insertItem(&p1, exf, coef);
    	}
    	printPoly(&p1);
    	printf("请输入第二个多项式的指数和系数\n");
    	creatPoly(&p2);
    	while (std::cin >> exf >> coef) {
    		if (!exf && !coef) break;
    		insertItem(&p2, exf, coef);
    	}
    	printPoly(&p2);
    	printf("多项式和为\n");
    	creatPoly(&p3);
    	add(&p1, &p2, &p3);
    	printPoly(&p3);
    	system("pause");
    	return 0;
    }




    展开全文
  • 数据结构-顺序表基本操作的实现(含全部代码) 版权声明:转载请注明出处,并附有原文链接。谢谢:) https://blog.csdn.net/lady_killer9/article/details/82695770 今天起开始编写数据结构中的各种...

    数据结构-顺序表基本操作的实现(含全部代码)

     

    版权声明:转载请注明出处,并附有原文链接。谢谢:) https://blog.csdn.net/lady_killer9/article/details/82695770

    今天起开始编写数据结构中的各种数据结构及其算法的实现。

    主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。

    今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。

    •     CreatList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    •     InitList(SqList &L) 参数:顺序表L 功能:初始化
    •     InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e
    •     ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素
    •     LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置
    •     PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出

     

    代码如下:

    /*
        Project: sequence_list(数据结构-顺序表) 
        Date:    2018/09/12
        Author:  Frank Yu
        CreatList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
        InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
        InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
        ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
        LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
        PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    */
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
        ElemType data[MaxSize];//顺序表元素
        int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList &L)
    {
        memset(L.data,0,sizeof(L));//初始化数据为0
        L.length=0;                //初始化长度为0
        return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreatList(SqList &L,int n)
    {
        if(n<0||n>MaxSize)false;//n非法
        for(int i=0;i<n;i++)
        {
            scanf("%d",&L.data[i]);
            L.length++;
        }
        return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList &L,int i,ElemType e)
    {
        if(i<1||i>L.length+1) //判断位置是否有效
         {
            printf("位置无效!!!\n");
            return false;
         }
        if(L.length>=MaxSize)//判断存储空间是否已满
        {
            printf("当前存储空间已满!!!\n");
            return false;
        }
        for(int j=L.length;j>=i;j--)//位置i及之后元素后移
        {
            L.data[j]=L.data[j-1];
        }
        L.data[i-1]=e;
        L.length++;
        return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList &L,int i)
    {
        if(i<1||i>L.length)
         {
            printf("位置无效!!!\n");
            return false;
         }
        for(int j=i;j<=L.length-1;j++)//位置i之后元素依次前移覆盖
        {
            L.data[j-1]=L.data[j];
        }
        L.length--;
        return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L,ElemType e)
    {
     for(int i=0;i<L.length;i++)//从低位置查找
        {
            if(L.data[i]==e)
                return i+1;
        }
     return 0;
     
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
        printf("当前顺序表所有元素:");
        for(int i=0;i<L.length;i++)
        {
            printf("%d ",L.data[i]);
        }
        printf("\n");
    }
    //创建顺序表函数
    void Create(SqList &L)
    {
        int n;bool flag;
        printf("请输入要创建的顺序表长度(>1):");
        scanf("%d",&n);
        printf("请输入%d个数(空格隔开):",n);
        flag=CreatList(L,n);
        if(flag){
            printf("创建成功!\n");
            PrintList(L);
        }
        else printf("输入长度非法!\n");
     
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
      int place;ElemType e;bool flag;
      printf("请输入要插入的位置(从1开始)及元素:\n");
      scanf("%d%d",&place,&e);
      flag=InsertList(L,place,e);
      if(flag) 
      {
        printf("插入成功!!!\n");
        PrintList(L);
      }
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
      int place;bool flag;
      printf("请输入要删除的位置(从1开始):\n");
      scanf("%d",&place);
      flag=ListDelete(L,place);
      if(flag) 
      {
        printf("删除成功!!!\n");
        PrintList(L);
      }
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
      ElemType e;int flag;
      printf("请输入要查找的值:\n");
      scanf("%d",&e);
      flag=LocateElem(L,e);
      if(flag) 
      {
        printf("该元素位置为:%d\n",flag);
      }
      else
          printf("未找到该元素!\n");
    }
    //菜单
    void menu()
    {
       printf("********1.创建    2.插入*********\n");
       printf("********3.删除    4.查找*********\n");
       printf("********5.输出    6.退出*********\n");
    }
    int main()
    {
     SqList L;int choice;
     InitList(L);
     while(1)
     {
      menu();
      printf("请输入菜单序号:\n");
      scanf("%d",&choice);
      if(6==choice) break;
      switch(choice)
      {
      case 1:Create(L);break;
      case 2:Insert(L);break;
      case 3:Delete(L);break;
      case 4:Search(L);break;
      case 5:PrintList(L);break;
      default:printf("输入错误!!!\n");
      }
     }
     return 0;
    }

     

    结果截图:

    插入结果截图

    删除结果截图
    查找结果截图
    输出结果截图

    2018-09-18更新 添加创建函数 菜单有改动

                                                                     

    更多数据结构与算法的实现:数据结构(严蔚敏版)与算法的实现(含全部代码)

    有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。

    转载于:https://www.cnblogs.com/yangf428/p/11253775.html

    展开全文
  • 这里我们实现顺序表的基本操作 1.构建顺序表 int InitList(SqlList *L,int List_Size) { L->elem=(int *)malloc(List_Size*sizeof(int)); //开辟一个大小为List_Size存储空间 if(!L->elem) return -1; ...
  • 今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。 //实现数组的以下操作,并编写程序验证你的操作。 int InputList(SeqList *L,int n); //输入n个整数存放到数组中 int ...
  • 线性表顺序存储结构是一种随机存取存储结构,高级语言中通常用数组来描述数据结构中顺序储存结构。 #define MAXSIZE 100 ...顺序表的初始化操作就是构造一个空的顺序表。 1.为顺序表L动态分配一个预定...
  • Description 建立具有10个元素的顺序表,并能对该表进行查找,插入,删除等基本操作
  • 操作算法中用到预定义常量和类型: #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef char ElemType; 线性表L初始化:
  • 知识准备 逻辑结构与存储结构区别 ...SqList L:指定义了一个SqList类型变量L,这里L是顺序表,SqList是顺序表L类型名。 从L中取成员: 若L为指针,即,SqList* L,取成员表示为, L->elem; L...
  • 顺序表基本操作的实现,这个程序中演示了顺序表的初始化、顺序表的插入、删除、查找以及输出等功能。使用c语言所写。
  • 顺序表的基本操作实现顺序表的基本操作实现顺序表的基本操作实现
  • 顺序表的基本操作实现

    千次阅读 2019-10-13 20:55:31
    2. 顺序表基本操作的实现 (1) 插入操作 (2) 删除操作 (3) 按值查找(顺序查找) 1. 顺序表的定义  线性表的顺序存储又称顺序表。它是一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑...
  • 顺序表基本操作的代码实现 初始化 静态分配方式 #include <stdio.h> #define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //存放数据元素 int length; //当前长度 }SqList; //顺序表...
  • 顺序表基本操作的代码实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,367
精华内容 1,746
关键字:

顺序表基本操作的实现