数据结构实验报告_顺序表的操作

一 .实验内容

1.Description

建立一个顺序表，然后在已建好的顺序表上实现顺序表插入和删除等基本操作。最后输出最终结果。

要求：Time Limit:1000MS  Memory Limit:65536K
2.eg.Input
有多组测试数据，每组数据由三部分组成。第一部分包含两个整数n(n<=1000）和m(m<=1000)，n表示第二部分包含n个整数，m表示第三部分包含m个操作。操作项的格式有：insert i x和delete i。insert i x 表示在第i个位置插入数字x，delete i表示删除第i个元素。当n和m同时为0时结束。

Output

对于每组数据，按顺序输出顺序表中的元素。输出结果占一行。

Sample Input

4 5

2 3 4 5

insert 2 6

delete 4

insert 2 9

insert 1 100

delete 4

Sample Output

100 2 9 3 5

二.实验源程序

#include <stdio.h>

#include <stdlib.h>

# define M 100

# define N 10

typedef struct {

    int *elem;

       int length;

       int size;

}SqList;

void InitList(SqList &L,int n){

    L.elem = (int *)malloc(M * sizeof(int));

       L.length = n;  //空间长度为n

       L.size = 100;  //初始存储容量

}

void show(SqList L){

       for(int i=0;i<L.length;i++)

              printf("%d  ",L.elem[i]);

       printf("\n");

       return;

}

void InsertList(SqList &L, int i, int e){

    if (i<1||i>L.length+1)

           return;  //i值不合法

    if (L.length == L.size) { //当前存储空间已满，增加分配

           int *newbase;

              newbase = (int *)realloc(L.elem,(L.size +N)* sizeof(int));

              L.elem = newbase;  //新基址

              L.size += N;   //增加出差容量

    }

       for (int j = L.length;j>=i;j--){

           L.elem[j] = L.elem[j-1];

       }

       L.elem[i-1] = e;

       L.length++;  //表长增1

       return;

}

void DeleteList(SqList &L, int i){

    if (i<1||i>L.length)

           return;//i值不合法

       for (int j = i; j<L.length;j++){

           L.elem[j-1] = L.elem[j];

       }

       L.length--; //表长减1

       return;

}

void main(void){

    int n,m,i,e;

       char s[7];

       SqList list;

      

       while (printf("\n输入数据n m\n")&&scanf("%d %d",&n,&m)&&(n||m)){

           InitList(list,n);

              printf("\n输入%d个整数\n",n);

              for (int j=1; j<=n; j++)

                   scanf ("%d",&list.elem[j-1]);

              printf("\n输入数据insert i x或delete i\n");

              for (int k=0;k<m;k++){

                  scanf("%6s %d",&s,&i);

                     if (s[0]=='i'){

                         scanf("%d",&e);

                            InsertList(list,i,e);

                     }

                     else if (s[0]=='d')

                         DeleteList(list,i);

              }

       show(list);

       }

}

四..实验结果

（1）

(2)

 

第二篇：数据结构实验一顺序表问题及实验报告模板 - Copy

实验一 顺序表问题

【实验报告】

《数据结构与算法》实验报告一

学院： 计算机与信息学院

学号：

日期： 班级： 姓名： 程序名：

一、上机实验的问题和要求：

顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：

1. 从键盘输入10个整数，产生顺序表，并输出结点值。

调试数据：9 8 7 6 5 4 3 2 1

2. 从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到，

则显示“找不到”。

调试数据：第一次输入 11，第二次输入3

3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插

入在对应位置上，输出顺序表所有结点值，观察输出结果。

调试数据：第一次insert "11" after "6" ， 第二次insert "86" at "2"

4. 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。

调试数据：第一次delete the number at "2" ，第二次delete value "9"

注意：顺序表输出表现形式如下（实验报告上为截图）：

顺序表：

第一题

Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题

找不到

6

第三题

insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

第四题

delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

二、源程序及注释：

以下程序仅供参考，其结果不代表本实验要求。学生可输入以下程序，调试并运行之，分析输出结果，然后结合书本上的算法进行修改，完成上述实验内容，请实验完成之后，把正确的程序复制在此处。程序一：

public class Searching {

private static final int NONE = -1;

public static int linearSearch1(Object[] a,int left, int right, Object val)

{

for (int i = left; i <= right; i++)

if (val.equals(a[i]))

return i;

return NONE;

}

public static int linearSearch2(Comparable[] a, int left, int right, Comparable val)

{

for (int i = left; i <= right; i++)

{ int comp = val.compareTo(a[i]);

if (comp == 0)

return i;

else if (comp < 0)

break;

}

return NONE;

}

public static int binarySearch(Comparable[] a,

int left, int right, Comparable val)

{

int l = left, r = right;

while (l <= r) {

int m = (l + r) / 2;

int comp = val.compareTo(a[m]);

if (comp == 0) return m;

else if (comp < 0) r = m - 1;

else l = m + 1;

}

return NONE;

}

public static void main(String[] args) {

String[] word1 = {"dog", "cat", "rat", "pig", "fox", "eel"};

int left1 = 0, right1 = word1.length - 1;

String[] word2 = {"cat", "dog", "eel", "fox", "pig", "rat"};

int left2 = 0, right2 = word2.length - 1;

String[] testcases = {"ant", "bat", "cat", "dog", "eel","fox", "hen", "pig", "rat"}; for (int t = 0; t < testcases.length; t++) {

String target = testcases[t];

System.out.println(target

+ " " + linearSearch1(word1, left1, right1, target) + " "

+ linearSearch2(word2, left2, right2, target)

+ " " + binarySearch(word2, left2, right2, target));

}

}

}

程序二

public class Searching {

private static final int NONE = -1;

public static int linearSearch1(Object[] a,int left, int right, Object val) {

for (int i = left; i <= right; i++)

if (val.equals(a[i]))

return i;

return NONE;

}

public static int linearSearch2(Comparable[] a, int left, int right, Comparable val) {

for (int i = left; i <= right; i++)

{ int comp = val.compareTo(a[i]);

if (comp == 0)

return i;

else if (comp < 0)

break;

}

return NONE;

}

public static int binarySearch(Comparable[] a,

int left, int right, Comparable val)

{

int l = left, r = right;

while (l <= r) {

int m = (l + r) / 2;

int comp = val.compareTo(a[m]);

if (comp == 0) return m;

else if (comp < 0) r = m - 1;

else l = m + 1;

}

return NONE;

}

public static void main(String[] args) {

String[] word1 = {"dog", "cat", "rat", "pig", "fox", "eel"};

int left1 = 0, right1 = word1.length - 1;

String[] word2 = {"cat", "dog", "eel", "fox", "pig", "rat"};

int left2 = 0, right2 = word2.length - 1;

String[] testcases = {"ant", "bat", "cat", "dog", "eel","fox", "hen", "pig", "rat"}; for (int t = 0; t < testcases.length; t++) {

String target = testcases[t];

System.out.println(target

+ " " + linearSearch1(word1, left1, right1, target) + " "

+ linearSearch2(word2, left2, right2, target)

+ " " + binarySearch(word2, left2, right2, target));

}

}

}

三、运行输出结果：

四、调试和运行程序过程中产生的问题及采取的措施：

相关推荐

专栏推荐