数据结构两个顺序表的合并

第1讲 线性表

本章主要掌握如下内容：

线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。

知识点分析

（一）线性表的定义和基本操作

1．线性表基本概念

1）定义：是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表

（ a1, a2, …, an）

a1是最前结点，an是最后结点。结点也称为数据元素或者记录。

2）线性表的长度：线性表中结点的个数称为其长度。长度为0的线性表称为空表。

3）结点之间的关系：设线性表记为（a1,a2,„ai-1 , ai, ai+1 ,„an），称ai-1是ai的直接前驱结点．．．．（简称前驱），ai+1是ai的直接后继结点．．．．（简称后继）。

4）线性表的性质：

① 线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。

② 如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。

注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。

『经典例题解析』

线性表的特点是每个元素都有一个前驱和一个后继。( )

【答案】错误。

【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。其余的所有元素都有一个前驱和后继。

2．线性表的抽象数据类型

线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。

《数据结构和算法》

实验指导书

实验及学时数分配

序号 实验名称 学时数（小时）

1 实验一 线性表 4

2 实验二 树和二叉树 2

3 实验三 图 2

4 实验四 查找 2

5 实验五 内部排序 2

合计 12

几点要求：

一、 上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、 上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。

三、 下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一 线性表

【实验目的】

1、 掌握用Turbo c上机调试线性表的基本方法；

2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；

3、 运用线性表解决线性结构问题。

【实验学时】

4 学时

【实验类型】

设计型

【实验内容】

1、 顺序表的插入、删除操作的实现；

2、 单链表的插入、删除操作的实现；

3、 两个线性表合并算法的实现。(选做)

【实验原理】

1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；

2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；

3、 详细原理请参考教材。

【实验步骤】

一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、 通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）

实验一 C语言数据类型的使用

[实验目的]

复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备。

[实验内容及要求]

1．建立一个简单链表（静态链表），它由3个学生数据的结点组成，每个结点包括学号和成绩。输出各结点中的数据。(根据题目完善程序)

#define NULL 0

struct student

{long num；

float score；

struct student *next；

} stu；

typedef struct student stu;

main ()

{ stu a,b,c,*head,*p；

a.num=99101；a.score=89.5；

b.num=99103；b.score=90；

c.num=99107；c.score=85；

head=&a；

a.next=&b；

b.next=&c；

c.next=NULL；

p=head；

do

{printf（“%ld%5.1f\n”, ）；/*输出学号和成绩*/

p=p->next；

}while( )；

}

输出：

2．建立一个动态链表，它由3个学生数据的结点组成，每个结点包括学号和成绩。输出各结点中的数据。

#define NULL 0

#define LEN sizeof(struct student)

struct student 1 {long num；

float score；

struct student *next；

}；

int n；

struct student *creat(void) /*尾插法建立链表*/

{

struct student *head；

struct student *p1, *p2；

n=0；

p1=p2=(struct student *)malloc(sizeof(struct student))；

数据结构(C语言版)严蔚敏课后习题答案

数据结构（C语言版）严蔚敏课后习题答案

一、线性表

1. 顺序表

顺序表是一种存储结构，它将元素顺序存放在一块连续的存储区域中。C语言中常用数组来实现顺序表。以下是一些常见题目的解答：

题目1：已知顺序表中存储了n个整数，请编写一个算法，将这个顺序表中的所有负数挑选出来，并将它们按照原有顺序存放在新的顺序表中。

解答：

```

#include

#define MAX_SIZE 100

int main() {

int A[MAX_SIZE], neg[MAX_SIZE];

int n, i, j = 0;

printf("Enter the number of elements: ");

scanf("%d", &n);

printf("Enter the elements: "); for (i = 0; i < n; i++) {

scanf("%d", &A[i]);

if (A[i] < 0) {

neg[j] = A[i];

j++;

}

}

printf("Negative numbers: ");

for (i = 0; i < j; i++) {

printf("%d ", neg[i]);

}

return 0;

}

```

题目2：假设顺序表A和B中的元素递增有序排列，编写一个算法合并这两个顺序表，并使合并后的顺序表仍然递增有序。

解答：

```

#include #define MAX_SIZE 100

int main() {

int A[MAX_SIZE], B[MAX_SIZE], C[MAX_SIZE * 2];

int m, n, i, j, k;