给出线性表的顺序实现:
代码如下:
//线性表的顺序存储实现 #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; typedef struct { ElementType Data[MAXSIZE]; int Last; }List; List L,*Ptrl; List *makeEmpty()//初始化 { List *ptrL; ptrL=(List *) malloc(sizeof(List)); ptrL->Last=-1; return ptrL; } int find(ElementType x,List *ptrL)//查找 { int i=0; while(i<=ptrL->Last&&ptrL->Data[i]!=x) { i++ } if(i>ptrL->Last) return -1; else return i; } void insert(ElementType x,int i,List *ptrL) { int j; if(ptrL->Last==<MAXSIZE-1) { printf("表满"); return ; } if(i<1||i>ptrL->Last+2) { printf("位置不合法"); return ; } for(j=ptrL->Last; j>=i-1; j--) ptrL->Data[j+1]=ptrL->Data[j]; ptrL->Data[i+1]=X; ptrL->Last++; return; } void delete(int i,List *ptrL) { int j; if(i<1||i>ptrL->Last+1) { printf("元素不存在!"); return; } for(j=i; j<=ptrL->Last; j++) ptrL->Data[j-1]=ptrL->Data[j]; ptrL->Last--; return ; } int main() { /* 如果把后移数组元素的循环 for ( j = PtrL->Last; j >= i-1; j-- ) PtrL->Data[j+1]=PtrL->Data[j]; 改为 for ( j = i-1; j <= PtrL->Last; j++ ) PtrL->Data[j+1]=PtrL->Data[j]; 那会是什么后果? 结果:分量Data[i-1]到Data[Ptrl->Last+1]都是同一个值,即移之前Data[i-1]的值*/ }
代码如下:
//线性表的链式存储实现 #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; typedef struct { ElementType Data; struct Node *Next; } List; List L,*PtrL; int Length(List *PtrL)/*采用循环遍历一遍的方法,当指向为空(null),返回j,时间性能为o(n)*/ { List *p=PtrL;/*p指向表的第一个结点*/ int j=0; while(p) { p=p->Next; j++;/*当前p指向的是第j个结点*/ } return j; } List *FindKth(int K,List *PtrL)/*按序号查找,时间性能为o(n)*/ { List *p=PtrL; int i=1; while(p!=NULL&&i<K) { p=p->Next; i++; } if(i==K) return p;/*找到第K个,返回指针*/ else return NULL;/*否则返回空*/ } List *Find(ElementType X,List *Ptrl)/*按值查找,时间性能为o(n)*/ { List *p=Ptrl; while(p!=NULL&&p->Data!=X) p=p->Next; return p; } List *Insert(ElementType X,List *Ptrl)//s->Next指向s,从而不能正确完成插入 { List *p,*s; if(i==1)/*新结点插入在表头*/ { s=(List*)malloc(sizeof(List));/*申请,填充结点*/ s->Data=X; s->Next=Ptrl; return s;/*返回新表头指针*/ } p=FindKth(i-1,PtrL);/*查找第i-1个结点*/ if(p==NULL)/*第i-1个不存在,不能插入*/ { printf("参数i错"); return NULL; } else { s=(List*)malloc(sizeof(List));/*申请,填充结点*/ s->Data=X; s->Next=p->Next;/*新结点插入在第i-1个结点的后面*/ p->Next=s; return Ptrl; } } List *Delete(int i,List *PtrL)/*平均查找次数n/2,时间性能o(n)*/ { List *p,*s; if(i==1)/*若要删除的是表的第一个结点*/ { s=PtrL;/*指向第1个结点*/ if(PtrL!=NULL) PtrL=PtrL->Next; else return NULL; free(s);/*释放被删除结点*/ return PtrL; } P=FindKth(i-1,PtrL);/*查找第i-1个结点*/ if(p==NULL) { printf("第%d 个结点不存在",i-1); return NULL; } else if(p->Next==NULL) { printf("第%d 个结点不存在",i);return NULL; } else { s=p->Next;/*指向第i个结点*/ p->Next=s->Next/*从链表中删除*/ free(s);/*释放被删除结点*/ return PtrL; } }