devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【实验一】数据结构：线性表_数据结构实验一线性表

作者：IT小白 | 2024-05-03 04:38:02

赞

踩

数据结构实验一线性表

实验1：顺序表

递增有序顺序表的插入

 已知顺序表L递增有序，将X插入到线性表的适当位置上，保证线性表有序。

输入格式: 第1行输入顺序表长度，第2行输入递增有序的顺序表，第3行输入要插入的数据元素X。

 输入样式：

5
1 3 5 7 9
6

输出格式: 对每一组输入，在一行中输出插入X后的递增的顺序表。

输出样式：

1,3,5,6,7,9,

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. #define TRUE        1
  5. #define FALSE       0
  6. #define OK          1
  7. #define ERROR       0
  8. #define INFEASIBLE  -1
  9. #define OVERFOLW    -2
  10. #define MAXSIZE     100
  11.  
  12. typedef int Status;             //定义Status函数
  13. typedef int SqElemType;
  14.  
  15. typedef struct List             //顺序表结构体
  16. {
  17.     SqElemType *num;
  18.     int length;  //长度
  19. }SqList;
  20.  
  21. Status InitSqList(SqList &L){                   //创建空顺序表
  22.     L.num = new SqElemType[MAXSIZE];
  23.     if(!L.num) exit(OVERFOLW);                  //分配失败
  24.     L.length = 0;           //长度初始值为0
  25.     return OK;    
  26. }
  27. int LocateElem(SqList L,SqElemType e){      //查找（要插入的位置i
  28.     int i;
  29.     for (i = 0; i < L.length; i++)
  30.     {
  31.         if (L.num[i] > e)               //从第一个开始比较e的值，找到位置i
  32.         {
  33.             break;
  34.         }
  35.     }
  36.     return i;
  37. }
  38. Status InsertSqList(SqList &L,SqElemType e){    //插入
  39.     int i,j;
  40.     j = LocateElem(L,e);
  41.     for (i = L.length-1; i >= j; --i)           //移动是后面的元素，所以从后面开始找
  42.     {       //下标是从0开始，所以要-1
  43.         L.num[i+1] = L.num[i];          //后移
  44.     }
  45.     L.num[j] = e;       //插入e
  46.     ++L.length;         //增表长
  47.     return OK;
  48. }
  49.  
  50. int main(){
  51.     SqList S;           //创建顺序表名为S结构体
  52.     SqElemType X;
  53.     int i;
  54.     InitSqList(S);      //初始化
  55.     scanf("%d",&S.length);
  56.     for (i = 0; i < S.length; i++)
  57.     {
  58.         scanf("%d",&S.num[i]);
  59.     }
  60.     scanf("%d",&X);
  61.     InsertSqList(S,X);
  62.     for (i = 0; i < S.length; i++){
  63.         printf("%d,",S.num[i]);
  64.     }
  65.     system("pause");    //防止窗口闪退，+头文件<stdlib.h>
  66.     return 0;
  67. }
  68.  
  69.  
  70.

实验2：链表

两个有序链表序列的交集

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。输出格式: 在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样式：

1 2 5 -1
2 4 5 8 10 -1

输出样式：

2 5

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. struct Node 
  4. {
  5.  	int data;
  6.  	struct Node *next;
  7. };
  8. struct Node *build();
  9. struct Node *operate(struct Node *a,struct Node *b);
  10. int main() 
  11. {
  12.  	struct Node *a,*b,*c;
  13.  	a=build();
  14.  	b=build();
  15.  	c=operate(a,b);
  16.  	if(!c)
  17.   		printf("NULL\n");
  18.  	while(c)
  19.  	{
  20.   		if(c->next==NULL)
  21.    			printf("%d",c->data);
  22.   		else
  23.    			printf("%d ",c->data);
  24.   		c=c->next;
  25.  	} 
  26. }
  27. struct Node *build()
  28. {
  29.  	int a;
  30.  	struct Node *head=NULL,*str=NULL;
  31.  	scanf("%d",&a);
  32.  	while(a!=-1)
  33.  	{
  34.   		struct Node *p=(struct Node*)malloc(sizeof(struct Node));
  35.   		p->data=a;
  36.   		p->next=NULL;
  37.   		if(head==NULL)
  38.    			head=p;
  39.   		else
  40.    			str->next=p;
  41.   		str=p; 
  42.   		scanf("%d",&a);
  43.  	}
  44.  	return head;
  45. }
  46. struct Node *operate(struct Node *a,struct Node *b)
  47. {
  48.  	struct Node *head=NULL,*str=NULL;
  49.  	while(a&&b)
  50.     	{
  51.         	if((a->data)<(b->data))
  52.            		a=a->next;
  53.         	else if((a->data)>(b->data))
  54.             		b=b->next;
  55.         	else if((a->data)==(b->data))
  56.         	{
  57.          		if(head==NULL)
  58.           			head=a;
  59.          		else
  60.           			str->next=a;
  61.          		str=a;        
  62.          		a=a->next;
  63.          		b=b->next;
  64.          		str->next=NULL;
  65.   		}
  66.  	}
  67.  	return head;
  68. }

