【C++线性表总结】期末考试救急！！！
线性表（顺序存储结构&链式存储结构）顺序存储结构，第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 分配成功返回指向该内存的地址，失败则返回 NULLif(!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==x) return i;}return -1;} //插入元素，将指定元素插入到指定下标Status InsertElem(SqList&L,int p,ElemType x) {//判断插入下标的合法性if(p<0||p>L.length-1) return ERROR;//判断存储空间是否够用 //realloc() 修改所指向的内存块的大小，并将新的内存指针返回。//第一个参数为需要重新分配的内存空间指针，第二个参数为新的内存空间的大小//realloc 分配成功返回指向该内存的地址，失败则返回 NULLif(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=L.data;} L.data=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; //删除操作for(int i=p;i<L.length;i++){ L.data=L.data;} L.length--;return OK;}//显示顺序表void DisplayList(SqList L){for(int i=0;i<L.length;i++){ cout<<L.data<<" ";}cout<<endl;} //获得指定位置的元素，并将获得的值赋值给变量eStatus GetElem(SqList L,int p,ElemType&e){//判断下标的合法性if(p<0||p>L.length-1) return ERROR;e=L.data;return OK;} //向顺序表中写入数据int main(){SqList L;InitList(L);int n;cout<<"请输入顺序表的长度：";cin>>n;cout<<"请写入顺序表的数据：";for(int i=0;i<n;i++){ cin>>L.data; 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;}
https://blog.51cto.com/u_15397571/4787861
页:
[1]