下载文档原格式
线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。
2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。
3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。
4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。
线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。
2. 插入操作：将一个新元素插入到线性表中的指定位置。
3. 删除操作：将线性表中的某个元素删除。
4. 更新操作：将线性表中的某个元素更新为新的值。
线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。
线性表的顺序存储结构通常采用数组来实现。
数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。
但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。
线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。
每个元素包含数据和指向下一个元素的指针。
链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。
但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。
线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。
2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。
3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。
线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。
2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。
线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。
2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。
浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验五线性表的链式表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。
2、掌握单链表、循环单链表的一些基本操作实现函数。
二.实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。
同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。
提示：⑴单向链表的存储结构可定义如下：struct LNode { // 定义单链表节点类型ElemType data; // 存放结点中的数据信息LNode *next; // 指示下一个结点地址的指针}⑵线性表基本操作可包括如下一些：①void InitList (LNode *&H) //初始化单链表②void ClearList(LNode *&H) //清除单链表③int LengthList (LNode *H) //求单链表长度④bool EmptyList (LNode *H) //判断单链表是否为空表⑤ElemType GetList (LNode *H, int pos)//取单链表第pos 位置上的元素⑥void TraverseList(LNode *H) //遍历单链表⑦bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素⑧bool DeleteList ( LNode *&H, ElemType &item, int pos)//从单链表中删除一个元素⑶带表头附加结点的单链表初始化操作的实现可参考如下：void InitList(LNode *&H){ //构造一个空的线性链表H，即为链表设置一个头结点，//头结点的data数据域不赋任何值，头结点的指针域next则为空H=(LNode *)malloc(sizeof(LNode)); // 产生头结点Hif (!H) exit(0); // 存储分配失败，退出系统H->next=NULL; // 指针域为空}2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)，实现将两个有序单链表La和Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。
数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。
最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。
要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。
当中就会留出空隙，⾃然就需要弥补。
问题就出在这⾥。
为了解决这个问题，⾃然⽽然的就出现了链式存储结构。
2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。
顺序存储结构：只需要存储数据元素信息。
链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。
3、关键词：数据域：存储数据元素信息的域。
指针域：存储直接后继位置的域。
指针或链：指针域中存储的信息。
结点（Node）：指针域+数据域组成数据元素的存储映像。
头指针：链表中第⼀个结点的存储位置。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。
PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。
线性表的应用一、问题描述线性表有两种不同的存储结构，分别是顺序存储结构和链式存储结构，在实际中应用十分广泛。
本设计要求分别利用线性表的两种存储结构，设计算法完成对大数的阶乘、加法、乘法的求解。
二、基本要求1、选择合适的存储结构实现大数存储；2、设计算法，采用顺序存储结构完成大数的阶乘运算；3、设计算法，采用链式存储结构完成大数的加法运算；4、设计算法，选择合适的存储结构完成大数的乘法运算；5、其中某一算法采用两种存储结构实现。
三、测试数据1、阶乘运算的测试数据：63!2、加法运算的测试数据： 9876876787+896789675599993、乘法运算的测试数据：9876876787×89678967559999四、算法思想1、阶乘运算的算法思想：一个数的阶乘，利用一个顺序表来存储结果，首先令L.elem[0]=1，其他全部赋值为零，再用for循环，从1至i完成阶乘运算，其中由于位数越乘越多，故将其按位存储在顺序表中，防止数据范围溢出，在逐位相乘中，利用for循环位数，如若有进位问题，每次运算时，此位保留的数位，t=L.elem[j]*i+jw; L.elem[j]=t%10;jw=t/10;如果满足j>=top && jw==0;程序跳出，进行下一步i运算，此处top位保留上一位的位数，如此运算下去，输出顺序表。
2、加法运算的算法思想：本运算分别采用了两种存储结构，链式和栈存储结构。
加法是两个数位数对齐，从低位向高位加的运算，如果在哪位有进位，则后一位，进行加法还要另加上前面的进位，由此将输入的字符大数，存入链表中，且改为整形存入，此时是的链表是倒序的，定义一个变量表示每次的进位jw=0，建立一个链表，让他存储结果，如此两链表的数相加，每次还要加上上次留下的进位，此为保留的数位：new->data =(p->data +q->data +jw)%10; new->next =NULL;jw =(p->data+q->data+jw)/10;当两个数是一场一短时，自然当相等的长度加完后在执行下面的判断，保留住剩下的数同时每次加上jw，最后就是当最后一位有进位时将最后一个链表值赋jw，由于现在此链表存储的结果是反序的，故将其压入栈中，让后再输出栈元素，就是想加的结果。
数据结构实验线性表及其应用在计算机科学的领域中，数据结构是一门极其重要的基础学科，它为我们有效地组织和管理数据提供了理论和方法。
而线性表作为一种常见且基础的数据结构，在实际的程序设计和算法应用中有着广泛的应用。
线性表是一种最基本的数据结构，它是由零个或多个数据元素组成的有限序列。
在这个序列中，每个元素都有其特定的位置和值。
从存储结构上来看，线性表可以分为顺序存储和链式存储两种方式。
顺序存储的线性表，就像是一排紧密排列的格子，每个格子里存放着一个数据元素。
这种存储方式的优点是可以随机访问表中的任意元素，时间复杂度为 O(1)。
比如说，如果我们要获取顺序表中第 5 个元素的值，只需要通过简单的计算就能直接找到对应的位置并获取其值。
然而，顺序存储也有它的不足之处。
当需要插入或删除元素时，可能需要移动大量的元素，以保持数据的连续性，这会导致时间复杂度较高，为 O(n)。
相比之下，链式存储的线性表则更加灵活。
它就像是一串珍珠项链，每个珍珠（数据元素）通过一根线（指针）与下一个珍珠相连。
在链式存储中，插入和删除元素相对较为方便，只需要修改相关指针的指向即可，时间复杂度通常为 O(1)。
但是，由于无法直接通过计算得到某个元素的位置，所以随机访问的效率较低，时间复杂度为 O(n)。
在实际应用中，线性表有着多种多样的用途。
比如，我们可以用线性表来实现一个学生成绩管理系统。
将每个学生的成绩作为一个元素存储在线性表中，可以按照学号或者成绩进行排序。
当有新的学生成绩需要添加时，根据具体的存储方式选择合适的插入操作；当需要删除某个学生的成绩时，也能快速准确地进行删除。
再比如，在一个购物网站的商品列表中，也可以使用线性表来存储商品的信息。
用户可以按照价格、销量、评价等因素对商品进行排序和筛选。
而网站后台在处理商品的上下架、库存管理等操作时，也会频繁地对线性表进行插入、删除和修改等操作。
此外，在文本编辑软件中，我们输入的文字也可以看作是一个线性表。
数据结构课程小论文题目：线性表的链式表示学号：090510126姓名：叶妍莉班级：090510学院：经济管理学院2011年12月8日一．引言： --------------------------------------------------------------------- 2 - 二．链表的概述 --------------------------------------------------------------- 2 -1.线性链表里的一些概念： ------------------------------------------ 3 -2.链表的有关概述： --------------------------------------------------- 3 -3.链表的存储方法： --------------------------------------------------- 4 -4.链表的分类： --------------------------------------------------------- 4 - 三．线性表的链式实现 ------------------------------------------------------ 4 -1.“插入”和“删除”操作的实现： ------------------------------ 5 -2.“合并链表”操作的实现： --------------------------------------- 6 - 四．链表的优点与缺点 ------------------------------------------------------ 6 - 五．总结 ------------------------------------------------------------------------ 7 -线性表的链式表示姓名：叶妍莉班级：090510 学号：090510126摘要:线性表对于学过数据结构的人来说都是再熟悉不过了，它是数据结构的一个基本内容，是最常用且最简单的一种数据结构。
广西工学院计算机学院《数据结构》课程实验报告书实验二线性表的链式结构及其应用学生姓名：李四学号：2012班级：计Y124指导老师：王日凤专业：计算机学院软件学院提交日期：2013年6月18日1．实验目的1）熟练掌握线性表的基本操作在链式存储结构上的实现。
（2）用线性表的链式操作实现线性表的合并。
2.实验内容（1）要求用链式存储结构。
然后实现如下操作：✧初始化线性表✧建立一个含n个数据的线性表，用头插法或尾插法。
✧查找：输入一个数，查找线性表，若有，则输出“查找成功”，否则输出“无此数”。
（流程图）✧插入：输入一个数和插入位置，实现插入操作，并显示插入成功。
✧删除：输入一个位置数，删除该位置上的数，并显示删除成功。
（流程图）（2）线性表的合并，已知两个升序线性表，要求合并成一个新的升序线性表。
3．实验要求（1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。
（2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。
（3）实验报告（于本周五下午）报告内容包括：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。
线性表的链式存储结构如下：#define LIST_INIT_SIZE 100;//存储空间初始分配量#define LISTINCREMENT 10;//存储空间分配增量typedef struct LNode{ElemType data; //存储空间基址Struct LNode *next; //当前长度}LNode, *LinkList;3．主要算法3.1 顺序存储结构（1）结构定义：#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<malloc.h>//各头文件#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;//定义宏参//链表的储存结构typedef struct LNode{ElemType data;//定义数据类型struct LNode *next;//下一个指针}LNode,*LinkList;//==============================函数声明=============================// void CreateList(LinkList &L);//建立链表void print(LinkList L);//规范输出int LinkEmpty(LinkList L);//判断链表是否为空int LinkLength(LinkList L );//链表的长度void LinkDestroy(LinkList &L);//销毁链表int ListInsert(LinkList &L,int i,ElemType e);//插入元素int ListSearch(LinkList L,ElemType &e);//查找元素int ListDelete(LinkList &L,int i,ElemType &e);//删除元素void LinkClear(LinkList &L);//清空链表void MergeList_L(LinkList La,LinkList Lb,LinkList &Lc);//链表合并//==============================函数声明=============================////建立链表void CreatList(LinkList &L,int n){ //操作结果:建立了一个链表LinkList p;//指针域为空int i;printf("初始化完成!\n");for(i=n;i>0;--i) //倒序输入元素{p=(LinkList)malloc(sizeof(LNode));//建立头结的printf("请输入第%d个数据：",i);scanf("%d",&p->data);p->next=L->next;L->next=p;//指向下一个指针}printf("新创建的链表为：");print(L);//调用输出函数}//判断链表是否为空int LinkEmpty(LinkList L){//初始条件:链表已存在//操作结果:若长度为返回，否则返回LinkList p;//指针域为空p=L->next;//p指向第一个结点if(p=NULL)//到链尾return 1;elsereturn 0;}//链表的长度int LinkLength(LinkList L ){//初始条件:链表已存在//操作结果:返回链表的长度int j;//j记录链表长度LinkList p;//指针域为空p=L;j=0;while(p->next!=NULL)//末到表尾{++j;p=p->next;//指向下一个指针}return j;}//销毁链表void LinkDestroy(LinkList &L){//初始条件:链表已存在//操作结果:销毁链表LinkList p;//指针域为空p=L->next;//p指向第一个结点while(p)//末到表尾{L->next=p->next;p=L->next;}free(L);//释放结的Lreturn;}//清空链表void LinkClear(LinkList &L){//初始条件:链表已存在//操作结果:清空链表LinkList p,q;//指针域为空p=L->next;//p指向第一个结点while(p)//末到表尾{q=p->next;free(p);//释放结的pp=q;}L->next=NULL;//头结点指针域为空return;}//规范输出void print(LinkList L){//初始条件:链表已存在//操作结果:输出链表中所有元素LinkList p;//指针域为空p=L->next;//p指向第一个结点while(p!=NULL)//末到表尾{printf("%d ",p->data);p=p->next;}printf("\n");return;}//插入元素int ListInsert(LinkList &L,int i,ElemType e) { //初始条件:链表已存在//操作结果:在链表第i个位置插入元素e，//若成功插入返回，否则返回LinkList p,s;//指针域为空p=L; //l链表带头节点int j=0;while(p&&j<i-1) //查找第i-1个结点{p=p->next;++j;}if(!p||j>i-1)//i小于或者大于表长return ERROR; //i狱界s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;//插入成功！}//查找元素int ListSearch(LinkList L,ElemType &e){ //初始条件:链表已存在//操作结果:查找链表第i个位置的元素e，//若成功插入返回，否则返回int i;LinkList p;//指针域为空p=L->next; //p指向第一个结点i=1;while(p!=NULL&&p->data!= e)//末到表尾{p= p->next;i++;}if(!p)//第i个元素不存在{printf("查找失败!\n");return(0);}else{printf("查找成功！\n");printf("数据的位置为: %d",i);return (i);}}//删除元素int ListDelete(LinkList &L,int i,ElemType &e){//初始条件:链表已存在//操作结果: 删除链表第i个位置的元素e，////若成功删除返回，否则返回if(LinkEmpty(L))return (0);LinkList p,q;//指针域为空p=L;int j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)//第i个元素不存在return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;}//链表合并void MergeList_L(LinkList La,LinkList Lb,LinkList &Lc) {//初始条件:链表La和Lb已存在//操作结果:链表La和Lb为LcLinkList pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb)//末到表尾{if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}else{pc->next=pa;pc=pa;pa=pa->next;}}pc->next=pa?pa:pb;free(Lb);//释放Lb}//主函数void main(){LinkList L,La,Lb,Lc,p;int e,k,i=1,j,n;while(1){system("cls");//清屏printf("\n\t***************************************************"); printf("\n\t* 线性表的链式结构及其应用 *");printf("\n\t***************************************************\n");printf("\t * 1.建立链表 2.插入数字 *\n");printf("\t * 3.查找数字 4.删除数字 * \n");printf("\t * 5.链表的长度 6.链表空否 * \n");printf("\t * 7.链表的合并 8.销毁链表 * \n");printf("\t * 9.清空链表 0.退出 *\n");printf("\t****************************************************\n");printf("请选择选项<1-9>: ");//打印选项功能提示scanf(" %d",&k);if(k<0||k>9){printf("输入有误，请重新输入!");printf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();continue;}switch(k)//分支结构来调用各功能子函数{case 1:printf("建立一个链表!\n");L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请输入要建立的链表L的长度：");scanf("%d",&n);CreatList(L,n);printf("\n");printf("\n\t\t\t按任意键进行重新操作!"); getch();break;case 2:printf("插入数字!\n");printf("请输入您要插入的位置：");scanf("%d",&i);if((i<1)||(i>LinkLength(L))){printf("您要插入的位置狱界!");printf("\n");}printf("请输入您要插入的数字：");scanf("%d",&e);ListInsert(L,i,e);printf("插入成功呦！\n");printf("新链表为：");print(L);printf("\n");printf("\n\t\t\t按任意键进行重新操作!"); getch();break;case 3:printf("查找数字!\n");printf("请输入您要查找的数字：");scanf("%d",&e);ListSearch(L,e);printf("\n");getchar();getchar();break;case 4:printf("删除数字!\n");printf("请输入您要删除的结点号数：");scanf("%d",&i);ListDelete(L,i,e);printf("删除成功呦!\n");printf("删除的数为:%d\n",e);printf("新链表为：");print(L);printf("\n");printf("\n\t\t\t按任意键进行重新操作!"); getch();break;case 5:printf("求链表的长度!\n");printf("链表为：");print(L);j=LinkLength(L);printf("链表的数据长度为:%d",j);printf("\n");printf("\n");printf("\n\t\t\t按任意键进行重新操作!"); getch();break;case 6:printf("判断链表是否为空!\n");i=LinkEmpty(L);if(i==1)printf("链表为空!\n");if(i==0)printf("链表不为空!\n");printf("\n");printf("\n\t\t\t按任意键进行重新操作!"); getch();break;case 7:system("cls");//清屏La=(LinkList)malloc(sizeof(LNode));La->next=NULL;printf("两个单链表的合并操作！\n");printf("请输入要建立的链表La的长度：");scanf("%d",&n);CreatList(La,n);printf("\n");Lb=(LinkList)malloc(sizeof(LNode));Lb->next=NULL;printf("请输入要建立的链表Lb的长度：");scanf("%d",&n);CreatList(Lb,n);printf("\n");printf("下面执行合并操作！\n");Lc=La;MergeList_L(La,Lb,Lc);printf("输出链表La和Lb归并所得新的链表Lc中的元素！\n");printf("新链表为：");print(Lc);printf("\n\t\t\t按任意键进行重新操作!");getch();break;case 8:printf("你真确定要销毁链表! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1)LinkDestroy(L);printf("链表销毁成功呦!\n");if(j==2)printf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;case 9:printf("你真确定要清空链表! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1){LinkClear(L);printf("链表清空成功呦!\n");}elseprintf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;case 0:printf("你真确定要退出! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1){printf("\n\t\t\t再见，欢迎再次使用!\n\n\t\t\t");exit(OVERFLOW);}elseprintf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;}}}3.流程图1.查找2.删除操作4．程序运行结果（1）实验内容（1）运行结果如下：（2）实验内容2）运行结果如下：2）运行结果如下：2）运行结果如下：2）运行结果如下：5.心得体会。