实验3：栈

简单计算器

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。

计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S2存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：

1.    从 S1 中弹出两个数字，顺序为 n1 和 n2；

2.    从 S2 中弹出一个运算符 op；

3.    执行计算 n2 op n1；

4.    将得到的结果压回 S1。

直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。

输入格式： 输入首先在第一行给出正整数 N（1<N≤103），为 S1 中数字的个数。 第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N−1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出格式： 将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。

题目保证计算的中间和最后结果的绝对值都不超过 109。 如果执行除法时出现分母为零的非法操作，则在一行中输出：ERROR: X/0，其中 X 是当时的分子。然后结束程序。

输入样例 1：

5

40 5 8 3 2

/ * - +

输出样例 1：

2

输入样例 2：

5

2 5 8 4 4

* / - +

输出样例 2：

ERROR: 5/0

  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>         //mallo函数所需头文件
  4.  
  5. typedef struct SNode1{      //S1结构体
  6.     int num;
  7.     struct SNode1 *top;     //头指针
  8. }*numS1;
  9. typedef struct SNode2{      //S2结构体
  10.     char opr;               //运算符
  11.     struct SNode2 *top;
  12. }*oprS2;
  13.  
  14. //接口定义：
  15. numS1 CreateS1();
  16. oprS2 CreateS2();
  17. void PushNumS1(int e,numS1 S);
  18. void PushOprS2(char e,oprS2 S);
  19. int PopNumS1(numS1 S);
  20. char PopOprS2(oprS2 S);
  21.  
  22. //S1数字栈（ALL
  23. numS1 CreateS1(){           //创建栈S1
  24.     numS1 S;
  25.     S = (numS1)malloc(sizeof(numS1));   //动态分配内存空间
  26.     S->top = NULL;          //空栈（栈顶指针）
  27.     return S;
  28. }
  29.  
  30. void PushNumS1(int e,numS1 S){         //压栈数字--无需返回值，采用void
  31.     numS1 Sql;              //定义存放e的Sql
  32.     Sql = (numS1)malloc(sizeof(numS1));
  33.     Sql->num = e;
  34.     Sql->top = S->top;      //栈顶指针上移
  35.     S->top = Sql;           //新栈顶元素为Sql
  36. }
  37.  
  38. int PopNumS1(numS1 S){      //出栈（数字，int整型
  39.     int old_num;            //定义保存出栈数据的值
  40.     numS1 top_data;         //栈顶数据
  41.     top_data = S->top;      //把当前栈顶赋值给top_data
  42.     S->top = top_data->top;
  43.     old_num = top_data->num;
  44.     free(top_data);         //释放
  45.     return old_num;         //返回出栈的值
  46. }
  47.  
  48.  
  49. //S2运算符栈（ALL
  50. oprS2 CreateS2(){           //创建栈S2
  51.     oprS2 S;
  52.     S = (oprS2)malloc(sizeof(oprS2));
  53.     S->top = NULL;
  54.     return S;
  55. }
  56.  
  57. void PushOprS2(char e,oprS2 S){         //压栈运算符
  58.     oprS2 Sql;              //定义存放e的Sql
  59.     Sql = (oprS2)malloc(sizeof(oprS2));
  60.     Sql->opr = e;
  61.     Sql->top = S->top;      //栈顶指针上移
  62.     S->top = Sql;           //新栈顶元素为Sql
  63. }
  64.  
  65. char PopOprS2(oprS2 S){      //出栈（运算符
  66.     char old_opr;            //定义保存出栈数据的值
  67.     oprS2 top_data;         //栈顶数据
  68.     top_data = S->top;      //把当前栈顶赋值给top_data
  69.     S->top = top_data->top;
  70.     old_opr = top_data->opr;
  71.     free(top_data);         //释放
  72.     return old_opr;         //返回出栈的值
  73. }
  74.  
  75. int main(){
  76.     int N,i,number,n1,n2,sum;
  77.     char operator,op;      
  78.     numS1 S1;
  79.     oprS2 S2;
  80.     scanf("%d",&N);             //数字个数
  81.     S1 = CreateS1();            //栈赋值给S1，S1指向numS1
  82.     for (i = 0; i < N; i++)     //循环，入栈
  83.     {
  84.         scanf("%d",&number);
  85.         PushNumS1(number,S1);   //调用
  86.     }
  87.     getchar();                  //输入缓冲区
  88.     S2 = CreateS2();
  89.     for (i = 0; i < N-1; i++)
  90.     {
  91.         scanf("%c",&operator);
  92.         getchar();
  93.         PushOprS2(operator,S2);
  94.     }
  95.     for (i = 0; i < N-1; i++)  //大循环
  96.     {
  97.         n1 = PopNumS1(S1);      //取出N1
  98.         n2 = PopNumS1(S1);      //取出N2
  99.         op = PopOprS2(S2);      //取出运算符
  100.         if (n1 == 0 && op == '/') //除法，分母为0时
  101.         {
  102.             printf("ERROR: %d/0",n2);
  103.             return 0;
  104.         }
  105.         else{
  106.             switch (op)         //加减乘除运算
  107.             {
  108.                 case '+':
  109.                     sum = n2 + n1;
  110.                     break;
  111.                 case '-':
  112.                     sum = n2 - n1;
  113.                     break;
  114.                 case '*':
  115.                     sum = n2 * n1;
  116.                     break;
  117.                 case '/':
  118.                     sum = n2 / n1;
  119.                     break;
  120.             }
  121.             PushNumS1(sum,S1);  //得到的结果压回S1
  122.         }
  123.     }
  124.     printf("%d",sum);     //打印最终值
  125.     return 0;
  126. }
  127.

