当前位置：文档之家› 数据结构上机作业——顺序表

数据结构上机作业——顺序表

一、实验目的

理解线性表的逻辑结构、顺序存储结构和数据操作，熟练运用Java语言实现线性表的基本操作，分析各种操作算法特点和时间复杂度。

熟悉JCreator调试程序的方法。

二、主要内容

1、按照教材P37编写顺序表类，在SeqList中增加main方法或者编写一个测试类测试各方法的正确性。

说明：注意package路径，导入LList，过程参考如下：

1）创建工程：File->New->Project，选择Empty Project，输入工程名称及路径，点击完成。

2）鼠标指向工程ds，单击鼠标右键，在快捷菜单中选择Add->New Folder，新建文件夹dataStructure，在dataStructure新建文件夹linearList。

3）鼠标指向文件夹linearList，单击鼠标右键，在快捷菜单中选择Add Existing Files，选择LList.java（教育在线例程中）。

4）鼠标指向文件夹linearList，单击鼠标右键，，在快捷菜单中选择New Class，在Class Wizard中输入相关内容，类名：SeqList。

5）程序编辑结束后，执行Build->Build File菜单命令，编译Java程序，系统在Build Output区域输出错误信息，编译通过后将生成字节码文件（.class）。

6）测试：

方法1 在SeqList类中增加main方法，例如

public static void main(String args[]){

SeqList list=new SeqList(7);

list.add("091202");

list.add("091203");

list.add("091205");

list.add("091206");

System.out.println(list.toString());

list.add(2,"091204");

System.out.println(list.toString());

list.remove(3);

System.out.println(list.toString());

}

修改main方法，完成相应测试。

方法2 新建一个测试类，在main方法中测试你所编写的各方法。例如

import dataStructure.linearList.*;

import java.util.Scanner;

