线性表的实现及操作(二)

实验一、线性表的实现及操作（一）

一、实验目的

了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。

(1)需求分析：

这份实验报告为所有必做题的实验报告。包括实验一顺序表建立、插入、删除等基本操作，实验二单链表的建立、插入、删除等基本操作，实验四二叉树的基本操作：树的建立、前序、中序、后序遍历及实验六图的遍历：深度优先和广度优先。这四份基础性的实验为改错性质，将每个实验题目中的错误改正过来并通过调试，有助于对基础知识的理解与强化记忆。

(2)概要设计：

实验一为对顺序线性表实现插入，删除，查找等基本操作。

需要用到的语句包括void ListInitiate(SeqList *L)

int ListInsert(SeqList *L, int i, DataType x)

int ListDelete(SeqList *L, int i, DataType *x)

int ListGet(SeqList L, int i, DataType *x)等。

实验二是对单链表进行建立，插入，删除等基本操作。

需要的语句为void ListInitiate(SeqList *L)

int ListInsert(SeqList *L, int i, DataType x)

int ListDelete(SeqList *L, int i, DataType *x)

int ListGet(SeqList L, int i, DataType *x)等。

实验四为二叉树，要求建立一个二叉树，并实现前序，中序及后序的遍历。

所需语句包括void ListInitiate(SeqList *L)

int ListInsert(SeqList *L, int i, DataType x)

int ListDelete(SeqList *L, int i, DataType *x)

int ListGet(SeqList L, int i, DataType *x)等。

实验六的内容是图的遍历包括邻接矩阵和邻接链表两种方法。

三、程序代码

（更正后的代码）

#include

#define MaxSize 100

typedef int DataType;

typedef struct

{

DataType list[MaxSize];

int size;

} SeqList;

void ListInitiate(SeqList *L) /*初始化顺序表L*/

{

L->size = 0; /*定义初始数据元素个数*/

}

int ListLength(SeqList L) /*返回顺序表L的当前数据元素个数*/ {

return L.size;

}

int ListInsert(SeqList *L, int i, DataType x)

/*在顺序表L的位置i（0 ≤i ≤size）前插入数据元素值x*/

/*插入成功返回1，插入失败返回0*/

{

int j;

if(L->size >= MaxSize)

{

printf("顺序表已满无法插入! \n");

return 0;

}

else if(i < 0 || i > L->size )

{

printf("参数i不合法! \n");

return 0;

}

else

{

for(j = L->size; j > i; j--) L->list[j] = L->list[j]; /*为插入做准备*/

L->list[i] = x; /*插入*/

L->size ++; /*元素个数加1*/

return 1;

}

}

int ListDelete(SeqList *L, int i, DataType *x)

/*删除顺序表L中位置i（0 ≤i ≤size - 1）的数据元素值并存放到参数x 中*/

/*删除成功返回1，删除失败返回0*/

{

int j;

if(L->size <= 0)

{

printf("顺序表已空无数据元素可删! \n");

return 0;

}

else if(i < 0 || i > L->size-1)

{

printf("参数i不合法");

return 0;

}

else

{//此段程序有一处错误

*x = L->list[i]; /*保存删除的元素到参数x中*/

for(j = i +1; j <= L->size-1; j++) L->list[j] = L->list[j-1]; /*依次前移*/

L->size--; /*数据元素个数减1*/

return 1;

}

}

int ListGet(SeqList L, int i, DataType *x)

/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/ {

if(i < 0 || i > L.size-1)

{

printf("参数i不合法! \n");

return 0;

}

else

{

*x = L.list[i];

return 1;

}

}

void main(void)

{ SeqList myList;

int i , x;

ListInitiate(&myList);

for(i = 0; i < 10; i++)

ListInsert(&myList, i, i+1);

ListDelete(&myList, 4, &x);

for(i = 0; i < ListLength(myList); i++)

{

ListGet( myList, i, &x); //此段程序有一处错误

printf("%d ", x);

}

}

测试结果：

线性表的实现及操作（二）

一、实验目的

了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。

三、程序代码：

（更正后的结果）

#include /*该文件包含pringtf()等函数*/

#include /*该文件包含exit()等函数*/

#include /*该文件包含malloc()等函数*/

