【C++线性表总结】期末考试救急！！！

PHP小丑

线性表（顺序存储结构&链式存储结构）
顺序存储结构，第n个数据元素的存储地址是LOC(an) = LOC(a1)+(n-1)k  其中k表示每个数据元素占用的存储单元的长度)显而易见，这种存储结构，相邻元素在物理位置上也相邻。
通常，我们把采用这种存储结构的线性表称为“顺序表”。
链式存储结构，对于数据元素a1来说，除了存储其自身的信息之外，还需要存储一个指示其直接后继的信息，所以我们引入指针的概念：称存储数据元素信息的域称为数据域，而存储直接后继地址信息的域称为指针域。
我们形象地称这种即包含自身数据信息，又包含其直接后继地址信息的数据元素为“结点”。显而易见，这种存储结构，相邻元素在物理位置上不一定相邻，他们之间用指针来表示逻辑关系。
通常，我们把采用这种存储结构的线性表称为“线性链表”。
​

所有相关函数汇总：
​
顺序表：

#include<iostream>#include<cstdlib>using namespace std;//传参问题 &/ /* //对引用的所有操作等同于对原对象的所有操作。引用代替指针带来了更干净的代码，可以避免某些bug，比如空指针问题 //直接传参则是传值，当不需要修改原对象时直接传参即可 //顺序表的定义#define MAXSIZE 20#define ADDSIZE 10  //空间不够时每次分配的增量 typedef int ElemType;typedef int Status;#define OK 0#define ERROR -1 typedef struct{  ElemType*data;  int length;  // 顺序表当前长度   int listsize;}SqList;//顺序表的初始化 Status InitList(SqList &L){  L.data=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));  //malloc 分配成功返回指向该内存的地址，失败则返回 NULL  if(!L.data) return ERROR;  L.length=0;  L.listsize=MAXSIZE;  return OK;  } //按值查找元素,找到返回下标，否则返回-1int LocateElem(SqList L,ElemType x){  for(int i=0;i<L.length;i++)  {  if(L.data[i]==x) return i;  }  return -1;} //插入元素，将指定元素插入到指定下标  Status InsertElem(SqList&L,int p,ElemType x) {  //判断插入下标的合法性  if(p<0||p>L.length-1) return ERROR;  //判断存储空间是否够用   //realloc() 修改所指向的内存块的大小，并将新的内存指针返回。  //第一个参数为需要重新分配的内存空间指针，第二个参数为新的内存空间的大小  //realloc 分配成功返回指向该内存的地址，失败则返回 NULL  if(L.length>MAXSIZE)  {  ElemType*newbase=(ElemType*)realloc(L.data,(MAXSIZE+ADDSIZE)*sizeof(ElemType));  if(!newbase) return ERROR;  L.data=newbase; //改为新基址   L.listsize+=ADDSIZE; //增加了存储容量   }  //插入操作  for(int i=L.length-1;i>=p;i--)  {  L.data[i+1]=L.data[i];  }   L.data[p]=x;  L.length++;  return OK; } //删除下标为p的元素，并将该元素的值赋值给变量eStatus DeleteElem(SqList &L,int p,ElemType&e){  //判断下标的合法性  if(p<0||p>L.length-1) return ERROR;  //赋值操作  e=L.data[p];   //删除操作  for(int i=p;i<L.length;i++)  {  L.data[i]=L.data[i+1];  }   L.length--;  return OK;}//显示顺序表void DisplayList(SqList L){  for(int i=0;i<L.length;i++)  {  cout<<L.data[i]<<" ";  }  cout<<endl;} //获得指定位置的元素，并将获得的值赋值给变量eStatus GetElem(SqList L,int p,ElemType&e){  //判断下标的合法性  if(p<0||p>L.length-1) return ERROR;  e=L.data[p];  return OK;} //向顺序表中写入数据int main(){  SqList L;  InitList(L);  int n;  cout<<"请输入顺序表的长度：";  cin>>n;  cout<<"请写入顺序表的数据：";  for(int i=0;i<n;i++)  {  cin>>L.data[i];  L.length++;  }   //测试各函数  DisplayList(L);  int temp1;  GetElem(L,2,temp1);  cout<<"下标为2的值为："<<temp1<<endl;  int temp2;  DeleteElem(L,4,temp2);  cout<<"删除下标为4的元素： "<<temp2<<endl;  cout<<"现在的顺序表为：";  DisplayList(L);  cout<<endl;  InsertElem(L,5,666);  cout<<"在下标为5的下标处，插入666之后的顺序表为：";   DisplayList(L);  cout<<endl;  }

