当前位置:首页 >> 其它课程 >>

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


数据结构实验一
班级 学号

顺序表的实现
姓名 分数

一、实验目的:
1. 熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现; 2. 以线性表的各种操作的实现为重点; 3. 通过本次学习帮助学生加深 C 语言的使用,掌握算法分析方法并对已经设计 出的算法进行分析,给出相应的结果。


二、实验要求:
编写实验程序, 上机运行本程序, 保存程序的运行结果, 结合程序进行分析并写出实验报告。

三、实验内容及分析:
1.顺序表的建立
建立一个含 n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 程序如下: 头文件 SqList.h 的内容如下: #include<stdio.h> #include<malloc.h> #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)
1

{ int i; printf("输入%d 个整数:\n",n); for(i=0;i<n;i++) scanf("\n%d",&L->elem[i]); return OK; } //以下是整个源程序: #include<stdio.h> #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;i<l->length;i++) printf("%7d",l->elem[i]); getchar(); } 程序的运行结果:

2

2.顺序表的插入
利用前面的实验先建立一个顺序表 L,然后再第 i 个位置插入元素,通过对比插入元素 前后的线性表发生的变化,判断插入操作是否正确。 参考程序: #include<stdio.h> #include<malloc.h> #include"SqList.h" Status ListInsert_Sq(SqList *L,int i,ElemType e) { //在线性表 L 中的第 i 个位置前插入一个值为 e 的元素 //i 的取值范围:1<=i<=ListLength_Sq(L) ElemType *newbase,*q,*p; if(i<1||i>L->length+1) return ERROR;//i 值不合法 if(L->length>=L->listsize){ //当前存储空间已满,增加分配量 newbase=(ElemType*)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) return (OVERFLOW); //存储分配失败 L->elem=newbase; //新基址 L->length=+LISTINCREMENT; //增加存储容量 }//if q=&(L->elem[i-1]); //q 为插入位置 for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; //插入位置及以后的元素右移 *q=e; //插入 e ++L->length; //表长增 1 return OK; }//ListInsert_Sq int main() { int n,i,x; SqList *L,a; L=&a; InitList_Sq(L); printf("\n 输入要建立的线性表 L 得长度:"); scanf("%d",&n); L->length=n; CreatList_Sq(L,n); printf("\n 插入元素之前线性表 L 的长度是:%d",L->length); printf("\n 插入元素之前线性表 L 中的元素是:"); for(i=0;i<L->length;i++) printf("%5d",L->elem[i]); printf("\n 输入要插入元素的位置:"); scanf("%d",&i); printf("\n 输入要插入的元素的值:");
3

scanf("\n %d",&x); if(ListInsert_Sq(L,i,x)>0) { printf("\n 插入元素之后线性表 L 的长度是: %d ",L->length); printf("\n 插入元素之后线性表 L 的元素是:\n"); for(i=0;i<L->length;i++) printf("%5d", L->elem[i]); }//if else printf("不能插入这个元素!\n"); getchar(); } 运行结果:

4. 单链表的实现
新建链表,生成一个有一定结点的链表,并且顺序输出。 程序代码: #include"stdio.h" #include"stdlib.h" #include"string.h" #define null 0 #define MAX 100 //最多元素个数 #define LENGTH sizeof(struct Node) typedef int Elem ; //数据元素类型 //单链表实现线性表 struct Node
4

{ Elem data; //数据域 struct Node *next; //指针域 }; typedef struct Node NODE; typedef struct Node *LINKLIST; //初始化链表,产生一个空链表 LINKLIST InitList() //返回空链表的头指针 { LINKLIST head; head=null; return head; } //新建链表,生成一个有一定结点的链表 LINKLIST CreateList() //返回新链表的首地址(指针) { LINKLIST head=null,p,q; int n,i; Elem temp; do{ printf("请输入要建的结点数:"); scanf("%d",&n); if(n<1 || n>MAX) printf("对不起!请输入的数在 1-%d 之间,请重新输入。\n",MAX); }while(n<1 || n>MAX); for(i=0;i<n;i++) { p=(LINKLIST)malloc(LENGTH); //开辟新结点空间 printf("请输入第%d 结点数据:",i+1); scanf("%d",&temp); //输入结点数据 p->data=temp; if(head==null) //如果 head 指向空,则 p 结点为第一个结点 { head=q=p; p->next=null; } else //不是第一个结点,则结点放到结尾并且,尾指针 后移 { p->next=null;
5

q->next=p; q=p; } } return head; } //遍历打印链表 int printList(LINKLIST h) //返回打印结果,0 表示无数据,1 表示成功打印完成 { LINKLIST pt=h; if(pt==null) //没有数据直接返回 { printf("对不起,没有数据!"); return 0; } while(pt) //结点不为空就打印结点内容 { printf("%d ",pt->data); pt=pt->next; } printf("\n"); return 1; } //返回新链表的首地址(指针)