typedef int DataType; /*定义DataType为int*/

typedef struct Node

{

DataType data;

struct Node *next;

} SLNode;

void ListInitiate(SLNode **head) /*初始化*/

{

/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/

if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);

(*head)->next = NULL; /*置链尾标记NULL */

}

int ListLength(SLNode *head)

{

SLNode *p = head; /*p指向首元结点*/

int size = 0; /*size初始为0*/

while(p->next != NULL) /*循环计数*/

{

p = p->next;

size ++;

}

return size;

}

int ListInsert(SLNode *head, int i, DataType x)

/*在带头结点的单链表head的数据元素ai（0 ≤i ≤size）结点前*/

/*插入一个存放数据元素x的结点*/

{

SLNode *p, *q;

int j;

p = head; /*p指向首元结点*/

j = -1; /*j初始为-1*/

while(p->next != NULL && j < i - 1)

/*最终让指针p指向数据元素ai-1结点*/

{

p = p->next;

j++;

}

if(j != i - 1)

{

printf("插入位置参数错！");

return 0;

}

/*生成新结点由指针q指示*/

if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);

q->data = x;

//此段程序有一处错误

p->next = q->next; /*给指针q->next赋值*/

p->next = q; /*给指针p->next重新赋值*/ return 1;

}

int ListDelete(SLNode *head, int i, DataType *x)

/*删除带头结点的单链表head的数据元素ai（0 ≤i ≤size - 1）结点*/ /*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/ {

SLNode *p, *s;

int j;

p = head; /*p指向首元结点*/

j = -1; /*j初始为-1*/

while(p->next != NULL && p->next->next!= NULL && j < i - 1)

/*最终让指针p指向数据元素ai-1结点*/

{

p = p->next;

j++;

}

if(j != i - 1)

{

printf("插入位置参数错！");

return 0;

}

//此段程序有一处错误

s = p->next; /*指针s指向数据元素ai结点*/

*x = s->data; /*把指针s所指结点的数据元素域值赋予x*/ p->next = s->next; /*把数据元素ai结点从单链表中删除指*/

free(s); /*释放指针s所指结点的内存空间*/

return 1;

}

int ListGet(SLNode *head, int i, DataType *x)

/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/

{

SLNode *p;

int j;

p = head;

j = -1;

while(p->next != NULL && j < i)

{

p = p->next; j++;

}

if(j != i)

{

printf("取元素位置参数错！");

return 0;

}

//此段程序有一处错误

*x = p->data;

return 1;

}

void Destroy(SLNode **head)

{

SLNode *p, *p1;

p = *head;

while(p != NULL)

{

p1 = p;

p = p->next;

free(p1);

}

*head = NULL;

}

void main(void)

{

SLNode *head;

int i , x;

ListInitiate(&head); /*初始化*/

for(i = 0; i < 10; i++)

{

if(ListInsert(head, i, i+1) == 0) /*插入10个数据元素*/

{

printf("错误! \n");

return;

}

}

if(ListDelete(head, 4, &x) == 0) /*删除数据元素5*/

{

printf("错误! \n");

return;

}

for(i = 0; i < ListLength(head); i++)

{

if(ListGet(head, i, &x) == 0) /*取元素*/

{

printf("错误! \n");

return;

}

else printf("%d ", x); /*显示数据元素*/ }

Destroy(&head);

}

测试结果为：

第二章 考研试题精选

第二章线性表作业 一、选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）

线性表的顺序存储结构定义和基本操作算法实现

#include "" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; }

数据结构_实验1_线性表的基本操作

实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题

要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE;

数据结构第2章作业 线性表(答案)

第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间：

线性表的顺序存储结构定义和基本操作算法实现

/************线性表的顺序存储结构定义和基本操作算法实现************/ #include "stdio.h" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i;

201560140140--袁若飞--实验1：线性表的基本操作及其应用

数据结构 实验1：线性表的基本操作及其应用 班级：RB软工移151 学号：201560140140 姓名：袁若飞

实验一线性表 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，题目一、二是必做题。题目三、题目四选作。 三、实验准备知识 1、请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个： （1）初始化线性表initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。 （2）求表长度List_length(L)——即求表中的元素个数。 （3）按序号取元素get_element(L,i)——取出表中序号为i的元素。（4）按值查询List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。 （5）插入元素List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6）删除元素List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。 2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。

