一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点优缺点。二、实验预习说明以下概念1、线性表由n(n≥0)个数据特性相同的元素构成的有限序列2、顺序表用一组地址连续的存储单元依次存储线性表的数据元素、这种表示也称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表( Sequential List)。3、链表链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域三、实验内容和要求1、阅读下面程序在横线处填写函数的基本功能。并运行程序写出结果。#includestdio.h#includemalloc.h#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的顺序表长度*/#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); /* 正位序输入n个元素的值建立带表头结点的单链表L */int ListInsert_sq(Sqlist *L,int i,ElemType e);/*在带头结点的单链表L中第i个位置插入值为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-length0;L-listsizeINIT_SIZE;return OK;}/*InitList*/int CreateList_sq(Sqlist *L,int n){ElemType e;int i;for(i0;in;i){printf(input data %d,i1);scanf(%d,e);if(!ListInsert_sq(L,i1,e))return ERROR;}return OK;}/*CreateList*//*输出顺序表中的元素*/int PrintList_sq(Sqlist *L){int i;for(i1;iL-length;i)printf(%5d,L-slist[i-1]);return OK;}/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e){int k;if(i1||iL-length1)return ERROR;if(L-lengthL-listsize){L-slist(ElemType*)realloc(L-slist,(INIT_SIZEINCREM)*sizeof(ElemType));if(!L-slist)return ERROR;L-listsizeINCREM;}for(kL-length-1;ki-1;k--){L-slist[k1] 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(void){Sqlist sl;int n,m,k;printf(please input n:); /*输入顺序表的元素个数*/scanf(%d,n);if(n0){printf(\n1-Create Sqlist:\n);InitList_sq(sl);CreateList_sq(sl,n);printf(\n2-Print Sqlist:\n);PrintList_sq(sl);printf(\nplease input insert location and data:(location,data)\n);scanf(%d,%d,m,k);ListInsert_sq(sl,m,k);printf(\n3-Print Sqlist:\n);PrintList_sq(sl);printf(\n);}elseprintf(ERROR);return 0;}运行结果please input n:51-Create Sqlist:input data 14input data 26input data 311input data 44input data 572-Print Sqlist:4 6 11 4 7please input insert location and data:(location,data)2,453-Print Sqlist:4 45 6 11 4 7Press any key to continue算法分析首先应该选择顺序表的动态存储方式进行顺序表结构的定义然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令接着编写各种操作函数的函数体而在主函数中要首先调用InitList_sq(sl)函数初始化然后调用InitList_sq()创建顺序表调用PrintList_sq()函数输出该顺序表中元素的值然后调用ListInsert_sq()函数进行插入操作并输出插入新元素后的状态。2、为第1题补充删除和查找功能函数并在主函数中补充代码验证算法的正确性。删除算法代码int ListDelete_sq(Sqlist *L,int i){if (L-length0)return 0;if(i1||iL-length)return 0;for(int ji;jL-length;j)L-slist[j-1]L-slist[j];L-length--;return 1;}运行结果3-Print Sqlist:4 45 6 11 4 7please input delete location:3Delete date is:64-Print Sqlist:4 45 11 4 7算法分析当在主函数里面调用删除功能函数并传参数进去时程序将自动跳到函数体里面利用所传参数一步步执行在该函数里面当把顺序表和序号i传值进去时程序可以先判断所传值是否满足条件若满足则开始从顺序表第一个元素开始依次遍历直到找到第i个位置的元素并将其删除后面的元素依次前移填补。而表的长度则减一删除成功。若不满足则返回0表示删除失败。查找算法代码int ListLocate(Sqlist *L,ElemType e){for(int i1; iL-length;i){if(L-slist[i-1]e)return i;return 0; }}运行结果4-Print Sqlist:4 45 11 4 7please input date date7Search date is No5算法分析当在主函数里面调用查找功能函数并传参数进去时程序将自动跳到函数体里面利用所传参数一步步执行在该函数里面当把顺序表和要查找的值e传值进去时程序开始从顺序表第一个元素开始依次遍历直到找到值为e的元素并返回其位置序号查找成功。若遍历了顺序表所有元素依然没有符合条件的e的值则返回0表示查找失败。3、阅读下面程序在横线处填写函数的基本功能。并运行程序写出结果。#includestdio.h#includemalloc.h#define ERROR 0#define OK 1typedef 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); /*用e返回L中第i个数据 */LinkList CreateList(int n){LNode *p,*q,*head;int i;head(LinkList)malloc(sizeof(LNode)); head-nextNULL;phead;for(i0;in;i){q(LinkList)malloc(sizeof(LNode)); printf(input data %i:,i1);scanf(%d,q-data); /*输入元素值*/q-nextNULL; /*结点指针域置空*/p-nextq; /*新结点连在表末尾*/pq;}return head;}/*CreateList*/void PrintList(LinkList L){LNode *p;pL-next; /*p指向单链表的第1个元素*/while(p!NULL){printf(%5d,p-data);pp-next;}}/*PrintList*/int GetElem(LinkList L,int i,ElemType *e){LNode *p;int j1;pL-next;while(pji){pp-next;j;}if(!p||ji)return ERROR;*ep-data;return OK;}/*GetElem*/int main(void){int n,i;ElemType e;LinkList LNULL; /*定义指向单链表的指针*/printf(please input n:); /*输入单链表的元素个数*/scanf(%d,n);if(n0){printf(\n1-Create LinkList:\n);LCreateList(n);printf(\n2-Print LinkList:\n);PrintList(L);printf(\n3-GetElem from LinkList:\n);printf(input i);scanf(%d,i);if(GetElem(L,i,e))printf(No%i is %d,i,e);elseprintf(not exists);}elseprintf(ERROR);return 0;}运行结果please input n:51-Create Sqlist:input data 1:12input data 2:8input data 3:23input data 4:9input data 5:312-Print Sqlist:12 8 23 9 313-GetElem from Linklist:Input i5No5 is 31Press any key to continue算法分析首先应该进行单链表结构的定义然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令接着编写各种操作函数的函数体而在主函数中要首先调用LinkList CreateList(int n)创建带头结点的单链表输入结点数然后依次输入各个结点的值。接着调用打印单链表功能函数输出单链表中的值。再调用查找功能函数输入查找元素的位置输出对应元素的值。然后调用插入功能函数输入要插入的位置和元素打印输出插入后的新链表。同理调用删除功能函数输入要删除的元素值最后打印输出删除后的单链表。4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。插入算法代码int InsertList(LinkList L,int i,ElemType e){int j0; LNode *p,*q; pL-next;while(pji-1){pp-next;j;}if(pnull||ji-1)printf(“\n i Error!”);else{q(LNode *)malloc(sizeof(LNode));q-datae; q-nextp-next; p-nextq; }return OK;}运行结果2-Print Sqlist:12 8 23 9 313-GetElem from Linklist:Input i5No5 is 314-Insert from Linklist:Input i2Input e1612 16 8 23 9 31算法分析在主函数里面调用查找功能函数并传参数进去时程序将自动跳到函数体里面利用所传参数一步步执行在该函数里面当把单链表要插入的位置序号和元素内容传值进去时程序开始从单链表第一个元素开始依次遍历直到找到插入位置的前一个节点用指针p指向它。然后创建一个以e为值的新节点指针q修改节点*q的next域指向节点*p的下一个节点再将节点*p的next域修改为指向新节点*s。返回ok表示插入成功。最后打印输出插入后的新链表。删除算法代码int DeleteList(LinkList L,ElemType e){LNode *p,*q;pL-next;while(pp-data!e){qp;pp-next;}if(!(p-next)||(ji-1))printf(“\n i Error!”);else{q-nextp-next;delete q;return OK; }运行结果4-Insert from Linklist:Input i2Input e1612 16 8 23 9 315-Delete from Linklist:Input e2312 16 8 9 31Press any key to continue算法分析当在主函数里面调用删除功能函数并传参数进去时程序将自动跳到函数体里面利用所传参数一步步执行在该函数里面当把单链表要删除的元素内容传值进去时开始从单链表第一个元素开始依次找直到找到删除位置的前一个节点用指针p指向它。指针q指向要删除的节点。然后修改指针p的下一个为指向待删除节点*q的后继节点。返回ok表示删除成功。最后打印输出删除后的新链表。————————————————版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。原文链接https://blog.csdn.net/WZY22502701/article/details/123798240