//求的链表的长度 int ListLength(LINKLIST h) //求的链表长度,返回链表长度,若链表为空则返回 0 { LINKLIST pt=h; int len=0; //初始化计数器为 0 while(pt) { len++; pt=pt->next; } return len; //返回链表长度 } /* //向链表链表尾部添加结点,无输入
6

LINKLIST AddNode(LINKLIST h,Elem { LINKLIST head,pt,p; pt=head=h; p=(LINKLIST)malloc(LENGTH); p->data=e; p->next=null; if(pt==null) head=p; else { while(pt->next) { pt=pt->next; } pt->next=p; } return head; } */

e)

//指向起始结点 //开辟结点空间 //向结点数据赋值 //结点后继指向空 //若链表为空,直接作为第一个结点 //若不为空,将结点插在最后

//返回头结点指针

/* //向链表链表尾部添加结点,有输入 LINKLIST AddNode(LINKLIST h) { LINKLIST head,pt,p; pt=head=h; //指向起始结点 p=(LINKLIST)malloc(LENGTH); //开辟结点空间 printf("请输入要添加的数据:"); scanf("%d",&p->data); p->next=null; //结点后继指向空 if(pt==null) //若链表为空,直接作为第一个结点 head=p; else //若不为空,将结点插在最后 { while(pt->next) { pt=pt->next; } pt->next=p; } return head; //返回头结点指针 } */
7

//将结点插入到链表的指定位置 LINKLIST AddNode(LINKLIST h,int i,Elem e) //插入位置 i,0<i,若 i 大于链表长度,则直接插在链表最后 { LINKLIST head,pt,p; int j; pt=head=h; if(i<1) //插入位置错误(i<1),输出信息并结束 程序 { printf("程序出错,请检查参数!"); exit(1); } if(pt && i>ListLength(h)) //链表不为空,且位置大于链表长度时 { while(pt->next) { pt=pt->next; } p=(LINKLIST)malloc(LENGTH); p->data=e; p->next=null; pt->next=p;

//开辟结点空间 //向结点数据赋值 //结点后继指向空

} else if(pt==null) //链表为空时 { p=(LINKLIST)malloc(LENGTH); //开辟结点空间 p->data=e; //向结点数据赋值 p->next=null; //结点后继指向空 head=p; } else //参数正确且链表不为空时 { if(i==1) //插入点为第 1 个位置 { p=(LINKLIST)malloc(LENGTH); //开辟结点空间 p->data=e; //向结点数据赋值 p->next=pt; //结点后继指向空 head=p; } else //插入在链表中间位置时 {
8

p=(LINKLIST)malloc(LENGTH); p->data=e; for(j=1;j<i-1;j++) { pt=pt->next; } p->next=pt->next; pt->next=p; } } return } //删除链表中的某位置结点 LINKLIST ListDelete(LINKLIST h,int i) //i 在 1 到 ListLength(h)之间 { LINKLIST head,pt; int j=1; pt=head=h; if(h==null) //空表 { printf("对不起,没有内容!"); return null; } if(i<1 || i>ListLength(h)) //检查 i 的范围 { printf("程序出错,请检查参数!"); exit(1); } else //i 合法, { if(i==1) //删除首结点 { head=pt->next; free(pt); } else //删除中间节点或尾结点 { while(j<i-1) { pt=pt->next; j++; } head;

//开辟结点空间 //向结点数据赋值

//返回头结点指针

9

pt->next=pt->next->next; } } return head; } //链表是否为空 int ListEmpty(LINKLIST h) //返回 0 表示空,1 表示链表不空 { if(h==null) return 0; return 1; } //取得指定位置的元素的值 Elem GetElem(LINKLIST h,int i) //返回结点的元素值 { LINKLIST pt=h; int j=1; if(i>ListLength(h) || i<1) { printf("程序出错,请检查参数!"); exit(1); } while(j<i) { pt=pt->next; j++; } return (pt->data); } //返回头结点指针

//检查参数

//找到第 i 个结点

//返回结点值

//链表的逆置 LINKLIST Invert(LINKLIST h) { LINKLIST head,middle,trail; //定义三个指针指向三个相邻的结点 middle=null; while(h) { //循环交换相邻两个的指针指向 trail=middle; middle=h;
10