第二章线性表答案

第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF

A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF

第2章线性表(课堂作业)

第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（）

A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为

线性表的基本操作讲解

实验二线性表的基本操作 一、实验目的 1．掌握用C++/C语言调试程序的基本方法。 2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。 二、实验要求 1．C++/C完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。 三、实验内容： 1. 分析并运行以下各子程序的主要功能。 程序1：顺序存储的线性表和运算 #include #define MAXSIZE 100 int list[MAXSIZE]; int n; /*insert in a seqlist*/ int sq_insert(int list[], int *p_n, int i, int x) {int j; if (i<0 || i>*p_n) return(1); if (*p_n==MAXSIZE) return(2); for (j=*p_n+1; j>i; j--) list[j]=list[j-1]; list[i]=x; (*p_n)++; return(0); } /*delete in a seq list*/ int sq_delete(int list[], int *p_n, int i) {int j; if (i<0 || i>=*p_n) return(1); for (j = i+1; j<=*p_n; j++) list[j-1] = list[j]; (*p_n)--; return(0); } void main() {int i,x,temp; printf("please input the number for n\n"); printf("n="); scanf("%d",&n); for (i=0; i<=n; i++) {printf("list[%d]=",i); scanf("%d",&list[i]);}

实验一 线性表的基本操作

实验一线性表的基本操作 一、实验目的 1. 熟悉C/C++语言上机环境； 2. 掌握线性表的基本操作：查找、插入、删除等运算在顺序存储、链式存储结构上的运算。 二、实验环境 1. 装有Visual C＋＋6.0的计算机。 2. 本次实验共计2学时。 三、实验内容 1. 建立顺序表，基本操作包括：初始化、建立顺序表、输出顺序表、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 2. 设有两个非递增有序的线性表A和B，均已顺序表作为存储结构。编写算法实现将A表和B表合并成一个非递增有序排列的线性表（可将线性表B插入线性表A中，或重新创建线性表C）。 3. 建立单链表，基本操作包括：初始化、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 四、源程序 #include #include #include #define MaxSize 50 typedef char ElemType; //-------存储结构---------- typedef struct { ElemType elem[MaxSize]; //存放顺序表中的元素 int length; //存放顺序表的长度 } SqList; //-------初始化线性表---------- void InitList(SqList *&L) //初始化线性表，构造一个空的线性表，并将长度设置为0 { L=(SqList *)malloc(sizeof(SqList)); L->length=0;

线性表习题2

线性表典型例题 一、单项选择题 [例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。 ①A．存储B．物理C．逻辑D．物理和逻辑 ②A．顺序B．网状C．星式D．链式 ③A．顺序B．二分法C．顺序及二分法D．随机 ④A．二分法查找B．快速查找C．顺序查找D．插入 解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。 [例7-2] 链表不具备的特点是( )。 A．插入和删除不需要移动元素B．可随机访问任一结点 C．不必预分配空间D．所需空间与其长度成正比 解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。本题答案为：B。 [例7-3] 不带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head_>next＝＝NULL C．head_>next＝＝head D．head!＝NULL 解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，head＝＝NULL表示该单链表为空。本题答案为：A。 [例7-4] 带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL 解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head —>next＝＝NULL表示该单链表为空。本题答案为：B。 [例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL 解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝head表示该单链表为空。本题答案为：C。 [例7-6] 线性表采用链式存储时其存储地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续不连续都可以 解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。 [例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。 A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior； B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior； C．s—>next=p；s—>prior=p—>prior；p—>prior=s；p—>prior—>next=s； D．s—>next=p；s—>prior=p—>prior；p—>prior—>next=s；p—>prior=s； 解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。本题答案为：D。

线性表的基本操作实验报告

实验一：线性表的基本操作 【实验目的】 学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。 【实验内容】 1.顺序表的实践 1) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立 的基本操作。 2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现 顺序表插入的基本操作。 3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9， 实现顺序表的删除的基本操作。 2.单链表的实践 3.1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链 表建立的基本操作。 2) 将该单链表的所有元素显示出来。 3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插 入的基本操作。 4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置 （如i=2）删除一个结点，实现单链表删除的基本操作。 5) 实现单链表的求表长操作。 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了刚创

