首页 > 代码库 > 数据结构（C++）——线性表
数据结构（C++）——线性表
线性表在数据结构中的基础章节，通过线性表的学习可以让我们对数据结构有一个基本的认识。下面是我对线性表的一些理解。
首先线性表的学习可以概括为三点：
- 数据描述。
- 数据存储。
- 数据操作。
1、数据描述
线性表的数据元素具有抽象（及不确定）的数据类型，只有在设计具体的应用程序时，数据元素的抽象类型将被具体的数据类型所取代，比如：字符型（char）、整型（int）、结构体类型（struct）等等。下面我就把一张成绩表用结构体类型描述出来。
如图，如何将这这些数据封装为一个数据类型呢？C++中用的是类（class），这里为了简便使用开放式的结构体类型封装。
struct StuGrade{ string num; string name; char sex; float Math; float Engl; float Comp;};
这样，我们就定义了一种新的数据类型（StuGrade），而这种数据类型包含了学生成绩所要求的所有数据，在进行数据处理时就不用对这些繁琐的数据单个进行处理，只需要找到学生编号，通过这个结构体数据类型进行处理。
2、数据存储
数据存储在线性表里有两种：一是顺序存储结构，简称顺序表。二是链式存储结构，简称链表。
- 顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。因为顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址（即基地址），计算任何一个元素的存储地址的时间是相等的，所以它的优点是：随机存取（即按下标可以随机访问顺序表中任何一个数据元素，时间开销小。O（1））。但也因为顺序表利用数组元素在物理位置（及数组下标）上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺序表具有以下缺点：
（1）表的容量难以确定。数组的长度必须事先确定。
（2）插入和删除操作需要移动大量元素。
（3）造成存储空间的“碎片”。这是因为数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如果不连续便无法使用，这便造成了存储空间“碎片”现象。
- 链表是为了克服顺序表的的缺点，采用的动态存储分配来存储线性表。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。而且插入删除操作也非常方便。唯一的缺点就是访问链表中的节点不是很方便。链表中的节点，需从头指针顺着链表扫描才能取得。
使用链表存储数据时，在每个节点包括两个部分：数据域和指针域，数据域存放需要的数据，指针域存放下一个节点的地址，如上面的结构体类型如果要运用链表存储，需在结构体结尾增添指针域。
struct StuGrade{ string num; string name; char sex; float Math; float Engl; float Comp; StuGrade *next;//指针域};
3、数据操作
无论线性表用哪种方式存储，最终还是为了数据处理方便。在线性表中，数据处理包括初始化、查找、插入、删除、遍历等等。用类封装起来就是：
用数组方式：
const int MaxSize=10;class SeqList{public: SeqList(); //无参构造函数，建立一个空的顺序表 SeqList(StuGrade a[],int n); //有参构造函数，建立一个长度为n的顺序表 ~SeqList(){} int Length(); //求线性表的长度 StuGrade Get(int i); //按位查找 int Locate(StuGrade x); //按值查找 void Insert(int i,StuGrade x); //插入操作 void Delete(int i); //删除操作 void PrintList(); //遍历操作private: StuGrade data[MaxSize]; int length;};
其中插入与删除函数是重点，我这里就给实现一下：
SeqList::SeqList(StuGrade a[],int n) //有参构造函数，建立一个长度为n的顺序表 { if(n>MaxSize)throw int(1); for(int i=0;i<n;i++) data[i]=a[i]; length=n;}void SeqList::Insert(int i,StuGrade x) //插入函数{ char a; if(length>=MaxSize)throw a; if(i<1||i>length+1)throw float(0.5); for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++;}void SeqList::Delete(int i) //删除函数{ if(length==0)throw double(0.55); if(i<1||i>length)throw float(0.5); for(int j=i;j<length;j++) data[j-1]=data[j]; length--;}void SeqList::PrintList() //遍历函数{ for(int i=0;i<length;i++) cout<<data[i].num<<‘\t‘<<data[i].name<<‘\t‘<<data[i].sex<<‘\t‘<<data[i].Math<<‘\t‘<<data[i].Engl<<‘\t‘<<data[i].Comp<<endl;}
int main(){ StuGrade stu[2]; for(int i=0;i<2;i++) { cout<<"请输入第"<<i+1<<"位学生学号:"<<endl; cin>>stu[i].num; cout<<"请输入该学生姓名:"<<endl; cin>>stu[i].name; cout<<"请输入该学生性别:"<<endl; cin>>stu[i].sex; cout<<"请输入该学生数学成绩:"<<endl; cin>>stu[i].Math; cout<<"请输入该学生英语成绩"<<endl; cin>>stu[i].Engl; cout<<"请输入该学生计算机成绩"<<endl; cin>>stu[i].Comp; } SeqList Grade(stu,2); try{ Grade.Insert(2,stu[0]); Grade.Delete(1); Grade.PrintList(); } catch(int){cout<<"参数非法"<<endl;} catch(char){cout<<"上溢"<<endl;} catch(float){cout<<"删除位置不当"<<endl;} catch(double){cout<<"下溢"<<endl;} return 0;}
为了测试这个顺序表，其中加入了构造函数和遍历函数以及主函数，运行后并未出错。
用链表方式：
class SeqList{public: SeqList(); //无参构造函数，建立一个空的链表 SeqList(StuGrade a[],int n); //有参构造函数，建立有n个元素的单链表 ~SeqList(){} int Length(); //求单链表的长度 StuGrade Get(int i); //按位查找 int Locate(StuGrade x); //按值查找 void Insert(int i,StuGrade x[]); //插入操作 void Delete(int i); //删除操作 void PrintList(); //遍历操作private: StuGrade *first; //单链表的头指针};
同样，为了测试这个类，我将其实现了一下，运行同样未出错。
SeqList::SeqList(StuGrade a[],int n) //有参构造函数，建立有n个元素的单链表{ StuGrade *head=NULL,*tail=NULL,*temp; head=new StuGrade; if (head==NULL) { cout << "No memory available!"; exit(1); } else { head->num=a[0].num; head->name=a[0].name; head->sex=a[0].sex; head->Math=a[0].Math; head->Engl=a[0].Engl; head->Comp=a[0].Comp; head->next=NULL; tail=head; } temp=new StuGrade; if (temp==NULL) { cout << "No memory available!"; exit(1); } else { for(int i=1;i<n;i++) { temp->num=a[i].num; temp->name=a[i].name; temp->sex=a[i].sex; temp->Math=a[i].Math; temp->Engl=a[i].Engl; temp->Comp=a[i].Comp; temp->next=NULL; tail->next=temp; tail=temp; } } first=new StuGrade; first=head;}void SeqList::Insert(int i,StuGrade *x) //插入操作{ StuGrade *p; p=new StuGrade; p=first; int count=1; while(p!=NULL&&count<i-1) { p=p->next; count++; }; if(p==NULL) { cout<<"插入位置溢出！"<<endl; exit(1); } else { x->next=p->next; p->next=x; }}void SeqList::Delete(int i) //删除操作{ StuGrade *preNode=NULL;//指向当前节点的前驱节点 StuGrade *curNode=first;// 指向当前节点 int count=0; while(curNode&&count<i-1) { preNode = curNode; // 当前节点变为前驱节点 curNode = curNode->next; count++; }; if (curNode == NULL) { cout<<"Can‘t find "<<i<<" in the list"<<endl; exit(0); }; if(preNode==NULL) //删除链首节点 { first=first->next; } else { preNode->next=curNode->next; }}void SeqList::PrintList() //遍历操作{ StuGrade *p=first; while(p) { cout<<p->num<<‘\t‘<<p->name<<‘\t‘<<p->sex<<‘\t‘<<p->Math<<‘\t‘<<p->Engl<<‘\t‘<<p->Comp<<endl; p=p->next; }}int main(){ StuGrade stu[2]={{"1345536126","张大丰",‘M‘,77,77,77},{"1345536127","张二丰",‘F‘,99,99,99}};/* for(int i=0;i<2;i++) { cout<<"请输入第"<<i+1<<"位学生学号:"<<endl; cin>>stu[i].num; cout<<"请输入该学生姓名:"<<endl; cin>>stu[i].name; cout<<"请输入该学生性别:"<<endl; cin>>stu[i].sex; cout<<"请输入该学生数学成绩:"<<endl; cin>>stu[i].Math; cout<<"请输入该学生英语成绩"<<endl; cin>>stu[i].Engl; cout<<"请输入该学生计算机成绩"<<endl; cin>>stu[i].Comp; }*/ StuGrade *k; k=new StuGrade; k=&stu[0]; SeqList Grade(stu,2); Grade.Insert(1,k); Grade.Delete(2); Grade.PrintList();}
至此，对线性表这章学习基本上有个了解，后面关于双链表和循环链表以及顺序表和链表的时间性能比较我以后再更新。
因为经验不足，文章中有待对算法进一步优化以及代码的进一步精简，希望大家指教！
数据结构（C++）——线性表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。