下载文档原格式
线性表知识点总结线性表的特点：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. 链式存储结构链式存储结构是通过节点之间的指针链接来实现线性表的存储。
在编译技术中，链式存储结构常用于存储中间代码、语法树等数据结构。
链式存储结构灵活性较高，可以动态地分配和释放存储空间。
二、栈栈是一种具有后进先出（LIFO）特性的线性表。
在编译技术中，栈常用于处理函数调用、表达式求值等场景。
栈的基本操作包括入栈和出栈。
入栈将元素压入栈顶，出栈将栈顶元素弹出。
编译技术中，栈还常用于处理函数的局部变量、函数的三、队列队列是一种具有先进先出（FIFO）特性的线性表。
在编译技术中，队列常用于处理优化算法、指令调度等场景。
队列的基本操作包括入队和出队。
入队将元素插入队尾，出队将队头元素移除。
编译技术中，队列还常用于处理指令流水线、任务调度等问题。
四、树树是一种非线性的数据结构，它由若干个节点组成，节点之间通过边连接。
在编译技术中，树常用于构建语法树、抽象语法树等数据结构。
树的基本概念包括根节点、叶子节点和内部节点。
树的遍历方式有前序遍历、中序遍历和后序遍历。
编译技术中，树的遍历常用于语法分析、语义分析等阶段。
五、图图是一种由节点和边组成的非线性数据结构。
在编译技术中，图常用于构建控制流图、数据依赖图等数据结构。
图的基本概念包括顶点、边和路径。
图可以分为有向图和无向图，还可以带有权重。
编译技术中，图的遍历常用于寻找程序中的循环、六、哈希表哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构。
在编译技术中，哈希表常用于符号表、常量表等数据结构。
数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。
最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。
要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。
当中就会留出空隙，⾃然就需要弥补。
问题就出在这⾥。
为了解决这个问题，⾃然⽽然的就出现了链式存储结构。
2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。
顺序存储结构：只需要存储数据元素信息。
链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。
3、关键词：数据域：存储数据元素信息的域。
指针域：存储直接后继位置的域。
指针或链：指针域中存储的信息。
结点（Node）：指针域+数据域组成数据元素的存储映像。
头指针：链表中第⼀个结点的存储位置。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。
PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。
1.实验目的掌握线性表的链式存储结构设计与基本操作的实现。
2.实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。
⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；3.数据结构设计逻辑结构：线性结构存储结构：链式存储结构4.算法设计#include <stdio.h>#include <malloc.h>#include <windows.h>typedef struct LNode{int data;struct LNode *next;}LNode;typedef struct Pnode{ float coef;int exp;struct Pnode *next;}Polynode;void menu(){printf("******************************* **************\n");printf("* 作者：Dick *\n");printf("* 信计1001 xxxxxxxxxx *\n");printf("*********************MENU**** ***************\n");printf("1 求A和B的并集C\n");printf("2 对A和B进行合并,用线性表C保存合并结果(有序)\n");printf("3 建立一元多项式(两个)\n");printf("4 两个一元多项式相加\n");printf("5 两个一元多项式相减\n");printf("6 退出程序\n");}void UnionList(){//先输入两个链表，然后判断是否为空，头结点还是要的。
int i;LNode *List1,*List2,*List3,*p,*q,*r;List1 = (LNode *)malloc( sizeof(LNode) );List2 = (LNode *)malloc( sizeof(LNode) );List3 = (LNode *)malloc( sizeof(LNode) );List1->next = List2->next = List3->next = NULL;printf("请输入第一个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了List1 = r;p = List1->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//第二个。
printf("请输入第二个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}List2 = r;p = List2->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//List3已经初始化了，现在先检测List1中是否有重复项p = List1->next;q = p->next;while(p->next != NULL){while(q != NULL){if(p->data == q->data){r = List1->next;while(r->next != q)r = r->next;r->next = q->next;free(q);q = r->next;}elseq = q->next;}if(p->next != NULL){p = p->next;q = p->next;}elsebreak;}//检测两个链表的重复项p = List1->next;q = List2->next;while(p != NULL ){while(q != NULL){if(p->data == q->data){r = List2;while( r ->next != q)r = r->next;r->next = q->next;free(q);q = r->next;}elseq = q->next;}q = List2->next;p = p->next;}List3->next = List1->next;r = List1;while(r->next != NULL)r = r->next;r->next = List2->next;//这里输出printf("\n并集C为:\n");p = List3->next;i = 0;while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}printf("\n请输入回车键继续\n");getchar();getchar();system("CLS");}void UnionSort(){//前面是一样的,抽空考虑优化代码//写的有问题。
破坏了链表结构所以这里就不能优化了。
int i;LNode *List1,*List2,*List3,*p,*q,*r;List1 = (LNode *)malloc( sizeof(LNode) );List2 = (LNode *)malloc( sizeof(LNode) );List3 = (LNode *)malloc( sizeof(LNode) );List1->next = List2->next = List3->next = NULL;printf("请输入第一个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了List1 = r;//输出下好了p = List1->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//第二个。
printf("请输入第二个链表的数据(1~100),以0结束\n");p = q = r = (LNode *)malloc( sizeof(LNode) );while(1){p = (LNode *)malloc( sizeof(LNode) );do{printf("请输入数据\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->data = i;if(p->data == 0){q->next = NULL;free(p);break;}q->next = p;q = p;}List2 = r;p = List2->next;printf("\n您输入的链表为\n");while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}//这里默认已经有序了,直接连接到第三个上面p = List1->next;q = List2->next;List3 = r = List1;while(p != NULL && q != NULL){if(p->data <= q->data){r->next = p;r = p;p = p->next;}else{r->next = q;r = q;q = q->next;}}r->next = p?p:q;free(List2);//这里输出printf("\n合并后的表格是:\n");p = List3->next;i = 0;while(p != NULL){i++;printf("%d\t",p->data);if(i == 5){i = 0;printf("\n");}p = p->next;}printf("\n请输入回车键继续\n");getchar();getchar();system("CLS");}void InitPolynomial(Polynode *&Poly1,Polynode *&Poly2){float j;int i;Polynode *p,*q,*r;Poly1->next = Poly2->next = NULL;extern void DisplayList(Polynode *&Poly3);printf("请输入第一个多项式的数据(1~100),以0结束\n");p = q = r = (Polynode *)malloc( sizeof(Polynode) );while(1){p = (Polynode *)malloc( sizeof(Polynode) );do{printf("请输入多项式系数\n");scanf("%f",&j);if(j < 0 || j > 100)printf("输入错误，请重新输入\n");}while(j < 0 || j > 100);p->coef = j;do{printf("请输入多项式次数\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->exp = i;if( (int) (p->coef - 0) <0.01 ){q->next = NULL;free(p);break;}q->next = p;q = p;}//这个时候链表基本搞定,连接上就行了Poly1 = r;printf("请输入第二个多项式的数据(1~100),以0结束\n");p = q = r = (Polynode *)malloc( sizeof(Polynode) );while(1){p = (Polynode *)malloc( sizeof(Polynode) );do{printf("请输入多项式系数\n");scanf("%f",&j);if(j < 0 || j > 100)printf("输入错误，请重新输入\n");}while(j < 0 || j > 100);p->coef = j;do{printf("请输入多项式次数\n");scanf("%d",&i);if(i < 0 || i > 100)printf("输入错误，请重新输入\n");}while(i < 0 || i > 100);p->exp = i;if( (int) (p->coef - 0) <0.01 ){q->next = NULL;free(p);break;}q->next = p;q = p;}Poly2 = r;//输出多项式DisplayList(*&Poly1);DisplayList(*&Poly2);}void PolyPlus(Polynode *&Poly1,Polynode *&Poly2){Polynode *Poly3,*p,*q,*r,*s;extern void DisplayList(Polynode *&Poly3);Poly3 = (Polynode *)malloc( sizeof(Polynode) );s = Poly3;p = Poly1->next;q = Poly2->next;//两个链表相加,都是判断语句，比较两个表中每个元素的次数while(p != NULL && q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );if(p->exp > q->exp){r->coef = q ->coef;r->exp = q->exp;s->next = r;s = r;q = q->next;}else if(p->exp < q->exp){r->coef = p ->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}else if( p->exp == q->exp){r->coef = p->coef + q->coef;if(r->coef == 0){free(r);}else if(r->coef != 0){r->exp = p->exp;s->next = r;s = r;}p = p->next;q = q->next;}}if(p != NULL)while(p != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = p->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}elsewhile(q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = q->coef;r->exp = q->exp;s->next = r;s = r;q = q->next;}r->next = NULL;DisplayList(*&Poly3);}void PolySub(Polynode *&Poly1,Polynode *&Poly2){Polynode *Poly3,*p,*q,*r,*s;extern void DisplayList(Polynode *&Poly3);Poly3 = (Polynode *)malloc( sizeof(Polynode) );s = Poly3;p = Poly1->next;q = Poly2->next;//和上面的基本一样,只不过变了个符号而已,感觉还能和上面的函数//加起来还能优化while(p != NULL && q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );if(p->exp > q->exp){r->coef = -(q->coef);r->exp = q->exp;s->next = r;s = r;q = q->next;}else if(p->exp < q->exp){r->coef = p ->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}else if( p->exp == q->exp){r->coef = (p->coef) - (q->coef);if(r->coef == 0){free(r);}else if(r->coef != 0){r->exp = p->exp;s->next = r;s = r;}p = p->next;q = q->next;}}if(p != NULL)while(p != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = p->coef;r->exp = p->exp;s->next = r;s = r;p = p->next;}elsewhile(q != NULL){r = (Polynode *)malloc( sizeof(Polynode) );r->coef = -(q->coef);r->exp = q->exp;s->next = r;s = r;q = q->next;}r->next = NULL;DisplayList(*&Poly3);}void DisplayList(Polynode *&Poly3){int i=0;Polynode *p;p = Poly3->next;printf("\n结果为\n");printf("F(x)= ");while(p->next != NULL){i++;//首先判断的是系数是否为1,为1的话就不输出系数了if( p->coef != 1 ){//这里判断次数，次数为0不输出"x"if( p->exp == 0){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3f+",p->coef);elseprintf("%6.3f+",p->coef);if(i == 10){i = 0;printf("\n");}}//这里判断次数是否为1,次数为1只输出一个"x"else if( p->exp == 1 ){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx+",(int)p->coef);elseprintf("%dx+",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3fx+",p->coef);elseprintf("%6.3fx+",p->coef);if(i == 10){i = 0;printf("\n");}}else{if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx^%d+",(int)p->coef,p->exp );elseprintf("%dx^%d+",(int)p->coef,p->exp);elseif(p->coef < 0)printf("\b%6.3fx^%d+",p->coef,p->exp);elseprintf("%6.3fx^%d+",p->coef,p->exp);if(i == 10){i = 0;printf("\n");}}}else{if( p->exp == 0){if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if(p->coef < 0)printf("\bx+",(int)p->coef);elseprintf("x+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else{if(p->coef < 0)printf("\bx^%d+",p->exp);elseprintf("x^%d+",p->exp);if(i == 10){i = 0;printf("\n");}}}p = p->next;}//这里是最后一个位置，因为最后少输出一个运算符//所以再进行一次输出,不然上面再增加判断语句的话//就更乱了i++;if( p->coef != 1 ){if( p->exp == 0){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%d",(int)p->coef);elseprintf("%d",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3f",p->coef);elseprintf("%6.3f",p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx",(int)p->coef);elseprintf("%dx",(int)p->coef);elseif(p->coef < 0)printf("\b%6.3fx",p->coef);elseprintf("%6.3fx",p->coef);if(i == 10){i = 0;printf("\n");}}else{if( (p->coef - (int)p->coef) < 0.01 )if(p->coef < 0)printf("\b%dx^%d",(int)p->coef,p->exp);elseprintf("%dx^%d",(int)p->coef,p->exp);elseif(p->coef < 0)printf("\b%6.3fx^%d",p->coef,p->exp);else printf("%6.3fx^%d",p->coef,p->exp);if(i == 10){i = 0;printf("\n");}}}else{if( p->exp == 0){if(p->coef < 0)printf("\b%d+",(int)p->coef);elseprintf("%d+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else if( p->exp ==1){if(p->coef < 0)printf("\bx+",(int)p->coef);elseprintf("x+",(int)p->coef);if(i == 10){i = 0;printf("\n");}}else{if(p->coef < 0)printf("\bx^%d+",p->exp);elseprintf("x^%d+",p->exp);if(i == 10){i = 0;printf("\n");}}}printf("\n");printf("\n请输入回车键继续\n");getchar();getchar();}void main(){int i;Polynode *Poly1,*Poly2;Poly1 = (Polynode *)malloc( sizeof(Polynode) );Poly2 = (Polynode *)malloc( sizeof(Polynode) );while(1){menu();do //这里循环直到你输入正确的数字为止{printf ( "请输入要进行的操作\n" );scanf ("%d",&i);if (i<1||i>6)printf("错误数字，请重新输入\n");}while (i<1||i>6);switch (i){case 1: UnionList(); break;case 2: UnionSort(); break;//清屏函数放到break前面可以有效的在执行完一系列函数之后才清屏case 3: InitPolynomial(*&Poly1,*&Poly2);system("CLS");break;case 4: PolyPlus(*&Poly1,*&Poly2);system("CLS");break;case 5: PolySub(*&Poly1,*&Poly2);system("CLS");break;case 6: exit(0); break;}}}5.测试结果图一：非递减有序排列图二：求并集图四：两个多项式相加图五：两个多项式相减图三：输入两个多项式。