建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 1、#include "stdio.h" #include "malloc.h" #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct { ElemType *elem; int length; int listsize; } SqList; Status InitList( SqList &L ) { int i,n; L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType)); if (!L.elem) return(OVERFLOW); printf("输入元素的个数:"); scanf("%d",&n); printf("输入各元素的值:"); for(i=0;i

数据结构与算法(线性表)练习题

三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。 四、已知一个单向链表，试给出复制该链表的算法。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。 五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数： int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。 六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。 要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置（position ）和游标（cursor ）的型。 2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。 3、在1、2的基础上完成本题。 4、在main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态 表，最后将这两个静态表合并。 七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：11 11...)(e e m e m x a x a t a x A m m +++= -- 其中，系数a i ≠0，指数e i 满足e m >e m-1>…>e 2>e 1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main 函数中，构建两个多项式，并测试相加和相乘运算。

实验一 线性表基本操作的编程实现

实验一线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求： 线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【思考问题】 1.线性表的顺序存储和链表存储的差异？优缺点分析？ 2.那些操作引发了数据的移动？ 3.算法的时间效率是如何体现的？ 4.链表的指针是如何后移的？如何加强程序的健壮性？ 【参考代码】（以下内容，学生任意选择一个完成即可） （一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include #include #define ListSize 100 //根据需要自己设定一个班级能够容纳的最大学生数 (2) typedef struct stu { int num; //学生的学号 char name[10]; //学生的姓名 float physics; //物理成绩 float math; //数学成绩 float english; //英语成绩 }STUDENT; //存放单个学生信息的结构体类型 typedef struct List { STUDENT stu[ListSize]; //存放学生的数组定义，静态分配空间

第二章线性表习题及答案

第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L;

线性表算法题

已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值（假设0为正数）元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。 ．两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。 设用带头结点的双向循环链表表示的线性表为L=（a1,a2, …a n）。写出算法将L改造成：L=（a1，a3，…a n，…a4，a2）。 已知A、B、C是三个顺序表且其元素按递增顺序排列，每个表中元素均无重复。在表A删去既在表B中出现又在表C中出现的元素。试设计实现上述删除操作的算法Delete。 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）。 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L） 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）。 设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间） ⑴确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列 {20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）； ⑵在单链表将比正整数x小的数按递减次序排列； ⑶将正整数（比）x大的偶数从单链表中删除。

实验一 线性表基本操作

实验一线性表基本操作 （4课时） 一、实验目的 掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。 二、实验要求 1.格式正确，语句采用缩进格式； 2.设计子函数实现题目要求的功能； 3.编译、连接通过，熟练使用命令键； 4.运行结果正确，输入输出有提示，格式美观。 5.输入数据至少三组，分别代表不同的情况，以测试程序的正确性。 6.将运行结果截图，并粘在文档的相应位置。 三、实验环境 1.turboc2,win-tc,VC++ 四、实验内容和步骤 1.编程实现在顺序存储的有序表中插入一个元素。 2.编程实现把顺序表中从i个元素开始的k个元素删除。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成(an,…..a2,a1)。4．约瑟夫环问题。 约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。 例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。 五、根据实验过程填写下面内容 1．写出第1题的程序并写出运行结果和分析。 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define ElemType int #define MAXSIZE 100 typedef struct//顺序表申明 { ElemType elem[MAXSIZE]; int last; }SeqList;

第二章课后作业答案

第二章线性表习题(答案) 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置也相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。 3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：（4）、（1）。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next;（4）S->next= P->next; （5）S->next= L; （6）S->next= NULL;（7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a[n]中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保 持线性表的有序性。 void insertData(int a[],int data) { int i,location=0; for(i=0;i=location;i--) /*把查入点及查入点之后的数据以次后移一位*/ { a[i+1]=a[i]; } a[location]=data; /*把查新数据*/ lenth++; } 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 int DeleteData(int a[],int i,int k) { int j; if(i<1||i>lenth||k<0||k>lenth-k+1)return 0; for(j=i-1;j