《数据结构实验一 顺序表的实现》由会员分享，可在线阅读，更多相关《数据结构实验一 顺序表的实现（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验一 顺序表的实现班级学号姓名分数一、实验目的：1. 熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现；2. 以线性表的各种操作的实现为重点；3. 通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计 出的算法进行分析，给出相应的结果。二、实验要求：编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告三、实验内容及分析：1. 顺序表的建立建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。程序如下：头文件SqList.h的内容如下：#include#include#define LIST_INIT_SIZE 1
2、00#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef structElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList *L)L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(E
3、lemType); if(!L-elem) return(OVERFLOW);L-length=0;L-listsize=LIST_INIT_SIZE;return OK;Status CreatList_Sq(SqList *L,int n)int i;printf(输入%d 个整数:n,n);for(i=0;ielemi);return OK;以下是整个源程序：#include#includeSqList.hint main()int i,n;SqList a;SqList *l = &a;if(InitList_Sq(l)=-2)printf(分配失败)；printf(n输入要建立的线性
4、表l的长度n:);/输入线性表得长度 scanf(%d, &n);l-length=n;printf(线性表的长度是:%dn,l-length);Crea tList_Sq(l,n); 生成线性表printf(输出线性表l中的元素值：)；/输出线性表中的元素 for(i=0;ilength;i+)printf(%7d,l-elemi);get char();程序的运行结果：2. 顺序表的插入利用前面的实验先建立一个顺序表L,然后再第i个位置插入元素，通过对比插入元素 前后的线性表发生的变化，判断插入操作是否正确。参考程序：#include#include#includeSqList.hStat
5、us ListInsert_Sq(SqList *L,int i,ElemType e)在线性表L中的第i个位置前插入一个值为e的元素i 的取值范围：l=i=ListLength_Sq(L)ElemType *newbase,*q,*p;f (iL-length+l) return ERROR;/i 值不合法 if(L-length=L-listsize) /当前存储空间已满，增加分配量 newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) return (OVER
6、FLOW); /存储分配失败 L-elem=newbase;/新基址L-length=+LISTINCREMENT; /增加存储容量/ifq=&(L-elemi-l);/q 为插入位置for(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p;/插入位置及以后的元素右移*q=e;插入 e+L-length; /表长增1return OK;/ListInsert_Sqint main()int n,i,x;SqList *L,a;L=&a;InitList_Sq(L);printf(n输入要建立的线性表L得长度:);scanf(%d,&n);L-length=n;Cr
7、eatList_Sq(L,n);printf(n插入元素之前线性表L的长度是:d,L-length);printf(n插入元素之前线性表L中的元素是:);for(i=0;ilength;i+) printf(%5d,L-elemi);printf(n输入要插入元素的位置:);scanf(%d,&i);printf(n输入要插入的元素的值:);scanf(n %d，&x); if(Lis tl nser t_Sq(L,i,x)0) printf( n插入元素之后线性表L的长度是：%d ,L-leng th); printf(n插入元素之后线性表L的元素是:n);for(i=0;ilength;i
8、+)printf(%5d, L-elemi);/ifelseprintf(不能插入这个元素！ n);get char();运彳丁结果：G:C 程序buqianxing biao l.x-eB炎器釐團线性表嗨长度汴23 14 517 31;7艮218表表1.-R-n 之、N23 一 L-L1VSiPfees mni# fccy1 ta continue4. 单链表的实现新建链表，生成一个有一定结点的链表，并且顺序输出。 程序代码：#includestdio.h#includestdlib.h#includestring.h#define null 0#define MAX 100最多元素个数#d
9、efine LENGTH sizeof(struct Node)typedef int Elem ;数据元素类型 单链表实现线性表 struct NodeElem data; /数据域 struct Node *next; /指针域 ;typedef struct Node NODE; typedef struct Node *LINKLIST; /初始化链表,产生一个空链表 LINKLIST InitList() /返回空链表的头指针LINKLIST head;head=null;return head; /新建链表，生成一个有一定结点的链表LINKLIST CreateList（） /返回
10、新链表的首地址（指针） LINKLIST head=null,p,q;int n,i;Elem temp;doprintf(请输入要建的结点数：”)；scanf(%d,&n);if(nMAX)printf(对不起！请输入的数在l-%d之间，请重新输入。n,MAX);while(nMAX)；for(i=0;idata=temp;if(head=null)head=q=p; p-next=null;else后移printf（请输入第%小结点数据：，i+l）;/输入结点数据如果head指向空，则p结点为第一个结点/不是第一个结点,则结点放到结尾并且，尾指针p-next=null;q-next=p;
11、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；i
12、nt len=0；/初始化计数器为0while(pt)len+；pt=pt-next；return len；/返回链表长度/*/向链表链表尾部添加结点，无输入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;*/指向起始结点/开辟结点空间/向结点数据赋值/结点后继指向空/若链表为空，
13、直接作为第一个结点/若不为空，将结点插在最后/返回头结点指针/*/向链表链表尾部添加结点，有输入 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;/指向起始结点/开辟结点空间);/结点后继指向空/若链表为空，直接作为第一个结点/若不为空，将结点插在最后/返回头结点指针*/将结点插入到链表的指定位置LINKL
