实验一 线性表（顺序表与链表）.docx

本文格式为Word版，下载可任意编辑实验一 线性表（顺序表与链表） 测验一 依次表与链表 一、测验目的 1、掌管线性表中元素的前驱、后续的概念 2、掌管依次表与链表的建立、插入元素、删除表中某元素的算法 3、对线性表相应算法的时间繁杂度举行分析 4、理解依次表、链表数据布局的特点（优缺点） 二、测验预习 说明以下概念 1、线性表： 2、依次表： 3、链表： 三、测验内容和要求 1、阅读下面程序，在横线处填写函数的根本功能并运行程序，写出结果 #include #include #define ERROR 0 #define OK 1 #define INIT_SIZE 100 /*初始调配的依次表长度*/ #define INCREM 5 /*溢出时，依次表长度的增量*/ typedef int ElemType; /*定义表元素的类型*/ typedef struct Sqlist{ ElemType *slist; /*存储空间的基地址*/ int length; /*依次表的当前长度*/ int listsize; /*当前调配的存储空间*/ }Sqlist; int InitList_sq(Sqlist *L); /* */ int CreateList_sq(Sqlist *L,int n); /* */ int ListInsert_sq(Sqlist *L,int i,ElemType e);/* */ int PrintList_sq(Sqlist *L); /*输出依次表的元素*/ int ListDelete_sq(Sqlist *L,int i); /*删除第i个元素*/ int ListLocate(Sqlist *L,ElemType e); /*查找值为e的元素*/ int InitList_sq(Sqlist *L){ L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L->slist) return ERROR; L->length=0; L->listsize=INIT_SIZE; return OK; }/*InitList*/ int CreateList_sq(Sqlist *L,int n){ ElemType e; int i; for(i=0;ilength;i++) printf(\ return OK; }/*PrintList*/ int ListInsert_sq(Sqlist *L,int i,ElemType e){ int k; if(iL->length+1) return ERROR; if(L->length>=L->listsize){ L->slist=(ElemType*)realloc(L->slist, (INIT_SIZE+INCREM)*sizeof(ElemType)); if(!L->slist) return ERROR; L->listsize+=INCREM; } for(k=L->length-1;k>=i-1;k--){ L->slist[k+1]= L->slist[k]; } L->slist[i-1]=e; L->length++; return OK; }/*ListInsert*/ /*在依次表中删除第i个元素*/ int ListDelete_sq(Sqlist *L,int i){ } /*在依次表中查找指定值元素，返回其序号*/ int ListLocate(Sqlist *L,ElemType e){ } int main(){ Sqlist sl; int n,m,k; printf(\输入依次表的元素个数*/ scanf(\ if(n>0){ printf(\ InitList_sq( CreateList_sq( printf(\ PrintList_sq( printf(\ scanf(\ ListInsert_sq( printf(\ PrintList_sq( printf(\ } else printf(\ return 0; } ? 运行结果 ? 算法分析 2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。

删除算法代码： ? 运行结果 ? 算法分析 查找算法代码： ? 运行结果 ? 算法分析 3、阅读下面程序，在横线处填写函数的根本功能并运行程序，写出结果 #include #include #define ERROR 0 #define OK 1 typedef int ElemType; /*定义表元素的类型*/ typedef struct LNode{ /*线性表的单链表存储*/ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreateList(int n); /* */ void PrintList(LinkList L); /*输出带头结点单链表的全体元素*/ int GetElem(LinkList L,int i,ElemType *e); /* */ LinkList CreateList(int n){ LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; p=head; for(i=0;inext=NULL; /*结点指针域置空*/ p->next=q; /*新结点连在表末尾*/ p=q; } return head; }/*CreateList*/ void PrintList(LinkList L){ LNode *p; p=L->next; /*p指向单链表的第1个元素*/ while(p!=NULL){ printf(\ p=p->next; } }/*PrintList*/ — 5 —。