链表：
》》添加结点（头插法/尾插法）
头插法：

尾插法：
​
》》链表结点的删除
​

#include<iostream>#include<cstdlib>using namespace std;#define OK 0#define ERROR -1//链表的结点 //一个结点包含数据域和指针域，数据域用来存放数据，指针域负责指向其他结点typedef int ElemType;typedef int Status;typedef struct Node{  ElemType data;  struct Node*next;}*LinkList,LNode;//链表的创建（头插法、尾插法） //创建的所有结点都应该是结构体指针类型，创建时不要忘记分配空间 //头插法创建单链表（逆序建立链表） LinkList HeadInsertCreat(LinkList head){  head=(LinkList)malloc(sizeof(LNode));  head->next=NULL;  cout<<"请输入需要插入的结点个数：";  int n;  cin>>n;  LNode *node=NULL; //定义新结点，指针初始化为空   cout<<"请输入需要插入的数据：";  for(int i=0;i<n;i++)  {  node=(LinkList)malloc(sizeof(LNode));  cin>>node->data;  node->next=head->next;  head->next=node;  }  return head;} //尾插法创建单链表(顺序建立链表)LinkList TailInsertCreat(LinkList head){  head=(LinkList)malloc(sizeof(LNode));  head->next=NULL;  LNode *tail=NULL;  tail=head;  cout<<"请输入需要插入的结点个数：";  int n;  cin>>n;  LNode *node=NULL;  cout<<"请输入需要插入的数据：";  for(int i=0;i<n;i++)  {  node=(LinkList)malloc(sizeof(LNode));  cin>>node->data;  tail->next=node;  tail=node;  }  tail->next=NULL;  return head;} //输出显示链表数据Status DisplayLinkList(LinkList L){  LinkList p;  //判断是否为空  if(L->next==NULL) return ERROR;   else  {  for(p=L->next;p!=NULL;p=p->next) cout<<p->data<<" ";  }  cout<<endl;  return OK;}//删除结点、链表的删除 Status DeleteLinkList(LinkList L,int i,ElemType&e){  LinkList p;  int j;  if(i<0||L->next==NULL) return ERROR; //判断是否为空、指定删除的下标是否合理  //j=i时退出循环 ，此时p在下标i-1的位置，p->next指向要删除的结点   for(p=L,j=0;p->next&&j<i;p=p->next,j++);  if(p->next==NULL) return ERROR;  //删除操作  LinkList q;  q=p->next;  //用 q 临时指向要删除元素   e=q->data;  p->next=q->next; //删除  free(q);  return OK; } //两个链表(都分别为递增序列)合并成一个新链表，要求合并之后的序列递增（可相同的值在一起）Status MergeLinkList(LinkList L1,LinkList L2,LinkList&L){  //创建新链表  L=(LinkList)malloc(sizeof(LNode));  //判断为空链表的情况   LinkList pa,pb;  pa=L1->next;  pb=L2->next;  if(pa==NULL&&pb==NULL) return ERROR;  //合并  LinkList pc=L;   while(pa&&pb)  {  if(pa->data<=pb->data)  {    pc->next=pa;    pc=pa;    pa=pa->next;  }  else  {    pc->next=pb;    pc=pb;    pb=pb->next;  }  }   if(pa) pc->next=pa;  else pc->next=pb;  return OK;} //函数的测试和使用int main(){  LinkList L1,L2;  cout<<"测试头插法逆序建立单链表A：";  L1=HeadInsertCreat(L1);  DisplayLinkList(L1);  cout<<endl;  cout<<"测试尾插法逆序建立单链表B：";  L2=TailInsertCreat(L2);  DisplayLinkList(L2);  cout<<endl;  cout<<"测试删除单链表A中下标为2的结点，并把该结点的数据赋值给变量e：";  ElemType e;   DeleteLinkList(L1,2,e);  cout<<"删除的该结点中的数据为："<<e<<endl;  cout<<"测试合并两个链表A和B："<<endl;  cout<<"合并前A:(已保证输入后创建的是增序列) "<<endl;  DisplayLinkList(L1);  cout<<endl;  cout<<"合并前B:(已保证输入后创建的是增序列) "<<endl;  DisplayLinkList(L2);  cout<<endl;  cout<<"合并后: "<<endl;  LinkList L;  MergeLinkList(L1,L2,L);  DisplayLinkList(L);  cout<<endl;  return 0;}