h=h->next; middle->next=trail; } head=middle; return head; } //将两个链表合并为一个链表 LINKLIST Union(LINKLIST La,LINKLIST Lb) //将 La 和 Lb 连接在一块,返回连接后的链表头指针 { LINKLIST head,pa; if(La==null) head=Lb; else { head=pa=La; while(pa->next) { pa=pa->next; } pa->next=Lb; //将 Lb 表头连接在链表 La 的结尾 } return head; //返回链表表头 } //将链表按非递减排序 LINKLIST ToUpSort(LINKLIST h) //返回排好序后的头指针 { LINKLIST p=h,q,temp; temp=(LINKLIST)malloc(LENGTH); while(p) { q=p->next; while(q) { if(q->data<p->data) { temp->data=p->data; p->data=q->data; q->data=temp->data; } q=q->next; //将最后的结点变为链表头 //返回链表表头

//开辟临时交换结点

//比较大小交换数据

11

} p=p->next; } free(temp); return h; } //释放临时空间 //返回头结点

//将链表按非递增排序 LINKLIST ToDownSort(LINKLIST h) //返回排好序后的头指针 { LINKLIST p=h,q,temp; temp=(LINKLIST)malloc(LENGTH); //开辟临时交换结点 while(p) { q=p->next; while(q) { if(q->data>p->data) //比较大小交换数据 { temp->data=p->data; p->data=q->data; q->data=temp->data; } q=q->next; } p=p->next; } free(temp); //释放临时空间 return h; //返回头结点 } //比较结点大小 int compare(NODE e1,NODE e2) //若 e1>e2 返回 1,若 e1=e2 返回 0,若 e1<e2 返回-1 { return 0; } int main() { LINKLIST p,q;
12

Elem n=8,i; p=CreateList(); p=ToUpSort(p); printList(p); return 0; } 运行结果:

13


相关文章:
数据结构顺序表操作实验报告
数据结构顺序表操作实验报告_电脑基础知识_IT/计算机_专业资料。实验 1 顺序表...6. 7. 8. 实验要求 输入一组整型元素序列,建立顺序表。 实现顺序表的遍历...
数据结构实验一 顺序表的实现
数据结构实验一 顺序表的实现_其它课程_高中教育_教育专区。数据结构中顺序表的实现 数据结构实验一班级 学号 顺序表的实现姓名 分数 一、实验目的: 1. 熟悉线性...
数据结构顺序表实验报告
数据结构顺序表实验报告_表格类模板_表格/模板_应用文书。一、 设计人员相关信息...实验题目:编写一个程序,实现顺序表的各种基本运算(假设顺序表元素为 char) , ...
数据结构实验一 顺序表的实现
算法分析实验一班级 学号 姓名 分数 顺序表的实现 一、 实验目的: 1.掌握线性表的顺序存储结构 2.能熟练地利用顺序存储结构实现线性表的基本操作 3.能熟练地...
数据结构顺序表的实现
数据结构顺序表的实现_计算机软件及应用_IT/计算机_专业资料。数据结构顺序表的实现实验3 顺序表一、实验目的 1. 熟练掌握顺序表的类型定义和基本操作算法(以建立、...
数据结构实验报告_顺序表的操作
数据结构实验报告_顺序表的操作 暂无评价|0人阅读|0次下载|举报文档 建立一个顺序表,然后在已建好的顺序表上实现顺序表插入和删除等基本操作。最后输出最终结果。...
数据结构实验-顺序表的基本操作
(3) 熟悉 c 语言程序的基本结构,掌握程序中的用户头文 件、实现文件和主文件...出实验数据结构描述,程序模块、功能及调用关系 第一步:定义顺序表的存储结构...
数据结构实验两个有序顺序表的合并
数据结构实验两个有序顺序表的合并_计算机软件及应用_IT/计算机_专业资料。两个...顺序表的创建 1.实现顺序表的追加 2.实现顺序表的显示 3.两顺序表的合并 *...
数据结构实验一_顺序表的基本操作实验报告
数据结构实验一_顺序表的基本操作实验报告_数学_自然科学_专业资料。实验一 顺序表的基本操作一、实验目的 掌握线性表的顺序表基本操作:建立、插入、删除、查找、...
数据结构-实验报告顺序表基本运算
数据结构-实验报告顺序表基本运算_电脑基础知识_IT/计算机_专业资料。(封面) ...□综合性实验 一、实验目的及要求: 1、目的 通过实验,实现顺序表的各种基本...
更多相关标签:
数据结构顺序表的实现 | 数据结构顺序表实验 | 数据结构顺序表 | 数据结构顺序表代码 | 数据结构顺序表的建立 | 数据结构建立顺序表 | 数据结构顺序表的逆置 | 数据结构创建顺序表 |