public class SeqListTest {

public static void main(String args[]){

SeqList list=new SeqList(7);

Scanner scanner=new Scanner(System.in);

System.out.println("请输入线性表长度");

int n=scanner.nextInt();

System.out.println("请依次输入各元素");

int e;

for(int i=0;i

e=scanner.nextInt();

list.add(new Integer(e));

}

System.out.println(list.toString());

}

修改main方法，完成相应测试。

7）运行：执行Run->Run File，若没有错误，系统将运行结果显示在General Output 区域。

8）调试

2、在SeqList类中增加下列成员方法。

1）public void concat(SeqList list)

说明：将指定顺序表list链接在当前顺序表之后

测试数据：第一组：(1，2，3，4，5)，()

第二组：()，(1，2，3，4，5)

第三组：(1，2，3，4，5)，(6，7，8)

2）public boolean remove(T element)

说明：移去首次出现的指定对象

测试数据：第一组：(1，2，3，4，5)，删除6

第二组： (1，2，3，4，5)，删除1

第三组： (1，2，3，4，5，5)，删除5

3）public boolean replace(Object obj, T element)

说明：将元素值为obj的结点值替换为element，若替换成功返回true，否则返回false

测试数据：第一组：(1，2，3，4，5)，将6替换为4

第二组： (1，2，3，4，5)，将3替换为30

第三组： (1，2，3，4，5，5)，将5替换为30

3、（选做）设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。

要求：测试数据使用一组随机数

提示：对象比较大小方法见例1.4；可继承SeqList类

三、要求

1、上机前请先理清程序思路，复杂程序的主要算法应事先写出。

2、源程序请自己保存，以备抽查。

3、上机后一周内交上机报告，包括源程序、测试数据、运行结果和上机调试心

得。

答案：

1.方法1：

package dataStructure.linearList;

import java.util.Scanner;

class SeqList {

private Object[]element;

private int len;

public SeqList(int size){

this.element=new Object[size];

this.len=0;

}

public SeqList(){

this(64);

}

public boolean isEmpty(){

return this.len==0;

}

public int length(){

return this.len;

}

public T get(int i){

if(i>=0&&i

return(T)this.element[i];

return null;

}

public void set(int i,T x){

if(x==null)

return;

if(i>=0&&i

this.element[i]=x;

else

throw new IndexOutOfBoundsException(i+"");

}

public String toString(){

String str="(";

if(this.len>0)

str+=this.element[0].toString();

for(int i=1;i

str+=","+this.element[i].toString();

return str+")";

}

public void insert(int i,T x){

if(x==null)

return;

if(this.len==element.length){

Object[]temp=this.element;

this.element=new Object[temp.length*2];

for(int j=0;j

this.element[j]=temp[j];

}

if(i<0)

i=0;

if(i>this.len)

i=this.len;

for(int j=this.len-1;j>=i;j--)

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

}

public void append(T x){

insert(this.len,x);

}

public T remove(int i){

if(this.len==0||i<0||i>=this.len)

return null;

T old=(T)this.element[i];

for(int j=i;j

this.element[j]=this.element[j+1];

this.element[this.len-1]=null;

this.len--;

return old;

}

public void removeAll(){

this.len=0;

}

public static void main(String args[]){

SeqList list=new SeqList(7);

list.append("091202");

list.append("091203");

list.append("091205");

list.append("091206");

System.out.println(list.toString());

list.insert(2,"091204");

System.out.println(list.toString());

list.remove(3);

System.out.println(list.toString());

}

运行结果：

--------------------Configuration: ds - JDK version 1.6.0_31 - --------------------

(091202,091203,091205,091206)

(091202,091203,091204,091205,091206)

(091202,091203,091204,091206)

Process completed.

方法2：

package dataStructure.linearList;

import java.util.Scanner;

class SeqListTest {

private Object[]element;

private int len;

public SeqListTest(int size){

this.element=new Object[size];

this.len=0;

}

public SeqListTest(){

this(64);

}

public boolean isEmpty(){

return this.len==0;

}

public int length(){

return this.len;

}

public T get(int i){

if(i>=0&&i

return(T)this.element[i];

return null;

}

public void set(int i,T x){

if(x==null)

return;

if(i>=0&&i

this.element[i]=x;

else

throw new IndexOutOfBoundsException(i+"");

}

public String toString(){

String str="(";

if(this.len>0)

str+=this.element[0].toString();

for(int i=1;i

str+=","+this.element[i].toString();

return str+")";

}

public void insert(int i,T x){

if(x==null)

return;

if(this.len==element.length){

Object[]temp=this.element;

this.element=new Object[temp.length*2];

for(int j=0;j

this.element[j]=temp[j];

}

if(i<0)

i=0;

if(i>this.len)

i=this.len;

for(int j=this.len-1;j>=i;j--)

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

}

public void append(T x){

insert(this.len,x);

}

public static void main(String args[]){

SeqList list=new SeqList(7);

Scanner scanner=new Scanner(System.in);

System.out.println("请输入线性表长度");

int n=scanner.nextInt();

System.out.println("请依次输入各元素");

int e;

for(int i=0;i

e=scanner.nextInt();

list.append(new Integer(e));

}

System.out.println(list.toString());

}

运行结果：

--------------------Configuration: ds - JDK version 1.6.0_31 - --------------------

请输入线性表长度

请依次输入各元素

1 3 5

2 4

(1,3,5,2,4) Process completed.

错误1：

错误分析：

没有声明T，所以找不到符号

错误2：

错误分析：

数组下标越界

54行处代码应为

for(int j=this.len-1;j>=i;j--)

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

错误3：

错误分析：

在调用insert方法时只填写了一个参数

而insert方法是(int i,T x),所以此时应调用append方法

(1)将指定顺序表list链接在当前顺序表之后

package dataStructure.linearList;

import java.util.Scanner;

class SeqListTest {

private Object[]element;

private int len;

public SeqListTest(int size){

this.element=new Object[size];

this.len=0;

}

public SeqListTest(){

this(64);

}

public boolean isEmpty(){

return this.len==0;

}

public int length(){

return this.len;

}

public T get(int i){

if(i>=0&&i

return(T)this.element[i];

return null;

}

public void set(int i,T x){

if(x==null)

return;

if(i>=0&&i

this.element[i]=x;

else

throw new IndexOutOfBoundsException(i+"");

}

public String toString(){

String str="(";

if(this.len>0)

str+=this.element[0].toString();

for(int i=1;i

str+=","+this.element[i].toString();

return str+")";

}

public void insert(int i,T x){

if(x==null)

return;

if(this.len==element.length){

Object[]temp=this.element;

this.element=new Object[temp.length*2];

for(int j=0;j

this.element[j]=temp[j];

}

if(i<0)

i=0;

if(i>this.len)

i=this.len;

for(int j=this.len-1;j>=i;j--)

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

}

public void append(T x){

insert(this.len,x);

}

public static void concat(SeqList list,SeqList list1){ int n=list1.length();

for(int i=0;i

list1.insert(i+n,list.get(i));

}

System.out.print(list1.toString());

}

public static void main(String args[]){

SeqList list=new SeqList(7);

SeqList list1=new SeqList(7);

Scanner scanner=new Scanner(System.in);

list.append("1");

list.append("2");

list.append("3");

list.append("4");

list.append("5");

list1.append(7);

list1.append(8);

list1.append(9);

concat(list1,list);

}

运行结果：

--------------------Configuration: da - JDK version 1.6.0_13 - --------------------

(1,2,3,4,5,7,8,9)

Process completed.

错误：

无法将 dataStructure.linearList.SeqListTest 中的insert(int,T) 应用于 (int,https://www.doczj.com/doc/4a7680398.html,ng.Object)

this.insert(i+5,list.get(i));

错误分析:

应将SeqList list=new SeqList(7);改为SeqList list1=new SeqList(7); ^

（2）移去首次出现的指定对象

package dataStructure.linearList;

import java.util.Scanner;

class SeqList {

private Object[]element;

private int len;

public SeqList(int size){

this.element=new Object[size];

this.len=0;

}

public SeqList(){

this(64);

}

public boolean isEmpty(){

return this.len==0;

}

public int length(){

return this.len;

}

public T get(int i){

if(i>=0&&i

return(T)this.element[i];

return null;

}

public void set(int i,T x){

if(x==null)

return;

if(i>=0&&i

this.element[i]=x;

else

throw new IndexOutOfBoundsException(i+""); }

public String toString(){

String str="(";

if(this.len>0)

str+=this.element[0].toString();

for(int i=1;i

str+=","+this.element[i].toString();

return str+")";

}

public void insert(int i,T x){

if(x==null)

return;

if(this.len==element.length){

Object[]temp=this.element;

this.element=new Object[temp.length*2];

for(int j=0;j

this.element[j]=temp[j];

}

if(i<0)

i=0;

if(i>this.len)

i=this.len;

for(int j=this.len-1;j>=i;j--)

this.element[j+1]=this.element[j];

this.element[i]=x;

this.len++;

}

public void append(T x){

insert(this.len,x);

}

public T Remove(int i){

if(this.len==0||i<0||i>=this.len)

return null;

T old=(T)this.element[i];

for(int j=i;j

this.element[j]=this.element[j+1];

this.element[this.len-1]=null;

this.len--;

return old;

}

public boolean remove(T x){

int i=0;

while(element[i]!=x&&i

i++;

}

if(element[i]==x&&i

this.Remove(i);

return true;

}

return false;

}

public void removeAll(int n){

this.len=0;

}

public static void main(String args[]){

SeqList list=new SeqList(7);

list.append("1");

list.append("2");

list.append("3");

list.append("4");

list.append("5");

System.out.println(list.toString());

list.remove("5");

System.out.println("删除后：");

System.out.print(list.toString());

}

运行结果：

--------------------Configuration: da - JDK version 1.6.0_13 - -------------------- (1,2,3,4,5,5)

删除后：

(1,2,3,4,5)

Process completed.

数据结构顺序表真题

第二章复习题本章重点掌握：线性结构特点，顺序存储结构和链式存储结构特点。 1.在顺序表中插入或删除一个元素，需要平均移动( 一半 )元素，具体移动的元素个数与( 插入或删除的位置 )有关。插入时平均次数（n/2 ）,删除时平均次数（(n-1)/2 ）。 2.有一个含头结点的循环链表，头指针为 head, 则其为空的条件是：( C ) A)head==NULL B)head->next==NULL C)head->next==head 3.在长度为 n 的顺序表的第 i 个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：( A ) A) n – i + 1 B) n – i C) i D) i – 1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C ) A)顺序表B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表D) 单链表 5.设单链表中结点的结构为（data, link）。已知指针 q 所指结点是指针 p 所指结点的直接前驱，若在*q 与*p 之间插入结点*s，则应执行下列哪一个操作？（ B ） A)s->link = p->link;p->link = s;(B) q->link = s;s->link = p; (C) p->link = s->link;s->link = p;(D) p->link = s;s->link = q; 6.设单链表中结点的结构为（data, link）。已知指针 p 所指结点不是尾结点，若在*p 之后插入结点*s，则应执行下列哪一个操作？（B）

A)s->link = p;p->link = s;(B) s->link = p->link;p->link = s; (C) s->link = p->link;p = s;(D) p->link = s;s->link = p; 7.设单链表中结点的结构为（data, link）。若想摘除结点*p 的直接后继，则应执行下列哪一个操作？（A） (A) p->link = p->link->link; (B) p = p->link;p->link = p->link->link; (C) p->link = p->link;(D) p = p->link->link; 8.设单循环链表中结点的结构为（data, link），且 rear 是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？（D） (A)s = rear;rear = rear->link;delete s; (B)rear = rear->link;delete rear; (C)rear = rear->link->link;delete rear; (D)s = rear->link->link;rear->link->link = s->link; delete s; （rear 指向尾结点，rear->link->link 指向第一个结点，第一个结点变为原来的第二个结点） 9.设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针 p 所指结点之后插入指针 s 所指结点，则应执行下列哪一个操作？( D )

华农数据结构上机实验答案

数据结构上机答案 1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int typedef struct { int *elem,length,listsize; }SqList; int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } int Load_Sq(SqList &L) { int i; if(L.length==0) printf("The List is empty!"); else { printf("The List is:"); for(i=0;iL.length+1) return ERROR; ElemType *newbase,*q,*p; if(L.length>=L.listsize)

{ newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size of(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; } int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a)

国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷3 (总分：60.00，做题时间：90分钟) 一、选择题(总题数：30，分数：60.00) 1.在最坏情况下（分数：2.00） A.快速排序的时间复杂度比冒泡排序的时间复杂度要小 B.快速排序的时间复杂度比希尔排序的时间复杂度要小 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小√ D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的解析：解析：按平均时间将排序分为四类：①平方阶(O(n 2 ))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(n。log2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。 2.在深度为7的满二叉树中，度为2的结点个数为（分数：2.00） A.64 B.63 √ C.32 D.31 解析：解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n 0 =2 m-1 (其中m为二叉树的深度)。本题的度为0的结点个数n 0 =2 7-1 =2 6 =64。因此，度为2的结点数n 2 =n 0 -1=63。所以选项B正确 3.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（分数：2.00） A.30 B.20 C.m-19 √ D.m-20 TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；当压入第二个元素时，TOP指针指向 1n+1．2=m．1；…以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 4.算法空间复杂度的度量方法是（分数：2.00） A.算法程序的长度 B.算法所处理的数据量 C.执行算法所需要的工作单元 D.执行算法所需要的存储空间√ 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。 5.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00） A.4 √ B.6 C.m-5

数据结构上机实验答案

《数据结构实验指导书》答案实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include int fun(int *a, int *b) { if (*a*(*b)>0) return(1); else return(0); } main() { int x,y; scanf("%d%d",&x,&y); if (fun(&x,&y)) printf("yes\n"); else printf("no"); } 2、计算1+2+3+……+100，要求用指针进行设计。即设计函数int fun(int *n)实现求 1+2+3+……+*n，在主函数中输入、调用、输出结果。 #include int fun(int *n) { int i,sum=0; for (i=1;i<=*n;i++) sum+=i; return(sum); } main() { int x,sum; scanf("%d",&x); printf("the sum is %d\n",fun(&x)); } 3、函数的功能是求数组a中最大数的位置（位序号）。在主函数中输入10个整数、调用函

数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i*max) max=a+i; return(max-a); } main() {int a[N],maxi; input(a,N); maxi=fun(a,N); printf("\n the max position is %d\n",maxi); } 4、请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a 中所有奇数之和和所有偶数之和。形参n给出数组中数据的个数；利用指针odd和even分别返回奇数之和和偶数之和。在主函数中输入10个整数、调用函数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i

数据结构实现顺序表的各种基本运算(20210215233821)

实现顺序表的各种基本运算一、实验目的了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。二、实验内容编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表三、算法思想与算法描述简图

主函数main

四、实验步骤与算法实现 #in clude #in clude #defi ne MaxSize 50 typedef char ElemType; typedef struct {ElemType data[MaxSize]; in t le ngth; void In itList(SqList*&L)〃初始化顺序表 L {L=(SqList*)malloc(sizeof(SqList)); L->le ngth=0; for(i=0;ile ngth;i++) prin tf("%c ",L->data[i]); } void DestroyList(SqList*&L)〃 {free(L); } int ListEmpty(SqList*L)〃 {retur n( L->le ngth==O); } int Listle ngth(SqList*L)〃 {return(L->le ngth); } void DispList(SqList*L)〃 {int i; 释放顺序表 L

数据结构上机例题及答案

习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else

{p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); }

经典数据结构上机题_答案解析

数据结构上机实验题目实验一线性表的顺序存储结构实验学时 2学时背景知识:顺序表的插入、删除及应用。目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #include

#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i

数据结构实验2.1顺序表

附页（实验2-1代码）：头文件“DEFINE2-1.h”： #define MaxSize 10 typedef struct { char data[MaxSize]; int length; }SqList; #include #include #include"DEFINE2-1.h" void InitList(SqList * &L) //初始化线性表 { L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间L->length = 0; //置空线性表长度为0 } bool ListInsert(SqList *&L, int i, char e) //插入数据元素 { int j; if (i<1 || i>L->length + 1) return false; //参数错误是返回false I--; //将顺序表逻辑序号转换为物理序号for (j = L->length; j>i; j--) //将data[i]及后面元素后移一个位置L->data[j] = L->data[j - 1]; L->data[i] = e; //插入元素e L->length++; //顺序表长度+1 return true; //成功插入返回true } void DispList(SqList *L) //输出线性表L { int i; for (i = 0; ilength; i++) //扫描顺序表输出各元素值printf("%3c", L->data[i]); printf("\n\n"); } int ListLength(SqList *L) //求线性表L的长度 { return (L->length); }

数据结构上机答案(c语言版)

实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。代码如下： 1.#include #include #include void main() { char x; struct node //定义个结构node { char c; struct node *next; }; struct node *head,*pb,*pf,*p,*s,*t; //定义指针 printf("请输入字符串，按Enter结束！\n"); for(int i=0;x!='\n';i++) { pb=(struct node *)malloc(sizeof(struct node));//动态分配n字节的内存空间 scanf("%c",&pb->c); //输入字符 x=pb->c; if(i==0){ //输入的首个字符作为头结点pf head=pb; pf=head;} else if(pb->c!='\n'){ //如果输入的是Enter，输入终止，否则把字符依次存入链表 pf->next=pb; //把输入的字符pb存在pf后，pb后为空 pb->next=NULL;

实验一数据结构顺序表的插入和删除

实验一顺序表的操作 1. 实验题目：顺序表的操作 2.实验目的和要求： 1)了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并 )。 2)通过在 Turbo C ( WinTc ，或 visual stdio6 )实现以上操作的 C 语言代码。 3)提前了解实验相关的知识(尤其是 C 语言)。 3.实验内容：(二选一) 1) 顺序表的插入算法, 删除算法, 顺序表的合并算法 2) 与线性表应用相关的实例( 自己选择具体实例) 4.部分参考实验代码： ⑴ 顺序表结构的定义： #include #define MAXLEN 255 typedef int ElemType; typedef struct { ElemType elem[MAXLEN]; int length; }sqList; ⑵ 顺序表前插(在第i 号元素前插入一个新的元素) int ListInsert(sqList *la,int i,int x) { int j; if(i<0||i>la-> length +1) { printf( “ n the value of i is wrong! ” ); return 0; } if(la-> length +1>=MAXLEN) { printf( “ n overflow! ” ); return 0; }

. for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length ++; return 1; } ⑶ 顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length ) { printf( “ return 0; n”); } for(i;i length;i++) la->list[i-1]=la->list[i]; la-> length --; return 1; } 5.附录：实验预备知识： ⑴ 复习 C 语言中数组的用法。 ⑵ 了解线性表和顺序表的概念，顺序表的定义方法；线性表是n 个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。在 C 语言中，顺序表是用数组来实现的。 ⑶ 掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和合并的算法。在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出未查到提示）。在实现插入的时候，首先要判断该顺序表是否为满，如为满则报错（此时要注意：顺序表是用数组来实现的，它不能随机分配空间）；如不为满，则需判断要插入的位置是否合法（例如：如果一个线性表的元素只有10 个，而要在第0 个元素前插入或在第 11 个元素后插入就为不合法）。其次要注意是前插还是后插，两

数据结构上机考试题

注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。哈夫曼树时间限制: 100 second 内存限制: 100 Kb 描述构造哈夫曼树（最优二叉树）输入输入n个结点每个结点的权值输出构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码

数据结构上机考试试题

数据结构上机考试试题（C++语言版）考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。考核成绩评分标准：所选3个题目全部编写出程序并调试通过：优所选3个题目全部编写出程序，但只有2个上机调试通过：良所选3个题目全部编写出程序，但只有1个上机调试通过：及格所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。考核试题： 1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作：（1）向线性表的表头、表尾或合适位置插入元素（2）对线性表按升序或降序输出 2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作：（1）从单链表中查找指定元素（2）返回单链表中指定序号的结点值 3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作：（1）按任中序遍历次序输出二叉树中的所有结点（2）求二叉树的叶子数 4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。 #include<> #include<> #include"" //初始化线性表 void InitList(LinearList& L, int ms) { =new ElemType[ms]; if(! { cerr<<"Memory allocation failure!"<

顺序表的应用数据结构实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

大学数据结构实验报告课程名称数据结构实验第（三）次实验实验名称顺序表的应用学生姓名于歌专业班级学号实验成绩指导老师（签名）日期2018年9月30日一、实验目的 1．学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。 2．掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。 3．掌握对多函数程序的输入、编辑、调试和运行过程。二、实验要求 1．预习C语言中结构体的定义与基本操作方法。 2．对顺序表的每个基本操作用单独的函数实现。 3．编写完整程序完成下面的实验内容并上机运行。 4．整理并上交实验报告。三、实验内容： 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能：（1）根据指定学生个数，逐个输入学生信息（2）逐个显示学生表中所有学生的相关信息（3）根据姓名进行查找，返回此学生的学号和成绩（4）根据指定的位置可返回相应的学生信息（学号，姓名，成绩）（5）给定一个学生信息，插入到表中指定的位置（6）删除指定位置的学生记录（7）统计表中学生个数四、实验设计 1．定义一个包含学生信息（学号，姓名，成绩）的顺序表，使其具有如下功能：（1）根据指定学生个数，逐个输入学生信息 for(count=0; count

大连理工大学数据结构(一)上机作业答案——张老师

1．将顺序表逆置，要求用最少的附加空间。参考答案 #include #include #include #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; #define LIST_INIT_SIZE 100 #define LISTTINCREMENT 10 typedef struct{ ElemType *elem; int length; int listsize; }SqList; //创建空顺序表 Status InitList_Sq(SqList &L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } //创建顺序表，插入元素 void ListInput_Sq(SqList &L){ int n,i; printf("input the length of Sqlist:"); scanf("%d",&n); L.length=n; for(i=0;i

国家二级MS+Office高级应用机试(数据结构与算法)模拟试卷8

国家二级MS Office高级应用机试（数据结构与算法）模拟试卷 8 (总分：56.00，做题时间：90分钟) 一、选择题(总题数：28，分数：56.00) 1.下列结构中属于线性结构链式存储的是（分数：2.00） A.双向链表√ B.循环队列 C.二叉链表 D.二维数组解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 2.下列叙述中错误的是（分数：2.00） A.循环链表中有一个表头结点 B.循环链表的存储空间是连续的√ C.循环链表实现了空表与非空表运算的统一 D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。 3.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为（分数：2.00） A.14 B.15 √ C.16 D.不可能有这样的树解析：解析：根据题目可知本树中还有度为2的结点。树的总结点＝(度1*个数＋度2*个数…)＋1，这里我们设度为2的结点数为x，那么30＝3*3＋2*x＋1*4＋1＝2*x＋14，由此可计算出x＝8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30－3－8－4＝15。 4.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为（分数：2.00） A.7 √ B.96 C.48 D.6 解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k＝log 2 n。其中n代表长度，k为比较次数。本题中可以计算出k＝7。 5.下列结构中属于非线性结构的是（分数：2.00） A.二叉链表 B.二维数组√ C.循环队列

数据结构实验一顺序表的实现

数据结构实验一顺序表的实现班级学号分数一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计出的算法进行分析，给出相应的结果。二、实验要求：编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。三、实验容及分析： 1.顺序表的建立建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。程序如下：头文件SqList.h的容如下： #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;ielem[i]); return OK; } //以下是整个源程序： #include #include"SqList.h" int main() { int i,n; SqList a; SqList *l = &a; if(InitList_Sq(l)==-2) printf("分配失败"); printf("\n输入要建立的线性表l的长度n:");//输入线性表得长度scanf("%d",&n); l->length=n; printf("线性表的长度是:%d\n",l->length); CreatList_Sq(l,n);//生成线性表 printf("输出线性表l中的元素值：");//输出线性表中的元素 for(i=0;ilength;i++) printf("%7d",l->elem[i]); getchar(); } 程序的运行结果：

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

实验一顺序表的基本操作一、实验目的掌握线性表的顺序表基本操作：建立、插入、删除、查找、合并、打印等运算。二、实验要求包含有头文件和main函数； 1.格式正确，语句采用缩进格式； 2.设计子函数实现题目要求的功能； 3.编译、连接通过，熟练使用命令键； 4.运行结果正确，输入输出有提示，格式美观。三、实验设备、材料和工具 1.奔腾2计算机或以上机型 2.turboc2,win-tc 四、实验内容和步骤 1. 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2. 往该顺序表中第i位置插入一个值为x的数据元素。 3. 从该顺序表中第j位置删除一个数据元素，由y返回。 4. 从该顺序表中查找一个值为e的数据元素，若找到则返回该数据元素的位置，否则返回“没有找到”。五、程序 #include #include #define list_init_size 10 #define increment 2

typedef struct { int *elem; int length,listsize; }sqlist; //类型定义 void initlist_sq(sqlist &L) //初始化顺序表 { } void output(sqlist L) //输出顺序表 { } void insertlist(sqlist &L,int i, int x) //顺序表中插入x { } void deletelist(sqlist &L,int j, int y) //顺序表中删除y { } int locateelem(sqlist &L,int e) //顺序表中查找e { } void main() { } 【运行结果】 void initlist_sq(sqlist &L) //初始化顺序表 { L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L.elem) exit (OVERFLOW);

数据结构上机题

#include #include #include #include #include #define null 0 #define M 100 //typedef int Elemtype;这里定义了却没用，可见思维不连惯struct Lnode { // int num; char data; struct Lnode *next; }; int lenth(struct Lnode **L) { int n=0; struct Lnode *t; t=*L; while(t!=null) { n++; t=t-> next; } return n; } /* int lenth1(char r[]) { int n=0; n=sizeof(r); return n-1; }*/ void creat(struct Lnode**L) { *L=null; }

//void insert(struct Lnode**L,int n, char d) //从功能化分上，这个函数不需要知道现在插入第几个字符//困为你init函数中是先对一个串的字符进行了排序，所以//这里直接插入链表的尾部就行了 void insert(struct Lnode**L, char d) { struct Lnode *t1,*t2; int j=1; t1=(struct Lnode*)malloc(sizeof(struct Lnode)); t1-> data=d; t1-> next=NULL; if(*L==NULL) { *L=t1; return; } t2=*L; while(t2-> next!=NULL) { t2=t2-> next; } t2-> next=t1; /* if(n==1) { t1-> next=t2; *L=t1; } else { while(j next!=null) { t2=t2-> next; j++; } if(j==n-1) { t1-> next=t2-> next; t2-> next=t1; } else { cout < < "Insert error! ";

数据结构实验-顺序表的基本操作

******************************* 实验题目：顺序表的基本操作实验者信息：班级13007102，姓名庞文正，学号1300710226实验完成的时间3:00 ****************************** 一、实验目的实验内容阿尔（1）掌握顺序表的基本运算，熟悉对顺序表的一些基本操作和具体函数的定义。（2）掌握顺序存储的概念，学会定义线性表的顺序存储类型。（3）熟悉c语言程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。（4）熟悉c语言环境的使用及程序的输入、编辑、调试和运行的全过程。加深对顺序存储结构的理解，逐步培养解决实际问题的编程能力。二、实验内容实现顺序表上的插入、删除等操作。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对有关算法的理解。三、算法设计与编码

1.本实验用到的理论知识本次实验用到结构体的定义，函数定义，具体函数的定义有： 1）insert(L,i,x)在顺序表的第i个元素之前插入一个新元素x. 2）delete (L,i) 删除顺序表的第i个元素。 3）listprint(L) 输出顺序表。 2.算法概要设计给出实验的数据结构描述，程序模块、功能及调用关系第一步:定义顺序表的存储结构。第二步：编写顺序表操作的具体函数定义。第三步：使用定义的顺序表并调用顺序表的一些操作，实现具体运算。四、运行与测试（1）运行成功的代码： #include"stdio.h" //包含输出输入文件 #define MAXSIZE 100 //宏定义 #define OK 1 #define OVERFLOW -2 typedef int elemtype; typedef struct //定义顺序表的结构 {