实验一 线性表的基本操作
一、实验目的与基本要求
1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。
2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。
3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。 4．掌握运用C语言上机调试线性表的基本方法。
二、实验条件
1．硬件：一台微机
2．软件：操作系统和C语言系统
三、实验方法
确定存储结构后，上机调试实现线性表的基本运算。
四、实验内容
1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。
3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表） 4． 假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。
五、附源程序及算法程序流程图
1.源程序
（1）源程序(实验要求1和3)
#include
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct arr {
1
int * elem; int length; int listsize; }Sqlist;
void menu(); //菜单
void InitList(Sqlist *p); // 创建线性表 void ShowList(Sqlist *p); // 输出顺序线性表
void ListDelete(Sqlist *p,int i,int &e); // 在顺序线性表中删除第i个元素，并用e返回其值
void ListInsert(Sqlist *p); // 新元素e
void ListEmpty(Sqlist *p); // void GetList(Sqlist *p,int i,int &e); // void ListInsert(Sqlist *p,int i,int e); bool compare(int a,int b);
void LocateElem(Sqlist *L,int e); // 满足compare()d元素的位序
void MergeList_L(Sqlist *La,Sqlist *Lb); //
void main() {
Sqlist La; Sqlist Lb; int n,m,x; menu();
scanf(\ while(n) {
switch(n) {
case 0: ; break; case 1:
InitList(&La);break; case 2:
ListEmpty(&La);break; case 3:
printf(\请输入插入的位序:\\n\ scanf(\
printf(\请出入要插入的数:\\n\ scanf(\
ListInsert(&La,m,x);break; case 4:
printf(\请输入删除元素的位序:\\n\
2
在顺序线性表中第i个元素前插入判断L是否为空表
用e返回L中第i个数据元素的值 在顺序线性表L中查找第1个值与e归并 scanf(\
ListDelete(&La,m,x);
printf(\删除的元素为:%d\\n\ case 5:
printf(\请输入要找的与线性表中相等的数:\\n\ scanf(\
LocateElem(&La,m);break; case 6:
printf(\请输入查找的位序:\\n\ scanf(\ GetList(&La,m,x);
printf(\中第%d个元素的值为%d\\n\ case 7:
ShowList(&La);break; case 8:
InitList(&Lb);break; case 9:
MergeList_L(&La,&Lb);
printf(\归并成功!\ }
menu();
scanf(\ } }
/*菜单*/ void menu() {
printf(\
printf(\退出\\n\\n\
printf(\创建线性表La\\n\\n\
printf(\判断La是否为空表\\n\\n\
printf(\插入元素(La)\\n\\n\
printf(\删除元素(La)\\n\\n\
printf(\定位元素(La)\\n\\n\
printf(\取元素(La)\\n\\n\
3
printf(\输出线性表\\n\\n\
printf(\创建线性表Lb\\n\\n\
printf(\归并为一个线性表La\\n\\n\
printf(\}
/*创建顺序线性表L*/
void InitList(Sqlist *L) {
int n; int i=0;
L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); if(NULL==L->elem)
printf(\储存分配失败!\\n\ else {
L->length=0;
L->listsize=LIST_INIT_SIZE; printf(\输入顺序表a:\\n\ scanf(\ while(n) {
L->elem[i]=n; i++;
L->length++;
L->listsize=L->listsize-4; scanf(\ } } }
/*输出顺序线性表*/
void ShowList(Sqlist *p) {
int i;
if(0==p->length)
printf(\数组为空!\\n\ else
for(i=0;i
printf(\ printf(\}
/*判断L是否为空表*/
4
void ListEmpty(Sqlist *p) {
if(0==p->length)
printf(\是空表!\\n\ else
printf(\不是空表!\\n\}
/*在顺序线性表中第i个元素前插入新元素e */ void ListInsert(Sqlist *p,int i,int e) {
int *newbase; int *q1; int *q2;
while(i<1||i>p->length+1) {
printf(\您输入的i超出范围!\\n请重新输入要插入的位置\\n:\ scanf(\ }
if(p->length>=p->listsize) {
newbase=(int
*)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) exit(0); else {
p->elem=newbase;
p->listsize+=LISTINCREMENT; } }
q1=&(p->elem[i-1]);
for(q2=&(p->elem[p->length-1]);q2>=q1;--q2) *(q2+1)=*q2; *q1=e;
++p->length; }
/*/在顺序线性表中删除第i个元素，并用e返回其值*/ void ListDelete(Sqlist *p,int i,int &e) {
int *q1,*q2;
while(i<1||i>p->length) {
printf(\您输入的i超出范围!请重新输入:\
5
C语言大数据结构线性表地基本操作实验报告材料
