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

数据结构实验一顺序表的实现数据结构实验一顺序表的实现数据结构实验一顺序表的实现班级学号姓名分数一、实验目的: 1. 熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现; 2. 以线性表的各种操作的实现为重点; 3. 通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计出的算法进行分析，给出相应的结果。二、实验要求: 编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。三、实验内容及分析: 1.顺序表的建立建立一个含n个数据元素的顺序表并输出该表...

数据结构实验一顺序表的实现数据结构实验一顺序表的实现班级学号姓名分数一、实验目的: 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) 1 { 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(); } 程序的运行结果: 2 2.顺序表的插入利用前面的实验先建立一个顺序表L，然后再第i个位置插入元素，通过对比插入元素前后的线性表发生的变化，判断插入操作是否正确。参考程序: #include #include #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;ilength;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;ilength;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;idata=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 e) { 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; //返回头结点指针 } */ /* //向链表链表尾部添加结点，有输入 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 参数～"); 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;jnext; } p->next=pt->next; pt->next=p; } } return head; //返回头结点指针 } //删除链表中的某位置结点 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(jnext; j++; } 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(jnext; j++; } return (pt->data); //返回结点值 } //链表的逆置 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->datadata) //比较大小交换数据 { 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

                    本文档为【数据结构实验一  顺序表的实现】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

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

你可能还喜欢

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