数据结构 线性表
线性表
定义
线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用a表示数据元素，则i称为数据元素ai在线性表中的位序。线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
分类
我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。
线性表的优点
线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
特征
1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有唯一的后继(后件)。
4．除第一个元素之外，均有唯一的前驱(前件)。
基本操作
1.MakeEmpty(L) 这是一个将L变为空表的方法
2.Length（L） 返回表L的长度，即表中元素个数
3.Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
4.Prior（L，i） 取i的前驱元素
5.Next（L，i） 取i的后继元素
6.Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
7.Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
8.Delete（L，p） 从表L中删除位置p处的元素
9.IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
10.Clear（L）清除所有元素
11.Init（L）同第一个，初始化线性表为空
12.Traverse（L）遍历输出所有元素
13.Find（L，x）查找并返回元素
14.Update（L，x）修改元素
15.Sort（L）对所有元素重新按给定的条件排序
16. strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
线性表的存储结构
线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。
顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链
线性表的结构特点
1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。
刷题
理论知识了解后就可以动手做题了：
- 求解一元多项式的值-顺序存储
【问题描述】一个形如a0x0+a1x1+…+anx^n的一元多项式含有n+1项，每一项由系数和指数唯一确定，可表示成由系数项和指数项构成的一个二元组(系数,指数)，一元多项式则可以表示成二元组的集合{(a0,0),(a1,1),(a2,2)…(an,n)}，可看成是数据元素为二元组(系数,指数)的线性表，若将某一个一元多项式的二元组集合采用顺序存储结构存储于顺序表中，请根据给定的x值，求解一元多项式的值。
例如：A(x)=3x2-4x6+6x8+10x9可表示成{(3,2),(-4,6),(6,8),(10,9)}，含有4个元素的线性表，采用顺序表存储。
下列的createPolyList函数，用于创建含有n项的一元多项式的顺序表存储结构，getValue函数则根据给定的一元多项式顺序表L和x值，求解并返回一元多项式的值。请将程序补充完整。
【输入形式】
第一行：一元多项式的项数
第二行：一元多项式的每一项的系数项和指数项，中间用空格间隔
第三行：一元多项式的x的取值
【输出形式】计算结果
【样例输入】
4
3 2 -4 6 6 8 10 9
1
【样例输出】15
#include <iostream>
#include <cstdlib>
using namespace std;
struct PolyNode
{double coef;int exp;
};
struct SqList
{PolyNode *elem;int length;int listsize;
};void initList(SqList &L,int n)
{L.elem=(PolyNode *)malloc(sizeof(PolyNode)*n);if(L.elem==NULL){cout<<"overflow";exit(0);}L.length=0;L.listsize=n;
}void add(SqList&L,PolyNode x)
{if(L.length>=L.listsize){PolyNode *base;base=(PolyNode *)realloc(L.elem,sizeof(PolyNode)*(L.listsize+10));if(base==NULL){cout<<"overflow";exit(0);}L.elem=base;L.listsize+=10;}L.elem[L.length]=x;L.length++;
}void createPolyList(SqList &L,int n)
{PolyNode e;initList(L,n);for(int i=1; i<=n; i++){cin>>e.coef>>e.exp;add(L,e);}
}double getValue(SqList &L, double x)
{double result = 0.0;double term = 1.0; for (int i = 0; i < L.length; i++){for (int j = 0; j < L.elem[i].exp; j++){term *= x;}result += L.elem[i].coef * term;term = 1.0;}return result;
}int main()
{SqList L;int n;double x;cin>>n;createPolyList(L,n);cin>>x;cout<<getValue(L,x);return 0;
}
- 求解一元多项式的值-单链表
#include <iostream>
#include <cstdlib>
using namespace std;
struct PolyNode
{double coef;int exp;
};
struct LNode
{PolyNode data;LNode *next;
};
typedef LNode *LinkList;void createPolyList(LinkList &L,int n)
{L=new LNode;L->next=NULL;LNode *r,*p;r=L;for(int i=1; i<=n; i++){p=new LNode;cin>>p->data.coef>>p->data.exp;r->next=p;r=p;}r->next=NULL;
}double getValue(LinkList L, double x)
{double result = 0.0;LNode *p = L->next;while (p != NULL){double term = 1.0;for (int i = 0; i < p->data.exp; i++){term *= x;}result += p->data.coef * term;p = p->next;}return result;
}int main()
{LinkList L;int n;double x;cin>>n;createPolyList(L,n);cin>>x;cout<<getValue(L,x);return 0;
}- 一元多项式相加-顺序存储
#include <bits/stdc++.h>
using namespace std;
struct PolyNode
{double coef;int exp;
};
struct SqList
{PolyNode *elem;int length;int listsize;
};void initList(SqList &L,int n)
{L.elem=(PolyNode *)malloc(sizeof(PolyNode)*n);if(L.elem==NULL){cout<<"overflow";exit(0);}L.length=0;L.listsize=n;
}void add(SqList &L,PolyNode x)
{if(L.length>=L.listsize){PolyNode *base;base=(PolyNode *)realloc(L.elem,sizeof(PolyNode)*(L.listsize+10));if(base==NULL){cout<<"overflow";exit(0);}L.elem=base;L.listsize+=10;}int j=L.length-1;while(j>=0&&L.elem[j].exp>x.exp){L.elem[j+1]=L.elem[j];j--;}L.elem[j+1]=x;L.length++;
}void createPolyList(SqList &L,int n)
{PolyNode e;initList(L,n);for(int i=1; i<=n; i++){cin>>e.coef>>e.exp;add(L,e);}
}void printItem(double coef,int exp)
{if(fabs(coef)!=1){cout<<fabs(coef);}if(exp==1)cout<<"X";elsecout<<"X^"<<exp;
}
void printPoly(SqList L)
{if(L.length==0){cout<<0;return;}if(L.elem[0].exp==0)cout<<L.elem[0].coef;else{if(L.elem[0].coef<0)cout<<"-";printItem(L.elem[0].coef,L.elem[0].exp);}int i=1;while (i<L.length){if(L.elem[i].coef>0)cout<<"+";elsecout<<"-";printItem(L.elem[i].coef,L.elem[i].exp);i++;}cout << endl;
}SqList polyAdd(SqList La, SqList Lb)
{SqList Lc;int i = 0, j = 0;initList(Lc, La.length + Lb.length);while (i < La.length && j < Lb.length){if (La.elem[i].exp < Lb.elem[j].exp){add(Lc, La.elem[i]);i++;}else if (La.elem[i].exp > Lb.elem[j].exp){add(Lc, Lb.elem[j]);j++;}else{double sum_coef = La.elem[i].coef + Lb.elem[j].coef;if (fabs(sum_coef) > 1e-6) {PolyNode sum_node;sum_node.coef = sum_coef;sum_node.exp = La.elem[i].exp;add(Lc, sum_node);}i++;j++;}}while (i < La.length){add(Lc, La.elem[i]);i++;}while (j < Lb.length){add(Lc, Lb.elem[j]);j++;}return Lc;
}int main()
{SqList La,Lb,Lc;int m,n;cin>>m>>n;createPolyList(La,m);createPolyList(Lb,n);Lc=polyAdd(La,Lb);printPoly(Lc);return 0;
}
- 一元多项式相加-单链表
#include <iostream>
using namespace std;
struct PolyNode {int exp;int coef;PolyNode *next;
};
typedef PolyNode *PLinkList;
PolyNode *getPrior(PLinkList L, int exp) {PolyNode *pre;pre = L;while (pre->next && pre->next->exp <= exp) {pre = pre->next;}return pre;
}
void createPLinkList(PLinkList &L, int n) {L = new PolyNode;L->next = NULL;PolyNode *p, *q;for (int i = 1; i <= n; i++) {p = new PolyNode;cin >> p->coef >> p->exp;q = getPrior(L, p->exp);p->next = q->next;q->next = p;}
}
void printPList(PLinkList L) {PolyNode *p;p = L->next;if (p) {cout << p->coef;if (p->exp != 0)cout << "X^" << p->exp;}p=p->next;while (p) {if(p->coef>0){cout<<"+"<<p->coef;}else{cout<<p->coef;}if (p->exp != 0)cout << "X^" << p->exp;p = p->next;}cout << endl;
}
void polyAdd(PLinkList &La, PLinkList &Lb)
{PolyNode *pa = La->next;PolyNode *pb = Lb->next;PolyNode *pc = La;while (pa && pb){if (pa->exp < pb->exp){pc->next = pa;pa = pa->next;pc = pc->next;}else if (pa->exp > pb->exp){pc->next = pb;pb = pb->next;pc = pc->next;}else{int sum_coef = pa->coef + pb->coef;if (sum_coef != 0){pa->coef = sum_coef;pc->next = pa;pa = pa->next;pb = pb->next;pc = pc->next;}else{PolyNode *temp = pa;pa = pa->next;delete temp;temp = pb;pb = pb->next;delete temp;}}}while (pa){pc->next = pa;pa = pa->next;pc = pc->next;}while (pb){pc->next = pb;pb = pb->next;pc = pc->next;}pc->next = NULL;}
int main() {PLinkList La, Lb;int m,n;cin>>m>>n;createPLinkList(La, m);createPLinkList(Lb, n);polyAdd(La, Lb);printPList(La);return 0;
}