【Dev-c++】C语言数据结构实验——线性表

实验一 线性表

一、实验目的

    1、深刻理解线性结构的特点，以及在计算机内的两种存储结构。

    2、熟练掌握线性表的顺序存储结构和链式存储结构，及其它们的基本操作，重点掌握查找、插入和删除等操作。

二、实验要求

    1、认真阅读程序，将未完成的代码补全（红色部分）。

2、上机调试，并运行程序。

3、保存和截图程序的运行结果，并结合程序进行分析。

三、实验内容和基本原理

    1、实验1.1 顺序表的操作

    利用顺序表存储方式实现下列功能（见参考程序1）：

    1）通过键盘输入数据建立一个线性表，并输出该线性表。

    如，依次输入元素25,21,46,90,12,98。

    2）根据屏幕菜单的选择，进行数据的插入、删除和查找，并在插入或删除数据后，再输出线性表。如，在第2个位置上插入元素43，然后输出顺序表。删除顺序表第4个元素，输出改变的顺序表。

    3）在屏幕菜单中选择0，结束程序的运行。

    基本原理：在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，在把新元素插入到该位置。当要删除第i个元素时，只需将第i个元素之后的所有元素前移一个位置。

    2、实验1.2 链表的操作 （见参考程序2）

     利用链式存储的方式实现线性表的创建、插入、删除和查找等操作。

    1）请输入初始时链表长度，如输入5。

    如，依次输入元素abcdf，然后输出链表。

    2）删除一个元素，如输入c。

    3）插入一个元素，如输入e。

    4）按关键字查找元素。如输入e。

    5）按序号查找元素。如输入3。

    基本原理：在带头结点的单链表中第i（从1开始计数）个位置之后插入元素、创建带头结点的单链表、在带头结点的单链表中删除第i个位置的元素等，最后输出单链表的内容。

四、实验步骤

    1、顺序表的操作

    1）运行Visual c++6.0，创建一个c++源文件

    提示：选择菜单栏中的“文件”下拉菜单中的“新建”按钮，在弹出的对话框中，选择“文件”子菜单中的“C/C++ Source File”。选中“Add to project”复选框。然后给一个文件名，如“sy1”，并保存在“桌面/姓名学号/”。

    2）将参考程序复制到文档窗口，选择菜单栏中的“组建”下拉菜单中的“编译”选项，在弹出的对话框中选择“是”。

    3）将未完成的代码补充完整，然后选择菜单中的“组建”下拉菜单中的“执行”，或者直接点击工具栏中的“ ”进行连接，调试和运行。

    4）运行程序，并检查插入、删除和查找等操作是否有误，正确后截图到Word文档中指定位置。

​​​​​​​ ​​​​​ 

图1

    说明：当程序运行错误时，如图2所示，查看组建窗口，双击出错部分（单击窗口然后滑动查看），逐条更改直到程序运行无误。

                     ​​​​​​​ 

图2

//参考程序1/       }       while(k!=0);       printf("\n              按回车键，返回...\n");       ch=getchar();}//建立线性表void creat_list(SqList *L){       int i;       printf("请输入线性表的长度: ");       scanf("%d",&L->length);       for(i=0;ilength;i++)       {              printf("数据 %d =",i);       scanf("%d",&(L->a[i]));}}//输出线性表void out_list(sqlist L){       int i;       for(i=0;i<=L.length-1;i++)              printf("%10d",L.a[i]);}//在线性表的第i个位置插入元素evoid insert_sq(SqList *L,int i,ElemType e){       int j;       if(L->length==MAXSIZE)              printf("线性表已满!\n");       else {              if(i<1||i>L->length+1)       printf("输入位置错!\n");              else {              for(j=L->length-1;j>=i-1;j--)                     L->a[j+1]=L->a[j];L->a[i-1]=e;               L->length++;              }       }}//删除第i个元素，返回其值ElemType delete_sq(SqList *L,int i){       ElemType x;       int j;       if(L->length==0)              printf("空表!\n");       else if(i<1||i>L->length)       {              printf("输入位置错！\n");              x=-1;       }       else       {              x=L->a[i-1];              for(j=i;j<=L->length-1;j++)L->a[j-1]=L->a[j];               L->length--;       }       return(x);}//查找值为e的元素，返回它的位置int locat_sq(SqList L,ElemType e){       int i=0;       while((i<=L.length)&&(L.a[i]!=e) ) i++;       if(i<=L.length-1)              return(i+1);}

    2、链表的操作。

   同顺序表一样。要求读懂程序，然后将未完成的代码补全（红色部分）。

//参考程序2/     free(q);           //释放该元素空间 return True;}BOOL ListFind_keyword(LinkList v,char e,int &i){//在单链表中查找关键字为e的元素，成功返回//True,并用i返回该元素位置， //失败返回False i=1; LinkList p; p=v->next; while((p->data!=e)&&(p->next!=NULL))//p指//针指向下一个，直到    {p=p->next;  i++;}                        //找到或到链表尾为止 if(p->data!=e)                      //该元//素在链表中不存在     return False; else return True;}BOOL ListFind_order(LinkList v,char &e,int i){//在单链表中查找第i个元素，成功返回True，//并用e返回该元素值， //失败返回False LinkList p; int j=0; p=v; while((p->next!=NULL)&&(jnext;++j;} if(j!=i) return False; //查找失败 else {e=p->data;       //查找成功，用e取得//该元素值       return True;      }}void ListPrint(LinkList v)  {//显示链表所有元素 LinkList q; q=v->next; printf("链表所有元素:"); while(q!=NULL)   {printf("%c ",q->data);q=q->next;} printf("\n");}.

来源地址：https://blog.csdn.net/m0_52474147/article/details/125955952