实验4：队列

银行业务队列简单模拟

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。

给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

输入格式: 输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式: 按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15

  1. #include <stdio.h>
  2. #include <malloc.h>         //动态存储分配头文件
  3. #include <stdlib.h>
  4.  
  5. //Status函数的返回值类型
  6. #define TRUE        1
  7. #define FALSE       0
  8. #define OK          1
  9. #define ERROR       0
  10. #define INFEASIBLE  -1
  11. #define OVERFLOW    -2
  12.  
  13. typedef int Status;         //定义Status
  14. typedef int QElemType;
  15. typedef struct QNode        //定义指针结构体
  16. {
  17.     QElemType Data;
  18.     struct QNode *Next;
  19. }QNode,*queuePtr;           //指针queuePtr指向QNode
  20. typedef struct Queue        //顺序队列
  21. {
  22.     queuePtr front;         //头指针
  23.     queuePtr rear;          //尾指针
  24. }SqQueue;
  25.  
  26. Status InitQueue(SqQueue &Q){                   //创建（初始化
  27.     Q.front = (QNode *)malloc(sizeof(QNode));   //动态分配空间给头结点
  28.     if(!Q.front) exit(OVERFLOW);    //超出，则分配失败
  29.     Q.front->Next = NULL;           //头结点指针指向空
  30.     Q.rear = Q.front;               //空队列
  31.     return OK;
  32. }
  33. Status EnQueue(SqQueue &Q,QElemType e){         //入队（rear队尾
  34.     queuePtr p;                     //新结点p
  35.     p = (QNode *)malloc(sizeof(QNode));
  36.     if(!p) exit(OVERFLOW);
  37.     p->Data = e;                    //e赋值给p指针的数据域
  38.     p->Next =NULL;                  //p指针域指向空
  39.     Q.rear->Next = p;               //p赋值给原队尾指针
  40.     Q.rear = p;                     //p为现在队尾
  41.     return OK;
  42. }
  43. Status DeQueue(SqQueue &Q,QElemType &e){    //出队
  44.     if(Q.front == Q.rear) return ERROR;     //队为空，返回error
  45.     queuePtr temp = Q.front->Next;          //头指针赋值给结点temp
  46.     e = temp->Data;
  47.     Q.front->Next = temp->Next;
  48.     if(Q.rear == temp) Q.rear = Q.front;    //如果删除的是最后一个元素
  49.     free(temp);             //释放
  50.     return OK;
  51. }
  52. Status QueueEmpty(SqQueue Q){       //判断是否为空队列
  53.     if (Q.front == Q.rear)
  54.     {
  55.         return TRUE;
  56.     }
  57.     else return FALSE;
  58. }
  59.  
  60. int main(){
  61.     SqQueue A;      //创建队列A，B
  62.     SqQueue B;
  63.     int n,m;
  64.     QElemType num,q;
  65.     InitQueue(A);   //创建空队列A,B
  66.     InitQueue(B);
  67.     scanf("%d",&n);   //输入顾客总数
  68.     for (int i = 0; i < n; ++i)     //输入指定数量的顾客编号
  69.     {
  70.         scanf("%d",&num);   //通过for循环以及判断奇偶，依次入队
  71.         if (num%2 == 1)     //取余（奇数
  72.         {
  73.             EnQueue(A,num);
  74.         }
  75.         else{
  76.             EnQueue(B,num); //偶数
  77.         }
  78.     }
  79.     m=0;        //用于是否输出空格
  80.     while (!QueueEmpty(A) && !QueueEmpty(B))    //1、都不为空
  81.     {
  82.         if (m==0)
  83.         {                           //奇数，输出两次
  84.             DeQueue(A,q);
  85.             printf("%d",q);
  86.             m++;
  87.             printf(" ");
  88.             DeQueue(A,q);
  89.             printf("%d",q);
  90.         }
  91.         else{
  92.             printf(" ");
  93.             DeQueue(A,q);
  94.             printf("%d",q);
  95.             m++;
  96.             printf(" ");
  97.             DeQueue(A,q);
  98.             printf("%d",q);
  99.         }
  100.         if (!QueueEmpty(B))         //偶数，输出一次
  101.         {
  102.             printf(" ");
  103.             DeQueue(B,q);
  104.             printf("%d",q);
  105.         }
  106.     }
  107.     while (!QueueEmpty(A) && QueueEmpty(B))     //全奇数，偶数为空
  108.     {
  109.         if (m==0)
  110.         {
  111.             DeQueue(A,q);
  112.             printf("%d",q);
  113.             m++;
  114.         }
  115.         else{
  116.             printf(" ");
  117.             DeQueue(A,q);
  118.             printf("%d",q);
  119.             m++;
  120.         }
  121.         
  122.     }
  123.     while (QueueEmpty(A) && !QueueEmpty(B))     //全偶数，奇数为空
  124.     {
  125.         if (m==0)
  126.         {
  127.             DeQueue(B,q);
  128.             printf("%d",q);
  129.             m++;
  130.         }
  131.         else{
  132.             printf(" ");
  133.             DeQueue(B,q);
  134.             printf("%d",q);
  135.             m++;
  136.         }
  137.         
  138.     }
  139.     printf("\n");
  140.     return 0;
  141. }

实验总结：（模板。。cv）

        通过本次实验，基本掌握线性表的基本知识 ，深入理解、掌握并灵活运用线性表。熟练掌握线性表的存储结构及主要运算的实现。通过实验学习到建立顺序表，并在顺序表上实现基本运算操作，已知顺序表L递增有序，将X插入到线性表的适当位置上，保证线性表有序 ， 建立链表，并在链表上实现基本运算操作，已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3，建立顺序栈，并在栈上实现基本运算操作 ，实现栈在简易计算器的应用 ，建立循环队列，并在队列上实现基本运算操作 ，实现银行业务队列的简单模拟。链表不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系。因此对线性表的插入、删除不需要移动数据元素，只需要修改“链”。

        通过本次实验，学会了线性表的逻辑结构特点和线性表抽象数据类型的描述方法 ；线性表的两类存储结构设计方法以及各自的优缺点；掌握线性表的基本知识 ；深入理解、掌握并灵活运用线性表；熟练掌握线性表的存储结构及主要运算的实现 ；掌握栈的定义、栈的逻辑结构特性和栈的基本运算；理解栈在表达式求值中的应用；  掌握队列的定义、队列的逻辑结构特性和栈的基本运算； 理解队列的应用。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/527826
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号